Map in C++ Standard Template Library (STL)

January 13, 2025

1

A map in C++ is a part of the Standard Template Library (STL) and is an associative container that stores elements in a key-value pair format. The keys are unique, and each key maps to exactly one value. Maps automatically maintain their elements in a sorted order based on the keys.

Features of `std::map`:

Key-Value Pair: Each element is a combination of a key and a value (key -> value).
Unique Keys: No two elements can have the same key.
Ordered: Elements are stored in ascending order of their keys by default.
Underlying Implementation: Internally implemented as a self-balancing binary search tree (typically a Red-Black Tree).
Dynamic Size: Maps can grow or shrink dynamically during runtime.
Efficient Search and Insertion: Both operations have a time complexity of O(log n).

Syntax:

KeyType: Data type of the key (e.g., int, string).
ValueType: Data type of the value associated with the key.

Common Operations on `std::map`:

Operation	Description
`insert()`	Inserts a key-value pair into the map.
`erase()`	Removes an element by key or iterator.
`find()`	Searches for an element by key.
`at()`	Accesses the value associated with a key.
`operator[]`	Accesses the value or inserts a new element if the key doesn’t exist.
`size()`	Returns the number of elements in the map.
`empty()`	Checks if the map is empty.
`clear()`	Removes all elements from the map.

Example 1: Basic Usage

cpp

#include <iostream>

#include <map>

using namespace std;
int main() {

    // Declare a map

    map<int, string> m;
    // Insert key-value pairs

    m[1] = "Apple";

    m[2] = "Banana";

    m[3] = "Cherry";
    // Display elements

    for (const auto& pair : m) {

        cout << "Key: " << pair.first << ", Value: " << pair.second << endl;

    }
    // Access a specific key

    cout << "Value at key 2: " << m.at(2) << endl;
    // Check if a key exists

    if (m.find(4) != m.end()) {

        cout << "Key 4 exists in the map." << endl;

    } else {

        cout << "Key 4 does not exist in the map." << endl;

    }

return 0; }

Output:

Example 2: Insertion and Deletion

cpp

#include <iostream>

#include <map>

using namespace std;
int main() {

    map<string, int> m;
    // Insert elements using insert()

    m.insert({"Alice", 30});

    m.insert({"Bob", 25});

    m.insert({"Charlie", 35});
    // Display map contents

    cout << "Map contents:\n";

    for (const auto& pair : m) {

        cout << pair.first << ": " << pair.second << endl;

    }
    // Erase an element

    m.erase("Alice");
    // Check if the map is empty

    if (m.empty()) {

        cout << "Map is empty." << endl;

    } else {

        cout << "Map is not empty." << endl;

    }

return 0; }

Output:

Key Functions in Detail:

insert():
- Inserts a new key-value pair.
- If the key already exists, the insertion is ignored.
cpp

m.insert({key, value});
erase():
- Removes an element by key or iterator.
cpp

m.erase(key);
find():
- Returns an iterator to the element with the given key. If the key is not found, it returns m.end().
cpp

auto it = m.find(key); if (it != m.end()) { cout << "Key found: " << it->first << ", Value: " << it->second << endl; } else { cout << "Key not found." << endl; }
operator[]:
- Accesses or inserts a value for the given key.
cpp

m[key] = value; // If key exists, updates value; otherwise inserts new key-value pair.
at():
- Similar to operator[], but throws an exception if the key is not found.
cpp

cout << m.at(key);

Advantages of `std::map`:

Automatic Sorting: Elements are always stored in ascending order based on the key.
Efficient Lookups: Searching for a key is logarithmic in time complexity.
Ease of Use: Provides built-in methods for common operations.

Limitations:

Memory Overhead: Due to tree-based implementation, std::map uses more memory compared to other containers like std::unordered_map.
Slower than std::unordered_map: For lookups, std::unordered_map is faster with average O(1) complexity.

Comparison with `std::unordered_map`:

Feature	`std::map`	`std::unordered_map`
Order	Sorted (ascending order)	Unordered
Underlying Structure	Red-Black Tree	Hash Table
Search Complexity	O(log n)	O(1) (average), O(n) (worst)
Insertion Complexity	O(log n)	O(1) (average), O(n) (worst)
Memory Usage	Higher	Lower

Conclusion:

std::map is a powerful and versatile container in C++ for managing key-value pairs where the order of keys is important. It provides efficient searching, insertion, and deletion operations with a time complexity of O(log n). However, for unordered key-value storage, std::unordered_map might be more suitable.