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

What does the compiler say? --> Just add the compiler errors/warnings/outputs to your post, if not for something else, then just for completeness sake. — Duck Dodgers, May 13 '19 at 12:42
I think in template only works if you have C++17 and the question is tagged C++11. See [this answer](https://stackoverflow.com/questions/38026884/advantages-of-auto-in-template-parameters-in-c17). There could other problems too I haven't took the time to carefully analyse the question but I would start by which standard is available. — Clonk, May 13 '19 at 12:49
I could be wrong about this, but [shouldn't templates be only implemented in the header file](https://stackoverflow.com/questions/495021/why-can-templates-only-be-implemented-in-the-header-file)? — Duck Dodgers, May 13 '19 at 12:51
Edits have reintroduced `radix_sort` vs `uint_sort` confusion — AndyG, May 13 '19 at 12:52
`std::vector> vec(10, -1);`? `-1` cannot be used to instantiate a `std::string` — AndyG, May 13 '19 at 12:55
@JoeyMallone there is no problem implementing a template in the same .cpp file where you use it. You only need to implement them in a header when you want to use the template in multiple different .cpp files which are including the header. There is no inherent reason a template can't be in a .cpp file. — Jonathan Wakely, May 13 '19 at 13:25
@JonathanWakely, `:O` I didn't know that. ... Thank you. `:)` — Duck Dodgers, May 14 '19 at 11:18

NathanOliver · Accepted Answer · 2019-05-13T13:09:38.170

8

The easy way to fix this is to not have a default function and instead have two overloads. This lets you get rid of using a std::function, which is expensive, at the cost of writing a couple lines of boiler plate code. If you use

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

the you get the default "identity" with no function, and you get the exact function object otherwise if one is provided.

edited May 13 '19 at 13:09

answered May 13 '19 at 12:52

NathanOliver

171,901
28
288
402

Does this mean that I can not give a default value, as I would like? – Alexander Stanovoy May 13 '19 at 12:55
1

That's what the second overload does for you. If you don't specify a third parameter, you get the second overload, and _that_ defines the default. – Useless May 13 '19 at 12:56
1

@AlexanderStanovoy The default is provided with the second overload. If you only call it with 2 iterators, you'll get the second function which uses your default identity function. If the user provides their own function object, then it will call the first one and use their provided one. – NathanOliver May 13 '19 at 12:57
2

Note that the lambda is going to return by value, which may not be desirable – AndyG May 13 '19 at 12:58
2

If that is a problem the lambda can be changed to `[](const typename std::iterator_traits::value_type& x) -> decltype(auto) { return (x); })` – NathanOliver May 13 '19 at 13:00

score 6 · Answer 2 · answered May 13 '19 at 13:23

For the benefit of future users, I would like to point out that C++20 introduces the class std::identity, which aids in solving the problem. With its help, the code can be rewritten as:

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

And it is very easy to implement a standard-conforming one yourself if you don't have C++20, like this:

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

  using is_transparent = void;
};

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

2 Answers2