We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Mail to Frank Brokken or use an e-mail form. Please state the concerned document version, found in the title.
C++ offers several predefined datatypes, all part of the Standard
Template Library, which can be used to implement solutions to frequently
occurring problems. The datatypes discussed in this chapter are all
containers: you can put stuff inside them, and you can retrieve the stored
information from them.
The interesting part is that the kind of data that can be stored inside these
containers has been left unspecified by the time the containers were
constructed. That's why they are spoken of as abstract containers.
The abstract containers rely heavily on templates, which are covered near
the end of the C++ Annotations, in chapter 16. However, in
order to use the abstract containers, only a minimal grasp of the template
concept is needed. In C++ a template is in fact a recipe for
constructing a function or a complete class. The recipe tries to abstract the
functionality of the class or function as much as possible from the data on
which the class or function operate. As the types of the data on which the
templates operate were not known by the time the template was constructed, the
datatypes are either inferred from the context in which a template function is
used, or they are mentioned explicitly by the time a template class is used
(the term that's used here is instantiated). In situations where the types
are explicitly mentioned, the angular bracket notation is used to indicate
which data types are required. For example, below (in section 7.1) we'll
encounter the pair container, which requires the explicit mentioning of
two data types. E.g., to define a pair variable containing both an int
and a string, the notation
pair<int, string>
myPair;
is used. Here, myPair is defined as a pair variable, containing
both an int and a string.
The angular bracket notation is used intensively in the following
discussion of the abstract container. Actually, understanding this part of
templates is the only real requirement for being able to use the abstract
containers. Now that we've introduced this notation, we can postpone the more
thorough discussion of templates to chapter 16, and get on with
their use in the form of the abstract container classes.
Most of the abstract containers are sequential containers: they represent
a series of data which can be stored and retrieved in some sequential
way. Examples are the vector, implementing an extendable array, the
list, implementing a datastructure in which insertions and deletions can
be easily realized, a queue, in which the first element that is entered
will be the first element that will be retrieved, and the stack, which is
a first in, last out datastructure.
Apart from the sequential containers, several special containers are
available. The pair is a basic container in which a pair of values (of
types that are left open for further specification) can be stored, like two
strings, two ints, a string and a double, etc.. Pairs are often used to return
data elements that naturally come in pairs. For example, the map is an
abstract container in which keys and corresponding values are stored. Elements
of these maps are returned as pairs.
A variant of the pair is the complex container, which implements
operations that are defined on complex numbers.
All abstract containers described in this chapter and the string datatype
discussed in section 3.3.3 are part of the standard template
library. There exists also an abstract container for the implementation of a
hashtable, but that container is not (yet) accepted by the ISO/ANSI
standard. The final section of this chapter will cover the
hashtable to some extent.
All containers support the = operator to assign two containers of the same
type to each other. All containers also support the ==, !=, <, <=, > and
>= operators.
Note that if a user-defined type (usually a class-type) is to be stored in
a container, the user-defined type must support
==)
<)
Closely linked to the standard template library are the generic
algorithms. These algorithms may be used to perform even more tasks than is
possible with the containers themselves, like counting, filling, merging,
filtering etc.. An overview of the generic algorithms and their applications
is given in chapter 10. Generic algorithms usually rely on the
availability of iterators, which represent begin and
endpoints for processing data stored inside the containers. The abstract
containers normally have constructors and members using iterators themselves,
and they have members returning iterators (comparable to the
string::begin() and string::end() members). In the remainder of this
chapter the use of iterators is not really covered. Refer to chapter 10
for the discussion of iterators.
The url http://www.sgi.com/Technology/STL is worth visiting by those readers who
want more information about the abstract containers and the standard template
library than can be provided in the C++ annotations.
Containers often collect data during their lifetime. When a container goes
out of scope, its destructor tries to destroy its data elements. This only
succeeds if the data elements themselves are stored inside the container. If
the data elements of containers are pointers, the data to which these pointers
point will not be destroyed, and a memory leak will result. A consequence of
this scheme is that the data stored in a container should be considered the
`property' of the container: the container should be able to destroy its data
elements when the destructor of the container is called. Consequently, the
container should not only contain no pointer data, but it should also not
contain const data elements, as these data elements cannot be destroyed by
the container's destructor.
pair container is a rather basic container. It can be used to store
two elements, called first and second, and that's about it. To define
a variable as a pair container, the header file
#include <utility>
must be included.
The data types of a pair are defined when the pair variable is
defined, using the standard template (see chapter Templates) notation:
pair<string, string>
piper("PA28", "PH-ANI"),
cessna("C172", "PH-ANG");
here, the variables piper and cessna are defined as pair variables
containing two strings. Both strings can be retrieved using the first
and second fields of the pair type:
cout << piper.first << endl << // shows 'PA28'
cessna.second << endl; // shows 'PH-ANG'
The first and second members can also be used to reassign values:
cessna.first = "C152";
cessna.second = "PH-ANW";
If a pair variable must be completely reassigned, it is also possible to
use an anonymous pair variable as the right-hand side operand of the
assignment. An anonymous variable defines a temporary variable (which receives
no name) solely for the purpose of (re)assigning another variable of the same
type. Its general form is
type(initializer list)
Note, however, that with a pair variable the type specification is not
completed when the containername pair has been mentioned. It also requires
the specification of the data types which are stored inside the pair. For this
the (template) angular bracket notation is used again. E.g., the reassignment
of the cessna pair variable could also have been accomplished as follows:
cessna = pair<string, string>("C152", "PH-ANW");
In cases like this, the type specification can become quite
elaborate, which has caused a revival of interest in the possibilities offered
by the typedef keyword. If a lot of pair<type1, type2> clauses are
used in a source, the amount of typing may be reduced and legibility might be
improved by first defining a name for the clause, and then using the defined
name later on. E.g.,
typedef pair<string, string> pairStrStr
...
cessna = pairStrStr("C152", "PH-ANW")
Apart from this (and the basic set of operations (assignment and
comparisons) the pair has no further special features. It is, however, a
basic ingredient of the upcoming abstract containers map, multimap and
hash_map.
vector class implements an (expandable) array. To use the vector,
the header file vector must be included:
#include <vector>
Vectors can be used like arrays, and can be defined with a fixed
number of elements. E.g., to define a vector of 30 ints we do
vector<int>
iVector(30);
Note the specification of the data type that is to be used: the datatype
is given between angular brackets after the vector container name. So, a
vector of 30 strings is defined as
vector<string>
strVector(30);
One of the nice characteristics of defining such a vector is that it's
initialized to the data type's default value. If there is a default
constructor, it is called to construct the elements of the vector. For the
basic data types the initial value is zero. So, for the int vector we know
its values are 0.
Another way to initialize the vector is to use explicit initialization
values:
vector<int>
iVector(1, 2, 3);
This does not work, however, if a vector of one element must be
initialized to a non-default value.
As with string variables,
vector objects may be initialized with other vectors, or
parts of existing vectors may be used to initialize a vector:
vector<int>
a(10);
...
vector<int>
b(&a[3], &a[6]);
[begin, end).
vectors may be assigned to each other,
== and != operators may be used to test the equality of
two vectors.
< operator may be used to test whether each element in the
left-hand operand vector is less than each corresponding element in the
right-hand operand vector. The <=, > and >= operators are also
available.
size() and empty() memberfunctions are available,
swap() memberfunction is available, swapping two
vectors. E.g.,
int main()
{
vector<int>
v1(10),
v2(10);
v1.swap(v2);
}
pos. Below
source represents a value of the type that is stored in the vector, while
pos is an iterator pointing to a position in the vector where
source must be inserted:
insert(pos, source) inserts source at pos,
insert(pos, begin, end) inserts the elements in the iterator range
[begin, end).
insert(pos, n, source) inserts n elements having value
source at position pos.
erase() and clear() both erase all elements, clear() is
not available with strings.
erase(pos) erases all elements starting at position pos,
erase(begin, end) erases elements indicated by the iterator range
[begin, end).
resize(n) and resize(n, source) may be used to resize the vector
to a size of n. If the vector is expanded, the extra elements are
initialized by the default value of the used datatype, or by the explicitly
provided value source.
Also available are:
void pop_back() may be used to remove the last element from the
vector. The element is not returned by this memberfunction.
front(), returning the initial element of the vector,
back(), returning the final element of the vector,
push_back(source) stores source at the end of the vector: a
new element is added at the end.
vector<int> ivect;.
This defines an empty vector, without any element at all. Therefore, a
statement like ivect[0] = 18; would (in this case) be an error, as there
isn't any element as yet. In this case the preferred idiom is
ivect.push_back(18);
list class implements a list datastructure. To use the list, the
header file list must be included:
#include <list>
A list is depicted in figure 5.

In figure 5 it is shown that a list consists of
separate data-items, connected to each other by pointers. The list can be
traversed in two ways: starting at the Front the list may be traversed
from left to right, until the 0-pointer is reached at the end of the rightmost
data-item. The list can also be traversed from right to left: starting at the
Back, the list is traversed from right to left, until eventually the
0-pointer emanating from the leftmost data-item is reached.
Both lists and vectors are often possible datastructures in situations where
an unknown number of data elements must be stored. However, there are some
rules of thumb to follow when a choice between the two datastructures must be
made.
vector is
the preferred datastructure. E.g., in a program that counts the frequencies of
characters in a textfile, a vector<int> frequencies(256) is the
datastructure doing the trick, as the values of the received characters can be
used as indices into the frequencies vector.
vector: if the number of elements is known in advance (and
does not notably change during the lifetime of the program), the vector
is also preferred over the list.
vector, maybe
containing holes, is used. Nonetheless, the list container exists, and
it may become popular now that the list-management is part of the
implementation of the abstract container.

Removing an element from a list also is a simple matter. Starting again
from the situation shown in figure 5, figure 7 shows
what happens if element two is removed from our list. Again: only pointers
need to be juggled. In this case it's even simpler than adding an element:
only two pointers need to be rerouted.

Summarizing the comparison between lists and vectors, it's probably best
to conclude that there is no clear-cut answer to the question what
datastructure to prefer. There are rules of thumb, which may be adhered
to. But if worse comes to worst, a profiler may be required to find out what's
working best.
But, no matter what thoughts remain, the list container is available,
so let's see what we can do with it. As with the vector-class, the
following constructors and memberfunctions are available:
Constructors:
list<string>
strList;
list<string>
hello(5, string("Hello")), // initialize to 5 Hello's
zilch(10); // initialize to 10 empty strings
vector<string> the following construction may be used:
extern vector<string>
svector;
list<string>
slist(&svector[5], &svector[11]);
list<int> ivect; *ivect.begin() = 18; ivect.push_back(18); vector,
are:
back(), returning the last element of the list.
clear(),
front(), returning the first element of the list.
empty(),
erase() and clear() both erase all elements,
erase(pos) erases all elements starting at the position pointed to
by iterator pos,
erase(begin, end) erases elements indicated by the iterator range
[begin, end).
pos:
insert(pos, source) inserts source at the position pointed to
by pos,
insert(pos, begin, end) inserts the elements in the iterator
range [begin, end) at the position pointed to by pos.
insert(pos, n, argument) inserts n elements having value
argument at the position pointed to by pos. The data type
of argument must be equal to the data type of the the elements of the
list.
resize(n) and resize(n, argument) may be used to resize the list
to a size of n. If the list is expanded, the extra elements are
initialized by the default value of the used datatype, or by the explicitly
provided value argument.
size(),
swap(argument), swaps two lists.
void push_front(source) to enter a new element at the head of the
list.
void push_back(source) to enter a new element at the end of the
list.
void pop_front() may be used to remove the first element from the
list. This element is not returned by this memberfunction.
void pop_back() may be used to remove the last element from the
list. This element is not returned by this memberfunction.
remove(source): This memberfunction removes all occurrences of
source from the list: the two strings Hello are removed from the
list object in the following example:
#include <iostream>
#include <string>
#include <list>
int main()
{
list<string>
object;
object.push_back(string("Hello"));
object.push_back(string("World"));
object.push_back(string("Hello"));
object.push_back(string("World"));
object.remove(string("Hello"));
while (object.size())
{
cout << object.front() << endl;
object.pop_front();
}
return (0);
}
sort() will sort the list. Once the list has been sorted, the
following memberfunction (unique()) may be used to remove all multiply
occurring elements from the list, leaving only one element of each. The
following example shows the use of both memberfunctions.
unique() makes sure that each element will occur
only once. Here's an example, leaving each single word only once in the list:
#include <iostream>
#include <string>
#include <list>
int main()
{
list<string>
target;
target.push_back(string("A"));
target.push_back(string("rose"));
target.push_back(string("is"));
target.push_back(string("a"));
target.push_back(string("rose"));
target.push_back(string("is"));
target.push_back(string("a"));
target.push_back(string("rose"));
cout << "Initially we have: " << endl;
list<string>::iterator
from;
for (from = target.begin(); from != target.end(); ++from)
cout << *from << " ";
cout << endl;
target.sort();
cout << "After sort() we have: " << endl;
for (from = target.begin(); from != target.end(); ++from)
cout << *from << " ";
cout << endl;
target.unique();
cout << "After unique() we have: " << endl;
for (from = target.begin(); from != target.end(); ++from)
cout << *from << " ";
cout << endl;
return (0);
}
merge(argument) combines the current list and the argument list.
The merging will add elements of source to target. When
both lists are ordered, the resulting list will be ordered as well. If both
list are not completely ordered, the resulting list will be ordered as much as
possible, given the initial ordering of the elements in each list. In the
following example this is illustrated: the object list is not completely
ordered, but the resulting list (alfa bravo golf oscar mike november quebec
zulu) is ordered 'as much as possible': mike has to follow oscar,
since this ordering is imposed by object, but given that imperfection the
resulting list is ordered alphabetically.
#include <iostream>
#include <string>
#include <list>
int main()
{
list<string>
object,
argument;
object.push_back(string("alfa"));
object.push_back(string("bravo"));
object.push_back(string("golf"));
object.push_back(string("quebec"));
argument.push_back(string("oscar"));
argument.push_back(string("mike"));
argument.push_back(string("november"));
argument.push_back(string("zulu"));
object.merge(argument);
list<string>::iterator
from;
for (from = object.begin(); from != object.end(); ++from)
cout << *from << " ";
cout << endl;
return (0);
}
merge() and sort() both assume the
availability of the < and == operators.
target.splice(iterator position, list source): This memberfunction
transfers the contents of source to the current list. Following
splice(), source is empty. For example:
#include <iostream>
#include <string>
#include <list>
int main()
{
list<string>
object;
object.push_front(string("Hello"));
object.push_back(string("World"));
list<string>
argument(object);
object.splice(++object.begin(), argument);
cout << "Object contains " << object.size() << " elements, " <<
"Argument contains " << argument.size() << " elements," << endl;
while (object.size())
{
cout << object.front() << endl;
object.pop_front();
}
return (0);
}
Alternatively, source may be followed by a iterator of source,
indicating the first element of source that should be spliced, or by two
iterators begin and end defining the iterator-range [begin,
end) on source that should be spliced into target.
Available operators with the list containertype are:
=,
==,
!=,
<: This operator returns true if each element stored in the
left-hand operand list is less than each corresponding element in the
right-hand operand list, based on the <-operator of the element-type of
the lists. Also available are the <=, > and >= operators.
queue class implements a queue datastructure. To use the queue,
the header file queue must be included:
#include <queue>
A queue is depicted in figure 8.

In figure 8 it is shown that a queue has one point (the
back) where items can be added to the queue, and one point (the front)
where items can be removed (read) from the queue.
Bearing this model of the queue in mind, let's see what we can do with it.
A queue can be initialized by an existing other queue, or it can be created
empty:
queue<int>
queue1;
...
queue<int>
queue2(queue1);
Apart from these constructors, and the basic operators for comparison and
assignment (see the introductory paragraph of this chapter),
the following memberfunctions are available:
empty(),
size(),
front(): returns the first element that would be removed by
pop(), Alternatively, the last element of the queue may be reassigned, as
illustrated in the following example, in which Hello World, rather than
Hello is displayed:
#include <iostream>
#include <string>
#include <queue>
int main()
{
queue<string>
q;
q.push("Hello");
q.front() = "Hello World";
cout << q.front() << endl;
return (0);
}
back(): returns the last element that was added to the
queue. Like front(), back() can be used to reassign the last item that
was added to the queue.
push(source): adds item source to the back of the queue.
void pop(): removes (but does not return) the element at the front of
the queue.
priority_queue class implements a priority queue datastructure. To
use the priority queue, the header file queue must be included:
#include <queue>
A priority queue is identical to a queue, but allows the entry of data
elements according to priority rules. An example of a situation where the
priority queue is encountered in real-life is found at the check-in terminals
at airports. At a terminal the passengers normally stand in line to wait for
their turn to check in, but late passengers are usually allowed to jump the
queue: they receive a higher priority than the other passengers.
The priority queue uses the <-operator of the used data type to decide
about the priority of the data elements. The smaller the value, the lower the
priority. So, the priority queue could also be used for sorting values
while they arrive.
A simple example of a priority queue application is the following program: it
reads words from cin and writes a sorted list of words to cout:
#include <iostream>
#include <string>
#include <queue>
int main()
{
priority_queue<string>
q;
string
word;
while (cin >> word)
q.push(word);
while (q.size())
{
cout << q.top() << endl;
q.pop();
}
return (0);
}
Unfortunately, the words are listed in reversed order: because of the
underlying <-operator the words appearing later in the ascii-sequence
appear first in the priority queue. A solution for that problem is to define a
wrapper class around the string datatype, in which the <-operator has
been defined according to our wish, i.e., making sure that the words appearing
early in the ascii-sequence appear first in the queue. Here is the modified
program:
#include <iostream>
#include <string>
#include <queue>
class Text
{
public:
Text(string const &str): s(str)
{}
operator string const &() const
{
return (s);
}
bool operator<(Text const &right) const
{
return (s > right.s);
}
private:
string
s;
};
ostream &operator<<(ostream &ostr, Text const &text)
{
return (ostr << text);
}
int main()
{
priority_queue<Text>
q;
string
word;
while (cin >> word)
q.push(word);
while (q.size())
{
word = q.top();
cout << word << endl;
q.pop();
}
return (0);
}
In the above program the wrapper class defines the operator< just the
other way around than the string class itself, resulting in the preferred
ordering. Other possibilities would be to store the contents of the priority
queue in, e.g., a vector, from which the elements can be read in reversed
order. However, the example shows how the priority queue can be fed objects of
a special class, in which the operator< has been tailored to a particular
use.
A priority queue can be initialized by an existing other priority queue, or it
can be created empty:
priority_queue<int>
priority_queue1;
...
priority_queue<int>
priority_queue2(priority_queue1);
Apart from these constructors, and the basic operators for comparison and
assignment (see the introductory paragraph of this chapter),
the following memberfunctions are available:
empty(),
size(),
top(): returns the first element that would be removed by
pop(). This element is not removed from the priority queue, and could be
given a new value, as in:
priority_queue<string>
pq;
...
pq.top() = "Hello world";
push(argument): adds item argument to its appropriate position,
respecting its priority.
deque class implements a double ended queue (deque) datastructure. To
use the deque class, the header file deque must be included:
#include <deque>
A deque is comparable to a queue, but it allows reading and writing at
both ends of the queue. Actually, the deque data type supports a lot more
functionality than the queue, as will be clear from the following overview
of memberfunctions that are available for the deque:
First, several constructors are available for the deque:
deque() initializes an empty deque.
deque(argument) initializes a deque with another deque argument.
deque(n, argument) initializes a deque with n values
provided by the argument variable. E.g., to initialize a deque with 10
strings containing Hello World we do:
deque<string>
hello(10, "Hello World");
deque(size_type n) initializes a deque with n default values of
the datatype stored in the deque.
deque(iterator first, iterator last) initializes the deque
with the iterator range implied by [first, last). The iterators
first and last may also be pointers to the data-type stored in the
deque.
begin(): this returns the iterator pointing to the front-element
end(): the iterator beyond the back-element.
rbegin(): the iterator pointing to the last (back) element
rend(): and the corresponding one pointing just before the first
(front) element.
front(): returns the element at the front of the deque. This member
may be used for reassigning the front element as well.
back(): and the element at the back of the deque. Again, reassignment
is possible.
size(), returning the number of elements in the deque.
empty(), returns true if the deque contains no elements.
The following operations and operator affect all elements of a deque:
=) may be used to assign one deque
object to another.
swap(argument) is used to swap the contents of the current deque with
deque argument.
push_back(source) adds source at the back of the deque,
push_front(source) adds source at the front of the deque.
pop_back() removes (but does not return) the element at the back of
the deque.
pop_front() removes (but does not return) the element at the front of
the deque.
insert(position, argument): argument is inserted at the
position indicated by the position iterator, which is itself returned by
the function. Argument may be omitted, in which case the default value of
the data-type used with the deque is inserted.
insert(pos, n, argument): At the position indicated by the
pos iterator n new elements are inserted, all having value
argument. There is no returnvalue.
insert(pos, first, last): At the position indicated by the pos
iterator the elements implied by the iterator range [first, last) are
inserted. There is no returnvalue.
resize(new_size, argument): the size of the deque is altered to
new_size. If new_size exceeds size(), then the new elements are
initialized to argument. If argument is omitted, the default value of
the data type of the deque is used. If new_size is less than size(),
then the size of the deque is merely reduced.
resize(), elements may be removed from the deque as
follows:
erase(pos) erases all elements of the deque from the position
indicated by the iterator pos to the end of the deque.
erase(first, last) erases all elements implied by the iterator range
[first, last).
clear() erases all elements from the deque.
map class implements a (sorted) associative array. To use the map,
the header file map must be included:
#include <map>
A map is filled with Key/Value pairs, which may be of any
container-acceptable type.
The key is used for looking up the information belonging to the key. The
associated information is the Value. For example, a phonebook uses the
names of people as the key, and uses the telephone number and maybe other
information (e.g., the zip-code, the address, the profession) as the value.
Basically, the operations on a map are the storage of Key/Value
combinations, and looking for a value, given a key. Each key can be stored
only once in a map. If the same key is entered twice, the last entered
key/value pair is stored, and the pair that was entered before is
lost.
A single value that must be entered into a map must be constructed
first. For this, every map defines a value_type which may be used to
create values of that type. For example, a value for a map<string, int>
can be constructed as follows:
map<string, int>::value_type(string("Hello"), 1)
The value_type is associated with the map<string, int> map.
Its leftmost argument defines the key, its rightmost argument defines its
value.
Instead of using the line map<string, string>::value_type(...) over
and over again, a typedef comes in handy:
typedef map<string, int>::value_type MapStrIntValue
Using this typedef, values for the map<string, int> may be constructed
as
MapStrIntValue(string("Hello"), 1);
Apart from the basic operations (assignment, comparison, etc,), the
map supports several more operations:
map. The types of the Key
and Value must be specified when the map is defined. E.g., to define a
map in which the key is a string and the value an int, use:
map<string, int>
object;
To define a map in which the key is a string and the value is a pair
of strings, use:
map<string, pair<string, string> >
object;
Note the white space between the two closing angular brackets >: this
is obligatory, as the immediate concatenation of the two angular brackets will
be interpreted by the compiler as a rightshift operator (>>), which is not
what you want here.
object(iterator first, iterator last): This constructor defines a
map that is initialized by the values implied by the iterator range
[first, last). The range could be defined by pointers in an array of
Key/Value pairs. For example (see section 7.1 for a discussion of
the pair container):
pair<string, int>
pa[] = {
pair<string,int>("one", 1),
pair<string,int>("two", 2),
pair<string,int>("three", 3),
};
map<string, int>
object(&pa[0], &pa[3]);
Note that &pa[3], as with the iterators, points to the first element
that must not be included in the map. The particular array element
does not have to exist.
Also note that key/value pairs are only entered if the corresponding key
has not yet been entered. If the last element of pa would have been
"one", 3, only two elements would have entered the map: "one", 1
and "two", 2. The value "one", 3 would have been ignored silently.
Finally, it is worth noting that the map receives its own copies of
the data to which the iterators point. The following example illustrates
this:
#include <iostream>
#include <string>
#include <utility>
#include <map>
class MyClass
{
public:
MyClass()
{
cout << "MyClass constructor called\n";
}
MyClass(const MyClass &other)
{
cout << "MyClass copy constructor called\n";
}
~MyClass()
{
cout << "MyClass destructor called\n";
}
};
int main()
{
pair<string, MyClass>
pairs[] =
{
pair<string, MyClass>("one", MyClass()),
};
cout << "pairs constructed\n";
map<string, MyClass>
mapsm(&pairs[0], &pairs[1]);
cout << "mapsm constructed\n";
return (0);
}
First, the constructors of a MyClass object is called to
initialize the first element of the array pairs. This object is copied
into the first element of the array pairs by calling the copy
constructor. Next, the original element is not needed anymore, and gets
destroyed. At that point the array pairs is constructed. Next, the map
constructs a temporary pair object, from which the map element is
constructed. Having constructed the map element, the temporary pair
objects is destroyed. Eventually, when the program terminates, the pair
element stored in the map is destroyed too.
When run, the program produces the following output:
MyClass constructor called
MyClass copy constructor called
MyClass destructor called
pairs constructed
MyClass copy constructor called
MyClass copy constructor called
MyClass destructor called
mapsm constructed
MyClass destructor called
object(argument): This constructor initializes object with an
existing map argument having the same key/value combinations.
begin()
end()
rbegin()
rend()
map are:
empty(),
size(),
swap(),
[]), which may be used to access and
redefine values. Here, the argument of the subscript operator is the keyvalue.
If the provided key is not available in the map, a new data element is
added to the map, using the default value or default constructor to
initialize the value part of the newly added key/value combination. This
default value is then returned.
When initializing a new or reassigning another element of the map, the
right-hand side of the assignment operator must have the type of the value
part of the map. E.g., to add another element "two" to the map that was
defined in the previous example, use the following construction:
mapsm["two"] = MyClass();
insert(argument) is used to insert a new value argument in the
map. The returnvalue is a pair<iterator,bool>. The bool field
indicates whether source was inserted (true is returned) or not (in
which case the key field of source was already available). In both
cases the iterator field points to the data-element in the map: a new
element if true is returned, the existing element if false is
returned. The following little program illustrates this:
#include <string>
#include <map>
#include <iostream>
int main()
{
pair<string, int>
pa[] = {
pair<string,int>("one", 1),
pair<string,int>("two", 2),
pair<string,int>("three", 3),
};
map<string, int>
xmap(&pa[0], &pa[3]);
// {four, 4} and true (1) is returned here
pair<map<string, int>::iterator, bool>
ret = xmap.insert(map<string, int>::value_type("four", 4));
cout << ret.first->first << " " << ret.first->second << " " <<
ret.second << " " << xmap["four"] << endl;
// {four, 4} and false (0) is returned here
ret = xmap.insert(map<string, int>::value_type("four", 0));
cout << ret.first->first << " " << ret.first->second << " " <<
ret.second << " " << xmap["four"] << endl;
return (0);
}
Note the somewhat peculiar constructions like
cout << ret.first->first << " " << ret.first->second << ...
Here ret is the pair variable returned by the insert member
function. Its first field is an iterator into the t(map<string, int>), so
it can be considered a pointer to a map<string, int> value type. These
value types themselves are pairs too, having first and second
fields. Consequently, ret.first->first is the key field of the map
value (a string), and ret.first->second is the value field (an
int).
insert(position, argument). This is another way to
insert a value, this time using a specific position within the
map. Position is an map<keytype, valuetype>::iterator.
Although a specific position is given, the new element is inserted at
its appropriate sorted location within the map, so mapVariable.begin()
could be used for the position.
insert(first, last): this memberfunction may be
used to insert a range of elements implied by the iterator range
[first, last) into the map. Again, elements are only inserted if
their keys are not yet in the map, and the map remains sorted by key
values. Instead of iterators pointers to elements of the same value type
as stored in the map may be used.
erase(position): erases the element at the indicated
position, which is an iterator of the particular map.
erase(key): erases the element having key as its key
value.
erase(first, last): erases the range of elements
implied by the iterator range [first, last).
clear(): erases all elements from the map.
find(key): an iterator is returned pointing to the
element whose key is key. If the element isn't available, the iterator
end() is returned. The following example illustrates the use of the
find() memberfunction:
#include <iostream>
#include <string>
#include <utility>
#include <map>
int main()
{
map<string, int>
mapsi;
mapsi["one"] = 1;
map<string, int>::iterator
it = mapsi.find("one");
cout << "\"one\" " <<
(it == mapsi.end() ? "not " : "") <<
"found\n";
it = mapsi.find("three");
cout << "\"three\" " <<
(it == mapsi.end() ? "not " : "") <<
"found\n";
return (0);
}
map too:
count(key): returns 1 if the provided key is available in
the map, otherwise 0 is returned.
lower_bound(key): returns an iterator pointing to the
first element having a key equal to or exceeding
the key value that is passed to the memberfunction. If no such value exists,
target.end() is returned.
upper_bound(key_type key): same as the previous function.
equal_range(key_type key): a pair<iterator,iterator> is
returned. In the case of a map, the range consists of the data element
having as its key the key value that is passed to the function. If no such
data element could be found, the pair (end(), end()) is returned.
map, the multimap class implements also a (sorted)
associative array. To use the multimap, the header file multimap must
be included:
#include <multimap>
The main difference between the map and the multimap is that the
multimap supports multiple entries of the same key, whereas the map
contains only unique keys. Note that multiple entries of the same key and
the same value are also accepted.
The functions that are available with the multimap and the map are practically
the same, with the exception of the subscript operator ([]), which is not
supported with the multimap. This is understandable: if multiple entries of
the same key are allowed, which of the possible values should be returned for
myMap[myKey]?
Below the available constructors and memberfunctions are mentioned. They are
presented without further comment if their function is identical to that of
the map container.
A single value that is to be entered into a multimap must be constructed. For
this, a multimap defines a value_type, corresponding to a particular
multimap type, which may be used to create values of that type. For example,
with a multimap<string, string> it can be used as follows:
multimap<string, string>::value_type(string("Hello"), 1)
Here are the constructors that are available for the
multimap:
multimap<string, int>
object;
object(first, last): This constructor defines a multimap that is
initialized by the values implied by the iterator range [first, last).
object(argument): This constructor initializes object with an
existing multimap.
begin()
end()
rbegin()
rend()
empty()
size()
swap()
insert(argument) is used to insert a new value argument in the
multimap. The returnvalue is an iterator (and not a
pair<iterator,bool> as with the map container), pointing to the newly
added element.
insert(position, argument).
insert(first, last).
erase(position).
erase(key).
erase(first, last).
clear().
find(key): an iterator is returned pointing to the
(first) element whose key is key. If the element isn't available,
target.end() is returned.
count(key): returns the number of times the provided key is
available in the multimap.
lower_bound(key): returns an iterator pointing to the first
of a series of data element having the same keys of which the value is equal
to or exceeds the key value that is passed to the memberfunction. If no such
value exists, the behavior of the function is undefined.
upper_bound(key): returns an iterator pointing to the last
of a series of data element having the same keys of which the value is equal
to or exceeds the key value that is passed to the memberfunction. If no such
value exists, the behavior of the function is undefined.
equal_range(key): a pair<iterator,iterator> is returned,
defining the range of data elements all having key value key. If no such
data element could be found, the pair (end(), end()) is returned.
set class implements a set of (sorted) values. To use the set,
the header file set must be included:
#include <set>
A set is filled with values, which may be of any container-acceptable
type. Each value can be stored only once in a set.
A single value that is to be entered in a set must be constructed. For this, a
set defines a value_type, corresponding to a particular type of set, which
may be used to create values of that type. For example, with a set<string>
it can be used as follows:
set<string>::value_type(string("Hello"))
Instead of using the line set<string>::value_type(...) over and
over again, a typedef may come in handy here:
typedef set<string>::value_type SetSValue
Using this typedef, values for the set<string, string> may be
constructed as follows:
SetSValue(string("Hello"))
Apart from the basic operations (assignment, comparison, etc,), the
set supports several more operations. They are:
ints can be stored, use:
set<int>
object;
object(iterator first, iterator last): This constructor defines a set
that is initialized by the values implied by the iterator range [first,
last). The range may also be defined by pointers in an array of values of the
same type as the values that must be stored in the set.
For example:
int
ia[] = {1, 2, 3, 4, 5};
set<int>
object(&ia[0], &ia[5]);
Note that &pa[5] points to the first element that must not be
included in the set. Also note that all values values in the set will be
different: it is not possible to store the same value more than once.
object(argument): This constructor initializes object with an
existing set argument, constructing a copy of the set argument.
begin()
end()
rbegin()
rend()
Other member functions are:
empty(),
size(),
swap(argument), swapping the contents of the current set and the set
argument.
insert(argument) is used to insert a new value argument in the
set. Argument is a value of the appropriate value type of the set. The
returnvalue is a pair<iterator, bool>. The bool field indicates whether
source was inserted (true is returned) or not (in which case the
key field of source was already available). In both cases the
iterator field points to the data-element in the set: a new element if
true is returned, the existing element if false is returned. An
example using the insert() memberfunction is given below:
#include <set>
#include <utility>
int main()
{
set<int>
object;
pair<set<int>::iterator, bool>
result = object.insert(set<int>::value_type(4));
cout << "Element " << *result.first << " was " <<
(result.second ? "" : "not ") << "inserted\n";
result = object.insert(set<int>::value_type(4));
cout << "Element " << *result.first << " was " <<
(result.second ? "" : "not ") << "inserted\n";
return (0);
}
insert(position, argument). This is another way to insert a value
argument, this time using a specific position within the set, indicated by
set<type>::iterator position. Although a specific position is given, the
new element is inserted at its appropriate sorted location within the set. An
insertion could therefore be realized using a statement like
object.insert(object.begin(), set<int>::value_type(1));
insert(first, last): this memberfunction may be
used to insert a range of elements implied by the iterator range
[first, last) into the set. Again, elements are only inserted if their
keys are not yet in the set, and the set remains sorted. Instead of iterators
pointers to elements of the same value type as stored in the set may be
used.
erase(position): erases the element at the indicated
set<type>::iterator position.
erase(argument): erases the element having argument as its
value.
erase(first, last): erases the range of elements implied by the
iterator range [first, last).
clear(): erases all elements from the set.
find(argument): an iterator is returned pointing to the element
whose value is argument. If the element isn't available, object.end()
is returned.
count(argument): returns 1 if the provided value is available in
the set, otherwise 0 is returned.
lower_bound(argument): returns an iterator pointing to the
(first) data element having a value which is equal to or exceeds
the value that is passed to the memberfunction. If no such value exists,
the behavior of the function is undefined.
upper_bound(argument): same as the previous function.
equal_range(argument): a pair<set<type>::iterator,
set<type>::iterator> is returned. In the case of a set, the range consists of
a pair of iterators of which the first iterator points to the element of the
set containing the value argument, while the second iterator points beyond
that elementand (or to end() if the first iterator points to the last
element in the set). If the set does not contain a data element having value
argument the pair (end(), end()) is returned.
set, the multiset class also implements a (sorted)
set of values. To use the multiset, the header file multiset must
be included:
#include <multiset>
The main difference between the set and the multiset is that the
multiset supports multiple entries of the same value, whereas the set
contains only unique values.
The member functions that are available for the set are also available for the
multiset. They are presented below without further comment if their functions
and parameters are comparable to those used by the set container's
members.
A single value that is to be entered into a multiset must be constructed. For
this, a multiset defines a value_type, corresponding to a particular
multiset type, which may be used to create values of that type. For example,
with a multiset<string> it can be used as follows:
multiset<string>::value_type(string("Hello"))
Here are the constructors that are available for the
multiset:
multiset<string>
object;
object(first, last): This constructor defines a
multiset that is initialized by the values implied by the iterator range
[first, last).
object(argument): This constructor initializes object with an
existing multiset argument, creating a copy of that multiset.
begin()
end()
rbegin()
rend()
empty(),
size(),
swap(argument), argument is an existing multiset.
insert(argument) is used to insert a new value
multiset<type>::value_type(argument) into the multiset. The returnvalue is
an iterator (and not a pair<iterator, bool> as with the set
container), pointing to the newly added element.
insert(position, argument). Position is an iterator of the
multiset, and argument is a value for the multiset.
insert(first, last), inserting values defined by the iterator range
rangett(first, last).
erase(position),
erase(argument),
erase(first, last),
clear().
find(argument): an iterator is returned pointing to the
(first) element whose value is argument. If the element isn't available,
object.end() is returned.
count(argument): returns the number of times the provided
value argument is available in the multiset.
lower_bound(argument): returns an iterator pointing to the first of a
series of data element having values which are equal to or exceed the value
argument that is passed to the memberfunction. If no such value exists,
the behavior of the function is undefined.
upper_bound(value): returns an iterator pointing to the last of a
series of data element having values which are equal to or exceed the value
argument that is passed to the memberfunction. If no such value exists,
the behavior of the function is undefined.
equal_range(argument): a pair<iterator, iterator> is returned,
defining the range of data elements all having the value argument. If no
such elements could be found, the pair (end(), end()) is returned.
A small example showing the use of various memberfunctions of a multiset is
given below:
#include <string>
#include <set>
#include <iostream>
int main()
{
string
sa[] =
{
"alfa",
"echo",
"hotel",
"mike",
"romeo"
};
multiset<string>
xset(&sa[0], &sa[5]);
xset.insert(multiset<string> ::value_type("echo"));
xset.insert(multiset<string> ::value_type("echo"));
xset.insert(multiset<string> ::value_type("echo"));
multiset<string>::iterator
it = xset.find("echo");
for (; it != xset.end(); ++it)
cout << *it << " ";
cout << endl;
pair
<
multiset<string>::iterator,
multiset<string>::iterator
>
itpair = xset.equal_range("echo");
for (; itpair.first != itpair.second; ++itpair.first)
cout << *itpair.first << " ";
cout << endl <<
xset.count("echo") << " occurrences of 'echo'" << endl;
return (0);
}
stack class implements a stack datastructure. To use the stack,
the header file stack must be included:
#include <stack>
A stack is also called a first-in last-out datastructure, as the first
item to enter the stack is the last item that will be removed from it.
A stack is an extremely useful datastructure in situations where data
must be temporarily be available. For example, programs maintain a stack to
store local variables of functions: these variables live only as long as the
functions live, contrary to global (or static local) variables, which live for
as long as the program itself lives. Another example is found in calculators
using the Reverse Polish Notation (RPN), in which the operands of
expressions are entered in the stack, and the operators pop their operands and
push the results of their work.
As an example of the use of a stack, consider figure 9, in which
the contents of the stack is shown while the expression (3 + 4) * 2 is
evaluated. In the RPN this expression becomes 3 4 + 2 *, and figure
9 shows the stack contents after each token (i.e., the
operands and the operators) is read from the input. Notice that indeed each
operand is pushed on the stack, while each operator changes the contents of
the stack.

3 4 + 2 *
The expression is evaluated in five steps. The caret between the tokens in
the expressions shown on the first line of figure 9 shows what
token has just been read. The next line shows the actual stack-contents, and
the final line shows the steps for referential purposes. Note that at step 2,
two numbers have been pushed on the stack. The first number (3) is now at
the bottom of the stack. Next, in step 3, the + operator is read. The
operator pops two operands (so that the stack is empty at that moment),
calculates their sum, and pushes the resulting value (7) on the
stack. Then, in step 4, the number 2 is read, which is dutifully pushed on
the stack again. Finally, in step 5 the final operator * is read, which
pops the values 2 and 7 from the stack, computes their product, and
pushes the result back on the stack. This result (14) could then be popped
to be displayed on some medium.
From figure 9 we see that a stack has one point (the top)
where items can be added to and removed from the stack. Furthermore, values
can be pushed and popped from a stack.
Bearing this model of the stack in mind, let's see what we can formally
do with it, using the stack container.
A stack can be initialized by an existing other stack, or it can be created
empty:
stack<int>
stack1;
...
stack<int>
stack2(stack1);
Apart from these constructors, and the basic operators for comparison and
assignment (see the introductory paragraph of this chapter),
the following memberfunctions are available:
empty(),
size(),
top(): returns the first element that would be removed by
pop(). Using top() the value at the top of the stack may be inspected
or reassigned.
push(argument): pushes item argument on the stack.
void pop(): removes (but does not return) the element at the top of
the stack.
(multi) map and (multi) set containertypes store sorted keys. This
is in general not the fastest way to store keys with respect to storage and
retrieval. The main benefit of sorted keys is that a listing of sorted keys
appeals more to humans than an unsorted list. However, a by far faster method
of storing keys is to use hashing.
Hashing uses a function (called the hash-function) to compute a (unsigned)
number from the key, which number is thereupon used as an index in the table
in which the keys are stored. Retrieval of a key is as simple as computing the
hashvalue of the provided key, and looking at the table in the computed
indexlocation: if the key is present, it is stored in the table, and its value
can be returned. If it's not present, the key is not stored.
Boundary conditions arise when a computed index position is already occupied
by another element. For these situations the abstract containers have
solutions available, but that topic is beyond the subject of this chapter.
The egcs compiler supports the hash_(multi)map and
hash_(multi)set containers. Below the hash_map container is
illustrated. The other containers using hashing (hash_multimap, hash_set
and hash_multiset) operate correspondingly.
Concentrating on the hash_map, its constructor needs a key-type, a
value-type, an object creating a hashvalue for the key, and an object
comparing two keys for equality.
The hash_map class implements an associative array in which the key is
stored according to some hashing scheme. To use the hash_map, the header
file hash_map must be included:
#include <hash_map>
Hash functions are available for char const * keys, and for all the
scalar numerical types char, short, int etc.. If another datatype must be
used, a hash function and an equality test must be implemented, possibly using
function objects (see section 6.8). For both situations examples
are given below.
The class implementing the hash-function could be called hash. Its
function-call operator returns the hashvalue of the key which is passed as its
argument.
A generic algorithm (see section 10) exists for the test of equality
(i.e., equal_to()), which can be used if the key's data type supports the
equality operator. Alternatively, a function object could also be constructed
here, supporting the equality test of two keys. Again, both situations are
illustrated below.
In the first example a hash_map is defined for a string, int
combination using existing template functions.
The test for equality is implemented using an instantiation of the
equal_to generic algorithm. The hash function uses a template
specialization for the hash template class. The how and why of template
specializations are covered in chapter 16.
The hash<string> explicit specialization in fact uses the predefined
hash<char const *> template, but the roundabout way is chosen here to
illustrate how a template explicit specialization can be constructed. Here it
is:
template <>
class hash<string>
{
public:
size_t operator()(string const &str) const
{
hash<char const *>
h;
return (h(str.c_str()));
}
};
The following program defines a map containing the names of the
months of the year and the number of days these months (usually) have. Then,
using the subscript operator the days in several months are displayed. The
equality operator used the generic algorithm equal_to<string>, which is
the default fourth argument of the hash_map constructor:
#include <iostream>
#include <string>
#include <hash_map>
template <> class hash<string>; // insert the above mentioned template
// here
int main()
{
hash_map<string, int, hash<string> >
months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "september -> " << months["september"] << endl <<
"april -> " << months["april"] << endl <<
"june -> " << months["june"] << endl <<
"november -> " << months["november"] << endl;
return (0);
}
Note that the definition hash_map<string, int, hash<string> > months;
may be written simpler if the key is a char const *:
hash_map<char const *, int> months;
The next example shows an alternative implementation, using function
objects. The class Equal defines the equality test of two keys in its
function call operator operator(), and a Equal object is now
explicitly mentioned when the hash_map is constructed. Similarly, the
hashString class defines the hash function of the key. A hashString
object is also passed explicitly to the constructor of the hash_map:
#include <iostream>
#include <string>
#include <hash_map>
class Equal
{
public:
size_t operator()(string const &s1, string const &s2) const
{
return (s1 == s2);
}
};
class hashString
{
public:
size_t operator()(string const &str) const
{
hash<char const *>
h;
return (h(str.c_str()));
}
};
int main()
{
hash_map
<
string,
int,
hashString,
Equal
>
months;
months["january"] = 31;
months["february"] = 28;
months["march"] = 31;
months["april"] = 30;
months["may"] = 31;
months["june"] = 30;
months["july"] = 31;
months["august"] = 31;
months["september"] = 30;
months["october"] = 31;
months["november"] = 30;
months["december"] = 31;
cout << "february -> " << months["february"] << endl <<
"april -> " << months["april"] << endl <<
"june -> " << months["june"] << endl <<
"november -> " << months["november"] << endl <<
"december -> " << months["december"] << endl;
return (0);
}
Like the map, a single value that will be entered into a hash_map must
be constructed. For this, a hash_map defines a value_type,
corresponding to a particular hash_map-type, which may be used to create
values of that type. For example, with a hash_map<string, int> it can be
used as follows:
hash_map<string, int>::value_type(string("Hello"), 1)
All the memberfunctions and constructors that are available for the
map datatype can also be used for the hash_map. The constructor
object(n) defines a hash_map consisting of an initial number of n
slots to put key/value combinations in. This number is automatically extended
when needed.
The hash_multimap, hash_set and hash_multiset containers are used
analogously. For these containers the equal and hash classes must also
be defined. The hash_multimap also requires the hash_map header file,
the hash_set and hash_multiset containers can be used after including
the hash_set header file. Be careful not to use the subscript operator
with the hash_multimap and hash_multiset, as this operator is not
defined for the multi_... containers.
complex container is a specialized container in that it defines
operations that can be performed on complex numbers, given possible numerical
real and imaginary data types.
In order to use the complex container, the headerfile
#include <complex>
must be included.
The complex container can be used to define complex numbers, consisting of
two parts, representing the real and complex parts of a complex number.
While initializing (or assigning) a complex variable, the imaginary part may
be left out of the initialization or assignment, in which case this part is
0 (zero). By default, both parts are zero.
When complex numbers are defined, the typedefinition requires the
specification of the datatype of the real and imaginary parts. E.g.,
complex<double>
complex<int>
complex<float>
Note that the real and imaginary parts of complex numbers have the same
datatypes.
Below it is silently assumed that the used complex type is
complex<double>. Given this assumption, complex numbers may be initialized
as follows:
target: A default initialization: real and imaginary parts are 0.
target(1): The real part is 1, imaginary part is 0
target(0, 3.5): The real part is 0, imaginary part is 3.5
target(source): target is initialized with the values of
source.
#include <iostream>
#include <complex>
#include <stack>
int main()
{
stack<complex<double> >
cstack;
cstack.push(complex<double>(3.14, 2.71));
cstack.push(complex<double>(-3.14, -2.71));
while (cstack.size())
{
cout << cstack.top().real() << ", " <<
cstack.top().imag() << "i" << endl;
cstack.pop();
}
return (0);
}
Note that a blank is required between the two consecutive >-barckets
used in the definition of cstack. If the blank is omitted, the resulting
>> is read as the right-shift operator, which of course makes no sense
here.
The following memberfunctions and operators are defined for complex numbers:
real(): this memberfunction returns the real part of a complex
number.
imag(): this memberfunction returns the imaginary part of a
complex number.
complex containers:
+, -, *, /, +=, -=, *=, /=.
abs(), arg(), conj(), cos(), cosh(), exp(), log(),
norm(), polar(), pow(), sin(), sinh()) and sqrt(). These functions are
normal functions, not memberfunctions. They accept complex numbers as their
arguments. For example,
abs(complex<double>(3, -5));
pow(target, complex<int>(2, 3));
Complex numbers may be extracted from istream objects and
inserted into ostream objects. The insertion results in an ordered pair
(x, y), in which x represents the real part and y the imaginary
part of the complex number. The same form may also be used when extracting a
complex number from an istream object. However, simpler forms are also
allowed. E.g., 1.2345: only the real part, the imaginary part will be set
to 0; (1.2345): the same value.
Finally, ordinary numbers may be used in expressions involving complex
numbers. E.g.,
// assume target is complex<double>:
target *= 3;
Note, however, that the reverse does not hold true: a complex number
cannot be assigned to a non-complex type variable. In these situations the
real(), imag() or other functions must be used. E.g.:
// assume x is double:
x = target; // error: x is not complex<double>
x = target.real(); // ok.