title: What container to choose for fast search/insert with huge amounts of data?
body: <p>So it's a thought experiment. I want to have a huge collection of structures such as:</p>
  
  <pre><code>struct
  {
      KeyType key;
      ValueType value;
  }
  </code></pre>
  
  <p>And I need fast access by a key and fast insertion of new values.</p>
  
  <p>I would not use std::map cuz it has too big memory overhead for one structure and for huge amounts of data it might be drastical. Right?</p>
  
  <p>So next I would consider using sorted std::vector and binary_search. It's fine for searching, but adding new values to the vector would be too slow. Imagine you need to add a new value to the beginning of the sorted array, you'd have to move data right aaaaaAAAALOT!</p>
  
  <p>What if I use deque? As I know it has O(1) for push_back/push_front, but still O(n) for inserting (as it would have to move data anyway, less data though).</p>
  
  <p>The questions are:</p>
  
  <p>1) Is O(n) of inserting data in deque much faster in real situation than O(n) in vector?</p>
  
  <p>2) What happens when you insert a value to Deque and the bucket it should go into is full?</p>
  
  <p>3) Is there another preferable type of container in case you need to store lots of data and need two fast operations: search and insertion?</p>
  
  <p>Thanks!</p>