[psurge]

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...

[stabbles]

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.

[psurge]

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

[codr7]

Very nice, had no idea.

Nodes it is then :)

Do you have any links to share describing the change?

Thanks!

[codr7]

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

[saagarjha]

> STL containers cannot have incomplete value types

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