PART II
Inserting and Deleting Elements
Using resize() is a convenient way to increase the size of a vector by a large number of elements that all require the same value, but it would quickly become tedious if that was the only way to add or delete elements, especially single values. However, the vector container provides a number of methods for the addition and deletion of particular elements.

For adding a single element to the end of a vector, the method push_back() is used. It is used with the following calling syntax:

This code appends the element val to the end of the vector. Similarly, to remove a single element from the end of a vector, the function pop_back() is used:


The following code demonstrates these functions:


Output:



It's perfectly reasonable to assume that, at some point, someone is going to need to insert or remove an element at a specific location other than the very end. The vector container provides methods for doing so: insert() and erase(). These are both very handy functions, but they require the use of iterators, which some may be unfamiliar with. Iterators are used to access elements of the STL containers. I won't go into much detail on them (they definitely warrant a tutorial of their own), but for the moment, they can be though of like pointers - they represent an address within a container, and it is possible to dereference an iterator to access a particular element within the container. The calling syntax for insert() is as follows:



The first inserts the element value before the location location, returning an iterator to the newly inserted element (note that you don't actually need to do anything with the return value, nor even specify storage for it in the code, unless there is something specific that you're going to do to the new element). The second line inserts number copies of the element value before the location location. The third inserts the values from start to end before the location location. The iterators start and end can refer to a different vector, making this syntax useful for copying some or all of the contents of one vector into another.

The function erase() is called with any of the following syntaxes:



The first deletes the element at location location, while the second deletes the elements from start to end. Both return an iterator to the last element following the ones that were erased. The code that follows demonstrates the use of insert() and delete():



Output:



The only tricky part of the above code (in the sense that it hasn't been covered here yet) are the functions begin() and end(). begin() returns an iterator to the first element of a vector, while end() returns an iterator to the element just past the last element in a vector. So to specify an iterator to the second element of a vector v, we can use v.begin() + 1 (remember that vector indices, like any normal C array, start at 0). Similarly, to get an iterator to the second to last element of v, we can use v.end() - 2. So, as an alternative to using an index in a for loop that must be less than v.size() for running through the elements of a vector, we could use the following syntax:





Assigning Values to An Entire Vector
Most of the techniques for assigning values to a vector dealt with to this point consider only assigning a value to a single element, or assigning multiple elements the same value. There are a couple of functions that allow for the en masse assignment of elements to a vector. The first is assign(). This function has the syntax:



The first version is used to fill a vector with number copies of the element value. This is especially useful when you've already declared a vector without assigning any values to it, and need to fill it up. The second version fills a vector with the elements between the iterators start and end. These can be iterators of belonging to another vector, which allows you to copy a portion of one vector into another (as we did with insert). In my experience, however, the most frequent use of the second form is to copy a raw array into a vector. This is especially useful when reading data from a stream into an array buffer (such as in the case of file I/O or user input), when you would really rather have it stored in a vector. The following code demonstrates both of the uses of assign, using it to fill an empty vector with multiple copies of a particular value, then reassign the vector with the elements stored in a static array:



Output:



The second major method for multiple assignment is the function swap(). This function, as its name suggests, swaps the content of one vector with another. The calling syntax is:



You should note well the fact that this function really does swap the vectors - the contents of source wind up in the calling vector, and the contents of the calling vector wind up in source. The following swaps the contents of one vector for another:



Output:



A rather trivial example, since each vector actually contains only one string. But it works. To be perfectly honest, though, I’ve never had to use swap() except when just playing around with the various vector methods for learning purposes. If anyone knows of a good reason to use swap() where another method wouldn’t work as well, please post it here for our enlightment.


That covers many of the basic vector methods available, and concludes Part II. In the next part of this tutorial, I’ll be dealing with all of the vector methods that I can think of that haven’t been presented thus far, as well as some considerations of the performance of vectors.



Other Vector Methods
There are a few more methods to round out the full complement of builtin functions available for vectors. I won’t present a lot of code for these, as most of them are relatively simple.


The front() and back() methods are used to return references to the start and end of a vector, respectively. The back() method is especially convenient when you need to play around with an element after you’ve push_back()’ed it into a vector.


begin() and end() return random access iterators to the first element, and the location just after the last element, respectively. They were briefly discussed when dealing with erasing particular elements, and that is when I use them most often. As with any iterator, they can be dereferenced to obtain a reference to the element that they point to.

Since front() and back() both return references, and begin() and end() both return iterators that can be dereferenced, these two sets of methods are often interchangeable when the modification of a single element element is required. The following two lines produce the same result:

The first (reference-return) form is obviously a much cleaner and simpler interface. However, the fact that the iterators returned by begin() and end(), like pointers, can be incremented, decremented, and dereferenced, makes the iterator approach much more versatile and powerful.



rbegin() and rend() return the same thing as begin() and end(), except the iterators that they return are reverse iterators. Reverse iterators are like dyslexic iterators – they exchange the meanings of +/-, +=/-=, and ++/--. Personally, I get more than a little confused by them, so I usually wind up just using random access iterators and take care of directionality and incrementing/decrementing myself. If anyone wants to explain them in more detail, feel free – I know it would be a learning experience for me.



clear() removes all of the elements from a vector. This means that size() will return zero after clear() is called. However, the capacity of the vector will remain the same (at least on all machines and using all compilers that I’ve found – I do not know whether this is specified in the ISO standard).



empty() returns true for the vector v if v.size()==0, and false otherwise. Simple, but useful in for loops and do-while statements to prevent overrunning the data if there are no elements to access (while avoiding extensive try-catch blocks).


That’s about all for the vector methods. They also support the full range of assignment and comparative operators, but that will have to wait for another day, or maybe for a tutorial on operator overloading.



Performance Issues
Throughout this tutorial I have simply presented the methods for the vector container, without regards to its performance. In fact, vectors are pretty well optimized, and so will show good (fast) performance in a lot of situations. However, if you’re specifically looking for performance from a container class, there are some things that you should be aware of. The following sections list the complexity of each of the methods discussed here.

Constant time vector methods O(1)


Linear time vector methods O(N)


This should give you a pretty good idea about where you can expect your performance bottlenecks to be in programs using vectors extensively. However, note the asterisked entries. push_back() runs in constant time, but only if size() is less than capacity. It will run in constant time right up until it runs out of allocated memory, then waits around for what amounts to an internal call to reserve() to occur, which occurs in linear time. Therefore, avoiding tons of push_back()’s is a good way to prevent performance hits. Frequently, using reserve() at the outset of a program to allocate a huge block of memory, on the order of what you expect usage to be, can make a big difference (at least in my experience).

The insert() method is flagged for a different reason. For vectors, insert() runs in linear time, but it can be much faster in other containers such as list or deque. The deque can be particularly good, both for performance, and the fact that it also offers push_front() and pop_front() methods for inserting and deleting from the first element of the container, if that’s something you have frequent use for. Fortunately, most of the other STL containers have similar methods to vectors, so learning them after getting comfortable with vectors can be pretty easy.



Multidimensional Vectors
One of the more frustrating aspects of using raw arrays is when multidimensional arrays (2 or more dimensions) are required. Although fundamentally logical, I frequently find the code required to create such arrays convoluted and prone to errors. Vectors themselves cannot be multidimensional – they do not support multiple subscripts. However, there is nothing that says the datatype stored in a vector cannot be simply another vector. Initialization and assignment require slightly more complex code than in the standard 1D vector; however, the overall amount of code required can be greatly reduced, because the constructors and destructor take care of memory allocation/deallocation when the objects are intialized or go out of scope.

The following code demonstrates a few of the uses of multidimensional arrays constructed from STL vectors. The user is asked to input a series of 10 floating point numbers. For each number entered, the sine of the number is calculated, and both are stored in an array. The array is then sorted, according to the sine values, and all of the numbers except those with the two largest and two smallest sine values are deleted.



The code above doesn’t really contain anything new, just an extension. The critical thing to note here is that the at() method returns a vector; individual elements of the array need to be accessed with the somewhat peculiar mdVector.at(row).at(col) syntax (accessing individual elements can also be done using the [][] operator(s), just as one would with a raw array).

I’m not really going to present anything more on multidimensional arrays constructed from vectors. Although they can incur a serious performance hit when they get large or need to be frequently resized, they are very useful for the convenience of multidimensional arrays without the inconvenience of dealing with memory allocation/deallocation.



That’s all for now. Hope this helps out some of you, and that any mistakes are caught before they hinder too many.

Thank you very much again for clarifying even more about vector functions.