Std :: vector :: erase (iterator position) optionally calls the corresponding element destructor

Question

Assuming I have a std::vector V of 5 elements,

V.erase(V.begin() + 2) remove the third element.

The STL vector implementation will move the 4th and 5th elements up, and then destroy the 5th element.

those. The erasing element I in vector does not guarantee that the destructor is called. For std::list this is not the case. Erasing the ith element calls the element's destructor.

What does the STL say about this behavior?

This is the code taken from my stl_vector.h system:

 392 iterator erase(iterator __position) { 393 if (__position + 1 != end()) 394 copy(__position + 1, _M_finish, __position); 395 --_M_finish; 396 destroy(_M_finish); 397 return __position; 

Answer 1

The C ++ 11 standard 23.3.6.5/4 says (emphasis mine):

Complexity: The destructor T is called the number of times equal to the number of elements to be erased , but the move destination operator for T is called the number of times equal to the number of elements in the vector after the elements to be erased.

If the implementation were called a destructor on the third element, this would not correspond.

Indeed, suppose the destructor is called on the third element. Since only one element is erased, the descriptor cannot be called again.

After calling the destructor, the 3rd position contains the raw memory (and not the completely constructed object T ). Therefore, for implementation it is necessary to call the constructor of movement to move from the 4th position to the third.

It cannot destroy the 4th element (because it can no longer call the destructor), and then to move from the 5th to the 4th element it must call the move assignment operator.

At this stage of implementation, it is still necessary to reduce the size of vector by 1 and destroy the 5th element, but, as we saw, no other call to destrucor is allowed. (Note also that the move assignment operator will not be called twice as required by the standard.) QED.

Answer 2

This is absolutely correct behavior. @Cassio Neri pointed out why this is required by the standard.

Short:

"std :: vector :: erase (iterator position) does not necessarily invoke the corresponding element destructor" [Op; Header] , but the destructor is called, which processes the data of the corresponding elements that were transferred to another object (either using the move to move mechanism, or through RAII to a temporary instance).

Long

Why you do not need to rely on the i-th destructor to be called.

I will give some tips why you should not worry at all which destructor is called in this case.

Consider the following small class

  class test { int * p; public: test (void) : p(new int[5]) { cout << "Memory " << p << " claimed." << endl; } ~test (void) { cout << "Memory " << p << " will be deleted." << endl; delete p; } }; 

If you correctly control the assignment of moving an object, there is no need to worry about which destructor is called correctly.

  test& operator= (test && rhs) { cout << "Move assignment from " << rhs.p << endl; std::swap(p, rhs.p); return *this; } 

Your move assignment statement should pass the state of the object “overwritten” to the object that is “moved from” ( rhs here), so the destructor will take the right action (if there is anything that the destructor needs to take care of). Perhaps you should use something like the "swap" function to pass to you.

If your object does not move, you will have to handle the “cleanup” (or any action based on the current state of the object) of the erased object in the copy destination operation before copying new data to the object.

  test& operator= (test const &rhs) { test tmp(rhs); std::swap(p, tmp.p); return *this; } 

Here we use RAII and again swap (which can still be a member function, but the test has only one pointer ...). The tmp destructor will make things cozy.

Do a little test:

  #include <vector> #include <iostream> using namespace std; class test { int * p; public: test (void) : p(new int[5]) { cout << "Memory " << p << " claimed." << endl; } test& operator= (test && rhs) { cout << "Move assignment from " << rhs.p << endl; std::swap(p, rhs.p); return *this; } ~test (void) { cout << "Memory " << p << " will be deleted." << endl; delete p; } }; int main (void) { cout << "Construct" << endl; std::vector<test> v(5); cout << "Erase" << endl; v.erase(v.begin()+2); cout << "Kick-off" << endl; return 0; } 

Results in

 Construct Memory 012C9F18 claimed. Memory 012CA0F0 claimed. Memory 012CA2B0 claimed. // 2nd element Memory 012CA2F0 claimed. Memory 012CA110 claimed. Erase Move assignment from 012CA2F0 Move assignment from 012CA110 Memory 012CA2B0 will be deleted. // destruction of the data of 2nd element Kick-off Memory 012C9F18 will be deleted. Memory 012CA0F0 will be deleted. Memory 012CA2F0 will be deleted. Memory 012CA110 will be deleted. 

Each declared memory cell will be released correctly if the assignment (or copy) operation passes critical properties to the object that will be destroyed.

Each destructor that relies on the internal state of an object will be called with the corresponding object around if your assignment operations are properly designed.

Answer 3

Unlike std::list , std::vector stores its elements contiguously. Therefore, when an element is removed from the middle of the container, it would be more advisable to copy all the elements that need to be moved. In this case, the destructor of the last shifted element will be called. This avoids the redistribution of all vector data.

Answer 4

The standard states that, as expected, the specification for vector::erase(const_iterator) (in the requirements table of the Sequence container) states that the requirements for this function:

For vector and deque , T must be MoveAssignable .

The reason for the MoveAssignable requirement is that each of the following elements will (move) assigned above the element in front of them, and the last one will be destroyed.

In theory, it would be possible for the original STL to do this differently and destroy the erased element, as you would expect, but there are good reasons that have not been selected. If you destroy only the erased element, you will leave the “vector” in the vector, which is not an option (the vector would have to remember where the holes were, and if the user says v[5] , the vector would have to remember the hole there and return v[6] .) Therefore, it is necessary to “shuffle” later elements to fill the hole. This could be done by destroying the Nth element in place (ie v[N].~value_type() ), and then using placement new to create a new object in that location (i.e ::new ((void*)&v[N]) value_type(std::move(v[N+1])) ), and then do the same for each next element until you reach the end, however in many cases this will lead to significantly worse results. If existing elements are allocated memory, for example. the containers themselves, then their purpose may allow them to reuse this memory, but destroying them and then creating new elements will require freeing up the memory and reallocating the memory, which can be much slower and can fragment the heap. Therefore, there is a very good reason for us to change the values ​​of elements without changing their identity.

This does not apply to std::list and other containers, because they do not store elements in an adjacent block, such as vector and deque , so deleting one element only requires adjusting the relationships between neighboring elements, and there is no need to "drag" other elements across the block, to take up an empty position.

Answer 5

In relation to the example written by Mats Peterson, perhaps this example will show more clearly that destruction 2 does occur, we simply do not have a destructor available for the built-in type, where we can conveniently add the print instruction:

 #include <vector> #include <iostream> #include <utility> using namespace std; struct Integer { int x; Integer(int v) : x(v) {} ~Integer() { cout << "Destroy Integer=" << x << endl; } }; class X { Integer Int; public: X(int v) : Int(v) {} X operator=(const X& a) { auto tmp(a.Int); swap(this->Int, tmp); cout << "copy x=" << Int.x << endl; return *this; } }; int main() { vector<X> v; for(int i = 0; i < 5; i++) { X a(i); v.push_back(a); } cout << "Erasing ... " << endl; v.erase(v.begin() + 2); } 

This will print:

 Destroy Integer=0 Destroy Integer=0 Destroy Integer=1 Destroy Integer=0 Destroy Integer=1 Destroy Integer=2 Destroy Integer=0 Destroy Integer=1 Destroy Integer=2 Destroy Integer=3 Destroy Integer=0 Destroy Integer=1 Destroy Integer=2 Destroy Integer=3 Destroy Integer=4 Erasing ... Destroy Integer=2 copy x=3 Destroy Integer=2 Destroy Integer=3 Destroy Integer=3 copy x=4 Destroy Integer=3 Destroy Integer=4 Destroy Integer=4 

(Missing printout of destructor calls for the whole vector when exiting the program)

One way to look at this is to ask yourself: what does it mean to erase an object from a vector? This means that, given the way this object is identified, you cannot find it in the vector after deletion. Perhaps it was a value that was rewritten, thereby acquiring a new identity. If resources are stored in it that could identify them, they will be properly released, as mentioned in other publications, while they move, assign and copy. In addition, the size of the vector will reflect that there is one smaller object.

For your philosophical entertainment, here are a few notes by Stepanov (the main author of STL):

The integral parts of an object are those parts of an object that are necessary to realize their main goal. Connections between integral parts make up the integral form of the object. Two intuitive restrictions that we have by definition of the essential parts (i) for certain objects, they can be divided, which will lead to they lose their identity, and later they can be combined which would imply their restoration of their identity. This allows objects to exist, disappear and later appear; thus, there is a gap in their existence. (ii) some material parts of an item may be replaced one after another without loss of item. To define identities in time, we introduce the concept of essential parts and essential form.

Definition A substantial part of the object is an integral part such that if it is removed, the object loses its identity, therefore, it disappears.

Answer 6

Here's a small program that shows the problem, and yes, if you want the destructor to be called for this object itself, you need to do something else besides what this code does:

 #include <iostream> #include <vector> using namespace std; class X { int x; public: X(int v) : x(v) {} ~X() { cout << "Destroy v=" << x << endl; } X operator=(const X& a) { x = ax; cout << "copy x=" << x << endl; return *this; } }; int main() { vector<X> v; for(int i = 0; i < 5; i++) { X a(i); v.push_back(a); } cout << "Erasing ... " << endl; v.erase(v.begin() + 2); } 

Output:

 Destroy v=0 Destroy v=0 Destroy v=1 Destroy v=0 Destroy v=1 Destroy v=2 Destroy v=3 Destroy v=0 Destroy v=1 Destroy v=2 Destroy v=3 Destroy v=4 Erasing ... copy x=3 Destroy v=3 copy x=4 Destroy v=4 <<< We expedct "destroy 2", not "destroy 4". Destroy v=4 Destroy v=0 Destroy v=1 Destroy v=3 Destroy v=4 

One solution to this problem is to store a (smart) pointer and manually copy the pointer, and then delete it.