What is STL Map in C++?

A map is an associative container in the Standard Template Library (STL) that stores elements as key-value pairs. Each key is unique, and every key is associated with exactly one value.

Unlike vectors, maps automatically sort their keys, making searches, insertions, and deletions efficient.

Think of a map as a dictionary: the word is the key, and the meaning is the value. You search using the word (key), and the dictionary returns its meaning (value).

Why does STL Map exist?

Suppose you're storing student records. Without a map, you might use two separate arrays for student IDs and names, and searching for a student ID requires finding its index first. With a map, the relationship between the key and value is stored directly.

• Store key-value pairs
• Keep keys sorted
• Prevent duplicate keys
• Provide efficient searching

Real-world use cases

• Student management systems
• Phone directories
• Dictionaries
• Employee databases
• Product catalogs
• Banking applications
• Caching systems
• Configuration settings
• Language translators

Prerequisites

• Variables and data types
• Functions
• Arrays
• Templates
• Basic STL containers (especially vector and set)

Including the map header

#include <map>

Creating a map

map<key_type, value_type> map_name;

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

// This creates an empty map where key is an integer and value is a string.

Initializing a map

• map<int,string> m; – empty map
• map<int,string> m = {{1,"A"},{2,"B"}}; – initialize using key-value pairs
• map<int,string> m{{1,"A"},{2,"B"}}; – uniform initialization

Characteristics of STL Map

• Stores data as key-value pairs
• Duplicate keys: not allowed
• Duplicate values: allowed
• Automatically sorted by key
• Random access: no index
• Search: O(log n)
• Insert: O(log n)
• Delete: O(log n)

Accessing elements

Using operator[]:

students[101] = "Alice";

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

Using at():

students.at(101);

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

Common map operations

• insert() – insert key-value pair
• erase() – remove an element
• find() – search for a key
• count() – check if key exists
• size() – number of elements
• empty() – check if empty
• clear() – remove all elements
• begin() – iterator to first element
• end() – iterator to last element

How maps store data

A std::map is usually implemented using a self-balancing Red-Black Tree. This allows sorted keys, fast insertion, fast deletion, and fast searching. All major operations generally run in O(log n) time.

Iterating through a map

Maps can be traversed using range-based for or iterators.

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

// first is the key, second is the value.

Example 1: Creating and displaying a map

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

int main()
{
    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;
}

// Output:
// 101 : Alice
// 102 : Bob
// 103 : Charlie

Example 2: Using insert()

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

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

    products.insert({1, "Laptop"});
    products.insert({2, "Mouse"});
    products.insert({3, "Keyboard"});

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

    return 0;
}

Example 3: Searching for a key

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

int main()
{
    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;
}

// Output: Bob

Example 4: Word frequency counter

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

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

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

// Output:
// apple : 3
// banana : 2
// orange : 1

Example 5: Student marks database

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

int main()
{
    map<int, int> marks;

    marks[101] = 85;
    marks[102] = 91;
    marks[103] = 78;

    cout << "Student Marks\n";

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

    return 0;
}

Common mistakes and pitfalls

• Using duplicate keys expecting multiple entries. Fix: keys must be unique, use std::multimap if duplicate keys are required
• Accessing a missing key with operator[]. Fix: use find() or at() if you don't want a new key to be created
• Expecting insertion order to be preserved. Fix: maps are always sorted by key
• Searching manually using loops. Fix: use find() for efficient lookups
• Using std::map when sorting isn't needed. Fix: consider std::unordered_map for faster average lookups

Best practices

• Use meaningful key types (such as IDs, names, or strings)
• Use find() instead of repeatedly checking with loops
• Pass maps by const reference when they don't need to be modified
• Use range-based for loops for cleaner iteration
• Prefer emplace() over insert() when constructing objects directly in the map
• Use std::unordered_map when sorted keys are unnecessary and performance is more important
• Avoid unnecessary copies of large maps

When not to use this

• Duplicate keys are required (use std::multimap)
• Fast index-based access is needed (use std::vector)
• Sorting by key is unnecessary and maximum lookup performance is desired (use std::unordered_map)
• The data is stored sequentially rather than as key-value pairs
• Memory usage is a primary concern, since tree-based maps use more memory than contiguous containers

Summary

• STL Map in C++ stores data as key-value pairs
• Keys are unique and automatically sorted
• Values can be duplicated even though keys cannot
• Common operations such as insertion, deletion, and lookup generally run in O(log n) time
• Use insert(), emplace(), find(), erase(), count(), clear(), and size() to manage elements
• Access values using operator[] or at(), keeping in mind that operator[] inserts missing keys
• Use maps whenever you need fast, organized access to data associated with unique keys
• Consider std::unordered_map if sorted order is not required and average lookup speed is more important

Frequently asked questions

What is the difference between a map and a vector?

A vector stores elements sequentially and accesses them by index. A map stores key-value pairs and accesses values using unique keys.

Can a map have duplicate keys?

No. Every key in a std::map must be unique. If duplicate keys are required, use std::multimap.

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

operator[] creates a new entry if the key does not exist. at() throws an exception if the key is missing, making it safer when you don't want accidental insertions.

What is the time complexity of searching in a map?

Searching with find() is typically O(log n) because std::map is usually implemented as a self-balancing Red-Black Tree.

When should I use std::unordered_map instead of std::map?

Use std::unordered_map when you don't need keys to be sorted and want average O(1) insertion, deletion, and lookup. Use std::map when sorted order or ordered traversal is important.