Archived

This topic is now archived and is closed to further replies.

WoX

stl question

Recommended Posts

I was wondering how to sort a list of structs after a specific membervariable. Here''s some nice pseudocode #include <list> struct Node { int x, y; int f, g, h; Node *Parent; }; std::list NodeList; for(int i=0; i<10; i++) { Node node = {i,i,rand()%100,0,0,0}; NodeList.push_back(node); } there, now I wan''t to sort the list after the f membervariable in ascending order, if the list would have contained int''s instead of Node''s this would have worked: NodeList.sort(); or for descending order: std::greater great; NodeList.sort(great); Anyone here''s a guru on stl and can share som knowledge?? thanks for any help

Share this post


Link to post
Share on other sites
Stl''s sort uses the operator < to sort the values. You can either change to a class and overload it as a member function or overload it like this

  
bool operator<(const Node & n1, const Node & n2)
{
return (n1.f<n2.f);
}

Share this post


Link to post
Share on other sites
You need to either overload comparison operators for your new types or define an appropriate binary predicate that you then pass to sort.

Like

bool
OrderByH( const Node& lhs, const Node& rhs )
{
return lhs.h < rhs.h;
}

...

sort( List.begin(), List.end(), OrderByH );

Share this post


Link to post
Share on other sites
quote:
Original post by hewhay
Stl''s sort uses the operator < to sort the values. You can either change to a class and overload it as a member function or overload it like this



No, that''s the _default_ behaviour. It may be indesirable to define a ''global'' ordering criterion for a given type (e.g. complex numbers), while still being able to sort them in some cases (by real part or imaginary part).

Share this post


Link to post
Share on other sites
You''re right, you must use list''s sort() member function.
But the parameter isn''t necessarily a function object, it can be a binary predicate (i.e. a function taking 2 parameters and returning a bool).

Share this post


Link to post
Share on other sites
PSA (Public Service Announcement):
std::list is the worst container you can sort. That''s why it has its own sort member function (rather than std::sort, which can be used on vectors and dequeus; maps and sets are always sorted, of course). If you''re sorting once, it''s probably OK. If you''re sorting a lot, you might want to look into a different container.

Share this post


Link to post
Share on other sites