3 ms·

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

by psurge 7y ago

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_map-and-abslflat_hash_set https://abseil.io/docs/cpp/guides/container#abslflat_hash_ma...

stabbles 7y ago
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.
- codr7 7y ago
  Very nice, had no idea. Nodes it is then :) Do you have any links to share describing the change? Thanks!
- psurge 7y ago
  Thanks for pointing this out! I didn't know that C++17 had relaxed this restriction.
saagarjha 7y ago
> STL containers cannot have incomplete value types As of C++17, certain containers have minimal support for incomplete types.
deleted 7y ago
[deleted]
codr7 7y ago
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 https://github.com/codr7/cidk/blob/master/src/cidk/env.hpp