title: Is there any array-like data structure that can grow in size on both sides?
body: <p>I'm a student working on a small project for an high performance computing course, hence efficiency it's a key issue.</p>
  
  <p>Let say that I have a vector of N floats and I want to remove the smallest n elements and the biggest n elements. There are two simple ways of doing this:</p>
  
  <p><strong>A</strong></p>
  
  <pre><code>sort in ascending order    // O(NlogN)
  remove the last n elements // O(1)
  invert elements order      // O(N)
  remove the last n elements // O(1)
  </code></pre>
  
  <p><strong>B</strong></p>
  
  <pre><code>sort in ascending order     // O(NlogN)
  remove the last n elements  // O(1)
  remove the first n elements // O(N)
  </code></pre>
  
  <p>In A inverting the elements order require swapping all the elements, while in B removing the first n elements require moving all the others to occupy the positions left empty. Using std::remove would give the same problem.</p>
  
  <p>If I could remove the first n elements for free then solution B would be cheaper. That should be easy to achieve, if instead of having a vector, i.e. an array with some empty space after <code>vector::end()</code>, I would have a container with some free space also before <code>vector::begin()</code>.</p>
  
  <p>So the question is: does exist already an <strong>array-like</strong> (i.e. contiguous memory, no linked lists) in some libraries (STL, Boost) that allows for O(1) inserting/removing on both sides of the array? </p>
  
  <p>If not, do you think that there are better solutions than creating such a data structure?   </p>