map vs unordered_map in C++

 unordered_map will be used in the following conditions :

  1. Want to store it as key-value pairs.
  2. All the operations should take 0(1) time as this is implemented using hash-map.
  3. How many substrings reappear in a given string? 
  4. Most of the pairing problems.
  5. Elements in the unordered_map is not sorted in any particular order either by key or by value 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 average time complexity on average)

Declaration 

unordered_map <string, int> umap;

Insertion 

Method 1: (string, int)

string t = "Unordered";
umap[t]++;

Method 2: (string, int)

    umap["Containers"] = 10;
    umap["are"] = 20;
    umap["good"] = 30;

Method 3: (string, int)

umap.insert(make_pair("STL", 2));

Method 4: (string, int)

    stringstream ss(str);  // Used for breaking words
    string word; // To store individual words
    while (ss >> word)
        umap[word]++;

Updation

If we try to insert a new element in the existing key, the new element will be updated replacing the old value mapped to the key.

Click here to lear Contains duplicate II program using this approach.

Deletion 

Method 1: By iterator


   // erase by iterator
    cout << "After erasing by Iterator : \n";
    umap.erase(umap.begin());

Method 2: By value

    // erase by value
    cout << "After erasing by Key : \n";
    umap.erase(4189);

Method 3: By range

    // erase by range
    cout << "After erasing by Range : \n";
    auto it = umap.begin();
    it++; // Returns iterator pointing to second element
    umap.erase(it, umap.end());

The order of the elemetns that are not erased is preserved. This further makes it possible to erase individual elements while iterating through the container. 

Searching O(n) 

Method 1: (string, int)

    string key = "STL";
 
    // 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";

Displaying  

Method 1: auto (C++11)

for (auto t : umap) {
     cout << " t map " << t.first << "   " <<  t.second << endl;
}

Click here to know this usage.

Method 2: iterator (C++98)

    unordered_map<string, int>:: iterator itr;
    cout << "\nAll Elements : \n";
    for (itr = umap.begin(); itr != umap.end(); itr++)
    {
        // itr works as a pointer to pair<string, int>
        // type itr->first stores the key part  and
        // itr->second stores the value part
        cout << itr->first << "  " << itr->second << endl;
     }

Method 3: iterator using auto 

    for (auto itr = umap.begin(); itr != umap.end(); itr++) {
        cout << itr->first << "  " << itr->second << endl;
    }

Method 4: key, value pair (C++17)

    for (const auto& [key, value] : m) {
        std::cout << '[' << key << "] = " << value << "; ";
    }

Unordered map with User defined data type

https://stackoverflow.com/questions/17016175/c-unordered-map-using-a-custom-class-type-as-the-key

Real time Application - Phonebook

When we want to store the phone-number(no duplicates) against name, we will go for map or unordered_map. 

map 

  1. It is an ordered sequence of unique keys. The key values are used to sort the elements of the map. Click here to understand this. 
  2. Usually implemented using Binary search tree specifically red-black tree.
  3. Since it is implemented as balanced tree structure, it is possible to maintain the order between the elements. Hence, Elements are sorted.
  4. Relatively small memory usage (doesn't need additional memory for the hash-table).
  5. Relatively fast lookup: O(log N).
  6. Duplicated values are allowed but not duplicate keys.
Example Programs : First Unique Character

unordered_map 

  1. In unordered_map, key can be stored in any order. 
  2. Usually implemented using hash-table.
  3. Elements are not sorted.
  4. Requires additional memory to keep the hash-table.
  5. Fast lookup O(1), but constant time depends on the hash-function which could be relatively slow. Also keep in mind that you could meet with the Birthday problem.
  6. Duplicate values are allowed but not duplicate keys. 


In the above image, the sequence is changed, so it is unordered. 

Without duplicate Keys

// 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;

}

Output

Contribute 30
GeeksforGeeks 10
Practice 20

With duplicate Keys

// 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["GeeksforGeeks"] = 20;
	umap["Contribute"] = 30;

	// Traversing an unordered map
	for (auto x : umap)
	cout << x.first << " " << x.second << endl;

}

Output

Contribute 30
GeeksforGeeks 20

Without duplicate Keys but duplicate values

// 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"] = 10;
	umap["Contribute"] = 30;

	// Traversing an unordered map
	for (auto x : umap)
	cout << x.first << " " << x.second << endl;

}

Output

Contribute 30
GeeksforGeeks 10
Practice 10

Map to Vector Conversion

Takeaways:

1. It is not that key value should begin in 0 or 1 for the map pairs <int, int>, it can start at 999 also. 
2. Try to go for unordered_map for any key-value problem if sorting is not concerned. 
3. Unordered_map is generally faster than map. 

Reference 

Comments

Post a Comment