std::map

std::map is an associative container provided by the Standard Template Library (STL).

It represents a sorted key-value pair collection, where each element is uniquely identified by its key.

The elements are automatically sorted by their keys in ascending order.

std::map uses a balanced binary search tree (usually Red-Black tree) to efficiently maintain the sorted order and provide fast lookup, insertion, and deletion operations.

Table of Contents

Creating a std::map:

To use std::map, you need to include the <map> header.

#include <iostream>
#include <map>

int main() {
    // Create an empty map of key-value pairs (int to string)
    std::map<int, std::string> myMap;

    // Create a map with initial values using initializer list
    std::map<int, std::string> initializedMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    return 0;
}

Advantages of std::map:

Sorted key-value pairs: Elements are automatically sorted by their keys, making it easy to retrieve them in a sorted order.
Fast search, insert, and delete: The balanced binary search tree allows std::map to provide logarithmic time complexity for these operations.
Automatic sorting: Elements are automatically sorted upon insertion, and maintaining sorted order is not the responsibility of the user.

Disadvantages of std::map:

Overhead: The balanced binary search tree used internally may require additional memory overhead compared to other containers like std::vector or std::unordered_map.
Unique keys: std::map only allows unique keys, so you cannot have multiple elements with the same key.

std::map is a great choice when you need to store a collection of key-value pairs and require them to be automatically sorted by the keys. It is especially useful for applications where efficient searching and retrieval based on keys are essential. If you need a container that allows duplicate keys and does not require sorting, consider using std::unordered_map.

Important Functions of std::map:

insert({key, value}):

Inserts the specified key-value pair into the map.

Time Complexity: Logarithmic time (O(log n)), where n is the number of elements in the map.
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {3, "three"}};

    myMap.insert({2, "two"}); // After this, myMap contains {{1, "one"}, {2, "two"}, {3, "three"}}

    return 0;
}

erase(key):

Removes the element with the specified key from the map, if it exists.

Time Complexity: Logarithmic time (O(log n)), where n is the number of elements in the map.
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    myMap.erase(2); // After this, myMap contains {{1, "one"}, {3, "three"}}

    return 0;
}

find(key):

Searches for the element with the specified key in the map and returns an iterator to it. If the key is not found, it returns the end() iterator.

Time Complexity: Logarithmic time (O(log n)), where n is the number of elements in the map.
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Element found: " << it->second << std::endl; // Output: "two"
    } else {
        std::cout << "Element not found." << std::endl;
    }

    return 0;
}

count(key):

Returns the number of occurrences of the specified key in the map (since it only contains unique keys, it will return either 0 or 1).

Time Complexity: Logarithmic time (O(log n)), where n is the number of elements in the map.
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    int count = myMap.count(2); // count = 1

    return 0;
}

size():

Returns the number of elements in the map.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

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

    return 0;
}

empty():

Checks if the map is empty.

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    if (myMap.empty()) {
        std::cout << "Map is empty." << std::endl;
    } else {
        std::cout << "Map is not empty." << std::endl;
    }

    return 0;
}

clear():

Removes all elements from the map.

Time Complexity: Linear time (O(n)), where n is the number of elements in the map.
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    myMap.clear(); // After this, myMap is empty

    return 0;
}

begin():

Returns an iterator to the beginning of the map (first key-value pair).

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.begin();
    std::cout << "First element: {" << it->first << ", " << it->second << "}" << std::endl; // Output: {1, "one"}

    return 0;
}

end():

Returns an iterator to the end of the map (past-the-end key-value pair).

Time Complexity: Constant time (O(1)).
Space Complexity: Constant space (O(1)).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.end();
    --it; // Move iterator to the last key-value pair
    std::cout << "Last element: {" << it->first << ", " << it->second << "}" <<

 std::endl; // Output: {3, "three"}

    return 0;
}

rbegin():

Returns a reverse iterator to the beginning of the reversed map (last key-value pair).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.rbegin();
    std::cout << "First element (reversed): {" << it->first << ", " << it->second << "}" << std::endl; // Output: {3, "three"}

    return 0;
}

rend():

Returns a reverse iterator to the end of the reversed map (before-the-beginning key-value pair).

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.rend();
    --it; // Move iterator to the last key-value pair in the reversed map
    std::cout << "Last element (reversed): {" << it->first << ", " << it->second << "}" << std::endl; // Output: {1, "one"}

    return 0;
}