C++ maps

---

Introduction

In C++, a map is a sorted associative container that stores key-value pairs, where each key is unique, and it is automatically ordered according to the keys. The C++ std::map is part of the C++ Standard Library and is defined in the <map> header. Maps provide an efficient way to store and retrieve data based on a unique key. The elements in a map are stored in ascending order by default, and the container ensures that no two elements have the same key.

Maps are implemented using self-balancing binary search trees, such as Red-Black trees, which guarantee logarithmic time complexity (O(log n)) for operations like insertions, deletions, and lookups.

---

Syntax

To declare a map, the syntax is as follows:

std::map<KeyType, ValueType> map_name;

Where:

• KeyType: The type of the key (e.g., int, std::string).
• ValueType: The type of the value associated with each key.

You can also specify custom comparators to define the ordering of keys:

std::map<KeyType, ValueType, Compare> map_name;

Where:

• Compare is a custom comparison function (a binary function object).

---

Declaring and Initializing a Map

Example 1: Basic Map Declaration

#include <iostream>
#include <map>

int main() {
    // Declare a map that associates an integer key with a string value
    std::map<int, std::string> map;

    // Inserting elements into the map
    map[1] = "One";
    map[2] = "Two";
    map[3] = "Three";

    // Displaying the map elements
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

1: One
2: Two
3: Three

Explanation:

• map[1] = "One" associates the key 1 with the value "One".
• The map stores the elements in ascending order based on the keys.

---

Operations on Maps

1. Insert Elements

You can insert elements into a map in several ways:

• Using the [] operator:

map[4] = "Four";  // Inserts key 4 with value "Four"

• Using the insert() method:

map.insert({5, "Five"});  // Inserts key 5 with value "Five"

2. Access Elements

To access elements, you can use the [] operator or the at() method:

• Using [] operator:

  std::cout << map[1] << std::endl;  // Output: "One"
  

• Using at() method (throws exception if key does not exist):

  std::cout << map.at(2) << std::endl;  // Output: "Two"
  

3. Find an Element

You can search for an element by key using the find() function, which returns an iterator pointing to the element if found, or map.end() if the key doesn't exist:

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

Explanation:

• find(2) looks for the key 2. If found, it returns an iterator to the key-value pair.

4. Remove Elements

To remove an element from the map, you can use the erase() method:

• Remove by key:

  map.erase(2);  // Removes the key-value pair with key 2
  

• Remove by iterator:

  auto it = map.find(1);
  map.erase(it);  // Removes the element pointed to by the iterator
  

5. Check Map Size and Emptiness

You can check the size of the map or whether it is empty:

std::cout << "Size: " << map.size() << std::endl;  // Size of the map
std::cout << "Is empty: " << (map.empty() ? "Yes" : "No") << std::endl;  // Check if map is empty

6. Clear All Elements

To remove all elements from the map, use the clear() method:

map.clear();  // Removes all elements from the map

---

Iterating Over a Map

You can iterate through the elements in a map using an iterator or a range-based for loop:

Example 1: Using Iterator

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

Example 2: Using Range-Based For Loop

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

---

Custom Sorting in Maps

By default, std::map stores elements in ascending order according to the keys. However, you can define a custom sorting criterion using a comparator.

Example: Custom Sorting (Descending Order)

#include <iostream>
#include <map>

bool descendingOrder(int a, int b) {
    return a > b;  // Custom comparator for descending order
}

int main() {
    // Create a map with a custom comparator
    std::map<int, std::string, bool(*)(int, int)> map(descendingOrder);

    map[1] = "One";
    map[2] = "Two";
    map[3] = "Three";

    // Display the elements in descending order
    for (const auto& pair : map) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:

3: Three
2: Two
1: One

---

Advantages of Using std::map

1. Automatic Sorting: Maps automatically sort their elements based on the key, which simplifies data management.
2. Logarithmic Time Complexity: Operations like insertions, deletions, and lookups are performed in O(log n) time due to the underlying tree structure.
3. Key-Value Pair Association: Maps provide an efficient way to store and access data by associating each key with a value.
4. Unique Keys: A map ensures that all keys are unique, and it automatically handles any attempts to insert duplicate keys.

---

When to Use std::map

Use a std::map when:

• You need to store key-value pairs with guaranteed uniqueness for keys.
• You need the keys to be automatically sorted.
• You need efficient lookup, insertion, and removal operations, typically on the order of O(log n).
• You want to maintain a dynamic collection where you can efficiently associate values with keys.

---

---