Sorting STL lists

[Tim Frink]

Hi,

I need some help with STL lists.

I've a list with pointers to some objects,

let's say std::list< ObjectA* myList.

The objects of the class ObjectA all have a
function "int getIntValue()". What I need
now is to sort all elements of "myList" by the
return value of "getIntValue()" , i.e. after sorting
the first element in the list will be the one with
the smallest return value of "getIntValu e()" ... and
the last obviously with the largest.

Could you give me some hints how to do that?

Regards,
Tim

[=?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=]

Re: Sorting STL lists

On 2007-07-14 16:29, Tim Frink wrote:

Hi,
>
I need some help with STL lists.
>
I've a list with pointers to some objects,
>
let's say std::list< ObjectA* myList.
>
The objects of the class ObjectA all have a
function "int getIntValue()". What I need
now is to sort all elements of "myList" by the
return value of "getIntValue()" , i.e. after sorting
the first element in the list will be the one with
the smallest return value of "getIntValu e()" ... and
the last obviously with the largest.
>
Could you give me some hints how to do that?

You have to create a comparator function, something like

bool cmp(const ObjectA* a, const ObjectA* b)
{
return a->getIntValue( ) < b->getIntValeu( );
}


and then use

std::sort(list. begin(), list.end(), cmp);

--
Erik Wikström

[Kai-Uwe Bux]

Re: Sorting STL lists

Tim Frink wrote:

I've a list with pointers to some objects,
>
let's say std::list< ObjectA* myList.
>
The objects of the class ObjectA all have a
function "int getIntValue()". What I need
now is to sort all elements of "myList" by the
return value of "getIntValue()" , i.e. after sorting
the first element in the list will be the one with
the smallest return value of "getIntValu e()" ... and
the last obviously with the largest.

#include <list>
#include <cassert>
#include <iostream>
#include <ostream>

struct Object {

int i;

Object ( int k )
: i ( k )
{}

int getIntValue ( void ) {
return ( i );
}

};

bool ptr_compare( Object * lhs, Object * rhs ) {
assert( lhs != 0 );
assert( rhs != 0 );
return ( lhs->getIntValue( ) < rhs->getIntValue( ) );
}

typedef std::list< Object* PtrList;

int main ( void ) {
PtrList ptr_list;
ptr_list.push_b ack( new Object ( 4 ) );
ptr_list.push_b ack( new Object ( 3 ) );
ptr_list.push_b ack( new Object ( 1 ) );
ptr_list.push_b ack( new Object ( 7 ) );
ptr_list.push_b ack( new Object ( 4 ) );
ptr_list.push_b ack( new Object ( 5 ) );
for ( PtrList::const_ iterator iter = ptr_list.begin( );
iter != ptr_list.end(); ++ iter ) {
std::cout << (*iter)->getIntValue( ) << '\n';
}
std::cout << '\n';

ptr_list.sort( &ptr_compare ); // !!!!!!!!!!!!!!! !!!!!

for ( PtrList::const_ iterator iter = ptr_list.begin( );
iter != ptr_list.end(); ++ iter ) {
std::cout << (*iter)->getIntValue( ) << '\n';
}
}



Best

Kai-Uwe Bux

[Kai-Uwe Bux]

Re: Sorting STL lists

Erik Wikström wrote:

On 2007-07-14 16:29, Tim Frink wrote:

>Hi,
>>
>I need some help with STL lists.
>>
>I've a list with pointers to some objects,
>>
>let's say std::list< ObjectA* myList.
>>
>The objects of the class ObjectA all have a
>function "int getIntValue()". What I need
>now is to sort all elements of "myList" by the
>return value of "getIntValue()" , i.e. after sorting
>the first element in the list will be the one with
>the smallest return value of "getIntValu e()" ... and
>the last obviously with the largest.
>>
>Could you give me some hints how to do that?

>
You have to create a comparator function, something like
>
bool cmp(const ObjectA* a, const ObjectA* b)
{
return a->getIntValue( ) < b->getIntValeu( );
}
>
>
and then use
>
std::sort(list. begin(), list.end(), cmp);

I think, std::sort() needs random access iterators. You want:

list.sort( cmp );


Best

Kai-Uwe Bux

[bnonaj]

Re: Sorting STL lists

Tim Frink wrote:

Hi,
>
I need some help with STL lists.
>
I've a list with pointers to some objects,
>
let's say std::list< ObjectA* myList.
>
The objects of the class ObjectA all have a
function "int getIntValue()". What I need
now is to sort all elements of "myList" by the
return value of "getIntValue()" , i.e. after sorting
the first element in the list will be the one with
the smallest return value of "getIntValu e()" ... and
the last obviously with the largest.
>
Could you give me some hints how to do that?
>
Regards,
Tim

As stated earlier you need a comparator function to use with
std::sort(). Myself I created a template to handle iterator type
comparisons like that below

template <typename T>
inline bool DRefCompare(T i1,T i2)
{
return *i1 < *i2;
}

class Compartment
{
public:
typedef std::vector<MyO bjectvector;
typedef std::vector<vec tor::iteratoriv ector;
typedef std::vector<vec tor::const_iter atorcivector;

bool operator < (const MyObject &inp) const;
/*
Rest of the definition here
*/
};

MyObject::ivect or viCmp;
/*
Other code here
Create sorted list of MyObject iterators
*/
MyObject::vecto r::iterator iC = vCmp.begin();
do
{
viCmp.push_back (iC);
}
while (++iC != vCmp.end());

std::sort(viCmp .begin(),viCmp. end(),&DRefComp are<MyObject::v ector::const_it erator>);

Naturally this relies on the operator < () exists for type T, so changes
to make it more general might be more suitable

JB

[bnonaj]

Re: Sorting STL lists

bnonaj wrote:

Tim Frink wrote:

>Hi,
>>
>I need some help with STL lists.
>>
>I've a list with pointers to some objects,
>>
>let's say std::list< ObjectA* myList.
>>
>The objects of the class ObjectA all have a
>function "int getIntValue()". What I need
>now is to sort all elements of "myList" by the
>return value of "getIntValue()" , i.e. after sorting
>the first element in the list will be the one with
>the smallest return value of "getIntValu e()" ... and
>the last obviously with the largest.
>>
>Could you give me some hints how to do that?
>>
>Regards,
>Tim

>
As stated earlier you need a comparator function to use with
std::sort(). Myself I created a template to handle iterator type
comparisons like that below
>
template <typename T>
inline bool DRefCompare(T i1,T i2)
{
return *i1 < *i2;
}
>
class Compartment
{
public:
typedef std::vector<MyO bjectvector;
typedef std::vector<vec tor::iteratoriv ector;
typedef std::vector<vec tor::const_iter atorcivector;
>
bool operator < (const MyObject &inp) const;
/*
Rest of the definition here
*/
};
>
MyObject::ivect or viCmp;
/*
Other code here
Create sorted list of MyObject iterators
*/
MyObject::vecto r::iterator iC = vCmp.begin();
do
{
viCmp.push_back (iC);
}
while (++iC != vCmp.end());
>
std::sort(viCmp .begin(),viCmp. end(),&DRefComp are<MyObject::v ector::const_it erator>);
>
>
Naturally this relies on the operator < () exists for type T, so changes
to make it more general might be more suitable
>
JB

That would be using std::list::sort for std::list types as pointed out
earlier

JB

[Tim Frink]

Re: Sorting STL lists

On Sat, 14 Jul 2007 16:53:50 +0200, Kai-Uwe Bux wrote:

>
ptr_list.sort( &ptr_compare ); // !!!!!!!!!!!!!!! !!!!!
>
for ( PtrList::const_ iterator iter = ptr_list.begin( );
iter != ptr_list.end(); ++ iter ) {
std::cout << (*iter)->getIntValue( ) << '\n';
}
}
>

Many thanks.

Regards,
Tim