#### Archived

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

# STL - sorting elements of a vector.

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

## 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 on other sites
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 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 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 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 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 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 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 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.

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 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

1. 1
Rutin
33
2. 2
3. 3
4. 4
5. 5

• 13
• 9
• 9
• 9
• 9
• ### Forum Statistics

• Total Topics
633330
• Total Posts
3011388
• ### Who's Online (See full list)

There are no registered users currently online

×