Sorting a list

[SKumar]

Hi All,
I have a list which contains my class objects. My class is
having two variables. I want to sort the list based on these two
variables.

Ex :
class Foo
{
...
...
public:
int nAngle;
int nDist;
};

int main()
{
std::vector<Foo> list;
...
...
//here i want to sort the list...first based on nAngle & then
nDist...
}

PS: Though in this case my variables are int, it may be anything else.
Is there any simple & generic way to do this?

Thanks,
#SKumar#

[Michiel.Salters]

SKumar wrote:

Hi All,
I have a list which contains my class objects. My class is
having two variables. I want to sort the list based on these two
variables.

Ex :
class Foo
{
public:
int nAngle;
int nDist;
};
std::vector<Foo> list;

That's not a list. A std::list<Foo> would be a list, but they don't
sort well.

Anyway, you need std::sort. If you tell it how to compare two Foo's, it

can sort a vector<Foo>. It can also sort a std::deque<Foo>, because
that
also has random iterators, but not std::list.

[persenaama]

Write a predicate compare function and use the std::vector:.sort that
invokes it.

int compare_pred(const Foo& a, const Foo& b)
{
// TODO: implement a < b here
}

// invoke like this
list.sort(compare_pred);

[Daniel T.]

In article <11**********************@g47g2000cwa.googlegroups .com>,
"SKumar" <Su************@gmail.com> wrote:

Hi All,
I have a list which contains my class objects. My class is
having two variables. I want to sort the list based on these two
variables.

Ex :
class Foo
{
...
...
public:
int nAngle;
int nDist;
};

int main()
{
std::vector<Foo> list;
...
...
//here i want to sort the list...first based on nAngle & then
nDist...
}

PS: Though in this case my variables are int, it may be anything else.
Is there any simple & generic way to do this?

Yes, you have to make an op< for comparing two Foos...

bool operator<( const Foo& lhs, const Foo& rhs ) {
//if ( lhs is "smaller" than rhs ) return true;
//else return false;
}

Once you have the above, you can:

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

BTW, "list" probably isn't the best name for a vector of Foo's.

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.

[persenaama]

Ooops, I goofed: returns bool, vector doesn't have *member* sort .. :)
Thanks!

[Dietmar Kuehl]

SKumar wrote:

I have a list which contains my class objects. My class is
having two variables. I want to sort the list based on these two
variables.

The first thing to do when you want to sort objects is to define
a [strict partial] ordering on them. For the case of your two
variables you probably could do with a lexicographical order as
you could obtain using tuples (either from TR1 or from Boost):

return tie(obj1.nAngle, obj1.nDist) < tie(obj2.nAngle, obj2.nDist);

'tie()' is a factory function creating a tuple of references and
the expression just returns the result of comparing the two created
tuples. The same effect can be obtained using appropriate logic to
compare the involved object but I consider the above much more
readable than manual alternative.

Once you have your ordering defined, you would next have to determine
how to apply the order. There are generally two possible approaches:

1. If the ordering always applies reasonably to the involved objects,
you can make the object available by overloading suitable
operators for the corresponding class. Effectively, this means
that you define 'operator<()' for objects for your class:

bool operator< (Type const& obj1, Type const& obj2) {
// e.g. the tuple expression goes here if the operator has
// appropriate access to the member variables
}

2. If the ordering is specific to the task at hand and is not really
related to the objects in general, you would rather use a
"predicate" which is just an object that can be used with the
function call operator on the involved objects. Such a predicate
can be a simple function (in which case the object is actually
just the function pointer) or a class, e.g.:

struct MyCompare {
bool operator()(Type const& obj1, Type const& obj2) const {
// comparing the objects goes here
}
};

With this in place, you could easily sort a random access sequence
of your objects using either the default predicate which happens to
be 'std::less<Type>' and simply uses 'operator<()', i.e.

std::sort(sequence.begin(), sequence.end());

or you can use the 'std::sort()' function specifying the predicate:

std::sort(sequence.begin(), sequence.end(), MyCompare());

If you really want to sort a 'std::list<Type>', you would use the
member 'sort()' because 'std::list<Type>' does not provide random
access iterators but can still be sorted efficiently.
--
<mailto:di***********@yahoo.com> <http://www.dietmar-kuehl.de/>
<http://www.eai-systems.com> - Efficient Artificial Intelligence