C++ Maps & Multimaps STL

C++ Maps are sorted associative containers that contain unique key/value pairs. For example, you could create a map that associates a string with an integer, and then use that map to associate the number of days in each month with the name of each month.

Map Operators

  • begin - returns an iterator to the beginning of the map
  • clear - removes all elements from the map
  • count - returns the number of elements matching a certain key
  • empty - true if the map has no elements
  • end - returns an iterator just past the last element of a map
  • equal_range - returns iterators to the first and just past the last elements matching a specific key
  • erase - removes elements from teh map
  • find - returns an iterator to specific elements
  • insert - insert items into a map
  • key_comp - returns the function that compares keys
  • lower_bound - returns an iterator to the first element greater than or equal to a certain value
  • max_size - returns the maximum number of elements the map can hold
  • rbegin - returns a reverse_iterator to the end of the map
  • rend - returns a reverse_iterator to the beginning of the map
  • size - returns the number of items in the map
  • swap - swap the contests of this map with another
  • upper_bound - returns an iterator to the first element greater than a certain value
  • value_comp - returns the functions that compares values
C++ Multimaps are like maps, in that they are sorted associative containers, but differ from maps in that they allow duplicate keys.

Multimap Operators

  • begin - returns an iterator to the beginning of the multimap
  • clear - removes all elements from the multimap
  • count - returns the number of elements matching a certain key
  • empty - true if the multimap has no elements
  • end - returns an iterator just past the last element of a multimap
  • equal_range - returns iterators to the first and just past the last elements matching a specific key
  • erase - removes elements from a multimap
  • find - returns an iterator to specific elements
  • insert - inserts items into a multimap
  • key_comp - returns the function that compares keys
  • lower_bound - returns an iterator to the first element greater than or equal to a certain value
  • max_size - returns the maximum number of elements that the multimap can hold
  • rbegin - returns a reverse_iterator to the end of the multimap
  • rend - returns a reverse_iterator to the beginning of the multimap
  • size - returns the number of items in the multimap
  • swap - swap the contents of the multimap with another
  • upper_bound - returns an iterator to the first element greater than a certain value
  • value_comp - returns the function that compares values
The implementation of the Multimap is the same as that of Maps.

Below is the implementation of the Map Operators. Let us start by creating a map object first...

begin()

  • The function begin() returns an iterator to the first element of the map. begin() should run in constant time.

end()

  • The end() function returns an iterator just past the end of the map.
  • Note that before you can access the last element of the map using an iterator that you get from a call to end(), you'll have to decrement the iterator first.


#include <iostream>
#include <map>
using namespace std;
int main() {
// Creating maps with String mapped to Number.
        // Here we will be mapping day
// to day number.
map<string, int> day;
// To add elements to the map we can use [] Operator.
day["Monday"] = 1;
day["Tuesday"] = 2;
day["Wednesday"] = 3;
day["Thrusday"] = 4;
day["Friday"] = 5;
day["Saturday"] = 6;
day["Sunday"] = 7;
// Printing all the element from the map.
// Maps can't be iterated like we iterate in contiguous 
        // array.
map<string, int>::iterator iter;
for (iter = day.begin(); iter != day.end(); iter++) {
cout << iter->first << " " << iter->second << "\n";
}
return 0;
}

Output:


Friday 5
Monday 1
Saturday 6
Sunday 7
Thrusday 4
Tuesday 2
Wednesday 3


Now we will be looking into clear() and empty()

clear() 

  • The function clear() deletes all of the elements in the map. clear() runs in linear time.

empty() 

  • The empty() function returns (1)true if the map has no elements, (0)false otherwise.

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

int main() {
map<string, int> day;
day["Monday"] = 1; // adds one element.
cout << "Is map is empty: " << day.empty() << "\n"; // 0-false/1-true
// clearing all the element from the map.
day.clear();
cout << "Is map is empty: " << day.empty() << "\n";
return 0;
}

Output:


Is map is empty: 0
Is map is empty: 1

Now let us use count(), size(), and max_size().

count() 

  • The function count() returns the number of occurrences of key in the map. count() runs in logarithmic time.
size()
  • The size() function returns the number of elements in the current map.

max_size()

  • The max_size() function returns the maximum number of elements that the map can  hold before more memory will have to be allocated, respectively.

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

int main() {
// Creating maps with String mapped to Number. Here we will be mapping day
// to day number.
map<string, int> day;
day["Monday"] = 1;
day["Tuesday"] = 2;
day["Wednesday"] = 3;
day["Thrusday"] = 4;
day["Friday"] = 5;
day["Saturday"] = 6;
day["Sunday"] = 7;

// Counting the number of items present in the map.
cout << "Number of element present in the map: " << day.size() << "\n";
cout << "Number of element the this map can hold: " << day.max_size()
<< "\n"; // Depends in your system memory availability.
cout << "Number of Monday present in Map: " << day.count("Monday")
<< "\n"; // duplicate key can't be present so it will
// return 0-if key is present/ 1-if key is not present.
return 0;
}

Output:


Number of element present in the map: 7
Number of element the this map can hold: 288230376151711743
Number of Monday present in Map: 1

Now let us learn about some more interesting things in maps erase(), find() and insert():

insert()

  • inserts pair<key,val>, but only if no element with the key key already exists. The return value is an iterator to the element inserted (or an existing pair with key key), and a boolean which is true if an insertion took place.

find() 

  • The find() function returns an iterator to key, or an iterator to the end of the map if key is not found. find() runs in logarithmic time.

erase()

  • The erase function() either erases the element at pos, erases the elements between start and end, or erases all elements that have the value of key.

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

int main() {
map<string, int> day;

// To add element into the map we can also use insert().
// Data are Lexicographically Sorted by default.
day.insert(make_pair("Monday", 1));
day.insert(make_pair("Tuesday", 2));
day.insert(make_pair("Wednesday", 3));
day.insert(make_pair("Thrusday", 4));
day.insert(make_pair("Friday", 5));

// Now we will be printing all the data present in the map "day" using
// iterator.
map<string, int>::iterator iter;
for (iter = day.begin(); iter != day.end(); iter++) {
cout << iter->first << " has day number: " << iter->second << "\n";
}

// The find() function returns an iterator to key, or an iterator to the end
// of the map if key is not found.
iter = day.find("Friday");
cout << "Found '" << iter->first << "' having Value:" << iter->second
<< "\n";

// Erasing the whole data from the map
map<string, int>::iterator niter;
while (!day.empty()) {
niter = day.begin();
cout << "Erasing :" << niter->first << " " << niter->second << "\n";
day.erase(niter);
}
// Checking the presence of element in the Map "day"
cout << "Is map 'day' is empty: " << day.empty() << "\n";
return 0;
}

Output:


Friday has day number: 5
Monday has day number: 1
Thrusday has day number: 4
Tuesday has day number: 2
Wednesday has day number: 3
Found 'Friday' having Value:5
Erasing :Friday 5
Erasing :Monday 1
Erasing :Thrusday 4
Erasing :Tuesday 2
Erasing :Wednesday 3
Is map 'day' is empty: 1

Now let us talk about lower_bound() and upper_bound()

lower_bound() 

  • The lower_bound() function returns an iterator to the first element which has a value greater than or equal to key. lower_bound() runs in logarithmic time.

upper_bound() 

  • The function upper_bound() returns an iterator to the first element in the map with a key greater than key.

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


int main() {
map<string, int> day;
// Inserting element into the map 'day'.
day["Monday"] = 1;
day["Tuesday"] = 2;
day["Wednesday"] = 3;
day["Thrusday"] = 4;
day["Friday"] = 5;
day["Saturday"] = 6;
day["Sunday"] = 7;


map<string, int>::iterator iter;
// lower_bound() function returns an iterator to the first element which has
// a value greater than or equal to key.
iter = day.lower_bound("Monday");
cout << "Lower bound for Monday: " << iter->first << " " << iter->second
<< "\n";
iter = day.lower_bound("Moon"); // find lower bound from lexicographically
// arranged map same for upper_bound().
cout << "Lower bound for Moon: " << iter->first << " " << iter->second
<< "\n\n";


// upper_bound() returns an iterator to the first element in the map with a
// key greater than key.
iter = day.upper_bound("Monday");
cout << "Upper bound for Monday: " << iter->first << " " << iter->second
<< "\n";
iter = day.upper_bound("Moon");
cout << "Upper bound for Moon: " << iter->first << " " << iter->second
<< "\n";

return 0;
}

Output:


Lower bound for Monday: Monday 1
Lower bound for Moon: Saturday 6

Upper bound for Monday: Saturday 6
Upper bound for Moon: Saturday 6

The related articles which you should read after this article.

  • Introduction to Hash Table
  • Collision handling and Hash Table Implementation in C++.


If there is any error or you have any doubt in the article then do ask us through the comment, we will be happy to help you.


If you think that this article has helped you to learn something then do share this with your friends.

Thank You for Reading