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

  2. Tim Frink

    Kai-Uwe Bux Guest


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

  3. Tim Frink

    Guest Guest

    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);
     
    Guest, Jul 14, 2007
    #3
  4. * Tim Frink:
    In general: write a comparision function, use std::list::sort.
     
    Alf P. Steinbach, Jul 14, 2007
    #4
  5. * Erik Wikström:
    No, std::sort is not guaranteed to forward to std::list::sort.

    You need to use std::list::sort.
     
    Alf P. Steinbach, Jul 14, 2007
    #5
  6. Tim Frink

    Kai-Uwe Bux Guest

    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

    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

    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

    Many thanks.

    Regards,
    Tim
     
    Tim Frink, Jul 16, 2007
    #9
    1. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.