Yet another thought about STL Vector

[dgmdgm]

Hi. Let's see this:

std::vector<int> vec;
vec.push_back(1);
vec.push_back(2);
vec.push_back(3);
vec.push_back(4);
cout << vec[0]; // should display 1

std::vector<index>::iterator i = vec.begin();
vec.erase(i);
cout << vec[0]; // should display 2

I was thinking about how this is implemented in STL. The first thing that did strike me was this: (in a simple way, we all know STL is not exactly like this, it's just a way I found to reproduce the same behaviour)

int *vec = new int[4];
vec[0] = 1;
vec[1] = 2;
vec[2] = 3;
vec[3] = 4;
cout << vec[0]; // should display 1

memcpy( vec[0], vec[1], 3 );
cout << vec[0]; // should display 2

Ok. All this to ask you how STL implements the erase. It's known that it actually does not erase anything. Does it copy the "following" data if you "erase" something in the middle of it with an iterator? For it could be way slow, say, in a very large vector.

Hope my question was exposed clearly.
Any thoughts will be appreciated.

[newb16]

It calls N assignment operators for vector elements ( N is distance from end() to iterator in erase() argument ) and one destructor ( applied to the last element )

[JosAH]

@dgmdgm
A small nitpick: note that this doesn't necessarily work; for overlapping memory regions memcpy may not do what you expect it to do. Use the memmove() function here. It all depends on the copying order used by memcpy().

kind regards,

Jos

[Banfa]

The basic premiss of your argument, that you could end up doing a lot of copying in a vector making it in-efficient is basically true.

The vector is meant to be a drop in replacement for an array, including maintaining the same structure in memory. Because of this any erase or insert operation on a vector is bound to involve copying some of the vector and even adding data to the end of a vector will involve copying if the vector does not already have enough memory to hold all the data.

For this reason you would really only want to use a vector in a situation where the data held was relatively static and when filling a vector it is worth making the function call that sets its size before putting all the individual values into it.

[emibt08]

I wouldn't implement the vector as an array. At least not as you suggested. That way, it will have very poor performance, being just an array. If it actually is implemented that way, it would also need an internal table to keep track of the memory locations and gain performance that way.
So then, i believe that the most effective way to implement it would be as a linked list (double-linked list to allow for backward-iteration). It would have an overhead, of course, but the performance comes with a price, and in this case it's well worth it.
For example if you have a double linked list of integers, you'll need a structure with the actual element of type int and 2 pointers to integer (which in this case will have the same size as int, 4 bytes), leading to use of 12 bytes per element instead of 4. But then suppose you have a large number of elements (maybe 10000) and you want to erase any of it, you wouldn't need to move a single piece of allocated memory, nor to copy. You can just reconnect the nodes of the list and delete the allocated memory for that element. That way you gain a lot in performance/speed. And not to mention that if in the vector you have elements with larger size (perhaps some struct/class, not a primitive type), then the size of the head/tail in the list won't be much of an overhead compared to the overall size. It always will be an overhead, but that's the trade off.
If you don't want any memory overhead, the only solution would be as you suggested with the array, and then do memory reallocation (which in a larger application won't be feasible).

Another thing that i saw in your code was:

memcpy( vec[0], vec[1], 3 );
cout << vec[0]; // should display 2
 

One thing is that as JosAH suggested, memmove() might be a better solution. I don't think that memset() wouldn't work, since there is not a memory overlap. After all, vec[0] and vec[1] are different objects of same size, no matter if they are next to each other or not.
But why use 3 as a third parameter??? The size of int is 4, not 3. So, in your example it will work, but that's just a coincinence, because you're copying the 1st 3 bytes, leaving the MSB unchanged. If you wanna check it out, try with this:

vec[0] = 0x11223344;
vec[1] = 0x55667788;
memcpy( vec[0], vec[1], 3 );
 

If you think that that code will make the value of vec[0] to be 0x55667788, well... think again. It will be: 0x11667788.

However, when using those functions, it would be safer to put sizeof(int) or sizeof(vec[0]) as a third parameter.

Cheers

[JosAH]

The STL also implements the 'list'. Lists and vectors are good at different things: if you want fast direct access (using a simple index), use a vector, if you want cheap element removal, use a list.

kind regards,

Jos

[dgmdgm]

Thank you all for your thoughts.
And, my bad, the memcpy should be:

memcpy( vec[0], vec[1], 3*sizeof(int) );

"Copy the next three 'ints'".
Sorry for that, it was a quick "in brownser coding" in order to explain my point.

And I think it is just like Banfa said, vector having the same structure in memory as an array, and the high price of removing an item in "the middle".

[weaknessforcats]

Personally, I wouldn't use any mem... functions in C++. Little problems about copy constructors or assignment operators beign ignored producing a result batch of improperly initialized objects.

vector is an array. If you need to remove elements from a vector you can't do it easily without a lot of copying stuff. Instead, create a vector of struct variables where a bool in the struct determines whether the element is active or not. You delete an element just by setting the bool to inactive. Then your code that uses this vector just takes that into account.

Next, actual deleting would be better accomplished using a list or some other node-based container rather than a vector.