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:

Functions returning void

C++ truths discusses an interesting interview question:

"Can you write a return statement in a function that returns void?" The answer is "Yes! You can return void!"

The following is a simple program picked up from the same blog and modified showing a function returning void

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//This is a simple example of a function returning void
#include<iostream>

using namespace std;

static void foo (void)
{
  cout<<"foo() called"<<endl;
}
static void bar (void)
{
  cout<<"bar() called"<<endl;
  return foo(); // Note this return statement.
}
int main ()
{
  cout<<"main() called"<<endl;
  bar();
  return 0;
}

The output is as follows:

This feature is very useful in case of Templates. Lets write a simple program that uses Templates:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//This is a simple example of a Template returning void
#include<iostream>
//#include <typeinfo> - Some compilers may need this

using namespace std;

template <class T> T FOO (void)
{
  cout<<"T FOO() called with T = "<<typeid(T).name()<<endl;
  return T(); // Default construction
}

template <class T> T BAR (void)
{
  cout<<"T BAR() called with T = "<<typeid(T).name()<<endl;
  return FOO<T>(); // Syntactic consistency. Same for int, void and everything else.
}

int main (void)
{
  cout<<"main() called"<<endl;
  BAR<void>();
  BAR<int>();
  BAR<char>();
}

The output is as follows:

An example of using Typename with Templates

Typename is used with templates where the type is unknown. Use the keyword typename if you have a qualified name that refers to a type and depends on a template parameter. Only use the keyword typename in template declarations and definitions.

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//This program shows an how to use typename with templates
//Example from
//http://www.deitel.com/articles/cplusplus_tutorials/20060428/index.html
#include<iostream>

//using namespace std; //No need to use the whole namespace std
using std::cout;
using std::endl;

// function template printArray definition
template<typename T>
void printArray( const T *array, int count )
{
  for ( int i = 0; i < count; i++ )
  {
    cout << array[ i ] << " ";
  }
  cout << endl;
} // end function template printArray

int main()
{
  const int ACOUNT = 5; // size of array a
  const int BCOUNT = 7; // size of array b
  const int CCOUNT = 6; // size of array c

  int a[ ACOUNT ] = { 1, 2, 3, 4, 5 };
  double b[ BCOUNT ] = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
  char c[ CCOUNT ] = "HELLO"; // 6th position for null

  cout << "Array a contains:" << endl;
  // call integer function-template specialization
  printArray( a, ACOUNT );

  cout << "Array b contains:" << endl;
  // call double function-template specialization
  printArray( b, BCOUNT );

  cout << "Array c contains:" << endl;
  // call character function-template specialization
  printArray( c, CCOUNT );

  return 0;
}

Note in the above example you could have replaced 'typename' with 'class' and obtain the same results. Compare this with our basic template example discussed before.

The output of the program is as follows:

Example of C++ Templates

Program to show how templates work in a very simple way:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Note this program shows Template example

#include<iostream>

using namespace std;

template <class T> class Arith
{
public:
  T Add(T a, T b)
  {
    return a + b;
  }
};

template <class T, class U> class ArithNew
{
public:
  T Add(T a, U b)
  {
    return (T)(a + b); //the return type is casted otherwise a warning will be generated
  }
};

int main(void)
{
  Arith<int> ar1;
  int x = ar1.Add(3, 5);
  cout<<"x = "<<x<<endl;

  Arith<double> ar2;
  double y = ar2.Add(3.3, 1.2);
  cout<<"y = "<<y<<endl;

  //Arith<int> ar3;
  //double z = ar3.Add(3, 1.2);
  //cout<<"z = "<<z<<endl;
  //The above is possible but loss of data and no flexibility. Cant mix two types

  ArithNew<double, int> ar4;
  double xx = ar4.Add(5.5, 2);
  cout<<"xx = "<<xx<<endl;

  //reversing the same as above
  ArithNew<int, double> ar5;
  int yy = ar5.Add(2, 5.5); //works without warning because of return type being casted otherwise warning
  cout<<"yy = "<<yy<<endl;

  return 0;
}

boost::any

boost::any is a strong concept and a much better replacement to void* to hold any type of data. You can make heterogenous containers using it as well. Let us see how it works in a very simplified way. The idea is to have a template class that can wrap all types and a value associated with that type. Something like this:

template<typename T>
class HoldData
{
    T t;
};

And then having a base class from which this wrapper would derive, so the above becomes adding a constructor that needs the type to be stored in it to be copy constructible:

class BaseHolder
{
    public:
        virtual ~BaseHolder(){}
};

template<typename T>
class HoldData : public BaseHolder
{
    public:
        HoldData(const T& t_) : t(t_){}
    private:
        T t;
};

Now, you would have a class, name it Variant that will take inputs of all types and then has a pointer to this wrapper's base type. So, now you have (including above classes):

class BaseHolder
{
    public:
        virtual ~BaseHolder(){}
};

template<typename T>
class HoldData : public BaseHolder
{
    public:
        HoldData(const T& t_) : t(t_){}
    private:
        T t;
};

class Variant
{
    public:
        template<typename T>
        Variant(const T& t) : data(new HoldData<T>(t)){}
        ~Variant(){delete data;}
    private:
        BaseHolder* data;
};

You construct the corresponding type's wrapper objects and save their pointer into the another class that you call variant, that can hold and help retrieve any data type and does not lose the respective type information. That is actually what boost::any does. Take a look at the code here - boost::any code.

The documentation on it can be found here - boost::any documentation.

Operator overloading basics

It is quite true that operator overloading looks such a big deal for beginners. I had my problems with that as well when I started with C++ and kept ignoring it considering it to be a complex thingie. But I tell you it is not. For an initial introduction to it, you may find this Codeguru FAQ entry quite useful : C++ Operator: How to deal with operator overloading?

Hope you find it interesting and easy to follow.

Keep rocking! Cheers!

Functors with state - 3 (print contents of vector using std::copy)

I had discussed an issue with function objects containing state and the problems they lead to (especially for std::remove_if algorithm) because of copy creation of those due to argument passing by value. The way they should be passed around is not guranteed by the standards. Here is the starting point for that discussion - Functors with state - 1.

There can be multiple things that can be improved in that code. The first one that I will pick up is the way the function "PrintVector" is laid down.

[CODE]

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

There are problems with this code. It is not flexible enough to let you choose the stream where you want the output to be pushed. Secondly, it uses loops and that loop leads to a third problem and that is the repeated call to vector<T>::size() function.

When we have algorithms at our disposal and feel they can improve the code, we should use them. Here is a better way to write the PrintVector function:

[CODE]

#include<vector>
#include<iostream>
#include<algorithm>
#include<iterator>
#include<string>

template<typename T>
void PrintVector(std::ostream& ostr, const std::vector<T>& t, const std::string& delimiter){
        std::copy(t.begin(), t.end(), std::ostream_iterator<T>(ostr, delimiter));
}

A simple one liner!

Another way to better it could be making it independent of the container type. Currently it would work for std::vector only (as demanded as the second argument). We can use iterator inputs (forward iterators should suffice). Here:

[CODE]

#include<iostream>
#include<algorithm>
#include<iterator>
#include<string>

template<typename T, typename InputIterator>
void Print(std::ostream& ostr, InputIterator itbegin, InputIterator itend, const std::string& delimiter){
        std::copy(itbegin, itend, std::ostream_iterator<T>(ostr, delimiter));
}

Now, this Print template can be used to print contents of any sequence that supports input iterators i.e. std::vector, std::deque, std::list, std::string and even plain arrays. The output stream can be anything, a file or the console or anything deriving from std::ostream and similarly we have generalized the delimiter between two subsequent elements that previously was a tab to any string.

More, later! Have fun!!

(Next installment here - Functors with state - 4)

Quiz : function pointers as template arguments

Yesterday, I came across a piece of template code that took me a little by surprise (because I had not come across something like this before) but I was able to put my reasoning through. I will share the code first:

[CODE]

#include <iostream>

template<typename T>
void foo(const T&)
{
               std::cout << "const";
}

template<typename T>
void foo(T&)
{
               std::cout << "non-const";
}

void bar() { }

int main()
{
               foo(bar);
}

The question was - what would the program print? Will the argument "bar" resolve as a parameter to the first template having argument type "const F&" or to the second template having non-const argument type "F&"?

The easiest way to check for the resolution is to ask for explicit template instantiation of the "foo" function template. How? Here is how:

[CODE]

int main()
{
               typedef void (*f_ptr)(); //create a typedef for functions like bar
                                                               //taking no arguments and having return type as void.
               foo<const f_ptr>(bar); //1
               foo<f_ptr>(bar); //2
}

After that, just remove one of the "foo" templates. So, the code to check for compilation is this:

[CODE]
#include<iostream>

template<typename T>
void foo(T&)
{
               std::cout << "non-const";
}

void bar() { }

int main()
{
               typedef void (*f_ptr)(); //create a typedef for functions like bar
                                                               //taking no arguments and having return type as void.
               foo<const f_ptr>(bar); //1
               foo<f_ptr>(bar); //2
}


If you removed the second template, code compiles fine. But if you kept the second one and removed the first one, you will see that the compilation fails for mis-match in the argument type in statement "//2".

Problem solved. Isn't it? What does this tell about the argument "bar" ? It tells that it is a constant. And hence the call in the initial sample code would resolve to the template instance having the argument type declared const. It is in a way similar to any other type constants, for example 5, 100, 2000 are integral constants, they are literals. And when you declare something as say int i; here i is a variable that can be modified. but 5, 100, or 2000 cannot be. In our initial code, both the templates were capable of instantiating the right function for the argument. In both's presence, the argument match has to be exact and hence instantiation happens from the const one but in its absense the instantiation can happen even with the non-const one as the call can help the template to instantiate over type const f_ptr instead of just f_ptr (which is the case for the const one).

Functions pointers when being passed by taking the address of the function directly is a value of const function pointer type.