Introduction to Map Data Structure with Practical Examples

• Map Data Structure
• Hash Map
• Tree Map
• Map in C++ STL
  • Functions in C++ STL Map
• Map Implementation in C++
• Useful Iterators of Map in c++
• Traversing a Map in C++
  • Traversing a Map Using Iterators
  • Traversing a Map Using Range-Based For Loops
• Applications of Map
• Run C Programming Online Compiler

The Map data structure, also known as a dictionary, plays a crucial role in various real-life applications such as database indexing, network routing, caching etc., making it one of the most essential data structures. Its efficiency in storing and retrieving key-value pairs is fundamental for tasks requiring quick and organized access to information. Almost every well-known programming language provides maps in their standard library, such as the map in C++, HashMap in Java, and dictionary in Python.

¶Map Data Structure

A map is a collection of key-value pairs where each key is unique, and each key is associated with a value. It enables quick and efficient retrieval of values based on their corresponding keys. This structure enables fast data retrieval, making maps an excellent choice for scenarios where quick lookups are crucial.

Maps are commonly implemented using either Hash Maps or Tree Structures, such as self-balancing Binary Search Trees (BST). These implementations are crucial for the efficiency and performance of map data structures.

¶Hash Map

A hash map, also known as a hash table maps keys to values using a hash function. The hash function transforms the key into an index within an array, allowing for quick access to the associated value. This mechanism ensures speedy lookups. It also ensures a uniform distribution to minimize collisions. The quality of the hash function directly influences the distribution of keys, impacting the map’s efficiency.
C++, Java, and Python offer hash map implementations in their standard libraries. In C++, it’s std::unordered_map, in Java, it’s HashMap, and in Python, it’s the built-in dictionary.

¶Tree Map

A tree map, implemented as a self-balancing binary search tree, organizes keys in a sorted order, optimizing search, insertion, and deletion operations. With an average time complexity of O(log n) for tasks like insertion and retrieval, tree maps provide a balanced and efficient solution for managing key-value pairs. As self-balancing binary Search tree Red-Black Tree are often preferred over AVL Tree because the re-balancing rotation in Red-Black Trees is an O(1) operation while AVL Trees require an O(log N) operation for re-balancing, making Red-Black Trees more efficient in situations where frequent re-balancing rotations are expected.
C++ offers tree map implementation in the standard library as std::map.

¶Map in C++ STL

A map is an associative container that stores elements in a key-value relationship. In C++, the std::map is based on a self-balancing binary search tree called Red-Black Trees. After an insertion or deletion, Red-Black Trees perform rotations to re-balance the tree. This process involves strategically rotating nodes to maintain the structure’s balance and uphold the properties of a Red-Black Tree.

To use the std::map in C++, we need to include the <map> header file. Syntax :

#include <map>
map<keyDataType, valueDataType> myMap;

¶Functions in C++ STL Map

• insert() Inserts a new key-value pair into the map. For each operation it shows logarithmic time complexity (O(log n)). The insert operation involves searching for the correct position in the binary search tree, which, due to its self-balancing nature, takes logarithmic time. This ensures that the tree remains balanced and maintains its efficiency.

• find() Searches for a specified key in the map. If the key does not exist in the map it returns end() iterator. For each operation it shows logarithmic time complexity (O(log n)). The find operation uses the binary search tree structure, allowing for efficient key lookup in logarithmic time.

• erase() Removes an element from the map. For each operation it shows logarithmic time complexity (O(log n)). The erase operation may involve re-balancing the tree after removal, ensuring that the binary search tree properties are maintained. This process takes logarithmic time.

• size() Returns the number of elements in the map. For each operation it shows constant time complexity (O(1)). The size function typically retrieves a precomputed size, resulting in constant time complexity.

• clear() Removes all elements from the map, leaving it empty.For each operation it shows linear time complexity (O(n)). Clearing the map involves deallocating memory for each element, resulting in a linear time complexity proportional to the number of elements.

• lower_bound() Retrieves an iterator pointing to the first element not less than a given key. For each operation it shows logarithmic time complexity (O(log n)). The lower_bound function utilizes the binary search property of the tree, ensuring efficient searching in logarithmic time.

• count() Returns the number of elements matching a specific key. For each operation it shows logarithmic time complexity (O(log n)). Similar to find, the count operation searches for a specific key in logarithmic time due to the binary search tree structure.

¶Map Implementation in C++

The following example shows the implementations of the discussed functions of the map stl in c++.

#include <iostream>
#include <map>

int main() {
    // Declare a map with int keys and string values
    std::map<int, std::string> myMap;

    // 1. Inserting key-value pairs
    myMap.insert({1, "apple"});
    myMap[2] = "banana";
    myMap[3] = "cherry";

    // 2. Finding a key
    auto search = myMap.find(2);
    if (search != myMap.end()) {
        std::cout << "Found: " << search->second << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    // 3. Erasing an element
    myMap.erase(1);

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

    // 5. Clearing the map
    myMap.clear();
    std::cout << "Size after clearing: " << myMap.size() << std::endl;

    // 6. Using lower_bound
    myMap[4] = "grape";
    myMap[5] = "orange";
    auto lowerBound = myMap.lower_bound(4);
    std::cout << "Lower bound key: " << lowerBound->first << ", value: " << lowerBound->second << std::endl;

    // 7. Using count
    int keyToCount = 5;
    int occurrences = myMap.count(keyToCount);
    std::cout << "Occurrences of key " << keyToCount << ": " << occurrences << std::endl;

    return 0;
}

¶Useful Iterators of Map in c++

• begin() Returns an iterator pointing to the first element of the Map. Used in traversing the key-value pairs of the map.
• end() Returns an iterator pointing one position after the last element of the Map. find() returns the iterator end() if the key is not found.
• rbegin() Returns a reverse iterator pointing to the last element of the Map. Used in traversing the key-value pairs of the map.
• rend() Returns a reverse iterator pointing one position before the first element of the Map. Used in traversing the key-value pairs of the map.

¶Traversing a Map in C++

Traversing a map in C++ can be done using iterators or range-based for loops.

¶Traversing a Map Using Iterators

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "apple";
    myMap[2] = "banana";
    myMap[3] = "cherry";

    // Using iterators to traverse the map
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
    }

    return 0;
}

¶Traversing a Map Using Range-Based For Loops

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;
    myMap[1] = "apple";
    myMap[2] = "banana";
    myMap[3] = "cherry";

    // Using range-based for loop to traverse the map
    for (const auto& pair : myMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    return 0;
}

¶Applications of Map

• Database Indexing: Maps are often used to implement indexes in databases, where keys correspond to unique identifiers, and values represent the associated data.

• Symbol Tables in Compilers: In compiler construction, maps are used as symbol tables to store variable names and their corresponding attributes.

• Caching Mechanisms: Maps are employed in caching systems to store frequently accessed data. The keys can be identifiers, and the values are the cached data.

• Routing Algorithms: Maps can be used in routing algorithms, where keys represent nodes, and values store information about the best routes or distances between nodes.

• Web Servers for Session Management: Maps can be used in web server applications for session management, where session IDs (keys) are associated with user data (values).

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.