Thread: 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.

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.

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

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

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);
}

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.