Определите функцию в объявлении функции, используя 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; });
}

вы получаете «идентичность» по умолчанию без функции, и вы получаете точный объект функции в противном случае, если он указан.

Answer 2

Для будущих пользователей, Я хотел бы отметить, что 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;
};