A generic sort program with 'functors' and 'templates'

Picked up this question from here and made a program out of it. It may be a good idea to quickly brush functors and templates if required.

The program sorts the input Vector provided regardless of the type.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Int
{
public:
  Int() {x_ = 0;}
  Int(const int &x) {x_ = x;}
  int getID (void) {return x_;}
  int x_;
};

class Str
{
public:
  Str() {x_ = "";}
  Str(const string &x) {x_ = x;}
  string getID (void) {return x_;}
  string x_;
};

template <typename Object> class Comparator {
  public:
    bool operator()(const Object &o1, const Object &o2) const 
    {
      return (const_cast<Object&>(o1).getID() < const_cast<Object&>(o2).getID());
    }

    bool operator()(const Object *o1, const Object *o2) const {
      return (o1->getID() < o2->getID());
    }
};

template <typename VecObject> void Display(VecObject v)
{
  VecObject::iterator it;
  for(it = v.begin(); it != v.end(); ++it)
  {
    cout<<it->getID()<<", ";
  }
  cout<<endl;
}

int main()
{
  vector<Int> objects1;
  objects1.push_back(Int(3));
  objects1.push_back(Int());
  objects1.push_back(Int(77));

  //print the output
  cout<<"objects1 before sort = ";
  Display(objects1);
  std::sort(objects1.begin(), objects1.end(), Comparator<Int> ());
  cout<<"objects1 after sort  = ";
  Display(objects1);

  std::vector<Str> objects2;
  objects2.push_back(Str("Hello Hello"));
  objects2.push_back(Str("apple?"));
  objects2.push_back(Str());
  objects2.push_back(Str("1 Jump"));

  //print the output
  cout<<"objects2 before sort = ";
  Display(objects2);
  std::sort(objects2.begin(), objects2.end(), Comparator<Str> ());
  cout<<"objects2 after sort  = ";
  Display(objects2);

  return 0;
}

The output is as follows:

Example of 'functors'

What are 'functors?'

Depending on what you prefer to read, there are many definitions and explanations of Functors.

From the function pointer tutorial:

Functors are functions with a state. In C++ you can realize them as a class with one or more private members to store the state and with an overloaded operator () to execute the function. Functors can encapsulate C and C++ function pointers employing the concepts templates and polymorphism. You can build up a list of pointers to member functions of arbitrary classes and call them all through the same interface without bothering about their class or the need of a pointer to an instance. All the functions just have got to have the same return-type and calling parameters. Sometimes functors are also known as closures. You can also use functors to implement callbacks.

From StackOverflow:

• A functor is pretty much just a class which defines the operator(). That makes it "look like" a function.
• Another advantage to a functor over a pointer to a function is that the call can be inlined in more cases.
• You can use boost::function, to create functors from functions and methods
  

Here is a simple example of functors that I have created using mishmash from various places:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to demonstrate the use of functors

#include<iostream>

using namespace std;

class someClass
{
public:
  someClass(int x) : someVariable(x) {}
  int operator()(int y) {return (someVariable + y);}
  int internalStateValue(){return someVariable;}

private:
  int someVariable;
};

int main()
{
  someClass class1(50);
  someClass class2(75);

  cout<<"Class1 state variable value is : "<<class1.internalStateValue()<<endl;
  cout<<"Class2 state variable value is : "<<class2.internalStateValue()<<endl;

  int test1 = class1(22);
  cout<<"Test 1 value is : "<< test1<<endl;
  int test2 = class2(22);
  cout<<"Test 2 value is : "<< test2<<endl;

  cout<<"Class1 final state variable value is : "<<class1.internalStateValue()<<endl;
  cout<<"Class2 final state variable value is : "<<class2.internalStateValue()<<endl;

  return 0;
}

The output is as follows:

Functors with state - 4 (alternative solution using stable_partition)

The is the fourth installment in this series - Functors with state - 1.

Here, what we shall try to do is meet the requirements with a different algorithm. This algorithm does not suffer from the problem that remove_if does as explained in here - Functors with state - 2. But can we be real sure that it is only associated with remove_if and not any of the other algorithms using state maintaining function objects? Well, lets leave that for now.

In this alternate solution, I shall exploit the std::stable_partition algorithm that will help us partition the vector contents based on a predicate test and give the iterator to the element at the partition point. Here is the code that shows how to achieve it.

[CODE]

#include<algorithm>
#include<vector>
#include<iostream>

template<typename T>
struct IsEvenIndex{
               private:
                               mutable/*static*/ typename std::vector<T>::size_type index;
               public:
                               bool operator()(const T& t) const{
                                               if (index%2==0){
                                                               ++index;
                                                               return true;
                                               }else{
                                                               ++index;
                                                               return false;
                                               }
                               }
};

//template<typename T>
//typename std::vector<T>::size_type IsEvenIndex<T>::index=0;

template<typename T>
void PrintVector(const std::vector<T>& t){
               std::cout << std::endl << "Printing vector contents" << std::endl;
               for(typename std::vector<T>::size_type i=0; i<t.size(); ++i){
                               std::cout << t[i] << '\t';
               }
               std::cout << std::endl << std::endl;
}

int main(){
               std::vector<int> myintVector;
               std::vector<int> myanotherintVector;
               for(int i=1; i<=10; ++i){
                       myintVector.push_back(i*10);
               }
               PrintVector(myintVector);
               //std::vector<int>::iterator itend = std::remove_if(myintVector.begin(), myintVector.end(), IsEvenIndex<int>(myotherintVector));
               std::vector<int>::iterator itend = std::stable_partition(myintVector.begin(), myintVector.end(), IsEvenIndex<int>());
               
               PrintVector(myintVector);
               myanotherintVector.assign(itend, myintVector.end());
               myintVector.erase(itend, myintVector.end());
               PrintVector(myintVector);
               PrintVector(myanotherintVector);
}

[OUTPUT]

Printing vector contents
10 20 30 40 50 60 70 80 90 100
Printing vector contents
10 30 50 70 90 20 40 60 80 100
Printing vector contents
10 30 50 70 90
Printing vector contents
20 40 60 80 100


Also, note here that we don't use a static state variable anymore. Just because of the fact that stable_partition does not suffer from the issue that remove_if suffers from due to the call to find_if, passing the predicate by value.

There is another way where we can improve our original code with the static state variable. To remove the static declaration what we do is change the predicate a little as follows:

[CODE]

template<typename T>
struct IsEvenIndex
{
        private:
                 mutable typename std::vector<T>::size_type index;
                 typename std::vector<T>::size_type & index_ref;
                 std::vector<T>& refVec;
        public:
                 bool operator()(const T& t) const
                 {
                          if ( 1 & index_ref++ ) // if it is odd, increment after statement
                          {
                                   return false;
                          }
                          else
                          {
                                   refVec.push_back( t );
                                   return true;
                          }
                 }

        explicit IsEvenIndex(std::vector<T>& vec)
        : refVec(vec), index(0), index_ref( index )
        {}
};

Testing is an exercise and dissecting the logic is what I shall leave for my blog readers and close the topic here with a few references:

1. Codeguru thread where I came across this problem
2. Article that suffices the reasoning
3. Herb Sutter - Extending the standard library