Chapter 12: 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. Send your email to Frank Brokken.

Please state the document version you're referring to, as found in the title (in this document: 5.1.0d) and please state the paragraph you're referring to.

All mail received is seriously considered, and new (sub)releases of the Annotations will normally reflect your suggestions for improvements. Except for the incidental case I will not otherwise acknowledge the receipt of suggestions for improvements. Please don't misinterpret this for lack of appreciation.

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

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

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

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

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

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

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

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

All abstract containers described in this chapter and the string datatype discussed in chapter 4 are part of the Standard Template Library. There also exists an abstract container for the implementation of a hashtable, but that container is not (yet) accepted by the ANSI/ISO standard. Nevertheless, the final section of this chapter will cover the hashtable to some extent. It may be expected that containers like hash_map and other, now still considered an extension, will become part of the ANSO/ISO standard at the next release: apparently by the time the standard was frozen these containers were not yet fully available. Now that they are available they cannot be official part of the C++ library , but they are in fact available, albeit as extensions.

All containers support the following operators:

  • The overloaded assignment operator, so we can assign two containers of the same type to each other.
  • Tests for equality: == 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.
  • Ordering operators: <, <=, > and >=. The < operator returns true if each element in the left-hand container is less than each corresponding element in the right-hand container. If the right-hand container has more elements than the left-hand container, they are ignored. Other ordering operators perform analogously.
  • Note that before a user-defined type (usually a class-type) can be stored in a container, the user-defined type should at least 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 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 normally have constructors and members expecting iterators for their arguments, and they often 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 17 for a discussion of iterators.

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

    Containers often collect data during their lifetime. When a container goes out of scope, its destructor tries to destroy its data elements. This only succeeds if the data elements themselves are stored inside the container. If the data elements of containers are pointers, the data to which these pointers point will not be destroyed, and a memory leak will result. A consequence of this scheme is that the data stored in a container should be considered the ` property' of the container: the container should be able to destroy its data elements when the destructor of the container is called. Consequently, in normal circumstances the container should contain no pointer data. Also, a container should not be required to contain const data, as for const data the, e.g., operator=() doesn't work.

    Below, at the descriptions of the containers, the following notational convention is used:

  • A container without angular brackets represents any container of that type. Mentally add the required type in angular bracket notation. E.g., pair may represent pair<string, int>.
  • The notation Type represents the generic type. Type could be int, string, etc.
  • Identifiers object and container represent objects of the container type under discussion.
  • The identifier value represents a value of the type that is stored in the container.
  • Simple, one-letter identifiers, like n represent unsigned values.
  • Longer identifiers represent iterators. Examples are pos, from, beyond
  • Some containers, e.g., the map container, contain combinations of values, usually called `keys' and `values'. For such containers the following natational convention is used in addition:
  • The identifier key indicates a value of the used key-tpye
  • The identifier keyvalue indicates a value of the `value_type' used with the particular container.
  • 12.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 pair container, source files should
        #include <utility>
    
    The data types of a pair are defined when the pair variable is defined, using the standard template (see chapter Templates) angular bracket notation:
        pair<string, string>
            piper("PA28", "PH-ANI"),
            cessna("C172", "PH-ANG");
    
    here, the variables piper and cessna are defined as pair variables containing two strings. Both strings can be retrieved using the first and second fields of the pair type:
        cout << piper.first << endl <<      // shows 'PA28'
                cessna.second << endl;      // shows 'PH-ANG'
    
    The first and second members can also be used to reassign values:
        cessna.first = "C152";
        cessna.second = "PH-ANW";
    
    If a pair object must be completely reassigned, an anonymous pair object can be used as the right-hand side operand of the assignment. An anonymous variable defines a temporary variable (which receives no name) solely for the purpose of (re)assigning another variable of the same type. Its generic form is
        type(initializer list)
    
    Note that when a pair object is used the type specification is not completed by just mentioning the containername pair. It also requires the specification of the data types which are stored within the pair. For this the (template) angular bracket notation is used again. E.g., the reassignment of the cessna pair variable could have been accomplished as follows:
        cessna = pair<string, string>("C152", "PH-ANW");
    
    In cases like these, the type specification can become quite elaborate, which has caused a revival of interest in the possibilities offered by the typedef keyword. If a lot of pair<type1, type2> clauses are used in a source, the typing effort may be reduced and legibility might be improved by first defining a name for the clause, and then using the defined name later. E.g.,
        typedef pair<string, string> pairStrStr;
    
        cessna = pairStrStr("C152", "PH-ANW")
    
    Apart from this (and the basic set of operations (assignment and comparisons)) the pair offers no further functionality. It is, however, a basic ingredient of the upcoming abstract containers map, multimap and hash_map.

    12.2: Sequential Containers

    12.2.1: The `vector' container

    The vector class implements an expandable array. To use the vector, source files should
        #include <vector>
    
    The following constructors, operators, and member functions are available:
  • Constructors:
  • A vector may be constructed empty:
        vector<string>
            object;
    
    Note the specification of the data type to be stored in the vector: the data type is given between angular brackets, just after the `vector' container name. This is common practice with containers.
  • A vector may be initialized to having a certain number of elements. One of the nicer characteristics of vectors (and other containers) is that it initializes its data elements to the data type's default value. The data type's default constructor is used for this initialization. With non-class data types the value 0 is used. So, for the int vector we know its initial values are zero. For example:
        vector<string>
            object(5, string("Hello")), // initialize to 5 Hello's,
            container(10);              // and to 10 empty strings
    
  • A vector may be initialized using a two iterators. To initialize a vector with elements 5 until 10 (including the last one) of a vector<string> the following construction may be used:
        extern vector<string>
            container;
        vector<string>
            object(&container[5], &container[11]);
    
    Note here that the last element pointed to by the second iterator (&container[11]) is not stored in object. This is a simple example of the use of iterators, in which the range of values that is used starts at the first value, and includes all elements up to, but not including the last value mentioned. The standard notation for this is [begin, end).
  • A vector may be initialized using a copy constructor:
        extern vector<string>
            container;
        vector<string>
            object(container);
    
  • Apart from the standard operators for containers, the vector supports the index operator, which may be used to retrieve or reassign individual elements of the vector. Note that the elements which are indexed must exist. For eaample, having defined an empty vector a statement like ivect[0] = 18 produces an error, as the vector is empty. So, the vector is not automatically expanded, and it does respect its array bounds. In this case the vector should be reiszed first, or ivect.push_back(18) should be used (see below).
  • The vector class has the following member functions:
  • Type &vector::back():
    this member returns a reference to the last element in the vector. It is the responsibility of the programmer not to use the member if the vector is empty.
  • vector::iterator vector::begin():
    this member returns an iterator pointing to the first element in the vector.
  • vector::clear():
    this member erases all elements in the vector.
  • bool vector::empty()
    this member returns true if the vector contains no elements.
  • vector::iterator vector::end():
    this member returns an iterator pointing beyond the last element in the vector.
  • vector::iterator vector::erase():
    this member can be used to erase a specific range of elements in the vector:
  • erase(pos) erases the element pointed to by pos. The iterator ++pos is returned.
  • erase(first, beyond) erases elements indicated by the iterator range [first, beyond). Beyond is returned.
  • Type &vector::front():
    this member returns a reference to the first element in the vector. It is the responsibility of the programmer not to use the member if the vector is empty.
  • ... vector::insert():
    elements may be inserted starting at a certain position. The return value depends on the version of insert() that is called:
  • vector::iterator insert(pos) inserts a default value of type Type at pos, pos is returned.
  • vector::iterator insert(pos, value) inserts value at pos, pos is returned.
  • void insert(pos, first, beyond) inserts the elements in the iterator range [first, beyond).
  • void insert(pos, n, value) inserts n elements having value value at position pos.
  • void vector::pop_back():
    this member removes the last element from the vector. With an empty vector nothing happens.
  • void vector::push_back(value):
    this member adds value to the end of the vector.
  • void vector::resize():
    this member can be used to alter the number of elements that are currently stored in the vector:
  • resize(n, value) may be used to resize the vector to a size of n. Value is optional. If the vector is expanded and tvalue is not provided, the extra elements are initialized to the default value of the used data type, otherwise the explicitly provided value value is used to initialize extra elements.
  • vector::reverse_iterator vector::rbegin():
    this member returns an iterator pointing to the last element in the vector.
  • vector::reverse_iterator vector::rend():
    this member returns an iterator pointing before the first element in the vector.
  • unsigned vector::size()
    this member returns the number of elements in the vector.
  • void vector::swap()
    this member can be used to swap two vectors. E.g.,
        #include <iostream>
        #include <vector>
    
        int main()
        {
            vector<int>
                v1(7),
                v2(10);
        
            v1.swap(v2);
            cout << v1.size() << " " v2.size() << endl;
        }
        /*
            Produced output:
        10 7
        */
    
  • 12.2.2: The `list' container

    The list container implements a list data structure. To use the list, source files should
        #include <list>
    
    The organization of a list is shown in figure 7.

    figure 7 is shown here.
    figure 7: A list data-structure


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

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

  • When the majority of accesses is random, then the vector is the preferred data structure. E.g., in a program that counts the frequencies of characters in a textfile, a vector<int> frequencies(256) is the datastructure doing the trick, as the values of the received characters can be used as indices into the frequencies vector.
  • 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 or 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.
  • 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 dynamic growth does involve a lot data-copying. Clearly, copying a million large data structures 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 non-involved data. Inserting a new element in a list merely requires us to juggle some pointers. In figure 8 this is shown: a new element is inserted between the second and third element, creating a new list of four elements.

    figure 8 is shown here.
    figure 8: 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 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.

    figure 9 is shown here.
    figure 9: 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 data structure to prefer. There are rules of thumb, which may be adhered to. But if worse comes to worst, a profiler may be required to find out what's working best.

    But, no matter what the thoughts on the subject are, the list container is available, so let's see what we can do with it. The following constructors, operators, and member functions are available:

  • Constructors:
  • A 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.
  • A list may be initialized to having a certain number of elements. By default, if the initialization value is not explicitly mentioned, the default value or default constructor for the actual data type is used. For example:
        list<string>
            object(5, string("Hello")), // initialize to 5 Hello's
            container(10);              // and to 10 empty strings
    
  • A list may be initialized using a two iterators. 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>
            container;
        list<string>
            object(&container[5], &container[11]);
    
  • A list may be initialized using a copy constructor:
        extern list<string>
            container;
        list<string>
            object(container);
    
  • There are no special operators available for the list, apart from the standard operators for containers.
  • The following member functions are available for lists:
  • Type &list::back():
    this member returns a reference to the last element in the list. It is the responsibility of the programmer not to use the member if the list is empty.
  • list::iterator list::begin():
    this member returns an iterator pointing to the first element in the list.
  • list::clear():
    this member erases all elements in the list.
  • bool list::empty():
    this member returns true if the list contains no elements.
  • list::iterator list::end():
    this member returns an iterator pointing beyond the last element in the list.
  • list::iterator list::erase():
    this member can be used to erase a specific range of elements in the list:
  • erase(pos) erases the element pointed to by pos. The iterator ++pos is returned.
  • erase(first, beyond) erases elements indicated by the iterator range [first, beyond). Beyond is returned.
  • Type &list::front():
    this member returns a reference to the first element in the list. It is the responsibility of the programmer not to use the member if the list is empty.
  • ... list::insert():
    this member can be used to insert elements into the list. The return value depends on the version of insert() that is called:
  • list::iterator insert(pos) inserts a default value of type Type at pos, pos is returned.
  • list::iterator insert(pos, value) inserts value at pos, pos is returned.
  • void insert(pos, first, beyond) inserts the elements in the iterator range [first, beyond).
  • void insert(pos, n, value) inserts n elements having value value at position pos.
  • void list<Type>::merge(list<Type> other):
    this member function assumes that the current and other lists are sorted (see below, the member sort()), and will, based on that assumption, insert the elements of other 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() uses Type::operator<() to sort the data in the list, which operator must therefore be available. The next example illustrates the use of the merge() member: the list `object' is not sorted, so the resulting list is ordered 'as much as possible'.
        #include <iostream>
        #include <string>
        #include <list>
        
        void showlist(list<string> &target)
        {
            for 
            (
                list<string>::iterator from = target.begin(); 
                from != target.end(); 
                ++from
            )
                cout << *from << " ";
        
            cout << endl;        
        }
        
        int main()
        {
            list<string>
                first,
                second;
        
            first.push_back(string("alpha"));
            first.push_back(string("bravo"));
            first.push_back(string("golf"));
            first.push_back(string("quebec"));
        
            second.push_back(string("oscar"));
            second.push_back(string("mike"));
            second.push_back(string("november"));
            second.push_back(string("zulu"));
        
            first.merge(second);
            showlist(first);
        }
    
    A subtlety is that merge() 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:
  • resize(n, value) may be used to resize the list to a size of n. Value is optional. If the list is expanded and tvalue is not provided, the extra elements are initialized to the default value of the used data type, otherwise the explicitly provided value value is used to initialize extra elements.
  • list::reverse_iterator list::rbegin():
    this member returns an iterator pointing to the last element in the list.
  • voidlist::remove(value):
    this member removes all occurrences of value from the list. In the following example, the two strings `Hello' are removed from the list object:
        #include <iostream>
        #include <string>
        #include <list>
        
        int main()
        {
            list<string>
                object;
        
            object.push_back(string("Hello"));
            object.push_back(string("World"));
            object.push_back(string("Hello"));
            object.push_back(string("World"));
        
            object.remove(string("Hello"));
        
            while (object.size())
            {
                cout << object.front() << endl;
                object.pop_front();
            }
        }
        /*
                Generated output:
            World
            World
        */
    
  • list::reverse_iterator list::rend():
    this member returns an iterator pointing before the first element in the list.
  • unsigned list::size():
    this member returns the number of elements in the list.
  • void list::reverse():
    this member reverses the order of the elements in the list. The element back() will become front() 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 the unique() member function below. list<Type>::sort() uses Type::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 of value to the current list. Following splice(), value is empty. For example:
    #include <iostream>
    #include <string>
    #include <list>
    
    int main()
    {
        list<string>
            object;
    
        object.push_front(string("Hello"));
        object.push_back(string("World"));
    
        list<string>
            argument(object);
    
        object.splice(++object.begin(), argument);
    
        cout << "Object contains " << object.size() << " elements, " <<
                "Argument contains " << argument.size() << 
                " elements," << endl;
    
        while (object.size())
        {
            cout << object.front() << endl;
            object.pop_front();
        }
    }
    
    Alternatively, value may be followed by a iterator of value, indicating the first element of value that should be spliced, or by two iterators begin and end defining the iterator-range [begin, end) on value that should be spliced into target.
  • void list::swap():
    this member can be used to swap two lists.
  • void list::unique():
    operating on a sorted list, this member function will remove all consecutively identical elements from the list. list<Type>::unique() uses Type::operator==() to identify identical data elements, which operator must therefore be available. Here's an example that removes all doubly occurring words from the list:
        #include <iostream>
        #include <string>
        #include <list>
                                // see the merge() example
        void showlist(list<string> &target);    
        
        int main()
        {
            string
                array[] = 
                {
                    "charley",
                    "alpha",
                    "bravo",
                    "alpha"
                };
                       
            list<string>
                target
                (
                    array, array + sizeof(array) 
                    / sizeof(string)
                );
        
            cout << "Initially we have: " << endl;
    
                        // shows: charley alpha bravo alpha 
            showlist(target);
        
            target.sort();
        
            cout << "After sort() we have: " << endl;
    
                        // shows: alpha alpha bravo charley 
            showlist(target);           
        
            target.unique();
        
            cout << "After unique() we have: " << endl;
    
                        // shows: alpha bravo charley 
            showlist(target);           
        }
    
  • 12.2.3: The `queue' container

    The queue class implements a queue data structure. To use the queue, source files should
        #include <queue>
    
    A queue is depicted in figure 10.

    figure 10 is shown here.
    figure 10: A queue data-structure


    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:

  • Constructors:
  • A queue may be constructed empty:
        queue<string>
            object;
    
    As with the vector, it is an error to refer to an element of an empty queue.
  • A queue may be initialized using a copy constructor:
        extern queue<string>
            container;
        queue<string>
            object(container);
    
  • No other operators than the basic operators for containers are available.
  • The following member functions are available for queues:
  • Type &queue::back():
    this member returns a reference to the last element in the queue. It is the responsibility of the programmer not to use the member if the queue is empty.
  • bool queue::empty():
    this member returns true if the queue contains no elements.
  • Type &queue::front():
    this member returns a reference to the first element in the queue. It is the responsibility of the programmer not to use the member if the queue is empty.
  • void queue::push(value):
    this member adds value to the back of the queue.
  • void queue::pop():
    this member removes the element at the front of the queue. Note that the element is not returned by this member.
  • unsigned queue::size():
    this member returns the number of elements in the queue.
  • 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 (or, of course, by having its destructor called).

    12.2.4: The `priority_queue' container

    The priority_queue class implements a priority queue data structure. To use the priority queue, source files should
        #include <queue>
    
    A priority queue is identical to a queue, but allows the entry of data elements according to priority rules. An example of a situation where the priority queue is encountered in real-life is found at the check-in terminals at airports. At a terminal the passengers normally stand in line to wait for their turn to check in, but late passengers are usually allowed to jump the queue: they receive a higher priority than other passengers.

    The priority queue uses operator<() of the data type stored in the priority ueue to decide about the priority of the data elements. The smaller the value, the lower the priority. So, the priority queue could be used to sort values while they arrive. A simple example of such a priority queue application is the following program: it reads words from cin and writes a sorted list of words to cout:

    #include <iostream>
    #include <string>
    #include <queue>
    
    int main()
    {
        priority_queue<string>
            q;
        string
            word;
    
        while (cin >> word)
            q.push(word);
    
        while (q.size())
        {
            cout << q.top() << endl;
            q.pop();
        }
    }
    
    Unfortunately, the words are listed in reversed order: because of the underlying <-operator the words appearing later in the ASCII-sequence appear first in the priority queue. A solution to that problem is to define a wrapper class around the string datatype, in which the operator<() has been defined according to our wish, i.e., making sure that the words appearing early in the ASCII-sequence will appear first in the queue. Here is the modified program:
    #include <iostream>
    #include <string>
    #include <queue>
    
    class Text
    {
        public:
            Text(string const &str)
            : 
                s(str) 
            {}
            operator string const &() const
            {
                return s;
            }
            bool operator<(Text const &right) const
            {
                return s > right.s;
            }
        private:
            string
                s;
    };
    
    int main()
    {
        priority_queue<Text>
            q;
        string
            word;
        
        while (cin >> word)
            q.push(word);
    
        while (q.size())
        {
            word = q.top();
            cout << word << endl;
            q.pop();
        }
    }
    
    In the above program the wrapper class defines the operator<() just the other way around than the string class itself, resulting in the preferred ordering. Other possibilities would be to store the contents of the priority queue in, e.g., a vector, from which the elements can be read in reversed order.

    The following constructors, operators, and member functions are available for the priority_queue container:

  • Constructors:
  • A 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.
  • A priority queue may be initialized using a copy constructor:
        extern priority_queue<string>
            container;
        priority_queue<string>
            object(container);
    
  • The priority_queue only supports the basic operators of containers.
  • The following member functions are available for priority queues:
  • bool priority_queue::empty():
    this member returns true if the priority queue contains no elements.
  • void priority_queue::push(value):
    this member inserts value at the appropriate position in the priority queue.
  • void priority_queue::pop():
    this member removes the element at the top of the priority queue. Note that the element is not returned by this member.
  • unsigned priority_queue::size():
    this member returns the number of elements in the priority queue.
  • Type &priority_queue::top():
    this member returns a reference to the first element of the priority queue. It is the responsibility of the programmer not to use the member if the priority queue is empty.
  • Note that the priority queue does not support iterators or a subscript operator. The only elements that can be accessed are its top element, and a priority queue can only be emptied by repeatedly removing its top element (or, of course, by having its destructor called).

    12.2.5: The `deque' container

    The deque (pronounce: `deck') class implements a doubly ended queue data structure (deque). To use the deque class, source files should
        #include <deque>
    
    A deque is comparable to a queue, but it allows reading and writing at both ends. Actually, the deque data type supports a lot more functionality than the queue, as will be clear from the following overview of member functions that are available for the deque. A deque is a combination of a vector and two queues, operating at both ends of the vector. In situations where random insertions and the addition and/or removal of elements at one or both sides of the vector occurs frequently, using a deque should be considered.

    The following constructors, operators, and member functions are available for deques:

  • Constructors:
  • A 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.
  • A deque may be initialized to having a certain number of elements. By default, if the initialization value is not explicitly mentioned, the default value or default constructor for the actual data type is used. For example:
        deque<string>
            object(5, string("Hello")), // initialize to 5 Hello's
            container(10);              // and to 10 empty strings
    
  • A deque may be initialized using a two iterators. To initialize a deque with elements 5 until 10 (including the last one) of a vector<string> the following construction may be used:
        extern vector<string>
            container;
        deque<string>
            object(&container[5], &container[11]);
    
  • A deque may be initialized using a copy constructor:
        extern deque<string>
            container;
        deque<string>
            object(container);
    
  • Apart from the standard operators for containers, the deque supports the index operator, which may be used to retrieve or reassign random elements of the deque. Note that the elements which are indexed must exist.
  • The following member functions are available for deques:
  • Type &deque::back():
    this member returns a reference to the last element in the deque. It is the responsibility of the programmer not to use the member if the deque is empty.
  • deque::iterator deque::begin():
    this member returns an iterator pointing to the first element in the deque.
  • deque::clear():
    this member erases all elements in the deque.
  • bool deque::empty():
    this member returns true if the deque contains no elements.
  • deque::iterator deque::end():
    this member returns an iterator pointing beyond the last element in the deque.
  • deque::iterator deque::erase():
    the member can be used to erase a specific range of elements in the deque:
  • erase(pos) erases the element pointed to by pos. The iterator ++pos is returned.
  • erase(first, beyond) erases elements indicated by the iterator range [first, beyond). Beyond is returned.
  • Type &deque::front():
    this member returns a reference to the first element in the deque. It is the responsibility of the programmer not to use the member if the deque is empty.
  • ... deque::insert():
    this member can be used to insert elements starting at a certain position. The return value depends on the version of insert() that is called:
  • deque::iterator insert(pos) inserts a default value of type Type at pos, pos is returned.
  • deque::iterator insert(pos, value) inserts value at pos, pos is returned.
  • void insert(pos, first, beyond) inserts the elements in the iterator range [first, beyond).
  • void insert(pos, n, value) inserts n elements having value value at position pos.
  • void deque::pop_back():
    this member removes the last element from the deque. With an empty deque nothing happens.
  • void deque::pop_front():
    this member removes the first element from the deque. With an empty deque nothing happens.
  • void deque::push_back(value):
    this member adds value to the end of the deque.
  • void deque::push_front(value):
    this member adds value before the first element of the deque.
  • void deque::resize():
    this member can be used to alter the number of elements that are currently stored in the deque:
  • resize(n, value) may be used to resize the deque to a size of n. Value is optional. If the deque is expanded and tvalue is not provided, the extra elements are initialized to the default value of the used data type, otherwise the explicitly provided value value is used to initialize extra elements.
  • deque::reverse_iterator deque::rbegin():
    this member returns an iterator pointing to the last element in the deque.
  • deque::reverse_iterator deque::rend():
    this member returns an iterator pointing before the first element in the deque.
  • unsigned deque::size():
    this member returns the number of elements in the deque.
  • void deque::swap():
    this member can be used to swap two deques.
  • 12.2.6: The `map' container

    The map class implements a (sorted) associative array. To use the map, source files should
        #include <map>
    
    A map is filled with key/value pairs, which may be of any container-acceptable type. Since types are associated with both the key and the value, we must specify two types in the angular bracket notation that is used for maps. The first type represents the type of the key, the second type represents the type of the value. For example, a map in which the key is a string and the value is a double can be defined as follows:
        map<string, double>
            object;
    
    The key is used for locating the information belonging to the key. The associated information is called the value. For example, a phone book uses the names of people as the key, and uses the telephone number and maybe other information (e.g., the zip-code, the address, the profession) as the value.

    The two fundamental operations on maps are the storage of Key/Value combinations, and the retrieval of values, given their keys. Each key can be stored only once in a map. If the same key is entered again, the new value replaces the formerly stored value, which is lost.

    A specific key/value combination can be implicitly or explicitly inserted into a map. If explicit insertion is required, the key/value combination must be constructed first. For this, every map defines a value_type which may be used to create values that can be stored in the map. For example, a value for a map<string, int> can be constructed as follows:

        map<string, int>::value_type
            siValue("Hello", 1);
    
    The value_type is associated with the map<string, int>: the type of the key is string, the type of the value is int. Anonymous value_type objects are also often used. E.g.,
        map<string, int>::value_type("Hello", 1);
    
    Instead of using the line map<string, int>::value_type(...) over and over again, a typedef is often used to reduce typing and to improve legibility:
        typedef map<string, int>::value_type StringIntValue
    
    Using this typedef, values for the map<string, int> may be constructed as follows:
        StringIntValue("Hello", 1);
    

    The following constructors, operators, and member functions are available vor the map container:

  • Constructors:
  • A map may be constructed empty:
        map<string, int>
            object;
    
    Note that the values stored in maps may be containers themselves. For example, the following defines a map in which the value is a pair: a container nested in another container:
        map<string, pair<string, string> >
            object;
    
    Note the blank space between the two closing angular brackets >: this is obligatory, as the immediate concatenation of the two angular closing brackets would be interpreted by the compiler as a right shift operator ( operator>>()), which is not what we want here.
  • A map may be initialized using a two iterators. The iterators may point to value_type values for the map to be constructed, or they may point to plain pair objects (see section 12.1), whose first elements reperesent the keys, and whose second elements represent the values to be used. For example:
        pair<string, int>
            pa[] = 
            {
                pair<string,int>("one", 1),
                pair<string,int>("two", 2),
                pair<string,int>("three", 3),
            };
    
        map<string, int>
            object(&pa[0], &pa[3]);
    
    In this example, map<string, int>::value_type could have been used instead of pair<string, int> as well.

    Note again that &pa[3], being interpreted as an iterator, points to the first element that must not be included in the map. The particular array element does not have to exist.

    Also note that, maybe contrary to intuition, the map constructor will only enter new keys. If the last element of pa would have been "one", 3, only two elements would have entered the map: "one", 1 and "two", 2. The value "one", 3 would have been silently ignored.

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

        #include <iostream>
        #include <string>
        #include <map>
        
        class MyClass
        {
            public:
                MyClass()
                {
                    cout << "MyClass constructor\n";
                }
                MyClass(const MyClass &other)
                {
                    cout << "MyClass copy constructor\n";
                }
                ~MyClass()
                {
                    cout << "MyClass destructor\n";
                }
        };
        
        int main()
        {
            pair<string, MyClass>
                pairs[] =
                {
                    pair<string, MyClass>("one", MyClass()),
                };
        
            cout << "pairs constructed\n";
        
            map<string, MyClass>
                mapsm(&pairs[0], &pairs[1]);
        
            cout << "mapsm constructed\n";
        }
        /*
            Generated output:
        MyClass constructor
        MyClass copy constructor
        MyClass destructor
        pairs constructed
        MyClass copy constructor
        MyClass copy constructor
        MyClass destructor
        mapsm constructed
        MyClass destructor
        */
    When tracing the output of this program, we see that, first, the constructor of a MyClass object is called to initialize the anonymous element of the array pairs. This object is then copied into the first element of the array pairs by the copy constructor. Next, the original element is not needed anymore, and gets destroyed. At that point the array pairs has been constructed. Thereupon, the map constructs a temporary pair object, which is used to construct the map element. Having constructed the map element, the temporary pair objects is destroyed. Eventually, when the program terminates, the pair element stored in the map is destroyed too.
  • A map may be initialized using a copy constructor:
        extern map<string, int>
            container;
        map<string, int>
            object(container);
    
  • Apart from the standard operators for containers, the map supports the index operator, which may be used to retrieve or reassign individual elements of the map. Here, the argument of the index operator is a key. If the provided key is not available in the map, a new data element is automatically added to the map, using the default value or default constructor to initialize the value part of the new element. This default value is returned if the index operator is used as an rvalue.

    When initializing a new or reassigning another element of the map, the right-hand side of the assignment operator must have the type of the value part of the map. E.g., to add or change the value of element "two" in a map, the following statement can be used:

        mapsm["two"] = MyClass();
    
  • The map class has the following member functions:
  • map::iterator map::begin():
    this member returns an iterator pointing to the first element of the map.
  • map::clear():
    this member erases all elements from the map.
  • unsigned map::count(key):
    this member returns 1 if the provided key is available in the map, otherwise 0 is returned.
  • bool map::empty():
    this member returns true if the map contains no elements.
  • map::iterator map::end():
    this member returns an iterator pointing beyond the last element of the map.
  • pair<map::iterator, map::iterator> map::equal_range(key):
    this member returns a pair of iterators, being respectively the return values of the member functions lower_bound() and upper_bound(), introduced below. An example illustrating the use of these member functions is given at the discussion of the member function upper_bound().
  • ... map::erase():
    this member can be used to erase a specific element or range of elements from the map:
  • bool erase(key) erases the element having the given key from the map. True is returned if the value was removed, false if the map did not contain an element using the given key.
  • void erase(pos) erases the element pointed to by pos.
  • void erase(first, beyond) erases all elements indicated by the iterator range [first, beyond).
  • map::iterator map::find(key):
    this member returns an iterator to the element having the given key. If the element isn't available, end() is returned. The following example illustrates the use of the find() member function:
        #include <iostream>
        #include <string>
        #include <map>
        
        int main()
        {
            map<string, int>
                object;
        
            object["one"] = 1;
        
            map<string, int>::iterator
                it = object.find("one");
        
            cout << "`one' " << 
                    (it == object.end() ? "not " : "") << "found\n";
        
            it = object.find("three");
        
            cout << "`three' " << 
                    (it == object.end() ? "not " : "") << "found\n";
        }
        /*
            Generated output:
        `one' found
        `three' not found
        */    
    
  • ... map::insert():
    this member can be used to insert elements starting at a certain position. Elements having the same keys as elements to be inserted are left untouched. The return value depends on the version of insert() that is called:
  • pair<map::iterator, bool> insert(keyvalue) is used to insert a new map::value_type into the map. The return value is a pair<map::iterator, bool>. If the returned bool field is true, keyvalue was inserted into the map. The value false indicates that the key that was specified in keyvalue was already available in the map, and so keyvalue was not inserted into the map. In both cases the map::iterator field points to the data element in the map having the key that was specified in keyvalue. The use of this variant of insert() is illustrated in the following example:
        #include <iostream>
        #include <string>
        #include <map>
        
        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, 4} and `true' (1) is returned
            pair<map<string, int>::iterator, bool>
                ret = object.insert
                        (
                            map<string, int>::value_type
                            ("four", 40)
                        );
        
            cout << ret.first->first << " " << 
                ret.first->second << " " << 
                ret.second << " " << object["four"] << endl;
        
                    // {four, 4} and `false' (0) is returned  
            ret = object.insert
                        (
                            map<string, int>::value_type
                            ("four", 0)
                        );
            
            cout << ret.first->first << " " << 
                ret.first->second << " " << 
                ret.second << " " << object["four"] << endl;
        }
        /*
            Generated output:
        four 40 1 40
        four 40 0 40
        */
    
    Note the somewhat peculiar constructions like
        cout << ret.first->first << " " << ret.first->second << ...
    
    Realize that `ret' is the pair variable returned by the insert() member function. Its `first' field is an iterator into the map<string, int>, so it can be considered a pointer to a map<string, int> value type. These value types themselves are pairs too, having `first' and `second' fields. Consequently, `ret.first->first' is the key of the map value (a string), and `ret.first->second' is the value (an int).
  • map::iterator insert(pos, keyvalue). This is another way to insert a map::value_type into the map. pos is ignored, and an iterator to the inserted element is returned.
  • void insert(first, beyond) inserts the (map::value_type) elements pointed to by the iterator range [first, beyond).
  • map::iterator map::lower_bound(key):
    this member returns an iterator pointing to the element with the given key. If no such value exists, map::end() is returned.
  • map::reverse_iterator map::rbegin():
    this member returns an iterator pointing to the last element of the map.
  • map::reverse_iterator map::rend():
    this member returns an iterator pointing before the first element of the map.
  • unsigned map::size():
    this member returns the number of elements in the map.
  • void map::swap():
    this member can be used to swap two maps.
  • map::iterator map::upper_bound(key):
    this member returns the iterator map::end(). The following example illustrates the member functions equal_range(), lower_bound() and upper_bound():
        #include <iostream>
        #include <string>
        #include <map>
        
        int main()
        {
            pair<string, int>
                pa[] = 
                {
                    pair<string,int>("one", 10),
                    pair<string,int>("two", 20),
                    pair<string,int>("three", 30),
                };
            map<string, int>
                object(&pa[0], &pa[3]);
    
            if (object.lower_bound("twoo") == object.end())
                cout << "lower-bound `twoo' not available" << endl;
    
            cout << "lower-bound two: " << 
                    object.lower_bound("two")->first << 
                    " is available\n";
    
            if (object.upper_bound("twoo") == object.end())
                cout << "upper-bound `twoo' not available" << endl;
    
            if (object.upper_bound("two") == object.end())
                cout << "upper-bound `two' not available" << endl;
    
            pair
            <
                map<string, int>::iterator, 
                map<string, int>::iterator
            >
                p = object.equal_range("two");
    
            cout << "equal range: `first' points to " <<
                        p.first->first << ", `second' is " <<
                (
                    p.second == object.end() ?
                        "not available"
                    :
                        p.second->first
                ) <<
                endl;
        }
        /*
            Generated output:
    lower-bound `twoo' not available
    lower-bound two: two is available
    upper-bound `twoo' not available
    upper-bound `two' not available
    equal range: `first' points to two, `second' is not available
        */
    
  • As mentioned at the beginning of this section, the map represents a sorted associative array. In a map the keys are sorted. If an application must visit all elements in a map (or just the keys or the values) the begin() and end() iterators must be used. The following example shows how to make a simple table from all keys and values in a map:
        #include <iostream>
        #include <iomanip.h>
        #include <string>
        #include <map>
        
        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
        */
    

    12.2.7: The `multimap' container

    Like the map, the multimap class implements a (sorted) associative array. To use the multimap, source files must
        #include <map>
    
    The main difference between the map and the multimap is that the multimap supports multiple entries of the same key, whereas the map contains unique keys. Note that the multimap also accepts multiple entries of values having the same keys and the same values.

    The map and the multimap have the same set of member functions, with the exception of the index operator ( operator[]()), which is not supported with the multimap. This is understandable: if multiple entries of the same key are allowed, which of the possible values should be returned for object[key]?

    Refer to section 12.2.6 for an overview of member functions that are available with the multimap. Some member functions, however, act a bit different with the multimap than with the map. These differences are discussed below.

    The following member functions act differently with multimap containers than with map containers:

  • unsigned map::count(key):
    this member returns the number of entries in the multimap that are associated with the given key.
  • ... multimap::erase():
    this member can be used to erase elements from the map:
  • unsigned erase(key) erases all elements having the given key. The number of erased elements is returned.
  • void erase(pos) erases the element pointed to by pos. Other elements possibly having the same keys are not erased.
  • void erase(first, beyond) erases all elements indicated by the iterator range [first, beyond).
  • pair<multimap::iterator, multimap::iterator> multimap::equal_range(key):
    this member function returns a pair of iterators, being respectively the return values of multimap::lower_bound() and multimap::upper_bound(), introduced below. The function provides a simple means to determine all elements in the multimap that have the same keys. 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 is key. If the element isn't available, multimap::end() is returned. The iterator could be incremented to visit all elements having the same key until it is either multimap::end(), or the iterator's first member is not equal to key anymore.
  • ... multimap::insert():
    this member function normally succeeds, and so a multimap::iterator is returned, instead of a pair<multimap::iterator, bool> as returned with the map container. The returned iterator points to the newly added element.
  • multimap::iterator multimap::lower_bound(key):
    this member returns an iterator pointing to the first keyvalue element of which the key is equal to or exceeds the specified key. If no such element exists, the function returns multimap::end().
  • multimap::iterator multimap::upper_bound(key):
    this member returns an iterator pointing to the first keyvalue element having a key exceeding the specified key. If no such element exists, the function returns multimap::end().
  • The following example illustrates multimap::lower_bound(), multimap::upper_bound() and multimap::equal_range:
        #include <iostream>
        #include <string>
        #include <map>
        
        int main()
        {
            pair<string, int>
                pa[] = 
                {
                    pair<string,int>("alpha", 1),
                    pair<string,int>("bravo", 2),
                    pair<string,int>("charley", 3),
                    pair<string,int>("bravo", 6),   // unordered `bravo' values
                    pair<string,int>("delta", 5),
                    pair<string,int>("bravo", 4),
                };
            multimap<string, int>
                object(&pa[0], &pa[6]);
    
            typedef multimap<string, int>::iterator msiIterator;
            
            msiIterator
                it = object.lower_bound("brava");
    
            cout << "Lower bound for `brava': " <<
                    it->first << ", " << it->second << endl;
    
            it = object.upper_bound("bravu");
    
            cout << "Upper bound for `bravu': " <<
                    it->first << ", " << it->second << endl;
    
            pair<msiIterator, msiIterator>
                itPair = object.equal_range("bravo");
    
            for (it = itPair.first; it != itPair.second; ++it)
                cout << it->first << ", " << it->second << endl;
    
            cout << "Upper bound: " << it->first << ", " << it->second << endl;
        }
        /*
            Generated output: 
        Lower bound for `brava': bravo, 2
        Upper bound for `bravu': charley, 3
        bravo, 2
        bravo, 6
        bravo, 4
        Upper bound: charley, 3
        */    
    
    Especially note the following characteristics:
  • lower_bound() and upper_bound() produce the same result for non-existing keys: they both return the first element having a key that exceeds the provided key.
  • Although the keys are ordered in the multimap, the values for equal keys are not ordered: they are retrieved in the order in which they were enterd.
  • 12.2.8: The `set' container

    The set class implements a sorted collection of values. To use the set, source files must #include <set>
        #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 key/value combination can be implicitly or explicitly inserted into a set. If explicit insertion is required, the value must be constructed first. For this, 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 StringSetValue
    
    Using this typedef, values for the set<string> may be constructed as follows:
        StringSetValue("Hello");
    

    The following constructors, operators, and member functions are available vor the set container:

  • Constructors:
  • A set may be constructed empty:
        set<int>
            object;
    
  • A set may be initialized using a two iterators. For example:
        int
            intarr[] = {1, 2, 3, 4, 5};
    
        set<int>
            object(&intarr[0], &intarr[5]);
    
  • Note that all values in the set must be different: it is not possible to store the same value repeatedly when the set is constructed. If the same value occurs repeatedly, only the first instance of the value will be entered, the other values will be silently ignored.

    Like the map, the set receives its own copy of the data it contains.

  • A set may be initialized using a copy constructor:
        extern set<string>
            container;
        set<string>
            object(container);
    
  • The set container only supports the standard set of operators that are available for containers.
  • The set class has the following member functions:
  • set::iterator set::begin():
    this member returns an iterator pointing to the first element of the set.
  • set::clear():
    this member erases all elements from the set.
  • unsigned set::count(key):
    this member returns 1 if the provided key is available in the set, otherwise 0 is returned.
  • bool set::empty():
    this member returns true if the set contains no elements.
  • set::iterator set::end():
    this member returns an iterator pointing beyond the last element of the set.
  • pair<set::iterator, set::iterator> set::equal_range(key):
    this member returns a pair of iterators, being respectively the return values of the member functions lower_bound() and upper_bound(), introduced below.
  • ... set::erase():
    this member can be used to erase a specific element or range of elements from the set:
  • bool erase(value) erases the element having the given value from the set. True is returned if the value was removed, false if the set did not contain an element `value'.
  • void erase(pos) erases the element pointed to by pos.
  • void erase(first, beyond) erases all elements indicated by the iterator range [first, beyond).
  • set::iterator set::find(value):
    this member returns an iterator to the element having the given value. If the element isn't available, end() is returned.
  • ... set::insert():
    this member can be used to insert elements into the set. 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 of insert() that is called:
  • pair<set::iterator, bool> insert(keyvalue) is used to insert a new set::value_type into the set. The return value is a pair<set::iterator, bool>. If the returned bool field is true, value was inserted into the set. The value false indicates that the value that was specified was already available in the set, and so the provided value was not inserted into the set. In both cases the set::iterator field points to the data element in the set having the specified value.
  • set::iterator insert(pos, keyvalue). This is another way to insert a set::value_type into the set. pos is ignored, and an iterator to the inserted element is returned.
  • void insert(first, beyond) inserts the (set::value_type) elements pointed to by the iterator range [first, beyond) into the set.
  • set::iterator set::lower_bound(key):
    this member returns an iterator pointing to the element with the given key. If no such value exists, end() is returned.
  • set::reverse_iterator set::rbegin():
    this member returns an iterator pointing to the last element of the set.
  • set::reverse_iterator set::rend():
    this member returns an iterator pointing before the first element of the set.
  • unsigned set::size():
    this member returns the number of elements in the set.
  • void set::swap():
    this member can be used to swap two sets.
  • set::iterator set::upper_bound(key):
    this member returns an iterator pointing to the element with the given key. If no such value exists, end() is returned.
  • 12.2.9: The `multiset' container

    Like the set, the multiset class implements a sorted collection of value. To use the multiset, source files must
        #include <set>
    
    The main difference between the set and the multiset is that the multiset supports multiple entries of the same value, whereas the set contains unique values.

    The set and the multiset have the same set of member functions. Refer to section 12.2.8 for an overview of member functions that are available with the multiset. Some member functions, however, act a bit different with the multiset than with the set. These differences are discussed below.

    The following member functions act differently with multiset containers than with set containers:

  • unsigned set::count(value):
    this member returns the number of entries in the multiset that are associated with the given value.
  • ... multiset::erase():
    this member can be used to erase elements from the set:
  • unsigned erase(value) erases all elements having the given value. The number of erased elements is returned.
  • void erase(pos) erases the element pointed to by pos. Other elements possibly having the same values are not erased.
  • void erase(first, beyond) erases all elements indicated by the iterator range [first, beyond).
  • pair<multiset::iterator, multiset::iterator> multiset::equal_range(value):
    this member function returns a pair of iterators, being respectively the return values of multiset::lower_bound() and multiset::upper_bound(), introduced below. The function provides a simple means to determine all elements in the multiset that have the same values.
  • 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 given value until it is either multiset::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 a pair<multiset::iterator, bool> as returned with the set container. The returned iterator points to the newly added element.
  • multiset::iterator multiset::lower_bound(value):
    this member returns an iterator pointing to the first valuevalue element of which the value is equal to or exceeds the specified value. If no such element exists, the function returns multiset::end().
  • multiset::iterator multiset::upper_bound(value):
    this member returns an iterator pointing to the first valuevalue element having a value exceeding the specified value. If no such element exists, the function returns multiset::end().
  • An example showing the use of various member functions of a multiset is given next:
        #include <iostream>
        #include <string>
        #include <set>
        
        using namespace std;
    
        int main()
        {
            string
                sa[] = 
                {
                    "alpha", 
                    "echo", 
                    "hotel", 
                    "mike", 
                    "romeo"
                };
         
            multiset<string>
                object(&sa[0], &sa[5]);
        
            object.insert("echo");
            object.insert("echo");
        
            multiset<string>::iterator
                it = object.find("echo");
        
            for (; it != object.end(); ++it)
                cout << *it << " ";
            cout << endl;
        
            pair
            <
                multiset<string>::iterator,
                multiset<string>::iterator
            >
                itpair = object.equal_range("echo");
        
            for (; itpair.first != itpair.second; ++itpair.first)
                cout << *itpair.first << " ";
        
            cout << endl << 
                    object.count("echo") << " occurrences of 'echo'" << endl;
        }
        /*
            Generated output:
    echo echo echo hotel mike romeo 
    echo echo echo 
    3 occurrences of 'echo'
        */
    

    12.2.10: The `stack' container

    The stack class implements a stack data structure. To use the stack, source files must
        #include <stack>
    
    A stack is also called a first in, last out ( FILO or LIFO) data structure, as the first item to enter the stack is the last item to leave. A stack is an extremely useful data structure in situations where data must temporarily remain available. For example, programs maintain a stack to store local variables of functions: these variables lifetime live only as long as the functions live, contrary to global (or static local) variables, which live for as long as the program itself lives. Another example is found in calculators using the Reverse Polish Notation ( RPN), in which the operands of expressions are entered in the stack, and the operators pop their operands and push the results of their work.

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

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

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

    Bearing this model of the stack in mind, let's see what we can formally do with it, using the stack container. For the stack, the following constructors, operators, and member functions are available:

  • Constructors:
  • A stack may be constructed empty:
        stack<string>
            object;
    
  • A stack may be initialized using a copy constructor:
        extern stack<string>
            container;
        stack<string>
            object(container);
    
  • The stack only supports the basic operators of containers.
  • The following member functions are available for stacks:
  • bool stack::empty():
    this member returns true if the stack contains no elements.
  • void stack::push(value):
    this member places value at the top of the stack, hiding the other elements from view.
  • void stack::pop():
    this member removes the element at the top of the stack. Note that the popped element is not returned by this member.
  • unsigned stack::size():
    this member returns the number of elements in the stack.
  • Type &stack::top():
    this member returns a reference to the first element of the stack. It is the responsibility of the programmer not to use the member if the stack is empty.
  • Note that the stack does not support iterators or a subscript operator. The only elements that can be accessed is its top element, and a stack can only be emptied by repeatedly popping its top-element.

    12.2.11: The `hash_map' and other hashing-based containers

    The map is a sorted data structure. The keys in maps are sorted using the operator<() of the key's data type. Generally, this is not the fastest way to either store or retrieve data. The main benefit of sorting is that a listing of sorted keys appeals more to humans than an unsorted list. However, a by far faster method to store and retrieve data is to use hashing.

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

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

    The Gnu g++ compiler supports the hash_(multi)map and hash_(multi)set containers. Below the hash_map container is discussed, but other containers using hashing ( hash_multimap, hash_set and hash_multiset) operate correspondingly.

    Concentrating on the hash_map, its constructor needs a key type, a value type, an object creating a hash value for the key, and an object comparing two keys for equality. Hash functions are available for char const * keys, and for all the scalar numerical types char, short, int etc.. If another data type is used, a hash function and an equality test must be implemented, possibly using function objects (see section 9.9). For both situations examples are given below.

    The class implementing the hash function could be called hash. Its function call operator ( operator()()) returns the hash value of the key that is passed as its argument.

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

    The hash_map class implements an associative array in which the key is stored according to some hashing scheme. To use the hash_map, sources must

        #include <ext/hash_map>
    
    The hash_(multi)map is still part of the ANSI/ISO extension. Once this container becomes part of the standard, the ext/ prefix in the #include preprocessor directive can be removed.

    Constructors, operators and member functions that are available for the map are also available for the hash_map. At the user-level there is no difference in the use of a map and a hash_map. However, the efficiency of a hash_map in terms of speed should greatly exceed the efficiency of the map. Comparable conclusions may be drawn for the hash_set, hash_multimap and the hash_multiset.

    Compared to the map container, the hash_map has an extra constructor:

            hash_map<...>
                hash(n);
    
    where n is an unsigned value, may be used to construct a hash_map consisting of an initial number of at least n empty slots to put key/value combinations in. This number is automatically extended when needed.

    The hashed data type is almost always text. So, a hash_map in which the key's data type is either char const * or a string occurs most often. If the following header file is placed in the C++ compiler's INCLUDE path as the file hashclasses.h, sources could

        #include <hashclasses.h>
    
    to make available a set of classes that can be used with the instantiation of a hash table. Otherwise, sources must
        #include <ext/hash_map>
    
    #ifndef _HASHCLASSES_H_
    #define _HASHCLASSES_H_
    
    #include <string>
    #include <ext/hash_map>
    
    /*
        This file is copyright (c) GPL, 2001.
        =====================================
    
    
        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:
                                        // key is char const *, case sensitive
            hash_map<char const *, int, HashCharPtr, EqualCharPtr >
                hashtab;
    
                                        // key is char const *, case insensitive
            hash_map<char const *, int, HashCaseCharPtr, EqualCaseCharPtr >
                hashtab;
    
                                        // key is std::string, case sensitive
            hash_map<std::string, int, HashString>
                hashtab;
    
                                        // key is std::string, case insensitive
            hash_map<std::string, int, HashCaseString, EqualCaseString>
                hashtab;
    
        Feb. 2001
        Frank B. Brokken (f.b.brokken@rc.rug.nl)
    */
    
    class HashCharPtr
    {
        public: bool 
        operator()(char const *str) const
        { 
            return std::hash<char const *>()(str);
        }
    };
    
    class EqualCharPtr
    {
        public: bool 
        operator()(char const *x, char const *y) const 
        { 
            return !strcmp(x, y); 
        }
    };
    
    class HashCaseCharPtr
    {
        public: bool 
        operator()(char const *str) const
        { 
            std::string
                s = str;
            transform(s.begin(), s.end(), s.begin(), tolower);
            return std::hash<char const *>()(s.c_str());
        }
    };
    
    class EqualCaseCharPtr
    {
        public: bool 
        operator()(char const *x, char const *y) const 
        { 
            return !strcasecmp(x, y); 
        }
    };
    
    class HashString
    {
        public: bool 
        operator()(std::string const &str) const
        { 
            return std::hash<char const *>()(str.c_str());
        }
    };
    
    class HashCaseString: public HashCaseCharPtr
    {
        public: bool 
        operator()(std::string const &str) const
        { 
            return HashCaseCharPtr::operator()(str.c_str());
        }
    };
    
    class EqualCaseString
    {
        public: bool 
        operator()(std::string const &s1, std::string const &s2) const 
        { 
            return !strcasecmp(s1.c_str(), s2.c_str()); 
        }
    };
    
    #endif
    
    The following program defines a hash_map containing the names of the months of the year and the number of days these months (usually) have. Then, using the subscript operator the days in several months are displayed. The equality operator used the generic algorithm equal_to<string>, which is the default fourth argument of the hash_map constructor:
    //    #include <hashclasses.h>
        #include <iostream>
        #include "hashclasses.h"
    
        using namespace std;
    
        int main()
        {
            hash_map<string, int, HashString >
                months;
        
            months["january"] = 31;
            months["february"] = 28;
            months["march"] = 31;
            months["april"] = 30;
            months["may"] = 31;
            months["june"] = 30;
            months["july"] = 31;
            months["august"] = 31;
            months["september"] = 30;
            months["october"] = 31;
            months["november"] = 30;
            months["december"] = 31;
          
            cout << "september -> " << months["september"] << endl <<
                    "april     -> " << months["april"] << endl <<
                    "june      -> " << months["june"] << endl <<
                    "november  -> " << months["november"] << endl;
        }
        /*
            Generated output:
        september -> 30
        april     -> 30
        june      -> 30
        november  -> 30
        */
    

    The hash_multimap, hash_set and hash_multiset containers are used analogously. For these containers the equal and hash classes must also be defined. The hash_multimap also requires the hash_map header file, the hash_set and hash_multiset containers can be used when source files

        #include <ext/hash_set>
    

    12.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, sources must

        #include <complex>
    
    The complex container can be used to define complex numbers, consisting of two parts, representing the real and imaginary parts of a complex number.

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

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

        complex<double>
        complex<int>        
        complex<float>      
    
    Note that the real and imaginary parts of complex numbers have the same datatypes.

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

  • target: A default initialization: real and imaginary parts are 0.
  • target(1): The real part is 1, imaginary part is 0
  • target(0, 3.5): The real part is 0, imaginary part is 3.5
  • target(source): target is initialized with the values of source.
  • 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();
            }
        }
        /*
            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):

  • Apart from the standard container operators, the following operators are supported from the complex container.
  • complex complex::operator+(value):
    this member returns the sum of the current complex container and value.
  • complex complex::operator-(value):
    this member returns the difference between the current complex container and value.
  • complex complex::operator*(value):
    this member returns the product of the current complex container and value.
  • complex complex::operator/(value):
    this member returns the quotient of the current complex container and value.
  • complex complex::operator+=(value):
    this member adds value to the current complex container, returning the new value.
  • complex complex::operator-=(value):
    this member subtracts value from the current complex container, returning the new value.
  • complex complex::operator*(value):
    this member multiplies the current complex container by value, returning the new value
  • complex complex::operator/(value):
    this member divides the current complex container by value, 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.
  • Several mathematical functions are available for the complex container, such as abs(), arg(), conj(), cos(), cosh(), exp(), log(), norm(), polar(), pow(), sin(), sinh() and sqrt(). These functions are normal functions, not member functions. They accept complex numbers as their arguments. For example,
        abs(complex<double>(3, -5));
        pow(target, complex<int>(2, 3));
    
  • 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.