Key-Value Structures with std::map and std::unordered_map in C++

In C++, map and unordered_map are the two primary associative containers that provide key–value (dictionary-like) data structures. Both are used to associate a key with a corresponding value efficiently, but they differ significantly in data structure, ordering, search time, and performance behavior. This article explains both containers in detail with practical examples.

1) What is map?

std::map is an ordered associative container implemented as a red–black tree (self-balancing binary search tree).

• Keys are stored in sorted order.
• Search, insertion, and deletion: O(log n)
• Keys are unique.
• Iteration is always in increasing key order.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Note: Items are printed alphabetically (Alice, Bob, Charlie).

2) What is unordered_map?

std::unordered_map is a hash-table-based associative container. It provides extremely fast average lookup times but does not maintain any order.

• Keys are hashed → ordering is not guaranteed.
• Search, insert, erase: average O(1) (worst-case O(n)).
• Iteration order is unpredictable and may change over time.
• Typically faster than map on large datasets.

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

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

    scores["Alice"] = 90;
    scores["Bob"] = 80;
    scores["Charlie"] = 95;

    for (auto& p : scores)
        cout << p.first << " -> " << p.second << endl;
}

Note: Output order is arbitrary and may differ between runs.

3) Comparison: map vs unordered_map

Summary: If ordering matters → use map. If speed matters → use unordered_map.

4) Basic Operations

a) Insertion

map<int,string> m;
m.insert({1, "One"});
m[2] = "Two";   // both inserts and updates

b) Lookup

auto it = m.find(1);
if (it != m.end())
    cout << "Found: " << it->second;

c) Erase

m.erase(2);          // erase by key
m.erase(m.begin());  // erase by iterator

d) Size & existence check

cout << m.size();
cout << m.count(1);   // returns 0 or 1

5) Custom Hash Functions for unordered_map

Built-in types such as int, string, and double already have hash support. For custom types, you must define your own hash and equality functions.

#include <unordered_map>
#include <string>

struct User {
    string name;
    int id;
};

struct UserHash {
    size_t operator()(User const& u) const noexcept {
        return hash<string>{}(u.name) ^ hash<int>{}(u.id);
    }
};

struct UserEq {
    bool operator()(User const& a, User const& b) const noexcept {
        return a.id == b.id && a.name == b.name;
    }
};

int main() {
    unordered_map<User, int, UserHash, UserEq> users;
}

6) Buckets & Load Factor in unordered_map

Data in an unordered_map is organized into buckets. All keys hashing to the same value go into the same bucket (collision).

unordered_map<int,string> um;

cout << um.bucket_count() << endl;
cout << um.load_factor() << endl;

As the load factor increases, performance degrades. Use rehash(n) to increase the number of buckets and restore performance.

7) Practical Example – Student Grade System

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

int main() {
    unordered_map<string, double> grades;

    grades["John"] = 85.5;
    grades["Emily"] = 92.0;
    grades["Michael"] = 78.0;

    if (grades.contains("Emily"))
        cout << "Emily's grade: " << grades["Emily"] << endl;

    grades.erase("Michael");

    for (auto& g : grades)
        cout << g.first << ": " << g.second << endl;
}

8) Which One Should You Use?

• Use map → when ordering is required, data is small/medium sized, or tree-like structure is beneficial.
• Use unordered_map → when maximum lookup/insert/delete speed is essential.
• For range queries (lower_bound, upper_bound) → only map works.
• For large datasets → unordered_map is usually much faster.

General Recommendation: If you do not need ordering → choose unordered_map. If you need sorted iteration → choose map.

9) TL;DR

Related Articles