Sorting STL lists

Discussion in 'C++' started by Tim Frink, Jul 14, 2007.

  1. Tim Frink

    Tim Frink Guest

    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 "getIntValue()" ... and
    the last obviously with the largest.

    Could you give me some hints how to do that?

    Regards,
    Tim
    Tim Frink, Jul 14, 2007
    #1
    1. Advertising

  2. Tim Frink

    Kai-Uwe Bux Guest

    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 "getIntValue()" ... 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_back( new Object ( 4 ) );
    ptr_list.push_back( new Object ( 3 ) );
    ptr_list.push_back( new Object ( 1 ) );
    ptr_list.push_back( new Object ( 7 ) );
    ptr_list.push_back( new Object ( 4 ) );
    ptr_list.push_back( 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, Jul 14, 2007
    #2
    1. Advertising

  3. 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 "getIntValue()" ... 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
    =?UTF-8?B?RXJpayBXaWtzdHLDtm0=?=, Jul 14, 2007
    #3
  4. * 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 "getIntValue()" ... and
    > the last obviously with the largest.
    >
    > Could you give me some hints how to do that?


    In general: write a comparision function, use std::list::sort.

    --
    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, Jul 14, 2007
    #4
  5. * Erik Wikström:
    > 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 "getIntValue()" ... 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();
    > }


    Yes.


    > and then use
    >
    > std::sort(list.begin(), list.end(), cmp);


    No, std::sort is not guaranteed to forward to std::list::sort.

    You need to use std::list::sort.

    --
    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, Jul 14, 2007
    #5
  6. Tim Frink

    Kai-Uwe Bux Guest

    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 "getIntValue()" ... 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
    Kai-Uwe Bux, Jul 14, 2007
    #6
  7. Tim Frink

    bnonaj Guest

    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 "getIntValue()" ... 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<MyObject> vector;
    typedef std::vector<vector::iterator> ivector;
    typedef std::vector<vector::const_iterator> civector;

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

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

    std::sort(viCmp.begin(),viCmp.end(),&DRefCompare<MyObject::vector::const_iterator>);

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

    JB
    bnonaj, Jul 14, 2007
    #7
  8. Tim Frink

    bnonaj Guest

    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 "getIntValue()" ... 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<MyObject> vector;
    > typedef std::vector<vector::iterator> ivector;
    > typedef std::vector<vector::const_iterator> civector;
    >
    > bool operator < (const MyObject &inp) const;
    > /*
    > Rest of the definition here
    > */
    > };
    >
    > MyObject::ivector viCmp;
    > /*
    > Other code here
    > Create sorted list of MyObject iterators
    > */
    > MyObject::vector::iterator iC = vCmp.begin();
    > do
    > {
    > viCmp.push_back(iC);
    > }
    > while (++iC != vCmp.end());
    >
    > std::sort(viCmp.begin(),viCmp.end(),&DRefCompare<MyObject::vector::const_iterator>);
    >
    >
    > 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
    bnonaj, Jul 14, 2007
    #8
  9. Tim Frink

    Tim Frink Guest

    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
    Tim Frink, Jul 16, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. JustSomeGuy

    Sorting lists of lists...

    JustSomeGuy, Jun 17, 2004, in forum: C++
    Replies:
    0
    Views:
    305
    JustSomeGuy
    Jun 17, 2004
  2. Jon Slaughter

    lists of lists

    Jon Slaughter, Dec 13, 2004, in forum: C++
    Replies:
    4
    Views:
    404
    Buster
    Dec 13, 2004
  3. Charlotte Henkle

    Counter for items in lists in lists?

    Charlotte Henkle, Sep 25, 2004, in forum: Python
    Replies:
    8
    Views:
    388
    Charlotte Henkle
    Sep 26, 2004
  4. =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==

    List of lists of lists of lists...

    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==, May 8, 2006, in forum: Python
    Replies:
    5
    Views:
    384
    =?UTF-8?B?w4FuZ2VsIEd1dGnDqXJyZXogUm9kcsOtZ3Vleg==
    May 15, 2006
  5. Chris Weisiger

    Help with sorting lists of lists

    Chris Weisiger, Oct 14, 2004, in forum: Perl Misc
    Replies:
    7
    Views:
    118
    Tad McClellan
    Oct 14, 2004
Loading...

Share This Page