Every container class provides a default constructor, a copy constructor, and a destructor. You can also initialize a container with elements of a given range. This constructor is provided to initialize the container with elements of another container, with an array, or from standard input. These constructors are member templates (see page 11), so not only the container but also the type of the elements may differ, provided there is an automatic conversion from the source element type to the destination element type.^[2] The following examples expand on this:

In principle, these techniques are also provided to assign or to insert elements from another range. However, for those operations the exact interfaces either differ due to additional arguments or are not provided for all container classes.

For all container classes, three size operations are provided:

The usual comparison operators ==, ! =, <, <=, >, and >= are defined according to the following three rules:

To compare containers with different types, you must use the comparing algorithms of Section 9.5.4.

If you assign containers, you copy all elements of the source container and remove all old elements in the destination container. Thus, assignment of containers is relatively expensive.

If the containers have the same type and the source is no longer used, there is an easy optimization: Use swap(). swap() offers much better efficiency because it swaps only the internal data of the containers. In fact, it swaps only some internal pointers that refer to the data (elements, allocator, sorting criterion, if any). So, swap() is guaranteed to have only constant complexity, instead of the linear complexity of an assignment.

Part of the way in which vectors give good performance is by allocating more memory than they need to contain all their elements. To use vectors effectively and correctly you should understand how size and capacity cooperate in a vector.

Vectors provide the usual size operations size(), empty(), and max_size() (see Section 6.1.2). An additional "size" operation is the capacity() function. capacity() returns the number of characters a vector could contain in its actual memory. If you exceed the capacity(), the vector has to reallocate its internal memory.

The capacity of a vector is important for two reasons:

Thus, if a program manages pointers, references, or iterators into a vector, or if speed is a goal, it is important to take the capacity into account.

To avoid reallocation, you can use reserve() to ensure a certain capacity before you really need it. In this way, you can ensure that references remain valid as long as the capacity is not exceeded:

    std::vector<int> v;       // create an empty vector
    v.reserve (80);           // reserve memory for 80 elements

Another way to avoid reallocation is to initialize a vector with enough elements by passing additional arguments to the constructor. For example, if you pass a numeric value as parameter, it is taken as the starting size of the vector:

    std::vector<T> v(5);       // creates a vector and initializes it with five values
// (calls five times the default constructor of type T)

Of course, the type of the elements must provide a default constructor for this ability. But note that for complex types, even if a default constructor is provided, the initialization takes time. If the only reason for initialization is to reserve memory, you should use reserve().

The concept of capacity for vectors is similar to that for strings (see Section 11.2.5), with one big difference: Unlike strings, it is not possible to call reserve() for vectors to shrink the capacity. Calling reserve() with an argument that is less than the current capacity is a no-op. Furthermore, how to reach an optimal performance regarding speed and memory usage is implementation defined. Thus, implementations might increase capacity in larger steps. In fact, to avoid internal fragmentation, many implementations allocate a whole block of memory (such as 2K) the first time you insert anything if you don't call reserve() first yourself. This can waste lots of memory if you have many vectors with only a few small elements.

Because the capacity of vectors never shrinks, it is guaranteed that references, pointers, and iterators remain valid even when elements are deleted, provided they refer to a position before the manipulated elements. However, insertions may invalidate references, pointers, and iterators.

There is a way to shrink the capacity indirectly: Swapping the contents with another vector swaps the capacity. The following function shrinks the capacity while preserving the elements:

    template <class T>
    void shrinkCapacity(std::vector<T>& v)
    {
         std::vector<T> tmp(v);    // copy elements into a new vector
         v.swap(tmp);              // swap internal vector data
    }

You can even shrink the capacity without calling this function by calling the following statement^[6]:

//shrink capacity of vector v for type T
   std::vector<T>(v).swap(v);

However, note that after swap(), all references, pointers, and iterators swap their containers. They still refer to the elements to which they referred on entry. Thus, shrinkCapacity() invalidates all references, pointers, and iterators.

Table 6.2 lists the constructors and destructors for vectors. You can create vectors with and without elements for initialization. If you pass only the size, the elements are created with their default constructor. Note that an explicit call of the default constructor also initializes fundamental types such as int with zero (this language feature is covered on page 14). See Section 6.1.2, for some remarks about possible initialization sources.

Table 6.3 lists all nonmodifying operations of vectors.^[7] See additional remarks in Section 6.1.2, and Section 6.2.1.

Table 6.4 lists the ways to assign new elements while removing all ordinary elements. The set of assign() functions matches the set of constructors. You can use different sources for assignments (containers, arrays, standard input) similar to those described for constructors on page 144. All assignment operations call the default constructor, copy constructor, assignment operator, and/or destructor of the element type, depending on how the number of elements changes. For example:

    std::list<Elem> l;
    std::vector<Elem> coll;
    ...
    //make coll be a copy of the contents of l
    coll.assign(l.begin(),l.end());

Table 6.5 shows all vector operations for direct element access. As usual in C and C++, the first element has index 0 and the last element has index size()−1. Thus, the nth element has index n−1. For nonconstant vectors, these operations return a reference to the element. Thus you could modify an element by using one of these operations (provided it is not forbidden for other reasons).

The most important issue for the caller is whether these operations perform range checking. Only at() performs range checking. If the index is out of range, it throws an out_of_range exception (see Section 3.3). All other functions do not check. A range error results in undefined behavior. Calling operator [], front(), and back() for an empty container always results in undefined behavior:

   std::vector<Elem> coll;          // empty!

   coll [5] = elem;                 // RUNTIME ERROR
$$$undefined behavior
   std::cout << coll.front ();     // RUNTIME ERROR
$$$undefined behavior

So, you must ensure that the index for operator [] is valid and the container is not empty when either front() or back() is called:

    std::vector<Elem> coll;         // empty!

    if (coll.size() > 5) {
        coll [5] = elem;            // OK
    }
    if (!coll.empty()) {
        cout << coll.front();       // OK
    }
    coll.at(5) = elem;              // throws out_of_range exception

Vectors provide the usual operators to get iterators (Table 6.6). Vector iterators are random access iterators (see Section 7.2, for a discussion of iterator categories). Thus, in principle you could use all algorithms of the STL.

The exact type of these iterators is implementation defined. However, for vectors they are often ordinary pointers. An ordinary pointer is a random access iterator, and because the internal structure of a vector is usually an array, it has the correct behavior. However, you can't count on it. For example, if a safe version of the STL that checks range errors and other potential problems is used, the iterator type is usually an auxiliary class. See Section 7.2.6, for a look at the nasty difference between iterators implemented as pointers and iterators implemented as classes.

Iterators remain valid until an element with a smaller index gets inserted or removed, or reallocation occurs and capacity changes (see Section 6.2.1).

Table 6.7 shows the operations provided for vectors to insert or to remove elements. As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container.

Regarding performance, you should consider that inserting and removing happens faster when

Inserting or removing elements invalidates references, pointers, and iterators that refer to the following elements. If an insertion causes reallocation, it invalidates all references, iterators, and pointers.

Vectors provide no operation to remove elements directly that have a certain value. You must use an algorithm to do this. For example, the following statement removes all elements that have the value val:

   std::vector<Elem> coll;
   ...
   //remove all elements with value val
   coll.erase(remove(coll.begin(), coll.end(),
                     val),
              coll.end());

This statement is explained in Section 5.6.1.

To remove only the first element that has a certain value, you must use the following statements:

   std::vector<Elem> coll;
   ...
   //remove first element with value val
   std::vector<Elem>::iterator pos;
   pos = find(coll.begin(),coll.end(),
              val);
   if (pos != coll.end()) {
       coll.erase(pos);
   }

The ability to create, copy, and destroy lists is the same as it is for every sequence container. See Table 6.12 for the list operations that do this. See also Section 6.1.2, for some remarks about possible initialization sources.

Lists provide the usual operations for size and comparisons. See Table 6.13 for a list and Section 6.1.2, for details.

Lists also provide the usual assignment operations for sequence containers (Table 6.14).

As usual, the insert operations match the constructors to provide different sources for initialization (see Section 6.1.2, for details).

Because a list does not have random access, it provides only front() and back() for accessing elements directly (Table 6.15).

As usual, these operations do not check whether the container is empty. If the container is empty, calling them results in undefined behavior. Thus, the caller must ensure that the container contains at least one element. For example:

   std::list<Elem> coll;           // empty!

   std::cout << coll.front();      // RUNTIME ERROR ⇒ undefined behavior

   if (!coll.empty()) {
       std::cout << coll.back();   // OK

   }

To access all elements of a list, you must use iterators. Lists provide the usual iterator functions (Table 6.16). However, because a list has no random access, these iterators are only bidirectional. Thus, you can't call algorithms that require random access iterators. All algorithms that manipulate the order of elements a lot (especially sorting algorithms) fall under this category. However, for sorting the elements, lists provide the special member function sort() (see page 245).

Table 6.17 shows the operations provided for lists to insert and to remove elements. Lists provide all functions of deques, supplemented by special implementations of the remove() and remove_if() algorithms.

As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container.

Inserting and removing happens faster if, when working with multiple elements, you use a single call for all elements rather than multiple calls.

For removing elements, lists provide special implementations of the remove() algorithms (see Section 9.7.1). These member functions are faster than the remove() algorithms because they manipulate only internal pointers rather than the elements. So, in contrast to vectors or deques, you should call remove() as a member function and not as an algorithm (as mentioned on page 154). To remove all elements that have a certain value, you can do the following (see Section 5.6.3, for further details):

    std::list<Elem> coll;
    ...
    //remove all elements with value val
    coll.remove(val);

However, to remove only the first occurrence of a value, you must use an algorithm such as that mentioned on page 154 for vectors.

You can use remove_if() to define the criterion for the removal of the elements by a function or a function object.^[13] remove_if() removes each element for which calling the passed operation yields true. An example of the use of remove_if() is a statement to remove all elements that have an even value:

    list.remove_if (not1(bind2nd(modulus<int>(),2)));

If you don't understand this statement, don't panic. Turn to page 306 for details. See page 378 for additional examples of remove() and remove_if().

Linked lists have the advantage that you can remove and insert elements at any position in constant time. If you move elements from one container to another, this advantage doubles in that you only need to redirect some internal pointers (Figure 6.5).

Figure 6.5. Splice Operations to Change the Order of List Elements

To support this ability, lists provide not only remove() but also additional modifying member functions to change the order of and relink elements and ranges. You can call these operations to move elements inside a single list or between two lists, provided the lists have the same type. Table 6.18 lists these functions. They are covered in detail in Section 6.10.8, with examples in Section 6.4.4.

Table 6.20 lists the constructors and destructors of sets and multisets.

Here, set may be one of the following:

You can define the sorting criterion in two ways:

If no special sorting criterion is passed, the default sorting criterion, function object less<>, is used, which sorts the elements by using operator <.^[19]

Note that the sorting criterion is also used to check for equality of the elements. Thus, when the default sorting criterion is used, the check for equality of two elements looks like this:

   if (! (elem1<elem2 || elem2<elem1))

This has three advantages:

However, checking for equality in this way takes a bit more time. This is because two comparisons might be necessary to evaluate the previous expression. Note that if the result of the first comparison yields true, the second comparison is not evaluated.

By now the type name of the container might be a bit complicated and boring, so it is probably a good idea to use a type definition. This definition could be used as a shortcut wherever the container type is needed (this also applies to iterator definitions):

   typedef std::set<int,std::greater<int> > IntSet;
   ...
   IntSet coll;
   IntSet::iterator pos;

The constructor for the beginning and the end of a range could be used to initialize the container with elements from containers that have other types, from arrays, or from the standard input. See Section 6.1.2, for details.

Sets and multisets provide the usual nonmodifying operations to query the size and to make comparisons (Table 6.21).

Comparisons are provided only for containers of the same type. Thus, the elements and the sorting criterion must have the same types; otherwise, a type error occurs at compile time. For example:

   std::set<float> c1;      // sorting criterion: std::less<>
   std::set<float,std::greater<float> > c2;
   ...
   if (c1 == c2) {          // ERROR: different types
      ...
   }

The check whether a container is less than another container is done by a lexicographical comparison (see page 360). To compare containers of different types (different sorting criteria), you must use the comparing algorithms in Section 9.5.4, page 356.

Sets and multisets are optimized for fast searching of elements, so they provide special search functions (Table 6.22). These functions are special versions of general algorithms that have the same name. You should always prefer the optimized versions for sets and multisets to achieve logarithmic complexity instead of the linear complexity of the general algorithms. For example, a search of a collection of 1,000 elements requires on average only 10 comparisons instead of 500 (see Section 2.3, page 21).

The find() member function searches the first element that has the value that was passed as the argument and returns its iterator position. If no such element is found, find() returns end() of the container.

lower_bound() and upper_bound() return the first and last position respectively, at which an element with the passed value would be inserted. In other words, lower_bound() returns the position of the first element that has the same or a greater value than the argument, whereas upper_bound() returns the position of the first element with a greater value. equal_range() returns both return values of lower_bound() and upper_bound() as a pair (type pair is introduced in Section 4.1, page 33). Thus, it returns the range of elements that have the same value as the argument. If lower_bound() or the first value of equal_range() is equal to upper_bound() or the second value of equal_range(), then no elements with the same value exist in the set or multiset. Naturally, in a set the range of elements that have the same values could contain at most one element.

The following example shows how to use lower_bound(), upper_bound(), and equal_range():

// cont/set2.cpp

    #include <iostream>
    #include <set>
    using namespace std;
    int main ()
    {

        set<int> c;

        c.insert(1);
        c.insert(2);
        c.insert(4);
        c.insert(5);
        c.insert(6);

        cout << "lower_bound(3): " << *c.lower_bound(3) << endl;
        cout << "upper_bound(3): " << *c.upper_bound(3) << endl;
        cout << "equal_range(3): " << *c.equal_range(3).first << " "
                                   << *c.equal_range(3).second << endl;
        cout << endl;
        cout << "lower_bound(5): " << *c.lower_bound(5) << endl;
        cout << "upper_bound(5): " << *c.upper_bound(5) << endl;
        cout << "equal_range(5): " << *c.equal_range(5).first << " "
                                   << *c.equal_range(5).second << endl;
    }

The output of the program is as follows:

    lower_bound(3): 4
    upper_bound(3): 4
    equal_range(3): 4 4

    lower_bound(5): 5
    upper_bound(5): 6
    equal_range(5): 5 6

If you use a multiset instead of a set, the program has the same output.

Sets and multisets provide only the fundamental assignment operations that all containers provide (Table 6.23). See page 147 for more details.

For these operations both containers must have the same type. In particular, the type of the comparison criteria must be the same, although the comparison criteria themselves may be different. See page 191 for an example of different sorting criteria that have the same type. If the criteria are different, they will also get assigned or swapped.

Sets and multisets do not provide direct element access, so you have to use iterators. Sets and multisets provide the usual member functions for iterators (Table 6.24).

As with all associative container classes, the iterators are bidirectional iterators (see Section 7.2.4, page 255). Thus, you can't use them in algorithms that are provided only for random access iterators (such as algorithms for sorting or random shuffling).

More important is the constraint that, from an iterator's point of view, all elements are considered constant. This is necessary to ensure that you can't compromise the order of the elements by changing their values. However, as a result you can't call any modifying algorithm on the elements of a set or multiset. For example, you can't call the remove() algorithm to remove elements because it "removes" by overwriting "removed" elements the with following arguments (see Section 5.6.2, page 115, for a detailed discussion of this problem). To remove elements in sets and multisets, you can use only member functions provided by the container.

Table 6.25 shows the operations provided for sets and multisets to insert and remove elements.

As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container.

Inserting and removing happens faster if, when working with multiple elements, you use a single call for all elements rather than multiple calls.

Note that the return types of the insert functions differ as follows:

The difference in return types results because multisets allow duplicates, whereas sets do not. Thus, the insertion of an element might fail for a set if it already contains an element with the same value. Therefore, the return type of a set returns two values by using a pair structure (pair is discussed in Section 4.1,):

In all other cases, the functions return the position of the new element (or of the existing element if the set contains an element with the same value already).

The following example shows how to use this interface to insert a new element into a set. It tries to insert the element with value 3.3 into the set c:

    std::set<double> c;
       
    ... if (c.insert(3.3).second) {
        std::cout << "3.3 inserted" << std::endl;
    }
    else {
        std::cout << "3.3 already exists" << std::endl;
    }

If you also want to process the new or old positions, the code gets more complicated:

//define variable for return value of insert()
    std::pair<std::set<float>::iterator, bool> status;

    //insert value and assign return value
    status = c.insert(value);

    //process return value
    if (status.second) {
        std::cout << value << " inserted as element "
    }
    else {
        std::cout << value << " already exists as element "
    }
    std::cout << std::distance(c.begin(), status.first) + 1
              << std::endl;

The output of two calls of this sequence might be as follows:

   8.9 inserted as element 4
   7.7 already exists as element 3

Note that the return types of the insert functions with an additional position parameter don't differ. These functions return a single iterator for both sets and multisets. However, these functions have the same effect as the functions without the position parameter. They differ only in their performance. You can pass an iterator position, but this position is processed as a hint to optimize performance. In fact, if the element gets inserted right after the position that is passed as the first argument, the time complexity changes from logarithmic to amortized constant (complexity is discussed in Section 2.3,). The fact that the return type for the insert functions with the additional position hint doesn't have the same difference as the insert functions without the position hint ensures that you have one insert function that has the same interface for all container types. In fact, this interface is used by general inserters. See Section 7.4.2, especially page 275, for details about inserters. To remove an element that has a certain value, you simply call erase():

   std::set<Elem> coll;
   ...
   //remove all elements with passed value
   coll.erase(value);

Unlike with lists, the erase() member function does not have the name remove() (see page 170 for a discussion of remove()). It behaves differently because it returns the number of removed elements. When called for sets, it returns only 0 or 1.

If a multiset contains duplicates, you can't use erase() to remove only the first element of these duplicates. Instead, you can code as follows:

   std::multiset<Elem> coll;
   ...
//remove first element with passed value
   std::multiset<Elem>::iterator pos;
   pos = coll.find (elem);
   if (pos != coll.end()) {
       coll.erase(pos);
   }

You should use the member function find() instead of the find() algorithm here because it is faster (see the example on page 154).

Note that there is another inconsistency in return types here. That is, the return types of the erase() functions differ between sequence and associative containers as follows:

The reason for this difference is performance. It might cost time to find and return the successor in an associative container because the container is implemented as a binary tree. However, as a result, to write generic code for all containers you must ignore the return value.

Table 6.26 lists the constructors and destructors of maps and multimaps.

Here, map may be one of the following:

You can define the sorting criterion in two ways:

If no special sorting criterion is passed, the default sorting criterion, function object less<>, is used. which sorts the elements by using operator <.^[26]

You should make a type definition to avoid the boring repetition of the type whenever it is used:

   typedef std::map<std::string,float,std::greater<string> >
           StringFloatMap;
   ...
   StringFloatMap coll;

The constructor for the beginning and the end of a range could be used to initialize the container with elements from containers that have other types, from arrays, or from the standard input. See Section 6.1.2, for details. However, the elements are key/value pairs, so you must ensure that the elements from the source range have or are convertible into type pair<key,value>.

Maps and multimaps provide the usual nonmodifying operations — those that query size aspects and make comparisons (Table 6.27).

Comparisons are provided only for containers of the same type. Thus, the key, the value, and the sorting criterion must be of the same type. Otherwise, a type error occurs at compile time. For example:

   std::map<float,std::string> c1;     // sorting criterion: less<>
   std::map<float,std::string,std::greater<float> > c2;
   ...
   if (c1 == c2) {                     // ERROR: different types
       ...
   }

To check whether a container is less than another container is done by a lexicographical comparison (see page 360). To compare containers of different types (different sorting criterion), you must use the comparing algorithms of Section 9.5.4.

Like sets and multisets, maps and multimaps provide special search member functions that perform better because of their internal tree structure (Table 6.28).

The find() member function searches for the first element that has the appropriate key and returns its iterator position. If no such element is found, find() returns end() of the container. You can't use the find() member function to search for an element that has a certain value. Instead, you have to use a general algorithm such as the find_if() algorithm, or program an explicit loop. Here is an example of a simple loop that does something with each element that has a certain value:

   std::multimap<std::string,float> coll;
   ...
   //do something with all elements having a certain value
   std::multimap<std::string,float>::iterator pos;
   for (pos = coll.begin(); pos != coll.end(); ++pos) {
      if (pos->second == value) {
          do_something();
      }
   }

Be careful when you want to use such a loop to remove elements. It might happen that you saw off the branch on which you are sitting. See page 204 for details about this issue.

Using the find_if() algorithm to search for an element that has a certain value is even more complicated than writing a loop because you have to provide a function object that compares the value of an element with a certain value. See page 211 for an example.

The lower_bound(), upper_bound(), and equal_range() functions behave as they do for sets (see page 180), except that the elements are key/value pairs.

Maps and multimaps provide only the fundamental assignment operations that all containers provide (Table 6.29). See page 147 for more details.

For these operations both containers must have the same type. In particular, the type of the comparison criteria must be the same, although the comparison criteria themselves may be different. See page 213 for an example of different sorting criteria that have the same type. If the criteria are different, they also get assigned or swapped.

Maps and multimaps do not provide direct element access, so the usual way to access elements is via iterators. An exception to that rule is that maps provide the subscript operator to access elements directly. This is covered in Section 6.6.3. Table 6.30 lists the usual member functions for iterators that maps and multimaps provide.

As for all associative container classes, the iterators are bidirectional (see Section 7.2.4, ). Thus, you can't use them in algorithms that are provided only for random access iterators (such as algorithms for sorting or random shuffling).

More important is the constraint that the key of all elements inside a map and a multimap is considered to be constant. Thus, the type of the elements is pair<const Key, T>. This is also necessary to ensure that you can't compromise the order of the elements by changing their keys. However, you can't call any modifying algorithm if the destination is a map or multimap. For example, you can't call the remove() algorithm to remove elements because it "removes" only by overwriting "removed" elements with the following arguments (see Section 5.6.2, for a detailed discussion of this problem). To remove elements in maps and multimaps, you can use only member functions provided by the container.

The following is an example of the use of iterators:

   std::map<std::string,float> coll;
   ...
   std::map<std::string,float>::iterator pos;
   for (pos = coll.begin(); pos != coll.end(); ++pos) {
       std::cout << "key: " << pos->first << "	"
                 << "value: " << pos->second << std::endl;
   }

Here, the iterator pos iterates through the sequence of string/float pairs. The expression

   pos->first

yields the key of the actual element, whereas the expression

   pos->second

yields the value of the actual element.^[27]

Trying to change the value of the key results in an error:

   pos->first = "hello";   // ERROR at compile time

However, changing the value of the element is no problem (as long as the type of the value is not constant):

   pos->second = 13.5;     // OK

To change the key of an element, you have only one choice: You must replace the old element with a new element that has the same value. Here is a generic function that does this:

// cont/newkey.hpp

   namespace MyLib {
       template <class Cont>
       inline
       bool replace_key (Cont& c,
                         const typename Cont::key_type& old_key,
                         const typename Cont::key_type& new_key)
       {
           typename Cont::iterator pos;
           pos = c.find(old_key);
           if (pos != c.end()) {
               //insert new element with value of old element
               c.insert(typename Cont::value_type(new_key,
                                                  pos->second));
               //remove old element
               c.erase(pos);
               return true;
           }
           else {
               //key not found
               return false;
           }
       }
   }

The insert() and erase() member functions are discussed in the next subsection.

To use this generic function you simply must pass the container the old key and the new key. For example:

   std::map<std::string,float> coll;
   ...
   MyLib::replace_key(coll,"old key","new key");

It works the same way for multimaps.

Note that maps provide a more convenient way to modify the key of an element. Instead of calling replace_key(), you can simply write the following:

//insert new element with value of old element
   coll["new_key"] = coll["old_key"];
   //remove old element
   coll.erase("old_key");

See Section 6.6.3, for details about the use of the subscript operator with maps.

   std::map<std::string,float> coll;
   ...
   if (coll.insert(std::make_pair("otto",22.3)).second) {
       std::cout << "OK, could insert otto/22.3" << std::endl;
   }
   else {
       std::cout << "Oops, could not insert otto/22.3 "
                 << "(key otto already exists)" << std::endl;
   }

   std::map<std::string,float> coll;
   ...
   //remove all elements with the passed key
   coll.erase(key);

   typedef std::multimap<string.float> StringFloatMMap;
   StringFloatMMap coll;
   ...
   //remove first element with passed key
   StringFloatMMap::iterator pos;
   pos = coll.find(key);
   if (pos != coll.end()) {
       coll.erase(pos);
   }

   typedef std::map<std::string,float> StringFloatMap;
   StringFloatMap coll;
   StringFloatMap::iterator pos;
   ...
   for (pos = coll.begin(); pos != coll.end(); ++pos) {
        if (pos->second == value) {
            coll.erase (pos);                   // RUNTIME ERROR !!!
        }
   }

   typedef std::map<std::string,float> StringFloatMap;
   StringFloatMap coll;
   StringFloatMap::iterator pos;
   ...
   for (pos = coll.begin(); pos != coll.end(); ) {
       if (pos->second == value) {
           pos = coll.erase(pos);  // would be fine, but COMPILE TIME ERROR
       }
       else {
           ++pos;
       }
   }

   typedef std::map<std::string,float> StringFloatMap;
   StringFloatMap coll;
   StringFloatMap::iterator pos;
   ...
   //remove all elements having a certain value
   for (pos = coll.begin(); pos != coll.end(); ) {
       if (pos->second == value) {
           coll.erase(pos++);
       }
       else {
           ++pos;
       }
   }

The following example shows the use of a map as an associative array. The map is used as a stock chart. The elements of the map are pairs in which the key is the name of the stock and the value is its price:

// cont/map1.cpp

   #include <iostream>
   #include <map>
   #include <string>
   using namespace std;

   int main()
   {
       /*create map/associative array
        *-keys are strings
        *-values are floats
        */
       typedef map<string,float> StringFloatMap;

       StringFloatMap stocks;      // create empty container
//insert some elements
       stocks["BASF"] = 369.50;
       stocks["VW"] = 413.50;
       stocks["Daimler"] = 819.00;
       stocks["BMW"] = 834.00;
       stocks["Siemens"] = 842.20;

       //print all elements
       StringFloatMap::iterator pos;
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           cout << "stock: " << pos->first << "	"
                << "price: " << pos->second << endl;
       }
       cout << endl;

       //boom (all prices doubled)
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           pos->second *= 2;
       }

       //print all elements
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           cout << "stock: " << pos->first << "	"
                << "price: " << pos->second << endl;
       }
       cout << endl;

       /*rename key from "VW" to "Volkswagen"
        *-only provided by exchanging element
        */
       stocks["Volkswagen"] = stocks["VW"];
       stocks.erase("VW");

       //print all elements
       for (pos = stocks.begin(); pos != stocks.end(); ++pos) {
           cout << "stock: " << pos->first << "	"
                << "price: " << pos->second << endl;
       }
   }

The program has the following output:

   stock: BASF price: 369.5
   stock: BMW price: 834
   stock: Daimler price: 819
   stock: Siemens price: 842.2
   stock: VW price: 413.5

   stock: BASF price: 739
   stock: BMW price: 1668
   stock: Daimler price: 1638
   stock: Siemens price: 1684.4
   stock: VW price: 827

   stock: BASF price: 739
   stock: BMW price: 1668
   stock: Daimler price: 1638
   stock: Siemens price: 1684.4
   stock: Volkswagen price: 827

The following example shows how to use a multimap as a dictionary:

// cont/mmap1.cpp

   #include <iostream>
   #include <map>
   #include <string>
   #include <iomanip>
   using namespace std;

   int main()
   {
       //define multimap type as string/string dictionary
       typedef multimap<string,string> StrStrMMap;

       //create empty dictionary
       StrStrMMap dict;

       //insert some elements in random order
       dict.insert(make_pair("day","Tag"));
       dict.insert(make_pair("strange","fremd"));
       dict.insert(make_pair("car","Auto"));
       dict.insert(make_pair("smart","elegant"));
       dict.insert(make_pair("trait","Merkmal"));
       dict.insert(make_pair("strange","seltsam"));
       dict.insert(make_pair("smart","raffiniert"));
       dict.insert(make_pair("smart","klug"));
       dict.insert(make_pair("clever","raffiniert"));

       //print all elements
       StrStrMMap::iterator pos;
       cout.setf (ios::left, ios::adjustfield);
       cout << ' ' << setw(10) << "english "
            << "german " << endl; 
       cout << setfill('-') << setw(20) << ""
            << setfill(' ') << endl;
       for (pos = dict.begin(); pos != dict.end(); ++pos) {
           cout << ' ' << setw(10) << pos->first.c_str()
                << pos->second << endl;
       }
       cout << endl;

       //print all values for key "smart"
       string word("smart");
       cout << word << ": " << endl;

       for (pos = dict.lower_bound(word);
            pos != dict.upper_bound(word); ++pos) {
               cout << " " << pos->second << endl;
       }

       //print all keys for value "raffiniert"
       word = ("raffiniert");
       cout << word << ": " << endl;
       for (pos = dict.begin(); pos != dict.end(); ++pos) {
           if (pos->second == word) {
               cout << " " << pos->first << endl;
           }
       }
   }

The program has the following output:

    english   german
   --------------------
    car       Auto
    clever    raffiniert
    day       Tag
    smart     elegant
    smart     raffiniert
    smart     klug
    strange   fremd
    strange   seltsam
    trait     Merkmal

   smart:
       elegant
       raffiniert
       klug
   raffiniert:
       clever
       smart

The following example shows how to use the global find_if() algorithm to find a element with a certain value:

// cont/mapfind.cpp

   #include <iostream>
   #include <algorithm>
   #include <map>
   using namespace std;

   /*function object to check the value of a map element
    */
   template <class K, class V>
   class value_equals {
     private:
       V value;
     public:
       //constructor (initialize value to compare with)
       value_equals (const V& v)
        : value(v) {
       }
       //comparison
       bool operator() (pair<const K, V> elem) {
           return elem.second == value;
       }
   };

   int main()
   {
       typedef map<float,float> FloatFloatMap;
       FloatFloatMap coll;
       FloatFloatMap::iterator pos;

       //fill container
       coll[1]=7;
       coll[2]=4;
       coll[3]=2;
       coll[4]=3;
       coll[5]=6;
       coll[6]=1;
       coll[7]=3;

       //search an element with key 3.0
       pos = coll.find (3.0);                     // logarithmic complexity
       if (pos != coll.end()) {
           cout << pos->first << ": "
                << pos->second << endl;
       }

       //search an element with value 3.0
       pos = find_if (coll.begin(),coll.end(),    // linear complexity
                      value_equals<float,float>(3.0));
       if (pos != coll.end()) {
           cout << pos->first << ": "
                << pos->second << endl;
       }
   }

The output of the program is as follows:

   3: 2
   4: 3

Using the noninvasive approach is simple. You only need objects that are able to iterate over the elements of an array by using the STL iterator interface. Actually, such iterators already exist: ordinary pointers. It was a design decision of the STL to use the pointer interface for iterators so that you could use ordinary pointers as iterators. This again shows the generic concept of pure abstraction: Anything that behaves like an iterator is an iterator. In fact, pointers are random access iterators (see Section 7.2.5,). The following example demonstrates how to use ordinary arrays as STL containers:

// cont/array1.cpp
   
   #include <iostream>
   #include <algorithm>
   #include <functional>
   using namespace std;

   int main()
   {
       int coll[] = { 5, 6, 2, 4, 1, 3 };
 
       //square all elements
       transform (coll, coll+6,          // first source
                  coll,                  // second source
                  coll,                  // destination
                  multiplies<int>());    // operation
//sort beginning with the second element
       sort (coll+1, coll+6);

       //print all elements
       copy (coll, coll+6,
             ostream_iterator<int>(cout," "));
       cout << endl;
   }

You must be careful to pass the correct end of the array, as it is done here by using coll+6. And, as usual, you have to make sure that the end of the range is the position after the last element.

The output of the program is as follows:

   25 1 4 9 16 36

Additional examples are on page 382 and page 421.

In his book The C++ Programming Language, 3rd edition, Bjarne Stroustrup introduces a useful wrapper class for ordinary arrays. It is safer and has no worse performance than an ordinary array. It also is a good example of a user-defined STL container. This container uses the wrapper approach because it offers the usual container interface as a wrapper around the array.

The class carray (the name is short for "C array" or for "constant size array") is defined as follows^[32]:

// cont/carray.hpp

   #include <cstddef>

   template<class T, std::size_t thesize>
   class carray {
     private:
       T v[thesize];    // fixed-size array of elements of type T

     public:
       //type definitions
       typedef T         value_type;
       typedef T*        iterator;
       typedef const T*  const_iterator;
       typedef T&        reference;
       typedef const T&  const_reference;
       typedef std::size_t    size_type;
       typedef std::ptrdiff_t difference_type;

       //iterator support
       iterator begin() { return v; }
       const_iterator begin() const { return v; }
       iterator end() { return v+thesize; }
       const_iterator end() const { return v+thesize; }

       //direct element access
       reference operator[](std::size_t i) { return v[i]; }
       const_reference operator[](std::size_t i) const { return v[i]; }

       //size is constant
       size_type size() const { return thesize; }
       size_type max_size() const { return thesize; }
 
       //conversion to ordinary array
       T* as_array() { return v; }
   };

Here is an example of the usage of the carray class:

// cont/carray1.cpp

   #include <algorithm>
   #include <functional>
   #include "carray.hpp"
   #include "print.hpp"
   using namespace std;

   int main()
   {
       carray<int,10> a;

       for (unsigned i=0; i<a.size(); ++i) {
           a[i] = i+1;
       }
       PRINT_ELEMENTS(a);

       reverse(a.begin(),a.end());
       PRINT_ELEMENTS(a);

       transform (a. begin(),a.end(),    // source
                  a. begin(),            // destination
                  negate<int>());        // operation
       PRINT_ELEMENTS(a);
   }

As you can see, you can use the general container interface operations (begin(), end(), and operator [ ]) to manipulate the container directly. Therefore, you can also use different operations that call begin() and end(), such as algorithms and the auxiliary function PRINT_ELEMENTS(), which is introduced on page 118.

The output of the program is as follows:

   1 2 3 4 5 6 7 8 9 10
   10 9 8 7 6 5 4 3 2 1
   −10 −9 −8 −7 −6 −5 −4 −3 −2 −1

size_type container::size () const

bool container::empty () const

size_type container::max_size () const

size_type container::capacity () const

void container::reserve (size_type num)

bool comparison (const container& c1, const container&, c2)

The member functions mentioned here are special implementations of corresponding STL algorithms that are discussed in Section 9.5 and Section 9.9. They provide better performance because they rely on the fact that the elements of associative containers are sorted. In fact, they provide logarithmic complexity instead of linear complexity. For example, to search for one of 1,000 elements, no more than ten comparisons on average are needed (see Section 2.3).

size_type container::count (const T& value) const

iterator container::find (const T& value)

const_iterator container::find (const T& value) const

iterator container::lower_bound (const T& value)

const_iterator container::lower_bound (const T& value) const

iterator container::upper_bound (const T& value)

const_iterator container::upper_bound (const T& value) const

pair<iterator,iterator> container::equal_range (const T& value)

pair<const_iterator,const_iterator> container::equal_range (const T& value) const

key_compare container::key_comp ()

value_compare container::value_comp ()