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

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

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

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

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

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

Конечно, я могу слегка модифицировать код, возвращать, например trie* из insert(), а корень объявить тоже как указатель. Типа так

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

int main() {
    string s = "test me";
    trie t;
    trie* tp = &t;
    for (auto c : s) {
         tp = tp->insert(c);
    }
}

Но... это же уродство какое-то А как можно сделать красиво, безопасно и одиоматически?

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

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

C>

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

C>Но... это же уродство какое-то А как можно сделать красиво, безопасно и одиоматически?

В подобных структурах проще писать на голых указателях или кастомных обёртках. Посмотри на коллекции STL, например.

Здравствуйте, 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> 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 оба их реализовать..

week_ptr ?

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

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

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

Может он хочет сделать аналог llvm::ImmutableMap?
https://llvm.org/doxygen/ImmutableMap_8h_source.html
Тогда тут как раз указатели со счётчиком ссылок в самый раз

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

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

// ноду нельзя копировать
struct trie_node {
  std::unordered_map<char, unique_ptr<trie_node> > children;
};

// сам трай с подсчётом ссылок и копируй сколько хочешь
struct trie {
  std::shared_ptr<trie_node> root;
};