In the above example, if the key stackoverflow is already present, its value will be updated to 2. If it isn't already present, a new entry will be created.
Note that using the operator[] on the map will actually insert a new value with the queried key into the map. This means that you cannot use it on a const std::map, even if the key is already stored in the map. To prevent this insertion, check if the element exists (for example by using find()) or use at() as described below.
The insert() function returns a pair consisting of an iterator and a bool value:
If the insertion was successful, the iterator points to the newly inserted element, and the bool value is true.
If there was already an element with the same key, the insertion fails. When that happens, the iterator points to the element causing the conflict, and the bool is value is false.
The following method can be used to combine insertion and searching operation:
auto success = fruits_count.insert({"grapes",20});if(!success.second){// we already have 'grapes' in the map
success.first->second +=20;// access the iterator to update the value}
For convenience, the std::map container provides the subscript operator to access elements in the map and to insert new ones if they don't exist:
fruits_count["apple"]=10;
While simpler, it prevents the user from checking if the element already exists. If an element is missing, std::map::operator[] implicitly creates it, initializing it with the default constructor before overwriting it with the supplied value.
`insert()` can be used to add several elements at once using a braced list of pairs. This version of insert() returns void:
std::map<std::string, size_t> fruits_count;
std::string fruit;while(std::cin >> fruit){// insert an element with 'fruit' as key and '1' as value// (if the key is already stored in fruits_count, insert does nothing)auto ret = fruits_count.insert({fruit,1});if(!ret.second){// 'fruit' is already in the map ++ret.first->second;// increment the counter}}
Time complexity for an insertion operation is O(log n) because std::map are implemented as trees.
A pair can be constructed explicitly using make_pair() and emplace():
If we know where the new element will be inserted, then we can use emplace_hint() to specify an iterator hint. If the new element can be inserted just before hint, then the insertion can be done in constant time. Otherwise it behaves in the same way as emplace():
std::map< std::string ,int> runs;auto it = runs.emplace("Barry Bonds",762);// get iterator to the inserted element// the next element will be before "Barry Bonds", so it is inserted before 'it'
runs.emplace_hint(it,"Babe Ruth",714);
Searching in std::map or in std::multimap
There are several ways to search a key in std::map or in std::multimap.
To get the iterator of the first occurrence of a key, the `find()` function can be used. It returns `end()` if the key does not exist.
std::multimap<int,int> mmp{{1,2},{3,4},{6,5},{8,9},{3,4},{6,7}};auto it = mmp.find(6);if(it!=mmp.end())
std::cout << it->first <<", "<< it->second << std::endl;//prints: 6, 5else
std::cout <<"Value does not exist!"<< std::endl;
it = mmp.find(66);if(it!=mmp.end())
std::cout << it->first <<", "<< it->second << std::endl;else
std::cout <<"Value does not exist!"<< std::endl;// This line would be executed.
Another way to find whether an entry exists in `std::map` or in `std::multimap` is using the `count()` function, which counts how many values are associated with a given key. Since `std::map` associates only one value with each key, its `count()` function can only return 0 (if the key is not present) or 1 (if it is). For `std::multimap`, `count()` can return values greater than 1 since there can be several values associated with the same key.
std::map<int,int> mp{{1,2},{3,4},{6,5},{8,9},{3,4},{6,7}};if(mp.count(3)>0)// 3 exists as a key in map
std::cout <<"The key exists!"<< std::endl;// This line would be executed.else
std::cout <<"The key does not exist!"<< std::endl;
If you only care whether some element exists, find is strictly better: it documents your intent and, for multimaps, it can stop once the first matching element has been found.
In the case of std::multimap, there could be several elements having the same key. To get this range, the equal_range() function is used which returns std::pair having iterator lower bound (inclusive) and upper bound (exclusive) respectively. If the key does not exist, both iterators would point to end().
auto eqr = mmp.equal_range(6);auto st = eqr.first, en = eqr.second;for(auto it = st; it != en;++it){
std::cout << it->first <<", "<< it->second << std::endl;}// prints: 6, 5// 6, 7
Initializing a std::map or std::multimap
std::map and std::multimap both can be initialized by providing key-value pairs separated by comma. Key-value pairs could be provided by either {key, value} or can be explicitly created by std::make_pair(key, value). As std::map does not allow duplicate keys and comma operator performs right to left, the pair on right would be overwritten with the pair with same key on the left.
The container std::map has a member function empty(), which returns true or false, depending on whether the map is empty or not. The member function size() returns the number of element stored in a std::map container:
std::map<std::string ,int> rank {{"facebook.com",1},{"google.com",2},{"youtube.com",3}};if(!rank.empty()){
std::cout <<"Number of elements in the rank map: "<< rank.size()<< std::endl;}else{
std::cout <<"The rank map is empty"<< std::endl;}
Types of Maps
Regular Map
A map is an associative container, containing key-value pairs.
In the above example, std::string is the key type, and size_t is a value.
The key acts as an index in the map. Each key must be unique, and must be ordered.
If you need mutliple elements with the same key, consider using `multimap` (explained below)
If your value type does not specify any ordering, or you want to override the default ordering, you may provide one:
#include<string>#include<map>#include<cstring>structStrLess{booloperator()(const std::string& a,const std::string& b){returnstrncmp(a.c_str(), b.c_str(),8)<0;//compare only up to 8 first characters}}
std::map<std::string, size_t, StrLess> fruits_count2;
If StrLess comparator returns false for two keys, they are considered the same even if their actual contents differ.
Multi-Map
Multimap allows multiple key-value pairs with the same key to be stored in the map. Otherwise, its interface and creation is very similar to the regular map.
A hash map stores key-value pairs similar to a regular map. It does not order the elements with respect to the key though. Instead, a hash(opens new window) value for the key is used to quickly access the needed key-value pairs.
Unordered maps are usually faster, but the elements are not stored in any predictable order. For example, iterating over all elements in an unordered_map gives the elements in a seemingly random order.
std::map<int,int> m;auto it = m.begin();while(it != m.end()){if(pred(*it))
it = m.erase(it);else++it;}
Iterating over std::map or std::multimap
std::map or std::multimap could be traversed by the following ways:
std::multimap<int,int> mmp{{1,2},{3,4},{6,5},{8,9},{3,4},{6,7}};//Range based loop - since C++11for(constauto&x: mmp)
std::cout<< x.first <<":"<< x.second << std::endl;//Forward iterator for loop: it would loop through first element to last element//it will be a std::map< int, int >::iteratorfor(auto it = mmp.begin(); it != mmp.end();++it)
std::cout<< it->first <<":"<< it->second << std::endl;//Do something with iterator//Backward iterator for loop: it would loop through last element to first element//it will be a std::map< int, int >::reverse_iteratorfor(auto it = mmp.rbegin(); it != mmp.rend();++it)
std::cout<< it->first <<" "<< it->second << std::endl;//Do something with iterator
While iterating over a std::map or a std::multimap, the use of auto is preferred to avoid useless implicit conversions (see this SO answer(opens new window) for more details).
Creating std::map with user-defined types as key
In order to be able to use a class as the key in a map, all that is required of the key is that it be copiable and assignable.
The ordering within the map is defined by the third argument to the
template (and the argument to the constructor, if used). This
defaults to std::less<KeyType>, which defaults to the < operator,
but there's no requirement to use the defaults. Just write a comparison
operator (preferably as a functional object):
In C++, the "compare" predicate must be a strict weak ordering(opens new window). In particular, compare(X,X) must return false for any X. i.e. if CmpMyType()(a, b) returns true, then CmpMyType()(b, a) must return false, and if both return false, the elements are considered equal (members of the same equivalence class).
Strict Weak Ordering
This is a mathematical term to define a relationship between two objects.
Its definition is:
Two objects x and y are equivalent if both f(x, y) and f(y, x) are false. Note that an object is always (by the irreflexivity invariant) equivalent to itself.
In terms of C++ this means if you have two objects of a given type, you should return the following values when compared with the operator <.
X a;
X b;
Condition: Test: Result
a is equivalent to b: a < b false
a is equivalent to b b < a false
a is less than b a < b true
a is less than b b < a false
b is less than a a < b false
b is less than a b < a true
How you define equivalent/less is totally dependent on the type of your object.
Remarks
To use any of `std::map` or `std::multimap` the header file `
`std::map` and `std::multimap` both keep their elements sorted according to the ascending order of keys. In case of `std::multimap`, no sorting occurs for the values of the same key.
The basic difference between `std::map` and `std::multimap` is that the `std::map` one does not allow duplicate values for the same key where `std::multimap` does.
Maps are implemented as binary search trees. So `search()`, `insert()`, `erase()` takes Θ(log n) time in average. For constant time operation use `std::unordered_map`.
`size()` and `empty()` functions have Θ(1) time complexity, number of nodes is cached to avoid walking through tree each time these functions are called.