Why isn't key_comp() working?

[Arslan7041]

Simple code below which is supposed to print out the maximum VALUE in a map (thus, the expected output below was "19").

I tried it with lambda expression and it worked perfectly. Then I thought I could compact the code by simply using std::map::key_compare already built within std::map. (Its my understanding that key_comp() compares values, and not keys as the name suggests). However, this doesn't work.

Im probably not understanding how key_comp() works, so If someone could clarify this for me, it would be much-appreciated.

#include <iostream>
#include <algorithm>
#include <map>

int main()
{
    std::map< int, int > m;

    m[1] = 2;
    m[2] = 3;
    m[3] = 3;
    m[4] = 19;
    m[5] = 6;
    m[6] = 2;

    std::cout << "Max value = " <<  std::max_element(m.begin(), m.end(), m.key_comp())->second; 

}

[ne555]

> However, this doesn't work.
Be precise, damn it

code doesn't compile

|| /usr/include/c++/6.2.1/bits/predefined_ops.h: In instantiation of ‘constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = std::_Rb_tree_iterator<std::pair<const int, int> >; _Iterator2 = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = std::less<int>]’:
/usr/include/c++/6.2.1/bits/stl_algo.h|5524 col 12| required from ‘constexpr _ForwardIterator std::__max_element(_ForwardIterator, _ForwardIterator, _Compare) [with _ForwardIterator = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<std::less<int> >]’
/usr/include/c++/6.2.1/bits/stl_algo.h|5575 col 43| required from ‘constexpr _FIter std::max_element(_FIter, _FIter, _Compare) [with _FIter = std::_Rb_tree_iterator<std::pair<const int, int> >; _Compare = std::less<int>]’
foo.cpp|16 col 64| required from here
/usr/include/c++/6.2.1/bits/predefined_ops.h|123 col 18| error: no match for call to ‘(std::less<int>) (std::pair<const int, int>&, std::pair<const int, int>&)’
||          { return bool(_M_comp(*__it1, *__it2)); }
||                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/6.2.1/bits/stl_function.h|385 col 7| note: candidate: constexpr bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = int]
||        operator()(const _Tp& __x, const _Tp& __y) const
||        ^~~~~~~~
/usr/include/c++/6.2.1/bits/stl_function.h|385 col 7| note:   no known conversion for argument 1 from ‘std::pair<const int, int>’ to ‘const int&’

There you can see the

error: no match for call to ‘(std::less<int>) (std::pair<const int, int>&, std::pair<const int, int>&)’

`key_comp()' returns a functor that operates on `int' (your key type), but you are trying to use it to compare pairs (value_type of the iterator)

> Its my understanding that key_comp() compares values, and not keys as the name suggests
you misunderstood.
http://www.cplusplus.com/reference/map/map/key_comp/

Returns a copy of the comparison object used by the container to compare keys.

[Arslan7041]

Im still a bit confused. How do I solve this problem then?

I tried this but it didn't work:

int main()
{
    std::map< int, int > m;
    using myMap = std::map< int, int >;
    using myPair = myMap::value_type;

    m[1] = 2;
    m[2] = 3;
    m[3] = 3;
    m[4] = 19;
    m[5] = 6;
    m[6] = 2;

    std::cout << "Max value = " << std::max_element(m.begin(), m.end(), m.key_comp(myPair a.second, myPair b.second) )->second;

}

I feel like im completely misusing these comparison functions in std::map.

The error im getting doesn't really help me:

expected primary-expression before "a" token
expected primary-expression before "b" token

[ne555]

you need to pass a functor that receives two pairs and compares their second element. You said that already solve it with lambdas, ¿so what's the problem then?

> m.key_comp(myPair a.second, myPair b.second)
key_comp() doesn't receive any arguments, the functor returned by `key_comp()' works on key_type, not pair_type, and that is not how you pass arguments to a function

[Arslan7041]

you need to pass a functor that receives two pairs and compares their second element. You said that already solve it with lambdas, ¿so what's the problem then?

Yes, it works with lambda, passing a functor, as well as passing a function. I've tried all 3 and it works.

But right now im just learning how to use key_comp(), as im not fully understanding how it works. Can you please post an example code using key_comp() to find max value in a map? I feel like seeing it explicitly is the only way I'll understand.

Also, why does the code below give me max key? Im using value_comp() here, isn't that supposed to compare values in the map?

#include <iostream>
#include <algorithm>
#include <functional>
#include <map>

using myMap = std::map< int, int >;
using myPair = myMap::value_type;

int main()
{
    myMap m;

    m[1] = 2;
    m[2] = 3;
    m[3] = 3;
    m[4] = 19;
    m[5] = 6;
    m[6] = 2;

    std::cout << "Max key = " << std::max_element(m.begin(), m.end(), m.value_comp() )->first; // prints 6 (maximum key). 

}

[JLBorges]

#include <iostream>
#include <map>
#include <functional>

int main()
{
    {
        using map_type = std::map< int, std::string > ;
        const map_type map { {1,"klm"}, {3,"abcdef"}, {6,"ghijk"}, {5,"klm"}, {4,"kl"}, {2,"klm"} };

        // map_type::key_compare compares keys ie. map_type::key_type ie. int
        const /* auto */ map_type::key_compare cmpk = map.key_comp() ; // std::less<int>
        const /* int */ map_type::key_type ka = 67, kb = 78 ;
        std::cout << std::boolalpha << cmpk(ka,kb) << '\n' ; // 67 < 78, true

        // map_type::value_compare compares values ie. map_type::value_type
        // ie. std::pair< const map_type::key_type, map_type::mapped_type > ;
        const /* auto */ map_type::value_compare cmpv = map.value_comp() ;
        const /* int */ map_type::value_type va = { 67, "hello" }, vb = { 78, "world" } ;

        // cmpv(va,vb) compares va, vb with va.first < vb.first (cmpv ignores va.second, vb.second)
        std::cout << std::boolalpha << cmpv(va,vb) << '\n' ; // 67 < 78, true
    }

    {
        using map_type = std::multimap< int, std::string, std::greater<> > ;
        const map_type map { {1,"klm"}, {3,"abcdef"}, {1,"ghijk"}, {3,"klm"}, {3,"kl"}, {1,"klm"} };

        // map_type::key_compare compares keys ie. map_type::key_type ie. int;
        const /* auto */ map_type::key_compare cmpk = map.key_comp() ; // std::greater<>
        const /* int */ map_type::key_type ka = 67, kb = 78 ;
        std::cout << std::boolalpha << cmpk(ka,kb) << '\n' ; // !(67>78), false

        // map_type::value_compare compares values ie. map_type::value_type
        // ie. std::pair< const map_type::key_type, map_type::mapped_type > ;
        const /* auto */ map_type::value_compare cmpv = map.value_comp() ;
        const /* int */ map_type::value_type va = { 67, "8hello" }, vb = { 67, "1world" } ;

        // cmpv(va,vb) compares va, vb with va.first > vb.first (cmpv ignores va.second, vb.second)
        std::cout << std::boolalpha << cmpv(va,vb) << '\n' ; // !(67>67), false
    }
}

http://coliru.stacked-crooked.com/a/1954a668cd944965
http://rextester.com/YXH91164

[Arslan7041]

Thank you JLBorges, that was clear and quite easy to understand.

Now, is there a way to use key_comp() or value_comp() with std::max_element to find the maximum mapped value in a map? If so, how would that be done?

[ne555]

no.

[JLBorges]

> is there a way to use key_comp() or value_comp() with std::max_element
> to find the maximum mapped value in a map?

No.

std::map<> requires that it must be able to compare keys:
either its key_type is LessThanComparable or we must provide a binary predicate to compare keys.

There is no such requirement for its mapped_type; the map has no information about how to compare the mapped values (or, for that matter, whether the mapped values can be compared at all).
Ergo, the value_compare of a map compares only the keys (it ignores the mapped values.)

[Arslan7041]

Right, so I was going about this wrong from the start.

So the only way to get max mapped value is to use lambda or to pass a functor/function as a third parameter in std::max_element.

Thank you all for your responses.

[LA48b7Xj]

Also, you could write a loop to find the max value or create an algorithm similar to max_element that compares the second member.

#include <iostream>
#include <map>

template<class Iter> Iter MaxMapVal(Iter first, Iter last)
{
    if (first == last)
        return last;

    Iter largest = first;
    ++first;

    for (; first != last; ++first)
        if (largest->second < first->second)
            largest = first; //correction, thanks to ne555

    return largest;
}

int main()
{
    std::map< int, int > m;

    m[1] = 2;
    m[2] = 3;
    m[3] = 3;
    m[4] = 19;
    m[5] = 6;
    m[6] = 2;

    std::cout << "Max value = " <<  MaxMapVal(m.begin(), m.end())->second << '\n';
}

[Arslan7041]

@krako, of course, that is another way. But I still prefer the lambda function method as it is much easier, and less code.

[ne555]

> largest->second = first->second;
you are modifying the map there

[Arslan7041]

@ne555: How? He created 'largest' as a local object of type Iter, and is simply assigning the max value to its 'second' field.

[LA48b7Xj]

The iterator referred to an element in the map I shouldn't of wrote to it, I made the correction. I should of tested it properly sorry about that.

[Arslan7041]

EDIT: ah, now I see why the correction was necessary. The iterator to the pair returned needs to have consistent key and value.