std::unordered_map is a Joke

http://www.reedbeta.com/blog/data-oriented-hash-table/

I'm not laughing

>>1

For instance, inserting or removing values in the middle of the sequence—something lists are supposed to be good at—is actually faster with an array, if the elements are a POD type and no bigger than 64 bytes (i.e. one cache line) or so! It turns out to actually be faster to shift around the array elements on insertion/removal than to first traverse the list to find the right position and then patch a few pointers to insert/remove one element. That’s because of the many cache misses in the list traversal, compared to relatively few for the array shift. (For larger element sizes, non-POD types, or if you already have a pointer into the list, the list wins, as you’d expect.)

Lists confirmed worst data structure again.

cache misses

IIRC, the C++ standard does not assume the existence of a ``cache".

>>4
the standard shouldn't consider it because it's hardware agnostic, but the implementations on modern architectures should

Arrays with cached edits?

>>6
3Arrays:
New array(realloc if < current_size),Old Array(switches to New Array, as if it was a Framebuffer backpage, with realloc if <current_size)
Stack edit array: elements are {edit operation,element number,new value}; when it fills, all edits are performed in New Array(resized by keeping current_size consistent with edit ops(by +/- for each new stack item)),Old Array is repurposed as next New Array.

Plast C Arrays will always be the fastest data structure, because they are 1:1 representation of physical memory. Editing the array doesn't need to be slow,e.g. instead of removing elements ->set it to null element.
insertion is the only operation that is slow and is usually resolved by changing the requirement to insert only at the end(append-only) while
sorting/ purging null elements will be only performed explicitly(like flush to disk).

>>7
What if its 1TB array and you have only 1TB RAM?

>>9
You get 2TB RAM and do it again.

Could use an edit marker in the old array to tell it to read the cache rather than scanning the cache for every read between edit and flush