Data Structure Performance Tradeoffs

Bad title. Datastructures always come with trade offs. In this case Insertion Speed and memory efficiency vs iteration and random access Speed.

A small savings for memory, but much faster. The link has benchmarks.

What specifically is wrong with vector? There have been a lot of hash maps done with flat memory to minimize allocations and pointer hopping over the STL but vector doesn't have those problems.

Please don't, because memory access pattern will be very different.

It is astonishing to me that the most basic of memory hacks are regarded as dark magics these days. Many things take zero extra effort to make orders of magnitude faster if you are simply aware of some basic concepts.For instance, if you know a collection of things is going to be bounded by a reasonable quantity (e.g. less than 1mm) and that you will frequently need to perform a full linear scan of these things, you should consider using an array rather than some b-tree or other pointer-chasi

Ugly special casing requires code that would detect those special cases. This adds overhead in terms of processing cycles and code. Most arrays, majority of the time, store a tiny amount of information. Less than a dozen entries. Doing that sort of detection is massive overkill and would actually hurt performance. You want to speed things up for the real world. Not artificial benchmarks. How many times in your code are you really going to need 100,000 integers in memory? Probably once in your en

All nicecly ordered in linear memory for good data locality?

It's a performance optimization for growing datastructures. If you can use all the space that was actually allocated, you can (on average) call realloc less often when the container is growing dynamically.

the time complexity of insert etc is superior and a good reason for abstraction on top of an array, I would think.

Would using a structure-of-arrays (instead of array-of-structues) make this less of a problem?