std::vector::erase(iterator position) does not necessarily invoke the corresponding element's destructor

Question

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

V.erase(V.begin() + 2) remove the 3rd element.

STL vector implementation will move 4th and 5th element up, and then destruct the 5th element.

I.e. erasing element i in a vector does not guarantee that ith destructor is called. For std::list, this is not the case. Erasing ith element invokes ith element's destructor.

What does STL say about this behavior?

This is code taken from my system's stl_vector.h:

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

In reference to example by Mats Petersson, perhaps this example will show more clearly that destroy 2 really happens, we just don't have destructor available for built-in type where we can conveniently add the printout statement:

#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

(skipped printout of destructor calls for entire vector on program exit)

One way of looking at this is to ask yourself: what does it mean to erase an object from a vector? It means that, given a way to identify that object, you won't be able to find it in a vector after the erase. Maybe it was a value that got overwritten, thereby acquiring a new identity. If it held resources that could identify it, those will be properly released, as others mentioned, as long as move, assignment and copy do the right thing. Additionally, the size of vector would reflect that there is one object less.

For your philosophical amusement, here are some notes by Stepanov (primary STL author):

Integral parts of an object are those parts of the object needed to realize its primary purpose. Connections among integral parts constitute the integral form of the object. Two intuitive constraints that we have on the definition of essential parts are (i) for certain objects, it is possible to take them apart which would result i n their losing their identity and later they could be brought together which would imply their regaining their identity. This allows objects to exist, disappear and later reappear; thus there is a discontinuity in their existence. (ii) some essential parts of an object can be replaced one by one without the object losing its identity. To define identity across time, we introduce the notion of essential parts and essential form.

Definition: An essential part of an object is an integral part such that if it is removed, the object loses its identity, hence it disappears.

Answer 2

This is perfectly valid behaviour. @Cassio Neri pointed out why it is required by the standard.

Short:

"std::vector::erase(iterator position) does not necessarily invoke the corresponding element's destructor" [Op; Headline] but a destructor is invoked, handling the data of the corresponding elements which has been transfered to another object (either via move constructor to the moved-from or via RAII to the temporary instance).

Long:

Why you don't have to rely on the ith destructor to be called.

I'll provide some hints why you shouldn't 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 handle your object move-assignment correctly there is no need to worry about the fact which destructor is called properly.

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

Your move assignment operator has to transfer the state of the object that is "overwritten" into the object that is "moved from" (rhs here) so it's destructor will take proper action (if there is something the destructor needs to take care of). Perhaps you should use something like a "swap" member function to do the transfer for you.

If your object is non-moveable you'll have to handle the "cleanup" (or whatever action that relies on the current state of the object) of the erased object in the copy assignment operation before you copy the new data into the object.

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

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

Let's do a small 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.

Every memory location that is claimed will be released properly if your move (or copy) assignment operation hands over the critical properties to the object that will be destroyed.

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

Answer 3

The standard says that's expected, the specification for vector::erase(const_iterator) (in the table of Sequence container requirements) says that the requirements on that function are:

For vector and deque, T shall be MoveAssignable.

The reason for requiring MoveAssignable is that each of the following elements will be (move) assigned over the element before them, and the last element destroyed.

In theory it would have been possible for the original STL to have done it differently and to have destroyed the erased element as you expect, but there are good reasons that wasn't chosen. If you only destroy the erased element you leave a "hole" in the vector, which isn't an option (the vector would have to remember where holes were and if a user says v[5] the vector would have to remember there's a hole there and return v[6] instead.) So it's necessary to "shuffle" the later elements down to fill the hole. That could have been done by destroying the Nth element in place (i.e. v[N].~value_type()) and then using placement new to create a new object at that location (i.e. ::new ((void*)&v[N]) value_type(std::move(v[N+1]))) and then doing the same for each following element, until you get to the end, however that would result in far worse performance in many cases. If the existing elements have allocated memory, e.g. are containers themselves, then assigning to them may allow them to reuse that memory, but destroying them and then constructing new elements would require deallocating and reallocating memory, which may be much slower and could fragment the heap. So there is a very good reason to us assignment to alter the elements' values, without necessarily altering their identities.

This isn't the case for std::list and other containers because they do not store elements in a contiguous block like vector and deque, so removing a single element just involves adjusting the links between the neighbouring elements, and there is no need to "shuffle" other elements down the block to take up the empty position.

Answer 4

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

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

Had the implementation called the destructor on the 3rd element, it wouldn't be conform.

Indeed, suppose that the destructor is called on the 3rd element. Since only one element is erased, the desctructor cannot be called again.

After the destructor call, the 3rd position contains raw memory (not a fully constructd object T). Hence the implementation needs to call the move constructor to move from the 4th position to the 3rd one.

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 point, the implementation still needs to decrease the vector size by 1 and destroy the 5th element but, as we have seen, no other destrucor call is allowed. (Notice also that the move assignement operator would not be called twice as required by the standard.) QED.

Answer 5

Unlike std::list, std::vector holds its elements contiguously. So when an element is erased from the middle of the container, it would make more sense to copy assign all elements that need to be shifted. In this scenario, the destructor of the last shifted element would be called. This avoids a re-allocation of the whole data of the vector.

Answer 6

Here's a small program that shows the problem, and yes, if you RELY on the destructor being called for that very object, you need to do something other than 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 = a.x; 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);
}

The output is:

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 variant to solve this would be to store a (smart) pointer, and manually copy out the pointer and then delete it.