Map in C++ Standard Template Library (STL)

In C++, the map is a part of the Standard Template Library (STL) and is used to store key-value pairs. Each key is unique, and each key maps to exactly one value. It is an associative container that allows fast retrieval of values based on the associated keys.

Key Characteristics of Map:

1. Ordered: A map in C++ stores its elements in sorted order according to the key. The sorting is done using the operator< by default, but it can be customized by using a comparator function.
2. Unique Keys: Each key in a map is unique, meaning no two elements can have the same key.
3. Associative: Elements are stored as key-value pairs, where the key is used to access the corresponding value.
4. Underlying Data Structure: Typically implemented as a balanced binary tree (such as a Red-Black Tree), which provides O(log n) time complexity for search, insertion, and deletion operations.

Map Syntax:

std::map<key_type, value_type>

Where:

• key_type is the data type of the key (e.g., int, string).
• value_type is the data type of the value associated with the key.

Basic Operations on Maps:

1. Creating a Map:

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap; // A map with 'int' as key and 'string' as value
    myMap[1] = "One";  // Insert key-value pair
    myMap[2] = "Two";  // Insert another key-value pair

    std::cout << "Key 1 maps to: " << myMap[1] << std::endl; // Accessing value by key
    return 0;
}

Output:

Key 1 maps to: One

2. Inserting Elements:

You can insert elements using the insert() function or the subscript operator ([]).

std::map<int, std::string> myMap;
myMap.insert(std::make_pair(1, "One"));
myMap.insert({2, "Two"});
myMap[3] = "Three";  // Using subscript operator to insert

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

Output:

1: One
2: Two
3: Three

3. Accessing Elements:

You can access the values of a map using the key as an index, or by using iterators.

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";

// Access value using key
std::cout << "Key 1 maps to: " << myMap[1] << std::endl; // Direct access

// Using an iterator to print map contents
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

Output:

Key 1 maps to: One
1: One
2: Two

4. Searching for a Key:

You can use the find() function to search for a key in a map. It returns an iterator to the element if the key is found, or end() if the key does not exist.

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";

// Search for key 2
auto it = myMap.find(2);
if (it != myMap.end()) {
    std::cout << "Found key 2: " << it->second << std::endl;
} else {
    std::cout << "Key not found." << std::endl;
}

Output:

Found key 2: Two

5. Removing Elements:

To remove elements from a map, use the erase() function. You can erase by key or by iterator.

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";
myMap[3] = "Three";

// Erase by key
myMap.erase(2);

// Erase by iterator
auto it = myMap.find(1);
if (it != myMap.end()) {
    myMap.erase(it);
}

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

Output:

3: Three

6. Size of the Map:

The size() function returns the number of key-value pairs in the map.

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";

std::cout << "Size of the map: " << myMap.size() << std::endl;

Output:

Size of the map: 2

7. Iterating Over a Map:

You can iterate over a map using iterators or range-based for loops.

std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";

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

Output:

1: One
2: Two

Custom Sorting:

By default, maps in C++ sort the keys in ascending order. You can change the sorting criteria by providing a custom comparison function.

#include <iostream>
#include <map>

struct Compare {
    bool operator()(int a, int b) const {
        return a > b; // Sorting in descending order
    }
};

int main() {
    std::map<int, std::string, Compare> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    return 0;
}

Output:

3: Three
2: Two
1: One

Time Complexity:

• Insertions: O(log n)
• Search: O(log n)
• Deletion: O(log n)

Since the map is implemented using a balanced binary search tree (usually a Red-Black Tree), all operations (insert, delete, search) are logarithmic in time complexity.

Conclusion:

• A map in C++ STL is an associative container that stores key-value pairs and provides efficient operations for inserting, accessing, and deleting data.
• It maintains the order of the keys and supports custom sorting with a comparator function.
• Maps are ideal for scenarios where fast retrieval of values based on keys is required.