std::map in C++

Posted on August 9, 2025  •  4 minutes  • 704 words

When you need to store key-value pairs in C++ while maintaining the keys in sorted order, the STL’s std::map is your go-to container.

It’s part of the associative containers family, using a balanced binary search tree (typically a Red-Black Tree ) under the hood.

1. Overview of std::map

Key Features

• Stores elements as key → value pairs
• Keys are unique (duplicates are not allowed)
• Automatically sorts keys in ascending order (custom comparators allowed)
• Logarithmic time complexity for insert, search, and delete
• Uses <map> header

Syntax:

#include <map>
std::map<KeyType, ValueType> mapName;

2. Creating and Initializing std::map

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

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

    // Insert elements
    students[1] = "Alice";
    students[2] = "Bob";
    students[3] = "Charlie";

    // Using insert()
    students.insert({4, "David"});

    // Printing the map
    for (auto &entry : students) {
        cout << entry.first << " → " << entry.second << endl;
    }
}

/*
Output

1 → Alice
2 → Bob
3 → Charlie
4 → David
*/

3. Inserting Elements

3.1 Using [] Operator

map<int, string> m;
m[10] = "Ten";
m[20] = "Twenty";

Note: If the key doesn’t exist, it creates a new entry with a default-initialized value.

3.2 Using insert()

m.insert({30, "Thirty"});
m.insert(make_pair(40, "Forty"));

3.3 Using emplace() (C++11+)

// Constructs in place
m.emplace(50, "Fifty");

4. Accessing Elements

4.1 Using []

cout << m[10]; // Outputs "Ten"

Caution: If the key doesn’t exist, this will insert a default value.

4.2 Using at()

// Safe, throws out_of_range if key not found
cout << m.at(20); 

5. Searching in std::map

5.1 Using find()

int key = 30;
auto it = m.find(key);
if (it != m.end())
    cout << "Found: " << it->first << " → " << it->second;
else
    cout << "Key not found";

5.2 Using count()

if (m.count(40))
    cout << "Key exists";

6. Deleting Elements

6.1 By Key

m.erase(20);

6.2 By Iterator

auto it = m.find(30);
if (it != m.end())
    m.erase(it);

6.3 By Range

m.erase(m.begin(), m.find(40));

7. Iterating Through std::map

7.1 Range-based for loop

for (auto &p : m)
    cout << p.first << " → " << p.second << endl;

7.2 Using Iterators

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->first << " : " << it->second << endl;

8. Custom Key Ordering

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

struct Descending 
{
    bool operator()(int a, int b) const 
    {
        return a > b;
    }
};

int main() 
{
    map<int, string, Descending> m;
    m[1] = "One";
    m[3] = "Three";
    m[2] = "Two";

    for (auto &p : m)
        cout << p.first << " → " << p.second << endl;
}

/*
Output:

3 → Three
2 → Two
1 → One

*/

9. Useful Member Functions

10. Example: Word Frequency Counter

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

int main() 
{
    string text = "apple banana apple orange banana apple";
    map<string, int> freq;
    string word;
    stringstream ss(text);

    while (ss >> word)
        freq[word]++;

    for (auto &p : freq)
        cout << p.first << " → " << p.second << endl;
}

/*
Output:

apple → 3
banana → 2
orange → 1
*/

11. Performance Notes

• Insertion, search, and deletion: O(log n)
• Uses more memory than std::unordered_map due to tree structure
• Maintains sorted order of keys

std::map is ideal when:

• You need sorted key-value pairs
• Duplicates are not allowed
• You can afford O(log n) operations

If order doesn’t matter and you need faster lookups, consider std::unordered_map .

By mastering std::map, you gain a powerful tool for storing and retrieving structured data efficiently.