Map: Container, C++

Map Container in C++: Usage and Operations

In C++, the map container is part of the Standard Template Library (STL). It is a collection that stores key-value pairs, where each key is unique, and the keys are always sorted in a specific order (usually ascending). This container is implemented as a balanced binary tree (typically a Red-Black tree), which ensures that insertions, deletions, and lookups occur in logarithmic time complexity. If maintaining the order of elements is important, the map is the ideal choice.

In this guide, we will explore the functionality of the map container in C++, detailing its construction, common operations, and effective usage.

---

Table of Contents

1. Introduction to Map in C++
2. Different Ways to Construct a Map
3. Common Operations on Map
   • insert()
   • erase()
   • find()
   • count()
   • size()
   • empty()
   • clear()
   • operator[]
4. Working with Custom Data Types
5. Iterators in Maps
6. Summary and Best Practices

---

1. Introduction to Map in C++

A map in C++ is a container that stores key-value pairs, where each key is unique and associated with a value. It maintains the order of the keys based on a comparison function, which is, by default, the < operator (ascending order). map uses a balanced binary search tree to store the elements, ensuring logarithmic time complexity for insertions, deletions, and lookups.

Key Features:

• Key-Value Pairs: Each element in a map is a pair consisting of a key and a value.
• Unique Keys: The keys in a map must be unique. If you insert a new pair with a key that already exists, the new value will replace the old one.
• Sorted Order: Elements are always sorted based on the key, ensuring efficient traversal and retrieval.
• Logarithmic Complexity: Insertions, deletions, and lookups are performed in logarithmic time complexity due to the balanced tree structure.

When to Use:

• Use map when you need to store key-value pairs where the order of keys matters (sorted).
• If order doesn't matter and you need faster average time complexity for access, consider using unordered_map instead.

---

2. Different Ways to Construct a Map

You can create a map in various ways, depending on the requirements.

2.1 Default Constructor

The default constructor creates an empty map.

map<int, string> m;

This creates an empty map that maps integers to strings, which can be populated later.

2.2 Constructor with Initializer List

You can initialize a map directly with a list of key-value pairs.

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

This creates a map containing the key-value pairs 1 -> "one", 2 -> "two", and 3 -> "three".

2.3 Constructor with Another Map

You can create a map by copying elements from another map.

map<int, string> m1 = {{1, "one"}, {2, "two"}};
map<int, string> m2(m1);  // Initializes m2 as a copy of m1

2.4 Constructor with Another Container

You can create a map by copying elements from another container, such as a vector of pairs.

vector<pair<int, string>> v = {{1, "one"}, {2, "two"}, {3, "three"}};
map<int, string> m(v.begin(), v.end());  // Initializes a map using iterators from a vector

2.5 Assignment Operator

You can assign one map to another using the assignment operator.

map<int, string> m1 = {{1, "one"}, {2, "two"}};
map<int, string> m2;
m2 = m1;  // Now m2 contains the same key-value pairs as m1

---

3. Common Operations on Map

3.1 insert()

The insert() function adds a key-value pair to the map. If the key already exists, the value will be updated.

Syntax:

• Insert a single key-value pair:

  m.insert({key, value});

• Insert multiple key-value pairs using an initializer list:

  m.insert({{key1, value1}, {key2, value2}, ...});

• Insert key-value pairs from another container:

  m.insert(container.begin(), container.end());

Example:

map<int, string> m;

// Insert a single key-value pair
m.insert({1, "one"});  // Inserts 1 -> "one"
m.insert({2, "two"});  // Inserts 2 -> "two"
m.insert({3, "three"});  // Inserts 3 -> "three"

// Insert multiple key-value pairs
m.insert({{4, "four"}, {5, "five"}, {6, "six"}});  // Inserts 4 -> "four", 5 -> "five", and 6 -> "six"

// Insert key-value pairs from another container
vector<pair<int, string>> v = {{7, "seven"}, {8, "eight"}, {9, "nine"}};
m.insert(v.begin(), v.end());  // Inserts 7 -> "seven", 8 -> "eight", and 9 -> "nine"

After these operations, the map will contain the key-value pairs: {1 -> "one", 2 -> "two", 3 -> "three", 4 -> "four", 5 -> "five", 6 -> "six", 7 -> "seven", 8 -> "eight", 9 -> "nine"}.

3.2 erase()

The erase() function removes a key-value pair from the map.

Syntax:

• Erase a single key-value pair:

  m.erase(key);

• Erase a key-value pair using an iterator:

  m.erase(iterator);

• Erase a range of key-value pairs:

  m.erase(start_iterator, end_iterator);

Example:

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}};

// Erase a single key-value pair
m.erase(2);  // Removes 2 -> "two"

// Erase using an iterator
auto it = m.find(3);
m.erase(it);  // Removes 3 -> "three"

// Erase a range of key-value pairs
m.insert({{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}});  // Reinsert key-value pairs for demonstration
auto start = m.find(1);
auto end = m.find(4);
m.erase(start, end);  // Removes 1 -> "one", 2 -> "two", and 3 -> "three"

After these operations, the map will contain: {4 -> "four", 5 -> "five"}.

3.3 find()

The find() function searches for a key in the map and returns an iterator to the corresponding key-value pair if found, or end() if not found.

Syntax:

auto it = m.find(key);

Example:

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
auto it = m.find(2);
if (it != m.end()) {
    cout << "Key found: " << it->first << " -> " << it->second << endl;  // Outputs: Key found: 2 -> "two"
} else {
    cout << "Key not found." << endl;
}

3.4 count()

The count() function returns the number of occurrences of a key in the map. Since map only allows unique keys, it will return either 0 or 1.

Syntax:

size_t count = m.count(key);

Example:

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
cout << "Count of 2: " << m.count(2) << endl;  // Outputs: Count of 2: 1
cout << "Count of 4: " << m.count(4) << endl;  // Outputs: Count of 4: 0

3.5 size()

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

Syntax:

size_t size = m.size();

Example:

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
cout << "Size: " << m.size() << endl;  // Outputs: Size: 3

3.6 empty()

The empty() function returns a boolean value indicating whether the map is empty or not.

Syntax:

bool is_empty = m.empty();

Example:

map<int, string> m;
cout << "Is empty: " << m.empty() << endl;  // Outputs: Is empty: 1 (true)

3.7 clear()

The clear() function removes all elements from the map.

Syntax:

m.clear();

Example:

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};
m.clear();  // Removes all elements from the map
cout << "Size after clear: " << m.size() << endl;  // Outputs: Size after clear: 0

3.8 operator[]

The operator[] allows you to access the value corresponding to a key, or insert a new key-value pair if the key does not exist.

Syntax:

m[key] = value;

Example:

map<int, string> m = {{1, "one"}, {2, "two"}};
m[3] = "three";  // Adds 3 -> "three"
cout << "Key 3: " << m[3] << endl;  // Outputs: Key 3: three

---

4. Working with Custom Data Types

You can use custom data types as keys in a map. Since the map relies on the keys being ordered, you need to provide a comparison function for your custom data type.

Custom Comparison Function

To use a custom data type as a key, you must define a comparison function that returns a boolean indicating whether one key is less than the other.

#include <iostream>
#include <map>

using namespace std;

struct Person {
    string name;
    int age;
};

// Custom comparison function for Person
struct ComparePerson {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.age < p2.age;  // Order by age
    }
};

int main() {
    map<Person, string, ComparePerson> m;

    Person p1{"Alice", 30};
    Person p2{"Bob", 25};

    m[p1] = "Engineer";
    m[p2] = "Doctor";

    cout << "Alice's profession: " << m[p1] << endl;  // Outputs: Alice's profession: Engineer
    cout << "Bob's profession: " << m[p2] << endl;    // Outputs: Bob's profession: Doctor

    return 0;
}

In this example, Person is a custom key type, and the ComparePerson struct is a custom comparison function.

---

5. Iterators in Maps

You can iterate through the elements of a map using iterators.

map<int, string> m = {{1, "one"}, {2, "two"}, {3, "three"}};

// Using an iterator to iterate
for (auto it = m.begin(); it != m.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
}

Alternatively, you can use a range-based for loop:

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

---

6. Summary and Best Practices

• Efficiency: map provides logarithmic time complexity for insertions, deletions, and lookups, making it efficient for maintaining a sorted collection of key-value pairs.
• Ordered Keys: The keys are always stored in sorted order, based on the comparison function. Use a map when you need to maintain sorted keys.
• Custom Types: You can use custom data types as keys by defining a suitable comparison function.
• Avoid Large Keys: The sorting operation adds overhead, so map may not be the most efficient choice for scenarios where fast, unordered access is required.

By understanding these fundamental operations, you can leverage the map container efficiently in C++ for handling key-value pairs in sorted order.