How to Create My Own Comparator For a Map

How can I create my own comparator for a map?

std::map takes up to four template type arguments, the third one being a comparator. E.g.:

struct cmpByStringLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

// ...
std::map<std::string, std::string, cmpByStringLength> myMap;

Alternatively you could also pass a comparator to maps constructor.

Note however that when comparing by length you can only have one string of each length in the map as a key.

Writing a custom comparator for a C++ map which has a custom defined key

Inside your operator(), simply compare the no values if the year values are equal:

struct Compare {
    bool operator()(const key &lhs, const key &rhs) const {
        if (lhs.year == rhs.year) {
            return lhs.no < rhs.no;
        }
        return lhs.year < rhs.year;
    }
};

And yes, a comparator can be implemented as a standalone function instead:

bool Compare (const key &lhs, const key &rhs) {
    if (lhs.year == rhs.year) {
        return lhs.no < rhs.no;
    }
    return lhs.year < rhs.year;
}

Alternatively, you can have your comparator use std::tie() to compare your key fields. See @Jarod42's answer.

Though, it would make more sense to implement operator< for your key type instead:

struct key {
    int year;
    int no;

    bool operator<(const key &rhs) const {
        if (year == rhs.year) {
            return no < rhs.no;
        }
        return year < rhs.year;
    }
};

Or

struct key {
    int year;
    int no;
};

bool operator<(const key &lhs, const key &rhs) {
    if (lhs.year == rhs.year) {
        return lhs.no < rhs.no;
    }
    return lhs.year < rhs.year;
}

Then you don't need a separate comparator:

map<key, detail> details_map;

Map constructor with comparator

This works:

std::sort(vec.begin(), vec.end(), cmp());

because function templates can deduce their template arguments from the provided arguments. For stl containers this does not work because you're not calling a template function, but declaring a specialization of a class template.

std::map<int, int> mp(cmp()); // Not working
std::map< int, int, cmp> mp; // Works fine.

For classes, if you provide any template parameters explicitly, you must provide them all (and for pre-c++17 you must provide them period.) The Compare template argument (3rd arg) defaults to std::less<Key> unless you tell it otherwise, as your example demonstrates.

This is just how c++ is. There's nothing you're doing wrong, but wanting to omit that parameter is not going to work.

Your lambda example has an identical explanation.

C++17 added Class Template Argument Deduction (CTAD) which works only if you allow it to deduce (or default) all the template parameters. You cannot explicitly provide any, or CTAD is disabled. With CTAD it is possible, but not advisable.
For example, you can declare a map like this:

std::map m{{std::pair{0, 0}}, std::greater<>{}};

But 1) this is rather ugly and is probably worse solution than the problem it's trying to solve, and 2) it creates the map with an initial element in it. The only other constructor that might work is if you already have an existing map with the correct key/value types, and provide an empty range of iterators into it to your constructor to create an empty object copy.

// also possible, assuming you have m1, you can use an 
// empty range (from end to end, for example)
std::map<int, int> m1;

// CTAD works here but will make people blink when they see it
std::map m2{end(m1), end(m1),  std::greater<>{}};

But this is kind of a contrived situation. If you don't already have m1, then it's not really a solution. To be clear, I'm not advising this, only mentioning it for completeness.

In short, unless you are wanting to do gymnastics and create an atrocity of code, you should just provide the type of the comparison as a template argument to containers.

How to create a map with custom class/comparator as key

Why isn't your version working?

You did well to create your own comparison function. To answer your question, you have an error in your operator<() function such that only returns true if m_f is outside of tolerance and m_t is within tolerance, which I'm guessing is not what you desired. Let's take a look.

int s_cmp = (abs(itemKey.m_f - m_f) > m_fEpsilon);

The above line basically is checking whether this->m_f and itemKey.m_f are within tolerance of eachother (meaning equal to each other). That is probably what was intended. Then you say

if (s_cmp == 0)
{
    return (abs(itemKey.m_t - m_t) > m_tEpsilon);
}

If s_cmp is true, then it will have the value of 1, and it will have a value of 0 for false (meaning that they are not within tolerance of each other). Then you return true if the m_t value is within tolerance. Up to this point, you return true if m_f is not equal (according to tolerance) and if m_t is equal (according to tolerance). Then your last line of code

return s_cmp < 0;

will return true always since a boolean converted to an integer cannot ever be negative.

How to get it working?

#include <iostream>
#include <string>
#include <map>
#include <cmath>  
#include <vector>

struct ItemKey
{
    double m_t;
    double m_f;
    static constexpr double t_eps = 3;
    static constexpr double f_eps = 0.1;

    ItemKey(double t, double f) : m_t(t), m_f(f) {}

    bool operator<(const ItemKey& other) const
    {
        // Here it is assumed that f_eps and t_eps are positive
        // We also ignore overflow, underflow, and NaN
        // This is written for readability, and assumed the compiler will be
        // able to optimize it.
        auto fuzzy_less_than = [] (double a, double b, double eps) {
          return a < b - eps;
        };
        bool f_is_less_than    = fuzzy_less_than(this->m_f, other.m_f, f_eps);
        bool f_is_greater_than = fuzzy_less_than(other.m_f, this->m_f, f_eps);
        bool f_is_equal        = !f_is_less_than && !f_is_greater_than;
        bool t_is_less_than    = fuzzy_less_than(this->m_t, other.m_t, t_eps);

        return f_is_less_than || (f_is_equal && t_is_less_than);
    }
};

int main()
{
    using namespace std;

    // The pairs are the respective values of m_t and m_f.
    vector<pair<double, double>> pairs;

    // These two should belong in one bucket
    // -> (109.9, 9.0), because m_f differs by 0.09 and m_t differs by just 1
    pairs.emplace_back(109.9, 9.0);
    pairs.emplace_back(110.9, 9.09);

    // This one is separate from above two beause even though m_t is in range,
    // m_f is beyong tolerance level
    pairs.emplace_back(109.5, 10.0);

    // Same for this as well, here both m_t and m_f are beyong tolerance of any
    // of the two categories found above
    pairs.emplace_back(119.9, 19.0);

    // This one matches the second bucket - (109.5, 10.0)
    pairs.emplace_back(109.9, 10.05);

    // And this one too.
    pairs.emplace_back(111.9, 9.87);

    map<ItemKey, size_t> itemMap;

    for (const auto& item: pairs)
    {
        ItemKey key(item.first, item.second);
        auto iter = itemMap.find(key);
        if (iter  == itemMap.end())
        {
            itemMap[key] = 1;
        }
        else
        {
            itemMap[iter->first] = itemMap[iter->first] + 1;
        }
    }

    // The map should have three keys
    // - (109.9, 9.0) -> count 2
    // - (109.5, 10.0) -> count 3
    // - (119.9, 19.0) -> count 1
    cout << itemMap.size();

    cout << "itemMap contents:" << endl;
    for (auto& item : itemMap) {
        cout << "  (" << item.first << ", " << ")" << endl;
    }

    return 0;
}

There are a few things I changed above. I have a few suggestions also unrelated to the programming mistake:

1. Do not store boolean values into integer variables.
   There's a reason that C++ introduced the bool type.
2. Write your code to be readable and in a way that the compiler
   can easily optimize. You may notice I used a lambda expression
   and multiple booleans. Smart compilers will inline the calls to
   that lambda expression since it is only used within the local scope.
   Also smart compilers can simplify boolean logic and make it
   performant for me.
3. The m_tEpsilon and m_fEpsilon are probably not good to be
   changable variables of the class. In fact, it may be bad if one
   object has a different epsilon than another one. If that were the
   case, which do you use when you do the < operator? For this
   reason, I set them as static const variables in the class.
4. For constructors, it is better to initialize your variables in the
   initializer list rather than in the body of the constructor. That
   is unless you are doing dynamic resource allocation, then you would
   want to do it in the constructor and make sure to clean it up if
   you end up throwing an exception (preferrably using the RAII
   pattern). I'm starting to get too far off topic :)
5. Even though class and struct are basically identical except for
   the default protection level (class is private by default and
   struct is public by default). It is convention to have it as a
   struct if you want direct access to the member variables. Although,
   in this case, I would probably set your class as immutable. To do
   that, set the m_t and m_f as private variables and have a getter
   m() and f(). It might be a bad idea to modify an ItemKey
   instance in a map after it has been inserted.

Potential problems with this approach

One of the problems you have with your approach here is that it will be dependent on the order in which you add elements. Consider the following pairs to be added: (3.0, 10.0) (5.0, 10.0) (7.0, 10.0). If we add them in that order, we will get (3.0, 10.0) (7.0, 10.0), since (5.0, 10.0) was deemed to be equal to (3.0, 10.0). But what if we were to have inserted (5.0, 10.0) first, then the other two? Well then the list would only have one element, (5.0, 10.0), since bother of the others would be considered equal to this one.

Instead, I would like to suggest that you use std::multiset instead, of course this will depend on your application. Consider these tests:

void simple_test_map() {
    std::map<ItemKey, size_t> counter1;
    counter1[{3.0, 10.0}] += 1;
    counter1[{5.0, 10.0}] += 1;
    counter1[{7.0, 10.0}] += 1;
    for (auto &itempair : counter1) {
       std::cout << "simple_test_map()::counter1: ("
                 << itempair.first.m_t << ", "
                 << itempair.first.m_f << ") - "
                 << itempair.second << "\n";
    }
    std::cout << std::endl;

    std::map<ItemKey, size_t> counter2;
    counter2[{5.0, 10.0}] += 1;
    counter2[{3.0, 10.0}] += 1;
    counter2[{7.0, 10.0}] += 1;
    for (auto &itempair : counter2) {
       std::cout << "simple_test_map()::counter2: ("
                 << itempair.first.m_t << ", "
                 << itempair.first.m_f << ") - "
                 << itempair.second << "\n";
    }
    std::cout << std::endl;
}

This outputs:

simple_test_map()::counter1: (3, 10) - 2
simple_test_map()::counter1: (7, 10) - 1

simple_test_map()::counter2: (5, 10) - 3

And for the multiset variant:

void simple_test_multiset() {
    std::multiset<ItemKey> counter1 {{3.0, 10.0}, {5.0, 10.0}, {7.0, 10.0}};
    for (auto &item : counter1) {
       std::cout << "simple_test_multiset()::counter1: ("
                 << item.m_t << ", "
                 << item.m_f << ")\n";
    }
    std::cout << std::endl;
    std::multiset<ItemKey> counter2 {{5.0, 10.0}, {3.0, 10.0}, {7.0, 10.0}};
    for (auto &item : counter2) {
       std::cout << "simple_test_multiset()::counter2: ("
                 << item.m_t << ", "
                 << item.m_f << ")\n";
    }
    std::cout << std::endl;
    std::cout << "simple_test_multiset()::counter2.size() = "
              << counter2.size() << std::endl;
    for (auto &item : counter1) {
       std::cout << "simple_test_multiset()::counter2.count({"
                 << item.m_t << ", "
                 << item.m_f << "}) = "
                 << counter1.count(item) << std::endl;
    }
    std::cout << std::endl;
}

This outputs

simple_test_multiset()::counter1: (3, 10)
simple_test_multiset()::counter1: (5, 10)
simple_test_multiset()::counter1: (7, 10)

simple_test_multiset()::counter2: (5, 10)
simple_test_multiset()::counter2: (3, 10)
simple_test_multiset()::counter2: (7, 10)

simple_test_multiset()::counter2.count({3, 10}) = 2
simple_test_multiset()::counter2.count({5, 10}) = 3
simple_test_multiset()::counter2.count({7, 10}) = 2
simple_test_multiset()::counter2.size() = 3

Note that count() here returns the number of elements within the multiset that are considered equal to the ItemKey passed in. This may be advantageous for situations where you want to ask "how many of my points are within my tolerance of a new point?"

Good luck!

Defining a map with custom comparator where the value datastructure also has custom comparator

Interesting problem. The latter portion (priority order based on the mapped-from key value) presents the real challenge.

Map Custom Key Comparison

The basic three methods from key comparison to a map are:

• Provide an operator < member override for the map key type, OR
• Provide a functor type as the comparator for the map, OR
• Provide a free-function.

The most common of these is the first, simply because it's the easiest to implement and visualize. The default comparator for a map is std::less<K> where K is the key type. The standard library std::less defaults to attempt an operator < comparison, in effect it does this:

bool isLess = (a < b)

where a and b are both your key type. Therefore, a simple member const operator < overload will fit the requirements and get you what you want:

struct Node {
    Node(int a=0, int b=0)
        : x(a), y(b)
    {
    }

    int x, y;

    // called by default std::less
    bool operator <(const Node& rhs) const
    {
        return (x < rhs.x) || (!(rhs.x < x) && y < rhs.y);
    }
    
    // simple distance calculation between two points in 2D space.
    double distanceFrom(Node const& node) const
    {
        return std::sqrt(std::pow((x - node.x), 2.0) + std::pow((y - node.y), 2.0));
    }

    friend std::ostream& operator <<(std::ostream& os, Node const& node)
    {
        return os << '(' << node.x << ',' << node.y << ')';
    }
};

This supports a strict weak order and will suffice. The other options are a little bit more complicated, but not by much. I'll not cover them here, but there are pleny of questions on SO that will.

Note: I added the distanceFrom and operator << members and friend for later use in the final sample; you'll see them later.

---

Priority Queue Instance Comparison Override

Never done this before, but if there is an easier way I'm certainly open to suggestion. The problem with using a template-type comparator override for your priority queue is you can't really do it. You want each queue to be ordered based on distance to origin, where the origin is the map key for that queue. That means each comparison object must somehow be fed the origin of the map key, and you can't do that with a template-type override (i.e. a compile-time thing).

What you can do, however, is provide an instance comparison override. std::priority_queue allows you to provide a custom comparison object where the queue is created (in our case, when it is inserted into the map as the mapped-to target). A little massaging and we come up with this:

First, a priority functor that takes either no args or a Node.

// instance-override type
struct NodePriority
{
    NodePriority() = default;

    NodePriority(Node node)
        : key(std::move(node))
    {
    }

    // compares distance to key of two nodes. We want these in
    // reverse order because smaller means closer means higher priority.
    bool operator()(const Node& lhs, const Node& rhs) const
    {
        return rhs.distanceFrom(key) < lhs.distanceFrom(key);
    }

private:
    Node key;
};

using NodeQueue = std::priority_queue<Node, std::deque<Node>, NodePriority>;

The using NodeQueue will save us a ton of typing in the sample that follows.

Sample

Using the above we are now ready to build our map and queue. The following creates a random list of ten nodes, each of which carry and x,y in the range of 1..9. We then use those nodes to build ten priority queues, one for each map entry we're creating. The map entries are the diagonal slice (i.e. (1,1), (2,2), (3,3), etc.). With the same the same ten random elements we should see different priority queue orderings as we report the final results.

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <queue>
#include <map>
#include <random>

struct Node {
    Node(int a=0, int b=0)
        : x(a), y(b)
    {
    }

    int x, y;

    // called by default std::less
    bool operator <(const Node& rhs) const
    {
        return (x < rhs.x) || (!(rhs.x < x) && y < rhs.y);
    }

    // simple distance calculation between two points in 2D space.
    double distanceFrom(Node const& node) const
    {
        return std::sqrt(std::pow((x - node.x), 2.0) + std::pow((y - node.y), 2.0));
    }

    friend std::ostream& operator <<(std::ostream& os, Node const& node)
    {
        return os << '(' << node.x << ',' << node.y << ')';
    }
};

// instance-override type
struct NodePriority: public std::less<Node>
{
    NodePriority() = default;

    NodePriority(Node node)
        : key(std::move(node))
    {
    }

    // compares distance to key of two nodes. We want these in
    // reverse order because smaller means closer means higher priority.
    bool operator()(const Node& lhs, const Node& rhs) const
    {
        return rhs.distanceFrom(key) < lhs.distanceFrom(key);
    }

private:
    Node key;
};

using NodeQueue = std::priority_queue<Node, std::deque<Node>, NodePriority>;

int main()
{
    std::mt19937 rng{ 42 }; // replace with  { std::random_device{}() } for random sequencing;
    std::uniform_int_distribution<> dist(1, 9);

    std::map<Node, NodeQueue> myMap;

    // generate ten random points
    std::vector<Node> pts;
    for (int i = 0; i < 10; ++i)
        pts.emplace_back(Node(dist(rng), dist(rng)));

    for (int i = 0; i < 10; ++i)
    {
        Node node(i, i);
        myMap.insert(std::make_pair(node, NodeQueue(NodePriority(node))));
        for (auto const& pt : pts)
            myMap[node].emplace(pt);
    }

    // enumerate the map of nodes and their kids
    for (auto& pr : myMap)
    {
        std::cout << pr.first << " : {";
        if (!pr.second.empty())
        {
            std::cout << pr.second.top();
            pr.second.pop();
            while (!pr.second.empty())
            {
                std::cout << ',' << pr.second.top();
                pr.second.pop();
            }
        }
        std::cout << "}\n";
    }
}

Note: the pseudo random generator is always seeded with 42 to have a repeatable sequence. When you decide to turn this loose with non-repeatable testing just replace that seed with the one provided in the comment next to the declaration.

Output (yours will vary, of course).

(0,0) : {(3,1),(5,1),(3,5),(5,3),(5,4),(5,5),(1,9),(6,7),(5,8),(6,8)}
(1,1) : {(3,1),(5,1),(3,5),(5,3),(5,4),(5,5),(6,7),(1,9),(5,8),(6,8)}
(2,2) : {(3,1),(3,5),(5,1),(5,3),(5,4),(5,5),(6,7),(5,8),(1,9),(6,8)}
(3,3) : {(3,1),(3,5),(5,3),(5,4),(5,5),(5,1),(6,7),(5,8),(6,8),(1,9)}
(4,4) : {(5,4),(5,5),(3,5),(5,3),(5,1),(3,1),(6,7),(5,8),(6,8),(1,9)}
(5,5) : {(5,5),(5,4),(3,5),(5,3),(6,7),(5,8),(6,8),(5,1),(3,1),(1,9)}
(6,6) : {(6,7),(5,5),(6,8),(5,4),(5,8),(3,5),(5,3),(5,1),(1,9),(3,1)}
(7,7) : {(6,7),(6,8),(5,8),(5,5),(5,4),(3,5),(5,3),(1,9),(5,1),(3,1)}
(8,8) : {(6,8),(6,7),(5,8),(5,5),(5,4),(3,5),(5,3),(1,9),(5,1),(3,1)}
(9,9) : {(6,8),(6,7),(5,8),(5,5),(5,4),(3,5),(5,3),(1,9),(5,1),(3,1)}

I'l leave you to verify the accuracy of the distanceFrom calculations, but hopefully you get the idea.

How to set custom comparator in Java Map of Map?

You're attempting to set the Comparator in the type argument, which is invalid syntax. The type arguments only specify the types, they aren't actual instances. What you would need to do is use the correct Comparator for each TreeMap you put into the outer Map:

Map<Character, TreeMap<Integer, String>> map = new HashMap<>();

TreeMap<Integer, String> treeMap = new TreeMap<>((x, y) -> y - x);
map.put('A', treeMap);

Note you cannot force, via the compiler, that every TreeMap use the same Comparator implementation.

How to write a custom Comparator for TreeMap in Java?

You need to write your own comparator for this and use it in TreeMap, e.g.:

public class StringComparator implements Comparator<String> {

    @Override
    public int compare(String s1, String s2) {
        return s1.length() == s2.length() ? s1.compareTo(s2) : s1.length() - s2.length();
    }

    public static void main(String[] args) throws JsonParseException, JsonMappingException, IOException {
        Map<String, String> map = new TreeMap<>(new StringComparator());
        map.put("IBARAKI", "MitoCity");
        map.put("TOCHIGI", "UtunomiyaCity");
        map.put("GUNMA", "MaehashiCity");
        map.put("SAITAMA", "SaitamaCity");
        map.put("CHIBA", "ChibaCity");
        map.put("TOKYO", "Sinjyuku");
        map.put("KANAGAWA", "YokohamaCity");

        System.out.println(map);
    }

}

This does not handle null values but you can add the handling if you are expecting null values in your use case.

C++ Comparator function to specifiy specific key ordering for map?

This is how you would create comparator function for map to create a specific sort order for a number of keys.

The inspiration from other answers allowed me to write my own answer that addresses my question exactly and in the best way possible (IMO).

RUN: https://ideone.com/7H5CZg

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// create vector holding desired ordering
vector<string> order({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create sort function for map   
struct my_comparator {
    bool operator()(const string &s1, const string &s2) {
        // find() - it.begin() gives you the index number. 
        int a = find(order.begin(), order.end(), s1) - order.begin();
        int b = find(order.begin(), order.end(), s2) - order.begin();
        return a < b; // lower index < higher index
    }
};

int main() {
    // create the map
    map<string,string, my_comparator> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

output: a=legato i=3 vl=3 rr=2

---

UPDATE: This will usually be faster, it uses a map instead of vector to look up key order.

You can apply this way of doing things to the other answers as well.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// using a map is faster in most cases (with more keys and such)
map<string, int> maporder({ {"a", 1}, {"d", 2}, {"i", 3}, {"n", 4}, {"ns", 5}, {"ne", 6}, {"vl", 7}, {"rr", 8} });

// create sort function for map   
struct mapcomp {
    bool operator()(const string &s1, const string &s2) {
         // compares ints by looking them up with the input string
        return maporder[s1] < maporder[s2];
    }
};

int main() {
    // create the map
    map<string,string, mapcomp> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

Member function as a map comparator?

You have several options:

In C++11 you can use a lambda:

std::map<std::string, std::string, bool (*)(std::string, std::string)> myMap(
    [](string lhs, int rhs){ // You may need to put [this] instead of [] to capture the enclosing "this" pointer.
       return MapComparator(lhs, rhs); // Or do the comparison inline
    });

If the function is static, use :: syntax:

class MyClass {
public:
    static bool MyClass::MapComparator(std::string left, std::string right);
};
...
std::map<std::string, std::string, bool (*)(std::string, std::string)> myMap(MyClass::MapComparator);

If the function is non-static, make a static wrapper, member or non-member, and call a member function from it.

---

Related Topics