How properly pass comparator to another template function

Question

I need a function that will take two iterators and a custom comparator to compare values of this iterators. I don't want use additional template argument for this. I've implemented it in this way:

template<typename T>
void foo(T begin, T end,
  function<bool(decltype(*begin), decltype(*begin))> compare = less<decltype(*begin)>())
{
    // I want to use 'compare' as: "compare(*begin, *begin);"
}

This code has been compiled normally by clang, but on GCC 5.4.0 I've got some errors:

binary_heap.cpp:10:79: error: local variable 'begin' may not appear in this context
   function<bool(decltype(*begin), decltype(*begin))> compare = less<decltype(*begin)>())
                                                                               ^
binary_heap.cpp:10:85: error: template argument 1 is invalid
   function<bool(decltype(*begin), decltype(*begin))> compare = less<decltype(*begin)>())

How to correct this code so that it can be successfully compiled on both clang and GCC? Or maybe are there a more suitable solution for defining such function?

Why do you not want to use an additional template argument for this? — Yakk - Adam Nevraumont, Oct 20 '16 at 18:47

score 5 · Answer 1 · answered Oct 20 '16 at 18:46

You cannot use a parameter in a default argument, even in an unevaluated context (although the Standard should probably be amended to loosen that restriction). Instead of decltype(*begin), use

decltype(*std::declval<T&>())

Edit: Actually, that probably doesn't do what you want, since if applying the * operator yields an lvalue, then the decltype specifier will resolve to an lvalue reference, but you would want the unreferenced type to be the argument to std::less. Better to use:

typename std::iterator_traits<T>::value_type

Edit 2: I agree with krzaq, it's better to just add another template parameter.

score 4 · Answer 2 · edited May 23 '17 at 11:48

4

You're pessimizing performance of your algorithm by a lot just by forcing the use of function (more details here). Just take template deduced Compare and you're golden:

template<typename T, typename Compare = std::less<typename iterator_traits<T>::value_type>>
void foo(T begin, T end, Compare compare = {})
{
    // I want to use 'compare' as: "compare(*begin, *begin);"
}

Interestingly, standard algorithms force/suggest use of lightweight functors by taking them by value instead of a forwarding reference.

To answer the actual question: you can use std::less<>, which defaults to std::less<void> and has templated operator() doing the actual comparisons:

template<typename T>
void foo(T begin, T end,
  function<bool(decltype(*begin), decltype(*begin))> compare = less<>())
{
    // I want to use 'compare' as: "compare(*begin, *begin);"
}

edited May 23 '17 at 11:48

Community

1
1

answered Oct 20 '16 at 18:48

krzaq

16,240
4
46
61

Out of curiosity, in what ways do you pessimize the performance by using `function`? – RyanP Oct 20 '16 at 18:51
@krzaq Thank you! If I interested in best performance, what kind of solution should I choose? – 0x1337 Oct 20 '16 at 18:54
@0x1337 I'd pass a template parameter without much interference. It makes for slightly worse error messages (hopefully to be fixed with concepts), but is readable, fast and consistent with the standard library. Look how `Compare` is taken by [`std::sort`](http://en.cppreference.com/w/cpp/algorithm/sort) – krzaq Oct 20 '16 at 18:57
1

I'd use `{}` instead of `Compare{}` following DRY. – Yakk - Adam Nevraumont Oct 20 '16 at 19:40

score 3 · Answer 3 · edited Oct 20 '16 at 18:58

Add another template parameter Compare. This makes inlining easier by the compiler. While I'm at it support Sentinels.

template<class It, class Sentinel, class Compare=std::less<void>>
void foo(It begin, Sentinel end, Compare cmp={}) {
}

However, assuming C++14, barring the above, I'd do this:

template<class T>
using comparator_sig = bool(T const&,T const&);
template<class T>
using comparator = std::function<comparator_sig<T>>;
template<class It>
using compare_inside_it = comparator<
  typename std::iterator_traits<It>::value_type
>;

template<typename T>
void foo(T begin, T end, compare_inside_it<T> compare = less<>) {
}

in C++11 I would write my own less<void>:

struct compare_less {
  template<class T>
  bool operator()( T const& lhs, T const& rhs ) const {
    return std::less<T>{}(lhs, rhs);
  }
};

and do:

template<typename T>
void foo(T begin, T end, compare_inside_it<T> compare = compare_less{}) {
}

or even just do:

template<typename T>
void foo(T begin, T end, compare_inside_it<T> compare = {}) {
  if (!compare) compare=compare_less{};
}

How properly pass comparator to another template function

3 Answers3