Define a function in function declaration using std::iterator traits and auto

Question

Today I tried to implement radix sort. The function must have two variables: begin iterator and end iterator, and can have third: some function that must return the integer type to sort by. By default it must be the identity function.

My tries look like (sorry, code looks very long and dirty, but it's just a try):

template<class ForwardIt>
void radix_sort(
    ForwardIt first,
    ForwardIt last,
    std::function<auto(typename std::iterator_traits<ForwardIt>::value_type)> get_value =
    [](const typename std::iterator_traits<ForwardIt>::value_type& x){ return x; }) {
        // ...
}

The returning type of get_value, of course, will be known in compilation time.

Usage should be:

std::vector<std::pair<uint32_t, std::string>> vec;
// ...
radix_sort(vec.begin(), vec.end(), [](const std::pair<uint32_t, std::string>& x){ return x.first; })

Or:

std::vector<uint32_t> vec;
// ...
radix_sort(vec.begin(), vec.end());

It doesn't even compile and I don't know how to solve the problem. How to do it? Simple example:

#include <bits/stdc++.h>

template<class ForwardIt>
void radix_sort(
    ForwardIt first,
    ForwardIt last,
    std::function<auto(typename std::iterator_traits<ForwardIt>::value_type)> get_value =
    [](const typename std::iterator_traits<ForwardIt>::value_type& x){ return x; }) {
        // ...
}

int main()
{
    std::vector<std::pair<uint32_t, std::string>> vec(10);
    radix_sort(vec.begin(), vec.end());
}

Compiler output:

source_file.cpp:17:37: error: no matching function for call to ‘radix_sort(std::vector<unsigned int>::iterator, std::vector<unsigned int>::iterator)’
     radix_sort(vec.begin(), vec.end());
                                      ^
source_file.cpp:6:6: note: candidate: template<class ForwardIt, class auto:1> void radix_sort(ForwardIt, ForwardIt, std::function<auto:1(typename std::iterator_traits<_Iter>::value_type)>)
 void radix_sort(
      ^
source_file.cpp:6:6: note:   template argument deduction/substitution failed:
source_file.cpp:17:37: note:   couldn't deduce template parameter ‘auto:1’
     radix_sort(vec.begin(), vec.end());

Answer 1

解决此问题的简单方法是不具有默认功能，而要具有两个重载。这样一来，您就不必使用std::function昂贵的了，而只需编写几行样板代码即可。如果您使用

template<class ForwardIt, class Func>
void radix_sort(ForwardIt first, ForwardIt last, Func get_value) {
    // ...
}

template<class ForwardIt>
void radix_sort(ForwardIt first, ForwardIt last) {
    radix_sort(first, last, [](const typename std::iterator_traits<ForwardIt>::value_type& x){ return x; });
}

，您将获得没有功能的默认“身份”，并且如果没有提供，则将获得确切的功能对象。

Answer 2

为了将来的用户受益，我想指出C ++ 20引入了class std::identity，它有助于解决问题。在其帮助下，代码可以重写为：

template <typename For, typename F = std::identity>
void radix_sort(For first, For end, F f = {})
{
  /* ... */
}

如果您没有C ++ 20，很容易自己实现符合标准的代码，例如：

struct identity {
  template <class T>
  constexpr T&& operator()(T&& t) const noexcept
  {
    return std::forward<T>(t);
  }

  using is_transparent = void;
};