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;
}
Missing semicolon.

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

{
vector<object> objects;
vector<int> indices;

sort(indices.begin(),indices.end(),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!

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?

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((*objects)[p1].x < (*objects)[p2].x);
}
};

and in my main
....
sort(indices.begin(),indices.end(),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

* laniik:

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;
Style & safety: make the pointer 'private'.
bool operator ()(const int p1,const int p2)
{
return((*objects)[p1].x < (*objects)[p2].x);
}
More style & safety: make that member function 'const'.
};

and in my main
...
sort(indices.begin(),indices.end(),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?

The 'compare' class constructor.

class compare
{
private:
std::vector<object>* myPObjects;
public:
compare( std::vector<object>* 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?

laniik wrote:

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((*objects)[p1].x < (*objects)[p2].x);
}
};

and in my main
...
sort(indices.begin(),indices.end(),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

#include <vector>
#include <algorithm>

struct object
{
int val;
};

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

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

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

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

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

return 0;
}

laniik wrote:

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((*objects)[p1].x < (*objects)[p2].x);
}
};

and in my main
...
sort(indices.begin(),indices.end(),compare());
...

Why use a pointer to the vector in your functor? Why
not use a reference?
class compare : public std::binary_function<int, int>
{
const std::vector<object>& objects;
public:
compare(const std::vector<object>& o) : objects(o) { }
inline bool operator()(const int p1, const int p2)
{
return (objects[p1].x < objects[p2].x);
}
};

//...
sort(indices.begin(), indices.end(), compare(objects));
//...

red floyd wrote:

laniik wrote:

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((*objects)[p1].x < (*objects)[p2].x);
}
};

and in my main
...
sort(indices.begin(),indices.end(),compare());
...

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

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>::iterator& i1,
const list<object>::iterator& i2 )
{
return (*i1).val < (*i2).val;
}

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

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

return 0;
}

* red floyd:

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

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?

* Greg:

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

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:

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?