STL sort compare function problem

[laniik]

Hi. I have a problem using STL's built in sort that seems impossible
to get around.

if i have:
--------------------------------
struct object
{
int val;
}

void main()
{
vector<object> objects;
vector<int> indices;

sort(indices.be gin(),indices.e nd(),compare)
}
--------------------------------

indices contains ints that refer to an index into the objects array

now, I want to sort the array "indices" based on the values in the
objects array that the integers in indices refer to. but i cannot
think of a legitimate compare funciton that could do this.

ideally i would have
bool compare(const int a, const int b, vector<object>& objects)
{
return(objects[a].val<objects[b].val)
}

but i cannot add that last parameter or i get compile problems.
"error C2064: term does not evaluate to a function taking 2 arguments"

does anyone know how to do this? thanks!

Oliver

[Alf P. Steinbach]

Re: STL sort compare function problem

* laniik:[color=blue]
> Hi. I have a problem using STL's built in sort that seems impossible
> to get around.
>
> if i have:
> --------------------------------
> struct object
> {
> int val;
> }[/color]

Missing semicolon.

[color=blue]
> void main()[/color]

Invalid signature for 'main' -- see the C++ FAQ or (even better)
Bjarne Stroustrup's own FAQ.

[color=blue]
> {
> vector<object> objects;
> vector<int> indices;
>
> sort(indices.be gin(),indices.e nd(),compare)
> }
> --------------------------------
>
> indices contains ints that refer to an index into the objects array
>
> now, I want to sort the array "indices" based on the values in the
> objects array that the integers in indices refer to. but i cannot
> think of a legitimate compare funciton that could do this.
>
> ideally i would have
> bool compare(const int a, const int b, vector<object>& objects)
> {
> return(objects[a].val<objects[b].val)
> }
>
> but i cannot add that last parameter or i get compile problems.
> "error C2064: term does not evaluate to a function taking 2 arguments"
>
> does anyone know how to do this? thanks![/color]

The comparison "function" can be an object that behaves like a function,
i.e. has an operator(). That kind of object is called a functor. And
a functor object can carry a pointer to the 'objects' vector.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[laniik]

Re: STL sort compare function problem

ok i did some research and am now introduced to the wonderful world of
functors, but its not entirely clear to me how this works.

i have a functor:
class compare
{
public:
vector<object>* objects;
bool operator ()(const int p1,const int p2)
{
return((*object s)[p1].x < (*objects)[p2].x);
}
};

and in my main
....
sort(indices.be gin(),indices.e nd(),compare()) ;
....

now this compiles fine, but the problem is that i have no clue how to
initiaize the pointer to the objects vector. I am not instantiating
the class when i pass it in the sort function, so I dont see how its
possible to set the pointer anywhere. Where can this be done?

thanks a lot for the help!

Oliver

[Alf P. Steinbach]

Re: STL sort compare function problem

* laniik:[color=blue]
> ok i did some research and am now introduced to the wonderful world of
> functors, but its not entirely clear to me how this works.
>
> i have a functor:
> class compare
> {
> public:
> vector<object>* objects;[/color]

Style & safety: make the pointer 'private'.
[color=blue]
> bool operator ()(const int p1,const int p2)
> {
> return((*object s)[p1].x < (*objects)[p2].x);
> }[/color]

More style & safety: make that member function 'const'.
[color=blue]
> };
>
> and in my main
> ...
> sort(indices.be gin(),indices.e nd(),compare()) ;
> ...
>
> now this compiles fine, but the problem is that i have no clue how to
> initiaize the pointer to the objects vector. I am not instantiating
> the class when i pass it in the sort function, so I dont see how its
> possible to set the pointer anywhere. Where can this be done?[/color]

The 'compare' class constructor.

class compare
{
private:
std::vector<obj ect>* myPObjects;
public:
compare( std::vector<obj ect>* p ): myPObjects( p ) {}
... as before
};

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Larry I Smith]

Re: STL sort compare function problem

laniik wrote:[color=blue]
> ok i did some research and am now introduced to the wonderful world of
> functors, but its not entirely clear to me how this works.
>
> i have a functor:
> class compare
> {
> public:
> vector<object>* objects;
> bool operator ()(const int p1,const int p2)
> {
> return((*object s)[p1].x < (*objects)[p2].x);
> }
> };
>
> and in my main
> ...
> sort(indices.be gin(),indices.e nd(),compare()) ;
> ...
>
> now this compiles fine, but the problem is that i have no clue how to
> initiaize the pointer to the objects vector. I am not instantiating
> the class when i pass it in the sort function, so I dont see how its
> possible to set the pointer anywhere. Where can this be done?
>
> thanks a lot for the help!
>
> Oliver
>[/color]


#include <vector>
#include <algorithm>

struct object
{
int val;
};

class compare
{
public:
std::vector<obj ect> * objects;

compare(std::ve ctor<object>* obj) : objects(obj) {}

bool operator ()(const int p1,const int p2)
{
return((*object s)[p1].val < (*objects)[p2].val);
}
};



int main()
{
std::vector<obj ect> objects;
std::vector<int > indices;

std::sort(indic es.begin(),indi ces.end(),compa re(&objects));

return 0;
}

[red floyd]

Re: STL sort compare function problem

laniik wrote:[color=blue]
> ok i did some research and am now introduced to the wonderful world of
> functors, but its not entirely clear to me how this works.
>
> i have a functor:
> class compare
> {
> public:
> vector<object>* objects;
> bool operator ()(const int p1,const int p2)
> {
> return((*object s)[p1].x < (*objects)[p2].x);
> }
> };
>
> and in my main
> ...
> sort(indices.be gin(),indices.e nd(),compare()) ;
> ...[/color]

Why use a pointer to the vector in your functor? Why
not use a reference?


class compare : public std::binary_fun ction<int, int>
{
const std::vector<obj ect>& objects;
public:
compare(const std::vector<obj ect>& o) : objects(o) { }
inline bool operator()(cons t int p1, const int p2)
{
return (objects[p1].x < objects[p2].x);
}
};

//...
sort(indices.be gin(), indices.end(), compare(objects ));
//...

[Greg]

Re: STL sort compare function problem

red floyd wrote:[color=blue]
> laniik wrote:[color=green]
> > ok i did some research and am now introduced to the wonderful world of
> > functors, but its not entirely clear to me how this works.
> >
> > i have a functor:
> > class compare
> > {
> > public:
> > vector<object>* objects;
> > bool operator ()(const int p1,const int p2)
> > {
> > return((*object s)[p1].x < (*objects)[p2].x);
> > }
> > };
> >
> > and in my main
> > ...
> > sort(indices.be gin(),indices.e nd(),compare()) ;
> > ...[/color]
>
> Why use a pointer to the vector in your functor? Why
> not use a reference?
>[/color]

The functor should ideally be stateless. And in fact it could be if the
indices vector stored iterators of the container holding objects,
instead of integer indices. For the indices vector to store iterators,
the iterators would have to be stable. Iterators for a vector do remain
valid most of the time, but increasing the size of a vector can
invalidate all of its iterators.

Since the indices vector already offers the benefits of vector storage,
why not change objects to a different type of container, one with
stable iterators? Doing so would make compare so simple it could become
just an ordinary function (if desired), and the whole implementation
would be more self-maintaining:

#include <vector>
#include <list>
#include <algorithm>

using std::vector;
using std::list;

struct object
{
int val;
};

bool
compare( const list<object>::i terator& i1,
const list<object>::i terator& i2 )
{
return (*i1).val < (*i2).val;
}

int main()
{
list<object> objects;
vector<list<obj ect>::iterator> indices;

std::sort( indices.begin() , indices.end(), compare);

return 0;
}

[Alf P. Steinbach]

Re: STL sort compare function problem

* red floyd:[color=blue]
>
> Why use a pointer to the vector in your functor? Why
> not use a reference?[/color]

A reference is not copyable. Hence some compilers may complain about not
being able to generate an assignment operator. And many people (including
me) dislike such warnings, and also dislike writing more to avoid them.

A reference as an argument gives you an existence guarantee under the
assumption that the reference is not obtained by pointer dereferencing,
or the assumption that the rest of the program is correct C++, while a
reference as member does not give any such guarantee, so it has no
advantage that way.

On the other hand, a reference states in code that a null-reference is a
bug (it's invalid C++), unintended.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Alf P. Steinbach]

Re: STL sort compare function problem

* Greg:[color=blue]
>
> The functor should ideally be stateless. And in fact it could be if the
> indices vector stored iterators of the container holding objects,
> instead of integer indices. For the indices vector to store iterators,
> the iterators would have to be stable. Iterators for a vector do remain
> valid most of the time, but [1] increasing the size of a vector can
> invalidate all of its iterators.[/color]

In addition to that last point, (2) the current design decouples the 'indices'
from the 'objects' so that a given 'indices' can be used with any 'objects'
vector of sufficient size.

And, it may be that (3) that design is not in one's own code, but imposed by
existing, frozen code.

[color=blue]
> Since the indices vector already offers the benefits of vector storage,
> why not change objects to a different type of container, one with
> stable iterators? Doing so would make compare so simple it could become
> just an ordinary function (if desired), and the whole implementation
> would be more self-maintaining:[/color]

Barring (1), (2) or (3), or some other reason. ;-)

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?