5 ms·

How did you get exactly a 3x slowdown? I thought unordered_map is a vector of vectors aka separate chaining?

• MauranKilom 5y ago
  No. unordered_map buckets are linked lists of nodes (key + value pairs). So you have one indexing into the bucket array to retrieve the list pointer, and then you may or may not have to chase an arbitrarily long linked list. But the nodes are necessarily allocated separately, so (assuming the bucket array is in cache [previous post should say 4 cachelines, not 3] and you don't have to chase beyond the first list element) you still have that indirection somewhere into memory. This all comes from the specification requiring even load factors arbitrarily close to 1 and to still have amortized constant time insertion, lookup and deletion.
  • Bancakes 5y ago
    That's horrid. I have some old code where adjacency matrices are unordered maps of unordered maps. Yikes.