title: Delete parts of a dynamic array and grow other
body: <p>I need to have a dynamic array, so I need to allocate the necessary amount of memory through a pointer. What makes me wonder about which is a good solution, is that C++ has the ability to do something like:</p>
  
  <pre><code>int * p = new int[6];
  </code></pre>
  
  <p>which allocates the necessary array. What I need is that, afterwards, I want to grow some parts of this array. A(n flawed) example:</p>
  
  <pre><code>int *p1 = &amp;p[0];
  int *p2 = &amp;p[2];
  int *p3 = &amp;p[4];
  // delete positions p[2], p[3]
  delete [] p2;
  // create new array
  p2 = new int[4];
  </code></pre>
  
  <p>I don't know how to achieve this behavior.</p>
  
  <p>EDIT: <code>std::vector</code> does not work for me since I need the time of insertion/deletion of <code>k</code> elements to be proportional to the number <code>k</code> and not to the number of elements stored in the <code>std::vector</code>.</p>
  
  <p>Using pointers, in the general case, I would point to the start of any non continuous region of memory and I would keep account of how many elements it stores. Conceptually, I would fragment the large array into many small ones and not necessarily in continuous space in the memory (the deletion creates "holes" while the allocation does not necessarily "fill" them).</p>