STL & Generic Programming: STL Containers
Thomas Becker
Why does the Standard C++ library provide so many kinds of containers? To enable tradeoffs in efficiency in their infinite variety of uses.
The STL Is More Than Containers
In my last column, I introduced you to using the STL by discussing a small code example that used a container, some iterators, and an algorithm. I said that I view containers, iterators, and algorithms as "the three pillars of the STL." Containers store objects in memory. An example is std::vector, which is essentially a dynamically growing C-style array. Algorithms are functions that operate on sequentially organized data. An example is std::find, which locates the first occurrence of an element in a sequence. Iterators are pointer-like objects that the STL uses to present sequentially organized data. Examples are the iterators exposed by the STL containers. These behave like pointers to objects that are stored in the container, or to a hypothetical position one past the last element in the container. Listing 1 shows a silly little code example to illustrate this again. This code fills a vector with 50 random integers between 0 and 41 and then checks if the number 13 is in the vector.
The most important point I made in my last column was that you should not view the STL as just another library of container classes, with algorithms and some other stuff thrown in for good measure. Instead, you should understand that the unique power of the STL lies in its extensibility. For example, if you write a new function that operates on a sequence of elements, such as a function to calculate the standard deviation of a sequence of numbers, you should write this function as an STL-style algorithm, passing the sequence of numbers as a pair of iterators. That way, you can reuse your function not only with numbers stored in any STL container, but with any sequential data that is presented through a pair of iterators. Showing you examples of how to extend the STL in various ways is in fact one of the main purposes of future columns in this series.
This being said, let me be honest and tell you how I (and the team that I was working with at the time) first started out using the STL. The term "generic programming" meant very little to us. We did not have the time to do a lot of studying. We were under pressure to deliver a major piece of software. We had been using container classes from a proprietary library in our code, but nobody was very happy with them. We felt that STL containers were designed much more thoughtfully, and we liked the consistency and the intellectual rigor of the STL. In other words, we did exactly what I told you not to do: we viewed the STL as just another library of container classes. And there is of course absolutely nothing wrong with starting out that way. Of the vast possibilities that the STL offers to the C++ programmer, containers are the most immediate need in real-life software development. Moreover, using containers simply to store and retrieve objects is an excellent way to get started using the STL when your time to study is limited. Therefore, I will devote this column to an overview of STL containers. Reading the following will enable you to select the right container for the right purpose, and it will get you started on using each type of container in your code.
STL Container Specification
In order to use STL containers efficiently and elegantly in your code, it is extremely important to understand how the various types of containers differ from each other and what they were designed for.
But before we go there, I must remind you that the STL is based on the idea of programming with concepts. This means that ideally, containers are not specified by describing the data structure that is used to implement them. Instead, the STL prefers to specify its containers as having certain interface methods and meeting certain complexity requirements. Meanwhile, back in the real world, it is not always practical to maintain such mathematical rigor. For example, the C++ standards committee has recently decided that it will require std::vector to be implemented as a contiguous, C-style array [1]. That way, it will be safe to use the contents of a vector as a drop-in for C-style arrays in legacy code. For now, vector is the only STL container whose implementation will be specified by the Standard, but others may follow suit.
This being said, I would like to encourage you to focus on the conceptual properties of STL containers rather than their implementation. This will help you to make wise decisions when it comes to choosing the right container for the right purpose. Moreover, it is of course very dangerous to rely on any implementation details that are not specified by the Standard. For example, I know of one STL implementation in which std::vector::iterator is a typedef for an actual C-style pointer. In another implementation, std::vector::iterator is a simple wrapper class around a C-style pointer. Both implementations comply with the current (soon-to-be-changed) version of the Standard. In keeping with Murphy’s Law, I was recently asked to port a major piece of software from the first STL implementation to the second, and the code contained ample occurrences of stuff like this:
std::vector<SomeClass>::iterator it; // ... BYTE* pMurphy = (BYTE*) it;
You get the picture.
STL Container Overview
The STL provides seven types of containers: std::vector, std::list, std::deque, std::set, std::multiset, std::map, and std::multimap. These can be divided into two categories: std::vector, std::list, and std::deque model a concept that the STL specification calls Sequence, whereas the four set and map classes are models of a concept called Sorted Associative Container. The concepts of Sequence and Sorted Associative Container are explained in detail in Matt Austern’s book [2]. If it were really necessary for you to fully understand these and other concepts in their full mathematical rigor before you could even use STL containers, I would be very hesitant to recommend the STL for use in real-life software engineering. While I strongly recommend that you study STL concepts carefully, I know from experience that you can achieve a lot based on a rather intuitive understanding.
So here’s the short take on the Sequence and Sorted Associative Container concepts: a Sequence is a variable sized container that stores its elements in the order in which they are inserted. Examples for this kind of storage are storage in a contiguous memory block and storage in a linked list of nodes. The difference between the various ways of implementing the Sequence concept lies in the efficiency of certain operations such as element access or inserting an element. I will discuss this below when I talk about the different STL containers in detail.
A Sorted Associative Container, on the other hand, is a container that holds its elements in a data structure where they are sorted according to a predefined ordering scheme. As you will remember from Algorithms and Data Structures 101, the classical way of implementing sorted storage efficiently is as a binary tree, where the left child of a node is considered less than the node and its right-hand child is considered greater than the node. The point of having Sorted Associative Containers in addition to Sequences is that Sorted Associative Containers are optimized for fast lookup of elements. Moreover, that is the primary reason for having them. In other words, in most cases you should not use any of the four STL Sorted Associative Containers unless you want to be able to find elements in them efficiently. The STL offers two kinds of Sorted Associative Containers. The std::set and std::multiset containers hold plain objects; by contrast, the std::map and std::multimap are associative arrays. They store key-value pairs, which can be looked up efficiently by key.
STL Containers in Detail
Below I discuss each of the seven container types in more detail. In order to use them, you will of course have to consult your documentation for details on constructors and member functions. The following discussion will provide you with the necessary understanding to use containers wisely, especially when it comes to selecting the right container type for the right purpose. I discuss std::vector in more detail than the rest of the containers because it is the default choice for an STL container and will likely be the best choice more often than anything else.
std::vector
An STL vector can be visualized as a C-style array of objects with some auto-sizing intelligence wrapped around it. Whenever you must decide which type of container to use, std::vector should be your default choice. The array-like behavior of STL’s vectors makes them simple to use, and they are very often suitable and efficient for the purpose at hand. All other containers are designed to provide better efficiency for certain operations, such as element insertion and removal, or element lookup. These special features should be used only when they are really needed. This helps to keep the code simple and uniform. Also, these optimizations incur an overhead, typically in the form of one or more node pointers per stored element. Whether or not this overhead is a problem to be taken into account depends on the context. (See also Herb Sutter’s column [1] on the subject of container overhead.)
The behavior of std::vector in terms of complexity is summarized in the sidebar. The most pleasant property is that element access can be performed in constant time. To see exactly what this means, suppose vect is a vector of objects of type SomeClass, and vect currently contains pos+1 or more elements. Then the time it takes to evaluate the right-hand side of
SomeClass x = vect[pos];
is independent of pos, or the number of elements currently stored in the vector, or any other variable quantity. In fact, given the inlining capabilities of today’s compilers, it is quite likely that evaluating vect[pos] is a matter of one pointer addition and one pointer dereference operation. Here, I have used the fact that vector provides an operator[] for element access, emphasizing its similarity to C-style arrays. The above line of code could have been written equivalently as
SomeClass x = *(vect.begin() + pos);
emphasizing the similarity between iterators and pointers. The same complexity guarantee for the evaluation of the right-hand side applies.
The fact that vector element access is so efficient is another great reason to make std::vector your default container choice. On the downside, the one operation that is very inefficient for vectors is element insertion and removal at arbitrary positions. The reason is of course that when an element is inserted or removed at some arbitrary position, then all elements to the right of that position must be shifted, which requires that many calls to the elements’ copy constructors.
As you can see from the sidebar, std::vector specifically boasts that insertion or removal of an element at the end can be done in amortized constant time. This is emphasized by the fact that vector provides special member functions for this purpose, namely, push_back and pop_back. It is clear that these functions do not require any shifting of elements; therefore they might seem to incur a constant cost. But there is a little more to it than that. An insertion at the end requires the vector to grow, and it may therefore cause a memory allocation, followed by copying the entire contents of the vector to the new location. In a naive implementation, this would happen on every call to push_back, thus making the cost of push_back proportional to the size of the vector. A standard-compliant implementation of std::vector is guaranteed to do better than that. When it needs to reallocate the memory, it does so in big chunks, typically by doubling the size of the memory previously allocated. Therefore, if one call to push_back causes a reallocation, you are guaranteed that many subsequent calls do not, thereby amortizing the cost of the one expensive call.
This behavior is quite satisfying from a theoretical point of view, and it tells you that it is not too bad to just keep calling push_back and pop_back, leaving size and memory management to the vector. On the other hand, if you know up front how many elements your vector will eventually hold, then it is of course much more efficient to perform a single memory allocation. std::vector allows you to do that in several different ways:
std::vector<int> vect; vect.reserve(42); for(int i=0; i<42; ++i) vect.push_back(i);
The call to reserve instructs the vector to allocate memory for at least 42 elements up front. The vector itself is still empty at this point, but it has enough memory for the next 42 calls to push_back up its sleeve.
std::vector<int> vect; vect.resize(42); for(int i=41; i>=0; —i) vect[i] = i;
The call to resize not only allocates memory for 42 elements, it actually places 42 default-constructed elements into the vector. These may now be accessed with operator[]. An advantage of this default construction of elements is that after a resize, you can store new elements in the container at arbitrary positions up to its new size. An equivalent way of sizing the container like this up front is to use a different constructor:
std::vector<int> vect(42);
The disadvantage of resizing as opposed to reserving is that constructor calls are made to fill the newly created positions in the vector with default element values. This may or may not be a problem, depending on the context.
You should definitely make it a rule to use reserving or resizing whenever you know at compile time how many elements your vector must hold. Not only may it save you many reallocation operations, it may also prevent you from allocating more memory than you acually need. To understand how, recall that when a vector reallocates memory, it typically allocates double the amount it had allocated before. So if you don’t reserve or resize first, and just keep calling push_back or insert, it is possible that at any given time, you will have allocated twice as much memory as you really need — an effect that can have serious consequences if your program stores a lot of data in memory. Although the STL specification does not require that reserve and resize allocate just the amount of memory requested, it is quite likely that your implementation will work this way.
One of the most frequent mistakes when using std::vector is to confuse reserving and resizing. Let us look at the two code examples above with resizing and reserving switched:
std::vector<int> vect; vect.resize(42); for(int i=0; i<42; ++i) vect.push_back(i);
This is valid code, but the effect is probably not what was intended. This will result in vect having 84 elements. The first 42 are default-constructed integers stored in the vector by the call to resize. The rest are the integers 0 through 42, put there by calling push_back repeatedly on a vector that already had 42 elements.
std::vector<int> vect; vect.reserve(42); for(int i=41; i>=0; —i) vect[i] = i; // BAD, BAD, BAD
In this snippet, after the call to reserve, the vector is still empty. Therefore, every single one of the expressions vect[i] refers to an invalid element location. The hideous part is that in all likelihood, the runtime will not signal an access violation, because you will be writing to heap memory that was allocated by the call to reserve(42). But your vector is still empty. For a more thorough discussion of these issues, see for example Herb Sutter’s Guru of the Week Question #74 [3].
std::list
STL lists can be pictured as classical doubly linked lists, and it is hard to imagine an STL implementation that would not implement them exactly that way. The characteristic property of lists is that insertion and removal of elements at any position happens in constant time; that is, it is independent of the current size of the list and of the position of the insertion or removal. This is of course because inserting and removing from a list requires no more than bending a few pointers. The tradeoff for this advantage over std::vector is an overhead of two pointers per element, and a cost per element access that is now proportional to its distance from the head node. This latter point is emphasized by the fact that std::list does not define operator[]. In order to access the n-th element of a list, you have to actually make n hops from the beginning of the list. If, for example, li is a list of integers that contains eight or more elements, then this is how you retrieve the eighth element:
std::list<int>::iterator it = li.begin(); for( int j=0; j<7; ++j ) ++it; int nElementAtSeven = *it;
You cannot even replace the for-loop by writing it+7. The STL does have a function advance to advance iterators by any number of steps, but for list iterators, advance won’t be able to do better than the for-loop above.
std::deque
std::deque (pronounced "deck" by most people, short for "double ended queue") is a variant of std::vector that is typically implemented as a segmented array, that is, as a list of chunks of contiguous memory. std::deque’s added benefit over vectors is that it allows amortized constant-time insertion and removal of an element not only at the end, but at the beginning as well. The tradeoff is a moderate space overhead and a performance penalty on certain operations such as incrementing an iterator. std::deque can be viewed as a compromise between vector and list: it retains more of vector’s efficiency than list does, but it offers more efficient insertion and removal — only at the begin position and not everywhere, as list does.
std::set
STL sets are containers that are optimized for fast lookup of elements. They are typically implemented as rather sophisticated binary trees such as red-and-black trees. This means that there is a space overhead, typically of three pointers per element [4]. More conspicuously, there is a requirement on the type of elements that a set can store: elements must be comparable via operator<, or alternatively, via a user-defined binary predicate. Matt Austern’s book [2] explains precisely what the requirements on the ordering relation are. For most practical purposes, it suffices to use your intuitive understanding of what "ordered" means. For example, if a < b and b < a are both true, then "<" is not an ordering.
Since the elements of a set are internally stored in ascending order, they can be looked up efficiently. The time required to find an element in a set, or to determine that it is not in there, is proportional to the logarithm of the number of elements in the set. In order to understand the enormous efficiency of this relationship, recall that the (base 2) logarithm of 232 equals 32.
A good example for the judicious use of a set would be our example of Listing 1. Listing 2 shows the same example, using std::set instead of std::vector. The most important thing to note here is that you must use the member function std::set::find, not the free-standing algorithm std::find. Since the latter algorithm gets its input in the form of two iterators, it does not know whether the input comes from a vector or a set or wherever else. It can only give you the default (rotten) linear time complexity, as opposed to the logarithmic complexity of std::set::find.
std::multiset
An std::multiset is very similar to an std::set. The only difference is that multisets can store elements having the same value multiple times. Plain sets, by contrast, behave like sets in the mathematical sense of the word, where each element in the set must be unique.
std::map
STL maps are similar to sets insofar as they are optimized for fast lookup. The difference is that maps store key-value pairs rather than plain elements. Elements in a map can then be looked up by key. In other words, STL maps are what are also known as associative arrays. This is emphasized by the fact that std::map implements operator[].
A good example application of std::map is a program that keeps track of the number of times each word occurs in a text. This is shown in a nutshell in Listing 3. As a little homework assignment until my next column, I encourage you to use your STL documentation to fully understand the code of Listing 3. I will explain it in detail at the beginnning of the next column.
std::multimap
std::multimap relates to std::map in the same way that std::multiset relates to std::set. Multimaps can store more than one key-value pair that have the same key. To lookup the entire range of elements with a given key, std::multiset provides the member functions lower_bound and upper_bound.
Hash Tables
There is one type of container that is conspicuously absent from the STL specification, namely, hash tables. As far as functionality is concerned, std::map can always be used when you wish you had a hash table. But there can be good reasons for wanting a hash table and not an std::map (such as better performance when the elements to be stored lend themselves easily to the definition of a hash function). Therefore, many STL implementations provide hash tables as an addition. Moreover, there is a lot of pressure on the standards committee to add hash tables to the STL specification, so stay tuned.
Notes and References
[1] See the sidebar "Standards Update" in Herb Sutter’s column, "Sutter’s Mill," in the January 2001 issue of CUJ.
[2] Matthew H. Austern. Generic Programming and the STL (Addison Wesley, 1998).
[3] <www.peerdirect.com/resources/gotw074a.html>
[4] The third pointer is a node back-pointer that is needed for efficient iteration through the container.
Thomas Becker works as a senior software engineer for Zephyr Associates, Inc. in Zephyr Cove, NV. He can be reached at [email protected].
