sorting a vector of std::pair > depending on pair.first

Question

I'm trying to sort a vector of pairs containing a smart pointers of a const object. I'm trying to sort only depending on the first object. Below you see (one of my numerous attempts to write) code that is supposed to do this, alongside with an excerpt from the error.

The compiler complains about the lambda parameters. I've tried to make the parameters const, non-const, references, rvalue-references, to no avail. Help please?

std::pair<int, std::unique_ptr<const std::string> > a;
auto uniq = std::make_unique<const std::string>("hurz");
a = std::make_pair(1,std::move(uniq));

std::pair<int, std::unique_ptr<const std::string> > b;
uniq = std::make_unique<const std::string>("hurz");
b = std::make_pair(2,std::move(uniq));

std::vector<std::pair<int,std::unique_ptr<const std::string> > > vec;

vec.push_back(std::move(a));
vec.push_back(std::move(b));

std::sort(std::make_move_iterator(vec.begin()),
    std::make_move_iterator(vec.end()),
    []
    (const std::pair<int,std::unique_ptr<const std::string> >& i1,
     const std::pair<int,std::unique_ptr<const std::string> >& i2)
    { return i1.first > i2.first;});

The error message didn't help me:

error: no matching function for call to 
'swap(std::move_iterator<__gnu_cxx::__normal_iterator<std::pair<int, 
std::unique_ptr<const std::basic_string<char> > >*, std::vector<std::pair<int, 
std::unique_ptr<const std::basic_string<char> > > > > >::value_type, 
std::move_iterator<__gnu_cxx::__normal_iterator<std::pair<int, 
std::unique_ptr<const std::basic_string<char> > >*, std::vector<std::pair<int, 
std::unique_ptr<const std::basic_string<char> > > > > >::value_type)' swap(*__a, 
*__b);
candidates are:
 /usr/include/c++/4.9/bits/move.h:166:5: note: void std::swap(_Tp&, _Tp&) 
[with _Tp = std::pair<int, std::unique_ptr<const std::basic_string<char> > >]

plus many more errors in the same vein

Why do you need a `std::unique_ptr` instead of simply `std::string` at all? — πάντα ῥεῖ, Jul 24 '18 at 17:20
the string is just an example. I have objects that i pass around and would like garbage collected once it goes out of scope. — the_toast, Jul 24 '18 at 17:22
_"I have objects that i pass around ..."_ That's an indicator you need a `std::shared_ptr` instead of `std::unique_ptr`. Check out their concepts of ownership. — πάντα ῥεῖ, Jul 24 '18 at 17:24
i never hold the object in two places at once and the performance hit of shared_ptr is too large in my application. — the_toast, Jul 24 '18 at 17:28
@NathanOliver [Same result here](http://coliru.stacked-crooked.com/a/334fc65d1c075402) — πάντα ῥεῖ, Jul 24 '18 at 17:38
Why would you ever want to pass a `move_iterator` to `std::sort`? — super, Jul 24 '18 at 17:38

score 8 · Accepted Answer · answered Jul 24 '18 at 17:43

The issue here is the use of std::make_move_iterator. When you do so you turn the iterators into move_iterator's which means when you dereference them you get a T&&, instead of a T& like you do with normal iterators.

std::swap, which is used in your implementation of std::sort only takes lvalue references so it cannot bind to the dereferenced iterator. If you use

std::sort(vec.begin(),
    vec.end(),
    []
    (const std::pair<int,std::unique_ptr<const std::string> >& i1,
     const std::pair<int,std::unique_ptr<const std::string> >& i2)
    { return i1.first > i2.first;});

instead then you will have lvalues for std::swap to bind to and std::swap will work for move only types

thanks for both solution and for the explanation why it couldn't work with move_iterator! — the_toast, Jul 24 '18 at 17:50

score 1 · Answer 2 · answered Jul 24 '18 at 21:08

I add some further explanation to the answer of @NathanOliver which is too long for a comment. I guess the OP's idea of using

std::sort(std::make_move_iterator(vec.begin()), std::make_move_iterator(vec.end()),
    [](const std::pair<int,std::unique_ptr<const std::string> >& i1,
       const std::pair<int,std::unique_ptr<const std::string> >& i2)
       { return i1.first > i2.first;});

i.e., with a move_iterator applied to vector.begin(), is to use move assignments (and not copies) inside the sorting routine. This idea is tempting, but it's not necessary because inside std::sort, assignments are usually done with std::swap which tries to move arguments passed by reference.

On the other hand, for algorithms which use input and output iterators, such as most basically std::copy or std::copy_if, the use of std::make_move_iterator can be quite useful. Those often use constructs like *output_it = *input_it, and together with std::make_move_iterator this corresponds to *output_it = std::move(*input_it), so the move-assignment operator of the type dereferenced by *output_it could be used.

sorting a vector of std::pair > depending on pair.first

2 Answers2