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...
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.
Thanks for pointing this out! I didn't know that C++17 had relaxed this restriction.
Very nice, had no idea.
Nodes it is then :)
Do you have any links to share describing the change?
Thanks!
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
> STL containers cannot have incomplete value types
As of C++17, certain containers have minimal support for incomplete types.
I did a quick re-implementation [0] taking these ideas into account. It also avoids assuming anything about inputs except iterating the key type and moves most functionality into Node to support more use cases.
I would consider switching the unordered_map to a sorted vector<pair<T, Node>>; or even better, move the key into Node and simply store as vector<Node>. Hash tables are relatively expensive to create in exchange for excellent performance for large tables, and you're creating a lot of tiny tables. A regular map would likely fall somewhere in between performance-wise since they're cheaper to create.