How to Use std::map with Custom Comparator in C++

In C++, you can use a std::map with a custom comparator by defining a struct or class with an operator() that compares keys, then passing it as the third template argument to std::map. This lets you control how keys are ordered inside the map.

Syntax

The syntax to declare a std::map with a custom comparator is:

std::map<KeyType, ValueType, Comparator> mapName;

Here:

• KeyType is the type of keys.
• ValueType is the type of values.
• Comparator is a callable type (like a struct with operator()) that defines how to compare two keys.

The comparator must return true if the first key is considered less than the second key.

cpp

struct CustomCompare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // Reverse order (descending)
    }
};

std::map<int, std::string, CustomCompare> myMap;

Example

This example shows how to create a std::map with a custom comparator that sorts keys in descending order.

cpp

#include <iostream>
#include <map>
#include <string>

struct DescendingCompare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // Sort keys in descending order
    }
};

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

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

    return 0;
}

Output

3: three
2: two
1: one

Common Pitfalls

Common mistakes when using a custom comparator with std::map include:

• Not making the comparator const or not marking operator() as const.
• Returning true for equal keys instead of ensuring strict weak ordering.
• Using a comparator that does not provide a strict weak ordering, which can cause undefined behavior.
• Forgetting to pass the comparator as the third template argument to std::map.

Example of a wrong comparator and the fixed version:

cpp

struct WrongCompare {
    // Incorrect: returns true if keys are equal or a < b, breaks strict weak ordering
    bool operator()(const int& a, const int& b) const {
        return a >= b;
    }
};

struct CorrectCompare {
    bool operator()(const int& a, const int& b) const {
        return a < b; // Proper strict weak ordering
    }
};

Quick Reference

• Define a comparator struct/class with bool operator()(const KeyType&, const KeyType&) const.
• Pass the comparator as the third template argument to std::map.
• The comparator must implement strict weak ordering.
• Use the comparator to customize key sorting (e.g., descending order).

Key Takeaways

Use a struct or class with operator() to define a custom comparator for std::map keys.

Pass the comparator as the third template argument to std::map to control key ordering.

Ensure the comparator implements strict weak ordering to avoid undefined behavior.

Custom comparators allow sorting keys in any order, such as descending or by custom rules.