Simple Trie Implementation in C++11

Re:Simple Trie Implementation in C++11 by stabbles on Sunday July 21, 2019 @04:20PM (#20493420)

Is `shared_ptr` just used for convenience? I think `unique_ptr` would be excellent for this tree structure.

It's not too bad to traverse the tree using non-owning raw pointers.

[ Parent | on HN ]

Re:Simple Trie Implementation in C++11 by nemetroid on Sunday July 21, 2019 @04:25PM (#20493447)

I don't think there's need for smart pointers at all, really. The "children" member could just be an unordered_map<T, Node>.

Edit: on second thought, having a class contain a container of itself actually isn't allowed (though you would think it would be in cases like this).

Edit again: apparently it depends on the container. unordered_map does not allow instantiation with an incomplete type, but other containers do (e.g. vector or map).

[ Parent | on HN ]

Re:Simple Trie Implementation in C++11 by stabbles on Sunday July 21, 2019 @05:23PM (#20493749)

Yes, I was playing around with it as well. It seems the support has been out there for a while, but officially since C++17 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n437... was accepted, s.t. std::vector, std::list and std::forward_list can work with incomplete types:

   struct example {
     std::vector<example> xs;
   };

[ Parent | on HN ]

Re:Simple Trie Implementation in C++11 by saagarjha on Sunday July 21, 2019 @05:25PM (#20493769)

I believe containers can contain incomplete types as of C++17, but you cannot use their members.

[ Parent | on HN ]

Re:Simple Trie Implementation in C++11 by xorz57 on Sunday July 21, 2019 @06:11PM (#20493988)

Yes `unique_ptr` would be better!

[ Parent | on HN ]