title: Container Data Structure similar to std::vector and std::list
body: <p>I am currently developing (at Design-Stage) a kinda small compiler which uses a custom IR. The problem I am having is to choose an efficient container data structure to contain all the instructions.</p>
  
  <p>A basic block will contain ~10000 instructions and an instruction will be like ~250 Bytes big.</p>
  
  <p>I thought about using a list because the compiler will have lots of complex transformations (ie. lots of random insertions/removals) so having a container data structure which does not invalidate iterators would be good. As it would keep the transformation algorithm simple and easy to follow.</p>
  
  <p>On the other hand, it would be a lost of performance because of the known problem with cache misses and memory fragmentation. An std::vector would help here but I imagine it would be a pain to implement transformations with a vector.</p>
  
  <p>So the questions is, if there is another data structure which has low memory fragmentation to reduce memory cache misses and does not invalidate iterators.
  Or if I should ignore this and keep using a list.</p>