designing classes

[Hamrick]

I wrote this trying to understand templates, functors and inheritance. it works but I want to know if there's a better way. Is a base and derived class overkill for a sorting function? How cand I make it better?

/*
  sorting test

  Class based sorting
    by Kimberly Hamrick
*/
#include <algorithm> // for C+'s sort
#include <iostream>  // for C++ I/O
#include <stdlib.h>  // for random numbers

using namespace std;

namespace hamrick {
  template <typename T>
  class sort_base {
  public:
    virtual void operator()( T array[], const int size ) const = 0;
  };

  template <typename T>
  class bubble_sort: public sort_base<T> {
  public:
    virtual void operator()( T array[], const int size ) const;
  private:
    // save the array for bubble_up
    mutable T *_array;

    // bubble up each element of the array
    void bubble_up( int from, const int downto ) const;
  };

  template <typename T>
  void bubble_sort<T>::operator()( T array[], const int size ) const {
    // save the array
    _array = array;

    // bubble up each element of the array
    for ( int x = 0; x < size; ++x )
      bubble_up( size - 1, x );
  }

  template <typename T>
  void bubble_sort<T>::bubble_up( int from, const int downto ) const {
    // bubble up to the last sorted element
    while ( from > downto ) {
      if ( _array[from] < _array[from - 1] )
        swap( _array[from], _array[from - 1] );
      --from;
    }
  }
}

// Check that an array of T is sorted
template <typename T>
bool issorted( T array[], const int size ) {
  bool sorted = true;

  // it's sorted if the previous element is smaller
  // than the current element for all elements
  for ( int i = 1; i < size; i++ ) {
    if ( array[i - 1] > array[i] ) {
      sorted = false;
      break;
    }
  }

  return sorted;
}

template <int size>
void unit_test( const hamrick::sort_base<int>& sorter ) {
  int array[size];
  int copy[size];

  // create a random array
  for ( int i = 0; i < size; ++i )
    copy[i] = array[i] = rand();

  // make sure it's sorted
  cout<<"before sort -- "<< boolalpha << issorted( array, size ) <<endl;
  sorter( array, size );
  cout<<"after sort  -- "<< boolalpha << issorted( array, size ) <<endl<<endl;

  // make sure it's sorted the right way
  sort( copy, copy + size );

  for ( int i = 0; i < size; ++i ) {
    if ( array[i] != copy[i] ) {
      cout<<"bad sort!"<<endl;
      break;
    }
  }
}

int main() {
  const int size = 10;

  unit_test<size>( hamrick::bubble_sort<int>() );

  return 0;
}

[vijayan121]

it is fine if your idea is just test out your understanding of templates, functors and inheritance. however, functors (aka function objects) are usually not implemented as object oriented types for a variety of reasons.

template <typename T> struct sort_base
 {
    virtual void operator()( T array[], const int size ) const = 0;
 };
void foobar( int array[], int size, const sort_base<int>& ref,
                         const sort_base<int>* ptr )
{
   ref( array, size ) ; 
   ptr->operator() ( array, size ) ; 
   (*ptr)( array, size ) ;
}

a. overloaded operators look natural and enhances readability when used with values (or references). object oriented types are usually accessed through pointers; using overloded operators with pointers is awkward. so we do not normally find object oriented types with overloaded operators.
b. void operator()( T array[], const int size ) const has a hardcoded assumption that we are sorting a C style array; we can make it somewhat more flexible by writing <template typename C> void operator()( C& array, const int size ) const . this would allow us to also sort a vector<> etc.

<template typename ITERATOR> 
  void operator()( ITERATOR begin, ITERATOR end ) const

would be even more generally applicable.
however, template member functions cannot be virtual.
c. this does not mean that we can not use the sort functors polymorphically. instead of

template <int size>
    void unit_test( const hamrick::sort_base<int>& sorter )

we could write this

template <int size, typename SORT_FUNCTOR>
   void unit_test( const SORT_FUNCTOR& sorter )

which would also be polymorphic.
d. we might want to store a sort functor as a member of another class. function objects are usually small in size; using value semantics (keeping a copy) would be the most convinient way. for example,

template< typename SORTER > class needs_to_sort_now_and_then
{
  // ...
  SORTER sorter ; // value
  int m ; // value 
};

using a base class would need pointer or reference semantics; this may cause life-time management (and sometimes aliasing) issues to crop up.
e. you might want to substitute a pointer to a free function for a function object; this would not be possible if a base class is involved.

[thekashyap]

>> Is a base and derived class overkill for a sorting function?
Yes (because for all practical purpose you would want your sort function to have bare minimum overhead, e.g. virtual call in this case). But not if you're trying to learn templates, inheritance and function objects

>> How cand I make it better?
Only thing missing here is the use of having a base and derived class.
One possible enhancement you can do is add another sorting method to your set of classes (say Heap, Quick, Insertion). That's when one can see/use the advantage of having a base/derived class.

Just one other comment, in function unit_test, IMO you're misusing the template parameter. You can make it like this

void unit_test( const int size, const hamrick::sort_base<int>& sorter )

or this

template< typename T >
void unit_test( const int size, const hamrick::sort_base<T>& sorter )

[Hamrick]

for vijayan121:

using overloded operators with pointers is awkward. so we do not normally find object oriented types with overloaded operators.

How is it awkward? And if you use a reference instead is it still awkward?

however, template member functions cannot be virtual.

Why not? I think that would be useful.

for thekashyap:

because for all practical purpose you would want your sort function to have bare minimum overhead

Why? I know sort functions need to be fast, but isn't that the way you do the sort and not how you call the function that matters most?

Just one other comment, in function unit_test, IMO you're misusing the template parameter.

Why? That's the only way I can get a constant to make an array, right? Array sizes have to be done at compile time and templates or literal values are the only way to do that.

[vijayan121]

How is it awkward? And if you use a reference instead is it still awkward?

void foobar( int array[], int size, const sort_base<int>& ref,
                         const sort_base<int>* ptr )
{
   ref( array, size ) ; // reference, not awkward
   ptr->operator() ( array, size ) ; // pointer, awkward
   (*ptr)( array, size ) ; // pointer, still awkward
 }

by awkword, i mean a. impairs rather than enhances readability b. is also not an elegant construct to write.

Why not? I think that would be useful.

this again requires a long answer (sigh)
let us say that in translation unit a.cpp, we have

struct base_class 
{
  template<typename T> virtual void template_member( const T& v ) const = 0;
};

and we compile this and put the resultant object file into a library.
i use this library and in my code (say my.cpp) write

struct my_class : A 
{
  template< typename T > virtual void template_member( const T& v ) const
      { /* what ever */ }
};
void use_base_class( base_class* pbc ) ;
void my_fun()
{
  int i = 23 ;
  string str = "this is going to be difficult" ;
  my_class* mc = new my_class ;
  mc.template_member(i) ;
  mc.template_member(str) ;
  mc.template_member(cout) ;
  mc.template_member(my_fun) ;
  use_base_class( mc ) ;
}

class my_class has now four(!) virtual functions my_class::template_member<int>, my_class::template_member<string> etc.
and i now define use_base_class this way

void use_base_class( base_class* pbc )
{
  int i = 23 ;
  string str = "this is going to be difficult" ;
  my_class* mc = new my_class ;
  pbc->template_member(i) ;
  pbc->template_member(str) ;
  pbc->template_member(cout) ;
  pbc->template_member(my_fun) ;
}

we would expect calls to the virtual template_members to be polymorphic, but these were never instantiated in the base_class and were therefore not present in the layout of base_class::vtable (http://en.wikipedia.org/wiki/Virtual_function_table ) if this is to work,
a. the base class would need to be recompiled everytime any derived class instantiated template_member<T> with a T which was till now not instantiated. any new (or modified) derived class will cause recompilation of the base_class (and every other derived class)! since classes in different translation units may inherit from one another, the complexity would become unmanageable in practice.
b. the C++ standard does not talk about dynamically loaded or shared libraries (http://en.wikipedia.org/wiki/Library_(computer_science)#Dynamic_loading ). but all modern platforms support them eg. dlls in windows, shared objects in BSD(unix). and allowing template virtual functions would require recompilation as part of dynamic loading! and any program can break any other program if they share libraries.
the very idea of virtual template member functions leads to insurmountable problems; it is simply too far outside the current linkage model employed on modern platforms. and therefore, is unworkable in a language that is designed to run on real machines and co-exist harmoniously with machines/operating systems/other languages/etc. which are present in the real world.

[thekashyap]

for thekashyap:
Why? I know sort functions need to be fast, but isn't that the way you do the sort and not how you call the function that matters most?

Now as Vijayan has enlightened us, it's not possible to have template+virtual. So I'll answer assuming the sort function is a non-template virtual function.
You are right in saying the sort algo itself is most important from performance POV but that does not mean that I provide a (going a bit extreme for example) JNI java implementation for my C++ users or vice versa. In which case the overhead of calling the function is much more visible/appreciable. Similarly although the overhead due to virtual function call is (comparatively) lower it does not mean we should do it that way.

for thekashyap:
Why? That's the only way I can get a constant to make an array, right? Array sizes have to be done at compile time and templates or literal values are the only way to do that.

Well, template parameter (IMO) should be used for template type and not the way you used it. Particularly given that there are better options available (like I gave examples).