Flexible sorting

This is a discussion on Flexible sorting within the C++ Programming forums, part of the General Programming Boards category; Hello all, I'm new to C++ but I do understand the basics of programming. I've recently started getting serious and ...

  1. #1
    Always learning
    Join Date
    Apr 2009
    Posts
    25

    Flexible sorting

    Hello all,

    I'm new to C++ but I do understand the basics of programming. I've recently started getting serious and intend to go "pro" with it.

    I made a template LinkedList that can accept any kind of data. For my assignment we have to make a base class called Vehicle, and two derived classes called Car and Truck. One of the things we have to do is to sort the lists in different ways, according to the user's input.

    My classmates are just as puzzled, if not more, so we're trying to figure this out (our assignments are always beyond what they teach us).

    I thought of two ways to do it, but they're not very "nice":
    - One way is to use a function as a parameter to the sorting of the list. Eg a compare_passengers(Vehicle &a, Vehicle &b) function that is passed on to the sort method of the LinkedList class.
    - The other way is to have a static member called compare_key that determines which member of the class the overloaded operator > will compare. Eg:
    Code:
    bool Vehicle::operator > (Vehicle &other)
    {
        switch (static_thingy)
        {
            case key_passengers:
                return this->passengers > other.passengers;
            case key_year:
                return this->year>other.year;
            //......etc
        }
    }
    (I didn't check the above code for syntax errors, so i I did something stupid it doesn't matter, this is just an example).

    I don't like either of my solutions. They are not nice in a programming way, or user friendly. What I'd like to have is something like this:
    Code:
    LinkedList<Vehicle> list;
    //....adding elements to the list...
    list.sort(Vehicle::get_passengers()) //sorts according to get_passengers()
    list.sort(Vehicle::year) //sorts according to year, which is an integer
    Or, maybe, you have a better suggestion.

    I'm sorry if this has been asked before, but I didn't even know what to search for besides "sorting" (which didn't give any good results).

    Thanks in advance!

    Edit: I forgot to mention that we are not allowed to use standard containers; we have to make our own.
    Last edited by Mr.Pointer; 04-13-2009 at 07:02 PM.

  2. #2
    Registered User
    Join Date
    Apr 2006
    Posts
    2,050
    The way the STL does it is have an optional "comparator", that is a function object that is used to compare two objects. For example std::max may look like this:

    Code:
    template <class T, class Compare>
        const T& max ( const T& a, const T& b, Compare comp ){
      return b(a,b);
    }
    The type of compare is either a function, or an object with an overloaded () operator. A function like max or min can be used to compare each element in a container.

    Often, the comparator std::less is used by default, which compares via the < operator.
    Last edited by King Mir; 04-13-2009 at 08:27 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  3. #3
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    I agree with King Mir - the comparison should be a function pointer or function object - that moves the decision as to how to sort to the applicaiton level, rather than the implementation of the class itself. Your car class shouldn't really care how it's sorted, but the application does.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    - One way is to use a function as a parameter to the sorting of the list. Eg a compare_passengers(Vehicle &a, Vehicle &b) function that is passed on to the sort method of the LinkedList class.
    This is a perfectly acceptable way.

    - The other way is to have a static member called compare_key that determines which member of the class the overloaded operator > will compare.
    This is rather ugly.
    (NB, STL uses operator< for comparisons.)

    I don't like either of my solutions. They are not nice in a programming way, or user friendly. What I'd like to have is something like this:
    For that kind of generality, as long as C++ doesn't have lambda functions, boost library has tools. It won't look very pretty but it is quite manageable if you get used to it:

    Code:
    #include <boost/bind.hpp>
    using namespace boost;
    
    ...
    LinkedList<Vehicle> list;
    //....adding elements to the list...
    list.sort(bind(&Vehicle::get_passengers, _1) < bind(&Vehicle::get_passengers, _2));
    list.sort(bind(&Vehicle::year, _1) < bind(&Vehicle::year, _2));
    For that to work, LinkedList<T>::sort has to accept a comparison function (object) as in the first way.
    Last edited by anon; 04-14-2009 at 03:56 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Naturally, the syntax you desire may be achieved too. You just have to provide overloads of sort that accept a pointer to member and member function.

    It may be convenient sometimes but it is probably not generic enough for STL style (allows to select member/member function to base sort on but not choose sorting order).

    Code:
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <vector>
    
    //some helpers, since not using boost and don't bother to implement sorting myself
    template <class T, class SubT>
    class compare_member_t
    {
        SubT T::*member_pointer;
    public:
        compare_member_t(SubT T::*mp): member_pointer(mp) {}
        bool operator()(const T& a, const T& b)
        {
            return (a.*member_pointer) < (b.*member_pointer);
        }
    };
    
    template <class T, class SubT>
    compare_member_t<T, SubT> compare_member(SubT T::*member_pointer)
    {
        return compare_member_t<T, SubT>(member_pointer);
    }
    
    template <class T, class SubT>
    class compare_member_function_t
    {
        SubT (T::*member_function)()const;
    public:
        compare_member_function_t(SubT (T::*mf)()const): member_function(mf) {}
        bool operator()(const T& a, const T& b)
        {
            return (a.*member_function)() < (b.*member_function)();
        }
    };
    
    template <class T, class SubT>
    compare_member_function_t<T, SubT> compare_member_function(SubT (T::*member_function)() const)
    {
        return compare_member_function_t<T, SubT>(member_function);
    }
    
    class Person
    {
    public:
        std::string name;
    private:
        int age;
    public:
        Person(const std::string& its_name, int its_age):
            name(its_name),
            age(its_age)
        {}
        int get_age() const { return age; }
    };
    
    void print(const Person& person)
    {
        std::cout << person.name << " (" << person.get_age() << ")\n";
    }
    
    template <class T>
    class MyContainer
    {
        std::vector<T> buffer;
    public:
        typedef typename std::vector<T>::iterator iterator;
        typedef typename std::vector<T>::const_iterator const_iterator;
        void push_back(const T& t) {
            buffer.push_back(t);
        }
        iterator begin() { return buffer.begin(); }
        iterator end() { return buffer.end(); }
        const_iterator begin() const { return buffer.begin(); }
        const_iterator end() const { return buffer.end(); }
    
        //there may be other overloads of sort
        template <class U>
        void sort(U T::*member)
        {
            std::sort(buffer.begin(), buffer.end(), compare_member(member));
        }
    
        template <class U>
        void sort(U (T::*member_function)() const)
        {
            std::sort(buffer.begin(), buffer.end(), compare_member_function(member_function));
        }
    };
    
    int main()
    {
        MyContainer<Person> persons;
        persons.push_back(Person("Joe", 42));
        persons.push_back(Person("Jack", 55));
        persons.push_back(Person("John", 33));
        persons.sort(&Person::name);
        std::cout << "Sorted by name:\n";
        std::for_each(persons.begin(), persons.end(), print);
        persons.sort(&Person::get_age);
        std::cout << "\nSorted by age:\n";
        std::for_each(persons.begin(), persons.end(), print);
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Always learning
    Join Date
    Apr 2009
    Posts
    25
    Thank you for your replies! For the sake of my assignment, I'll use the method you suggested, which is having a default comparing function but also the possibility to accept other comparing functions.

    an object with an overloaded () operator.
    That didn't even cross my mind ^^

    Anon's suggestion is currently beyond me, and way beyond the current level of my class; I'm still not familiar the concept of iterators and vectors, among other things. I will save the link to this thread and get back to it when I'm more experienced. But really, thanks for your time

    This is a great community and I'm sure I'll learn a lot from you guys.
    Last edited by Mr.Pointer; 04-14-2009 at 06:07 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 06-11-2009, 11:27 AM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21