unordered_map vs map in C++

map (like set) is an ordered sequence of unique keys whereas in unordered_map key can be stored in any order, so unordered.

The time complexity of map operations is O(logN) while for unordered_map, It is O(1) on average.

Let us see the differences in a tabular (표로 산출된) form. 

 

# About unordered_map

unordered_map is an associated container that stores elements formed by the combination of key-value , and a mapped value. 

The key value is used to uniquely identify the element and the mapped value is the content associated with the key. 

Both key and value can be of any type predefined or user-defined. 

Internally (내부적으로) unordered_map is implemented using Hash Table.

The cost of search / insert / delete from the hash table is O(1).  (Time complexity)

// C++ program to demonstrate functionality of unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;
 
int main()
{
    // Declaring umap to be of <string, int> type
    // key will be of string type and mapped value will
    // be of int type
    unordered_map<string, int> umap;
 
    // inserting values by using [] operator
    umap["GeeksforGeeks"] = 10;
    umap["Practice"] = 20;
    umap["Contribute"] = 30;
 
    // Traversing an unordered map
    for (auto x : umap)
    cout << x.first << " " << x.second << endl;
 
}
 

int main() {
    unordered_map<string, double> umap;
    
    // inserting values by using [] operator.
    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap["root3"] = 1.732;
    umap["log10"] = 2.302;
    umap["loge"] = 1.0;
    
    // inserting value by 'insert' function.
    umap.insert(make_pair("e", 2.718));
    
    string key = "PI";
    
    // If key not found in map iterator to end is returned.!
    if(umap.find(key) == umap.end())
        cout << key << " not found...\n\n";
        
    // If key found then iterator to that key is returned
    else
        cout << "FOUND " << key << "\n\n";
 
    key = "lambda";
    if (umap.find(key) == umap.end())
        cout << key << " not found .. \n";
    else
        cout << "FOUND! " << key << '\n';
        
    // iterating over all value of umap
    unordered_map<string, double>:: iterator itr;
    cout << "\n ALL Elements : \n";
    for(itr = umap.begin(); itr != umap.end(); itr++)
        cout << itr->first << " " << itr->second << '\n';
    
 
    return 0;
}

void printFrequencies(const string &str)
{
    unordered_map<string, int> wordFreq;
    
    // breaking input into word using string stream
    stringstream ss(str);   // Used for breaking words.
    string word;  // To store individual words.
    while(ss >> word) wordFreq[word]++;
    
    unordered_map<string, int>:: iterator p;
    for(p = wordFreq.begin(); p != wordFreq.end(); p++)
        cout << "(" << p->first << ", " << p->second << ")\n";    
    
}
 
int main() {
    string str = "geeks for geeks geeks quiz "
                 "practice qa for";
    printFrequencies(str);
 
    return 0;
}