Simple Trie Implementation in C++11

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

I don't think Node can contain a std::vector<Node>, since STL containers cannot have incomplete value types. But maybe I'm misunderstanding you?

I think absl::flat_hash_map<T, std::unique_ptr<Node>> would be worth considering in this application. Keys and values are stored inline, so the memory and creation costs should be comparable to std::vector - https://abseil.io/docs/cpp/guides/container#abslflat_hash_ma...

[ Parent | on HN ]

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

Not all containers though, since C++17 std::vector, std::list and std::forward_list do support incomplete element types as long as the allocator meets certain requirements. So std::vector<Node> is definitely OK.

[ Parent | on HN ]

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

Thanks for pointing this out! I didn't know that C++17 had relaxed this restriction.

[ Parent | on HN ]

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

Very nice, had no idea.

Nodes it is then :)

Do you have any links to share describing the change?

Thanks!

[ Parent | on HN ]

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

True enough, my mistake :)

Just getting rid of the hash buckets and shared_ptrs would be a giant leap in the right direction.

Nice. I have no experience from absl, but I've sucessfully used sorted vectors to speed up these kinds of solutions on several occasions [0].

[0] https://github.com/codr7/cidk/blob/master/src/cidk/env.hpp

[ Parent | on HN ]

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

> STL containers cannot have incomplete value types

As of C++17, certain containers have minimal support for incomplete types.

[ Parent | on HN ]