title: How is C++ std::vector implemented?
body: <p>I have been using <code>std::vector</code> a lot, and recently I asked myself this question: "How is <code>std::vector</code> implemented?"</p>
  
  <p>I had two alternatives:</p>
  
  <p>1) Linked list, and then making the API feel like random access (i.e. overloading <code>operator[]</code>).</p>
  
  <p>2) Using <code>new</code>, e.g. <code>Foo* temp = new Foo[20]</code>: I believe they do something like this, but then it raises one more question. Do they always allocate a maximum (<code>uint32_t</code>) storage to give random access? (This is inefficient in terms of memory.)</p>
  
  <p>Or is there something else that I should be aware of?</p>