C++ : sorting a vector

William Labbett

hi,

I've got a vector of class pointers I need to sort according to the value of a member of the class.

I thought of using C stdlib.h qsort but I'm not sure it's meant to be used on members of a C++ vector.

What should I do ?

Arthur Kalliokoski

http://www.cplusplus.com/reference/algorithm/sort/ ?

ImLeftFooted

I prefer this method:

#SelectExpand
  1class YourWhateverClass {
  2...
  3};
  4
  5class YourWhateverPointer {
  6public:
  7  YourWhateverClass *ptr;
  8  YourWhateverPointer(YourWhateverClass *ptr) : ptr(ptr) {}
  9
 10  bool operator <(YourWhateverPointer &right) {
 11    return ptr->someValue < right.ptr->someValue;
 12  }
 13};
 14
 15int main() {
 16  vector<YourWhateverPointer> items;
 17  
 18  items.push_back(YourWhateverPointer(new YourWhateverClass));
 19  items.push_back(YourWhateverPointer(new YourWhateverClass));
 20  items.push_back(YourWhateverPointer(new YourWhateverClass));
 21
 22  sort(items.begin(), items.end();
 23}

The value of doing it this way is you'll be able to sort inside other containers, not just vector.

If 'someValue' wont change, than you should use multiset which sorts on insertion for great speed boosts.

int main() {
  multiset<YourWhateverPointer> items;
  
  items.push_back(YourWhateverPointer(new YourWhateverClass));
  items.push_back(YourWhateverPointer(new YourWhateverClass));
  items.push_back(YourWhateverPointer(new YourWhateverClass));

  // items is already sorted.
}

William Labbett

Thanks.

#SelectExpand
  1#ifndef LEVEL_FEATURE_H
  2#define LEVEL_FEATURE_H
  3
  4
  5
  6enum { PONGPING_FEATURE_C_DRAW, PONGPING_FEATURE_G_DRAW };
  7
  8
  9
 10class LevelFeature {
 11
 12
 13   protected:
 14      LevelFeature() {}
 15      
 16   public:
 17   
 18      int feature_type;
 19   
 20      int time_to_delete;
 21   
 22      int draw_priority;
 23   
 24      virtual void draw() const = 0;
 25      virtual void update() =0;

That's what the top of my class definition looks like.

So I've got :

vector<LevelFeature *> features_for_level;

I need to sort them for lower values of draw_priority first.

Don't understand the code on the link page.

What should I study ?

I don't know about templates.

/* EDIT */

Thanks Dustin

ImLeftFooted

In my example you would make a LevelFeaturePointer class and implement the operator < on it. The answer is in my last post if you read it carefully.

William Labbett

No I was asking about Arthur's post. nm.

So if I wanted to access members of

YourWhateverClass

with a

vector<YourWhateverPointer> v;

v.push_back(YourWhateverPointer(new YourWhateverClass));
v.push_back(YourWhateverPointer(new YourWhateverClass));
v.push_back(YourWhateverPointer(new YourWhateverClass));

sort(items.begin(), items.end();

// I'd have to do :

((YourWhateverClass *) v[0].ptr)->member;

Is that right ?

ImLeftFooted

There's no casting.

v[0].ptr->member

Pro-tip: Try to write code that never needs to leverage type casting.

William Labbett

Code like this ? :-/

features_for_level.push_back( LevelFeaturePointer( (LevelFeature *) rp ));

Stas B.

Dustin Dettmer said:

The value of doing it this way is you'll be able to sort inside other containers, not just vector.

What are you talking about? Why would you want to wrap a pointer in a special class and provide it with a comparison operator that only makes any sense in the context of sorting and only allows you to sort by one specific property? If you then wanted to sort by another property, would you need to make another pointer wrapper just for that? What does it have to do with being able to sort inside other containers? You're using an overload of the same sort function used in Arthur's example. In short, horrible, horrible idea. OP should totally go with Arthur's example. Why would you even want anything else?

William Labbett

I'd rather not have to rewrite all my code to deal with the new class, but I can't see how the code Arthur posts would work in my situation.

Stas B.

#SelectExpand
  1struct Test {
  2 int i;
  3 
  4 Test()
  5 {
  6  this->i = 0;
  7 }
  8 
  9 Test(int i)
 10 {
 11  this->i = i;
 12 }
 13};
 14
 15bool cmp(Test* t1, Test* t2) { return (t1->i<t2->i); }
 16
 17int main () {
 18  std::vector<Test*> vec;
 19  
 20  vec.push_back(new Test(1));
 21  vec.push_back(new Test(6));
 22  vec.push_back(new Test(3));
 23  vec.push_back(new Test(0));
 24
 25  sort(vec.begin(), vec.end(), cmp);
 26
 27  for(int i = 0; i < vec.size(); i++)
 28   printf("%d", vec[i]->i);
 29
 30  return 0;
 31}

Works exactly the same if you change the vector to a list or anything else.

William Labbett

Magic.

Thanks very much.

...and thanks to Arthur and Dustin too.

ImLeftFooted

William Labbett said:

Code like this ?

features_for_level.push_back( LevelFeaturePointer( (LevelFeature *) rp ));

No! Stop casting things. This code will require no casting.

Quote:

What are you t ... angry gibbering ... ing else?

Because you're cluttering your program space with functions everywhere on the global namespace and the definition of sort is not connected to the class. The more you put into the class the better.

I would actually update the code to something like this:

#SelectExpand
  1class YourWhateverClass {
  2public:
  3
  4  bool operator <(YourWhateverClass &right) {
  5    return someValue < right.someValue;
  6  }
  7};
  8
  9class YourWhateverPointer {
 10public:
 11  YourWhateverClass *ptr;
 12  YourWhateverPointer(YourWhateverClass *ptr) : ptr(ptr) {}
 13
 14  bool operator <(YourWhateverPointer &right) {
 15    return *ptr < *right.ptr;
 16  }
 17};

And then you can make YourWhateverPointer a generic class with a template parameter. But I'll leave that as an exercise for the reader.

http://www.themusingsofalostprogrammer.com/2012/05/beauty-of-c-is-in-its-sorting.html

Stas B.

Dustin Dettmer said:

Because you're cluttering your program space with functions everywhere on the global namespace and the definition of sort is not connected to the class. The more you put into the class the better.

I like it how you conviniently forget to address my "angry gibbering" even though it makes a bunch of valid points and explains why what you're doing is bad. You still haven't explained what your method has to do with sorting different containers either. While you're at it, please explain why littering the program and global namespace with bogus pointer wrapper classes is any better than littering it with functions? A class has a global identifier name and takes up more space. Finally, explain what stops you from making the comparator function a static member function the class. That would connect it to the class, get it out of the global namespace and is really a pretty obvious thing to do.

Quote:

The real solution to this problem lies in C++11's new move semantics to use MyClass objects in items instead of pointers (really cool stuff, go read about move semantics).

This is from your brilliant article. Sure, move semantics could save you the effort of writing pointer wrappers, but how exactly are they going to help you if you want to sort by different properties in different places in your program? It's pretty common to want to be able to do that.

Quote:

And then you can make YourWhateverPointer a generic class with a template parameter. But I'll leave that as an exercise for the reader.

You very obviously can't because the comparison operator would be different in pretty much every case.

Don't forget to remove your embarassing article. You wouldn't want it to mislead people, would you?

Audric

edit: missed that StasB has already addressed the point about global namespace.

static bool Test:comparebyheight(Test* t1, Test* t2) { return (t1->height<t2->height); }

axilmar

William Labbett said:

I've got a vector of class pointers I need to sort according to the value of a member of the class.

#SelectExpand
  1#include <algorithm>
  2#include <vector>
  3using namespace std;
  4
  5class Foo {
  6    int bar;
  7};
  8
  9bool compare_foos(Foo *a, Foo *b) {
 10    return a->bar < b->bar;
 11}
 12
 13int main() {
 14    vector<Foo *> foos;
 15    std::sort(foos.begin(), foos.end(), compare_foos);
 16}

Trent Gamblin

Just a side note, the standard libraries will sometimes do random things if the comparator function doesn't address equal values. Handling equal values is called making the sort "stable". So I'd write axilmar's code as:

bool compare_foos(Foo *a, Foo *b) {
   return a->bar <= b->bar;
}

Just the simple addition of the = sign in the comparison.

Stas B.

Trent Gamblin said:

Just a side note, the standard libraries will sometimes do random things if the comparator function doesn't address equal values. Handling equal values is called making the sort "stable".

As far as I know, "stable" simply means that elements with equal keys keep their relative order after the sort. It usually doesn't matter. How does the addition of the equality sign affect the stability? As far as I know, the "sort" function does an unstable sort in both cases and the "stable_sort" function does a stable sort in both cases.

Trent Gamblin

Stas B. said:

As far as I know, "stable" simply means that elements with equal keys keep their relative order after the sort.

Yeah, exactly, and that's exactly what the '=' does. Think about it.

EDIT: Also, in many cases is DOES matter, that's why it exists. Try implementing A* with a vector without a stable sort and nobody to tell you the difference. You'll likely go nuts before figuring it out.

Stas B.

I said it USUALLY doesn't matter. Stability depends on the algorithm. Your particular implementation of your particular sorting algorithm of choice needed that correction. The STL stable_sort function does not. There is no single "correct" way. You just need read the documentation to see what a given implementation expects your comparison callback to return, so your point is entirely moot.

Trent Gamblin

Yes, entirely. Or you're just mad because I proved you wrong and now you're being a whiney little jerk. All I did was point out something that could be important for the OP to know. You thought you saw an opportunity to show us how smort you are and I rebuffed you. Now go get your mom to make you some cookies and milk and stop being an asshat.

Dizzy Egg

He is a bit snappy isn't he?

Arthur Kalliokoski

AFAICT he's just started it in the last couple of months, even though he's been here 4 years. Maybe something else happened.

Trent Gamblin

What? The guy obviously thinks this is some sort of competition, and thinks he's a genius and talks nonsense to try to not look bad. All I did was try to tell William about stable sorts which are important and he tries to shut me down. A real asshat.

Stas B.

Trent Gamblin said:

All you did was to say something completely nonsensical. All I did was to correct you. You rebuffed me? I'm sorry, I totally missed it since you did not actually address anything I said.

Your advice is factually incorrect and misleading. Your suggestion may actually lead to incorrect results. The comparison callback has nothing to do with the stability of the sorting. You just need to provide the appropriate algorithm with the approproate callback function which may or may not need an additional '='. I'm not mad at you or anyone. I'm sorry if you need three spoons of sugar to go with the criticism of your nonsense. I couldn't care less what people here think about my intelligence. I will keep calling you on your bullsh*t and you feel free to call me on mine. Unlike you, I don't hesitate to admit that I'm wrong, apologize and thank whoever corrects me.

[EDIT]

Oh. Excuse me. Did I say "may"? Your suggestion in fact DOES give incorrect results. Run this and see for yourself:

#SelectExpand
  1#include <iostream>
  2#include <algorithm>
  3#include <vector>
  4#include <conio.h>
  5
  6using namespace std;
  7
  8bool compare_as_ints (double i,double j)
  9{
 10  return (int(i)<=int(j));
 11}
 12
 13int main () {
 14  double mydoubles[] = {3.14, 1.41, 2.72, 4.67, 1.73, 1.32, 1.62, 2.58};
 15
 16  vector<double> myvector;
 17  vector<double>::iterator it;
 18
 19  myvector.assign(mydoubles,mydoubles+8);
 20
 21  cout << "using default comparison:";
 22  stable_sort (myvector.begin(), myvector.end());
 23  for (it=myvector.begin(); it!=myvector.end(); ++it)
 24    cout << " " << *it;
 25
 26  myvector.assign(mydoubles,mydoubles+8);
 27
 28  cout << "\nusing 'compare_as_ints' :";
 29  stable_sort (myvector.begin(), myvector.end(), compare_as_ints);
 30  for (it=myvector.begin(); it!=myvector.end(); ++it)
 31    cout << " " << *it;
 32
 33  cout << endl;
 34  
 35  getch();
 36
 37  return 0;
 38}

Trent Gamblin

See, you don't admit you're wrong because you WERE and ARE wrong. What I showed in that code is how to produce a stable sort using std::sort. Geeze man, get over yourself.

Arthur Kalliokoski

Stas B. said:

I'm not mad at you or anyone.

Quote:

you need three spoons of sugar

Quote:

I couldn't care less

Quote:

I will keep calling you on your bullsh*t

You could have fooled me.

Trent Gamblin

The only thing I did wrong in this thread is fail to explain that you don't always want or need a stable sort. That was an accidental omission. Feel free to point out any other "nonsensical bullshit".

Stas B.

Trent Gamblin said:

See, you don't admit you're wrong because you WERE and ARE wrong. What I showed in that code is how to produce a stable sort using std::sort. Geeze man, get over yourself.

Are you honestly an idiot?
Your callback gives incorrect result both for sort and stable_sort.
See updated previous post for a demonstration.

Arthur Kalliokoski said:

You could have fooled me.

That's my default manner of speaking. Shame on me.
I don't outright flame people with personal attacks and I do try to help and answer people's questions, so bear with me.

Trent Gamblin

1) The sort you used first was completely different from mine. Don't compare apples and oranges. YOUR results are wrong. It's supposed to sort them as integers.

2) Try putting MINE first, not after you've fucked up the arrays. It WORKS. Numb nuts.

Audric

For what it's worth, I find the documentation of STL's sort() very ambiguous on how the compare function should behave.
Libc's qsort() seems more sane to me as it specifies that the comparison functions should handle explicitely the 'equal' case. Most comparison functions I've written for qsort were simply return obj2->y - obj1->y;

Dizzy Egg

Finally an exciting thread! Come on Trent destroy him DESTROY!!!!

Trent Gamblin

I think I just did that.

EDIT: And I appologize for being a prick. I should have corrected you in a more calm manner ... got the rage in me, it's a sickness.

axilmar

The function std::sort does not guarantee the preservation of order of equivalents; std::stable_sort does have that guarantee.

Stas B.

Audric said:

For what it's worth, I find the documentation of STL's sort() very ambiguous on how the compare function should behave.

That's actually true. Thankfully, it comes with an example. But to be honest, that's not even the point. The point was that the stability depends on the algorithm, not on the comparison function. Granted, it won't work if you don't provide it with the callback it expects, but that's obvious and besides the point.

Trent Gamblin said:

1) The sort you used first was completely different from mine. Don't compare apples and oranges. YOUR results are wrong. It's supposed to sort them as integers.

2) Try putting MINE first, not after you've fucked up the arrays. It WORKS. Numb nuts.

I honestly don't understand what you're talking about. I hope you're just trolling... Correct me if I'm wrong, but you said that this callback:

bool compare_foos(Foo *a, Foo *b) {
   return a->bar <= b->bar;
}

Can be used with std::sort to achieve stable sorting.
My example demonstrates that it doesn't work with neither std::sort nor std::stable_sort. There's nothing wrong with my array. I copy it into a vector then sort the vector by using the integer part as the key. The fractional part is used to differentiate between the numbers to see if they end up in the original relative order. Clearly, they don't. Feel free to hack up your own example and post it here so we could all observe how it also fails.

Come on, guys. You're better than that. Somebody take a serious look at it and explain to him why he's wrong.

[EDIT]

To be fair, this example isn't even mine. It's from the STL documentation that demonstrates stable sorting. I just replaced their callback with yours.

Matthew Leverton

The std sort is not stable when two elements are equal. How is that up for discussion?

Trent Gamblin

Ok, I'm wrong. I had my definitions wrong. By 'stable sort' I actually meant a sort that will return the same results every time. Hell, I may even be wrong about that, but I remember having different results returned when using < and not <= when implementing A* one time. So it's not a stable sort, and I'm not even sure that < will return different results at any time. I was sure that was the case though. Anyway, appologies for posting incorrect information.

Stas B.

Trent Gamblin said:

Ok, I'm wrong. I had my definitions wrong. By 'stable sort' I actually meant a sort that will return the same results every time.

Oh. In that case, I'm sorry, Trent. I didn't realize we were actually talking about completely different things!

I'll just leave this here:

Trent Gamblin said:

Trent Gamblin:
Stas B. said:
As far as I know, "stable" simply means that elements with equal keys keep their relative order after the sort.

Yeah, exactly, and that's exactly what the '=' does. Think about it.

Trent Gamblin said:

YOUR results are wrong. It's supposed to sort them as integers.

2) Try putting MINE first, not after you've fucked up the arrays. It WORKS. Numb nuts.

Implying my example gave you different results every time?
It's obvious that the only reason for your apology is because I mentioned that's the proper way to behave in my previous posts. Your disgusting dishonesty still shows through, though. No. I'm not mad. I'm just calling you on your bullshit again.

Trent Gamblin

Ok dude, think what you want. I don't really care. If you can't accept an appology then you don't deserve one.

Stas B.

Trent Gamblin said:

Ok dude, think what you want. I don't really care. If you can't accept an appology then you don't deserve one.

Oh, come on. Nobody can be that thick. You think I need your apologies? Seriously? It's just about being a decent person. How decent is it when you're outright lying in your apology? It's not about what I think. It's about what anybody who reads your posts thinks. Maybe I sound like a jerk, but at least I'm honest.

Trent Gamblin

I was being completely honest. I think you just have a hard time seeing any merit in anyone but yourself. You win on technical terms, but I have no doubt that I walk away the better person.

Stas B.

Trent Gamblin said:

I was being completely honest. I think you just have a hard time seeing any merit in anyone but yourself. You win on technical terms, but I have no doubt that I walk away the better person.

You started flaming me with personal attacks as a response to my posts that talked exclusively about the technical matter at hand and not about you. After realizing you were wrong, you wrote a phoney apology where you lie about mixing up the definitions, as evident by the fact that some of your earlier posts make no sense in this new context and the fact that you've confirmed that we are in fact talking about the same thing. If you think you walk away the better person, I feel sorry for you.

Trent Gamblin

I was right about one thing: asshat. And that's not a compliment even though you wear it like a badge of pride. Don't feel sorry for me, my shit has been sorted for a long time now. Good luck with yours.

Dizzy Egg

Your imlplying that Trent is thick? Oh dear oh dear, a LOT to learn then Stas B.

GibbSticks

Another thread completely destroyed because of petty arguments, sigh

:'( :-X ::) :-/

bamccaig

I'm a little confused about this... It sounds like stable_sort is designed to work the way Trent's revision is without explicitly coding the comparer that way. So wouldn't the correct way to achieve a "stable sort" be using stable_sort instead of altering the behavior of your comparer?

Stas B.

bamccaig said:

So wouldn't the correct way to achieve a "stable sort" be using stable_sort instead of altering the behavior of your comparer?

Yes. The only way if you want to use the STL sort functions.

bamccaig

@Stas B.: For what it's worth I don't think that you were being an asshat in this thread either... :-/

Trent Gamblin

bamccaig said:

@Stas B.: For what it's worth I don't think that you were being an asshat in this thread either...

Predictable.

Let's rewind and see who threw the first punch...

Stas B. said:

so your point is entirely moot

Stas B.

Trent Gamblin said:

Let's rewind and see who threw the first punch...

Stas B. said:
so your point is entirely moot

But it was. :-/
I don't see why you'd find that so offensive. It's not even a personal attack. I just said your point was moot. I even bothered to explain why.

Trent Gamblin

It wasn't. My code was wrong, but my point was to let the OP know about stable sorts. Code being wrong doesn't make the purpose of the message wrong. And it is offensive and I think you meant it that way. Why would I post something for no purpose whatsoever? Only an imbecile would do so and that's what your statement implies.

Stas B.

I was not implying anything beyond what I clearly stated, specifically, that your suggestion was wrong and misleading. Arguably, if you don't know how to sort, you are an incompetent programmer, but that's besides the point. Your trouble with A* had nothing to do with stable sorting or with the sort returning a different result every time. That's obviously unlikely if you pass it the same input. It had to do with you failing to read the documentation that describes what your callback should do.

Trent Gamblin

Another one to lump with bamccaig.

Thread #610283. Printed from Allegro.cc