Chapter 3. Container Basics
Ah, when she moved, she moved more ways than one:
The shapes a bright container can contain!
— “I Knew a Woman”
THEODORE ROETHKE
The Standard Template Library, more commonly known as the STL,[1] is the invention of Dave Musser, Alex Stepanov, and Meng Lee. The design of the STL factors common programming tasks into four fundamental components: sequences, algorithms, iterators, and callable types.[2] As we’ll see, the STL and the standard C++ library provide templates that aid in programming with all four of these components.
In addition, the STL and the standard C++ library have several containers that hold sequences of elements. The TR1 library provides five new containers: a fixed-size array (Chapter 4), unordered sets, unordered multisets, unordered maps, and unordered multimaps (Chapter 5).
3.1. STL Components
A sequence is an ordered series of zero or more elements. An algorithm performs operations on the elements of a sequence, using iterators to access individual elements. An iterator is a generalization of a pointer; it can be dereferenced to get to the sequence element that it points to, and it can be incremented so that it points to the next element in the sequence.[3] One iterator is reachable from another iterator if it can be incremented zero or more times to get a value that compares equal to the other iterator. A range is a pair of iterators [first, last) where last is reachable from first. An input sequence is a range. The first iterator points to the current element, and the second iterator points to a position that’s past the end of the sequence. When the two iterators compare equal, the sequence is empty. For example, an algorithm to find the maximum value in a nonempty sequence could be written like this:
Example 3.1. Input Sequence (contbasic/input.cpp)
#include <iostream>
using std::cout;
template <class Iter>
Iter maximum(Iter first, Iter last)
{ // algorithm to find maximum value in nonempty sequence
Iter res = first++;
while (first != last)
{ // check current element
if (*res < *first)
res = first;
++first;
}
return res;
}
int main()
{ // demonstrate use of input sequence
const int NVALS = 6;
int values[NVALS] = { 3,1,9,4,5,7};
cout << "maximum: " <<
*maximum(values, values + NVALS) << '
';
return 0;
}
An output sequence is designated by a single iterator. If the iterator points to an element of a preexisting series of elements, assigning to the dereferenced iterator overwrites the value of the current element. In this case, an algorithm that writes to the output sequence must be written so that it doesn’t write past the end of the sequence, either by passing an element count to the algorithm or by passing an input sequence that’s no longer than the output sequence.
Example 3.2. Counted Output Sequence (contbasic/countoutput.cpp)
#include <iostream>
using std::cout;
template <class Iter>
void setcount(Iter first, int count)
{ // algorithm to write successive values to sequence
for (int i = 0; i < count; ++i)
*first++ = i;
}
int main()
{ // demonstrate use of output sequence
const int NVALS = 6;
int values[NVALS];
setcount (values, NVALS);
for (int i = 0; i < NVALS; ++i)
cout << values[i] << ' ';
cout << '
';
return 0;
}
The output sequence doesn’t have to be a series of existing elements, however. An insert iterator creates a new element whenever the code assigns to the dereferenced iterator. The underlying sequence can be thought of as an unbounded series of uninitialized elements. Another form of iterator writes to a data sink, such as a file. In both cases, there is no need—nor any way, in general—to check for the end of the output sequence.
Example 3.3. Unbounded Output Sequence (contbasic/unboundedoutput.cpp)
#include <iostream>
#include <iterator>
using std::iterator; using std::output_iterator_tag;
using std::cout;
struct write_iter : iterator <output_iterator_tag, int>
{ // iterator that writes to cout
struct writer
{ // proxy with assignment operator
template <class Ty> writer& operator=(const Ty& val)
{ // write the passed value
cout << val << ' ';
return *this;
}
};
writer operator*() const
{ // return a proxy object
return writer();
}
write_iter& operator++()
{ // do nothing
return *this;
}
const write_iter& operator++(int)
{ // do nothing
return *this;
}
};
template <class Iter>
void setcount (Iter first, int count)
{ // write successive values to sequence
for (int i = 0; i < count; ++i)
* first++ = i;
}
int main()
{ // demonstrate use of unbounded output iterator
const int NVALS = 6;
setcount(write_iter(), NVALS);
return 0;
}
Some algorithms take a callable object[4] as one of their arguments. Algorithms that take a callable object with a unary function call operator typically call that object with each element in their input sequence.
Example 3.4. Unary Callable Object (contbasic/unary.cpp)
#include <algorithm>
#include <functional>
#include <iostream>
using std::for_each; using std::unary_function;
using std::cout;
template <class Ty>
struct writer : unary_function<Ty, void>
{ // write values
void operator()(const Ty& val)
{ // write the passed value
cout << val << ' ';
}
};
int main ()
{ // demonstrate use of unary function object
const int NVALS = 6;
int values[NVALS] = { 3, 1, 9, 4, 5, 7 };
for_each(values, values + NVALS, writer<int>());
return 0;
}
Algorithms that take a callable object with a binary function call operator call that object with two elements. For some algorithms, both elements come from a single input sequence; for others, they come from two input sequences.
Example 3.5. Binary Callable Object (contbasic/binary.cpp)
#include <functional>
#include <iostream>
using std::binary_function;
using std::cout;
template <class Ty>
struct lt : binary_function<Ty, Ty, bool>
{ // compare values
bool operator()(const Ty& val0, const Ty& val1)
{ // return val0< val1
return val0 < val1;
}
};
template <class Iter, class Cmp>
void merge (Iter first1, Iter last1,
Iter first2, Iter last2,
Iter dest, Cmp cmp)
{ // merge sorted ranges
while (first1 != last1 && first2 != last2)
{ // copy lesser element to output sequence
if (cmp (*first1, *first2))
*dest++ = *first1++;
else
*dest++ = *first2++;
}
while (first1 != last1)
*dest++ = *first1++;
while (first2 != last2)
*dest++ = *first2++;
}
int main()
{ // demonstrate use of binary function object
const int NVAL0 = 6;
const int NVAL1 = 7;
const int NRES = NVAL0 + NVAL1;
int values0[NVAL0] = { 1, 4, 9, 16, 25, 36 };
int values1[NVAL1] = { 1, 1, 2, 3, 5, 8, 13 };
int res[NRES];
merge(values0, values0 + NVAL0,
values1, values1 + NVAL1,
res, lt<int>());
for (int i = 0; i < NRES; ++i)
cout << res[i] << ' ';
cout << '
';
return 0;
}
3.2. Containers
In addition to the fundamental components described in the previous section, the STL and the standard C++ library provide a set of containers. Each container holds elements that can be stored and accessed according to a strategy that is specific to the container. The elements constitute the container’s controlled sequence. You can access this sequence by calling the member functions begin and end, which return, respectively, an iterator that points to the first element in the controlled sequence and an iterator that points past the end of the controlled sequence.
Example 3.6. Container Iterators (contbasic/contiter.cpp)
#include <iostream>
#include <vector>
using std::cout;
using std::vector;
template <class Iter>
Iter maximum (Iter first, Iter last)
{ // find maximum value in nonempty sequence
Iter res = first++;
while (first != last)
{ // check current element
if (*res < *first)
res = first;
++first;
}
return res;
}
int main ()
{ // demonstrate use of vector for input sequence
const int NVALS = 6;
int values[NVALS] = { 3, 1, 9, 4, 5, 7 };
vector<int> vec(values, values + NVALS);
cout << "maximum: " <<
*maximum (vec.begin(), vec.end ()) << '
';
return 0;
}
The standard C++ library has two kinds of containers: sequence containers and associative containers. In a sequence container, the elements are organized linearly. You can insert elements at any point in that linear sequence, and the order of the elements in the sequence pointed to by the iterators [begin(), end()) is determined by the locations where the elements were inserted.
Example 3.7. Sequence Container (contbasic/seqcont.cpp)
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using std::copy; using std::ostream_iterator;
using std::vector; using std::cout;
int main()
{ // show order of elements in sequence container
vector <int> cont;
cont.push_back(0);
cont.push_back(2);
cont.push_back(4);
cont.push_back(1);
cont.push_back(3);
cont.push_back(5);
copy(cont.begin(), cont.end(),
ostream_iterator <int>(cout, " "));
cout << '
';
return 0;
}
Three sequence containers are in the standard C++ library. The container vector holds its elements in a contiguous array. This makes access to arbitrary elements fast but makes inserting new elements anywhere other than at the end slow. The container list holds its elements in a double-linked list. This makes access to arbitrary elements slow but makes inserting new elements anywhere in the container fast. The container deque typically holds its elements in multiple small arrays. This provides speeds that are intermediate between the speeds of vector and of list for accessing and inserting elements.
An associative container supports fast searching for elements that match a given key. The sequence pointed to by the iterators [begin(), end()) is ordered according to the values of the keys.[5]
Example 3.8. Associative Container (contbasic/assoccont.cpp)
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
using std::copy; using std::ostream_iterator;
using std::set; using std::cout;
int main ()
{ // show order of elements in associative container
set<int>cont;
cont.insert(0);
cont.insert(2);
cont.insert(4);
cont.insert(1);
cont.insert(3);
cont.insert(5);
copy(cont.begin(), cont.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
Four associative containers are in the standard C++ library. The container set supports searching for a key that has the same type as the container’s elements. Duplicate elements are not allowed. The container multiset is like a set but allows duplicate elements. The container map holds elements of type pair<const Key, Value> and supports searching for a key of type Key. Thus, it associates a key and a value. Duplicate keys are not allowed. The container multimap is like a map but allows duplicate keys.
Containers can also be reversible. A reversible container is one with a bidirectional or a random-access iterator type. Reversible containers support iterating from the end of the container back toward the beginning. The member functions rbegin() and rend() return reverse iterators. The corresponding range, [rbegin(), rend()), iterates through the same elements as [begin(), end()) but in the opposite order. All the containers in the standard C++ library are reversible.
The TR1 library provides another kind of container. An unordered associative container, like an associative container, supports fast searching for elements that match a given key. Unlike an associative container, the sequence pointed to by the iterators [begin(), end()) is unspecified.[6]
Example 3.9. Unordered Container (contbasic/unordcont.cpp)
#include <algorithm>
#include <iostream>
#include <iterator>
#include <unordered_set>
using std::copy; using std::ostream_iterator;
using std::tr1::unordered_set;
using std::cout;
int main()
{ // show order of elements in unordered associative container
unordered_set <int> cont;
cont.insert(0);
cont.insert(2);
cont.insert(4);
cont.insert(1);
cont.insert(3);
cont.insert(5);
copy(cont.begin(), cont.end(),
ostream_iterator<int>(cout, " "));
cout << '
';
return 0;
}
Four unordered associative containers are in the TR1 library. The container unordered_set is like set but doesn’t require any particular order for the contained sequence. Similarly, unordered_multiset is like multiset, unordered_map is like map, and unordered_multimap is like multimap.
Further Reading
• Generic Programming and the STL [Aus99] gives a detailed explanation of sequences, algorithms, iterators, callable types, and containers.
• The C++ Standard Library [Jos99] discusses the entire standard C++ library, including sequences, algorithms, iterators, callable types, and containers.
Exercises
Exercise 1
Suppose that you have an array of 12 int values and 2 variables of type int*:
int values[12] = { 1, 1, 2, 3, 5, 8,
13, 21, 34, 55, 89, 144 };
const int *first, *last;
After each of the following pairs of assignments, how many elements are in the sequence pointed at by the iterator range [first, last)? Write a program to verify your conclusions.
1. first = values; last = values + 12;
2. first = values + 1; last = values + 2;
3. first = values; last = values;
4. first = values + 12; last = values + 12;
Exercise 2
Repeat the previous example, using a vector<int> instead of an array to hold the int values and using a pair of iterators of type vector<int>::const_iterator instead of pointers.
Exercise 3
Write an algorithm that takes a pair of iterators designating a writable sequence of integer values. The algorithm should double each value in the controlled sequence and store the result in place of the original value. Test the algorithm by calling it on a sequence of integer values and displaying the result.
Exercise 4
Write a class that has a function call operator that takes an argument of type int and returns a value of type int that is twice the value of its argument. Modify the algorithm you wrote for the previous exercise to take a third template argument that provides the operation to perform on each element in the sequence. Test the new algorithm and the callable type by creating an object of the callable type and passing it to the algorithm along with a pair of iterators that points to a sequence of integer values and displaying the result.
Exercise 5
Rewrite the callable type that you wrote in the previous exercise so that its constructor takes a value that it stores in the object being constructed. Instead of multiplying by 2, the function call operator should multiply its argument by that stored value. Test the new callable type by creating an object that will multiply values by 3 and passing it to the algorithm that you wrote in the previous exercise.
Exercise 6
Insert a dozen or so values of type int, in no particular order, into an object of type vector<int>, and show the contents of the controlled sequence. Insert the same series of values into an object of type set<int>, and show the contents of the controlled sequence. Insert the same series of values into an object of type unordered_set<int>,[7] and show the contents of the controlled sequence.