Kinds of Containers
The STL has both container concepts and container types. The concepts are general categories with names such as container, sequence container, and associative container. The container types are templates you can use to create specific container objects. The original 11 container types are deque, list, queue, priority_queue, stack, vector, map, multimap, set, multiset, and bitset. (This chapter doesn’t discuss bitset, which is a container for dealing with data at the bit level.) C++11 adds forward_list, unordered_map, unordered_multimap, unordered_set, and unordered_multiset, and it moves bitset from the container category into its own separate category. Because the concepts categorize the types, let’s start with them.
Container Concepts
No type corresponds to the basic container concept, but the concept describes elements common to all the container classes. It’s sort of a conceptual abstract base class—conceptual because the container classes don’t actually use the inheritance mechanism. Or to put it another way, the container concept lays down a set of requirements that all STL container classes must satisfy.
A container is an object that stores other objects, which are all of a single type. The stored objects may be objects in the OOP sense, or they may be values of built-in types. Data stored in a container is owned by the container. That means when a container expires, so does the data stored in the container. (However, if the data are pointers, the pointed-to data does not necessarily expire.)
You can’t store just any kind of object in a container. In particular, the type has to be copy constructable and assignable. Basic types satisfy these requirements, as do class types—unless the class definition makes one or both of the copy constructor and the assignment operator private or protected. (C++11 refines the concepts, adding terms such as CopyInsertable and MoveInsertable, but we’ll take a more simplified, if less precise, overview.)
The basic container doesn’t guarantee that its elements are stored in any particular order or that the order doesn’t change, but refinements to the concept may add such guarantees. All containers provide certain features and operations. Table 16.5 summarizes several of these common features. In the table, X represents a container type (such as vector), T represents the type of object stored in the container, a and b represent values of type X, r is a value of type X&, and u represents an identifier of type X (that is, if X represents vector<int>, then u is a vector<int> object).
Table 16.5. Some Basic Container Properties
The Complexity column in Table 16.5 describes the time needed to perform an operation. This table lists three possibilities, which, from fastest to slowest, are as follows:
• Compile time
• Constant time
• Linear time
If the complexity is compile time, the action is performed during compilation and uses no execution time. A constant complexity means the operation takes place during runtime but doesn’t depend on the number of elements in an object. A linear complexity means the time is proportional to the number of elements. Thus, if a and b are containers, a == b has linear complexity because the == operation may have to be applied to each element of the container. Actually, that is a worst-case scenario. If two containers have different sizes, no individual comparisons need to be made.
Complexity requirements are characteristic of the STL. Although the details of an implementation may be hidden, the performance specifications should be public so that you know the computing cost of doing a particular operation.
C++11 Additions to Container Requirements
Table 16.6 shows some additions C++11 has made to the general container requirements. The table uses the notation rv to denote a non-constant rvalue of type X (for example, the return value of a function). Also the requirement in Table 16.6 that X::iterator satisfy the requirements for a forward iterator is a change from the former requirement that it just not be an output iterator.
Table 16.6. Some Added Basic Container Requirements (C++11)
The difference between copy construction and copy assignment on the one hand and move construction and move assignment on the other hand is that a copy operation leaves the original unchanged, whereas a move operation can alter the original, perhaps transferring ownership without doing any copying When the source object is temporary, move operations can provide more efficient code than does regular copying. Chapter 18 discusses move semantics further.
Sequences
You can refine the basic container concept by adding requirements. The sequence is an important refinement because several of the STL container types—deque, forward_list (C++11), list, queue, priority_queue, stack, and vector—are sequences. (Recall that a queue allows elements to be added at the rear end and removed from the front. A double-ended queue, represented by deque, allows addition and removal at both ends.) The requirement that the iterator be at least a forward iterator guarantees that the elements are arranged in a definite order that doesn’t change from one cycle of iteration to the next. The array class also is classified as a sequence container, although it doesn’t satisfy all the requirements.
The sequence also requires that its elements be arranged in strict linear order. That is, there is a first element, there is a last element, and each element but the first and last has exactly one element immediately ahead of it and one element immediately after it. An array and a linked list are examples of sequences, whereas a branching structure (in which each node points to two daughter nodes) is not.
Because elements in sequence have a definite order, operations such as inserting values at a particular location and erasing a particular range become possible. Table 16.7 lists these and other operations required of a sequence. The table uses the same notation as Table 16.5, with the addition of t representing a value of type T—that is, the type of value stored in the container, of n, an integer, and of p, q, i, and j, representing iterators.
Table 16.7. Sequence Requirements
Because the deque, list, queue, priority_queue, stack, and vector template classes are all models of the sequence concept, they all support the operators in Table 16.7. In addition, there are operations that are available to some of these six models. When allowed, they have constant-time complexity. Table 16.8 lists these additional operations.
Table 16.8. Optional Sequence Requirements
Table 16.8 merits a comment or two. First, notice that a[n] and a.at(n) both return a reference to the nth element (numbering from 0) in a container. The difference between the two is that a.at(n) does bounds checking and throws an out_of_range exception if n is outside the valid range for the container. Next, you might wonder why, say, push_front() is defined for list and deque and not for vector. Suppose you want to insert a new value at the front of a vector of 100 elements. To make room, you have to move element 99 to position 100, and then you have to move element 98 to position 99, and so on. This is an operation with linear-time complexity because moving 100 elements would take 100 times as long as moving a single element. But the operations in Table 16.8 are supposed to be implemented only if they can be performed with constant-time complexity. The design for lists and double-ended queues, however, allows an element to be added to the front without moving the other elements to new locations, so they can implement push_front() with constant-time complexity. Figure 16.4 illustrates push_front() and push_back().
Figure 16.4. push_front() and push_back().
Let’s take a closer look at the six sequence container types.
vector
You’ve already seen several examples using the vector template, which is declared in the vector header file. In brief, vector is a class representation of an array. The class provides automatic memory management that allows the size of a vector object to vary dynamically, growing and shrinking as elements are added or removed. It provides random access to elements. Elements can be added to or removed from the end in constant time, but insertion and removal from the beginning and the middle are linear-time operations.
In addition to being a sequence, a vector container is also a model of the reversible container concept. This adds two more class methods: rbegin() returns an iterator to the first element of the reversed sequence, and rend() returns a past-the-end iterator for the reversed sequence. So if dice is a vector<int> container and Show(int) is a function that displays an integer, the following code displays the contents of dice first in forward order and then in reverse order:
for_each(dice.begin(), dice.end(), Show); // display in order
cout << endl;
for_each(dice.rbegin(), dice.rend(), Show); // display in reversed order
cout << endl;
The iterator returned by the two methods is of a class scope type reverse_iterator. Recall that incrementing such an iterator causes it to move through a reversible container in reverse order.
The vector template class is the simplest of the sequence types and is considered the type that should be used by default unless the program requirements are better satisfied by the particular virtues of the other types.
deque
The deque template class (declared in the deque header file) represents a double-ended queue, a type often called a deque (pronounced “deck”), for short. As implemented in the STL, it’s a lot like a vector container, supporting random access. The main difference is that inserting and removing items from the beginning of a deque object are constant-time operations instead of being linear-time operations the way they are for vector. So if most operations take place at the beginning and ends of a sequence, you should consider using a deque data structure.
The goal of constant-time insertion and removal at both ends of a deque makes the design of a deque object more complex than that of a vector object. Thus, although both offer random access to elements and linear-time insertion and removal from the middle of a sequence, the vector container should allow faster execution of these operations.
list
The list template class (declared in the list header file) represents a doubly linked list. Each element, other than the first and last, is linked to the item before it and the item following it, implying that a list can be traversed in both directions. The crucial difference between list and vector is that list provides for constant-time insertion and removal of elements at any location in the list. (Recall that the vector template provides linear-time insertion and removal except at the end, where it provides constant-time insertion and removal.) Thus, vector emphasizes rapid access via random access, whereas list emphasizes rapid insertion and removal of elements.
Like vector, list is a reversible container. Unlike vector, list does not support array notation and random access. Unlike a vector iterator, a list iterator remains pointing to the same element even after items are inserted into or removed from a container. For example, suppose you have an iterator pointing to the fifth element of a vector container. Then suppose you insert an element at the beginning of the container. All the other elements have to be moved to make room, so after the insertion, the fifth element now contains the value that used to be in the fourth element. Thus, the iterator points to the same location but to different data. Inserting a new element into a list, however, doesn’t move the existing elements; it just alters the link information. An iterator pointing to a certain item still points to the same item, but it may be linked to different items than before.
The list template class has some list-oriented member functions in addition to those that come with sequences and reversible containers. Table 16.9 lists many of them. (For a complete list of STL methods and functions, see Appendix G.) The Alloc template parameter is one you normally don’t have to worry about because it has a default value.
Table 16.9. Some list Member Functions
Listing 16.12 illustrates these methods, along with the insert() method, which comes with all STL classes that model sequences.
// list.cpp -- using a list
#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
void outint(int n) {std::cout << n << " ";}
int main()
{
using namespace std;
list<int> one(5, 2); // list of 5 2s
int stuff[5] = {1,2,4,8, 6};
list<int> two;
two.insert(two.begin(),stuff, stuff + 5 );
int more[6] = {6, 4, 2, 4, 6, 5};
list<int> three(two);
three.insert(three.end(), more, more + 6);
cout << "List one: ";
for_each(one.begin(),one.end(), outint);
cout << endl << "List two: ";
for_each(two.begin(), two.end(), outint);
cout << endl << "List three: ";
for_each(three.begin(), three.end(), outint);
three.remove(2);
cout << endl << "List three minus 2s: ";
for_each(three.begin(), three.end(), outint);
three.splice(three.begin(), one);
cout << endl << "List three after splice: ";
for_each(three.begin(), three.end(), outint);
cout << endl << "List one: ";
for_each(one.begin(), one.end(), outint);
three.unique();
cout << endl << "List three after unique: ";
for_each(three.begin(), three.end(), outint);
three.sort();
three.unique();
cout << endl << "List three after sort & unique: ";
for_each(three.begin(), three.end(), outint);
two.sort();
three.merge(two);
cout << endl << "Sorted two merged into three: ";
for_each(three.begin(), three.end(), outint);
cout << endl;
return 0;
}
Here is the output of the program in Listing 16.12:
List one: 2 2 2 2 2
List two: 1 2 4 8 6
List three: 1 2 4 8 6 6 4 2 4 6 5
List three minus 2s: 1 4 8 6 6 4 4 6 5
List three after splice: 2 2 2 2 2 1 4 8 6 6 4 4 6 5
List one:
List three after unique: 2 1 4 8 6 4 6 5
List three after sort & unique: 1 2 4 5 6 8
Sorted two merged into three: 1 1 2 2 4 4 5 6 6 8 8
Program Notes
The program in Listing 16.12 uses the for_each() algorithm and an outint() function to display the lists. With C++11, you could use the range-based for loop instead:
for (auto x : three) cout << x << " ";
The main difference between insert() and splice() is that insert() inserts a copy of the original range into the destination, whereas splice() moves the original range into the destination. Thus, after the contents of one are spliced to three, one is left empty. (The splice() method has additional prototypes for moving single elements and a range of elements.) The splice() method leaves iterators valid. That is, if you set a particular iterator to point to an element in one, that iterator still points to the same element after splice() relocates it in three.
Notice that unique() only reduces adjacent equal values to a single value. After the program executes three.unique(), three still contains two fours and two sixes that weren’t adjacent. But applying sort() and then unique() does limit each value to a single appearance.
There is a nonmember sort() function (Listing 16.9), but it requires random access iterators. Because the trade-off for rapid insertion is to give up random access, you can’t use the nonmember sort() function with a list. Therefore, the class includes a member version that works within the restrictions of the class.
The list Toolbox
The list methods form a handy toolbox. Suppose, for example, that you have two mailing lists to organize. You could sort each list, merge them, and then use unique() to remove multiple entries.
The sort(), merge(), and unique() methods also each have a version that accepts an additional argument to specify an alternative function to be used for comparing elements. Similarly, the remove() method has a version with an additional argument that specifies a function used to determine whether an element is removed. These arguments are examples of predicate functions, a topic to which we’ll return later.
forward_list (C++11)
C++11 adds forward_list as a container class. This class implements a singly linked list. In this kind of list, each item is linked just to the next item, but not to the preceding item. Therefore, the class requires just a forward iterator, not a bidirectional one. Thus, unlike vector and list, forward_list isn’t a reversible container. Compared to list, forward_list is simpler, more compact, but with fewer features.
queue
The queue template class (declared in the queue—formerly queue.h—header file) is an adapter class. Recall that the ostream_iterator template is an adapter that allows an output stream to use the iterator interface. Similarly, the queue template allows an underlying class (deque, by default) to exhibit the typical queue interface.
The queue template is more restrictive than deque. Not only does it not permit random access to elements of a queue, the queue class doesn’t even allow you to iterate through a queue. Instead, it limits you to the basic operations that define a queue. You can add an element to the rear of a queue, remove an element from the front of a queue, view the values of the front and rear elements, check the number of elements, and test to see if a queue is empty. Table 16.10 lists these operations.
Note that pop() is a data removal method, not a data retrieval method. If you want to use a value from a queue, you first use front() to retrieve the value and then use pop() to remove it from the queue.
priority_queue
The priority_queue template class (declared in the queue header file) is another adapter class. It supports the same operations as queue. The main difference between the two is that with priority_queue, the largest item gets moved to the front of the queue. (Life is not always fair, and neither are queues.) An internal difference is that the default underlying class is vector. You can alter the comparison used to determine what gets to the head of the queue by providing an optional constructor argument:
priority_queue<int> pq1; // default version
priority_queue<int> pq2(greater<int>); // use greater<int> to order
The greater<>() function is a predefined function object, and it is discussed later in this chapter.
stack
Like queue, stack (declared in the stack—formerly stack.h—header file) is an adapter class. It gives an underlying class (vector, by default) the typical stack interface.
The stack template is more restrictive than vector. Not only does it not permit random access to elements of a stack, the stack class doesn’t even allow you to iterate through a stack. Instead, it limits you to the basic operations that define a stack. You can push a value onto the top of a stack, pop an element from the top of a stack, view the value at the top of a stack, check the number of elements, and test whether the stack is empty. Table 16.11 lists these operations.
Much as with queue, if you want to use a value from a stack, you first use top() to retrieve the value, and then you use pop() to remove it from the stack.
array (C++11)
The array template class, introduced in Chapter 4 and defined in the array header file, is not an STL container because it has a fixed size. Thus, operations that would resize a container, such as push_back() and insert(), are not defined for array. But those member functions that do make sense, such as operator[]() and at(), are provided. And you can use many standard STL algorithms, such as copy() and for_each(), with array objects.