今天我试图实现radix排序。该函数必须具有两个变量:开始迭代器和结束迭代器,并且可以具有第三个:某些函数必须返回整数类型进行排序。默认情况下,它必须是身份函数。
我的尝试看起来像(对不起,代码看起来很长又脏,但这只是一个尝试(:
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());
解决此操作的简单方法是没有默认功能,而是有两个过载。这使您可以摆脱使用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; });
}
您获得没有函数的默认"身份",如果提供了一个,则可以获得确切的功能对象。
为了未来用户的利益,我想指出的是,C 20引入了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;
};