stable_sort() & predicate routines -- need help thinking at higher level of abstraction

I should add that I've got this down to a one-line macro that generates two compare routines per invocation but thats cheating ;)

Objects being compared need to have a friend operator< overload defined to make them less than comparable - see http://www.sgi.com/tech/stl/LessThanComparable.html. Then you can use stable_sort without the comparison function/functor.

e.g.
--------8<--------
class Foo {
//....
public:
        friend bool operator<(const Foo& left,const Foo& right) {
                return left.whatever_field < right.whatever_field;
        }
};
--------8<--------

Its not that I need help with "is this Foo less than that Foo".  What I need help with is the quesiton "Is this part of Foo less than that part of Foo".

As in your example's use of "whatever_field" ... I have LOTS of whatever_field that need to be compared.

If I understand your question correctly, which is by no means certain, here is how you can do it.

Perhaps first I should restate the problem as I understand it.  You have a collection of objects of some class, say Foo.  You want to be able to sort the collection using various members of Foo as the key, only one key at a time, using stable_sort.  You have found you can do this by having a comparison function for each member by which the collection might be sorted.  There are more members than types of members, so you would like to simplify the code by having only one function per type, rather than one function per member.

You can do this with the magic of function objects and member pointers.  You store a member pointer in the function object to tell it which member to test, and you give the function object an operator() function so it can impersonate a binary predicate.

Here's a simple example.

class Emily
{
public:
      int Fred;
      int Ginger;
};

class EmilyFunction
{
public:
      // The constructor takes pointer-to-int-member parameter and saves it.
      EmilyFunction(int Emily::* memberPointer)
            :      ptr(memberPointer) {}

      // The operator() member function allows an EmilyFunction object to be passed
      // to stable_sort as a binary predicate.
      bool operator() (const Emily& lhs, const Emily& rhs)
      {
            //  Compare the members specified by the stored member pointer.
            return lhs.*ptr < rhs.*ptr;
      }

private:
      int Emily::* ptr;
};

      // Define different EmilyFunction objects to sort on different fields.
      EmilyFunction compareFred(&Emily::Fred);
      EmilyFunction compareGinger(&Emily::Ginger);

      vector<Emily> vec;

      stable_sort(vec.begin(), vec.end(), compareFred);

      stable_sort(vec.begin(), vec.end(), compareGinger);

If the types of the members to be compared have < operators defined, you could make EmilyFunction a template so it could work with multiple types.

Also, rather than have separate objects for ascending and descending sorts, you could just tell a function object which way to sort and have it remember that, before you pass the object to stable_sort.

--efn

You have restated my question perfectly.  Now to make it closer to what I'm trying to accomplish:

* take Emily and give it ten different members of various data types
* build a vector of Emily's
* take as input a column # (given that each member has its own column)
* sort based on the column #, alternating directions for each sort of a specific column

Your comment is so hip-looking & I definitely don't understand it (yet).  Could I actually store the EmilyFunction pointers in a map of <int, EmilyFunction> and then do:

stable_sort(vec.begin(), vec.end(), mapOfEmilyFunctions[column_number]); ???

I don't even care if I need two maps (one for ascending, one for descending)...

If you have an actual working example of this I'll boost the points to 500.  Let me know.  In any event, I need to stare at this for quite some time.

Cool stuff.

... Or you can make the functor a friend and pass its constructor something corresponding to column name and forward/reverse and use the operator to sort according to those variables.

e.g.
--------8<--------
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

class Person
{
private:
        std::string firstname;
        std::string secondname;
        int age;
        friend class PersonSelectFunctor;
        template<typename C> friend std::basic_ostream<C>& operator<<(std::basic_ostream<C>& os,const class Person& person) {
                return os << person.firstname << ' ' << person.secondname << " (" << person.age << ')';
        }
public:
        Person(const std::string& firstname,const std::string& secondname,int age) : firstname(firstname),secondname(secondname),age(age) {}
};

class PersonSelectFunctor
{
public:
        enum Selector {firstname,secondname,age};
private:
        Selector selector;
        bool reverse;
public:
        PersonSelectFunctor(Selector selector = secondname,bool reverse = false) : selector(selector),reverse(reverse) {}
        bool operator() (const Person& lhs,const Person& rhs) {
                switch (selector) {

                case age:
                        if (reverse)
                                return lhs.age > rhs.age;
                        else
                                return lhs.age < rhs.age;

                case firstname:
                        if (reverse)
                                return lhs.firstname > rhs.firstname;
                        else
                                return lhs.firstname < rhs.firstname;

                case secondname:
                default:
                        if (reverse)
                                return lhs.secondname > rhs.secondname;
                        else
                                return lhs.secondname < rhs.secondname;
                }
        }
};

int main()
{
        std::vector<Person> v;
        v.push_back(Person("Charlie","Zed",45));
        v.push_back(Person("Abie","Zed",102));
        v.push_back(Person("Bertie","Zed",45));

        std::cout << "\nPersons unsorted:\n";
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on secondname:\n";
        stable_sort(v.begin(),v.end(),PersonSelectFunctor(PersonSelectFunctor::secondname,false));
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on age:\n";
        stable_sort(v.begin(),v.end(),PersonSelectFunctor(PersonSelectFunctor::age,false));
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on firstname:\n";
        stable_sort(v.begin(),v.end(),PersonSelectFunctor(PersonSelectFunctor::firstname,false));
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on age:\n";
        stable_sort(v.begin(),v.end(),PersonSelectFunctor(PersonSelectFunctor::age,false));
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons reverse-sorted on firstname:\n";
        stable_sort(v.begin(),v.end(),PersonSelectFunctor(PersonSelectFunctor::firstname,true));
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));
}
--------8<--------

If the friend functor looks good to you, you should ask yourself what advantages it has over adding the less than add criteria to static variables in your class and then defining a less than operator which depends on those static variables.

i.e.
--------8<--------
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

class Person
{
private:
        std::string firstname;
        std::string secondname;
        int age;
        friend class PersonSelectFunctor;
        template<typename C> friend std::basic_ostream<C>& operator<<(std::basic_ostream<C>& os,const class Person& person) {
                return os << person.firstname << ' ' << person.secondname << " (" << person.age << ')';
        }
public:
        Person(const std::string& firstname,const std::string& secondname,int age) : firstname(firstname),secondname(secondname),age(age) {}
        enum Selector {Firstname,Secondname,Age};
private:
        static Selector selector;
        static bool reverse;
public:
        static void set_sorting(Selector selector = Secondname,bool reverse = false) {
                Person::selector = selector;
                Person::reverse = reverse;
        }
        friend bool operator<(const Person& lhs,const Person& rhs) {
                switch (Person::selector) {

                case Age:
                        if (reverse)
                                return lhs.age > rhs.age;
                        else
                                return lhs.age < rhs.age;

                case Person::Firstname:
                        if (reverse)
                                return lhs.firstname > rhs.firstname;
                        else
                                return lhs.firstname < rhs.firstname;

                case Secondname:
                default:
                        if (reverse)
                                return lhs.secondname > rhs.secondname;
                        else
                                return lhs.secondname < rhs.secondname;
                }
        }
};

Person::Selector Person::selector = Person::Secondname;
bool Person::reverse = false;

int main()
{
        std::vector<Person> v;
        v.push_back(Person("Charlie","Zed",45));
        v.push_back(Person("Abie","Zed",102));
        v.push_back(Person("Bertie","Zed",45));

        std::cout << "\nPersons unsorted:\n";
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on secondname:\n";
        Person::set_sorting(Person::Secondname,false);
        stable_sort(v.begin(),v.end());
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on age:\n";
        Person::set_sorting(Person::Age,false);
        stable_sort(v.begin(),v.end());
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on firstname:\n";
        Person::set_sorting(Person::Firstname,false);
        stable_sort(v.begin(),v.end());
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons sorted on age:\n";
        Person::set_sorting(Person::Age,false);
        stable_sort(v.begin(),v.end());
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));

        std::cout << "\nPersons reverse-sorted on firstname:\n";
        Person::set_sorting(Person::Firstname,true);
        stable_sort(v.begin(),v.end());
        copy(v.begin(),v.end(),std::ostream_iterator<Person>(std::cout,"\n"));
}
--------8<--------

You set the "less than compare" variables before doing each stable_sort and then use the two-parameter stable_sort without the function pointer / functor.

It isn't thread-safe taking the static variables approach, but I find it tidier than the functor. All said... functors are fun... and I hate to be a damp squib :-)

Nice one, efn :-)

I like the fact that the comparison classes are allowed to be ignorant about the class being compared. You could indeed go one stage further, by replacing EmilyComparison, EmilyComparisonBase and EmilyComparer with generic equivalents Comparison<>, ComparisonBase<> and Comparer<>, put the templates into a utility header file and then use the same approach for any class with public members which are less than comparable.

i.e. (if you'll forgive the hack of your example code)...
--------8<--------
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

//----------------------------------------------------------------
//     The class of the objects to be sorted.
class Emily
{
public:
     Emily(int f, int g, float h)
          :     Fred(f),
               Ginger(g),
               Hugo(h)
     {}

     int Fred;
     int Ginger;
     float Hugo;
};

//----------------------------------------------------------------
//     Interface for all function classes that compare Emilys.
template<class C> class ComparisonBase
{
public:
     virtual bool operator() (const C& lhs, const C& rhs) = 0;
};

//----------------------------------------------------------------
//     Template that can compare two Emilys by a specified member.
//     The type of the member must have operator < defined.
template <class C,class T> class Comparison : public ComparisonBase<C>
{
public:
     Comparison(T C::* memberPointer)
          :     ptr(memberPointer)
     {}

     bool operator() (const C& lhs, const C& rhs)
     {
          return lhs.*ptr < rhs.*ptr;
     }

private:
     T C::* ptr;
};

//----------------------------------------------------------------
//     Adapter function class that has an operator() so stable_sort
//     can use it, but calls an EmilyComparisonBase-derived object to
//     do the real work.
template<class C> class Comparer
{
public:
     //     Save the pointer to the object that will do the comparisons.
     Comparer(ComparisonBase<C>* cmp)
          : comparer(cmp)
     {}

     bool operator() (const C& lhs, const C& rhs)
     {
          //     Let *comparer do the comparison and return its result.
          return (*comparer)(lhs, rhs);
     }

     ComparisonBase<C>* comparer;
};

//----------------------------------------------------------------
//     Function to show a vector of Emilys for testing.
void report(const char* name, const vector<Emily>& vec)
{
     cout << "By " << name << ":\n";

     for (int n = 0; n < vec.size(); ++n)
     {
          cout << vec[n].Fred
               << "  " 
               << vec[n].Ginger
               << "  " 
               << vec[n].Hugo
               << '\n';
     }
}

//----------------------------------------------------------------
int main(int argc, char* argv[])
{
     vector<Emily> vec;

     //     Set up some test data.
     vec.push_back(Emily(0, 9, 0));
     vec.push_back(Emily(1, 8, 9));
     vec.push_back(Emily(2, 7, 3));
     vec.push_back(Emily(3, 6, 6));

     vector<Comparer<Emily> > funcvec;

     //     Fill the vector of function objects with comparers for the
     //     various fields.
     funcvec.push_back(Comparer<Emily>(new Comparison<Emily,int>(&Emily::Fred)));
     funcvec.push_back(Comparer<Emily>(new Comparison<Emily,int>(&Emily::Ginger)));
     funcvec.push_back(Comparer<Emily>(new Comparison<Emily,float>(&Emily::Hugo)));

     //     Test.
     stable_sort(vec.begin(), vec.end(), funcvec[0]);

     report("Fred", vec);

     stable_sort(vec.begin(), vec.end(), funcvec[1]);

     report("Ginger", vec);

     stable_sort(vec.begin(), vec.end(), funcvec[2]);

     report("Hugo", vec);

     //     Clean up the dynamically allocated function objects.
     for (int n = 0; n < funcvec.size(); ++n)
     {
          delete funcvec[n].comparer;
     }

     getchar();

     return 0;
}
--------8<--------

Yep!

With all this wizardry, _Scotch_ is hardly going to have any code left.  :^)

--efn

You could save the overhead of constructing a comp object for each comparison:

     template<class T,class MT,class comp = std::less<MT> > class member_comp
     {
          MT T::* pm;
          comp comparer;
     public:
          member_comp(MT T::* pm) : pm(pm) {};
          bool operator() (const T& lhs,const T& rhs) {
               return comparer(lhs.*pm,rhs.*pm);
          }
     };

Not that it makes much difference when comp is std::less.

I'm sure _Scotch_'s users will be thrilled to have their lists sorted in 45 milliseconds instead of having to sit around waiting for 50 milliseconds.  :-)

--efn

Those 5 millisecs could be valuably spent in meetings discussing much more important things like brand etc. ;-)

holy smokes ... I have 500 points to spend.  You guys tell me who gets what points.  I'm not qualified to judge the two approaches or the amount of effort you have into this.  Its way over my head and going to take awhile to absorb.  

It's not really two approaches.  rstaveley presented a couple of solutions that didn't address the goal of avoiding writing code per field.  I presented a design that would have a class per sort key type, but you couldn't keep objects of classes for different sort key types in a vector or array.  So I came up with a more elaborate solution that allowed you to have an array of objects that could sort by different key types.  Finally, rstaveley suggested some changes to make my last design more general and improve its performance.  Any of the last three designs should work for you.

Modesty restrains me from claiming more than half the points.  I say, if in doubt, split them down the middle.  And don't worry about the amount of effort.  For me, at least, this was a fun question, and I suspect it was for my esteemed colleague as well.

--efn

PAQ the question when you've digested the content. No hurry. No worries about points. I enjoyed the exchange too.

PAQ the question when you've digested the content. No hurry. No worries about points. I enjoyed the exchange too.

Bump in points

I thank you both for the efforts.  Now where did I leave my stroustrup... I think I'm going to need it.