Sort list using STL sort function

Question

I'm trying to sort a list (part of a class) in descending order containing items of a struct, but it doesn't compile:

error: no match for 'operator-' in '__last - __first'

sort(Result.poly.begin(), Result.poly.end(), SortDescending());

And here's SortDescending:

struct SortDescending
{
    bool operator()(const term& t1, const term& t2)
    { 
        return t2.pow < t1.pow; 
    }
};

Can anyone tell me what's wrong?

Solution 1

The standard algorithm std::sort requires random access iterators, which std::list<>::iterators are not (list iterators are bidirectional iterators).

You should use the std::list<>::sort member function.

Solution 2

std::list has a built-in sort method that you need to use since std::sort only works with random access iterators, whereas std::list::iterator merely belongs to the bidirectional iterator class of iterators.

Result.poly.sort(SortDescending());

Also, your operator () should be marked const.

struct SortDescending
{
    bool operator()(const term& t1, const term& t2) const
    { 
        return t2.pow < t1.pow; 
    }
};

Finally, if the type term overloads an appropriate operator> you might not need to write your own comparer for sorting — simply use std::greater<T> (located in the standard header <functional>):

Result.poly.sort(std::greater<term>());

Solution 3

It seems like the iterator types for Result.poly is missing operator -. std::sort doesn't work with std::list change to Result.poly.sort

Comments

[Vlad]

@Glen see stackoverflow.com/questions/2425452/…

[Andreas Brinck]

No this isnt it, there's nothing in the standard that says that this needs to be const. If you look at the error message it seems like operator -` is missing for the input iterators.

[visitor]

It would make a better answer if it was reordered (const-ness is a side-issue here).

[Vlad]

still doesn't work either with my own comparer or using greater() it still gives a bunch of errors

[Vlad]

but i don't know how to overload correctly the less operator for my class

[Vlad]

but i don't know how to overload correctly the less operator for my class

[Konrad Rudolph]

@Andreas: my concern was that a temporary object gets passed into the sort function. I had forgotten that the comparer is passed by value and since temporaries cannot be bound to non-const references this would have required the function to be const.

[Konrad Rudolph]

@Vlad: what errors? This code should work. Did you include the header <functional> for std::greater?

[Glen]

@Vlad, you don't need to overload anything. Result.poly.sort(SortDescending()); should work just fine.

[Andreas Brinck]

@Vlad you can call this by Result.poly.sort(SortDescending()), no need for operator <.

[Andreas Brinck]

@Konrad I think he was talking about operator < and had missed the fact that there's a version of std::ist::sort that takes a predicate.

[Konrad Rudolph]

The operator () in your comparer should still be marked const as it doesn’t modify any members.

[UncleBens]

std::greater will only work if operator> is overloaded for term which probably isn't the case here.