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

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 2

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 3

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.