map vs unordered_map in C++ Standard Template Library (STL)

Map

Map is a data structure that store elements formed by a combination of a key and a value. In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content mapped to this key. In C++ map, no two entries can have same key. key is the unique identifier for an entry in map. Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion. The average and worst case time complexity for accessing a map element is logarithmic O(logn).

Unordered Map

Unordered map is a data structure that store elements formed by a combination of a key and a value. In C++ unordered_map, no two entries can have same key. key is the unique identifier for an entry in unordered_map. Internally, the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values (unlike map container), but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values (with a constant O(1) average time complexity and linear O(n)worst time complexity for accessing a map element).

To use STL map, you need to include <map> header.
To use STL unordered_map, you need to include <unordered_map> header.

Code

//
//  main.cpp
//  Map and Unordered Map (STL)
//
//  Created by Himanshu on 23/03/22.
//

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

void printUnorderedMap (unordered_map<string, int> myMap) {
    for (auto& it: myMap) {
        cout<<(it.first)<<": "<<(it.second)<<" ";
    }
    cout<<endl;
}

void printMap (map<string, int> myMap) {
    for (auto& it: myMap) {
        cout<<(it.first)<<": "<<(it.second)<<" ";
    }
    cout<<endl;
}

int main () {
    
    unordered_map<string, int> initUnorderedMap = { {"gamma", 3}, {"beta", 2}, {"alpha", 1} };
    map<string, int> initMap = { {"gamma", 1}, {"beta", 2}, {"alpha", 3} };
    
    unordered_map<string, int> myUnorderedMap;
    map<string, int> myMap;
    
    map<string, int>::iterator it;
    
    //Iterating over 'unordered_map'
    cout<<"initUnorderedMap elements:"<<endl;
    printUnorderedMap(initUnorderedMap);
    
    //Iterating over 'map'
    cout<<endl<<"initMap elements:"<<endl;
    printMap(initMap);
    
    cout<<"Elements in the initMap (map) container are kept sorted based on their key values"<<endl;
    
    initUnorderedMap.clear();
    //size of unordered_map after clear
    cout<<endl<<"Size of unordered_map after clear: "<<initUnorderedMap.size()<<endl;
    
    initMap.clear();
    //size of map after clear
    cout<<endl<<"Size of map after clear: "<<initMap.size()<<endl;
    
    myUnorderedMap.insert({"first", 30});
    myUnorderedMap["second"] = 20;
    myUnorderedMap["third"] = 10;
    
    myMap.insert({"first", 10});
    myMap["second"] = 20;
    myMap["third"] = 30;
    
    //Iterating over 'myUnorderedMap'
    cout<<endl<<"myUnorderedMap elements:"<<endl;
    printUnorderedMap(myUnorderedMap);
    
    //Iterating over 'myMap'
    cout<<endl<<"myMap elements:"<<endl;
    printMap(myMap);
    
    //Iterating over 'myUnorderedMap' after erase
    myUnorderedMap.erase("second");
    cout<<endl<<"myUnorderedMap elements after erase 'second': "<<endl;
    printUnorderedMap(myUnorderedMap);
    
    //Iterating over 'myMap' after erase
    myMap.erase(myMap.begin());
    cout<<endl<<"myMap elements after erase myMap.begin(): "<<endl;
    printMap(myMap);
    cout<<endl<<"Find operation on map and unordered_map:"<<endl;
    
    if (myUnorderedMap.find("second") != myUnorderedMap.end()) {
        cout<<"key 'second' is present in myUnorderedMap"<<endl;
    } else {
        cout<<"key 'second' is not present in myUnorderedMap"<<endl;
    }
    
    if (myMap.find("second") != myMap.end()) {
        cout<<"key 'second' is present in myMap"<<endl;
    } else {
        cout<<"key 'second' is not present in myMap"<<endl;
    }
    
    myMap.clear();
    
    myMap["a"] = 1;
    myMap["b"] = 2;
    myMap["c"] = 3;
    myMap["d"] = 4;
    myMap["e"] = 5;
    myMap["f"] = 6;
    myMap["g"] = 7;
    myMap["h"] = 8;
    
    //Iterating over 'myMap'
    cout<<endl<<"myMap new elements after clear:"<<endl;
    printMap(myMap);
    
    //Iterating over 'myMap' after erase on a range
    myMap.erase(myMap.find("f"), myMap.end());
    cout<<endl<<"myMap elements after erasing a range of elements:"<<endl;
    printMap(myMap);
    
    //Upper bound of "c" in myMap
    cout<<endl<<"(Upper bound method is only available for map but not for unordered_map) Upper bound of 'c' in myMap: ";
    cout<<((myMap.upper_bound("c"))->first)<<": "<<((myMap.upper_bound("c"))->second)<<endl;
    
    //Lower bound of "c" in myMap
    it  = myMap.lower_bound("c");
    cout<<endl<<"(Lower bound method is available for map but not for unordered_map) Lower bound of 'c' in myMap: ";
    cout<<it->first<<": "<<it->second<<endl;
    
    return 0;
}

Output

initUnorderedMap elements:
alpha: 1 beta: 2 gamma: 3 

initMap elements:
alpha: 3 beta: 2 gamma: 1 
Elements in the initMap (map) container are kept sorted based on their key values

Size of unordered_map after clear: 0

Size of map after clear: 0

myUnorderedMap elements:
third: 10 first: 30 second: 20 

myMap elements:
first: 10 second: 20 third: 30 

myUnorderedMap elements after erase 'second': 
third: 10 first: 30 

myMap elements after erase myMap.begin(): 
second: 20 third: 30 

Find operation on map and unordered_map:
key 'second' is not present in myUnorderedMap
key 'second' is present in myMap

myMap new elements after clear:
a: 1 b: 2 c: 3 d: 4 e: 5 f: 6 g: 7 h: 8 

myMap elements after erasing a range of elements:
a: 1 b: 2 c: 3 d: 4 e: 5 

(Upper bound method is available for map but not for unordered_map) Upper bound of 'c' in myMap: d: 4

(Lower bound method is available for map but not for unordered_map) Lower bound of 'c' in myMap: c: 3

Here’s a working example:
Ideone

Reference:
https://www.cplusplus.com/reference/map/map/

Leave a Reply

Your email address will not be published.