title: list or container O(1)-ish insertion/deletion performance, with array semantics
body: <p>I'm looking for a collection that offers list semantics, but also allows array semantics.  Say I have a list with the following items: </p>
  
  <pre><code>apple orange carrot pear 
  </code></pre>
  
  <p>then my container array would: </p>
  
  <pre><code>container[0] == apple 
  container[1] == orangle 
  container[2] == carrot 
  </code></pre>
  
  <p>Then say I delete the orange element: </p>
  
  <pre><code>container[0] == apple 
  container[1] == carrot 
  </code></pre>
  
  <p>I want to collapse gaps in the array without having to do an explicit resizing, Ie if I delete container[0], then the container collapses, so that container[1] is now mapped as container[0], and container[2] as container[1], etc.  I still need to access the list with array semantics, and null values aren't allow (in my particular use case). </p>
  
  <p>EDIT: </p>
  
  <p>To answer some questions - I know O(1) is impossible, but I don't want a container with array semantics approaching O(log N).  Sort of defeats the purpose, I could just iterate the list. </p>
  
  <p>I originally had some verbiage here on sort order, I'm not sure what I was thinking at the time (Friday beer-o-clock most likely).  One of the use-cases is Qt list that contains images - deleting an image from the list should collapse the list, not necessary take the last item from the list and throw it in it's place.  In this case, yet, I do want to preserve list semantics.</p>
  
  <p>The key differences I see as separating list and array: 
     Array - constant-time access 
     List  - arbitrary insertion </p>
  
  <p>I'm also not overly concerned if rebalancing invalidates iterators.</p>