C++ Flat Map

In this article, you will learn about the flat_map in C++ with its example.

A flat map: what is it?

A data structure called a flat_map combines the characteristics of a vector and a map. In essence, it is an ordered associative container that stores key - value pairs in a contiguous memory architecture, much like a vector.

There are several significant implications for this design choice's use:

1. Ordered items:

• ✅ The items in a flat map are kept in a certain order determined by the key, in contrast to std::unordered_map , which has no particular order.
• ✅ It is helpful in situations where element order must be maintained.

1. Quick Lookup:

• ✅ A flat map, like std::map , enables quick lookups depending on the keys.
• ✅ Because the keys are maintained in order, search operations can be performed with logarithmic time complexity .

1. Vector-Like Features:

• ✅ Like a vector, a flat map lets you traverse through the elements quickly because the data is stored consecutively.

1. Low Memory Overhead:

• ✅ As a flat map stores its items in a contiguous manner, it generally has less memory overhead than a std::map.

1. Value Semantics:

• ✅ A flat_map stores key-value pairs together, as opposed to std::map, which stores keys and values independently.
• ✅ This makes using the data structure easier.

What distinguishes it from other implementations of maps?

It's important to contrast a flat_map with other C++ map implementations to fully appreciate its benefits:

1. std::map

• ✅ A balanced binary search tree-based container is std::map .
• ✅ It provides logarithmic complexity and keeps the elements sorted for the majority of operations.
• ✅ However, because of the tree structure, there is some overhead, which could lead to a slightly greater memory consumption.

1. std::Unordered map

• ✅ Because std::unordered_map is built on a hash table, most operations have constant-time complexity.
• ✅ However, it does not preserve a particular sequence for the elements.
• ✅ While it uses less memory than std::map , it isn't the best option when element order is important.

1. flat map

• ✅ The advantages of both worlds are combined in a flat_map, which provides vector-like iteration, quick lookups, ordered items, and little memory overhead.
• ✅ It is a desirable option for many use scenarios due to its ordered elements and contiguous storage, particularly when you require both efficient key-based access and a predictable element order.

When to Use flat_map:-

There are several situations where you can use the flatmap. In the following situations, a flatmap might be a wise option:

1. Maintaining Element Order:

• ✅ A flat map is a great option if you need to preserve a particular element order.
• ✅ For jobs like sorting and showing data, it can be helpful.

1. Key-Based Lookup:

• ✅ A flat_map is a suitable choice if you need a quick key-based lookup with logarithmic complexity.
• ✅ In terms of efficiency, it finds a middle ground between std::map and std::unordered_map .

1. Iterating Efficiently:

• ✅ A flat map offers contiguous storage, which makes it the best option when you need to iterate across elements as if you were using a vector.

1. Low Memory Overhead:

• ✅ Because a flat_map's storage is contiguous, it usually has less memory overhead than a std::map when memory use is an issue.

Program:

Let's take an example to illustrate the use of flat_map in C++.

#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
   std::map<int, std::string> myMap;
    std::vector<std::pair<int, std::string>> flatMap;
    // Insert key-value pairs
    myMap[1] = "Go";
    myMap[2] = "for";
    myMap[3] = "DSA";
    myMap[4] = "Coding";
    // Convert the std::map to a flat_map (std::vector)
    for (const auto& pair : myMap) {
        flatMap.push_back(pair);
    }
    // Print the map before erasing
    cout << "Map before erasing:" << endl;
    for (const auto& pair : flatMap) {
        cout << "Key: " << pair.first
            << ", Value: " << pair.second << endl;
    }
    // Erase an element by key
    for (auto it = flatMap.begin(); it != flatMap.end(); ) {
        if (it->first == 3) {
            it = flatMap.erase(it);
        } else {
            ++it;
        }
    }
    // Print the map after erasing by key
    cout << "Map after erasing by key:" << endl;
    for (const auto& pair : flatMap) {
        cout << "Key: " << pair.first
            << ", Value: " << pair.second << endl;
    }
    // Clear the flat_map (std::vector)
    flatMap.clear();
    // Check if the flat_map is empty after clearing
    if (flatMap.empty()) {
        cout << "The flat_map is empty after clearing." << endl;
    }
    return 0;
}

Output:

Explanation:

• ✅ Include Headers: The required C++ standard library headers are included at the start of the code. It comprises <map> to build a map, <vector> to create a vector, and <iostream> for input and output.
• ✅ Make a std::vector and std::map: We define two types of data structures: two objects: a std::vector of std::pair<int, std::string> named flatMap and a std::map named myMap. The vector will mimic a flat map, and the map will hold key-value pairs.
• ✅ Insert Key-Value Pairs into the std::map: The myMap is updated with four key-value pairs using square bracket notation. Strings are the values, and integers are the keys.
• ✅ Convert std::map to a Flat Map (Vector): Using the push_back method, the code iterates through the myMap adding each key-value pair to the flatMap vector. It mimics how a std::map is changed into a flat map that is represented by a std::vector.
• ✅ Print the Map Before Erasing: The code outputs the key-value pairs from the flatMap vector before any erasing takes place. The vector is iterated through, showing each key and value.
• ✅ Clear the Flat Map (Vector): The code utilises the clear method to delete all entries from the flatMap vector to effectively clear the flat map.
• ✅ Check whether the Flat Map is Empty: Lastly, the code uses the empty method to see if the flatMap vector is empty. If it's empty, a notification saying that the cleared flat map is empty is shown.

Conclusion:

Among C++ data structures, the flatmap is a particularly adaptable and effective option for a range of use situations. It combines the minimal memory overhead and vector-like iteration of std::unorderedmap with the ordered items and key-based lookup of std::map.