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[i]].

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

I want to use a sort(random_acc ess_iterator first, random_access_i terator
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[i] << endl;
}

------------

Is that at all possible or am I going about it entirely the wrong way?

[John Harrison]

"Mike" <ha*****@impkin .com> wrote in message
news:2004021812 53253492%haladi e@impkincom...

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[i]].

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

I want to use a sort(random_acc ess_iterator first, random_access_i terator
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[i] << endl;
}

------------

Is that at all possible or am I going about it entirely the wrong way?

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::operat or() 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]

"Mike" <ha*****@impkin .com> wrote
[...]

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_obj ect" (or "compare_object s", 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_fun ction <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[i] << endl;
}

------------

Is that at all possible or am I going about it entirely the wrong way?

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

Good luck,
Buster.

[Buster]

"John Harrison" <jo************ *@hotmail.com> wrote > "Mike"
<ha*****@impkin .com> wrote in message

[...]

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

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

"Buster" <no***@nowhere. com> wrote in message
news:c0******** **@newsg1.svr.p ol.co.uk...

"John Harrison" <jo************ *@hotmail.com> wrote > "Mike"
<ha*****@impkin .com> wrote in message

[...]

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]

"John Harrison" <jo************ *@hotmail.com> wrote

"Buster" <no***@nowhere. com> wrote

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

No, RANK is a vector of ints.

john

You're totally right and I apologize.
Buster.