18.2 Containers

Put all your eggs in one basket and—WATCH THAT BASKET.

MARK TWAIN, Pudd’n head Wilson

The container classes of the STL are different kinds of data structures for holding data, such as lists, queues, and stacks. Each is a template class with a parameter for the particular type of data to be stored. So, for example, you can specify a list to be a list of ints, or doubles, or strings, or any class or struct type you wish. Each container template class may have its own specialized accessor and mutator functions for adding data and removing data from the container. Different container classes may have different kinds of iterators. For example, one container class may have bidirectional iterators while another container class may have only forward iterators. However, whenever they are defined the iterator operators and the member functions begin() and end() have the same meaning for all STL container classes.

Sequential Containers

A sequential container arranges its data items into a list so that there is a first element, a next element, and so forth up to a last element. The linked lists we discussed in Chapter 13 are examples of a kind of list. The lists we discussed in Chapter 13 are sometimes called singly linked lists because there is only one link from one location to another. The STL has no container corresponding to such singly linked lists, although some implementations do offer an implementation of them, typically under the name slist. The simplest list that is part of the STL is the doubly linked list, which is the template class named list. The difference between these two kinds of lists is illustrated in Display 18.4.

Display 18.4 Two Kinds of Lists

Figure 18.4 Full Alternative Text

The lists in Display 18.4 contain the three integer values 1, 2, and 3 in that order. The types for the two lists are slist<int> and list<int>. That display also indicates the location of the iterators begin() and end(). We have not yet told you how you can enter the integers into the lists.

In Display 18.4 we have drawn our singly and doubly linked lists as nodes and pointers of the form discussed in Chapter 14. The STL class list and the nonstandard class slist might (or might not) be implemented in this way. However, when using the STL template classes, you are shielded from these implementation details. So, you simply think in terms of locations for the data (which may or may not be nodes) and iterators (not pointers). You can think of the arrows in Display 18.4 as indicating the directions for ++ (which is down) and −− (which is up in Display 18.4).

We wanted to present the template class slist to help give a context for the sequential containers. It corresponds to what we discussed most in Chapter 13, and it is the first thing that comes to the mind of most programmers when you mention linked lists. However, since the template class slist is not standard, we will discuss it no more. If your implementation offers the template class slist and you want to use it, the details are similar to those we will describe for list, except that the decrement operators −− (prefix and postfix) are not defined for slist.

A simple program using the STL template class list is given in Display 18.5. The function push_back adds an element to the end of the list. Notice that for the list template class, the dereferencing operator gives you access to the data for reading and for changing the data. Also notice that with the list template class and all the template classes and iterators of the STL, all definitions are placed in the std namespace.

Display 18.5 Using the list Template Class

 1    //Program to demonstrate the STL template class list.
 2    #include <iostream>
 3    #include <list>
 4    using std::cout;
 5    using std::endl;
 6    using std::list;
 7     
 8    int main()
 9    {
10        list<int> listObject;
11     
12	  for (int i = 1; i <= 3; i++)
13            list_object.push_back(i);
14     
15        cout << "List contains:\n";
16        list<int>::iterator iter;
17        for (iter = listObject.begin(); iter != listObject.end(); iter++)
18            cout << *iter << " ";
19        cout << endl;
20     
21        cout << "Setting all entries to 0:\n";
22        for (iter = listObject.begin(); iter != listObject.end(); iter++)
23            *iter = 0;
24     
25        cout << "List now contains:\n";
26        for (iter = listObject.begin(); iter != listObject.end(); iter++)
27            cout << *iter << " ";
28        cout << endl;
29     
30        return 0;
31    }

Sample Dialogue

List contains:
1 2 3
Setting all entries to 0:
List now contains:
0 0 0

Note that Display 18.5 would compile and run exactly the same if we replace list and list<int> with vector and vector<int>, respectively. This uniformity of usage is a key part of the STL syntax.

There are, however, differences between a vector and a list container. One of the main differences is that a vector container has random access iterators while a list has only bidirectional iterators. For example, if you start with Display 18.2, which uses random access, and replace all occurrences of vector and vector<char> with list and list<char>, respectively, and then compile the program, you will get a compiler error. (You will get an error message even if you delete the statements containing container[i] or container[2].)

The basic sequential container template classes of the STL are given in Display 18.6. A sample of some member functions is given in Display 18.7. Other containers, such as stacks and queues, can be obtained from these using techniques discussed in the subsection entitled “Container Adapters stack and queue.” All these sequence template classes have a destructor that returns storage for recycling.

Display 18.6 STL Basic Sequential Containers

Template Class Name	Iterator Type Names	Kind of Iterators	Library Header File
slist	slist<T>::iterator	mutable forward	<slist>
Warning: slist is not part of the STL.	slist<T>::const_iterator	constant forward	Depends on implementation and may not be available.
list	list<T>::iterator	mutable bidirectional	<list>
	list<T>::const_iterator	constant bidirectional
	list<T>::reverse_iterator	mutable bidirectional
	list<T>::const_reverse_iterator	constant bidirectional
vector	vector<T>::iterator	mutable random access	<vector>
	vector<T>::const_iterator	constant random access
	vector<T>::reverse_iterator	mutable random access
	vector<T>::const_reverse_iterator	constant random access
deque	deque<T>::iterator	mutable random access	<deque>
	deque<T>::const_iterator	constant random access
	deque<T>::reverse_iterator	mutable random access
	deque<T>::const_reverse_iterator	constant random access

Display 18.7 Some Sequential Container Member Functions

Member Function (c is a Container Object)	Meaning
c.size()	Returns the number of elements in the container.
c.begin()	Returns an iterator located at the first element in the container.
c.end()	Returns an iterator located one beyond the last element in the container.
c.rbegin()	Returns an iterator located at the last element in the container. Used with reverse_iterator. Not a member of slist.
c.rend()	Returns an iterator located one beyond the first element in the container. Used with reverse_iterator. Not a member of slist.
c.push_back(Element)	Insert the Element at the end of the sequence. Not a member of slist.
c.push_front(Element)	Insert the Element at the front of the sequence. Not a member of vector.
c.insert(Iterator, Element)	Insert a copy of Element before the location of Iterator.
c.erase(Iterator)	Removes the element at location Iterator. Returns an iterator at the location immediately following. Returns c.end() if the last element is removed.
c.clear()	A void function that removes all the elements in the container.
c.front()	Returns a reference to the element in the front of the sequence. Equivalent to *(c.begin()).
c1 == c2	True if c1.size() == c2.size() and each element of c1 is equal to the corresponding element of c2.
c1 != c2	!(c1 == c2)
<All the sequential containers discussed in this section also have a default constructor, a copy constructor, and various other constructors for initializing the container to default or specified elements. Each also has a destructor that returns all storage for recycling and a well-behaved assignment operator.>

Deque, pronounced “d-queue” or “deck,” stands for “doubly ended queue.” A deque is a kind of super queue. With a queue you add data at one end of the data sequence and remove data from the other end. With a deque you can add data at either end and remove data from either end. The template class deque is a template class for a deque with a parameter for the type of data stored.

Sequential Containers

A sequential container arranges its data items into a list so that there is a first element, a next element, and so forth up to a last element. The sequential container template classes that we have discussed are slist, list, vector, and deque.

Pitfall Iterators and Removing Elements

When you add or remove an element to or from a container, that can affect other iterators. In general, there is no guarantee that the iterators will be located at the same element after an addition or deletion. Some containers do, however, guarantee that the iterators will not be moved by additions or deletions, except of course if the iterator is located at an element that is removed.

Of the template classes we have seen so far, list and slist guarantee that their iterators will not be moved by additions or deletions, except of course if the iterator is located at an element that is removed. The template classes vector and deque make no such guarantee.

Programming Tip Type Definitions in Containers

The STL container classes contain type definitions that can be handy when programming with these classes. We have already seen that STL container classes may contain the type names iterator, const_iterator, reverse_iterator, and const_reverse_iterator (and hence must contain their type definitions behind the scenes). There are typically other type definitions as well.

All the template classes we have discussed so far have the defined types value_type and size_type. The type value_type is the type of the elements stored in the container. For example, list<int>::value_type is another name for int. Another defined type is size_type, which is an unsigned integer type that is the return type for the member function size. As we noted in Chapter 8, the size_type for the vector template class is unsigned int, although most compilers will be happy if you think of the type as just plain int.

Self-Test Exercises

7. What is a major difference between a vector and a list?

8. Which of the template classes slist, list, vector, and deque have the member function push_back?

9. Which of the template classes slist, list, vector, and deque have random access iterators?

10. Which of the template classes slist, list, vector, and deque can have mutable iterators?

Container Adapters stack and queue

Container adapters are template classes that are implemented on top of other classes. For example, the stack template class is by default implemented on top of the deque template class, which means that buried in the implementation of the stack is a deque, which is where all the data resides. However, you are shielded from this implementation detail and see a stack as a simple last-in/first-out data structure.

Other container adapter classes are the queue and priority_queue template classes. Stacks and queues were discussed in Chapter 13. A priority queue is like a queue with the additional property that each entry is given a priority when it is added to the queue. If all entries have the same priority, then entries are removed from a priority queue in the same manner as they are removed from a queue. If items have different priorities, the higher-priority items are removed before lower-priority items. We will not be discussing priority queues in any detail, but mention it for those who may be familiar with the concept.

Although an adapter template class has a default container class on top of which it is built, you may choose to specify a different underlying container, for efficiency or other reasons depending on your application. For example, any sequential container may serve as the underlying container for a stack and any sequential container other than vector may serve as the underlying container for a queue. The default underlying data structure is the deque for both the stack and the queue. For a priority_queue, the default underlying container is a vector. If you are happy with the default underlying container type, then a container adapter looks like any other template container class to you. For example, the type name for the stack template class using the default underlying container is stack<int> for a stack of ints. If you wish to specify that the underlying container is instead the vector template class, you would use stack<int, vector<int>> as the type name. We will always use the default underlying container.

Warning

If you do specify an underlying container, be warned that C++ compilers prior to C++11 cannot compile code with two > symbols in the type expression without a space in between them. Use stack<int, vector<int> >, with a space between the last two >’s. Do not use stack<int, vector<int>>. C++11 compilers do not need a space between the two > symbols.

The member functions and other details about the stack template class are given in Display 18.8. For the queue template class these details are given in Display 18.9. A simple example of using the stack template class is given in Display 18.10.

Display 18.8 Stack Template Class

Stack Adapter Template Class Details

Type name stack<T> or stack<T, Underlying_Container> for a stack of elements of type T.

Library header: <stack>, which places the definition in the std namespace.

Defined types: value_type, size_type.

There are no iterators.

Sample Member Functions

Member Function (s is a Stack Object)	Meaning
s.size()	Returns the number of elements in the stack.
s.empty()	Returns true if the stack is empty; otherwise returns false.
s.top()	Returns a mutable reference to the top member of the stack.
s.push(Element)	Inserts a copy of Element at the top of the stack.
s.pop()	Removes the top element of the stack. Note that pop is a void function. It does not return the element removed.
s1 == s2	True if s1.size() == s2.size() and each element of s1 is equal to the corresponding element of s2; otherwise returns false.

The stack template class also has a default constructor, a copy constructor, as well as a constructor that takes an object of any sequential container class and initializes the stack to the elements in the sequence. It also has a destructor that returns all storage for recycling and a well-behaved assignment operator.

Display 18.9 Queue Template Class

Queue Adapter Template Class Details

Type name queue<T> or queue<T, Underlying_Container> for a queue of elements of type T.

For efficiency reasons, the Underlying_Container cannot be a vector type.

Library header: <queue> which places the definition in the std namespace.

Defined types: value_type, size_type.

There are no iterators.

Sample Member Functions

Member Function (q is a Queue Object)	Meaning
q.size()	Returns the number of elements in the queue.
q.empty()	Returns true if the queue is empty; otherwise returns false.
q.front()	Returns a mutable reference to the front member of the queue.
q.back()	Returns a mutable reference to the last member of the queue.
q.push(Element)	Adds Element to the back of the queue.
q.pop()	Removes the front element of the queue. Note that pop is a void function. It does not return the element removed.
q1 == q2	True if q1.size() == q2.size() and each element of q1 is equal to the corresponding element of q2; otherwise returns false.
The queue template class also has a default constructor, a copy constructor, as well as a constructor that takes an object of any sequential container class and initializes the stack to the elements in the sequence. It also has a destructor that returns all storage for recycling and a well-behaved assignment operator.

Display 18.10 Program Using the Stack Template Class

Sample Dialogue

Enter a line of text:
straw
Written backward that is:
warts

Self-Test Exercises

11. What kind of iterators (forward, bidirectional, or random access) does the stack template adapter class have?

12. What kind of iterators (forward, bidirectional, or random access) does the queue template adapter class have?

13. If s is a stack<char>, what is the type of the returned value of s.pop()?

Associative Containers set and map

Associative containers are basically very simple databases. They store data, such as structs or any other type of data. Each data item has an associated value known as its key. For example, if the data is a struct with an employee’s record, the key might be the employee’s Social Security number. Items are retrieved on the basis of the key. The key type and the type for data to be stored need not have any relationship to one another, although they often are related. A very simple case is when the each data item is its own key. For example, in a set every element is its own key.

The set template class is, in some sense, the simplest container you can imagine. It stores elements without repetition. The first insertion places an element in the set. Additional insertions after the first have no effect, so no element appears more than once. Each element is its own key; basically, you just add or delete elements and ask if an element is in the set or not. Like all STL classes, the set template class was written with efficiency as a goal. In order to work efficiently, a set object stores its values in sorted order. You can specify the order used for storing elements as follows:

set<T, Ordering> s;

Ordering should be a well-behaved ordering relation that takes two arguments of type T and returns a bool value.1 T is the type of elements stored. If no ordering is specified, then the ordering is assumed to be the < relational operator. Some basic details about the set template class are given in Display 18.11. A simple example that shows how to use some of the member functions of the template class set is given in Display 18.12.

¹ The ordering must be a strict weak ordering. Most typical orderings used to implement the < operator is strict weak ordering. For those who want the details: A strict weak ordering must be: (irreflexive) Ordering(x, x) is always false; (antisymmetric) Ordering(x, y) implies !Ordering(y, x); (transitive) Ordering(x, y) and Ordering(y, z) imply Ordering(x, z); and (transitivity of equivalence) if x is equivalent to y and y is equivalent to z, then x is equivalent to z. Two elements x and y are equivalent if Ordering(x, y)and Ordering(y, x) are both false.

Display 18.11 set Template Class

set Template Class Details

Type name set<T> or set<T, Ordering> for a set of elements of type T. The Ordering is used to sort elements for storage. If no Ordering is given, the ordering used is the binary operator <.

Library header: <set>, which places the definition in the std namespace.

Defined types include: value_type, size_type.

Iterators: iterator, const_iterator, reverse_iterator, and const_reverse_iterator. All iterators are bidirectional and those not including const_ are mutable. begin(), end(), rbegin(), and rend() have the expected behavior. Adding or deleting elements does not affect iterators, except for an iterator located at the element removed.

Sample Member Functions

Member Function (s is a Set Object)	Meaning
s.insert(Element)	Inserts a copy of Element in the set. If Element is already in the set, this has no effect.
s.erase(Element)	Removes Element from the set. If Element is not in the set, this has no effect.
s.find(Element)	Returns a mutable iterator located at the copy of Element in the set. If Element is not in the set, s.end() is returned.
s.erase(Iterator)	Erases the element at the location of the Iterator.
s.size()	Returns the number of elements in the set.
s.empty()	Returns true if the set is empty; otherwise returns false.
s1 == s2	Returns true if the sets contains the same elements; otherwise returns false.
The set template class also has a default constructor, a copy constructor, as well as other specialized constructors not mentioned here. It also has a destructor that returns all storage for recycling and a well-behaved assignment operator.

Display 18.12 Program Using the set Template Class

Sample Dialogue

The set contains:
A B C D
Removing C.
A B D

Figure 18.12 Full Alternative Text

A map is essentially a function given as a set of ordered pairs. For each value first that appears in a pair, there is at most one value second such that the pair (first, second) is in the map. The template class map implements map objects in the STL. For example, if you want to assign a unique number to each string name, you could declare a map object as follows:

map<string, int> numberMap;

For string values known as keys, the numberMap object can associate a unique int value.

An alternate way to think of a map is as an associative array. A traditional array maps from a numerical index to a value. For example, a[10] = 5 would store the number 5 at index 10. An associative array allows you to define your own indices using the data type of your choice. For example, numberMap["c++"] = 5 would associate the integer 5 with the string “c++". For convenience, the [] square bracket operator is defined to allow you to use an array-like notation to access a map, although you also can use the insert or find methods if you want.

Like a set object, a map object stores its elements in sorted order by its key values. You can specify the ordering on keys as a third entry in the angular brackets <>. If you do not specify an ordering, a default ordering is used. The restrictions on orderings you can use is the same as those on the orderings allowed for the set template class. Note that the ordering is on key values only. The second type can be any type and need not have anything to do with any ordering. As with the set object, the sorting of the stored entries in a map object is done for reasons of efficiency.

The easiest way to add and retrieve data from a map is to use the [] operator. Given a map object m, the expression m[key] will return a reference to the data element associated with key. If no entry exists in the map for key, then a new entry will be created with the default value for the data element. For numeric data types, the default value is 0. For objects of type string, the default value is an empty string.

The [] operator can be used to add a new item to the map or to replace an existing entry. For example, the statement m[key] = newData; will create a new association between key and newData. Note that care must be taken to ensure that map entries are not created by mistake. For example, if you execute the statement val = m[key]; with the intention of retrieving the value associated with key but mistakenly enter a value for key that is not already in the map, then a new entry will be made for key with the default value and assigned into val.

Some basic details about the map template class are given in Display 18.13. In order to understand these details, you first need to know something about the pair template class.

Display 18.13 map Template Class

map Template Class Details

Type name map<KeyType, T> or map<KeyType, T, Ordering> for a map that associates (“maps”) elements of type KeyType to elements of type T.

The Ordering is used to sort elements by key value for efficient storage. If no Ordering is given, the ordering used is the binary operator <.

Library header: <map> places the definition in the std namespace.

Defined types include: key_type for the type of the key values, mapped_type for the type of the values mapped to, and size_type. (So, the defined type key_type is simply what we called KeyType earlier.)

Iterators: iterator, const_iterator, reverse_iterator, and const_reverse_iterator.

All iterators are bidirectional. Those iterators not including const_ are neither constant nor mutable, but something in between. For example, if p is of type iterator, then you change the key value but not the value of type T. Perhaps it is best, at least at first, to treat all iterators as if they were constant.

begin(), end(), rbegin(), and rend() have the expected behavior. Adding or deleting elements does not affect iterators, except for an iterator located at the element removed.

Sample Member Functions

Member Function (m is a Map Object)	Meaning
m.insert(Element)	Inserts Element in the map. Element is of type pair<KeyType, T>. Returns a value of type pair<iterator, bool>. If the insertion is successful, the second part of the returned pair is true and the iterator is located at the inserted element.
m.erase(Target_Key)	Removes the element with the key Target_Key.
m.find(Target_Key)	Returns an iterator located at the element with key value Target_Key. Returns m.end() if there is no such element.
m[Target_Key]	Returns a reference to the object associated with the key Target_Key. If the map does not already contain such an object, then a default object of type T is inserted and returned.
m.size()	Returns the number of pairs in the map.
m.empty()	Returns true if the map is empty; otherwise returns false.
m1 == m2	Returns true if the maps contains the same pairs; otherwise returns false.
The map template class also has a default constructor, a copy constructor, as well as other specialized constructors not mentioned here. It also has a destructor that returns all storage for recycling and a well-behaved assignment operator.

The STL template class pair<T1,T2> has objects that are pairs of values such that the first element is of type T1 and the second is of type T2. If aPair is an object of type pair<T1,T2>, then aPair.first is the first element, which is of type T1, and aPair.second is the second element, which is of type T2. The member variables first and second are public member variables, so no accessor or mutator functions are needed.

The header file for the pair template is <utility>. So, to use the pair template class, you need the following, or something like it, in your file:

#include <utility>
using std::pair;

The map template class uses the pair template class to store the association between the key and a data item. For example, given the definition

map<string, int> numberMap;

we can add a mapping from "c++" to the number 10 by using a pair object:

pair<string, int> toInsert("c++", 10);
numberMap.insert(toInsert);

or by using the [] operator:

numberMap["c++"] = 10;

In either case, when we access this pair using an iterator, iterator->first will refer to the key "c++" while iterator->second will refer to the data value 10. A simple example that shows how to use some of the member functions of the template class map is given in Display 18.14.

Display 18.14 Program Using the map Template Class

 1    //Program to demonstrate use of the map template class.
 2    #include <iostream>
 3    #include <map>
 4    #include <string>
 5    using std::cout;
 6    using std::endl;
 7    using std::map;
 8    using std::string;
 9    int main()
10    {
11        map<string, string> planets;
12        planets["Mercury"] = "Hot planet";
13        planets["Venus"] = "Atmosphere of sulfuric acid";
14        planets["Earth"] = "Home";
15        planets["Mars"] = "The Red Planet";
16        planets["Jupiter"] = "Largest planet in our solar system";
17        planets["Saturn"] = "Has rings";
18        planets["Uranus"] = "Tilts on its side";
19        planets["Neptune"] = "1500 mile-per-hour winds";
20        planets["Pluto"] = "Dwarf planet";
21        cout << "Entry for Mercury - " << planets["Mercury"]
22             << endl << endl;
23        if (planets.find("Mercury") != planets.end())
24            cout << "Mercury is in the map." << endl;
25        if (planets.find("Ceres") == planets.end())
26            cout << "Ceres is not in the map." << endl << endl;
27        cout << "Iterating through all planets: " << endl;
28        map<string, string>::const_iterator iter;
29        for (iter = planets.begin(); iter != planets.end(); iter++)
30        {
31            cout << iter->first << " - " << iter->second << endl;
32        }
33        return 0;
34    }

Sample Dialogue

18.2-1 Full Alternative Text

Jupiter - Largest planet in our solar system
Mars - The Red Planet
Mercury - Hot planet
Neptune - 1500 mile-per-hour winds
Pluto - Dwarf planet
Saturn - Has rings
Uranus - Tilts on its side
Venus - Atmosphere of sulfuric acid

We will mention two other associative containers, although we will not give any details about them. The template classes multiset and multimap are essentially the same as set and map, respectively, except that a multiset allows repetition of elements and a multimap allows multiple values to be associated with each key value.

C++11 and Containers

Programming Tip Use Initialization, Ranged for, and auto with Containers

Several features introduced in C++11 make it easier to work with collections. In particular, you can initialize your container objects using the uniform initializer list format, which consists of initial data in curly braces. You can also use auto and the ranged for loop to easily iterate through a container. Consider the following two initialized collection objects:

map<int, string> personIDs = {
                                  {1,"Walt"},
                                  {2,"Kenrick"}
                              };
set<string> colors = {"red","green","blue"};

We can iterate through each container conveniently using a ranged for loop and auto:

for (auto p : personIDs)
     cout << p.first << " " << p.second << endl;
for (auto p : colors)
     cout << p << " ";

The output of this snippet is:

1 Walt
2 Kenrick
blue green red

Efficiency

The STL was designed with efficiency as an important consideration. In fact, the STL implementations strive to be optimally efficient. For example, the set and map elements are stored in sorted order so that algorithms that search for the elements can be more efficient.

Each of the member functions for each of the template classes has a guaranteed maximum running time. These maximum running times are expressed using what is called big-O notation, which we discuss in Section 18.3. (Section 18.3 also gives some guaranteed running times for some of the container member functions we have already discussed. These are in the subsection entitled “Container Access Running Times.”) When using more advanced references or even later in this chapter, you will be told the guaranteed maximum running times for certain functions.

Self-Test Exercises

14. How many elements will be in the map mymap after the following code is executed?

    map<int, string> myMap;
    myMap[5] = "c++";
    cout << myMap[4] << endl;

15. Can a set have elements of a class type?

16. Suppose s is of the type set<char>. What value is returned by s.find('A') if 'A' is in s? What value is returned if 'A' is not in s?