How to sort std: list when you need member data?

Question

So, I would know how to sort it if I could use a vector, but we have to implement it using a list. Our professor said that we can use the sort function already implemented in the list class. If it were a vector, I could create a structure, and then use the sort from <algorithm> to go, although my list, but it will not allow me to use this, since std :: list does not have random access. The API says "template <class Compare>", but I don’t think it will help me.

I understand that I can use the sort function, but I need to use the item data to sort it. I sort the points by their polar angle, and I need to use the current Point, which is a member of my class as “origin”, so I cannot use the static comparison sorter, as usual.

EDIT I ​​use this as my sorting call: sortedList.sort(sorting);

and here is my function:

 bool sorting(const Point& p, const Point& q) { Point z = pointStack.top(); Point u = Point(p.getX() - z.getX(), p.getY() - z.getY()); Point v = Point(q.getX() - z.getX(), q.getY() - z.getY()); double r = u.polarAngle(); double s = v.polarAngle(); if (r < s) { return true; } else { return false; } } 

I keep getting

c: \ users \ wooly \ documents \ visual studio 2010 \ projects \ proj5 \ proj5 \ grahamscan.cpp (20): error C3867: 'GrahamScan :: sorting': list of calls to missing arguments; use '& GrahamScan :: sorting' to create a pointer to a member

since I need a top pointStack value to sort, but it is a member of my class.

Answer 1

You can simply call the sort function directly if your value type has an operator <defined.

 std::list<int> myList; // Do stuff to the list myList.sort(); 

Or, if it is not, you need to provide a functor that will perform the comparison.

 struct MyClassComparator { bool operator()(const MyClass& first, const MyClass& second) const { // Return true if first should go before second return true; } }; std::list<MyClass> myList; // Do stuff to the list myList.sort(MyClassComparator()); 

Answer 2

You can simply call the member function of sort if the types you are already saving can be compared to < :

 list<int> l; l.push_back(3); l.push_back(2); l.push_back(1); l.sort(); print_list(l); 

And if print_list printed the list, it will print 1 2 3 .

You only need to pass the sort argument if the type you are storing in the list does not have operator< . You can do it like this:

 class Compare_MyClass { public: bool operator()(const MyClass& lhs, const MyClass& rhs) { return lhs.member < rhs.member; // or some comparison } }; list<MyClass> l; l.push_back(MyClass(...)); l.push_back(MyClass(...)); l.push_back(MyClass(...)); l.sort(Compare_MyClass());