title: std::list and std::vector - Best of both worlds?
body: <p>By <a href="https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl">vector vs. list in STL</a>:</p>
  
  <ul>
  <li><p>std::vector: Insertions at the end are constant, amortized time, but insertions elsewhere are a costly O(n).</p></li>
  <li><p>std::list: You cannot randomly access elements, so getting at a particular element in the list can be expensive.</p></li>
  </ul>
  
  <p>I need a container such that you can both access the element at any index in O(1) time, but also insert/remove an element at any index in O(1) time. It must also be able to manage thousands of entries. Is there such a container?</p>
  
  <p>Edit: If not O(1), some X &lt;&lt; O(n)?</p>