Sunday, February 2, 2014

map and multimap in c++

Map and Multimap c++: Standard Template Library Tutorial, ccplusplus.com
Map and multimap containers are containers that manage key/value pairs as elements. They sort their elements automatically according to a certain sorting criterion that is used for the actual key. The difference between the two is that multimaps allow duplicates, whereas maps do not (figure below).

Figure: Maps and Multimaps

To use a map or multimap, you must include the header file <map>:


There, the type is defined as a class template inside namespace std:


The first template argument is the type of the element's key, and the second template argument is the type of the element's value. The elements of a map or multimap may have any types Key and T that meet the following two requirements:
  1. The key/value pair must be assignable and copyable.
  2. The key must be comparable with the sorting criterion.
The optional third template argument defines the sorting criterion. Like sets, this sorting criterion must define a "strict weak ordering" The elements are sorted according to their keys, thus the value doesn't matter for the order of the elements. The sorting criterion is also used to check equality; that is, two elements are equal if neither key is less than the other. If a special sorting criterion is not passed, the default criterion less is used. The function object less sorts the elements by comparing them with operator <
The optional fourth template parameter defines the memory model. The default memory model is the model allocator, which is provided by the C++ standard library.

Abilities of Maps and Multimaps


Like all standardized associative container classes, maps and multimaps are usually implemented as balanced binary trees (figure below). The standard does not specify this but it follows from the complexity of the map and multimap operations. In fact, sets, multisets, maps, and multimaps typically use the same internal data type. So, you could consider sets and multisets as special maps and multimaps, respectively, for which the value and the key of the elements are the same objects. Thus, maps and multimaps have all the abilities and operations of sets and multisets. Some minor differences exist, however. First, their elements are key/value pairs. In addition, maps can be used as associative arrays.

Figure: Internal Structure of Maps and Multimaps

Maps and multimaps sort their elements automatically according to the element's keys. Thus they have good performance when searching for elements that have a certain key. Searching for elements that have a certain value promotes bad performance. Automatic sorting imposes an important constraint on maps and multimaps: You may not change the key of an element directly because this might compromise the correct order. To modify the key of an element, you must remove the element that has the old key and insert a new element that has the new key and the old value. As a consequence, from the iterator's point of view, the element's key is constant. However, a direct modification of the value of the element is still possible (provided the type of the value is not constant).

Map and Multimap Operations

Create, Copy, and Destroy Operations


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

Table:- Constructors and Destructors of Maps and Multimaps
Operation Effect
map c Creates an empty map/multimap without any elements
map c(op) Creates an empty map/multimap that uses op as the sorting criterion
map c1(c2) Creates a copy of another map/multimap of the same type (all elements are copied)
map c(beg,end) Creates a map/multimap initialized by the elements of the range [beg,end)
map c(beg,end,op) Creates a map/multimap with the sorting criterion op initialized by the elements of the range [beg,end)
c. ~map () Destroys all elements and frees the memory

Here, map may be one of the following:

Map Effect
map<Key,Elem> A map that sorts keys with less<> (operator <)
map<Key,Elem,Op> A map that sorts keys with Op
multimap<Key,Elem> A multimap that sorts keys with less<> (operator <)
multimap<Key,Elem,Op> A multimap that sorts keys with Op

You can define the sorting criterion in two ways:
  1. As a template parameter.
    For example:

    In this case, the sorting criterion is part of the type. Thus, the type system ensures that only containers with the same sorting criterion can be combined. This is the usual way to specify the sorting criterion. To be more precise, the third parameter is the type of the sorting criterion. The concrete sorting criterion is the function object that gets created with the container. To do this, the constructor of the container calls the default constructor of the type of the sorting criterion.
  2. As a constructor parameter.
    In this case you might have a type for several sorting criteria, and the initial value or state of the sorting criteria might differ. This is useful when processing the sorting criterion at runtime, or when sorting criteria are needed that are different but of the same data type. A typical example is specifying the sorting criterion for string keys at runtime.
If no special sorting criterion is passed, the default sorting criterion, function object less<>, is used. which sorts the elements by using operator <.


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


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. 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>.

Nonmodifying and Special Search Operations

Maps and multimaps provide the usual nonmodifying operations - those that query size aspects and make comparisons (table below).

Table :- Nonmodifying Operations of Maps and Multimaps
Operation Effect
c.size() Returns the actual number of elements
c.empty() Returns whether the container is empty (equivalent to size()==0, but might be faster)
c.max_size() Returns the maximum number of elements possible
c1 == c2 Returns whether c1 is equal to c2
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to !(c1==c2))
c1 < c2 Returns whether c1 is less than c2
c1 > c2 Returns whether c1 is greater than c2 c2<c1)
c1 <= c2 Returns whether c1 is less than or equal to c2 (equivalent to !(c2<c1))
c1 >= c2 Returns whether c1 is greater than or equal to c2 (equivalent to !(c1<c2))

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:


To check whether a container is less than another container is done by a lexicographical comparison. To compare containers of different types (different sorting criterion),

Special Search Operations

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

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:


Table :- Special Search Operations of Maps and Multimaps
Operation Effect
count(key) Returns the number of elements with key key
find(key) Returns the position of the first element with key key or end()
lower_bound(key) Returns the first position where an element with key key would get inserted (the first element with key >= key)
upper_bound(key) Returns the last position where an element with key key would get inserted (the first element with key > key)
equal_range(key) Returns the first and last positions where elements with key key would get inserted (the range of elements with key == key)

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. 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.

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. 

Assignments

Maps and multimaps provide only the fundamental assignment operations that all containers provide (table below)

Table :- Assignment Operations of Maps and Multimaps
Operation Effect
c1 = c2 Assigns all elements of c2 c1
c1.swap(c2) Swaps the data of c1 and c2
swap(c1,c2) Same (as global function)

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. If the criteria are different, they also get assigned or swapped. 

Iterator Functions and Element Access

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. Table below lists the usual member functions for iterators that maps and multimaps provide.

Table 6.30. Iterator Operations of Maps and Multimaps
Operation Effect
c.begin() Returns a bidirectional iterator for the first element (keys are considered const)
c.end() Returns a bidirectional iterator for the position after the last element (keys are considered const)
c.rbegin() Returns a reverse iterator for the first element of a reverse iteration
c.rend() Returns a reverse iterator for the position after the last element of a reverse iteration

As for all associative container classes, the iterators are bidirectional. 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. 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:


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


yields the key of the actual element, whereas the expression


yields the value of the actual element.

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


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


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:


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:


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:


Inserting and Removing Elements

Table below shows the operations provided for maps and multimaps to insert and remove elements.

Table :- Insert and Remove Operations of Maps and Multimaps
Operation Effect
c.insert(elem) Inserts a copy of elem and returns the position of the new element and, for maps, whether it succeeded
c.insert(pos,elem) Inserts a copy of elem and returns the position of the new element (pos is used as a hint pointing to where the insert should start the search)
c.insert(beg,end) Inserts a copy of all elements of the range [beg,end)(returns nothing)
c.erase(elem) Removes all elements with value elem and returns the number of removed elements
c.erase(pos) Removes the element at iterator position pos (returns nothing)
c.erase(beg,end) Removes all elements of the range [beg,end)(returns nothing)
c.clear() Removes all elements (makes the container empty)

In particular, the return types of these operations have the same differences as they do for sets and multisets. However, note that the elements here are key/value pairs. So, the use is getting a bit more complicated.

To insert a key/value pair, you must keep in mind that inside maps and multimaps the key is considered to be constant. You either must provide the correct type or you need to provide implicit or explicit type conversions. There are three different ways to pass a value into a map:
  1. Use value_type
    To avoid implicit type conversion, you could pass the correct type explicitly by using value_type, which is provided as a type definition by the container type. For example:


  2. Use pair<>
    Another way is to use pair<> directly. For example:


    In the first insert() statement the type is not quite right, so it is converted into the real element type. For this to happen, the insert() member function is defined as a member template.
  3. Use make_pair()
    Probably the most convenient way is to use the make_pair() function. This function produces a pair object that contains the two values passed as arguments:


    Again, the necessary type conversions are performed by the insert() member template.
Here is a simple example of the insertion of an element into a map that also checks whether the insertion was successful:


To remove an element that has a certain value, you simply call erase():


This version of erase() returns the number of removed elements. When called for maps, the return value of erase() can only be 0 or 1.

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


You should use the member function find() instead of the find() algorithm here because it is faster. However, you can't use the find() member functions to remove elements that have a certain value (instead of a certain key).

When removing elements, be careful not to saw off the branch on which you are sitting. There is a big danger that will you remove an element to which your iterator is referring. For example:


Calling erase() for the element to which you are referring with pos invalidates pos as an iterator of coll. Thus, if you use pos after removing its element without any reinitialization, then all bets are off. In fact, calling ++pos results in undefined behavior.

A solution would be easy if erase() always returned the value of the following element:


It was a design decision not to provide this trait, because if not needed, it costs unnecessary time. I don't agree with this decision however, because code is getting more error prone and complicated (and may cost even more in terms of time).

Here is an example of the correct way to remove elements to which an iterator refers:


Note that pos++ increments pos so that it refers to the next element but yields a copy of its original value. Thus, pos doesn't refer to the element that is removed when erase() is called.

Using Maps as Associative Arrays


Associative containers don't typically provide abilities for direct element access. Instead, you must use iterators. For maps, however, there is an exception to this rule. Nonconstant maps provide a subscript operator for direct element access (table below). However, the index of the subscript operator is not the integral position of the element. Instead, it is the key that is used to identify the element. This means that the index may have any type rather than only an integral type. Such an interface is the interface of a so-called associative array.

Table :- Direct Element Access of Maps with Operator [ ]
Operation Effect
m[key] Returns a reference to the value of the element with key key Inserts an element with key if it does not yet exist

The type of the index is not the only difference from ordinary arrays. In addition, you can't have a wrong index. If you use a key as the index, for which no element yet exists, a new element gets inserted into the map automatically. The value of the new element is initialized by the default constructor of its type. Thus, to use this feature you can't use a value type that has no default constructor. Note that the fundamental data types provide a default constructor that initializes their values to zero.

This behavior of an associative array has both advantages and disadvantages:
  • The advantage is that you can insert new elements into a map with a more convenient interface.
    For example:


    The statement


    is processed here as follows:
    1. Process coll["otto"] expression:
      • If an element with key "otto" exists, the expression returns the value of the element by reference.
      • If, as in this example, no element with key "otto" exists, the expression inserts a new element automatically with "otto" as key and the value of the default constructor of the value type as the element value. It then returns a reference to that new value of the new element.
    2. Assign value 7.7:
      • The second part of the statement assigns 7.7 to the value of the new or existing element.
    The map then contains an element with key "otto" and value 7.7.
  • The disadvantage is that you might insert new elements by accident or mistake. For example, the following statement does something you probably hadn't intended or expected:


    It inserts a new element with key "ottto" and prints its value, which is 0 by default. However, it should have generated an error message telling you that you wrote "otto" incorrectly.
    Note, too, that this way of inserting elements is slower than the usual way for maps. This is because the new value is first initialized by the default value of its type, which is then overwritten by the correct value.

Exception Handling


Maps and multimaps provide the same behavior as sets and multisets with respect to exception safety. This behavior is mentioned on page 185.

Examples of Using Maps and Multimaps


Using a Map as an Associative Array


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:


The program has the following output:


Using Multimap as a  Directory

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


The program has the following output:



Find Elements with Certain Values

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


The output of the program is as follows:


Example with Maps, Strings, and Sorting Criterion at Runtime

Here is another example. It is for advanced programmers rather than STL beginners. You can take it as an example of both the power and the snags of the STL. In particular, this example demonstrates the following techniques:
  • How to use maps
  • How to write and use function objects
  • How to define a sorting criterion at runtime
  • How to compare strings in a case-insensitive way


main() creates two containers and calls fillAndPrint() for them. fillAndPrint() fills the containers with the same elements and prints the contents of them. However, the containers have two different sorting criteria:
  1. coll1 uses the default function object of type RuntimeStringCmp, which compares the elements by using operator <.
  2. coll2 uses a function object of type RuntimeStringCmp that is initialized by value nocase of class RuntimeStringCmp. nocase forces this function object to sort strings in a case-insensitive way.
The program has the following output:


The first block of the output prints the contents of the first container that compares with operator <. The output starts with all uppercase keys followed by all lowercase keys.


The second block prints all case-insensitive items, so the order changed. But note, the second block has one item less. This is because the uppercase word "Unternehmen" is, from a case-insensitive point of view, equal to the lowercase word "unternehmen," and we use a map that does not allow duplicates according to its comparison criterion. Unfortunately the result is a mess because the German key that is the translation for "enterprise" got the value "undertake." So probably a multimap should be used here. This makes sense because a multimap is the typical container for dictionaries.








-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

No comments:

Post a Comment