7

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)?

molbdnilo
  • 64,751
  • 3
  • 43
  • 82
Jesper Juhl
  • 30,449
  • 3
  • 47
  • 70
  • 5
    It seems like std::reference_wrapper doesn't provide binary operator – Incomputable Apr 01 '16 at 12:22
  • on [reference page](http://en.cppreference.com/w/cpp/utility/functional/reference_wrapper) there is no operators for comparison, so I think you need to write your own. – Incomputable Apr 01 '16 at 12:24
  • 1
    How many elements is in the vector? Can't you just copy it? You basically do that anyway now with the `reference_wrapper` vector. – Some programmer dude Apr 01 '16 at 12:24
  • 1
    Why not just have a vector of iterators to the original vector? – NathanOliver Apr 01 '16 at 12:25
  • MSVC2013 gives a shorter error message telling me *Failed to specialize function template 'unknown-type std::less....* – marom Apr 01 '16 at 12:27
  • 3
    Use the three argument form of http://en.cppreference.com/w/cpp/algorithm/sort and write you own comparator (lambda use is possibly the easiest). – Niall Apr 01 '16 at 12:33
  • 1
    I think the problem is that the `operator<` on `duration` is a function template. (I can't explain the exact reason, so I'm not posting an answer.) @Niall's suggestion sounds like a decent workaround. – molbdnilo Apr 01 '16 at 12:35
  • @Joachim Pileborg it is potentially huge, so I would rather not copy it. – Jesper Juhl Apr 01 '16 at 12:52
  • 2
    While your solution using reference wrappers doesn't copy the actual contents of the unsorted vector, it still creates an equally large vector in a loop, saving neither execution time nor space. – Some programmer dude Apr 01 '16 at 12:54

2 Answers2

18

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>.

Jonathan Wakely
  • 166,810
  • 27
  • 341
  • 521
  • Thanks a lot. I guess the multiple pages of errors made me completely blind to that initial clear message. It works perfectly. – Jesper Juhl Apr 01 '16 at 12:46
  • 2
    Always start with the first error :-) With C++ templates the cascade of later errors might be side effects of that first one, and might go away when you solve the first one. – Jonathan Wakely Apr 01 '16 at 13:40
5

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(); } );
Brian Cain
  • 14,403
  • 3
  • 50
  • 88