4 ms·

And if you really need it you can even do both tree and vector simultaneously - just make sure both consist of pointers only so you avoid update/sync issues.

• bluGill 4y ago
  You can, but probably shouldn't. The pointers means a cache miss when you follow it. Putting everything in the vector is the point, otherwise the map is potentially faster
  • jcelerier 4y ago
    If you have to do a binary search in a million elements you'll have cache misses anyways
    • bluGill 4y ago
      Sure, ln cache misses. With a linear search through pointers you have n cache misses.