title: Why is std::vector::insert complexity linear (instead of being constant)?
body: <p>Lets say I was inserting p new elements at the 'i' th position in an <code>std::vector&lt;mytype&gt;</code> of size 'n'.</p>
  
  <p>Since items in <code>std::vector</code> are guaranteed to use contiguous storage locations for their elements, it seems like this would take me 4 steps to do the above:</p>
  
  <p>1) Possible reallocation of the vector if we are out of space, basically doubling its size. But that is a constant time operation (albeit a very large one).</p>
  
  <p>2) Next there is a memcpy of elements from index 0 through i-1 from the old vector into the new one.</p>
  
  <p>3) Then you copy 'p' new items being inserted at ith index.</p>
  
  <p>4) Then another memcpy for all items from i+1 through n indexes from the old vector to the new vector.</p>
  
  <p>Aren't all the above constant time operations? Then shouldn't insertion itself be a constant time operation? Why then is <code>std::vector::insert</code> linear on the number of elements inserted (copy/move construction) plus the number of elements after position (moving)?</p>