c++ - 使用 std::iterator traits 和 auto 在函数声明中定义一个函数

Question

今天我尝试实现基数排序。该函数必须有两个变量:开始迭代器和结束迭代器，并且可以有第三个:一些必须返回整数类型以进行排序的函数。默认情况下，它必须是恒等函数。

我的尝试看起来像(抱歉，代码看起来又长又脏，但这只是一个尝试):

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; }) {
        // ...
}

get_value 的返回类型当然会在编译时知道。

用法应该是:

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; })

或者:

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

它甚至不编译，我不知道如何解决这个问题。怎么做？简单示例:

#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());
}

编译器输出:

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; });
}

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