C++ templates, default argument as a method

Question

For this implementation of selection sort:

template <typename Iterator, typename Compare>
void sort(Iterator begin, Iterator end, Compare comp) {
    for (auto i = begin; i != end; ++i) {
        auto min = i;
        for (auto j = i + 1; j != end; ++j) {
            if (comp(*j, *min)) {
                min = j;
            }
        }
        std::swap(*min, *i);
    }
}

How should I modify it so that Compare comp should be std::less method if last parameter is skipped for sort method?

I tried function overloading by introducing another method:

template <typename Iterator>
void sort(Iterator begin, Iterator end) {
    sort(begin, end, std::less<std::iterator_traits<Iterator>::value_type>());
}

But it gave errors like:

In file included from ../src/selection_sort_demo.cpp:1:
../include/selection_sort.hpp:24:29: error: template argument for template type parameter must be a type; did you forget 'typename'?
        sort(begin, end, std::less<std::iterator_traits<Iterator>::value_type>());
                                   ^
                                   typename 
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/6.3.1/../../../../include/c++/6.3.1/bits/stl_function.h:380:21: note: template parameter is declared here
  template<typename _Tp>
                    ^
In file included from ../src/selection_sort_demo.cpp:1:
../include/selection_sort.hpp:24:2: error: call to 'sort' is ambiguous
        sort(begin, end, std::less<std::iterator_traits<Iterator>::value_type>());
        ^~~~
../src/selection_sort_demo.cpp:22:13: note: in instantiation of function template specialization 'selection::sort<__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > >' requested here
        selection::sort(v.begin(), v.end());
                   ^
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/6.3.1/../../../../include/c++/6.3.1/bits/stl_algo.h:4727:5: note: candidate function [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >, _Compare = std::less<int>]
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
    ^
../include/selection_sort.hpp:7:6: note: candidate function [with Iterator = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >, Compare = std::less<int>]
void sort(Iterator begin, Iterator end, Compare comp)
     ^
2 errors generated.
[2/4] Compiling cpp object 'test/testexe@exe/selection_sort_test.cpp.o'
FAILED: test/testexe@exe/selection_sort_test.cpp.o 
clang++  '-Itest/testexe@exe' '-Itest' '-I../test' '-I../include' '-Wall' '-Winvalid-pch' '-Wnon-virtual-dtor' '-std=c++14' '-O0' '-g' '-pthread' '-MMD' '-MQ' 'test/testexe@exe/selection_sort_test.cpp.o' '-MF' 'test/testexe@exe/selection_sort_test.cpp.o.d' -o 'test/testexe@exe/selection_sort_test.cpp.o' -c ../test/selection_sort_test.cpp
In file included from ../test/selection_sort_test.cpp:2:
../include/selection_sort.hpp:24:29: error: template argument for template type parameter must be a type; did you forget 'typename'?
        sort(begin, end, std::less<std::iterator_traits<Iterator>::value_type>());
                                   ^
                                   typename 
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/6.3.1/../../../../include/c++/6.3.1/bits/stl_function.h:380:21: note: template parameter is declared here
  template<typename _Tp>
                    ^
In file included from ../test/selection_sort_test.cpp:2:
../include/selection_sort.hpp:24:2: error: call to 'sort' is ambiguous
        sort(begin, end, std::less<std::iterator_traits<Iterator>::value_type>());
        ^~~~
../test/selection_sort_test.cpp:17:13: note: in instantiation of function template specialization 'selection::sort<__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > >' requested here
        selection::sort(v1.begin(), v1.end());
                   ^
/usr/bin/../lib64/gcc/x86_64-pc-linux-gnu/6.3.1/../../../../include/c++/6.3.1/bits/stl_algo.h:4727:5: note: candidate function [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >, _Compare = std::less<int>]
    sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
    ^
../include/selection_sort.hpp:7:6: note: candidate function [with Iterator = __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >, Compare = std::less<int>]
void sort(Iterator begin, Iterator end, Compare comp)
     ^
2 errors generated.

`typename Iterator` instead of `Iterator` ? – malat Feb 03 '17 at 14:28 — malat, Feb 03 '17 at 14:28
[Related Q](http://stackoverflow.com/q/610245/1782465) – Angew is no longer proud of SO Feb 03 '17 at 14:36 — Angew is no longer proud of SO, Feb 03 '17 at 14:36

Richard Hodges · Accepted Answer · 2017-02-03T20:29:01.940

14

Since it's c++14:

template <typename Iterator, typename Compare = std::less<> >
void sort(Iterator begin, Iterator end, Compare comp = Compare())
{
    for (auto i = begin; i != end; ++i) {
        auto min = i;
        for (auto j = i + 1; j != end; ++j) {
            if (comp(*j, *min)) {
                min = j;
            }
        }
        std::swap(*min, *i);
    }
}

c++11:

template <typename Iterator, typename Compare = std::less< typename std::iterator_traits<Iterator>::value_type > >
void sort(Iterator begin, Iterator end, Compare comp = Compare())
{
    for (auto i = begin; i != end; ++i) {
        auto min = i;
        for (auto j = i + 1; j != end; ++j) {
            if (comp(*j, *min)) {
                min = j;
            }
        }
        std::swap(*min, *i);
    }
}

Explanation:

We have to offer the compiler both a default type in the template argument list and a default function argument list.

For explanation of std::less<> since c++14 see:

http://en.cppreference.com/w/cpp/utility/functional/less

edited Feb 03 '17 at 20:29

answered Feb 03 '17 at 14:28

Richard Hodges

68,278
7
90
142

Hey, spaces are not needed after less<>. – Peter K Feb 03 '17 at 14:30
2

@PeterK you and the compiler might not need them, but I do! :-) – Richard Hodges Feb 03 '17 at 14:32
4

If you go through `iterator_traits` instead of using `Iterator::`, the code will work with all iterators (including pointers). – Angew is no longer proud of SO Feb 03 '17 at 14:36
2

@Angew Awesome suggestion. I deleted my answer since using that with this answer would be much better. – NathanOliver Feb 03 '17 at 14:37
@RichardHodges great answer. One small question though, why do I've to write this part - `Compare comp = Compare()` instead of just `Compare comp` like other args are written. Is it always done with default template args? – Abhinav Gauniyal Feb 03 '17 at 15:24
@AbhinavGauniyal if you don't add the `= Compare()` you're not providing a default function argument, so you'd have to supply it at the call site. – Richard Hodges Feb 03 '17 at 20:27
@RichardHodges I thought it was done with `typename Compare = std::less<>`, nvm I'll read about it. – Abhinav Gauniyal Feb 04 '17 at 05:58
1

@AbhinavGauniyal `typename Compare = std::less<>` provides a default *template argument* for the *template parameter.* `Compare comp = Compare()` provides a default *function argument* for the *function parameter.* Without the latter, you'd still have to provide a function argument when calling the function, but (thanks to the default template argument), its type would default to `std::less<>` if it wasn't deducible (such as if you used `{}`). – Angew is no longer proud of SO Feb 06 '17 at 09:26

score 5 · Answer 2 · edited Feb 03 '17 at 15:12

5

You were right, but forgot the typename keyword. Check this:

template <typename Iterator>
void sort(Iterator begin, Iterator end) {
    sort(begin, end, std::less<typename std::iterator_traits<Iterator>::value_type>());
}

Probably you wanted default template argument, but this works too.

edited Feb 03 '17 at 15:12

Omnifarious

54,333
19
131
194

answered Feb 03 '17 at 14:34

Peter K

1,787
13
15

4

How is it ambiguous? The arity is different. – Peter K Feb 03 '17 at 14:38
sorry it's just my MSVC picking up `std::sort` through ADL – Nazar554 Feb 03 '17 at 14:41
@Nazar554 I do have my own namespace in my code, excluded here for simplicity. – Abhinav Gauniyal Feb 03 '17 at 15:07

C++ templates, default argument as a method

2 Answers2