how to use sort for

[Mike]

Hi there,

I'm very new to the STL and am struggling a bit with a sort, and would love
some help if possible!

I have a simple array V of objects of class OBJ that I want to rank in
order of the float OBJ.t and put the ranks into a list of ints, call it
RANK, so I can then access the OBJ with the i-th smallest value of t by
V[RANK].

This is hideous and does not take advantage of STL's sort algorithm.

I want to use a sort(random_access_iterator first, random_access_iterator
last, compare comp) for this but I don't know how.

I'd like to sent up with something *like*

#include <algorithm>
#include <functional> // I'm assuming I need this included

class OBJ {
public:
OBJ() { t = 0.0; }
~OBJ();
float
t;
};

class compOBJ : public binary_function<OBJ &o1, OBJ &o2, bool>
{
public:
bool operator()(OBJ &o1, OBJ &o2)
{ return (o1.t < o2.t); }
};

int main()
{
vector<OBJ>
V(10);
vector<OBJ*>
S(10); // vector of pointers to OBJ

int i;
for (i = 0; i < 10; i++)
V.t = (float) rand(); // put in some random vals

S.sort(V.first, V.last, compObj); // sort the objects in V and put their
pointers in order into S

OBJ *ob;
for (i = 0; i < 10; i++)
cout << i << "-ranked OBJ pointer is " << S << endl;
}

 

[John Harrison]

Hi there,

I'm very new to the STL and am struggling a bit with a sort, and would love
some help if possible!

I have a simple array V of objects of class OBJ that I want to rank in
order of the float OBJ.t and put the ranks into a list of ints, call it
RANK, so I can then access the OBJ with the i-th smallest value of t by
V[RANK].

This is hideous and does not take advantage of STL's sort algorithm.

I want to use a sort(random_access_iterator first, random_access_iterator
last, compare comp) for this but I don't know how.

I'd like to sent up with something *like*

#include <algorithm>
#include <functional> // I'm assuming I need this included

class OBJ {
public:
OBJ() { t = 0.0; }
~OBJ();
float
t;
};

class compOBJ : public binary_function<OBJ &o1, OBJ &o2, bool>
{
public:
bool operator()(OBJ &o1, OBJ &o2)
{ return (o1.t < o2.t); }
};

int main()
{
vector<OBJ>
V(10);
vector<OBJ*>
S(10); // vector of pointers to OBJ

int i;
for (i = 0; i < 10; i++)
V.t = (float) rand(); // put in some random vals

S.sort(V.first, V.last, compObj); // sort the objects in V and put their
pointers in order into S

OBJ *ob;
for (i = 0; i < 10; i++)
cout << i << "-ranked OBJ pointer is " << S << endl;
}

Both, its possible, and you are going about it the wrong way.

All code is untested.

To start with you need to be clear what you are sorting. In your description
you talk about a list (or maybe a vector) of ints called RANK, in your code
you use a vector of pointers called S. I'm going to assume you want a vector
of ints. Since you are sorting a vector of ints, your sort criterion has to
compare two integers. Like this

class RankCmp : public binary_function<int, int, bool>
{
public:
bool operator()(int i1, int i2) const
{
...

And you do the sort of RANK something like this

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

Now for the two bits that say ...

The RankCmp:perator() is clearly going to have to refer back to the
original object vector, so the RankCmp class needs a reference to that
vector, i.e.


class RankCmp : public binary_function<int, int, bool>
{
public:
RankCmp(const vector<OBJ>& o) : obj(o) {}
bool operator()(int i1, int i2) const
{
...
}
private:
const vector<OBJ>& obj;
};

The constructor has been added so the obj member variable can be
initialised.

Now the operator() is easy since we have a reference to the original vector,
it's just

bool operator()(int i1, int i2) const
{
return obj[i1].t < obj[i2].t;
}

And finally to fill in the last blank start the sort off with

sort(RANK.begin(), RANK.end(), RankCmp(V));

I guess you were struggling with the idea that a functor (like RankCmp) can
have member variables. It's a very powerful idea which is the great
advantage of functors over traditional function pointers.

john

 

[Buster]

[...]

I've re-indented the code because my newsreader doesn't handle tabs
properly.

#include <algorithm>
#include <functional> // I'm assuming I need this included

class OBJ {
public:
OBJ() { t = 0.0; }
~OBJ();
float
t;
};

Apart from looking horrible (IMO), all-caps is usually only used for
preprocessor macro names, so this might confuse people. What's wrong
with "object" and "comparison_object" (or "compare_objects", or
whatever it was you intended)?

class compOBJ : public binary_function<OBJ &o1, OBJ &o2, bool>
{
public:
bool operator()(OBJ &o1, OBJ &o2)
{ return (o1.t < o2.t); }
};

int main()
{
vector<OBJ>
V(10);
vector<OBJ*>
S(10); // vector of pointers to OBJ

int i;
for (i = 0; i < 10; i++)
V.t = (float) rand(); // put in some random vals

S.sort(V.first, V.last, compObj); // sort the objects in V and put their
pointers in order into S

No, this is not OK. vector <> has no sort () member function, and
std::sort () provides an in-place sort. You either want "std::sort
(V.first (), V.last (), compOBJ ());" (after which the rank of an
object is equal to its index in V) or "std::sort (S.first (), S.last
(), compare_objects_by_pointer ());" where we have

class compare_objects_by_pointer : public std::binary_function <OBJ
* p1, OBJ * p2, bool>
{
public:
bool operator () (OBJ * p1, OBJ * p2)
{ return p1->t < p2->t; }
};

The first option (sorting V directly) is to be preferred on grounds
of simplicity and expressiveness unless there is a good reason why
not (e.g., you have found that sorting V makes the program run too
slowly, and that sorting pointers instead gives a significant
improvement).

OBJ *ob;
for (i = 0; i < 10; i++)
cout << i << "-ranked OBJ pointer is " << S << endl;
}

It's certainly possible, but I think you should steer clear of
containers-of-pointers when possible.

Good luck,
Buster.

 

[Buster]

[...]

Now the operator() is easy since we have a reference to the original vector,
it's just

bool operator()(int i1, int i2) const
{
return obj[i1].t < obj[i2].t;
}

And finally to fill in the last blank start the sort off with

sort(RANK.begin(), RANK.end(), RankCmp(V));

John, this will never work. RankCmp would be passed OBJ
objects/references/const references, not indices.

 

[Mike]

Dear John,

Both, its possible, and you are going about it the wrong way.

Thought as much... ;-)
I think the fundamental bit was the idea of the comparison functor having a
member variable, yes.
Many thanks!

 

[John Harrison]

[...]

Now the operator() is easy since we have a reference to the original vector,
it's just

bool operator()(int i1, int i2) const
{
return obj[i1].t < obj[i2].t;
}

And finally to fill in the last blank start the sort off with

sort(RANK.begin(), RANK.end(), RankCmp(V));

John, this will never work. RankCmp would be passed OBJ
objects/references/const references, not indices.

No, RANK is a vector of ints.

john

 

[Buster]

No, RANK is a vector of ints.

john

You're totally right and I apologize.
Buster.