Skip to main content

map

map is a SORTED Associative Container that contains key-value pairs with unique keys.

  • Keys are sorted.
  • Search, removal, and insertion operations have logarithmic complexity.
  • Maps are usually implemented as red-black trees.

Declaration​

map<int, int> mp;

Initialisation​

map<int, int> m;
m[1] = 5;  // [(1, 5)]
m[3] = 14;  // [(1, 5); (3, 14)]
m[2] = 7;  // [(1, 5); (2, 7); (3, 14)]
m[0] = -1;  // [(0, -1); (1, 5); (2, 7); (3, 14)]

Printing map​

for (const auto &it : m) {
    cout << it.first << " " << it.second << endl;
}
for (auto el:mapName)
{
  cout << mapName.first << ", " << mapName.second << endl;
}

map Methods​

Element access​

at()​

  • in map at() doesn't really have any advantage so better use [] for map

access specified element with bounds checking

caution

only use at() for accessing elements NOT FOR giving values like this mp.at("hey") = "hello"; as it will ERROR

ERROR for mp.at(
terminate called after throwing an instance of 'std::out_of_range'
  what():  map::at

operator[]​

  • use [] for assigning values

Lookup - binary_search() Alternatives​

caution
  • use find() for search element's Index No.
  • use contains() for checking element present or not: ⇢⇢ ☠️ Don't use binary_search() ☠️
    • returns true or false ~~ from C++ 20
  • use count() for checking element present or not: ⇢⇢ ☠️ Don't use binary_search() ☠️
    • returns 1 or 0

💣 binary_search() from STL MUST not be used with set, multiset, map, multimap. 💣​

  • binary_search() becomes O(n) when used with set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, unordered_multimap.

  • All the Associative Containers have O(log n) alternative of binary_search() ↠

    • find() for IndexNo. of target search element

    • contains() for element present or not -- true or false

    • count() for element present or not -- 1 or 0

    • lower_bound() ⇢ container's own lower_bound()

    • upper_bound() ⇢ container's own upper_bound()

    • equal_range() ⇢ container's own equal_range()

      unordered_set, unordered_multiset, unordered_map, unordered_multimap don't have lower_bound() , upper_bound()

Hence, binary_search() must not be used with Associative Containers

tip

  • https://discuss.codechef.com/t/set-find-vs-binary-search-help-needed-asap/23991/6

  • binary_search has a logarithmic time complexity only for LegacyRandomAccessIterators . This is the case of std::vector iterators, for example. Sets/multisets are trees, so their iterators don’t allow random access. This makes binary_search() run in linear time, which is significantly slower for a large range. This is why std::set and std::multiset have a “find” function, while vector doesn’t. They need their own binary search implementation to be able to run in logarithmic time.

  • For instance, if your range spans over 1000 elements, binary_search() will want to look at the element at position 500 first. Vector iterators are more or less pointers, it’s easy to do begin + 500 with pointer arithmetics. Since the elements are sorted, we can remove half of the range with a single comparison. That’s why binary_search() is very efficient, with logarithmic complexity.

  • ❎ BUT, In a set or multiset, nodes that are neighbors in the tree are not necessarily neighbors in memory. So, binary_search() would not even be able to know how many elements are in the range, end - begin is not supported. So the search starts at begin the iterator is incremented, until it reaches a value not lower than the one we are searching for. This is why binary_search() has poor performance with sets, and you should use the find() function provided by that particular container, that has a more suitable search strategy.

find()​

caution

Time Complexity is :~ O(log n)​

count()​

caution

Time Complexity is :~ O(log n)​

tip
  • count() returns 1 if the set or map contains the element and 0 if it doesn't.

contains() ~~ C++ 20​

caution

Time Complexity is :~ O(log n)​

  • contains() returns true if the set or map contains the element and false if it doesn't.

upper_bound()​

lower_bound()​

Modifiers​

clear()​

clears the contents

insert()​

insert_or_assign​

inserts an element or assigns to the current element if the key already exists

emplace()​

constructs element in-place

emplace_hint()​

constructs elements in-place using a hint

try_emplace()​

inserts in-place if the key does not exist, does nothing if the key exists

erase()​

erases elements

swap()​

swaps the contents

extract()​

extracts nodes from the container

merge()​

splices nodes from another container

map based Problems​

// 💣💣💣💣TO TRY 💣💣💣💣

unordered_map<int,int> unmap;
for(int i=0 ; i<nums.size() ; i++){
    unmap[nums[i]]++;
    if(unmap[nums[i]] >= 2) return true;
}
return false;