Naithani's blog

DON'T use std::unordered_map for Trie
By Naithani, history, 4 years ago, In English

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?

  • Vote: I like it
  • -18
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Auto comment: topic has been updated by Naithani (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But why? unordered_map is similar like an array, right?

    Or there is something different about binary Trie.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      Generally avoid using unordered containers because some tests may intentionally cause collisions and the complexity per operation can become $$$O(n)$$$.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is not true for small data types as keys (byte and char)

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply