3

I would like to code a custom comparator for a std::multimap. What I would like to do is to compare the keys, in case they are equal, then compare the values. I'm trying to do it by overloading the operator() in a struct and passing the function object as a third parameter in the std::multimap constructor.

struct CustomComp {
    bool operator()(int key_lhs, int key_rhs){
        if (key_lhs < key_rhs) return true;
        if (key_lhs == key_rhs) //Check values;
        else return false;
    }
};

multimap<int, int, CustomComp> myMap;

How can I access the values, not only the keys, if both are int?

JeJo
  • 30,635
  • 6
  • 49
  • 88
Jules
  • 134
  • 1
  • 10
  • This is not how hashmaps works. You only hash the key, not the value. There is no way to access the value, unless you put the value inside of the key-struct (which would be an overkill and waste memory) – hellow Aug 29 '18 at 09:40
  • 1
    why would you want to do that? Smells like a [xy problem](https://meta.stackexchange.com/questions/66377/what-is-the-xy-problem). What would be the use case? what do you actually want to achieve? – 463035818_is_not_an_ai Aug 29 '18 at 09:41
  • 1
    well ok, the "what do you want to do?" is more or less clear, but why does it have to be a `multimap` ? You could use a `std::map >` instead, would that be fine? – 463035818_is_not_an_ai Aug 29 '18 at 09:43
  • Anything being key compared needs to be part of the key. Period. (its a world gone mad, I know). – WhozCraig Aug 29 '18 at 09:44
  • 1
    What you want to do is not possible. You should tell us why you need such a structure: What do you want to with it? How do you want to access elements? Insert elements? etc. If you can give us the requirements on the structure, we can start giving you advice on which structure is the best for you. – Holt Aug 29 '18 at 10:21
  • The answer below looks interesting. What I want to do is exactly what I explained before. I have a group of pair of int, i.e: (2,3), (2,4), (4,4) (4,5) and I want to sort them not only taking into account the first value, also the second one. In case I have (2,4) and (2,3), I want (2, 3) first no matter if it arrives later to the container. – Jules Aug 30 '18 at 07:46

2 Answers2

2

You can achieve the desired effect with std::multiset<std::tuple<int, int>>. No custom comparator is necessary because std::tuple uses lexicographical comparison (the one you are trying to implement).

Maxim Egorushkin
  • 131,725
  • 17
  • 180
  • 271
  • 1
    That's look interesting. Citing: "In a multiset, the value of an element also identifies it". http://www.cplusplus.com/reference/set/multiset/ – Jules Aug 30 '18 at 07:52
2

What I would like to do is to compare the keys, in case they are equal, then compare the values.

No, you can not make a comparison for std::multimap according to the values.

I would suggest using std::vector< std::pair<int, int> > instead and simply sort. The operator< of std::pair will take care of what you want.

See output here

std::vector< std::pair<int, int> > vec{ {1,2}, {1,-1},{ 2,2 } ,{ -1,1 } };
std::sort(std::begin(vec), std::end(vec));

Update: After reading the other answer(i.e, std::multiset<std::tuple<int, int>>), I was thinking about, how bad is the std::multiset::insert.

Then I came up with the following benchmark, which shows, why should be std::vector at first place in the above problem.

See Quick benchmark online here

Vector-Sort Vs Multimap-Insertion

JeJo
  • 30,635
  • 6
  • 49
  • 88
  • 1
    That is exactly what I was looking for. Thank you. – Jules Aug 30 '18 at 11:49
  • 1
    Owesome!, I am interested in high-perfomance as well. Thanks again. I see results scale the same when compiler optimizations are out, pure algorithm performance due to pick the right data structure. – Jules Aug 31 '18 at 07:18