Delete parts of a dynamic array and grow other

Question

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:

int * p = new int[6];

which allocates the necessary array. What I need is that, afterwards, I want to grow some parts of this array. A(n flawed) example:

int *p1 = &p[0];
int *p2 = &p[2];
int *p3 = &p[4];
// delete positions p[2], p[3]
delete [] p2;
// create new array
p2 = new int[4];

I don't know how to achieve this behavior.

EDIT: std::vector does not work for me since I need the time of insertion/deletion of k elements to be proportional to the number k and not to the number of elements stored in the std::vector.

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).

Answer 1

You achieve this behavior by using std::vector:

std::vector<int> v(6);         // create a vector with six elements.
v.erase(v.begin() + 2);        // erase the element at v[2]
v.insert(v.begin() + 2, 4, 0); // insert four new elements starting at v[2]

Really, any time you want to use a dynamically allocated array, you should first consider using std::vector. It's not the solution to every problem, but along with the rest of the C++ standard library containers it is definitely the solution to most problems.

Answer 2

You should look into STL containers in C++, for example vector has pretty much the functionality you want.

Answer 3

I'd advise against doing this on your own. Look up std::vector for a reasonable starting point.

Answer 4

another option, besides std::vector is std::deque, which works in much the same way, but is a little more efficient at inserting chunks into the middle. If that's still not good enough for you, you might get some mileage using a collection of collections. You'll have to do a little bit more work getting random access to work (perhaps writing a class to wrap the whole thing.