C++ - C++ std::map and std::unordered_map?

In C++, std::map and std::unordered_map are associative containers used to store data in the form of key-value pairs. Instead of accessing an element only through a numerical index, you access the associated value using a unique key. For example, if you want to store student marks, the student's roll number can be the key and the marks can be the value. Both containers are part of the Standard Template Library (STL), but they use different internal data structures and therefore have different performance characteristics.

1. What is `std::map`?

std::map stores elements as key-value pairs and keeps the keys sorted in ascending order by default. Every key must be unique. Internally, it is generally implemented using a self-balancing binary search tree, commonly a Red-Black Tree.

The basic syntax is:

#include <map>

std::map<KeyType, ValueType> mapName;

For example:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> students;

    students[103] = "Rahul";
    students[101] = "Anita";
    students[102] = "Kiran";

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

    return 0;
}

The output will be:

101 : Anita
102 : Kiran
103 : Rahul

Although the elements were inserted in the order 103, 101, and 102, std::map automatically maintains them according to their keys.

2. Important characteristics of `std::map`

A std::map has several important properties:

It stores data as key-value pairs.
Keys are unique.
Keys remain sorted.
Elements can be inserted and removed dynamically.
Searching, insertion, and deletion generally take O(log n) time.
It supports ordered traversal.
It does not provide direct random access like a vector.
It can use custom comparison functions to define the ordering of keys.

For example:

std::map<int, std::string> employees;

employees[3] = "Ravi";
employees[1] = "Anita";
employees[2] = "John";

The map internally maintains the order:

1 -> Anita
2 -> John
3 -> Ravi

3. Accessing elements in `std::map`

One of the simplest ways to access an element is using the [] operator:

std::map<int, std::string> students;

students[101] = "Anita";
students[102] = "Rahul";

std::cout << students[101];

Output:

Anita

However, there is an important point to remember. If the specified key does not exist, using [] can insert a new element with a default-initialized value.

For example:

std::map<int, std::string> students;

std::cout << students[105];

The key 105 will be inserted into the map with an empty string as its value.

If you only want to access an existing element without inserting a new one, at() can be used:

std::cout << students.at(101);

If the key does not exist, at() throws an exception.

4. Searching in `std::map`

The find() function is commonly used to determine whether a key exists.

std::map<int, std::string> students;

students[101] = "Anita";
students[102] = "Rahul";

auto it = students.find(102);

if (it != students.end()) {
    std::cout << "Student: " << it->second;
}

Here, find() returns an iterator pointing to the matching element. If the key is not found, it returns students.end().

Another useful function is count():

if (students.count(102) > 0) {
    std::cout << "Key exists";
}

Since a std::map does not allow duplicate keys, count() returns either 0 or 1.

5. Inserting elements into `std::map`

There are several ways to insert elements.

Using []:

students[101] = "Anita";

Using insert():

students.insert({102, "Rahul"});

Using emplace():

students.emplace(103, "Kiran");

emplace() constructs the element directly inside the container and can avoid unnecessary temporary objects in some situations.

6. Removing elements from `std::map`

An element can be removed using its key:

students.erase(102);

You can also remove an element using an iterator:

auto it = students.find(103);

if (it != students.end()) {
    students.erase(it);
}

To remove all elements:

students.clear();

The number of elements can be obtained using:

std::cout << students.size();

7. What is `std::unordered_map`?

std::unordered_map also stores key-value pairs, but unlike std::map, it does not maintain its elements in sorted order.

It is generally implemented using a hash table. A hash function converts a key into a hash value, which determines where the associated element is stored.

The syntax is:

#include <unordered_map>

std::unordered_map<KeyType, ValueType> mapName;

Example:

#include <iostream>
#include <unordered_map>

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

    students[103] = "Rahul";
    students[101] = "Anita";
    students[102] = "Kiran";

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

    return 0;
}

The output order is not guaranteed to be:

101
102
103

The elements can appear in a different order because unordered_map organizes them according to their hash values rather than their keys' sorted order.

8. Performance of `std::unordered_map`

The major advantage of unordered_map is its average-case performance.

Searching, insertion, and deletion generally take:

Average case: O(1)

This means that for many practical workloads, looking up a value can be very fast regardless of the number of elements.

However, the worst-case complexity can become:

Worst case: O(n)

This can happen when many keys produce hash collisions and end up in the same bucket.

Therefore, unordered_map is not automatically faster in every situation. Its performance depends on the quality of the hash function, the distribution of keys, and the workload.

9. Hashing and buckets

The fundamental difference between the two containers comes from how they organize their data.

std::map uses an ordered tree structure:

        20
       /  \
     10    30
    / \    / \
   5  15 25 35

This structure allows the keys to remain ordered.

std::unordered_map uses hashing. Conceptually, the keys are distributed among different buckets:

Bucket 0 -> key/value
Bucket 1 -> key/value -> key/value
Bucket 2 -> key/value
Bucket 3 -> key/value

The hash function determines which bucket a key belongs to.

If multiple keys map to the same bucket, a hash collision occurs. The implementation has mechanisms for handling these collisions.

10. Difference between `map` and `unordered_map`

Feature	`std::map`	`std::unordered_map`
Internal structure	Balanced tree	Hash table
Ordering	Sorted by key	No guaranteed order
Search	O(log n)	O(1) average
Insertion	O(log n)	O(1) average
Deletion	O(log n)	O(1) average
Worst-case lookup	O(log n)	O(n)
Duplicate keys	Not allowed	Not allowed
Ordered traversal	Yes	No
Custom hash required	No	Sometimes
Supports range-based ordered operations	Yes	No

11. When should you use `std::map`?

Use std::map when ordering is important.

For example, suppose you want to store product prices according to product IDs and later display them in increasing ID order:

std::map<int, double> prices;

prices[105] = 450.50;
prices[101] = 250.00;
prices[103] = 325.75;

When you iterate over the map, the keys will appear in sorted order:

101 -> 250.00
103 -> 325.75
105 -> 450.50

std::map is also useful when you need operations involving key ranges, such as finding all keys between two values.

For example:

auto start = prices.lower_bound(101);
auto end = prices.upper_bound(105);

for (auto it = start; it != end; ++it) {
    std::cout << it->first << " : " << it->second << '\n';
}

These ordered operations are an important reason to choose map.

12. When should you use `std::unordered_map`?

Use std::unordered_map when fast key-based lookup is more important than maintaining sorted order.

For example, consider a program that maintains employee information:

std::unordered_map<int, std::string> employees;

employees[1001] = "Arun";
employees[1002] = "Priya";
employees[1003] = "Vijay";

If your primary operation is:

auto it = employees.find(1002);

and you do not care about the order in which employees are displayed, unordered_map can be an appropriate choice.

It is particularly useful for applications such as lookup tables, caches, frequency counting, and dictionaries.

13. Example: Counting word frequency

One common application of unordered_map is counting how frequently words occur.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> frequency;

    frequency["apple"]++;
    frequency["banana"]++;
    frequency["apple"]++;
    frequency["orange"]++;
    frequency["banana"]++;

    for (const auto& item : frequency) {
        std::cout << item.first << " : "
                  << item.second << '\n';
    }

    return 0;
}

The resulting counts will be:

apple : 2
banana : 2
orange : 1

The order of the output is unspecified because this is an unordered_map.

If sorted output is required, std::map would be more suitable:

std::map<std::string, int> frequency;

Then the words will be traversed according to their alphabetical order.

14. Custom ordering in `std::map`

By default, std::map sorts keys in ascending order. However, you can provide a custom comparator.

For example:

#include <iostream>
#include <map>
#include <functional>

int main() {
    std::map<int, std::string, std::greater<int>> students;

    students[101] = "Anita";
    students[102] = "Rahul";
    students[103] = "Kiran";

    for (const auto& student : students) {
        std::cout << student.first << " : "
                  << student.second << '\n';
    }

    return 0;
}

The keys will be displayed in descending order:

103 : Kiran
102 : Rahul
101 : Anita

This demonstrates one of the major advantages of std::map: its ordering behavior can be customized.

15. Choosing between `map` and `unordered_map`

The decision should primarily depend on what your application requires.

Choose std::map when:

You need keys to remain sorted.
You need ordered traversal.
You need operations such as lower_bound() and upper_bound().
You want predictable logarithmic complexity for lookup, insertion, and deletion.
You need range-based operations on ordered keys.

Choose std::unordered_map when:

You mainly need fast key-based lookup.
Key ordering is irrelevant.
Average O(1) lookup, insertion, and deletion are desirable.
You are implementing a hash-based lookup structure.
You are building applications such as frequency counters or caches.

Conclusion

std::map and std::unordered_map both provide an efficient way to associate keys with values, but their underlying approaches are different. std::map maintains keys in sorted order using a tree-based structure and generally provides O(log n) operations. std::unordered_map uses hashing and provides average O(1) lookup, insertion, and deletion, but does not maintain any particular ordering.

The most important distinction is therefore ordered access versus hash-based fast access. If your program needs sorted keys or range-based operations, std::map is usually the better choice. If you only need quick lookup and do not care about ordering, std::unordered_map is often the more suitable option.

C++ - C++ std::map and std::unordered_map?

1. What is std::map?

2. Important characteristics of std::map

3. Accessing elements in std::map

4. Searching in std::map

5. Inserting elements into std::map

6. Removing elements from std::map

7. What is std::unordered_map?

8. Performance of std::unordered_map

9. Hashing and buckets

10. Difference between map and unordered_map

11. When should you use std::map?

12. When should you use std::unordered_map?

13. Example: Counting word frequency

14. Custom ordering in std::map

15. Choosing between map and unordered_map

Conclusion

1. What is `std::map`?

2. Important characteristics of `std::map`

3. Accessing elements in `std::map`

4. Searching in `std::map`

5. Inserting elements into `std::map`

6. Removing elements from `std::map`

7. What is `std::unordered_map`?

8. Performance of `std::unordered_map`

10. Difference between `map` and `unordered_map`

11. When should you use `std::map`?

12. When should you use `std::unordered_map`?

14. Custom ordering in `std::map`

15. Choosing between `map` and `unordered_map`