Maps and multimaps

A map container stores two different items, a key and a value, and it maintains the items in an sort order according to the key. A sorted map means that it is quick to locate an item. The class has the same interface as other containers to add items: you can put them into the container via the constructor, or you can use member methods insert and emplace. You also have access to items via iterators. Of course, an iterator gives access to a single value, so with a map this will be to a pair object that has both the key and the value:

    map<string, int> people; 
    people.emplace("Washington", 1789); 
    people.emplace("Adams", 1797); 
    people.emplace("Jefferson", 1801); 
    people.emplace("Madison", 1809); 
    people.emplace("Monroe", 1817); 

    auto it = people.begin(); 
    pair<string, int> first_item = *it; 
    cout << first_item.first << " " << first_item.second << endl;

The calls to emplace puts items into the map where the key is a string (the name of a president) and the value is an int (the year the president started their term of office). The code then obtains an iterator to the first item in the container, and the item is accessed by dereferencing the iterator to give a pair object. Since the items are stored in the map in a sorted order, the first item will be set to "Adams". You can also insert items as pair objects, either as objects or through iterators to pair objects in another container using the insert method.

Most of the emplace and insert methods will return a pair object of the following form, where the iterator type is relevant to the map:

    pair<iterator, bool>

You use this object to test for two things. First, the bool indicates if the insertion was successful (it will fail if an item with the same key is already in the container). Secondly, the iterator part of the pair either indicates the position of the new item or it indicates the position of the existing item that will not be replaced (and will cause the insertion to fail).

The failure depends on equivalence rather than equality. If there is an item with a key that is equivalent to the item you are trying to insert, then the insertion will fail. The definition of equivalence depends on the comparator predicate being used with the map object. So, if the map uses a predicate comp, then equivalence between the two items, a and b, is determined by testing !comp(a,b) && !comp(b,a). This is not the same as testing for (a==b).

Assuming the previous map object, you can do this:

    auto result = people.emplace("Adams", 1825); 
    if (!result.second) 
       cout << (*result.first).first << " already in map" << endl;

The second item in the result variable is tested to see if the insertion was successful, and if not, then the first item is an iterator to a pair<string,int>, which is the existing item, and the code dereferences the iterator to get the pair object and then prints out the first item, which is the key (in this case, the name of the person).

If you know where in the map the item should go, then you can call emplace_hint:

    auto result = people.emplace("Monroe", 1817); 
    people.emplace_hint(result.first, "Polk", 1845);

Here we know that Polk comes after Monroe so we can pass the iterator to Monroe as the hint. The class gives access to items via iterators, so you can use ranged for (which is based on iterator access):

    for (pair<string, int> p : people) 
    { 
        cout << p.first << " " << p.second << endl; 
    }

In addition, there is access to individual items using the at method and the [] operator. In both cases the class will search for an item with the provided key and if the item is found, a reference to the item's value is returned. The at method and the [] operator behave differently in a situation where there is no item with the specified key.

If the key does not exist, the at method will throw an exception; if the [] operator cannot find the specified key, it will create a new item using the key and calling the default constructor of the value type. The [] operator will return a reference to the value if the key exists, so you can write code like this:

    people["Adams"] = 1825; 
    people["Jackson"] = 1829;

The second line behaves as you expect: there will be no item with a key of Jackson, so the map will create an item with that key, initialize it by calling the default constructor of the value type (int, so the value is initialized to zero), and then it returns a reference to this value, which is assigned a value of 1829. The first line, however, will look up Adams, see that there is an item, and return a reference to its value, which is then assigned a value of 1825. There is no indication that the value of an item has been changed as opposed to a new item being inserted. You may want this behavior in some circumstances, but it is not the intention in this code, where, clearly, an associative container that allows duplicate keys (such as multimap) is needed. Furthermore, in both of these cases, there is a search for the key, a reference is returned, and then an assignment is performed. Be aware that, although it is valid to insert items this way, it is more efficient to emplace a new key-value pair in the container because you do not have this extra assignment.

Once you have filled the map you can search for a value using the following:

• The at method, which is passed a key and returns a reference to the value for that key
• The [] operator, which when passed a key returns a reference to the value for that key
• The find function, which will use the predicate specified in the template (unlike the global find function, mentioned later) and it will give you an iterator to the entire item as a pair object
• The begin method will give you an iterator to the first item and the end method will give you an iterator after the last item
• The lower_bound method returns an iterator to the item that has a key equalto or greater than the key that you pass as a parameter
• The upper_bound method returns an iterator of the first item in the map that has a key greater than the key provided
• The equal_range method returns both the lower and upper bounds values in a pair object