Simulating Polymorphic Operators in C++

Michael presents three different techniques for making operators polymorphic.


July 02, 2007
URL:http://www.drdobbs.com/cpp/simulating-polymorphic-operators-in-c/200001978

Michael is an Assistant Professor of Computer Science at Augusta State University. He can be contacted at [email protected].


In C++, polymorphism lets a variable refer to objects of different data types. The only catch is that the different data types must be members of the same inheritance hierarchy and they must be lower in the hierarchy than the variable's data type. The cool part is this ability lets the same instruction behave differently, based on the actual object's data type instead of the variable's data type.

Consider the hierarchy of the UML class diagram in Figure 1. Here, I have derived the Manager and Salesperson classes from the Employee class. This lets me use an Employee pointer to point to an Employee, Manager, or Salesperson object.

[Click image to view at full size]

Figure 1: A class hierarchy.

The following code is an attempt at polymorphism:

Employee* pEmp = new Manager;
cout << *pEmp << endl;

However, this attempt fails since the code does not invoke the Manager's insertion operator (<<) as I intended—it invokes the Employee's insertion operator. This happens because the indirection operation (*) is performed first, so *pEmp returns the data type of the pointer. In this case, because pEmp is an Employee pointer, the *pEmp operation returns the Employee data type in spite of pointing to a Manager object. After *pEmp is done, the function call is matched using the Employee data type. Consequently, the Employee's insertion function is matched and not the Manager's function as intended.

In C++, polymorphism normally requires virtual methods. Because only methods can be inherited, many programmers think the insertion (<<) and extraction (>>) operators cannot display polymorphic behavior because these operators are implemented as nonmember friend functions. However, there are several ways of making these operators polymorphic. In this article, I compare and contrast three different techniques.

Version 1: Auxiliary Methods

The first and simplest version accomplishes the polymorphic behavior by adding extra virtual methods to each class. While the operators are nonmember functions, these new items are methods and can be polymorphic. So my insertion operator calls a polymorphic virtual method from the class and I let the compiler do the heavy lifting. Compilers typically build a table of function pointers called a "virtual function table" (vtable) to help resolve the call to a virtual method. Each class with a virtual method has memory allocated for a vtable. In addition, every object or instance of a class with virtual methods has a pointer to the vtable. Therefore, the space required for this version is the memory for the class's vtable plus memory for a pointer in each and every object. Listing One presents this version of the Employee example.


class Employee 
{
public:
  friend ostream& operator<<(ostream& os, const Employee & aEmployee);
  virtual ostream& print(ostream& os) const;
};
class Manager : public Employee
{
public:
  friend ostream& operator<<(ostream& os, const Manager & aManager);
  virtual ostream& print(ostream& os) const;
};
ostream& Employee::print(ostream& os) const
{
// code to print the Employee class
    return os;
}
ostream& operator<<(ostream& os, const Employee & aEmployee)
{
    return aEmployee.print(os);
}
ostream& Manager::print(ostream& os) const
{
    Employee::print(os);
    // code to print the Manager class
    return os;
}
ostream& operator<<(ostream& os, const 
        Manager & aManager)
{
    return aManager.print(os);
}
Listing One

Version 2: The dynamic_cast Operator

My next version removes the extra virtual methods of version 1 to reduce the memory requirements of the program while keeping the performance levels the same. Keep in mind that my version 1 needed an extra pointer for each and every object. In version 2, I simulate the desired polymorphism by using the C++ Runtime_type_information (RTTI) feature combined with the dynamic_cast operator within the parent's insertion function. The dynamic_cast operator converts a pointer or reference from one object type to another object type when both types are within the same class hierarchy (see C++ for Game Programmers, by Noel Llopis; Charles River Media, 2003). This is the only kind of cast operation in C++ that's checked at runtime. The other type conversions either don't check, or check at compile time. If the runtime conversion between pointer types is not valid, the dynamic_cast operation returns a null pointer (see The C++ Standard Library: A Tutorial and Reference, by Nicolia M. Josuttis; Addison-Wesley, 1999).

My strategy for version 2 is to use the dynamic_cast operator in a parent's function to find out if an object passed to this parent function is actually a child object. In other words, if I'm passed a child object, I process the parent's portion of the object, then I call the child's function to process the child's portion. This processing order mimics the first, polymorphic version of the code. Listing Two is the Employee example for version 2.

ostream& operator<<(ostream& os, const Employee& a Employee)
{
// code to print the Employee class
    if (dynamic_cast<const Manager*>(&a Employee) != NULL)
        os << *(dynamic_cast<const Manager*>(&a Employee));
    return os;
}
Listing Two

Getting back to my initial attempt to use the insertion operator (cout << *pEmp), the Employee class is the parent while the Manager is considered a child. In the Employee's insertion (<<) function, I always print the Employee's private variables. Afterwards, I use the dynamic_cast operator to see if I was passed a Manager object. If so, I then call the Manager's insertion function to handle printing the Manager's private variables. Thus, I've printed the Manager's portion using the Manager's function even though the Employee's function is called. This is how the simulated polymorphism is accomplished.

However, I found that using the dynamic_cast operator in this manner leads to a problem. The error shows up in a nonpolymorphic use of the insertion functions. For example:

Manager m1;
cout << manager1;

Unlike the first example using the << function, this time, the Manager's insertion function is correctly called and passed a Manager object. When inside the Manager's function, I have to deal with the Employee portion of the object. This is typically done by calling the Employee's function from within the Manager's function:

ostream& operator<<(ostream& 
   os, const Manager& aManager)
{
   os << static_cast<const 
   Employee&>(aManager);
// code to print the Manager class
   return os;
}

Unfortunately, this call to the Manager's function leads to an infinite recursive loop between the child and parent functions because they are now calling each other. To solve this problem, I introduced a Boolean flag. This flag is a static function variable because its value must be retained during the nested function calls. Listing Three is the updated version of the Manager's insertion function. It uses the Boolean flag I just discussed to stop the recursive loop problem.

ostream& operator<<(ostream& os, const Manager& aManager)
{
    static bool Manager_printed = false;
    if (Manager_printed == false)
    {
        Manager_printed = true;
        os << static_cast<const Employee&>(aManager);
        Manager_printed = false;        
// code to print the Manager class
    }
    return os;
}
Listing Three

Now, calling the Manager's function directly using the manager1 object from the second example correctly invokes the Employee's insertion function to print the Employee portion of manager1. Keep in mind that the Employee's insertion function then calls the Manager's function, but my new flag prevents the loop from going any further. The flag also prevents the Manager's portion of the object from being printed twice.

While this version correctly deals with being called directly by a Manager object, my original example using an Employee pointer that points to a Manager object has a problem—the Employee's function is called twice. The Employee's function is called first because it's processing an Employee pointer. Because the Employee's function was handed a Manager object, it correctly calls the Manager's insertion function. The problem arises within the Manager's function. The Manager's function should not call the Employee's function in this case. However, there is no way for it to tell that it was called by the Employee's function. To fix this problem, a Boolean flag is also added to the Employee function; see Listing Four.

ostream& operator<<(ostream& os, const Employee& a Employee)
{
    static bool Employee_printed = false;
    if (Employee_printed == false)
    {
// code to print the Employee class
        Employee_printed = true; 
        if (dynamic_cast<const Manager*>(&a Employee) != NULL)
            os << *(dynamic_cast<const Manager*>(&a Employee));
        Employee_printed = false;   
    }
    return os;
}
Listing Four

So, the Manager's insertion function successfully deals with its two possible uses—being called directly by a Manager object, or being called indirectly by the Employee's insertion function. In the first case, it calls the Employee's insertion function to process the Employee's portion of the object. In the second case, the Employee's portion is being processed elsewhere.

Unfortunately, I found out that the executable size of the program grows when RTTI is turned on, so my desire to reduce memory requirements may not work as well as I hoped. To make matters even worse, for the dynamic_cast operation to work, the parent class must have at least one virtual method. Because one virtual method is required, the space for this version is the same as the previous version—one vtable for the class, plus a pointer to the vtable for every object. However, if the class already has a virtual method for some other reason, then additional space is not required for this version to implement polymorphism.

Version 3: An Enumerated Type

My final version replaces the dynamic_cast operator with a type identifier added to the parent class. No virtual method is needed for any of the classes. This lets me reduce the memory required for each object from a 32-bit pointer pointing to the vtable to an 8-bit character that stores the type identifier. In addition, no memory for the class's vtable is needed since a virtual method is not used nor is it required for the dynamic_cast operator because this operator is also not being used. The type identifier is an enumerated type stored in a character variable that is added to the Employee class; see Listing Five.

enum type { EMPLOYEE=1, MANAGER=2, SALESPERSON=3 };
class Employee
{
public:
    char _type;
    Employee()  { _type= EMPLOYEE; }
    friend ostream& operator<<(ostream& os, const Employee& aEmployee);
};
class Manager : public Employee
{
public:
    Manager() { _type = MANAGER; }
    friend ostream& operator<<(ostream& os, const Manager& aManager);
};
Listing Five

Objects must initialize the type identifier in their constructors. For brevity, I made the type identifier public but it could also be made private. Protected accessor and mutator methods would also be supplied for this option.

The new type identifier serves two purposes—it identifies the type of object passed to the parent's insertion function, and it replaces the Boolean flag used in the previous version. The flag stops the infinite recursion between the two insertion functions. The type identifier can act as a flag if it is altered while the two functions are executing, but reset prior to exiting the insertion operation.

Listing Six is version 3 of the example. The code for the Employee insertion function extends the previous examples so that it works for a situation where the Employee class has two children—a Manager and a Salesperson class. The Employee insertion function processes the Employee portion of the class before checking the type identifier. If a Manager object was passed into the Employee function, the type identifier is changed, then the Manager's function is called.

ostream& operator<<(ostream& os, const Employee& aEmployee)
{
// code to print the Employee class
    if (aEmployee._type == MANAGER)
    {
        const_cast<Employee&>(aEmployee)._type = - aEmployee._type;
        os << static_cast<const Manager&>(aEmployee);
        const_cast<Employee&>(aEmployee)._type = - aEmployee._type;
    }
    else if (aEmployee._type == SALESPERSON)
    {
        const_cast<Employee&>(aEmployee)._type = - aEmployee._type;
        os << static_cast<const Manager&>(aEmployee);
        const_cast<Employee&>(aEmployee)._type = - aEmployee._type;
    }
    return os;
}
ostream& operator<<(ostream& os, const Manager& aManager)
{
    if (aManager._type == MANAGER)
    {
        const_cast<Manager&>(aManager)._type = - aManager._type;
        os << static_cast<const Employee&>(aManager);
        const_cast<Manager&>(aManager)._type = - aManager._type;
    }
// code to print the Manager class
    return os;
}
Listing Six

The Manager's insertion function checks the object's type identifier before calling the Employee's insertion function. If the type identifier has been changed, then we know that the Manager's function was called by its parent and, thus, should not be called again. If the type identifier has not been modified, then we know it's the nonpolymorphic case, and therefore, we will have to call the Employee's insertion function to process the Employee portion of the object.

While this behavior appears equivalent to version 2, the behavior is actually slightly improved. Version 2 calls the Employee's function twice for the first example (cout << *pEmp). However, version 3 does not call the Employee function a second time because the Manager's function sees that the Employee's function changed the type identifier. Replacing version 2's static function variable with a class variable allows for this improvement.

How Do They Compare?

My primary motivation for exploring alternative versions of polymorphic insertion functions was to create a version that uses less memory than the virtual method version while obtaining comparable performance.

To compare the three versions of code, I experimented with six test cases; see Table 1. The first two test cases use objects and not pointers, so they are nonpolymorphic.

Test 1                  
Employee employee1;   
cout << employee1;

Test 2
Manager m1;
cout << manager1;

Test 3
Employee* pEmp = new Employee;
cout << *pEmp;

Test 4
Manager* pManager1 = new Manager;
cout << *pManager1;

Test 5
Employee* pEmp = new Manager;
cout << *pEmp;

Test 6
Employee* pEmp = new Salesperson;
cout << *pEmp;

Table 1: Test cases.

The first test calls the Employee's insertion function using an Employee object. Likewise, the second test calls the Manager's function using a Manager object. The next two test cases use pointers where the type of the pointer matches the type of the object that is being pointed to by the pointer. The third uses an Employee pointer that is pointing to an Employee object. The fourth test uses a Manager pointer that is pointing to a Manager object. The last two test cases assess the polymorphic behavior of the functions. They both use an Employee pointer that points to a Manager and Salesperson object, respectively.

Figure 2 shows the test timing data for each version. The time unit is microseconds. These numbers are the average of several runs using Visual C++ Version 7.

[Click image to view at full size]

Figure 2: Test timing data for each version.

I expected version 2 to be slower because it uses runtime type information (RTTI), but was surprised that it was so much slower. Keep in mind, version 2 is using just as much memory as version 1.

As I hoped, versions 1 and 3 are comparable in performance. In fact, version 3 is a little faster for the first and third test cases. Both of these test cases deal with parent objects. However, version 3 is a little slower for the test cases dealing with child objects.

Version 1 requires a class to have a vtable, plus every object must contain a pointer to the vtable. Version 3 requires each object to have a type identifier, but this needs less memory than the pointer for a vtable. So, version 3 uses less memory per object and per class.

Conclusion

In this article I presented three different techniques for polymorphic insertion functions. The third version is a viable option for situations with a small class hierarchy where more parent objects are used than children. In these examples, I assumed that there would be many more Employee objects than Manager and Salesperson objects.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.