Информация об изменениях

Сообщение Re: Рекурсивные структуры данных и современный С++ от 01.02.2022 13:21

Изменено 01.02.2022 13:50 watchmaker

Старый текст
Новый текст
Разница

Re: Рекурсивные структуры данных и современный С++

Здравствуйте, cppguard, Вы писали:

C>Как их правильно готовить? Допустим, хотим реализовать trie в виде
C>но таким образом удаляется коструктор копирования по-умолчанию (из-за присутствия unique_ptr)

Добавлять конструктор копирования для сложных структур данных — опасное решение из-за того, что можно легко и неявно просадить производительность.
Я не говорю, что это никогда не нужно. Но скорее стоит задуматься, а точно ли плюсы перевесят возможность ошибки.

C>Можно теперь заменить контейнер указателя на shared_ptr, но тогда все добавляется подсчёт ссылок,

Гораздо важнее другое: теперь при копировании новые объекты будут ссылаться на общие узлы. Поменял содержимое в одном и оно поменяется в копии — совсем другая семантика.

C>Если бы, ну чисто теоретически, конструктор копирования по-умолчанию присутствовал
У unique_ptr не просто так нет конструктора копирования. Но если нужно, то сделай свой умный указатель с копированием и используй его.

условно так

template <typename T>
class cloning_ptr {

    cloning_ptr(const cloning_ptr& other) {        // copy contructor
        if (other != nullptr) {
            holder = make_unique<T>(*other);
        }
    }

    cloning_ptr(cloning_ptr&& other) = default;    // move constructor
            
    // other accessors

private:
    unique_ptr<T> holder; 
};

C>Как их правильно готовить? Допустим, хотим реализовать trie в виде

C>

C>struct trie {
C>  std::unordered_map<char, unique_ptr<trie>> children;
C>};
C>

C>но таким образом удаляется коструктор копирования по-умолчанию (из-за присутствия unique_ptr). Можно теперь заменить контейнер указателя на shared_ptr, но тогда все добавляется подсчёт ссылок, время жизни объекта становится непонятным, ещё и барьеры синхронизации (а ведь нам говорили "you don't pay for what you don't use"). Как быть? Пример искусственный, можете представить любую рекурсивную структуру данных.

C>Если бы, ну чисто теоретически, конструктор копирования по-умолчанию присутствовал, до код построения дерева мог бы быть таким:

Скрытый текст

C>struct trie {
C>  std::unordered_map<char, unique_ptr<trie>> children;
C>  trie& insert(char c) noexcept {
C>    auto [i, ignored] = children.try_insert(c, std::make_unique<trie>());
C>    return *i->second;
C>  }

C>  void make_trie(const std::string& s) {
C>    trie root;
C>    for (auto c : s) {
C>      root = root.insert(c);  // compilation error: deleted copy ctor
C>    }
C>};
C>

Re: Рекурсивные структуры данных и современный С++

условно так

template <typename T>
class cloning_ptr {

    cloning_ptr(const cloning_ptr& other) {        // copy contructor
        if (other != nullptr) {
            holder = make_unique<T>(*other);
        }
    }

    cloning_ptr(cloning_ptr&& other) = default;    // move constructor
            
    // other accessors

private:
    unique_ptr<T> holder; 
};

C>Как их правильно готовить? Допустим, хотим реализовать trie в виде

C>

C>struct trie {
C>  std::unordered_map<char, unique_ptr<trie>> children;
C>};
C>

Скрытый текст

C>struct trie {
C>  std::unordered_map<char, unique_ptr<trie>> children;
C>  trie& insert(char c) noexcept {
C>    auto [i, ignored] = children.try_insert(c, std::make_unique<trie>());
C>    return *i->second;
C>  }

C>  void make_trie(const std::string& s) {
C>    trie root;
C>    for (auto c : s) {
C>      root = root.insert(c);  // compilation error: deleted copy ctor
C>    }
C>};
C>

Отличный пример, где отсуствие copy-конструктора помешало тебе совершить ошибку.
Это конечно не означает, что копирование не нужно. Скорее означает, что нужно понимать зачем оно нужно.

Грубо говоря, если владеющий указатель, а есть итератор. А ты пытаешься одним классом trie оба их реализовать..