Dissecting the C++ STL Vector: Part 5 – Deletion


This is the last part of the series, in which I will discuss the erase method group. The purpose of these methods is to delete one or more elements from a vector. We will see that the implementation of these methods is wrong. There are two overloads defined as follows:

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

The first method accepts an iterator and deletes the single element it points to. The second method accepts two iterators that define a half-open interval of elements to be deleted. They both return an iterator pointing to the new location of the element that followed the last element erased by the method call. This is the container end if the operation erased the last element in the sequence.

I will discuss only the first method and leave the second one as an exercise for the reader. The first method is defined as follows:

iterator erase(const_iterator _Where)
{
	_Move(_VIPTR(_Where) + 1, this->_Mylast, _VIPTR(_Where));
	_Destroy(this->_Mylast - 1, this->_Mylast);
	--this->_Mylast; // The arrow operator has higher precedence.
	return (_Make_iter(_Where));
}

The code first calls _Move. This method is implemented externally by the C++ runtime. It shifts all the elements following the one to be deleted ti the left by one position by only copying their bytes. It does not modify the state of the vector in any way.

Then _Destroy is called, which destructs the very last element of the vector. Note that there are now two copies of this element, namely the last two elements. Calling _Destroy on the last element may actually corrupt the other. It does not even destruct the element being erased. This implementation is completely wrong (the same applies to the over overload). It should have been implemented as follows:

iterator erase(const_iterator _Where)
{
	_Destroy(this->_Where, this->_Where + 1);
	_Move(_VIPTR(_Where) + 1, this->_Mylast, _VIPTR(_Where));
	--this->_Mylast; // The arrow operator has higher precedence.
	return (_Make_iter(_Where));
}

We should first destructs the element to be erased. Then we can copy the bytes. The state is fixed by decreasing _Mylast. The last element should not be destructed unless it is the element to be erased.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s