Interview Question on the Slicing Problem

Someone was talking about the Slicing Problem with classes in one of the companies we do projects for. As the name states, the Slicing problem arises when a part of the class is Sliced away. This will happen when derived class is assigned to the base class. Here is a simple example that is also been used for interviews:

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

using namespace std;

class Parent
{
public:
  virtual void func_a(void);
};

class Child : public Parent
{
public:
  void func_a(void);
};

void func_1(Parent p);
void func_2(Parent* p);
void func_3(Parent& p);


int main()
{
  //Using the Parent class
  Parent p;
  cout<<"\nParent Class"<<endl;
  func_1(p);
  func_2(&p);
  func_3(p);

  //Using the Child class
  Child c;
  cout<<"\n\nChild Class"<<endl;
  func_1(c);
  func_2(&c);
  func_3(c);

  //Using the Parent class that is initialised to class
  Parent p2 = c; //Note that in p2, additional info about c would be lost
  cout<<"\n\nParent p2 Class"<<endl;
  func_1(p2);
  func_2(&p2);
  func_3(p2);

  //Not possible to initialise directly from base to derived class. 
  //Child c2 = p2; - ERROR: cannot convert from 'Parent' to 'Child'
  //The way round it would be to have a constructor or overload operator = 

  return 0;
}

void Parent::func_a()
{
  cout<<"Parent::func_a()"<<endl;
}

void Child::func_a(void)
{
  cout<<"Child::func_a()"<<endl;
}

void func_1(Parent p) 
{ 
  cout<<"func_1 -> ";
  p.func_a(); 
} 

void func_2(Parent* p) 
{ 
  cout<<"func_2 -> ";
  p->func_a(); 
} 

void func_3(Parent& p) 
{ 
  cout<<"func_3 -> ";
  p.func_a(); 
} 

The output is as follows:

Printing Debug information through Macros

This example shows probably one of the most useful case for using Macro's. Since Macro's are expanded before the code is compiled, debug information like filename and line number is available in the macro to be used.

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

using namespace std;

#define PRINT_DEBUG_INFO \
  cout<<__DATE__<<" "<<__TIME__<<": "<<__FUNCTION__<<", "<<__FILE__<<", "<<__LINE__<<endl;
//Note that __TIMESTAMP__ can be used instead of __DATE__ and __TIME__

void func1(int* someNum)
{
  if(someNum)
  {
    //Perform normal operations here
    int someVar=0;
  }
  else
  {
    //Abnormal scenario
    PRINT_DEBUG_INFO;
  }
}

void func2(int *); //forward declaration of func2

int main()
{
  int *x = NULL;
  func1(x); //Creating exception scenario
  func2(x); //Creating exception scenario

  return 0;
}

void func2(int* someNum)
{
  try
  {
    //Normal case here
    if(someNum)
      *someNum = 100;
    else
      throw 0;
  }
  catch(...) //Abnormal case
  {
    PRINT_DEBUG_INFO;
  }
}

The output is as follows:
Please note that in the above example, the __DATE__ and __TIME_ functions return the compilation date and time, not the current date and time. More details here.

To get the current execution date and time, see this example.

C++ example of 'transform'

From the CPP Reference:
#include

1. output_iterator transform( input_iterator start, input_iterator end, output_iterator result, UnaryFunction f );
2. output_iterator transform( input_iterator start1, input_iterator end1, input_iterator2 start2, output_iterator result, BinaryFunction f );

The transform algorithm applies the function f to some range of elements, storing the result of each application of the function in result.

The first version of the function applies f to each element in [start,end) and assigns the first output of the function to result, the second output to (result+1), etc.

The second version of the transform works in a similar manner, except that it is given two ranges of elements and calls a binary function on a pair of elements.

Here is an example that is modified from C++ Reference:

//Program tested on Microsoft Visual Studio 2008 - Zahid Ghadialy
//Program to show how transform works in C++

#include<iostream>
#include<vector>
#include<algorithm> //for the transform() function

using namespace std;

int increase (int i) { return ++i; }
int sum (int i, int j) { return i+j; }

int main()
{
  int someNums[] = {10,20,30,40,50}; //Array of 5 values
  //Another way to initialise a vector using the iterator constructor
  vector<int> vectorOne (someNums, someNums + sizeof(someNums) / sizeof(int)); 
  vector<int> vectorTwo;
  vector<int>::iterator it;

  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;

  vectorTwo.resize(vectorOne.size()); //allocate space

  //OutputIterator transform ( InputIterator first1, InputIterator last1,
  //                           OutputIterator result, UnaryOperator op );
  std::transform(vectorOne.begin(), vectorOne.end(), vectorTwo.begin(), increase);

  cout<<"\nAfter transform with increase:"<<endl;
  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;
  cout<<"vectorTwo elements are : ";
  for(unsigned int i = 0; i < vectorTwo.size(); ++i)
    cout<<vectorTwo[i]<<" ";
  cout<<endl;

  //OutputIterator transform ( InputIterator1 first1, InputIterator1 last1,
  //                           InputIterator2 first2, OutputIterator result,
  //                           BinaryOperator binary_op );
  transform (vectorOne.begin(), vectorOne.end(), vectorTwo.begin(), vectorOne.begin(), sum);

  cout<<"\nAfter transform with sum:"<<endl;
  cout<<"vectorOne elements are : ";
  for(unsigned int i = 0; i < vectorOne.size(); ++i)
    cout<<vectorOne[i]<<" ";
  cout<<endl;
  cout<<"vectorTwo elements are : ";
  for(unsigned int i = 0; i < vectorTwo.size(); ++i)
    cout<<vectorTwo[i]<<" ";
  cout<<endl;

  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:

Comparing floating point numbers

Floating point comparisons can be a painful work to achieve. And always must one avoid laziness in doing equality comparisons using inbuilt operator== for floating point numbers.

There could be roundings involved and/or infinite decimal expansions that can lead to inaccurate representations or better say, losing of some precision off the number. Owing to that, even though you would expect a number to match a definite expansion that the calculation may have lead to, it may not.

An easy way to handle that is to choose a reasonable tolerance in the comparison. For example, we could choose a tolerance of 0.0000001 when comparing two doubles for equality such that the absolute value of their difference if less than this value then, you could consider them to be equal or better say, 'close enough' for most reasonable cases. This tolerance can, however, be insufficient if:

    1) The numbers are very large or if the numbers are very small in value for the tolerance to be able to compare to their difference.
    2) If there have been multiple arithematic operations performed that could lead to compounded incorrectness (owing to multiple roundings/loss of precision involved) in the result.

In C++, there is a value std::numeric_limits::epsilon() that is referred to sometimes as machine epsilon value/tolerance or machine accuracy. It gives the difference between 1 and the smallest value greater than 1 that is representable for data type for which the template's instantiated, which is double here. This helps us with the standardization of the tolerance value that we previously had chosen as 0.0000001. But doesn't help us with the limitations 1) and 2) pointed out above.

There could more factors than that mentioned in 2) that can cause the rounding error. Apart from arithematic operations, it could be type promotions or binary conversions that can cause more than epsilon() rounding error. So, combination of 2 arithematic operations could lead to more than 2*epsilon. I don't know how quantifiable that is, but by a safer choice of N (number of arithematic operations involved), we hope to be able to overcome the problem in most practical cases. :-)

For the short-coming mentioned in 1), we would need to bring the epsilon to the degree of large-ness or small-ness of the numbers involved. Considering this, you might have something like:

template<typename T>
bool fequal(T x, T y, int N)
{
    T diff = std::abs(x-y);
    T tolerance = N*std::numeric_limits::epsilon(); //caters to 2)
    return (diff <= tolerance*std::abs(x) && diff <= tolerance*std::abs(y)); //caters to 1)
}

where x and y are the input numbers being compared for near equality and N is the approximate number of rounding errors you are expecting.

References:

1) Trap Handlers, Sticky Bits, and Floating-point Comparisons
2) Floating-point comparison algorithms
3) numeric_limits::epsilon

Floating point numbers and NaN

NaN expands to 'not a number'. Various floating point operations can lead to this value. IEEE-754 is the most widely used floating point computation standards. It defines 5 possible exceptions that can occur during floating point arithematic:

    1) Invalid Operation: when an invalid operation is performed on a number, for example, taking square root of a negative value, taking log of 0 or a negative number, etc.
    2) Division by Zero: when a number is divided by zero
    3) Overflow: when the result is too large to be representable
    4) Underflow: when the result is too small to be representable
    5) Inexact: when the result is inexact meaning the number was rounded and caused discarding of any non-zero digits

The cases falling under invalid operation would result in a value of NaN as per the above mentioned standard. (I get -INF with gcc 3.4.4, but NaN for any negative number's logarithm). You would check for NaNs and Infinities resulting out of computations in order to determine the success and validity of the operation but that can lead to code that is cluttered with ifs and elses and can become almost un-readable. You can, however, do the checks at every logical chunk of the computation. However, NaNs and INFs can get lost mid-calculations. The standard dictates that an exceptional value NaN or INF should get propagated throughout the calculations so that the checks at the end of a computation could catch them but certain operations can lose them, for example:

    1) NaN operation with INF value would result in INF, as in NaN + INF = INF.
    2) INF can become 0, as in x/INF = 0

The way to catch these would be to check the sticky bits that are essentially the exception flags that are set on occurence of floating point exceptions anywhere during the calculation. But let's not get too carried away and leave it to the credibility of the programmers and users to be able to handle the various cases in the most sensible way. :-)

To conclude, here is a function that will help check if a value is a NaN or not, based on the fact that any comparison involving NaNs would result in 'false' result:

template<typename T>
bool myIsNaN(T value)
{
    return value != value;
}

C99 has a function isNaN() and TR1 for C++ has included the support for this function but just in case your compiler doesn't support it. Similarly, you have isinf() that will help catch both positive and negative infinities. If you are feeling too experimental, try your own version of isinf() using numeric limits. :-)

References:

1) Trap Handlers, Sticky Bits, and Floating-point Comparisons
2) What is this NaN thing?
3) C++ Numeric limits
4) Wikipedia - IEEE 754