Sorting a list

Discussion in 'C++' started by SKumar, Feb 7, 2006.

  1. SKumar

    SKumar Guest

    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#
     
    SKumar, Feb 7, 2006
    #1
    1. Advertising

  2. SKumar

    Guest

    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.
     
    , Feb 7, 2006
    #2
    1. Advertising

  3. SKumar

    persenaama Guest

    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);
     
    persenaama, Feb 7, 2006
    #3
  4. SKumar

    Daniel T. Guest

    In article <>,
    "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;
    > };
    >
    > 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.
     
    Daniel T., Feb 7, 2006
    #4
  5. SKumar

    persenaama Guest

    Ooops, I goofed: returns bool, vector doesn't have *member* sort .. :)
    Thanks!
     
    persenaama, Feb 7, 2006
    #5
  6. 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:> <http://www.dietmar-kuehl.de/>
    <http://www.eai-systems.com> - Efficient Artificial Intelligence
     
    Dietmar Kuehl, Feb 8, 2006
    #6
    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. james_027

    sorting a list of list

    james_027, Nov 21, 2007, in forum: Python
    Replies:
    2
    Views:
    243
    Matt Nordhoff
    Nov 21, 2007
  2. Santiago  Romero
    Replies:
    10
    Views:
    530
    Peter Otten
    Jan 21, 2008
  3. Replies:
    2
    Views:
    1,441
    James Kanze
    Jul 6, 2010
  4. Jason
    Replies:
    0
    Views:
    390
    Jason
    Oct 4, 2006
  5. Tom Kirchner

    sorting by multiple criterias (sub-sorting)

    Tom Kirchner, Oct 11, 2003, in forum: Perl Misc
    Replies:
    3
    Views:
    476
    Michael Budash
    Oct 11, 2003
Loading...

Share This Page