Hey everyone, I was solving this trie problem. At first, I was trying to solve this using std::unordered_map which causes TLE, but then, I tried using static array, and then it worked fine.
Solution with std::unordered_map: (link) https://pastebin.com/LtLQ47fk
Solution using static array: (link) https://pastebin.com/BUDPhxXk
Is there is any way to optimize the std::unordered_map?
Is there any mistake in the unordered_map solution?
Is there something wrong?
Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).
You should highlight that this is a binary trie, of course that an unordered map is going to have a huge time/memory constant factor
But why? unordered_map is similar like an array, right?
Or there is something different about binary Trie.
Generally avoid using unordered containers because some tests may intentionally cause collisions and the complexity per operation can become $$$O(n)$$$.
This is not true for small data types as keys (byte and char)
Two main reasons:
Vectors of structs are allocated sequentially in memory. When your struct contains an unordered_map, the underlying storage for the map gets allocated elsewhere.
Unordered map needs to hash keys and index them into the underlying storage.
The first one is probably the more important factor here.
Thanks man :)