Jump to content
  • Advertisement

Archived

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

AndreTheGiant

STL - sorting elements of a vector.

This topic is 5219 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Suppose I have a class Thingy like this (simplified):
class Thingy {
  public:
    Thingy(int id, list<int> scores);
    void print();
  private:
    int id;
    list<int> scores;
};
.. and I have a vector of Thingys. Now suppose I want to sort my vector of Thingys in order of increasing score values. So for eg if I have these scores: Thingy1: 3 5 6 6 Thingy2: 1 4 8 13 Thingy3: 2 3 4 5 then the sorted vector will contain the Thingys in this order: Thingy2, Thingy3, Thingy 1 Note that the scores within each Thingy are already sorted in increasing order. Im more interested in the syntax for whatever STL-compatible sorting mechanism I need to use, than I am interested in the exact sorting algorithm. For example, I vaguely recall some kind of function that returns true if one Thingy is <= another Thingy. Or is it a new class I need to make? Or a member function? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Either overload operator< (or operator> for that matter) or provide a comparison function to pass to std::sort. By default std::sort uses operator<, so just overloading it is probably the simplest way to go.

Share this post


Link to post
Share on other sites
You can use a feature that algorithm's sort() function supports that allows you to specify your own binary function as a search criteria. For example:


bool helper(const thingy &a, const thingy &b)
{
return a.scores[0]<b.scores[0];
//Or however you want to sort

}

...

int main()
{
vector<thingy> stuff;
...
sort(stuff.begin(), stuff.end(), helper);
...
return 1;
}


The binary helper function must be outside of any class definition, and the syntax required is just as above, no parameters when used in the sort function.

[edited by - eleusive on May 7, 2004 6:09:13 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by ze_jackal
Either overload operator< (or operator> for that matter) or provide a comparison function to pass to std::sort. By default std::sort uses operator<, so just overloading it is probably the simplest way to go.


I''m pretty sure it has to be operator<. The library code will be written using that, and because user-defined operator overloads don''t have to obey the mathematical rules, the compiler can''t turn your comparison around.

Anyway, this version looks like:

bool Thingy::operator<(const Thingy &rhs) {
// I assume you want to sort by first score, then second, etc.

int max = this.size();
int tmp = rhs.size();
if (tmp < max) max = tmp;
for(int i = 0; i < max;i++) {
if (this.scores[i] < rhs.scores[i]) return true;
}
return (max < tmp); // reached the end of either vector

// so the "lesser" one is whichever is shorter

}

vector<thingy> stuff;
...
sort(stuff.begin(), stuff.end()); // 2-arg version invokes the class''s operator< for comparisons.



Share this post


Link to post
Share on other sites
Thanks guys. I guess thats 2 of the 3 different ways that I was thinking of. Isnt there another way where you make a whole new class whose sole purpose is to provide a sort function?

Anyway, thanks.

Share this post


Link to post
Share on other sites
quote:
Original post by Zahlman
I''m pretty sure it has to be operator<. The library code will be written using that, and because user-defined operator overloads don''t have to obey the mathematical rules, the compiler can''t turn your comparison around.


Only if you''re using a braindead STL implementation/compiler.

Here''s how you use a function object class:

struct ThingyComparer {
bool operator()(const Thingy & lhs, const Thingy & rhs) {
return std::lexicographical_compare(lhs.scores.begin(), lhs.scores.end(),
rhs.scores.begin(), rhs.scores.end());
}
};

int main(int, char **) {
std::vector<Thingy> thingies;
// fill the thingies

std::sort(thingies.begin(), thingies.end(), ThingyComparer());

return 0;
}

Obviously, you need to make ThingyComparer a friend of Thingy.

Share this post


Link to post
Share on other sites
quote:
Original post by SiCrane
quote:
Original post by Zahlman
I''m pretty sure it has to be operator<. The library code will be written using that, and because user-defined operator overloads don''t have to obey the mathematical rules, the compiler can''t turn your comparison around.


Only if you''re using a braindead STL implementation/compiler.


I think Zahlman was referring to ze_jackal''s implication that you could overload either < or >.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
Ah, I thought he was saying that you couldn''t create a function object to pass to std::sort(). My mistake.

Share this post


Link to post
Share on other sites
Ok my original question is solved, so thanks all. But now I have a more important question:

Ive seen 3 ways to do this.

1. overloading operator > (or < or whatever)
2. use a helper function
3. use a helper class (or structure)

What are the real differences between these 3 methods? When should I use which?

Share this post


Link to post
Share on other sites
Overloading < - Useful if you can do it (you can''t do it for built-in types) and there''s one natural ordering for objects of that type. For instance, bank accounts might be sorted by names or by account numbers, so it''s up to you to decide whether one of those is "natural" (I''d choose the account number).

Helper function - this is the C way. It works fairly well, but is not as likely to be inlined, and isn''t as flexible as function objects.

Function object - Like helper functions, but easily allows inlining, makes it easy to create "stateful" functions, and allows you to pass arguments to the function object during creation (tho this isn''t quite as useful a feature with something like sort).


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!