Why can't I sort a vector of reference_wrapper<std::chrono::milliseconds>?

Question

I want a sorted view of a std::vector<std::chrono::milliseconds> but I don't want to modify the original container. std::reference_wrapper seems perfect for this and it works just fine for a vector of integers.

I've created this small example:

#include <chrono>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>

int main()
{
    std::vector<int> numbers{1, 42, 3, 9, 5};
    std::vector<std::reference_wrapper<int>> sorted_numbers(numbers.begin(), numbers.end());
    std::sort(sorted_numbers.begin(), sorted_numbers.end());

    std::cout << "Numbers: ";
    for (const auto& n : numbers)
        std::cout << n << ' ';
    std::cout << '\n';

    std::cout << "Sorted numbers: ";
    for (const auto& n : sorted_numbers)
        std::cout << n << ' ';
    std::cout << '\n';

    std::cout << "Numbers: ";
    for (const auto& n : numbers)
        std::cout << n << ' ';
    std::cout << '\n';

    std::vector<std::chrono::milliseconds> durations{std::chrono::milliseconds{1},
                                                     std::chrono::milliseconds{42},
                                                     std::chrono::milliseconds{3},
                                                     std::chrono::milliseconds{9},
                                                     std::chrono::milliseconds{5}};
    std::vector<std::reference_wrapper<std::chrono::milliseconds>>
        sorted_durations(durations.begin(), durations.end());
    // std::sort(sorted_durations.begin(), sorted_durations.end());

    std::cout << "Durations: ";
    for (const auto& d : durations)
        std::cout << d.count() << ' ';
    std::cout << '\n';

    std::cout << "Sorted durations: ";
    for (const auto& d : sorted_durations)
        std::cout << d.get().count() << ' ';
    std::cout << '\n';

    std::cout << "Durations: ";
    for (const auto& d : durations)
        std::cout << d.count() << ' ';
    std::cout << '\n';
}

Which produces the expected output (except that sorted_durations isn't sorted of course since that is commented out):

Numbers: 1 42 3 9 5 
Sorted numbers: 1 3 5 9 42 
Numbers: 1 42 3 9 5 
Durations: 1 42 3 9 5 
Sorted durations: 1 42 3 9 5 
Durations: 1 42 3 9 5 

As you can see, the original vector of integers numbers is unchanged by the sort operation done on sorted_numbers - that's exactly what I want for the sorted_durations vector as well. But when I uncomment that line my compiler gets very cross with me and I must admit that I can't figure out what it is trying to tell me. My compiler is clang++ version 3.8 and I build the example program like so:

clang++ -std=c++11 test.cc

And here's the error output I get:

In file included from test.cc:4:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/algorithm:62:
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:1935:11: error: invalid operands to binary expression
      ('std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >' and 'std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >')
        if (*__i < *__first)
            ~~~~ ^ ~~~~~~~~
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:5308:12: note: in instantiation of function template specialization
      'std::__heap_select<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >
      >' requested here
      std::__heap_select(__first, __middle, __last);
           ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:2310:24: note: in instantiation of function template specialization
      'std::partial_sort<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >
      >' requested here
              _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
                              ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:5460:9: note: in instantiation of function template specialization
      'std::__introsort_loop<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >,
      long>' requested here
          std::__introsort_loop(__first, __last,
               ^
test.cc:35:10: note: in instantiation of function template specialization 'std::sort<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >
      *, std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > >
      > >' requested here
    std::sort(sorted_durations.begin(), sorted_durations.end());
         ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/chrono:488:7: note: candidate template ignored: could not match 'duration' against 'reference_wrapper'
      operator<(const duration<_Rep1, _Period1>& __lhs,
      ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/chrono:667:7: note: candidate template ignored: could not match 'time_point' against 'reference_wrapper'
      operator<(const time_point<_Clock, _Dur1>& __lhs,
      ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_pair.h:220:5: note: candidate template ignored: could not match 'pair' against 'reference_wrapper'
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:297:5: note: candidate template ignored: could not match 'reverse_iterator' against
      'reference_wrapper'
    operator<(const reverse_iterator<_Iterator>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:347:5: note: candidate template ignored: could not match 'reverse_iterator' against
      'reference_wrapper'
    operator<(const reverse_iterator<_IteratorL>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:1055:5: note: candidate template ignored: could not match 'move_iterator' against 'reference_wrapper'
    operator<(const move_iterator<_IteratorL>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:1061:5: note: candidate template ignored: could not match 'move_iterator' against 'reference_wrapper'
    operator<(const move_iterator<_Iterator>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_vector.h:1421:5: note: candidate template ignored: could not match 'vector' against 'reference_wrapper'
    operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2569:5: note: candidate template ignored: could not match 'basic_string' against 'reference_wrapper'
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2581:5: note: candidate template ignored: could not match 'basic_string' against 'reference_wrapper'
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2593:5: note: candidate template ignored: could not match 'const _CharT *' against
      'std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >'
    operator<(const _CharT* __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/array:238:5: note: candidate template ignored: could not match 'array' against 'reference_wrapper'
    operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/tuple:824:5: note: candidate template ignored: could not match 'tuple' against 'reference_wrapper'
    operator<(const tuple<_TElements...>& __t,
    ^
In file included from test.cc:4:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/algorithm:62:
In file included from /usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:61:
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_heap.h:235:35: error: invalid operands to binary expression ('std::reference_wrapper<std::chrono::duration<long,
      std::ratio<1, 1000> > >' and 'std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >')
          if (*(__first + __secondChild) < *(__first + (__secondChild - 1)))
              ~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_heap.h:407:9: note: in instantiation of function template specialization
      'std::__adjust_heap<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >,
      long, std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > >' requested here
          std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value));
               ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:1933:12: note: in instantiation of function template specialization
      'std::make_heap<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >
      >' requested here
      std::make_heap(__first, __middle);
           ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:5308:12: note: in instantiation of function template specialization
      'std::__heap_select<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >
      >' requested here
      std::__heap_select(__first, __middle, __last);
           ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:2310:24: note: in instantiation of function template specialization
      'std::partial_sort<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >
      >' requested here
              _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
                              ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_algo.h:5460:9: note: in instantiation of function template specialization
      'std::__introsort_loop<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > *,
      std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > > >,
      long>' requested here
          std::__introsort_loop(__first, __last,
               ^
test.cc:35:10: note: in instantiation of function template specialization 'std::sort<__gnu_cxx::__normal_iterator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >
      *, std::vector<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >, std::allocator<std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > > > >
      > >' requested here
    std::sort(sorted_durations.begin(), sorted_durations.end());
         ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/chrono:488:7: note: candidate template ignored: could not match 'duration' against 'reference_wrapper'
      operator<(const duration<_Rep1, _Period1>& __lhs,
      ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/chrono:667:7: note: candidate template ignored: could not match 'time_point' against 'reference_wrapper'
      operator<(const time_point<_Clock, _Dur1>& __lhs,
      ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_pair.h:220:5: note: candidate template ignored: could not match 'pair' against 'reference_wrapper'
    operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:297:5: note: candidate template ignored: could not match 'reverse_iterator' against
      'reference_wrapper'
    operator<(const reverse_iterator<_Iterator>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:347:5: note: candidate template ignored: could not match 'reverse_iterator' against
      'reference_wrapper'
    operator<(const reverse_iterator<_IteratorL>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:1055:5: note: candidate template ignored: could not match 'move_iterator' against 'reference_wrapper'
    operator<(const move_iterator<_IteratorL>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_iterator.h:1061:5: note: candidate template ignored: could not match 'move_iterator' against 'reference_wrapper'
    operator<(const move_iterator<_Iterator>& __x,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/stl_vector.h:1421:5: note: candidate template ignored: could not match 'vector' against 'reference_wrapper'
    operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2569:5: note: candidate template ignored: could not match 'basic_string' against 'reference_wrapper'
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2581:5: note: candidate template ignored: could not match 'basic_string' against 'reference_wrapper'
    operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/bits/basic_string.h:2593:5: note: candidate template ignored: could not match 'const _CharT *' against
      'std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >'
    operator<(const _CharT* __lhs,
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/array:238:5: note: candidate template ignored: could not match 'array' against 'reference_wrapper'
    operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b)
    ^
/usr/lib/gcc/x86_64-redhat-linux/4.8.5/../../../../include/c++/4.8.5/tuple:824:5: note: candidate template ignored: could not match 'tuple' against 'reference_wrapper'
    operator<(const tuple<_TElements...>& __t,
    ^

It actually goes on for a bit longer, but stackoverflow won't let me post all 55000 characters of the error.

Can anyone please explain to me what I'm doing wrong or why this is simply not possible (if that's the case)?

Answer 1

The first error seems pretty clear:

In file included from [...]/algorithm:62:
[...]/bits/stl_algo.h:1935:11: error: invalid operands to binary expression
      ('std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >' and 'std::reference_wrapper<std::chrono::duration<long, std::ratio<1, 1000> > >')
        if (*__i < *__first)
            ~~~~ ^ ~~~~~~~~

You can't use < to compare two reference_wrapper<duration<...>> objects.

The conversion to duration<...> doesn't happen because (as a comment above says) the operator< for duration is a function template and its arguments cannot be deduced from reference_wrapper<duration<...>>.

If you passed an instance of std::less<std::chrono::milliseconds> to std::sort then that would cause the wrappers to be converted to the duration types, and compared correctly.

 std::sort(sorted_durations.begin(), sorted_durations.end(), std::less<std::chrono::milliseconds>{});

This basically says you want to sort the objects by comparing them as milliseconds not reference_wrapper<milliseconds>.

Answer 2

Per @Niall's suggestion, you can use a lambda as comparator for the sort():

std::sort(sorted_durations.begin(), sorted_durations.end(), 
    [](const std::reference_wrapper<std::chrono::milliseconds> &a, 
       const std::reference_wrapper<std::chrono::milliseconds> &b) 
       -> bool { return a.get() < b.get(); } );