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. Send your email to Frank Brokken.Please state the document version you're referring to, as found in the title (in this document: 5.2.0a) and please state the paragraph you're referring to.
All mail received is seriously considered, and new (sub)releases of the Annotations will normally reflect your suggestions for improvements. Except for the incidental case I will not otherwise acknowledge the receipt of suggestions for improvements. Please don't misinterpret this for lack of appreciation.
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.
Abstract containers rely heavily on templates, which are covered near
the end of the C++ Annotations, in chapter 18. 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
12.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 abstract containers. Actually, understanding this part of templates is the only real requirement for using the abstract containers. Now that we've introduced this notation, we can postpone the more thorough discussion of templates to chapter 18, 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
, also called a
FIFO
(
first in, first out) structure, 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 (
FILO or
LIFO) structure.
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,
implementing operations that are defined on
complex numbers.
All abstract containers described in this chapter and the string
datatype
discussed in chapter 4 are part of the Standard Template
Library. There also exists an abstract container for the implementation of a
hashtable, but that container is not (yet) accepted by the
ANSI/ISO
standard. Nevertheless, the final section of this chapter will
cover the hashtable to some extent. It may be expected that containers like
hash_map
and other, now still considered an extension, will become
part of the
ANSO/ISO standard at the next release: apparently by the time
the standard was frozen these containers were not yet fully available. Now
that they are available they cannot be official part of the C++ library
, but they are in fact available, albeit as extensions.
All containers support the following operators:
==
and
!=
The
equality operator applied to two containers returns
true
if the two
containers have the same number of elements, which are pairwise equal
according to the equality operator of the contained data type. The
inequality operator does the opposite.
<
,
<=
,
>
and
>=
. The <
operator returns true
if each element in the
left-hand container is less than each corresponding element in the
right-hand container. If the right-hand container has more elements than
the left-hand container, they are ignored. Other ordering operators perform
analogously.
class
-type) can be stored in a container, the
user-defined type should at least support
==
)
<
)
string::begin()
and
string::end()
members). In the remainder of
this chapter the use of iterators is not really covered. Refer to chapter
17 for a discussion of iterators.
The url http://www.sgi.com/Technology/STL is worth visiting by those readers who are looking for 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, in normal circumstances the
container should contain no pointer data. Also, a container should not be
required
to contain const
data, as for const
data the, e.g., operator=()
doesn't work.
Below, at the descriptions of the containers, the following notational convention is used:
pair
may represent pair<string,
int>
.
Type
represents the
generic type. Type
could
be int
, string
, etc.
object
and container
represent objects of the
container type under discussion.
value
represents a value of the type that is
stored in the container.
n
represent unsigned
values.
pos
, from
, beyond
map
container, contain combinations of
values, usually called `keys' and `values'. For such containers the following
natational convention is used in addition:
key
indicates a value of the used key-tpye
keyvalue
indicates a value of the `value_type
'
used with the particular container.
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 pair
container, source files should
#include <utility>The data types of a
pair
are defined when the pair
variable is
defined, using the standard template (see chapter Templates
) angular
bracket 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
object must be completely reassigned, an anonymous
pair object can be used 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
generic form is
type(initializer list)Note that when a
pair
object is used the type specification is not
completed by just mentioning the containername pair
. It also requires the
specification of the data types which are stored within the pair. For this the
(template)
angular bracket notation is used again. E.g., the reassignment
of the cessna
pair variable could have been accomplished as follows:
cessna = pair<string, string>("C152", "PH-ANW");In cases like these, 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
typing effort may be reduced and legibility might be
improved by first defining a name for the clause, and then using the defined
name later. 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
offers no further
functionality. 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
,
source files should
#include <vector>The following constructors, operators, and member functions are available:
vector
may be constructed empty:
vector<string> object;Note the specification of the data type to be stored in the
vector
:
the data type is given between angular brackets, just after the `vector
'
container name. This is common practice with containers.
int
vector we know its initial values are zero. For example:
vector<string> object(5, string("Hello")), // initialize to 5 Hello's, container(10); // and to 10 empty strings
vector<string>
the following construction may be used:
extern vector<string> container; vector<string> object(&container[5], &container[11]);Note here that the last element pointed to by the second iterator (
&container[11]
) is not stored in object
. This is a simple
example of the use of
iterators, in which the
range of values that is
used starts at the first value, and includes all elements up to, but not
including the last value mentioned. The standard notation for this is
[begin, end)
.
extern vector<string> container; vector<string> object(container);
vector
supports the
index operator, which may be used to retrieve or reassign
individual elements of the vector. Note that the elements which are indexed
must exist. For eaample, having defined an empty vector a statement like
ivect[0] = 18
produces an error, as the vector is empty. So, the vector
is not automatically
expanded, and it does
respect its
array bounds. In this case the vector should be reiszed first,
or ivect.push_back(18)
should be used (see below).
vector
class has the following
member functions:
Type &vector::back()
:
this member returns a reference to the last element in the vector. It is the responsibility of the programmer not to use the member if the vector is empty.
vector::iterator vector::begin()
:
this member returns an iterator pointing to the first element in the vector.
vector::clear()
:
this member erases all elements in the vector.
bool vector::empty()
this member returns true
if the vector contains no
elements.
vector::iterator vector::end()
:
this member returns an iterator pointing beyond the last element in the vector.
vector::iterator vector::erase()
:
this member can be used to erase a specific range of elements in the vector:
erase(pos)
erases the element pointed to by pos
. The
iterator ++pos
is returned.
erase(first, beyond)
erases elements indicated by the iterator
range [first, beyond)
. Beyond
is returned.
Type &vector::front()
:
this member returns a reference to the first element in the vector. It is the responsibility of the programmer not to use the member if the vector is empty.
... vector::insert()
:
elements may be inserted starting at a certain position. The
return value depends on the version of insert()
that is called:
vector::iterator insert(pos)
inserts a default value of type
Type
at pos
, pos
is returned.
vector::iterator insert(pos, value)
inserts value
at
pos
, pos
is returned.
void insert(pos, first, beyond)
inserts the elements in the
iterator range
[first, beyond)
.
void insert(pos, n, value)
inserts n
elements having value
value
at position pos
.
void vector::pop_back()
:
this member removes the last element from the vector. With an empty vector nothing happens.
void vector::push_back(value)
:
this member adds value
to the end of the vector.
void vector::resize()
:
this member can be used to alter the number of elements that are currently stored in the vector:
resize(n, value)
may be used to resize the vector to a size of
n
. Value
is optional. If the vector is expanded and tvalue
is
not provided, the extra elements are initialized to the
default value of
the used data type, otherwise the explicitly provided value value
is used
to initialize extra elements.
vector::reverse_iterator vector::rbegin()
:
this member returns an iterator pointing to the last element in the vector.
vector::reverse_iterator vector::rend()
:
this member returns an iterator pointing before the first element in the vector.
unsigned vector::size()
this member returns the number of elements in the vector.
void vector::swap()
this member can be used to swap two vectors. E.g.,
#include <iostream> #include <vector> int main() { vector<int> v1(7), v2(10); v1.swap(v2); cout << v1.size() << " " << v2.size() << endl; } /* Produced output: 10 7 */
list
container implements a
list data structure. To use the
list
, source files should
#include <list>The organization of a
list
is shown in figure 7.
In figure 7 it is shown that a list consists of separate
list-elements, connected to each other by pointers. The list can be
traversed in two ways: starting at Front the list
may be traversed from left to right, until the 0-pointer is reached at the end
of the rightmost list-element. The list can also be traversed from right to
left: starting at Back, the list is traversed from right to left,
until eventually the 0-pointer emanating from the leftmost list-element is
reached.
Both lists and vectors are often appropriate data structures 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 data structures must be made.
vector
is
the preferred data structure. 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.
Removing an element from a list also is a simple matter. Starting again
from the situation shown in figure 7, figure 9 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 data
structure 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 the thoughts on the subject are, the list
container is available, so let's see what we can do with it.
The following constructors, operators, and member functions
are available:
list
may be constructed empty:
list<string> object;As with the
vector
, it is an error to refer to an element of an
empty list.
list<string> object(5, string("Hello")), // initialize to 5 Hello's container(10); // and to 10 empty strings
vector<string>
the following construction may be used:
extern vector<string> container; list<string> object(&container[5], &container[11]);
extern list<string> container; list<string> object(container);
list
, apart from
the standard operators for containers.
Type &list::back()
:this member returns a reference to the last element in the list. It is the responsibility of the programmer not to use the member if the list is empty.
list::iterator list::begin()
:this member returns an iterator pointing to the first element in the list.
list::clear()
:this member erases all elements in the list.
bool list::empty()
:this member returns true
if the list contains no elements.
list::iterator list::end()
:this member returns an iterator pointing beyond the last element in the list.
list::iterator list::erase()
:this member can be used to erase a specific range of elements in the list:
erase(pos)
erases the element pointed to by pos
. The
iterator ++pos
is returned.
erase(first, beyond)
erases elements indicated by the iterator
range [first, beyond)
. Beyond
is returned.
Type &list::front()
:this member returns a reference to the first element in the list. It is the responsibility of the programmer not to use the member if the list is empty.
... list::insert()
:this member can be used to
insert elements into the list. The return value depends on the version of
insert()
that is called:
list::iterator insert(pos)
inserts a default value of type
Type
at pos
, pos
is returned.
list::iterator insert(pos, value)
inserts value
at
pos
, pos
is returned.
void insert(pos, first, beyond)
inserts the elements in the
iterator range
[first, beyond)
.
void insert(pos, n, value)
inserts n
elements having value
value
at position pos
.
void list<Type>::merge(list<Type> other)
:this member function assumes that the current and other lists are sorted (see below, the membersort()
), and will, based on that assumption, insert the elements ofother
into the current list in such a way that the modified list remains sorted. If both list are not sorted, the resulting list will be ordered `as much as possible', given the initial ordering of the elements in the two lists.list<Type>::merge()
usesType::operator<()
to sort the data in the list, which operator must therefore be available. The next example illustrates the use of themerge()
member: the list `object
' is not sorted, so the resulting list is ordered 'as much as possible'.#include <iostream> #include <string> #include <list> void showlist(list<string> &target) { for ( list<string>::iterator from = target.begin(); from != target.end(); ++from ) cout << *from << " "; cout << endl; } int main() { list<string> first, second; first.push_back(string("alpha")); first.push_back(string("bravo")); first.push_back(string("golf")); first.push_back(string("quebec")); second.push_back(string("oscar")); second.push_back(string("mike")); second.push_back(string("november")); second.push_back(string("zulu")); first.merge(second); showlist(first); }A subtlety is thatmerge()
doesn't alter the list if the list itself is used as argument:object.merge(object)
won't change the list `object
'.
void list::pop_back()
:this member removes the last element from the list. With an empty list nothing happens.
void list::pop_front()
:this member removes the first element from the list. With an empty list nothing happens.
void list::push_back(value)
:this member
adds value
to the end of the list.
void list::push_front(value)
:this member
adds value
before the first element of the list.
void list::resize()
:this member can be used to alter the number of elements that are currently stored in the list:
list::reverse_iterator list::rbegin()
:this member returns an iterator pointing to the last element in the list.
void list::remove(value)
:this member removes all occurrences ofvalue
from the list. In the following example, the two strings `Hello
' are removed from the listobject
:#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(); } } /* Generated output: World World */
list::reverse_iterator list::rend()
:this member returns an iterator pointing before the first element in the list.
unsigned list::size()
:this member returns the number of elements in the list.
void list::reverse()
:this member reverses the order of the elements in the list. The elementback()
will becomefront()
and vice versa.
void list::sort()
:this member will sort the list. Once the list has been sorted, An example of its use is given at the description of theunique()
member function below.list<Type>::sort()
usesType::operator<()
to sort the data in the list, which operator must therefore be available.
void list::splice(pos, object)
:this member function transfers the contents ofobject
to the current list. Followingsplice()
,object
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(); } }Alternatively,value
may be followed by a iterator ofvalue
, indicating the first element ofvalue
that should be spliced, or by two iteratorsbegin
andend
defining the iterator-range[begin, end)
onvalue
that should be spliced intotarget
.
void list::swap()
:this member can be used to swap two lists.
void list::unique()
:operating on a sorted list, this member function will remove all consecutively identical elements from the list.list<Type>::unique()
usesType::operator==()
to identify identical data elements, which operator must therefore be available. Here's an example that removes all doubly occurring words from the list:#include <iostream> #include <string> #include <list> // see the merge() example void showlist(list<string> &target); int main() { string array[] = { "charley", "alpha", "bravo", "alpha" }; list<string> target ( array, array + sizeof(array) / sizeof(string) ); cout << "Initially we have: " << endl; // shows: charley alpha bravo alpha showlist(target); target.sort(); cout << "After sort() we have: " << endl; // shows: alpha alpha bravo charley showlist(target); target.unique(); cout << "After unique() we have: " << endl; // shows: alpha bravo charley showlist(target); }
queue
class implements a
queue data structure. To use the
queue
, source files should
#include <queue>A queue is depicted in figure 10.
In figure 10 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. A queue
is therefore
also called a
FIFO data structure, for
first in, first out. It is
most often used in situations where events should be handled in the same order
as they are generated.
The following constructors, operators, and member functions are available
for the queue
container:
Type &queue::back()
:this member returns a reference to the last element in the queue. It is the responsibility of the programmer not to use the member if the queue is empty.
bool queue::empty()
:this member returns
true
if the queue contains no elements.
Type &queue::front()
:this member returns a reference to the first element in the queue. It is the responsibility of the programmer not to use the member if the queue is empty.
void queue::push(value)
:this member
adds value
to the back of the queue.
void queue::pop()
:this member removes the element at the front of the queue. Note that the element is not returned by this member.
unsigned queue::size()
:this member returns the number of elements in the queue.
priority_queue
class implements a
priority queue data structure.
To use the priority queue, source files should
#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 other passengers.
The priority queue uses operator<()
of the data type stored in the
priority ueue to decide about the priority of the data elements. The
smaller the value, the lower the priority. So, the priority queue
could be used to sort values while they arrive. A simple example of such
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(); } }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 to 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 will 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; }; 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(); } }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.
The following constructors, operators, and member functions are available
for the priority_queue
container:
priority_queue
may be constructed empty:
priority_queue<string> object;As with the
vector
, it is an error to refer to an element of an
empty priority queue.
extern priority_queue<string> container; priority_queue<string> object(container);
priority_queue
only supports the basic operators of
containers.
bool priority_queue::empty()
:this
member returns true
if the priority queue contains no elements.
void priority_queue::push(value)
:this
member inserts value
at the appropriate position in the priority queue.
void priority_queue::pop()
:this member removes the element at the top of the priority queue. Note that the element is not returned by this member.
unsigned priority_queue::size()
:this member returns the number of elements in the priority queue.
Type &priority_queue::top()
:this member returns a reference to the first element of the priority queue. It is the responsibility of the programmer not to use the member if the priority queue is empty.
deque
(pronounce: `deck') class implements a
doubly ended queue data structure (deque). To use the deque
class,
source files should
#include <deque>A deque is comparable to a queue, but it allows reading and writing at both ends. Actually, the
deque
data type supports a lot more
functionality than the queue
, as will be clear from the following overview
of member functions that are available for the deque
. A deque
is a
combination of a vector
and two queues, operating at both ends of the
vector. In situations where random insertions and the addition and/or removal
of elements at one or both sides of the vector occurs frequently, using
a deque
should be considered.
The following constructors, operators, and member functions are available for deques:
deque
may be constructed empty:
deque<string> object;As with the
vector
, it is an error to refer to an element of an
empty deque.
deque<string> object(5, string("Hello")), // initialize to 5 Hello's container(10); // and to 10 empty strings
vector<string>
the following construction may be used:
extern vector<string> container; deque<string> object(&container[5], &container[11]);
extern deque<string> container; deque<string> object(container);
Type &deque::back()
:this member returns a reference to the last element in the deque. It is the responsibility of the programmer not to use the member if the deque is empty.
deque::iterator deque::begin()
:this member returns an iterator pointing to the first element in the deque.
deque::clear()
:this member erases all elements in the deque.
bool deque::empty()
:this member returns
true
if the deque contains no elements.
deque::iterator deque::end()
:this member returns an iterator pointing beyond the last element in the deque.
deque::iterator deque::erase()
:the member can be used to erase a specific range of elements in the deque:
erase(pos)
erases the element pointed to by pos
. The
iterator ++pos
is returned.
erase(first, beyond)
erases elements indicated by the iterator
range [first, beyond)
. Beyond
is returned.
Type &deque::front()
:this member returns a reference to the first element in the deque. It is the responsibility of the programmer not to use the member if the deque is empty.
... deque::insert()
:this member can be used to
insert elements starting at a certain position. The return value depends on
the version of insert()
that is called:
deque::iterator insert(pos)
inserts a default value of type
Type
at pos
, pos
is returned.
deque::iterator insert(pos, value)
inserts value
at
pos
, pos
is returned.
void insert(pos, first, beyond)
inserts the elements in the
iterator range
[first, beyond)
.
void insert(pos, n, value)
inserts n
elements having value
value
at position pos
.
void deque::pop_back()
:this member removes the last element from the deque. With an empty deque nothing happens.
void deque::pop_front()
:this member removes the first element from the deque. With an empty deque nothing happens.
void deque::push_back(value)
:this member
adds value
to the end of the deque.
void deque::push_front(value)
:this member
adds value
before the first element of the deque.
void deque::resize()
:this member can be used to alter the number of elements that are currently stored in the deque:
deque::reverse_iterator deque::rbegin()
:this member returns an iterator pointing to the last element in the deque.
deque::reverse_iterator deque::rend()
:this member returns an iterator pointing before the first element in the deque.
unsigned deque::size()
:this member returns the number of elements in the deque.
void deque::swap()
:this member can be used to swap two deques.
map
class implements a (sorted)
associative array. To use the
map
, source files should
#include <map>A
map
is filled with
key/value pairs, which may be of any
container-acceptable type. Since types are associated with both the key and
the value, we must specify
two types in the
angular bracket notation
that is used for maps. The first type represents the type of the key, the
second type represents the type of the value. For example, a map
in which
the key is a string
and the value is a double
can be defined as
follows:
map<string, double> object;The key is used for locating the information belonging to the key. The associated information is called the value. For example, a phone book 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.
The two fundamental operations on maps are the
storage of Key/Value
combinations, and the
retrieval of values, given their keys. Each key can
be stored only once in a map
. If the same key is entered again, the new
value replaces the formerly stored value, which is lost.
A specific key/value combination can be implicitly or explicitly inserted into
a map
. If
explicit insertion is required, the key/value combination
must be constructed first. For this, every map
defines a
value_type
which may be used to
create values that can be stored in the map
. For
example, a value for a map<string, int>
can be constructed as follows:
map<string, int>::value_type siValue("Hello", 1);The
value_type
is associated with the map<string, int>
: the
type of the key is string
, the type of the value is int
. Anonymous
value_type
objects are also often used. E.g.,
map<string, int>::value_type("Hello", 1);Instead of using the line
map<string, int>::value_type(...)
over
and over again, a
typedef
is often used to
reduce typing and to improve
legibility:
typedef map<string, int>::value_type StringIntValueUsing this typedef, values for the
map<string, int>
may be constructed
as follows:
StringIntValue("Hello", 1);
The following constructors, operators, and member functions are available
for the map
container:
map
may be constructed empty:
map<string, int> object;Note that the values stored in maps may be containers themselves. For example, the following defines a
map
in which the value is a pair
: a
container
nested in another
container:
map<string, pair<string, string> > object;Note the blank space between the two closing angular brackets
>
: this
is obligatory, as the immediate
concatenation of the two
angular closing brackets would be interpreted by the compiler as a
right shift operator (
operator>>()
), which is not what we want
here.
value_type
values for the map to be constructed, or they may
point to plain
pair
objects (see section 12.1), whose
first
elements reperesent the keys, and whose second
elements represent the
values to be used. For example:
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]);In this example,
map<string, int>::value_type
could have been used
instead of pair<string, int>
as well.
Note again that &pa[3]
, being interpreted as an iterator, 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, maybe
contrary to intuition, the map
constructor
will only enter new keys. 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
silently ignored.
Finally, it is worth noting that the map
receives its own copies of
the data to which the iterators point. The is illustrated by the following
example:
#include <iostream> #include <map> using namespace std; class MyClass { public: MyClass() { cout << "MyClass constructor\n"; } MyClass(const MyClass &other) { cout << "MyClass copy constructor\n"; } ~MyClass() { cout << "MyClass destructor\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"; } /* Generated output: MyClass constructor MyClass copy constructor MyClass destructor pairs constructed MyClass copy constructor MyClass copy constructor MyClass destructor mapsm constructed MyClass destructor */When tracing the output of this program, we see that, first, the constructor of a
MyClass
object is called to initialize the anonymous
element of the array pairs
. This object is then copied into the first
element of the array pairs
by the copy constructor. Next, the original
element is not needed anymore, and gets destroyed. At that point the array
pairs
has been constructed. Thereupon, the map
constructs a temporary
pair
object, which is used to construct the map element. 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.
extern map<string, int> container; map<string, int> object(container);
map
supports the
index operator, which may be used to retrieve or reassign
individual elements of the map. Here, the argument of the index operator is a
key. If the provided key is not available in the map
, a new data element
is automatically added to the map
, using the default value or default
constructor to initialize the value part of the new element. This default
value is returned if the index operator is used as an
rvalue.
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 or change the value of element "two"
in a
map, the following statement can be used:
mapsm["two"] = MyClass();
map
class has the following
member
functions:
map::iterator map::begin()
:this member returns an iterator pointing to the first element of the map.
map::clear()
:this member erases all elements from the map.
unsigned map::count(key)
:this member returns 1 if
the provided key is available in the map
, otherwise 0 is returned.
bool map::empty()
:this member returns true
if
the map contains no elements.
map::iterator map::end()
:this member returns an iterator pointing beyond the last element of the map.
pair<map::iterator, map::iterator> map::equal_range(key)
:this member returns a pair of iterators, being respectively the return values of the member functionslower_bound()
andupper_bound()
, introduced below. An example illustrating the use of these member functions is given at the discussion of the member functionupper_bound()
.
... map::erase()
:this member can be used to erase a specific element or range of elements from the map:
bool erase(key)
erases the element having the
given key
from the map
. True
is returned if the value was removed,
false
if the map did not contain an element using the given key
.
void erase(pos)
erases the element pointed to by pos
.
void erase(first, beyond)
erases all elements indicated by
the iterator range [first, beyond)
.
map::iterator map::find(key)
:this member returns an iterator to the element having the given key. If the element isn't available,end()
is returned. The following example illustrates the use of thefind()
member function:
#include <iostream> #include <map> using namespace std; int main() { map<string, int> object; object["one"] = 1; map<string, int>::iterator it = object.find("one"); cout << "`one' " << (it == object.end() ? "not " : "") << "found\n"; it = object.find("three"); cout << "`three' " << (it == object.end() ? "not " : "") << "found\n"; } /* Generated output: `one' found `three' not found */
... map::insert()
:this member can be used to
insert elements starting at a certain position. Elements having the same keys
as elements to be inserted are left untouched. The return value depends on the
version of insert()
that is called:
pair<map::iterator, bool> insert(keyvalue)
is used to insert
a new map::value_type
into the map. The return value is a
pair<map::iterator, bool>
. If the returned
bool
field is true
,
keyvalue
was inserted into the map. The value false
indicates that the
key that was specified in keyvalue
was already available in the map, and
so keyvalue
was not inserted into the map. In both cases the
map::iterator
field points to the data element in the map
having the
key
that was specified in keyvalue
. The use of this variant of
insert()
is illustrated in the following example:
#include <iostream> #include <string> #include <map> using namespace std; int main() { pair<string, int> pa[] = { pair<string,int>("one", 10), pair<string,int>("two", 20), pair<string,int>("three", 30), }; map<string, int> object(&pa[0], &pa[3]); // {four, 40} and `true' (1) is returned pair<map<string, int>::iterator, bool> ret = object.insert ( map<string, int>::value_type ("four", 40) ); cout << ret.first->first << " " << ret.first->second << " " << ret.second << " " << object["four"] << endl; // {four, 40} and `false' (0) is returned ret = object.insert ( map<string, int>::value_type ("four", 0) ); cout << ret.first->first << " " << ret.first->second << " " << ret.second << " " << object["four"] << endl; } /* Generated output: four 40 1 40 four 40 0 40 */Note the somewhat peculiar constructions like
cout << ret.first->first << " " << ret.first->second << ...Realize that `
ret
' is the pair
variable returned by the
insert()
member function. Its `first
' field is an iterator into the
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 of the map value (a string
), and `ret.first->second
' is
the value (an int
).
map::iterator insert(pos, keyvalue)
. This is another way to
insert a map::value_type
into the map. pos
is ignored, and an iterator
to the inserted element is returned.
void insert(first, beyond)
inserts the (map::value_type
)
elements pointed to by the
iterator range
[first, beyond)
.
map::iterator map::lower_bound(key)
:this member returns an iterator pointing to the element with the givenkey
. If no such value exists,map::end()
is returned.
map::reverse_iterator map::rbegin()
:this member returns an iterator pointing to the last element of the map.
map::reverse_iterator map::rend()
:this member returns an iterator pointing before the first element of the map.
unsigned map::size()
:this member returns the number of elements in the map.
void map::swap()
:this member can be used to swap two maps.
map::iterator map::upper_bound(key)
:this member returns the iteratormap::end()
. The following example illustrates the member functionsequal_range()
,lower_bound()
andupper_bound()
:#include <iostream> #include <map> using namespace std; int main() { pair<string, int> pa[] = { pair<string,int>("one", 10), pair<string,int>("two", 20), pair<string,int>("three", 30), }; map<string, int> object(&pa[0], &pa[3]); if (object.lower_bound("twoo") == object.end()) cout << "lower-bound `twoo' not available" << endl; cout << "lower-bound two: " << object.lower_bound("two")->first << " is available\n"; if (object.upper_bound("twoo") == object.end()) cout << "upper-bound `twoo' not available" << endl; if (object.upper_bound("two") == object.end()) cout << "upper-bound `two' not available" << endl; pair < map<string, int>::iterator, map<string, int>::iterator > p = object.equal_range("two"); cout << "equal range: `first' points to " << p.first->first << ", `second' is " << ( p.second == object.end() ? "not available" : p.second->first ) << endl; } /* Generated output: lower-bound `twoo' not available lower-bound two: two is available upper-bound `twoo' not available upper-bound `two' not available equal range: `first' points to two, `second' is not available */
map
represents a
sorted associative array. In a map
the keys are sorted. If an application
must
visit all elements in a map (or just the keys or the values)
the begin()
and end()
iterators must be used. The following example
shows how to make a simple table from all keys and values in a map:
#include <iostream> #include <iomanip> #include <map> using namespace std; int main() { pair<string, int> pa[] = { pair<string,int>("one", 10), pair<string,int>("two", 20), pair<string,int>("three", 30), }; map<string, int> object(&pa[0], &pa[3]); for ( map<string, int>::iterator it = object.begin(); it != object.end(); ++it ) cout << setw(5) << it->first.c_str() << setw(5) << it->second << endl; } /* Generated output: one 10 three 30 two 20 */
map
, the
multimap
class implements a (sorted)
associative array. To use the multimap
, source files must
#include <map>The main difference between the
map
and the multimap
is that the
multimap supports multiple entries of the same key, whereas the map contains
unique keys. Note that the multimap also accepts multiple entries of values
having the same keys and the same values.
The map
and the multimap
have the same
set of member functions, with the exception of the
index operator
(
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 object[key]
?
Refer to section 12.2.6 for an
overview of
member functions that are available with the multimap
. Some member
functions, however, act a bit different with the multimap
than with the
map
. These differences are discussed below.
The following member functions act differently with multimap
containers
than with map
containers:
unsigned map::count(key)
:this member returns the
number of entries in the multimap that are associated with the given key
.
... multimap::erase()
:this member can be used to erase elements from the map:
unsigned erase(key)
erases all elements having the
given key
. The number of erased elements is returned.
void erase(pos)
erases the element pointed to by
pos
. Other elements possibly having the same keys are not erased.
void erase(first, beyond)
erases all elements indicated by
the iterator range [first, beyond)
.
pair<multimap::iterator, multimap::iterator> multimap::equal_range(key)
:this member function returns a pair of iterators, being respectively the return values ofmultimap::lower_bound()
andmultimap::upper_bound()
, introduced below. The function provides a simple means to determine all elements in themultimap
that have the samekeys
. An example illustrating the use of these member functions is given at the end of this section.
multimap::iterator multimap::find(key)
:this member returns an iterator pointing to the first value whose key iskey
. If the element isn't available,multimap::end()
is returned. The iterator could be incremented to visit all elements having the samekey
until it is eithermultimap::end()
, or the iterator'sfirst
member is not equal tokey
anymore.
... multimap::insert()
:this member function normally succeeds, and so a multimap::iterator is returned, instead of apair<multimap::iterator, bool>
as returned with themap
container. The returned iterator points to the newly added element.
multimap::iterator multimap::lower_bound(key)
:this member returns an iterator pointing to the firstkeyvalue
element of which thekey
is equal to or exceeds the specifiedkey
. If no such element exists, the function returnsmultimap::end()
.
multimap::iterator multimap::upper_bound(key)
:this member returns an iterator pointing to the firstkeyvalue
element having akey
exceeding the specifiedkey
. If no such element exists, the function returnsmultimap::end()
.
multimap::lower_bound()
,
multimap::upper_bound()
and multimap::equal_range
:
#include <iostream> #include <map> using namespace std; int main() { pair<string, int> pa[] = { pair<string,int>("alpha", 1), pair<string,int>("bravo", 2), pair<string,int>("charley", 3), pair<string,int>("bravo", 6), // unordered `bravo' values pair<string,int>("delta", 5), pair<string,int>("bravo", 4), }; multimap<string, int> object(&pa[0], &pa[6]); typedef multimap<string, int>::iterator msiIterator; msiIterator it = object.lower_bound("brava"); cout << "Lower bound for `brava': " << it->first << ", " << it->second << endl; it = object.upper_bound("bravu"); cout << "Upper bound for `bravu': " << it->first << ", " << it->second << endl; pair<msiIterator, msiIterator> itPair = object.equal_range("bravo"); for (it = itPair.first; it != itPair.second; ++it) cout << it->first << ", " << it->second << endl; cout << "Upper bound: " << it->first << ", " << it->second << endl; } /* Generated output: Lower bound for `brava': bravo, 2 Upper bound for `bravu': charley, 3 bravo, 2 bravo, 6 bravo, 4 Upper bound: charley, 3 */Especially note the following characteristics:
lower_bound()
and upper_bound()
produce the same result for
non-existing keys: they both return the first element having a key that
exceeds the provided key.
multimap
, the values for
equal keys are not ordered: they are retrieved in the order in which they were
enterd.
set
class implements a
sorted collection of values. To use the
set
, source files must
#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 specific value to be inserted into a set
can be
explicitly created: Every set
defines a
value_type
which may be used to
create values that can be stored in the set
. For
example, a value for a set<string>
can be constructed as follows:
set<string>::value_type setValue("Hello");The
value_type
is associated with the set<string>
. Anonymous
value_type
objects are also often used. E.g.,
set<string>::value_type("Hello");Instead of using the line
set<string>::value_type(...)
over
and over again, a
typedef
is often used to
reduce typing and to improve
legibility:
typedef set<string>::value_type StringSetValueUsing this typedef, values for the
set<string>
may be constructed
as follows:
StringSetValue("Hello");Alternatively, values of the type that are used with the set may be used immediately. In that case the value of type
Type
is implicitly
converted to a set<Type>::value_type
.
The following constructors, operators, and member functions are available
vor the set
container:
set
may be constructed empty:
set<int> object;
int intarr[] = {1, 2, 3, 4, 5}; set<int> object(&intarr[0], &intarr[5]);
Like the map, the set
receives its own copy of the data it
contains.
extern set<string> container; set<string> object(container);
set
container only supports the standard set of operators
that are available for containers.
set
class has the following
member
functions:
set::iterator set::begin()
:this member returns an iterator pointing to the first element of the set.
set::clear()
:this member erases all elements from the set.
unsigned set::count(key)
:this member returns 1 if
the provided key is available in the set
, otherwise 0 is returned.
bool set::empty()
:this member returns true
if
the set contains no elements.
set::iterator set::end()
:this member returns an iterator pointing beyond the last element of the set.
pair<set::iterator, set::iterator> set::equal_range(key)
:this member returns a pair of iterators, being respectively the return values of the member functionslower_bound()
andupper_bound()
, introduced below.
... set::erase()
:this member can be used to erase a specific element or range of elements from the set:
bool erase(value)
erases the element having the given
value
from the set
. True
is returned if the value was removed,
false
if the set did not contain an element `value
'.
void erase(pos)
erases the element pointed to by pos
.
void erase(first, beyond)
erases all elements
indicated by the iterator range [first, beyond)
.
set::iterator set::find(value)
:this member returns
an iterator to the element having the given value. If the element isn't
available, end()
is returned.
... set::insert()
:this member can be used to insert elements into theset
. If the element already exists, the existing element is left untouched and the element to be inserted is ignored. The return value depends on the version ofinsert()
that is called:
pair<set::iterator, bool> insert(keyvalue)
is used to insert
a new set::value_type
into the set. The return value is a
pair<set::iterator, bool>
. If the returned
bool
field is true
,
value
was inserted into the set. The value false
indicates that the
value that was specified was already available in the set, and
so the provided value
was not inserted into the set. In both cases the
set::iterator
field points to the data element in the set
having the
specified value
.
set::iterator insert(pos, keyvalue)
. This is another way to
insert a set::value_type
into the set. pos
is ignored, and an iterator
to the inserted element is returned.
void insert(first, beyond)
inserts the (set::value_type
)
elements pointed to by the
iterator range
[first, beyond)
into the
set.
set::iterator set::lower_bound(key)
:this member returns an iterator pointing to the element with the givenkey
. If no such value exists,end()
is returned.
set::reverse_iterator set::rbegin()
:this member returns an iterator pointing to the last element of the set.
set::reverse_iterator set::rend()
:this member returns an iterator pointing before the first element of the set.
unsigned set::size()
:this member returns the number of elements in the set.
void set::swap()
:this member can be used to swap two sets.
set::iterator set::upper_bound(key)
:this member returns an iterator pointing to the element with the givenkey
. If no such value exists,end()
is returned.
set
, the
multiset
class implements a
sorted collection of value. To use the multiset
, source files must
#include <set>The main difference between the
set
and the multiset
is that the
multiset supports multiple entries of the same value, whereas the set contains
unique values.
The set
and the multiset
have the same
set of member functions.
Refer to section 12.2.8 for an
overview of
member functions that are available with the multiset
. Some member
functions, however, act a bit different with the multiset
than with the
set
. These differences are discussed below.
The following member functions act differently with multiset
containers
than with set
containers:
unsigned set::count(value)
:this member returns
the number of entries in the multiset that are associated with the given
value
.
... multiset::erase()
:this member can be used to erase elements from the set:
unsigned erase(value)
erases all elements having the
given value
. The number of erased elements is returned.
void erase(pos)
erases the element pointed to by
pos
. Other elements possibly having the same values are not erased.
void erase(first, beyond)
erases all elements indicated by
the iterator range [first, beyond)
.
pair<multiset::iterator, multiset::iterator> multiset::equal_range(value)
:this member function returns a pair of iterators, being respectively the return values ofmultiset::lower_bound()
andmultiset::upper_bound()
, introduced below. The function provides a simple means to determine all elements in themultiset
that have the samevalues
.
multiset::iterator multiset::find(value)
:this member returns an iterator pointing to the first element having the specified value. If the element isn't available,multiset::end()
is returned. The iterator could be incremented to visit all elements having the givenvalue
until it is eithermultiset::end()
, or the iterator doesn't point to `value
' anymore.
... multiset::insert()
:this member function normally succeeds, and so a multiset::iterator is returned, instead of apair<multiset::iterator, bool>
as returned with theset
container. The returned iterator points to the newly added element.
multiset::iterator multiset::lower_bound(value)
:this member returns an iterator pointing to the firstvaluevalue
element of which thevalue
is equal to or exceeds the specifiedvalue
. If no such element exists, the function returnsmultiset::end()
.
multiset::iterator multiset::upper_bound(value)
:this member returns an iterator pointing to the firstvaluevalue
element having avalue
exceeding the specifiedvalue
. If no such element exists, the function returnsmultiset::end()
.
#include <iostream> #include <set> using namespace std; int main() { string sa[] = { "alpha", "echo", "hotel", "mike", "romeo" }; multiset<string> object(&sa[0], &sa[5]); object.insert("echo"); object.insert("echo"); multiset<string>::iterator it = object.find("echo"); for (; it != object.end(); ++it) cout << *it << " "; cout << endl; pair < multiset<string>::iterator, multiset<string>::iterator > itpair = object.equal_range("echo"); for (; itpair.first != itpair.second; ++itpair.first) cout << *itpair.first << " "; cout << endl << object.count("echo") << " occurrences of 'echo'" << endl; } /* Generated output: echo echo echo hotel mike romeo echo echo echo 3 occurrences of 'echo' */
stack
class implements a
stack data structure. To use the
stack
, source files must
#include <stack>A stack is also called a first in, last out ( FILO or LIFO) data structure, as the first item to enter the stack is the last item to leave. A stack is an extremely useful data structure in situations where data must temporarily remain available. For example, programs maintain a stack to store local variables of functions: these variables lifetime 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 11, 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
11 shows the stack contents after each
token (i.e., the
operands and the operators) is read from the input. Notice that each operand
is indeed 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 11 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 11 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. For the stack
, the following
constructors, operators, and member functions are available:
stack
only supports the basic operators of containers.
bool stack::empty()
:this
member returns true
if the stack contains no elements.
void stack::push(value)
:this member places
value
at the top of the stack, hiding the other elements from view.
void stack::pop()
:this member removes the element at the top of the stack. Note that the popped element is not returned by this member.
unsigned stack::size()
:this member returns the number of elements in the stack.
Type &stack::top()
:this member returns a reference to the first element of the stack. It is the responsibility of the programmer not to use the member if the stack is empty.
operator<()
of the key's
data type. Generally, this is not the fastest
way to either store or retrieve data. The main benefit of sorting is that a
listing of sorted keys appeals more to humans than an unsorted list. However,
a by far faster method to store and retrieve data is to use
hashing.
Hashing uses a function (called the hash function) to compute an (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 hash value of the provided key, and looking in the table at the computed index location: 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.
Collisions occur 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
Gnu
g++ compiler supports the hash_(multi)map and
hash_(multi)set
containers. Below the
hash_map
container is
discussed, but 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 hash value for the key, and an object
comparing two keys for equality. Hash functions are available for
char const *
keys, and for all the
scalar numerical types char, short, int
etc.. If another data type
is used, a hash function and an equality test must be implemented,
possibly using
function objects (see section
9.9). For both situations examples are given below.
The class implementing the hash function could be called hash
. Its
function call operator (
operator()()
) returns the hash value of the key
that is passed as its argument.
A generic algorithm (see chapter 17) 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 specialized
function object could be
constructed here, supporting the equality test of two keys. Again, both
situations are illustrated below.
The hash_map
class implements an
associative array in which the key is
stored according to some hashing scheme. To use the hash_map
, sources must
#include <ext/hash_map>The
hash_(multi)map
is still part of the
ANSI/ISO extension. Once
this container becomes part of the standard, the ext/
prefix in the
#include
preprocessor directive can be removed.
Constructors, operators and member functions that are available for the
map
are also available for the hash_map
. At the user-level there is no
difference in the use of a map
and a hash_map
. However, the
efficiency of a hash_map
in terms of speed should greatly exceed the
efficiency of the map
. Comparable conclusions may be drawn for the
hash_set
, hash_multimap
and the hash_multiset
.
Compared to the map
container, the hash_map
has an extra constructor:
hash_map<...> hash(n);where
n
is an unsigned
value, may be used to construct a
hash_map
consisting of an initial number of at least n
empty slots to
put key/value combinations in. This number is automatically extended when
needed.
The hashed data type is almost always text. So, a hash_map
in which the
key's data type is either char const *
or a string
occurs most often.
If the following
header file is placed in the C++ compiler's
INCLUDE path
as the file
hashclasses.h
, sources could
#include <hashclasses.h>to make available a set of classes that can be used with the instantiation of a hash table. Otherwise, sources must
#include <ext/hash_map>
#ifndef _INCLUDED_HASHCLASSES_H_ #define _INCLUDED_HASHCLASSES_H_ #ifndef _INCLUDED_STRING_ #include <string> #define _INCLUDED_STRING_ #endif #ifndef _INCLUDED_CCTYPE_ #include <cctype> #define _INCLUDED_CCTYPE_ #endif #ifndef _INCLUDED_HASH_MAP_ #include <ext/hash_map> #define _INCLUDED_HASH_MAP_ #endif #ifndef _INCLUDED_ALGORITHM_ #include <algorithm> #define _INCLUDED_ALGORITHM_ #endif /* This file is copyright (c) GPL, 2001, 2002 ========================================== april 2002: namespace FBB introduced abbreviated class templates defined, see the END of this comment section for examples of how to use these abbreviations. jan 2002: redundant include guards added, required header files adapted, for_each() rather than transform() used With hash_maps using char const * for the keys: ============ * Use `HashCharPtr' as 3rd template argument for case-sensitive keys * Use `HashCaseCharPtr' as 3rd template argument for case-insensitive keys * Use `EqualCharPtr' as 4th template argument for case-sensitive keys * Use `EqualCaseCharPtr' as 4th template argument for case-insensitive keys With hash_maps using std::string for the keys: =========== * Use `HashString' as 3rd template argument for case-sensitive keys * Use `HashCaseString' as 3rd template argument for case-insensitive keys * OMIT the 4th template argument for case-sensitive keys * Use `EqualCaseString' as 4th template argument for case-insensitive keys Examples, using int as the value type. Any other type can be used instead for the value type: // key is char const *, case sensitive std::hash_map<char const *, int, FBB::HashCharPtr, FBB::EqualCharPtr > hashtab; // key is char const *, case insensitive std::hash_map<char const *, int, FBB::HashCaseCharPtr, FBB::EqualCaseCharPtr > hashtab; // key is std::string, case sensitive std::hash_map<std::string, int, FBB::HashString> hashtab; // key is std::string, case insensitive std::hash_map<std::string, int, FBB::HashCaseString, FBB::EqualCaseString> hashtab; Instead of the above full typedeclarations, the following shortcuts should work as well: FBB::CharPtrHash<int> // key is char const *, case sensitive hashtab; FBB::CharCasePtrHash<int> // key is char const *, case insensitive hashtab; FBB::StringHash<int> // key is std::string, case sensitive hashtab; FBB::StringCaseHash<int> // key is std::string, case insensitive hashtab; With these template types iterators and other map-members are also available. E.g., -------------------------------------------------------------------------- extern FBB::StringHash<int> dh; for (FBB::StringHash<int>::iterator it = dh.begin(); it != dh.end(); it++) std::cout << it->first << " - " << it->second << std::endl; -------------------------------------------------------------------------- Feb. 2001 - April 2002 Frank B. Brokken (f.b.brokken@rc.rug.nl) */ namespace FBB { class HashCharPtr { public: bool operator()(char const *str) const { return std::hash<char const *>()(str); } }; class EqualCharPtr { public: bool operator()(char const *x, char const *y) const { return !strcmp(x, y); } }; class HashCaseCharPtr { public: bool operator()(char const *str) const { std::string s = str; for_each(s.begin(), s.end(), *this); return std::hash<char const *>()(s.c_str()); } void operator()(char &c) const { c = tolower(c); } }; class EqualCaseCharPtr { public: bool operator()(char const *x, char const *y) const { return !strcasecmp(x, y); } }; class HashString { public: bool operator()(std::string const &str) const { return std::hash<char const *>()(str.c_str()); } }; class HashCaseString: public HashCaseCharPtr { public: bool operator()(std::string const &str) const { return HashCaseCharPtr::operator()(str.c_str()); } }; class EqualCaseString { public: bool operator()(std::string const &s1, std::string const &s2) const { return !strcasecmp(s1.c_str(), s2.c_str()); } }; template<typename Value> class CharPtrHash: public std::hash_map<char const *, Value, HashCharPtr, EqualCharPtr > { public: CharPtrHash() {} template <typename InputIterator> CharPtrHash(InputIterator first, InputIterator beyond) : std::hash_map<char const *, Value, HashCharPtr, EqualCharPtr> (first, beyond) {} }; template<typename Value> class CharCasePtrHash: public std::hash_map<char const *, Value, HashCaseCharPtr, EqualCaseCharPtr > { public: CharCasePtrHash() {} template <typename InputIterator> CharCasePtrHash(InputIterator first, InputIterator beyond) : std::hash_map<char const *, Value, HashCaseCharPtr, EqualCaseCharPtr> (first, beyond) {} }; template<typename Value> class StringHash: public std::hash_map<std::string, Value, HashString> { public: StringHash() {} template <typename InputIterator> StringHash(InputIterator first, InputIterator beyond) : std::hash_map<std::string, Value, HashString> (first, beyond) {} }; template<typename Value> class StringCaseHash: public std::hash_map<std::string, int, HashCaseString, EqualCaseString> { public: StringCaseHash() {} template <typename InputIterator> StringCaseHash(InputIterator first, InputIterator beyond) : std::hash_map<std::string, int, HashCaseString, EqualCaseString> (first, beyond) {} }; } #endifThe following program defines a hash_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 <hashclasses.h> #include <iostream> using namespace std; int main() { // hash_map<char const *, int, HashCaseCharPtr, EqualCaseCharPtr > // the above hash_map uses char const * c-strings, and could also be used. hash_map<string, int, HashString > 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; } /* Generated output: september -> 30 april -> 30 june -> 30 november -> 30 */
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 when source
files
#include <ext/hash_set>
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, sources must
#include <complex>The
complex
container can be used to define complex numbers,
consisting of two parts, representing the real and imaginary 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 type definition 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> using namespace std; 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(); } } /* Generated output: -3.14, -2.71i 3.14, 2.71i */Note the required extra blank space between the two closing pointed arrows in the type specification of
cstack
.
The following member functions and operators are defined for complex
numbers (below, value
may be either a primitve
scalar type or a
complex
object):
complex
container.
complex complex::operator+(value)
:this member returns the sum of the currentcomplex
container andvalue
.
complex complex::operator-(value)
:this member returns the difference between the currentcomplex
container andvalue
.
complex complex::operator*(value)
:this member returns the product of the currentcomplex
container andvalue
.
complex complex::operator/(value)
:this member returns the quotient of the currentcomplex
container andvalue
.
complex complex::operator+=(value)
:this member addsvalue
to the currentcomplex
container, returning the new value.
complex complex::operator-=(value)
:this member subtractsvalue
from the currentcomplex
container, returning the new value.
complex complex::operator*(value)
:this member multiplies the currentcomplex
container byvalue
, returning the new value
complex complex::operator/(value)
:this member divides the currentcomplex
container byvalue
, returning the new value.
Type complex::real()
:this member returns the real part of a complex number.
Type complex::imag()
:this member returns the imaginary part of a complex number.
complex
container, such as
abs()
,
arg()
,
conj()
,
cos()
,
cosh()
,
exp()
,
log()
,
norm()
,
polar()
,
pow()
,
sin()
,
sinh()
and
sqrt()
. These functions are normal functions,
not member functions. They accept complex numbers as their arguments. For
example,
abs(complex<double>(3, -5)); pow(target, complex<int>(2, 3));
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.