Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.Please state the document version you're referring to, as found in the title (in this document: 7.2.2) and please state chapter and paragraph name or number you're referring to.
All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.
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 at 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 operates. As the data types on which the
templates operate were not known at the time the template was constructed, the
datatypes are either inferred from the context in which a function template is
used, or they are mentioned explicitly when a class template is used
(the term that's used here is
instantiated). In situations where the
types are explicitly mentioned, the
angle bracket notation is used to
indicate which data types are required. For example, below (in section
12.2) 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 angle 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 abstract containers. Now that we've introduced this notation, we can postpone the more thorough discussion of templates to chapter 18, and concentrate on their use in this chapter.
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 implemented, 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 storing keys and their associated values. 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 as well as the string
and stream datatypes (cf. chapters 4 and 5) are part of
the Standard Template Library. An abstract container implementing a
hashtable, exists as a supported extension in many compilers, even though
the hashtable container is not yet officially part of the standard C++
library. The final section of this chapter will cover the
hashtable to some extent.
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 side container is less than each corresponding element in the
right-hand side container. Additional elements in either the left-hand side
container or the right-hand side container are ignored.
container left; container right; left = {0, 2, 4}; right = {1, 3}; // left < right right = {1, 3, 6, 1, 2}; // left < right
class
-type) can be stored in a container, the
user-defined type should at least support:
==
)
<
)
Most containers (exceptions are the stack (section 12.3.10), priority_queue (section 12.3.4), and queue (section 12.3.3) containers) support members to determine their maximum sizes (through their member max_size()).
Closely linked to the standard template library are the
generic algorithms. These algorithms may be used to perform
frequently occurring tasks or more complex tasks than is possible with the
containers themselves, like counting, filling, merging, filtering etc.. An
overview of generic algorithms and their applications is given in chapter
17. Generic algorithms usually rely on the availability of
iterators, which represent begin and
end-points for processing data stored within containers. The abstract
containers usually support constructors and members expecting iterators, and
they often have members returning iterators (comparable to the
string::begin()
and
string::end()
members). In the remainder of this
chapter the iterator concept is not covered. Refer to chapter 17 for
this.
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 lifetimes. 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 pointed to by these pointers will not be destroyed,
resulting in a
memory leak. 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 container's
destructor is called. So, normally containers should contain no pointer
data. Also, a container should not be required
to contain const
data, as const
data
prevent the use of many of the container's members, like the assignment
operator.
std::
is usually omitted.
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 pairs of
values, usually called `keys' and `values'. For such containers the following
notational convention is used in addition:
key
indicates a value of the used key-type
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. Before pair
containers can be used the following preprocessor
directive must have been specified:
#include <utility>The data types of a
pair
are specified when the pair
variable is
defined (or declared) using the standard template (see chapter 18)
angle bracket notation:
pair<string, string> piper("PA28", "PH-ANI"); pair<string, string> 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 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)
angle 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.
Before vector
containers can be used the following preprocessor
directive must have been specified:
#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 angle brackets, just after the `vector
'
container name. This is common practice with containers.
int
vector we know its initial values are zero. Some examples:
vector<string> object(5, string("Hello")); // initialize to 5 Hello's, vector<string> 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 element to which the second iterator refers. 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 example, 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 resized 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 to use the member only if the vector is not empty.
vector::iterator vector::begin()
:
this member returns an
iterator pointing to the first
element in the vector, returning vector::end()
if the vector is empty.
size_t vector::capacity()
:
Number of elements for which memory has been
allocated. It returns at least the value returned by size()
vector::clear()
:
this member erases all the vector's elements.
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 the iterator
pos
. The value ++pos
is returned.
erase(first, beyond)
erases elements indicated by the iterator
range [first, beyond)
, returning beyond
.
Type &vector::front()
:
this member returns a reference to the first element in the vector. It is the responsibility of the programmer to use the member only if the vector is not 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::reserve(size_t request)
:
ifrequest
is less than or equal tocapacity()
, this call has no effect. Otherwise, it is a request to allocate additional memory. If the call is successful, thencapacity()
returns a value of at leastrequest
. Otherwise,capacity()
is unchanged. In either case,size()
's return value won't change, until a function likeresize()
is called, actually changing the number of accessible elements.
void vector::resize()
:
this member can be used to alter the number of elements that are currently stored in the vector:
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.
size_t vector::size()
this member returns the number of elements in the vector.
void vector::swap()
this member can be used to swap two vectors using identical data types. E.g.,
#include <iostream> #include <vector> using namespace std; int main() { vector<int> v1(7); vector<int> v2(10); v1.swap(v2); cout << v1.size() << " " << v2.size() << endl; } /* Produced output: 10 7 */
list
container implements a
list data structure. Before list
containers can be used the following preprocessor directive must have been
specified:
#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 directions: 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.
As a subtlety note that the representation given in figure 7 is not necessarily used in actual implementations of the list. For example, consider the following little program:
int main() { list<int> l; cout << "size: " << l.size() << ", first element: " << l.front() << endl; }When this program is run it might actually produce the output:
size: 0, first element: 0Its front element can even be assigned a value. In this case the implementor has choosen to insert a hidden element to the list, which is actually a circular list, where the hidden element serves as terminating element, replacing the 0-pointers in figure 7. As noted, this is a subtlety, which doesn't affect the conceptual notion of a list as a data structure ending in 0-pointers. Note also that it is well known that various implementations of list-structures are possible (cf. Aho, A.V., Hopcroft J.E. and Ullman, J.D., (1983) Data Structures and Algorithms (Addison-Wesley)).
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., a program counting 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
should be the preferred
container; even when implementing algorithms traditionally using lists.
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 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 list<string> 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
s, 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 to use this member only if the list is not empty.
list::iterator list::begin()
:this member
returns an
iterator pointing to the first element in the list, returning
list::end()
if the list is empty.
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 to use this member only if the list is not 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> using namespace std; 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; list<string> 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> using namespace std; 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.
size_t 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, starting the insertion at the iterator positionpos
of the object using thesplice()
member. Followingsplice()
,object
is empty. For example:#include <iostream> #include <string> #include <list> using namespace std; 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,argument
may be followed by an iterator ofargument
, indicating the first element ofargument
that should be spliced, or by two iteratorsbegin
andend
defining the iterator-range[begin, end)
onargument
that should be spliced intoobject
.
void list::swap()
:this member can be used to swap two lists using identical data types.
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 removing all multiply occurring words from the list:#include <iostream> #include <string> #include <list> using namespace std; // see the merge() example void showlist(list<string> &target); void showlist(list<string> &target) { for ( list<string>::iterator from = target.begin(); from != target.end(); ++from ) cout << *from << " "; cout << endl; } int main() { string array[] = { "charley", "alpha", "bravo", "alpha" }; list<string> target ( array, array + sizeof(array) / sizeof(string) ); cout << "Initially we have: " << endl; showlist(target); target.sort(); cout << "After sort() we have: " << endl; showlist(target); target.unique(); cout << "After unique() we have: " << endl; showlist(target); } /* Generated output: Initially we have: charley alpha bravo alpha After sort() we have: alpha alpha bravo charley After unique() we have: alpha bravo charley */
queue
class implements a
queue data structure. Before queue
containers can be used the following preprocessor directive must have been
specified:
#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:
queue
container only supports the basic operators for
containers.
Type &queue::back()
:this member returns a reference to the last element in the queue. It is the responsibility of the programmer to use the member only if the queue is not 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 to use the member only if the queue is not 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. Nothing happens if the member is called for an empty queue. One might wonder whypop()
returnsvoid
, instead of a value of typeType
(cf.front()
). Because of this, we must usefront()
first, and thereafterpop()
to examine and remove the queue's front element. However, there is a good reason for this design. Ifpop()
would return the container's front element, it would have to return that element by value rather than by reference, as a return by reference would create a dangling pointer, sincepop()
would also remove that front element. Return by value, however, is inefficient in this case: it involves at least one copy constructor call. Since it is impossible forpop()
to return a value correctly and efficiently, it is more sensible to havepop()
return no value at all and to require clients to usefront()
to inspect the value at the queue's front.
size_t queue::size()
:this member returns the number of elements in the queue.
priority_queue
class implements a
priority queue data structure.
Before priority_queue
containers can be used the following preprocessor
directive must have been specified:
#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> using namespace std; 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 { std::string d_s; public: Text(std::string const &str) : d_s(str) {} operator std::string const &() const { return d_s; } bool operator<(Text const &right) const { return d_s > right.d_s; } }; using namespace std; 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. Nothing happens if this member is called for and empty priority queue. See section 12.3.3 for a discussion about the reason whypop()
has return typevoid
.
size_t 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 to use the member only if the priority queue is not empty.
deque
(pronounce: `deck') class implements a
doubly ended queue data structure (deque). Before deque
containers
can be used the following preprocessor directive must have been specified:
#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 available member functions. 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 deque<string> 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 to use the member only if the deque is not empty.
deque::iterator deque::begin()
:this member returns an iterator pointing to the first element in the deque.
void 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 to use the member only if the deque is not 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
starting at iterator 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.
size_t deque::size()
:this member returns the number of elements in the deque.
void deque::swap(argument)
:this member can be used to swap two deques using identical data types.
map
class offers a (sorted)
associative array. Before map
containers can be used, the following preprocessor directive must have been
specified:
#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
angle bracket notation,
comparable to the specification we've seen with the pair
(section
12.2) container. 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 to access its associated information. That 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. Since a
map
sorts its keys, the key
's operator<()
must be
defined, and it must be sensible to use it. For example, it is generally a bad
idea to use pointers for keys, as sorting pointers is something different than
sorting the values these pointers point to.
The two fundamental operations on maps are the
storage of Key/Value
combinations, and the
retrieval of values, given their keys. The index
operator using a key as the index, can be used for both. If the index
operator is used as lvalue, insertion will be performed. If it is used as
rvalue, the key's associated value is retrieved. 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 now be
constructed using:
StringIntValue("Hello", 1);Finally,
pairs
may be used to represent key/value combinations used by
maps:
pair<string, int>("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 angle brackets
>
: this
is obligatory, as the immediate
concatenation of the two
angle 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 to
plain
pair
objects (see section 12.2). If pairs are used, their
first
elements represent the keys, and their 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 written
instead of pair<string, int>
as well.
When begin
is the first iterator used to construct a map and
end
the second iterator, [begin, end)
will be used to initialize
the map. 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.
The map
receives its own copies of the data to which the iterators
point. This 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 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 is 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 type of
the right-hand side of the assignment operator must be equal to (or promotable
to) the type of the map's value part. 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.
size_t 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 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 the iterator
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 into the map. It will, however, not replace the values
associated with already existing keys by new values. Its return value depends
on the version of insert()
that is called:
pair<map::iterator, bool> insert(keyvalue)
inserts
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 having the
key
that was specified in keyvalue
. The use of this variant of
insert()
is illustrated by 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' is returned pair<map<string, int>::iterator, bool> ret = object.insert ( map<string, int>::value_type ("four", 40) ); cout << boolalpha; cout << ret.first->first << " " << ret.first->second << " " << ret.second << " " << object["four"] << endl; // {four, 40} and `false' 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 true 40 four 40 false 40 */Note the somewhat peculiar constructions like
cout << ret.first->first << " " << ret.first->second << ...Note that `
ret
' is equal to the pair
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 way a
map::value_type
may also be inserted 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 firstkeyvalue
element of which thekey
is at least equal to the specifiedkey
. If no such element exists, the function returnsmap::end()
.
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.
size_t map::size()
:this member returns the number of elements in the map.
void map::swap(argument)
:this member can be used to swap two maps using identical key/value types.
map::iterator map::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 returnsmap::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]); map<string, int>::iterator it; if ((it = object.lower_bound("tw")) != object.end()) cout << "lower-bound `tw' is available, it is: " << it->first << endl; 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 ((it = object.upper_bound("tw")) != object.end()) cout << "upper-bound `tw' is available, it is: " << it->first << endl; 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 `tw' is available, it is: two lower-bound `twoo' not available lower-bound two: two is available upper-bound `tw' is available, it is: two 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 listing 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. Before multimap
containers can be used the
following preprocessor directive must have been specified:
#include <map>The main difference between the
map
and the multimap
is that the
multimap supports multiple values associated with the same key, whereas the
map contains single-valued keys. Note that the multimap also accepts multiple
identical values associated with identical keys.
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.3.6 for an
overview of
the multimap
member functions. Some member functions, however, deserve
additional attention when used in the context of the multimap
container. These members are discussed below.
size_t map::count(key)
:this member returns the
number of entries in the multimap associated with the given key
.
... multimap::erase()
:this member can be used to erase elements from the map:
size_t erase(key)
erases all elements having the
given key
. The number of erased elements is returned.
void erase(pos)
erases the single 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::iterator 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.
lower_bound()
and upper_bound()
act
identically in the map
and multimap
containers, their operation in a
multimap
deserves some additional attention. The next example illustrates
multimap::lower_bound()
, multimap::upper_bound()
and
multimap::equal_range
applied to a multimap
:
#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"); cout << "Equal range for `bravo':\n"; for (it = itPair.first; it != itPair.second; ++it) cout << it->first << ", " << it->second << endl; cout << "Upper bound: " << it->first << ", " << it->second << endl; cout << "Equal range for `brav':\n"; itPair = object.equal_range("brav"); 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 Equal range for `bravo': bravo, 2 bravo, 6 bravo, 4 Upper bound: charley, 3 Equal range for `brav': Upper bound: bravo, 2 */In particular 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. Before set
containers can be used the following preprocessor directive must have been
specified:
#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 set's type 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
for 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. If the set is
empty set::end()
is returned.
set::clear()
:this member erases all elements from the set.
size_t 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 the iterator
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)
inserts
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 way a
set::value_type
may also be inserted 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 firstkeyvalue
element of which thekey
is at least equal to the specifiedkey
. If no such element exists, the function returnsset::end()
.
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.
size_t set::size()
:this member returns the number of elements in the set.
void set::swap(argument)
:this member can be used
to swap two sets (argument
being the second set) that use identical data
types.
set::iterator set::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 returnsset::end()
.
set
, the
multiset
class implements a
sorted collection of values. Before
multiset
containers can be used the following preprocessor directive must have
been specified:
#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.3.8 for an overview
of the multiset
member functions. Some member functions, however,
deserve additional attention when used in the context of the multiset
container. These members are discussed below.
size_t set::count(value)
:this member returns
the number of entries in the multiset associated with the given
value
.
... multiset::erase()
:this member can be used to erase elements from the set:
size_t 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 the iterator
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.
lower_bound()
and upper_bound()
act
identically in the set
and multiset
containers, their operation in a
multiset
deserves some additional attention. In particular note that with
the multiset
container lower_bound()
and upper_bound()
produce the
same result for non-existing keys: they both return the first element having a
key exceeding the provided key.
Here is an example showing the use of various member functions of a multiset:
#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; cout << "Multiset::equal_range(\"ech\")\n"; pair < multiset<string>::iterator, multiset<string>::iterator > itpair = object.equal_range("ech"); if (itpair.first != object.end()) cout << "lower_bound() points at " << *itpair.first << endl; for (; itpair.first != itpair.second; ++itpair.first) cout << *itpair.first << " "; cout << endl << object.count("ech") << " occurrences of 'ech'" << endl; cout << "Multiset::equal_range(\"echo\")\n"; itpair = object.equal_range("echo"); for (; itpair.first != itpair.second; ++itpair.first) cout << *itpair.first << " "; cout << endl << object.count("echo") << " occurrences of 'echo'" << endl; cout << "Multiset::equal_range(\"echoo\")\n"; itpair = object.equal_range("echoo"); for (; itpair.first != itpair.second; ++itpair.first) cout << *itpair.first << " "; cout << endl << object.count("echoo") << " occurrences of 'echoo'" << endl; } /* Generated output: echo echo echo hotel mike romeo Multiset::equal_range("ech") lower_bound() points at echo 0 occurrences of 'ech' Multiset::equal_range("echo") echo echo echo 3 occurrences of 'echo' Multiset::equal_range("echoo") 0 occurrences of 'echoo' */
stack
class implements a
stack data structure. Before stack
containers can be used the following preprocessor directive must have been
specified:
#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: the lifetime of these variables is determined by the time these functions are active, 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 operators are entered in the stack, whereas operators pop their operands off the stack and push the results of their work back onto the stack.
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 pushed onto and popped off the stack. This top element is the stack's only immediately visible element. It may be accessed and modified directly.
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
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. Nothing happens ifpop()
is used with an empty stack. See section 12.3.3 for a discussion about the reason whypop()
has return typevoid
.
size_t stack::size()
:this member returns the number of elements in the stack.
Type &stack::top()
:this member returns a reference to the stack's top (and only visible) element. It is the responsibility of the programmer to use this member only if the stack is not 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. 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 numeric 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.10). 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. Before hash_map
containers can be
used the following preprocessor directive must have been specified:
#include <ext/hash_map>The
hash_(multi)map
is not yet part of the
ANSI/ISO standard. Once
this container becomes part of the standard, it is likely that the ext/
prefix in the #include
preprocessor directive can be removed. Note that
starting with the
Gnu
g++
compiler version 3.2 the
__gnu_cxx
namespace is used
for symbols defined in the ext/
header files. See also section
2.1.
Constructors, operators and member functions available for the map
are
also available for the hash_map
. The map
and hash_map
support
the same set of operators and member functions. 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 additional
constructor:
hash_map<...> hash(n);where
n
is a size_t
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 key 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 installed in the C++ compiler's
INCLUDE path
as the file
hashclasses.h
, sources may specify the
following preprocessor directive to make a set of classes available that can
be used to instantiate
a hash table
#include <hashclasses.h>Otherwise, sources must specify the following preprocessor directive:
#include <ext/hash_map>
#ifndef INCLUDED_HASHCLASSES_H_ #define INCLUDED_HASHCLASSES_H_ #include <string> #include <cctype> /* Note that with the Gnu g++ compiler 3.2 (and beyond?) the ext/ header uses the __gnu_cxx namespace for symbols defined in these header files. When using compilers before version 3.2, do: #define __gnu_cxx std before including this file to circumvent problems that may occur because of these namespace conventions which were not yet used in versions before 3.2. */ #include <ext/hash_map> #include <algorithm> /* This file is copyright (c) GPL, 2001-2004 ========================================== august 2004: redundant include guards removed october 2002: provisions for using the hashclasses with the g++ 3.2 compiler were incorporated. 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 __gnu_cxx::hash_map<char const *, int, FBB::HashCharPtr, FBB::EqualCharPtr > hashtab; // key is char const *, case insensitive __gnu_cxx::hash_map<char const *, int, FBB::HashCaseCharPtr, FBB::EqualCaseCharPtr > hashtab; // key is std::string, case sensitive __gnu_cxx::hash_map<std::string, int, FBB::HashString> hashtab; // key is std::string, case insensitive __gnu_cxx::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@rug.nl) */ namespace FBB { class HashCharPtr { public: size_t operator()(char const *str) const { return __gnu_cxx::hash<char const *>()(str); } }; class EqualCharPtr { public: bool operator()(char const *x, char const *y) const { return !strcmp(x, y); } }; class HashCaseCharPtr { public: size_t operator()(char const *str) const { std::string s = str; for_each(s.begin(), s.end(), *this); return __gnu_cxx::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: size_t operator()(std::string const &str) const { return __gnu_cxx::hash<char const *>()(str.c_str()); } }; class HashCaseString: public HashCaseCharPtr { public: size_t 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 __gnu_cxx::hash_map<char const *, Value, HashCharPtr, EqualCharPtr > { public: CharPtrHash() {} template <typename InputIterator> CharPtrHash(InputIterator first, InputIterator beyond) : __gnu_cxx::hash_map<char const *, Value, HashCharPtr, EqualCharPtr>(first, beyond) {} }; template<typename Value> class CharCasePtrHash: public __gnu_cxx::hash_map<char const *, Value, HashCaseCharPtr, EqualCaseCharPtr > { public: CharCasePtrHash() {} template <typename InputIterator> CharCasePtrHash(InputIterator first, InputIterator beyond) : __gnu_cxx::hash_map<char const *, Value, HashCaseCharPtr, EqualCaseCharPtr> (first, beyond) {} }; template<typename Value> class StringHash: public __gnu_cxx::hash_map<std::string, Value, HashString> { public: StringHash() {} template <typename InputIterator> StringHash(InputIterator first, InputIterator beyond) : __gnu_cxx::hash_map<std::string, Value, HashString> (first, beyond) {} }; template<typename Value> class StringCaseHash: public __gnu_cxx::hash_map<std::string, int, HashCaseString, EqualCaseString> { public: StringCaseHash() {} template <typename InputIterator> StringCaseHash(InputIterator first, InputIterator beyond) : __gnu_cxx::hash_map<std::string, int, HashCaseString, EqualCaseString>(first, beyond) {} }; template<typename Key, typename Value> class Hash: public __gnu_cxx::hash_map<Key, Value, __gnu_cxx::hash<Key>(), equal<Key>()) {}; } #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 <iostream> // the following header file must be available in the compiler's // INCLUDE path: #include <hashclasses.h> using namespace std; using namespace FBB; int main() { __gnu_cxx::hash_map<string, int, HashString > months; // Alternatively, using the classes defined in hashclasses.h, // the following definitions could have been used: // CharPtrHash<int> months; // or: // StringHash<int> 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.
Before the hash_set
and hash_multiset
containers can be used the
following preprocessor directive must have been specified:
#include <ext/hash_set>
complex
container is a specialized container in that it defines
operations that can be performed on
complex numbers, given possible
numeric real and imaginary data types.
Before complex
containers can be used the following preprocessor directive
must have been specified:
#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, accepting 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.