- Next chapter
- Previous chapter
- Table of contents

# Chapter 7: Abstract Containers

> We're always interested in getting feedback. E-mail us if you like this guide, if you think that important material is omitted, if you encounter errors in the code examples or in the documentation, if you find any typos, or generally just if you feel like e-mailing. Mail to Frank Brokken or use an e-mail form. Please state the concerned document version, found in the title.

C++ offers several predefined datatypes, all part of the Standard Template Library, which can be used to implement solutions to frequently occurring problems. The datatypes discussed in this chapter are all containers: you can put stuff inside them, and you can retrieve the stored information from them.

The interesting part is that the kind of data that can be stored inside these containers has been left unspecified by the time the containers were constructed. That's why they are spoken of as abstract containers.

The abstract containers rely heavily on templates, which are covered near the end of the C++ Annotations, in chapter 16. However, in order to use the abstract containers, only a minimal grasp of the template concept is needed. In C++ a template is in fact a recipe for constructing a function or a complete class. The recipe tries to abstract the functionality of the class or function as much as possible from the data on which the class or function operate. As the types of the data on which the templates operate were not known by the time the template was constructed, the datatypes are either inferred from the context in which a template function is used, or they are mentioned explicitly by the time a template class is used (the term that's used here is instantiated). In situations where the types are explicitly mentioned, the angular bracket notation is used to indicate which data types are required. For example, below (in section 7.1) we'll encounter the `pair` container, which requires the explicit mentioning of two data types. E.g., to define a `pair` variable containing both an `int` and a `string`, the notation

        pair<int, string>
            myPair;

is used. Here, `myPair` is defined as a `pair` variable, containing both an `int` and a `string`.

The angular bracket notation is used intensively in the following discussion of the abstract container. Actually, understanding this part of templates is the only real requirement for being able to use the abstract containers. Now that we've introduced this notation, we can postpone the more thorough discussion of templates to chapter 16, and get on with their use in the form of the abstract container classes.

Most of the abstract containers are sequential containers: they represent a series of data which can be stored and retrieved in some sequential way. Examples are the `vector`, implementing an extendable array, the `list`, implementing a datastructure in which insertions and deletions can be easily realized, a `queue`, in which the first element that is entered will be the first element that will be retrieved, and the stack, which is a first in, last out datastructure.

Apart from the sequential containers, several special containers are available. The `pair` is a basic container in which a pair of values (of types that are left open for further specification) can be stored, like two strings, two ints, a string and a double, etc.. Pairs are often used to return data elements that naturally come in pairs. For example, the `map` is an abstract container in which keys and corresponding values are stored. Elements of these maps are returned as `pairs`.

A variant of the `pair` is the `complex` container, which implements operations that are defined on complex numbers.

All abstract containers described in this chapter and the `string` datatype discussed in section 3.3.3 are part of the standard template library. There exists also an abstract container for the implementation of a hashtable, but that container is not (yet) accepted by the `ISO/ANSI` standard. The final section of this chapter will cover the hashtable to some extent.

All containers support the `=` operator to assign two containers of the same type to each other. All containers also support the `==, !=, <, <=, >` and `>=` operators.

Note that if a user-defined type (usually a `class`-type) is to be stored in a container, the user-defined type must support

- A default-value (e.g., a default constructor)
- The equality operator (`==`)
- The less-than operator (`<`)

Closely linked to the standard template library are the generic algorithms. These algorithms may be used to perform even more tasks than is possible with the containers themselves, like counting, filling, merging, filtering etc.. An overview of the generic algorithms and their applications is given in chapter 10. Generic algorithms usually rely on the availability of iterators, which represent begin and endpoints for processing data stored inside the containers. The abstract containers normally have constructors and members using iterators themselves, and they have members returning iterators (comparable to the `string::begin()` and `string::end()` members). In the remainder of this chapter the use of iterators is not really covered. Refer to chapter 10 for the discussion of iterators.

The url http://www.sgi.com/Technology/STL is worth visiting by those readers who want more information about the abstract containers and the standard template library than can be provided in the C++ annotations.

Containers often collect data during their lifetime. When a container goes out of scope, its destructor tries to destroy its data elements. This only succeeds if the data elements themselves are stored inside the container. If the data elements of containers are pointers, the data to which these pointers point will not be destroyed, and a memory leak will result. A consequence of this scheme is that the data stored in a container should be considered the `property' of the container: the container should be able to destroy its data elements when the destructor of the container is called. Consequently, the container should not only contain no pointer data, but it should also not contain `const` data elements, as these data elements cannot be destroyed by the container's destructor.

## 7.1: The `pair' container

The `pair` container is a rather basic container. It can be used to store two elements, called `first` and `second`, and that's about it. To define a variable as a `pair` container, the header file

                #include <utility>

must be included.

The data types of a `pair` are defined when the `pair` variable is defined, using the standard template (see chapter `Templates`) notation:

                pair<string, string>
                    piper("PA28", "PH-ANI"),
                    cessna("C172", "PH-ANG");

here, the variables `piper` and `cessna` are defined as `pair` variables containing two `strings`. Both strings can be retrieved using the `first` and `second` fields of the `pair` type:

                cout << piper.first << endl <<  // shows 'PA28'
                        cessna.second << endl;  // shows 'PH-ANG'

The `first` and `second` members can also be used to reassign values:

                cessna.first = "C152";
                cessna.second = "PH-ANW";

If a `pair` variable must be completely reassigned, it is also possible to use an anonymous pair variable as the right-hand side operand of the assignment. An anonymous variable defines a temporary variable (which receives no name) solely for the purpose of (re)assigning another variable of the same type. Its general form is

                type(initializer list)

Note, however, that with a `pair` variable the type specification is not completed when the containername `pair` has been mentioned. It also requires the specification of the data types which are stored inside the pair. For this the (template) angular bracket notation is used again. E.g., the reassignment of the `cessna` pair variable could also have been accomplished as follows:

                cessna = pair<string, string>("C152", "PH-ANW");

In cases like this, the `type` specification can become quite elaborate, which has caused a revival of interest in the possibilities offered by the `typedef` keyword. If a lot of `pair<type1, type2>` clauses are used in a source, the amount of typing may be reduced and legibility might be improved by first defining a name for the clause, and then using the defined name later on. E.g.,

                typedef pair<string, string> pairStrStr
                ...
                cessna = pairStrStr("C152", "PH-ANW")

Apart from this (and the basic set of operations (assignment and comparisons) the `pair` has no further special features. It is, however, a basic ingredient of the upcoming abstract containers `map, multimap` and `hash_map`.

## 7.2: Sequential Containers

### 7.2.1: The `vector' container

The `vector` class implements an (expandable) array. To use the `vector`, the header file `vector` must be included:

                #include <vector>

`Vector`s can be used like arrays, and can be defined with a fixed number of elements. E.g., to define a vector of 30 `int`s we do

                vector<int>
                    iVector(30);

Note the specification of the data type that is to be used: the datatype is given between angular brackets after the `vector` container name. So, a vector of 30 `string`s is defined as

                vector<string>
                    strVector(30);

One of the nice characteristics of defining such a vector is that it's initialized to the data type's default value. If there is a default constructor, it is called to construct the elements of the vector. For the basic data types the initial value is zero. So, for the `int` vector we know its values are 0.

Another way to initialize the vector is to use explicit initialization values:

                vector<int>
                    iVector(1, 2, 3);

This does not work, however, if a vector of one element must be initialized to a non-default value.

As with `string` variables,

- `vector` objects may be initialized with other `vectors`, or parts of existing `vector`s may be used to initialize a `vector`:

                  vector<int>
                      a(10);
                  ...
                  vector<int>
                      b(&a[3], &a[6]);

Note here that the last element mentioned is not used for the initialization. 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)`.

- `vectors` may be assigned to each other,
- the subscript operator may be used to retrieve individual elements,
- the `==` and `!=` operators may be used to test the equality of two `vectors`.
- the `<` operator may be used to test whether each element in the left-hand operand vector is less than each corresponding element in the right-hand operand vector. The `<=, >` and `>=` operators are also available.
- the `size()` and `empty()` memberfunctions are available,
- the `swap()` memberfunction is available, swapping two vectors. E.g.,

              int main()
              {
                  vector<int>
                      v1(10),
                      v2(10);

                  v1.swap(v2);
              }

- elements may be inserted at a certain position `pos`. Below `source` represents a value of the type that is stored in the vector, while `pos` is an iterator pointing to a position in the vector where `source` must be inserted:
  - `insert(pos, source)` inserts `source` at `pos`,
  - `insert(pos, begin, end)` inserts the elements in the iterator range `[begin, end)`.
  - `insert(pos, n, source)` inserts `n` elements having value `source` at position `pos`.
- elements may be erased:
  - `erase()` and `clear()` both erase all elements, `clear()` is not available with `strings`.
  - `erase(pos)` erases all elements starting at position `pos`,
  - `erase(begin, end)` erases elements indicated by the iterator range `[begin, end)`.
- `resize(n)` and `resize(n, source)` may be used to resize the vector to a size of `n`. If the vector is expanded, the extra elements are initialized by the default value of the used datatype, or by the explicitly provided value `source`.

Also available are:

- `void pop_back()` may be used to remove the last element from the vector. The element is not returned by this memberfunction.
- `front()`, returning the initial element of the `vector`,
- `back()`, returning the final element of the `vector`,
- `push_back(source)` stores `source` at the end of the `vector`: a new element is added at the end.

Note that a vector may be defined without size: `vector<int> ivect;`. This defines an empty vector, without any element at all. Therefore, a statement like `ivect[0] = 18;` would (in this case) be an error, as there isn't any element as yet. In this case the preferred idiom is `ivect.push_back(18);`

### 7.2.2: The `list' container

The `list` class implements a list datastructure. To use the `list`, the header file `list` must be included:

                #include <list>

A list is depicted in figure 5.

figure 5: A list data-structure

In figure 5 it is shown that a list consists of separate data-items, connected to each other by pointers. The list can be traversed in two ways: starting at the Front the list may be traversed from left to right, until the 0-pointer is reached at the end of the rightmost data-item. The list can also be traversed from right to left: starting at the Back, the list is traversed from right to left, until eventually the 0-pointer emanating from the leftmost data-item is reached.

Both lists and vectors are often possible datastructures in situations where an unknown number of data elements must be stored. However, there are some rules of thumb to follow when a choice between the two datastructures must be made.

- When the majority of accesses is random, then the `vector` is the preferred datastructure. E.g., in a program that counts the frequencies of characters in a textfile, a `vector<int> frequencies(256)` is the datastructure doing the trick, as the values of the received characters can be used as indices into the `frequencies` vector.
- The previous example illustrates a second rule of thumb, also favoring the `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`.
- In cases where insertions and deletions prevail, the list is generally preferred. Actually, in my experience, lists aren't that useful at all, and often an implementation will be faster when a `vector`, maybe containing holes, is used. Nonetheless, the `list` container exists, and it may become popular now that the list-management is part of the implementation of the abstract container.

Other considerations related to the choice between lists and vectors should also be given some thought. Although it is true that the vector is able to grow dynamically, the dynamical growth does involve a lot of copying of data elements. Clearly, copying a million large datastructures takes a considerable amount of time, even on fast computers. On the other hand, inserting a large number of elements in a list doesn't require us to copy the remainder of the list structure: inserting a new element in a list merely requires us to juggle some pointers. In figure 6 this is shown: a new element is inserted between the second and third element, creating a new list of four elements.

figure 6: Adding a new element to a list

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

figure 7: Removing an element from a list

Summarizing the comparison between lists and vectors, it's probably best to conclude that there is no clear-cut answer to the question what datastructure to prefer. There are rules of thumb, which may be adhered to. But if worse comes to worst, a profiler may be required to find out what's working best. But, no matter what thoughts remain, the `list` container is available, so let's see what we can do with it. As with the `vector`-class, the following constructors and memberfunctions are available:
Constructors:

- an empty list is created using, e.g.,

          list<string>
              strList;

- A list may be initialized with a certain number of elements. By default, if the initialization value is not explicitly mentioned, the defaultvalue or default constructor for the actual datatype is used. For example:

          list<string>
              hello(5, string("Hello")),  // initialize to 5 Hello's
              zilch(10);                  // initialize to 10 empty strings

- A list may be initialized using a two iterators, e.g., to initialize a list with elements 5 until 10 (including the last one) of a `vector<string>` the following construction may be used:

          extern vector<string>
              svector;
          list<string>
              slist(&svector[5], &svector[11]);

Note that a list may be defined without size:
`list<int> ivect;`
This defines an empty list, without any element at all. So, a statement like
`*ivect.begin() = 18;`
would in this case be an error, as there isn't any element as yet. In this case, the preferred idiom is:
`ivect.push_back(18);`
Other memberfunctions, some of which were also available in `vector`, are:

- `back()`, returning the last element of the list.
- `clear()`,
- `front()`, returning the first element of the list.
- `empty()`,
- elements may be erased:
  - `erase()` and `clear()` both erase all elements,
  - `erase(pos)` erases all elements starting at the position pointed to by iterator `pos`,
  - `erase(begin, end)` erases elements indicated by the iterator range `[begin, end)`.
- elements may be inserted at a certain position pointed to by the iterator `pos`:
  - `insert(pos, source)` inserts `source` at the position pointed to by `pos`,
  - `insert(pos, begin, end)` inserts the elements in the iterator range `[begin, end)` at the position pointed to by `pos`.
  - `insert(pos, n, argument)` inserts `n` elements having value `argument` at the position pointed to by `pos`. The data type of `argument` must be equal to the data type of the the elements of the list.
- `resize(n)` and `resize(n, argument)` may be used to resize the list to a size of `n`. If the list is expanded, the extra elements are initialized by the default value of the used datatype, or by the explicitly provided value `argument`.
- `size()`,
- `swap(argument)`, swaps two lists.

Also available are:

- `void push_front(source)` to enter a new element at the head of the list.
- `void push_back(source)` to enter a new element at the end of the list.
- `void pop_front()` may be used to remove the first element from the list. This element is not returned by this memberfunction.
- `void pop_back()` may be used to remove the last element from the list. This element is not returned by this memberfunction.
- `remove(source)`: This memberfunction removes all occurrences of `source` from the list: the two strings `Hello` are removed from the list `object` in the following example:

      #include <iostream>
      #include <string>
      #include <list>

      int main()
      {
          list<string>
              object;

          object.push_back(string("Hello"));
          object.push_back(string("World"));
          object.push_back(string("Hello"));
          object.push_back(string("World"));

          object.remove(string("Hello"));

          while (object.size())
          {
              cout << object.front() << endl;
              object.pop_front();
          }

          return (0);
      }

- `sort()` will sort the list. Once the list has been sorted, the following memberfunction (`unique()`) may be used to remove all multiply occurring elements from the list, leaving only one element of each. The following example shows the use of both memberfunctions.
- `unique()` makes sure that each element will occur only once. Here's an example, leaving each single word only once in the list:

      #include <iostream>
      #include <string>
      #include <list>

      int main()
      {
          list<string>
              target;

          target.push_back(string("A"));
          target.push_back(string("rose"));
          target.push_back(string("is"));
          target.push_back(string("a"));
          target.push_back(string("rose"));
          target.push_back(string("is"));
          target.push_back(string("a"));
          target.push_back(string("rose"));

          cout << "Initially we have: " << endl;
          list<string>::iterator
              from;
          for (from = target.begin(); from != target.end(); ++from)
              cout << *from << " ";
          cout << endl;
          target.sort();
          cout << "After sort() we have: " << endl;
          for (from = target.begin(); from != target.end(); ++from)
              cout << *from << " ";
          cout << endl;
          target.unique();
          cout << "After unique() we have: " << endl;
          for (from = target.begin(); from != target.end(); ++from)
              cout << *from << " ";
          cout << endl;

          return (0);
      }

- `merge(argument)` combines the current list and the `argument` list. The merging will add elements of `source` to `target`. When both lists are ordered, the resulting list will be ordered as well. If both list are not completely ordered, the resulting list will be ordered as much as possible, given the initial ordering of the elements in each list. In the following example this is illustrated: the `object` list is not completely ordered, but the resulting list (`alfa bravo golf oscar mike november quebec zulu`) is ordered 'as much as possible': `mike` has to follow `oscar`, since this ordering is imposed by `object`, but given that imperfection the resulting list is ordered alphabetically.

      #include <iostream>
      #include <string>
      #include <list>

      int main()
      {
          list<string>
              object,
              argument;

          object.push_back(string("alfa"));
          object.push_back(string("bravo"));
          object.push_back(string("golf"));
          object.push_back(string("quebec"));

          argument.push_back(string("oscar"));
          argument.push_back(string("mike"));
          argument.push_back(string("november"));
          argument.push_back(string("zulu"));

          object.merge(argument);

          list<string>::iterator
              from;
          for (from = object.begin(); from != object.end(); ++from)
              cout << *from << " ";
          cout << endl;

          return (0);
      }

Note that the members `merge()` and `sort()` both assume the availability of the `<` and `==` operators.

- `target.splice(iterator position, list source)`: This memberfunction transfers the contents of `source` to the current list. Following `splice()`, `source` is empty. For example:

      #include <iostream>
      #include <string>
      #include <list>

      int main()
      {
          list<string>
              object;

          object.push_front(string("Hello"));
          object.push_back(string("World"));

          list<string>
              argument(object);

          object.splice(++object.begin(), argument);

          cout << "Object contains " << object.size() << " elements, " <<
                  "Argument contains " << argument.size() << " elements," << endl;

          while (object.size())
          {
              cout << object.front() << endl;
              object.pop_front();
          }

          return (0);
      }

  Alternatively, `source` may be followed by a iterator of `source`, indicating the first element of `source` that should be spliced, or by two iterators `begin` and `end` defining the iterator-range `[begin, end)` on `source` that should be spliced into `target`.

Available operators with the `list` containertype are:

- The assignment of a list to another: `=`,
- The test for equality of two lists: `==`,
- The test for inequality of two lists: `!=`,
- `<`: This operator returns `true` if each element stored in the left-hand operand list is less than each corresponding element in the right-hand operand list, based on the `<`-operator of the element-type of the lists. Also available are the `<=, >` and `>=` operators.

### 7.2.3: The `queue' container

The `queue` class implements a queue datastructure. To use the `queue`, the header file `queue` must be included:

        #include <queue>

A queue is depicted in figure 8.

figure 8: A queue data-structure

In figure 8 it is shown that a queue has one point (the back) where items can be added to the queue, and one point (the front) where items can be removed (read) from the queue.

Bearing this model of the queue in mind, let's see what we can do with it.

A queue can be initialized by an existing other queue, or it can be created empty:

        queue<int>
            queue1;
        ...
        queue<int>
            queue2(queue1);

Apart from these constructors, and the basic operators for comparison and assignment (see the introductory paragraph of this chapter), the following memberfunctions are available:

- `empty()`,
- `size()`,
- `front()`: returns the first element that would be removed by `pop()`, Alternatively, the last element of the queue may be reassigned, as illustrated in the following example, in which `Hello World`, rather than `Hello` is displayed:

      #include <iostream>
      #include <string>
      #include <queue>

      int main()
      {
          queue<string>
              q;

          q.push("Hello");
          q.front() = "Hello World";

          cout << q.front() << endl;

          return (0);
      }

- `back()`: returns the last element that was added to the queue. Like `front(), back()` can be used to reassign the last item that was added to the queue.
- `push(source)`: adds item `source` to the back of the queue.
- `void pop()`: removes (but does not return) the element at the front of the queue.

Note that the queue does not support iterators or a subscript operator. The only elements that can be accessed are its front and back element, and a queue can only be emptied by repeatedly removing its front element.

### 7.2.4: The `priority_queue' container

The `priority_queue` class implements a priority queue datastructure. To use the priority queue, the header file `queue` must be included:

        #include <queue>

A priority queue is identical to a `queue`, but allows the entry of data elements according to priority rules. An example of a situation where the priority queue is encountered in real-life is found at the check-in terminals at airports. At a terminal the passengers normally stand in line to wait for their turn to check in, but late passengers are usually allowed to jump the queue: they receive a higher priority than the other passengers.

The priority queue uses the `<`-operator of the used data type to decide about the priority of the data elements. The smaller the value, the lower the priority. So, the priority queue could also be used for sorting values while they arrive.

A simple example of a priority queue application is the following program: it reads words from `cin` and writes a sorted list of words to `cout`:

    #include <iostream>
    #include <string>
    #include <queue>

    int main()
    {
        priority_queue<string>
            q;

        string
            word;

        while (cin >> word)
            q.push(word);

        while (q.size())
        {
            cout << q.top() << endl;
            q.pop();
        }

        return (0);
    }

Unfortunately, the words are listed in reversed order: because of the underlying `<`-operator the words appearing later in the ascii-sequence appear first in the priority queue. A solution for that problem is to define a wrapper class around the `string` datatype, in which the `<`-operator has been defined according to our wish, i.e., making sure that the words appearing early in the ascii-sequence appear first in the queue. Here is the modified program:

    #include <iostream>
    #include <string>
    #include <queue>

    class Text
    {
        public:
            Text(string const &str): s(str)
            {}
            operator string const &() const
            {
                return (s);
            }
            bool operator<(Text const &right) const
            {
                return (s > right.s);
            }
        private:
            string
                s;
    };

    ostream &operator<<(ostream &ostr, Text const &text)
    {
        return (ostr << text);
    }

    int main()
    {
        priority_queue<Text>
            q;
        string
            word;

        while (cin >> word)
            q.push(word);

        while (q.size())
        {
            word = q.top();
            cout << word << endl;
            q.pop();
        }
        return (0);
    }

In the above program the wrapper class defines the `operator<` just the other way around than the `string` class itself, resulting in the preferred ordering. Other possibilities would be to store the contents of the priority queue in, e.g., a vector, from which the elements can be read in reversed order. However, the example shows how the priority queue can be fed objects of a special class, in which the `operator<` has been tailored to a particular use.

A priority queue can be initialized by an existing other priority queue, or it can be created empty:

        priority_queue<int>
            priority_queue1;
        ...
        priority_queue<int>
            priority_queue2(priority_queue1);

Apart from these constructors, and the basic operators for comparison and assignment (see the introductory paragraph of this chapter), the following memberfunctions are available:

- `empty()`,
- `size()`,
- `top()`: returns the first element that would be removed by `pop()`. This element is not removed from the priority queue, and could be given a new value, as in:

          priority_queue<string>
              pq;
          ...
          pq.top() = "Hello world";

- `push(argument)`: adds item `argument` to its appropriate position, respecting its priority.

Note that the priority queue does not support iterators or a subscript operator. The only element that can be accessed is its top element, and it can only be emptied by repeatedly removing this element.

### 7.2.5: The `deque' container

The `deque` class implements a double ended queue (deque) datastructure. To use the `deque` class, the header file `deque` must be included:

        #include <deque>

A deque is comparable to a queue, but it allows reading and writing at both ends of the queue. Actually, the `deque` data type supports a lot more functionality than the `queue`, as will be clear from the following overview of memberfunctions that are available for the `deque`:

First, several constructors are available for the `deque`:

- `deque()` initializes an empty deque.
- `deque(argument)` initializes a deque with another deque `argument`.
- `deque(n, argument)` initializes a deque with `n` values provided by the `argument` variable. E.g., to initialize a deque with 10 strings containing `Hello World` we do:

          deque<string>
              hello(10, "Hello World");

- `deque(size_type n)` initializes a deque with `n` default values of the datatype stored in the deque.
- `deque(iterator first, iterator last)` initializes the deque with the iterator range implied by `[first, last)`. The iterators `first` and `last` may also be pointers to the data-type stored in the deque.

To access the individual elements of the deque, the following members are available:

- `begin()`: this returns the iterator pointing to the front-element
- `end()`: the iterator beyond the back-element.
- `rbegin()`: the iterator pointing to the last (back) element
- `rend()`: and the corresponding one pointing just before the first (front) element.
- The subscript operator may be used to access random elements from the deque.
- `front()`: returns the element at the front of the deque. This member may be used for reassigning the front element as well.
- `back()`: and the element at the back of the deque. Again, reassignment is possible.
- `size()`, returning the number of elements in the deque.
- `empty()`, returns `true` if the deque contains no elements.

The following operations and operator affect all elements of a deque:

- The assignment operator (`=`) may be used to assign one deque object to another.
- `swap(argument)` is used to swap the contents of the current deque with deque `argument`.

Elements may be added and removed from both ends of a deque:

- `push_back(source)` adds `source` at the back of the deque,
- `push_front(source)` adds `source` at the front of the deque.
- `pop_back()` removes (but does not return) the element at the back of the deque.
- `pop_front()` removes (but does not return) the element at the front of the deque.

Elements may also inserted somewhere within the deque:

- `insert(position, argument)`: `argument` is inserted at the position indicated by the `position` iterator, which is itself returned by the function. `Argument` may be omitted, in which case the default value of the data-type used with the deque is inserted.
- `insert(pos, n, argument)`: At the position indicated by the `pos` iterator `n` new elements are inserted, all having value `argument`. There is no returnvalue.
- `insert(pos, first, last)`: At the position indicated by the `pos` iterator the elements implied by the iterator range `[first, last)` are inserted. There is no returnvalue.
- `resize(new_size, argument)`: the size of the deque is altered to `new_size`. If `new_size` exceeds `size()`, then the new elements are initialized to `argument`. If `argument` is omitted, the default value of the data type of the deque is used. If `new_size` is less than `size()`, then the size of the deque is merely reduced.

Apart from using `resize()`, elements may be removed from the deque as follows:

- `erase(pos)` erases all elements of the deque from the position indicated by the iterator `pos` to the end of the deque.
- `erase(first, last)` erases all elements implied by the iterator range `[first, last)`.
- `clear()` erases all elements from the deque.

### 7.2.6: The `map' container

The `map` class implements a (sorted) associative array. To use the `map`, the header file `map` must be included:

        #include <map>

A `map` is filled with Key/Value pairs, which may be of any container-acceptable type.

The key is used for looking up the information belonging to the key. The associated information is the Value. For example, a phonebook uses the names of people as the key, and uses the telephone number and maybe other information (e.g., the zip-code, the address, the profession) as the value.

Basically, the operations on a `map` are the storage of Key/Value combinations, and looking for a value, given a key. Each key can be stored only once in a `map`. If the same key is entered twice, the last entered key/value pair is stored, and the pair that was entered before is lost.

A single value that must be entered into a `map` must be constructed first. For this, every `map` defines a `value_type` which may be used to create values of that type. For example, a value for a `map<string, int>` can be constructed as follows:

        map<string, int>::value_type(string("Hello"), 1)

The `value_type` is associated with the `map<string, int>` map. Its leftmost argument defines the key, its rightmost argument defines its value.

Instead of using the line `map<string, string>::value_type(...)` over and over again, a `typedef` comes in handy:

        typedef map<string, int>::value_type MapStrIntValue

Using this typedef, values for the `map<string, int>` may be constructed as

        MapStrIntValue(string("Hello"), 1);

Apart from the basic operations (assignment, comparison, etc,), the `map` supports several more operations:

- The constructor defining an empty `map`. The types of the Key and Value must be specified when the `map` is defined. E.g., to define a `map` in which the key is a `string` and the value an `int`, use:

          map<string, int>
              object;

  To define a map in which the key is a `string` and the value is a pair of strings, use:

          map<string, pair<string, string> >
              object;

  Note the white space between the two closing angular brackets `>`: this is obligatory, as the immediate concatenation of the two angular brackets will be interpreted by the compiler as a rightshift operator (`>>`), which is not what you want here.
- `object(iterator first, iterator last)`: This constructor defines a `map` that is initialized by the values implied by the iterator range `[first, last)`. The range could be defined by pointers in an array of Key/Value pairs. For example (see section 7.1 for a discussion of the `pair` container):

          pair<string, int>
              pa[] = {
                  pair<string,int>("one", 1),
                  pair<string,int>("two", 2),
                  pair<string,int>("three", 3),
              };

          map<string, int>
              object(&pa[0], &pa[3]);

  Note that `&pa[3]`, as with the iterators, points to the first element that must not be included in the `map`. The particular array element does not have to exist.

  Also note that key/value pairs are only entered if the corresponding key has not yet been entered. If the last element of `pa` would have been `"one", 3`, only two elements would have entered the `map`: `"one", 1` and `"two", 2`. The value `"one", 3` would have been ignored silently.

  Finally, it is worth noting that the `map` receives its own copies of the data to which the iterators point. The following example illustrates this:

      #include <iostream>
      #include <string>
      #include <utility>
      #include <map>

      class MyClass
      {
          public:
              MyClass()
              {
                  cout << "MyClass constructor called\n";
              }
              MyClass(const MyClass &other)
              {
                  cout << "MyClass copy constructor called\n";
              }
              ~MyClass()
              {
                  cout << "MyClass destructor called\n";
              }
      };

      int main()
      {
          pair<string, MyClass>
              pairs[] =
              {
                  pair<string, MyClass>("one", MyClass()),
              };

          cout << "pairs constructed\n";

          map<string, MyClass>
              mapsm(&pairs[0], &pairs[1]);

          cout << "mapsm constructed\n";

          return (0);
      }

  First, the constructors of a `MyClass` object is called to initialize the first element of the array `pairs`. This object is copied into the first element of the array `pairs` by calling the copy constructor. Next, the original element is not needed anymore, and gets destroyed. At that point the array `pairs` is constructed. Next, the `map` constructs a temporary `pair` object, from which the map element is constructed. Having constructed the map element, the temporary `pair` objects is destroyed. Eventually, when the program terminates, the `pair` element stored in the `map` is destroyed too.

  When run, the program produces the following output:

          MyClass constructor called
          MyClass copy constructor called
          MyClass destructor called
          pairs constructed
          MyClass copy constructor called
          MyClass copy constructor called
          MyClass destructor called
          mapsm constructed
          MyClass destructor called

- `object(argument)`: This constructor initializes `object` with an existing map `argument` having the same key/value combinations.

The standard iterators are also available:

- `begin()`
- `end()`
- `rbegin()`
- `rend()`

Other member functions of the `map` are:

- `empty()`,
- `size()`,
- `swap()`,
- The subscript operator (`[]`), which may be used to access and redefine values. Here, the argument of the subscript operator is the keyvalue. If the provided key is not available in the `map`, a new data element is added to the `map`, using the default value or default constructor to initialize the value part of the newly added key/value combination. This default value is then returned.

  When initializing a new or reassigning another element of the map, the right-hand side of the assignment operator must have the type of the value part of the map. E.g., to add another element `"two"` to the map that was defined in the previous example, use the following construction:

          mapsm["two"] = MyClass();

- `insert(argument)` is used to insert a new value `argument` in the map. The returnvalue is a `pair<iterator,bool>`. The `bool` field indicates whether `source` was inserted (`true` is returned) or not (in which case the `key` field of `source` was already available). In both cases the iterator field points to the data-element in the `map`: a new element if `true` is returned, the existing element if `false` is returned. The following little program illustrates this:

      #include <string>
      #include <map>
      #include <iostream>

      int main()
      {
          pair<string, int>
              pa[] = {
                  pair<string,int>("one", 1),
                  pair<string,int>("two", 2),
                  pair<string,int>("three", 3),
              };

          map<string, int>
              xmap(&pa[0], &pa[3]);

                                  // {four, 4} and true (1) is returned  here
          pair<map<string, int>::iterator, bool>
              ret = xmap.insert(map<string, int>::value_type("four", 4));

          cout << ret.first->first << " " << ret.first->second << " " <<
                  ret.second << " " << xmap["four"] << endl;

                                  // {four, 4} and false (0) is returned  here
          ret = xmap.insert(map<string, int>::value_type("four", 0));

          cout << ret.first->first << " " << ret.first->second << " " <<
                  ret.second << " " << xmap["four"] << endl;

          return (0);
      }

  Note the somewhat peculiar constructions like

          cout << ret.first->first << " " << ret.first->second << ...

  Here `ret` is the `pair` variable returned by the `insert` member function. Its `first` field is an iterator into the t(map<string, int>), so it can be considered a pointer to a `map<string, int>` value type. These value types themselves are pairs too, having `first` and `second` fields. Consequently, `ret.first->first` is the key field of the map value (a `string`), and `ret.first->second` is the value field (an `int`).
- `insert(position, argument)`. This is another way to insert a value, this time using a specific position within the `map`. `Position` is an `map<keytype, valuetype>::iterator`. Although a specific position is given, the new element is inserted at its appropriate sorted location within the `map`, so `mapVariable.begin()` could be used for the `position`.
- `insert(first, last)`: this memberfunction may be used to insert a range of elements implied by the iterator range `[first, last)` into the `map`. Again, elements are only inserted if their keys are not yet in the `map`, and the `map` remains sorted by key values. Instead of iterators pointers to elements of the same value type as stored in the `map` may be used.
- `erase(position)`: erases the element at the indicated position, which is an iterator of the particular map.
- `erase(key)`: erases the element having `key` as its key value.
- `erase(first, last)`: erases the range of elements implied by the iterator range `[first, last)`.
- `clear()`: erases all elements from the `map`.
- `find(key)`: an iterator is returned pointing to the element whose key is `key`. If the element isn't available, the iterator `end()` is returned. The following example illustrates the use of the `find()` memberfunction:

      #include <iostream>
      #include <string>
      #include <utility>
      #include <map>

      int main()
      {
          map<string, int>
              mapsi;

          mapsi["one"] = 1;

          map<string, int>::iterator
              it = mapsi.find("one");

          cout << "\"one\" " <<
                  (it == mapsi.end() ? "not " : "") <<
                  "found\n";

          it = mapsi.find("three");

          cout << "\"three\" " <<
                  (it == mapsi.end() ? "not " : "") <<
                  "found\n";

          return (0);
      }

The following members have special meanings with the multimap, but they are defined with the plain `map` too:

- `count(key)`: returns 1 if the provided key is available in the `map`, otherwise 0 is returned.
- `lower_bound(key)`: returns an iterator pointing to the first element having a key equal to or exceeding the key value that is passed to the memberfunction. If no such value exists, `target.end()` is returned.
- `upper_bound(key_type key)`: same as the previous function.
- `equal_range(key_type key)`: a `pair<iterator,iterator>` is returned. In the case of a `map`, the range consists of the data element having as its key the key value that is passed to the function. If no such data element could be found, the pair `(end(), end())` is returned.

### 7.2.7: The `multimap' container

Like the `map`, the `multimap` class implements also a (sorted) associative array. To use the `multimap`, the header file `multimap` must be included:

        #include <multimap>

The main difference between the `map` and the `multimap` is that the multimap supports multiple entries of the same key, whereas the `map` contains only unique keys. Note that multiple entries of the same key and the same value are also accepted.

The functions that are available with the multimap and the map are practically the same, with the exception of the subscript operator (`[]`), which is not supported with the multimap. This is understandable: if multiple entries of the same key are allowed, which of the possible values should be returned for `myMap[myKey]`?

Below the available constructors and memberfunctions are mentioned. They are presented without further comment if their function is identical to that of the `map` container.

A single value that is to be entered into a multimap must be constructed. For this, a multimap defines a `value_type`, corresponding to a particular multimap type, which may be used to create values of that type. For example, with a `multimap<string, string>` it can be used as follows:

        multimap<string, string>::value_type(string("Hello"), 1)

Here are the constructors that are available for the multimap:

- The constructor defining an empty multimap. E.g.,

          multimap<string, int>
              object;

- `object(first, last)`: This constructor defines a multimap that is initialized by the values implied by the iterator range `[first, last)`.
- `object(argument)`: This constructor initializes `object` with an existing multimap.

The standard iterator producing member functions are available:

- `begin()`
- `end()`
- `rbegin()`
- `rend()`

Other available memberfunctions are:

- `empty()`
- `size()`
- `swap()`
- `insert(argument)` is used to insert a new value `argument` in the multimap. The returnvalue is an iterator (and not a `pair<iterator,bool>` as with the map container), pointing to the newly added element.
- `insert(position, argument)`.
- `insert(first, last)`.
- `erase(position)`.
- `erase(key)`.
- `erase(first, last)`.
- `clear()`.
- `find(key)`: an iterator is returned pointing to the (first) element whose key is `key`. If the element isn't available, `target.end()` is returned.
- `count(key)`: returns the number of times the provided key is available in the multimap.
- `lower_bound(key)`: returns an iterator pointing to the first of a series of data element having the same keys of which the value is equal to or exceeds the key value that is passed to the memberfunction. If no such value exists, the behavior of the function is undefined.
- `upper_bound(key)`: returns an iterator pointing to the last of a series of data element having the same keys of which the value is equal to or exceeds the key value that is passed to the memberfunction. If no such value exists, the behavior of the function is undefined.
- `equal_range(key)`: a `pair<iterator,iterator>` is returned, defining the range of data elements all having key value `key`. If no such data element could be found, the pair `(end(), end())` is returned.

The subscript operator is not available.

### 7.2.8: The `set' container

The `set` class implements a set of (sorted) values. To use the `set`, the header file `set` must be included:

        #include <set>

A set is filled with values, which may be of any container-acceptable type. Each value can be stored only once in a set.

A single value that is to be entered in a set must be constructed. For this, a set defines a `value_type`, corresponding to a particular type of set, which may be used to create values of that type. For example, with a `set<string>` it can be used as follows:

        set<string>::value_type(string("Hello"))

Instead of using the line `set<string>::value_type(...)` over and over again, a `typedef` may come in handy here:

        typedef set<string>::value_type SetSValue

Using this typedef, values for the `set<string, string>` may be constructed as follows:

        SetSValue(string("Hello"))

Apart from the basic operations (assignment, comparison, etc,), the `set` supports several more operations. They are:

- The constructor defining an empty set. When the set is defined, the type of the value must be specified. E.g., to define a set in which `int`s can be stored, use:

          set<int>
              object;

- `object(iterator first, iterator last)`: This constructor defines a set that is initialized by the values implied by the iterator range `[first, last)`. The range may also be defined by pointers in an array of values of the same type as the values that must be stored in the set. For example:

          int
              ia[] = {1, 2, 3, 4, 5};

          set<int>
              object(&ia[0], &ia[5]);

  Note that `&pa[5]` points to the first element that must not be included in the set. Also note that all values values in the set will be different: it is not possible to store the same value more than once.
- `object(argument)`: This constructor initializes `object` with an existing set `argument`, constructing a copy of the set `argument`.

The standard iterators are all available:

- `begin()`
- `end()`
- `rbegin()`
- `rend()`

Other member functions are:

- `empty()`,
- `size()`,
- `swap(argument)`, swapping the contents of the current set and the set `argument`.
- `insert(argument)` is used to insert a new value `argument` in the set. `Argument` is a value of the appropriate value type of the set. The returnvalue is a `pair<iterator, bool>`. The `bool` field indicates whether `source` was inserted (`true` is returned) or not (in which case the `key` field of `source` was already available). In both cases the iterator field points to the data-element in the set: a new element if `true` is returned, the existing element if `false` is returned. An example using the `insert()` memberfunction is given below:

      #include <set>
      #include <utility>

      int main()
      {
          set<int>
              object;

          pair<set<int>::iterator, bool>
              result = object.insert(set<int>::value_type(4));

          cout << "Element " << *result.first << " was " <<
              (result.second ? "" : "not ") << "inserted\n";

          result = object.insert(set<int>::value_type(4));

          cout << "Element " << *result.first << " was " <<
              (result.second ? "" : "not ") << "inserted\n";

          return (0);
      }

- `insert(position, argument)`. This is another way to insert a value `argument`, this time using a specific position within the set, indicated by `set<type>::iterator position`. Although a specific position is given, the new element is inserted at its appropriate sorted location within the set. An insertion could therefore be realized using a statement like

          object.insert(object.begin(), set<int>::value_type(1));

- `insert(first, last)`: this memberfunction may be used to insert a range of elements implied by the iterator range `[first, last)` into the set. Again, elements are only inserted if their keys are not yet in the set, and the set remains sorted. Instead of iterators pointers to elements of the same value type as stored in the set may be used.
- `erase(position)`: erases the element at the indicated `set<type>::iterator position`.
- `erase(argument)`: erases the element having `argument` as its value.
- `erase(first, last)`: erases the range of elements implied by the iterator range `[first, last)`.
- `clear()`: erases all elements from the set.
- `find(argument)`: an iterator is returned pointing to the element whose value is `argument`. If the element isn't available, `object.end()` is returned.

The following members have special meanings with the multiset, but they are defined with the plain set too:

- `count(argument)`: returns 1 if the provided value is available in the set, otherwise 0 is returned.
- `lower_bound(argument)`: returns an iterator pointing to the (first) data element having a value which is equal to or exceeds the value that is passed to the memberfunction. If no such value exists, the behavior of the function is undefined.
- `upper_bound(argument)`: same as the previous function.
- `equal_range(argument)`: a `pair<set<type>::iterator, set<type>::iterator>` is returned. In the case of a set, the range consists of a pair of iterators of which the first iterator points to the element of the set containing the value `argument`, while the second iterator points beyond that elementand (or to `end()` if the first iterator points to the last element in the set). If the set does not contain a data element having value `argument` the pair `(end(), end())` is returned.

### 7.2.9: The `multiset' container

Like the `set`, the `multiset` class also implements a (sorted) set of values. To use the `multiset`, the header file `multiset` must be included:

        #include <multiset>

The main difference between the `set` and the `multiset` is that the multiset supports multiple entries of the same value, whereas the `set` contains only unique values.

The member functions that are available for the set are also available for the multiset. They are presented below without further comment if their functions and parameters are comparable to those used by the `set` container's members.

A single value that is to be entered into a multiset must be constructed. For this, a multiset defines a `value_type`, corresponding to a particular multiset type, which may be used to create values of that type. For example, with a `multiset<string>` it can be used as follows:

        multiset<string>::value_type(string("Hello"))

Here are the constructors that are available for the multiset:

- The constructor defining an empty multiset. E.g.,

          multiset<string>
              object;

- `object(first, last)`: This constructor defines a multiset that is initialized by the values implied by the iterator range `[first, last)`.
- `object(argument)`: This constructor initializes `object` with an existing multiset `argument`, creating a copy of that multiset.

The standard iterators:

- `begin()`
- `end()`
- `rbegin()`
- `rend()`

Other member functions are:

- `empty()`,
- `size()`,
- `swap(argument)`, `argument` is an existing multiset.
- `insert(argument)` is used to insert a new value `multiset<type>::value_type(argument)` into the multiset. The returnvalue is an iterator (and not a `pair<iterator, bool>` as with the set container), pointing to the newly added element.
- `insert(position, argument)`. `Position` is an iterator of the multiset, and `argument` is a value for the multiset.
- `insert(first, last)`, inserting values defined by the iterator range `rangett(first, last)`.
- `erase(position)`,
- `erase(argument)`,
- `erase(first, last)`,
- `clear()`.
- `find(argument)`: an iterator is returned pointing to the (first) element whose value is `argument`. If the element isn't available, `object.end()` is returned.
- `count(argument)`: returns the number of times the provided value `argument` is available in the multiset.
- `lower_bound(argument)`: returns an iterator pointing to the first of a series of data element having values which are equal to or exceed the value `argument` that is passed to the memberfunction. If no such value exists, the behavior of the function is undefined.
- `upper_bound(value)`: returns an iterator pointing to the last of a series of data element having values which are equal to or exceed the value `argument` that is passed to the memberfunction. If no such value exists, the behavior of the function is undefined.
- `equal_range(argument)`: a `pair<iterator, iterator>` is returned, defining the range of data elements all having the value `argument`. If no such elements could be found, the pair `(end(), end())` is returned.

A small example showing the use of various memberfunctions of a multiset is given below:

        #include <string>
        #include <set>
        #include <iostream>

        int main()
        {
            string
                sa[] =
                {
                    "alfa",
                    "echo",
                    "hotel",
                    "mike",
                    "romeo"
                };

            multiset<string>
                xset(&sa[0], &sa[5]);

            xset.insert(multiset<string> ::value_type("echo"));
            xset.insert(multiset<string> ::value_type("echo"));
            xset.insert(multiset<string> ::value_type("echo"));

            multiset<string>::iterator
                it = xset.find("echo");

            for (; it != xset.end(); ++it)
                cout << *it << " ";
            cout << endl;

            pair
            <
                multiset<string>::iterator,
                multiset<string>::iterator
            >
                itpair = xset.equal_range("echo");

            for (; itpair.first != itpair.second; ++itpair.first)
                cout << *itpair.first << " ";

            cout << endl <<
                    xset.count("echo") << " occurrences of 'echo'" << endl;

            return (0);
        }

### 7.2.10: The `stack' container

The `stack` class implements a stack datastructure. To use the `stack`, the header file `stack` must be included:

        #include <stack>

A stack is also called a first-in last-out datastructure, as the first item to enter the stack is the last item that will be removed from it. A stack is an extremely useful datastructure in situations where data must be temporarily be available. For example, programs maintain a stack to store local variables of functions: these variables live only as long as the functions live, contrary to global (or static local) variables, which live for as long as the program itself lives. Another example is found in calculators using the Reverse Polish Notation (RPN), in which the operands of expressions are entered in the stack, and the operators pop their operands and push the results of their work.

As an example of the use of a stack, consider figure 9, in which the contents of the stack is shown while the expression `(3 + 4) * 2` is evaluated. In the RPN this expression becomes `3 4 + 2 *`, and figure 9 shows the stack contents after each token (i.e., the operands and the operators) is read from the input. Notice that indeed each operand is pushed on the stack, while each operator changes the contents of the stack.

figure 9: The contents of a stack while evaluating `3 4 + 2 *`

The expression is evaluated in five steps. The caret between the tokens in the expressions shown on the first line of figure 9 shows what token has just been read. The next line shows the actual stack-contents, and the final line shows the steps for referential purposes. Note that at step 2, two numbers have been pushed on the stack. The first number (`3`) is now at the bottom of the stack. Next, in step 3, the `+` operator is read. The operator pops two operands (so that the stack is empty at that moment), calculates their sum, and pushes the resulting value (`7`) on the stack. Then, in step 4, the number `2` is read, which is dutifully pushed on the stack again. Finally, in step 5 the final operator `*` is read, which pops the values `2` and `7` from the stack, computes their product, and pushes the result back on the stack. This result (`14`) could then be popped to be displayed on some medium.

From figure 9 we see that a stack has one point (the top) where items can be added to and removed from the stack. Furthermore, values can be pushed and popped from a stack.

Bearing this model of the stack in mind, let's see what we can formally do with it, using the `stack` container.

A stack can be initialized by an existing other stack, or it can be created empty:

        stack<int>
            stack1;
        ...
        stack<int>
            stack2(stack1);

Apart from these constructors, and the basic operators for comparison and assignment (see the introductory paragraph of this chapter), the following memberfunctions are available:

- `empty()`,
- `size()`,
- `top()`: returns the first element that would be removed by `pop()`. Using `top()` the value at the top of the stack may be inspected or reassigned.
- `push(argument)`: pushes item `argument` on the stack.
- `void pop()`: removes (but does not return) the element at the top of the stack.

Note that the stack does not support iterators or a subscript operator. The only elements that can be accessed is its top element, and it can only be emptied by repeatedly popping the element at the top.

### 7.2.11: The `hash_map' and other hashing-based containers

The `(multi) map` and `(multi) set` containertypes store sorted keys. This is in general not the fastest way to store keys with respect to storage and retrieval. The main benefit of sorted keys is that a listing of sorted keys appeals more to humans than an unsorted list. However, a by far faster method of storing keys is to use hashing.

Hashing uses a function (called the hash-function) to compute a (unsigned) number from the key, which number is thereupon used as an index in the table in which the keys are stored. Retrieval of a key is as simple as computing the hashvalue of the provided key, and looking at the table in the computed indexlocation: if the key is present, it is stored in the table, and its value can be returned. If it's not present, the key is not stored.

Boundary conditions arise when a computed index position is already occupied by another element. For these situations the abstract containers have solutions available, but that topic is beyond the subject of this chapter.

The egcs compiler supports the hash_(multi)map and `hash_(multi)set` containers. Below the `hash_map` container is illustrated. The other containers using hashing (`hash_multimap, hash_set` and `hash_multiset`) operate correspondingly.

Concentrating on the `hash_map`, its constructor needs a key-type, a value-type, an object creating a hashvalue for the key, and an object comparing two keys for equality.

The `hash_map` class implements an associative array in which the key is stored according to some hashing scheme. To use the `hash_map`, the header file `hash_map` must be included:

        #include <hash_map>

Hash functions are available for `char const *` keys, and for all the scalar numerical types `char, short, int` etc.. If another datatype must be used, a hash function and an equality test must be implemented, possibly using function objects (see section 6.8). For both situations examples are given below.

The class implementing the hash-function could be called `hash`. Its function-call operator returns the hashvalue of the key which is passed as its argument.

A generic algorithm (see section 10) exists for the test of equality (i.e., `equal_to()`), which can be used if the key's data type supports the equality operator. Alternatively, a function object could also be constructed here, supporting the equality test of two keys. Again, both situations are illustrated below.

In the first example a `hash_map` is defined for a `string, int` combination using existing template functions.

The test for equality is implemented using an instantiation of the `equal_to` generic algorithm. The hash function uses a template specialization for the `hash` template class. The how and why of template specializations are covered in chapter 16.

The `hash<string>` explicit specialization in fact uses the predefined `hash<char const *>` template, but the roundabout way is chosen here to illustrate how a template explicit specialization can be constructed. Here it is:

        template <>
        class hash<string>
        {
            public:
                size_t operator()(string const &str) const
                {
                    hash<char const *>
                        h;

                    return (h(str.c_str()));
                }
        };

The following program defines a map containing the names of the months of the year and the number of days these months (usually) have. Then, using the subscript operator the days in several months are displayed. The equality operator used the generic algorithm `equal_to<string>`, which is the default fourth argument of the `hash_map` constructor:

        #include <iostream>
        #include <string>
        #include <hash_map>

        template <> class hash<string>; // insert the above mentioned template
                                        // here

        int main()
        {
            hash_map<string, int, hash<string> >
                months;

            months["january"] = 31;
            months["february"] = 28;
            months["march"] = 31;
            months["april"] = 30;
            months["may"] = 31;
            months["june"] = 30;
            months["july"] = 31;
            months["august"] = 31;
            months["september"] = 30;
            months["october"] = 31;
            months["november"] = 30;
            months["december"] = 31;

            cout << "september -> " << months["september"] << endl <<
                    "april     -> " << months["april"] << endl <<
                    "june      -> " << months["june"] << endl <<
                    "november  -> " << months["november"] << endl;

            return (0);
        }

Note that the definition `hash_map<string, int, hash<string> > months;` may be written simpler if the key is a `char const *`: `hash_map<char const *, int> months;`

The next example shows an alternative implementation, using function objects. The class `Equal` defines the equality test of two keys in its function call operator `operator()`, and a `Equal` object is now explicitly mentioned when the `hash_map` is constructed. Similarly, the `hashString` class defines the hash function of the key. A `hashString` object is also passed explicitly to the constructor of the `hash_map`:

        #include <iostream>
        #include <string>
        #include <hash_map>

        class Equal
        {
            public:
                size_t operator()(string const &s1, string const &s2) const
                {
                    return (s1 == s2);
                }
        };

        class hashString
        {
            public:
                size_t operator()(string const &str) const
                {
                    hash<char const *>
                        h;

                    return (h(str.c_str()));
                }
        };

        int main()
        {
            hash_map
            <
                string,
                int,
                hashString,
                Equal
            >
                months;

            months["january"] = 31;
            months["february"] = 28;
            months["march"] = 31;
            months["april"] = 30;
            months["may"] = 31;
            months["june"] = 30;
            months["july"] = 31;
            months["august"] = 31;
            months["september"] = 30;
            months["october"] = 31;
            months["november"] = 30;
            months["december"] = 31;

            cout << "february -> " << months["february"] << endl <<
                    "april     -> " << months["april"] << endl <<
                    "june      -> " << months["june"] << endl <<
                    "november  -> " << months["november"] << endl <<
                    "december  -> " << months["december"] << endl;

            return (0);
        }

Like the `map`, a single value that will be entered into a hash_map must be constructed. For this, a `hash_map` defines a `value_type`, corresponding to a particular `hash_map`-type, which may be used to create values of that type. For example, with a `hash_map<string, int>` it can be used as follows:

        hash_map<string, int>::value_type(string("Hello"), 1)

All the memberfunctions and constructors that are available for the `map` datatype can also be used for the `hash_map`. The constructor `object(n)` defines a `hash_map` consisting of an initial number of `n` slots to put key/value combinations in. This number is automatically extended when needed.

The `hash_multimap, hash_set` and `hash_multiset` containers are used analogously. For these containers the `equal` and `hash` classes must also be defined. The `hash_multimap` also requires the `hash_map` header file, the `hash_set` and `hash_multiset` containers can be used after including the `hash_set` header file. Be careful not to use the subscript operator with the `hash_multimap` and `hash_multiset`, as this operator is not defined for the `multi_...` containers.

## 7.3: The `complex' container

The `complex` container is a specialized container in that it defines operations that can be performed on complex numbers, given possible numerical real and imaginary data types.

In order to use the `complex` container, the headerfile

        #include <complex>

must be included.

The `complex` container can be used to define complex numbers, consisting of two parts, representing the real and complex parts of a complex number.

While initializing (or assigning) a complex variable, the imaginary part may be left out of the initialization or assignment, in which case this part is `0` (zero). By default, both parts are zero.

When complex numbers are defined, the typedefinition requires the specification of the datatype of the real and imaginary parts. E.g.,

        complex<double>
        complex<int>
        complex<float>

Note that the real and imaginary parts of complex numbers have the same datatypes.

Below it is silently assumed that the used `complex` type is `complex<double>`. Given this assumption, complex numbers may be initialized as follows:

- `target`: A default initialization: real and imaginary parts are 0.
- `target(1)`: The real part is 1, imaginary part is 0
- `target(0, 3.5)`: The real part is 0, imaginary part is 3.5
- `target(source)`: `target` is initialized with the values of `source`.

Anonymous complex values may also be used. In the following example two anonymous complex values are pushed on a stack of complex numbers, to be popped again thereafter:

    #include <iostream>
    #include <complex>
    #include <stack>

    int main()
    {
        stack<complex<double> >
            cstack;

        cstack.push(complex<double>(3.14, 2.71));
        cstack.push(complex<double>(-3.14, -2.71));

        while (cstack.size())
        {
            cout << cstack.top().real() << ", " <<
                    cstack.top().imag() << "i" << endl;
            cstack.pop();
        }

        return (0);
    }

Note that a blank is required between the two consecutive `>`-barckets used in the definition of `cstack`. If the blank is omitted, the resulting `>>` is read as the right-shift operator, which of course makes no sense here.

The following memberfunctions and operators are defined for complex numbers:

- The standard assignment and comparison operators that are available for containers are also available for complex numbers.
- `real()`: this memberfunction returns the real part of a complex number.
- `imag()`: this memberfunction returns the imaginary part of a complex number.
- The following operations are defined for `complex` containers: `+, -, *, /, +=, -=, *=, /=`.

Furthermore, several mathematical functions are available for complex numbers. They are `abs()`, arg(), conj(), cos(), cosh(), exp(), log(), norm(), polar(), pow(), sin(), sinh()) and `sqrt()`. These functions are normal functions, not memberfunctions. They accept complex numbers as their arguments. For example,

        abs(complex<double>(3, -5));
        pow(target, complex<int>(2, 3));

Complex numbers may be extracted from `istream` objects and inserted into `ostream` objects. The insertion results in an ordered pair `(x, y)`, in which `x` represents the real part and `y` the imaginary part of the complex number. The same form may also be used when extracting a complex number from an `istream` object. However, simpler forms are also allowed. E.g., `1.2345`: only the real part, the imaginary part will be set to 0; `(1.2345)`: the same value.

Finally, ordinary numbers may be used in expressions involving complex numbers. E.g.,

        // assume target is complex<double>:
        target *= 3;

Note, however, that the reverse does not hold true: a complex number cannot be assigned to a non-complex type variable. In these situations the `real(), imag()` or other functions must be used. E.g.:

        // assume x is double:
        x = target;         // error: x is not complex<double>
        x = target.real();  // ok.

- Next chapter
- Previous chapter
- Table of contents