Sign in to follow this  
NovaBlack

std::list::Sort() custom compare operator

Recommended Posts

Ok.. so ive implemented several custom functon to sort my list before (in cases when overloading the '<' operator for the list objects just cant cut it). However, i recently got a bit stuck! Im not sure if its just syntax or something.. or wether im trying to do the impossible. Basically i write my custom compare function n it works fine, but only seems to work fine if the function itself is written as a global function. Ive tried writing the compare function as a member function of the class that manages the list(so it can compare objects contained in a list of node pointers using some handy vectors of prebaked data the managing class itself stores). However i ALWAYS seem to get a compilation error. Is it just impossible to use a member function as a comparison function for a list sort? (i think it may be to do with the adress of the function in memory obviously depending on an object existing and staying in one place... but even if i make the member function static.. it still doesnt seem to work... :S) Any ideas on how to access that prebaked data if i cant use a member comparison function?.. all you can pass in are the two values to be compared.. and it would seem messy to just hackily give the objects i'm comparing pointers to the data. hmm thinking about it.. can i declare a NULL function pointer with the same signature and use that, and at runtime assign the member function with same sigature to that pointer, and tell sort to use that? lol seems messy again!

Share this post


Link to post
Share on other sites
You've almost got the right idea.

You have already realized that you to specify a comparison "functor" to std::list.

To make this easier the C++ standard library provides you with some pre-baked functors which are commonly used (#include <functional>). This includes the global functor std::less which lives in the global namespace and looks like this:


template<class Type>
struct less : public binary_function <Type, Type, bool>
{
bool operator()(const Type& _Left, const Type& _Right) const
{
return _Left < _Right;
}
};


If you look at the default template arguments for std::list, it specifies std::less as the default comparison functor.

All you have to do to make it work is define an operator<() to compare your types. By supplying a comparison operator, the line where I've added emphasis will call your comparison function.

You can make your comparison function a member function if you so wish, a free function will also work however.

Share this post


Link to post
Share on other sites
Ahh right i was so close!

I have a method i THINK will fix the problems now ill give it a try..

essentially the other additional problem i was having was that i needed to basically send in more data into the comparison functor than was accessible directly through the two objects i passed in. The managing class had additional data i wanted.

So in the end ill implement it exactly how youve said, but ill sneak inthe extra data, by having a list of std::pair< myOriginalNodeType, float sneakyInfo>
and comparing them.. then when i do the


'return _Left < _Right;'

bit, i can do


'return _Left->second < _Right->second;'

to compare the two objects using the custom heuristic data i wanted to sneak in!

cheers for the help. Ill let you know how it goes.

Share this post


Link to post
Share on other sites
You should always be able to write a function object that stores the extra data that you can "sneak in" through the constructor of that.

In addition, boost library has more powerful means of creating slightly more complex comparison functions, like in this entirely pointless example (use a third X object as this for the member function call:


#include <list>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>

struct X
{
int a, b;
bool compare(X x, X y) const { return x.a < a && y.a < b; }
};

int main()
{
using namespace boost::lambda;
std::list<X> li;
X x;
li.sort(bind(&X::compare, x, _1, _2));
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this