Dissecting the C++ STL Vector: Part 4 – Insertion

Part 4 of the series will cover one of the two most important features of the vector container, namely insertion. The next part will cover deletion, which will be last part about the source code. Future parts will cover the theory behind the vector container. We will be interested in only the insert method group. The following overloads of insert are provided by the vector container:

iterator insert(const_iterator _Where, const _Ty& _Val);
iterator insert(const_iterator _Where, size_type _Count, const _Ty& _Val);
template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value, iterator>::type
	insert(const_iterator _Where, _Iter _First, _Iter _Last);
iterator insert(const_iterator _Where, _Ty&& _Val);
iterator insert(const_iterator _Where, _XSTD initializer_list<value_type> _Ilist);

All of these methods have one common parameter, _Where, which is of type const_iterator. This parameter points at the position at which to begin inserting elements. The type const_iterator depends on the allocator being used and is determined by vector’s grandparent _Vector_val. If we are using the default allocator, it will look something like std::_Vector_const_iterator<std::_Vector_val<std::_Simple_types<_Ty>>>, where _Ty is the element type. We can call the begin method on a vector instance to get an instance of this type. All of these methods return an iterator that points to the first of the newly inserted elements.

The first method enables us to insert one element only. The second enables us to insert a number of elements, all of the same value. The third method enables us to insert a range of elements represented by two iterators. The fourth inserts a given element by moving it. The last overload inserts a number of elements contained within an initializer list. I will discuss only the first three overloads and leave the others as an exercise for the reader.

The first two overloads share the same implementation. They are defined as follows:

iterator insert(const_iterator _Where, const _Ty& _Val)
	return (_Insert_n(_Where, (size_type)1, _Val));

iterator insert(const_iterator _Where, size_type _Count, const _Ty& _Val)
	return (_Insert_n(_Where, _Count, _Val));

They both call the _Insert_n method, which accepts three arguments. The first is an iterator indicating the position. The second is the number of elements to insert. And the third argument is the value of these elements. The body of the method is a bit lengthy and so it is better to look at its control structure first.

iterator _Insert_n(const_iterator _Where, size_type _Count, const value_type& _Val)
	size_type _Off = _VIPTR(_Where) - this->_Myfirst;
	if (_Count == 0) ;
	else if (_Unused_capacity() < _Count)
	{ // not enough room, reallocate } 
	else if ((size_type)(this->_Mylast - _VIPTR(_Where)) < _Count)
	{ // new stuff spills off end }
	{ // new stuff can all be assigned }
	return (begin() + _Off);

We have seen _VIPTR before in part 1. It is macro that takes an iterator an returns its pointer, which is of the same type as _Myfirst. For example, if element type is int and if we are using the default allocator then the pointer type is int*. It is clear now that the local variable _Off is the number of elements that precedes _Where.

There are four cases. If the number of elements to insert is zero, we don’t have to do anything. If the number of unoccupied slots is less than the required number elements, we need to reallocate the underlying array. The logic is very similar to resize except that instead of initializing the new elements using the default constructor, we initialize them with _Val. Also the newly inserted elements might be inserted somewhere in the middle of the array. To do this, the following existing elements have to be shifted to the right to accommodate the new elements. For this reason, inserting elements in a vector might be very inefficient.

The third case occurs when the capacity is large enough, but the number of elements that will be shifted is less than the number of new elements. In this case, we have to move those existing elements that require shifting to their new positions. This is done using the _Umove method, which we have discussed in part 3. Then we construct the new elements depending on whether they will occupy an previously occupied slot or an unoccupied slot. The second case is called spilling and is handled by calling the _Ufill method. This method construct the elements using the copy constructor, where the value to be copied is _Val. The first case can also be handled by using a copy constructor followed by an movement, but we can improve performance by just assigning the value to the existing instance (which is could be invalid because it has already been moved to its new position, hopefully it does not matter) instead of creating a new instance. This is implemented by a method called fill.

The fourth case occurs otherwise. No new elements are spilled, but some of the existing elements will be spilled. This case is handled similarly to the third case.

The third overload of insert is implemented as follows:

template<class _Iter>
typename enable_if<_Is_iterator<_Iter>::value,iterator>::type
	insert(const_iterator _Where, _Iter _First, _Iter _Last)
	{	// insert [_First, _Last) at _Where
		size_type _Off = _VIPTR(_Where) - this->_Myfirst;
		_Insert(_Where, _First, _Last, _Iter_cat(_First));
		return (begin() + _Off);

The logic of this method is very similar to the previous overload of insert except that the new elements are provided as a couple of iterators. The interesting part here is the weird return type enable_if<_Is_iterator::value,iterator>::type. enable_if is a type defined in xtr1common. The return type will be iterator when _Is_iterator::value is true, otherwise it is undefined and the compiler will emit an error. _Is_iterator is a type defined in xmemory0. _Is_iterator::value is true when is_integral::value is false. is_integral is a type defined in xtr1common. In other words, insert requires that _Iter to not be an integral type and the compiler will emit an error (function template specialization failure) otherwise.

There are many exceptions that might be thrown due to many different reasons including invalid iterators and arguments, failed copying, failed, movement, failed destruction, failed assignment, failed construction, out of memory, and exceeding maximum size. In many cases, the state of the vector becomes undefined.


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