What is Unordered Map in C++?

An unordered map is an associative container in the Standard Template Library (STL) that stores key-value pairs using a hash table. Each key is unique, and every key maps to exactly one value. Since a hash table is used internally, elements are not stored in sorted order.

Think of an unordered map as a phone contact list stored in a digital database. Instead of searching alphabetically, the system quickly locates a contact using an internal indexing mechanism (hashing), making lookups much faster.

Why does Unordered Map exist?

Although std::map automatically sorts keys, maintaining that order requires extra processing. If sorting isn't necessary, an unordered map provides several benefits.

• Faster average lookup
• Faster average insertion
• Faster average deletion
• Efficient storage of key-value pairs

Real-world use cases

• User account management
• Employee databases
• Product catalogs
• Caching systems
• Word frequency counting
• Database indexing
• DNS lookups
• Session management
• Compiler symbol tables

Prerequisites

• Variables and data types
• Arrays and loops
• Functions
• Templates
• Basic STL containers
• std::map (recommended)

Including the header

#include <unordered_map>

Creating an unordered map

unordered_map<key_type, value_type> map_name;

// Example:
unordered_map<int, string> students;

Initializing an unordered map

unordered_map<int, string> students =
{
    {101, "Alice"},
    {102, "Bob"},
    {103, "Charlie"}
};

Characteristics of unordered map

• Stores data as key-value pairs
• Duplicate keys: not allowed
• Duplicate values: allowed
• Order: no guaranteed order
• Search: average O(1)
• Insert: average O(1)
• Delete: average O(1)
• Implementation: hash table

Common operations

• insert() – insert a key-value pair
• emplace() – construct and insert an element
• erase() – remove an element
• find() – search for a key
• count() – check whether a key exists
• size() – number of elements
• empty() – check whether the map is empty
• clear() – remove all elements
• operator[] – access or insert a value
• at() – access an existing value
• begin() – iterator to the first element
• end() – iterator to one past the last element

How unordered maps store data

An unordered map uses a hash table internally. When a key is inserted, a hash function computes a hash value, the hash value determines a bucket, and the key-value pair is stored in that bucket. This allows very fast average-case operations.

Accessing elements

Using operator[]:

students[101] = "Alice";

// If the key doesn't exist, it is automatically created.

Using at():

cout << students.at(101);

// Unlike operator[], at() throws an exception if the key does not exist.

Iterating through an unordered map

for (const auto& student : students)
{
    cout << student.first << " : "
         << student.second << endl;
}

Note: the iteration order is unspecified and may vary between executions.

Example 1: Creating and displaying an unordered map

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

int main()
{
    unordered_map<int, string> students;

    students[101] = "Alice";
    students[102] = "Bob";
    students[103] = "Charlie";

    for (const auto& student : students)
    {
        cout << student.first << " : ";
        cout << student.second << endl;
    }

    return 0;
}

// Possible output:
// 103 : Charlie
// 101 : Alice
// 102 : Bob
// Note: the order is not guaranteed.

Example 2: Searching for a key

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

int main()
{
    unordered_map<int, string> students;

    students[101] = "Alice";
    students[102] = "Bob";

    auto it = students.find(102);

    if (it != students.end())
    {
        cout << it->second;
    }
    else
    {
        cout << "Student not found";
    }

    return 0;
}

Example 3: Removing an element

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

int main()
{
    unordered_map<int, string> products =
    {
        {1, "Laptop"},
        {2, "Mouse"},
        {3, "Keyboard"}
    };

    products.erase(2);

    for (const auto& product : products)
    {
        cout << product.first << " : ";
        cout << product.second << endl;
    }

    return 0;
}

Example 4: Word frequency counter

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

int main()
{
    vector<string> words =
    {
        "apple",
        "banana",
        "apple",
        "orange",
        "banana",
        "apple"
    };

    unordered_map<string, int> frequency;

    for (const string& word : words)
    {
        frequency[word]++;
    }

    for (const auto& item : frequency)
    {
        cout << item.first << " : ";
        cout << item.second << endl;
    }

    return 0;
}

Example 5: Employee salary database

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

int main()
{
    unordered_map<int, double> salaries;

    salaries[1001] = 55000.50;
    salaries[1002] = 62000.75;
    salaries[1003] = 48000.00;

    cout << "Employee Salaries\n";

    for (const auto& employee : salaries)
    {
        cout << "ID: " << employee.first;
        cout << " Salary: ";
        cout << employee.second << endl;
    }

    return 0;
}

Common mistakes and pitfalls

• Expecting keys to be sorted. Fix: remember that unordered_map does not maintain key order
• Using duplicate keys expecting multiple entries. Fix: keys must be unique, use std::unordered_multimap if duplicate keys are needed
• Accessing a missing key with operator[] unintentionally. Fix: use find() or at() when you don't want a new key to be created
• Iterating expecting insertion order. Fix: iteration order is unspecified and may change
• Forgetting custom hash functions for user-defined keys. Fix: define a custom hash function when using custom types as keys

Best practices

• Use unordered_map when sorted keys are unnecessary
• Prefer find() for lookups that should not insert new keys
• Use reserve() when inserting a large number of elements to reduce rehashing
• Use emplace() instead of insert() when constructing objects directly in the container
• Pass large unordered maps by const reference to avoid unnecessary copying
• Use custom hash functions for user-defined key types
• Switch to std::map if ordered traversal or range queries are required

When not to use this

• Keys must remain sorted
• You need ordered traversal or range-based queries
• Deterministic iteration order is required
• Worst-case lookup performance is more important than average-case speed
• Memory usage must be minimized, as hash tables generally consume more memory than tree-based maps

Summary

• Unordered Map in C++ stores key-value pairs using a hash table
• Keys are unique, while values may be duplicated
• Keys are not stored in sorted order
• Lookup, insertion, and deletion are typically O(1) on average
• Use operator[], at(), find(), erase(), insert(), emplace(), clear(), and size() for common operations
• unordered_map is ideal for fast key-based lookups when ordering is not required
• Use std::map when sorted keys or ordered traversal are needed

Frequently asked questions

What is the difference between map and unordered_map?

std::map stores keys in sorted order using a self-balancing tree and provides O(log n) operations. std::unordered_map stores keys in a hash table, does not maintain order, and typically provides O(1) average-case operations.

Can an unordered map have duplicate keys?

No. Every key must be unique. If duplicate keys are required, use std::unordered_multimap.

Why is the iteration order different every time?

std::unordered_map organizes elements into hash buckets rather than sorting them. As a result, iteration order is unspecified and may vary across runs or implementations.

What is the difference between operator[] and at()?

operator[] inserts a new element with a default value if the key is missing. at() accesses an existing element and throws an exception if the key does not exist.

When should I use unordered_map instead of map?

Use std::unordered_map when you need fast average-case lookups and do not require sorted keys. Choose std::map when ordered traversal, range queries, or sorted output are important.