Professional C__ - Marc Gregoire [197]
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 6 7 8 9 10
100 100 100 100 100 100 100 100 100
Recall that iterator pairs represent a half-open range, and insert() adds elements before the element referred to by the iterator position. Thus, you can insert the entire contents of vectorTwo into the end of vectorOne, like this:
vectorOne.insert(vectorOne.end(), vectorTwo.begin(), vectorTwo.end());
Methods such as insert() and erase() that take a vector range as arguments assume that the beginning and ending iterators refer to elements in the same container, and that the end iterator refers to an element at or past the begin iterator. The methods will not work correctly if these preconditions are not met!
Algorithmic Complexity and Iterator Invalidation
Inserting or erasing elements in a vector causes all subsequent elements to shift up or down to make room for, or fill in the holes left by, the affected elements. Thus, these operations take linear complexity. Furthermore, all iterators referring to the insertion or removal point or subsequent positions are invalid following the action. The iterators are not “magically” moved to keep up with the elements that are shifted up or down in the vector.
Also keep in mind that an internal vector reallocation can cause invalidation of all iterators referring to elements in the vector, not just those referring to elements past the point of insertion or deletion. See the next section for details.
The vector Memory Allocation Scheme
The vector allocates memory automatically to store the elements that you insert. Recall that the vector requirements dictate that the elements must be in contiguous memory, like in standard C-style arrays. Because it’s impossible to request to add memory to the end of a current chunk of memory, every time the vector allocates more memory it must allocate a new, larger, chunk in a separate memory location and copy/move all the elements to the new chunk. This process is time-consuming, so vector implementations attempt to avoid it by allocating more space than needed when they have to perform a reallocation. That way, they can avoid reallocating memory every time you insert an element.
One obvious question at this point is why you, as a client of the vector, care how it manages its memory internally. You might think that the principle of abstraction should allow you to disregard the internals of the vector memory allocation scheme. Unfortunately, there are two reasons why you need to understand how it works:
1. Efficiency. The vector allocation scheme can guarantee that an element insert runs in amortized constant time: Most of the time the operation is constant, but once in a while (if it requires a reallocation), it’s linear. If you are worried about efficiency you can control when the vector performs reallocations.
2. Iterator invalidations. A reallocation invalidates all iterators referring to elements in the vector.
Thus, the vector interface allows you to query and control the vector reallocations. If you don’t control the reallocations explicitly, you should assume that all insertions cause a reallocation and thus invalidate all iterators.
Size and Capacity
The vector provides two methods for obtaining information about its size: size() and capacity(). The size() method returns the number of elements in the vector, while capacity() returns the number of elements that it can hold without a reallocation. Thus, the number of elements that you can insert without causing a reallocation is capacity() - size().
You can query whether a vector is empty with the empty() method. A vector can be empty but have nonzero capacity.
Reserving Capacity
If you don’t care about efficiency or iterator invalidations, there is never a need to control the vector memory allocation explicitly. However, if you want to make your program as efficient as possible, or want to guarantee that iterators will not be invalidated, you can force the vector to preallocate enough space to hold all of its elements. Of course, you need to know how many elements