Imitating Derivation Constraints in C++
Posted by riwalk on 21 Jul 2010 | Tagged as: Software Design
One of the nicer features that is present in C# (and not in C++) is the ability to have constraints on template parameters.
Say, for example, you wanted to create a Set class that holds a set of unique objects. We could write a simple Set class that checks if an item exists prior to adding it. To extend it, we could make it a template class so that it would accept any object, and we would be done.
But say we wanted to be creative. Say we wanted our Set class to not only check if its items were equal, but also if its items are equivalent.
What is the difference you ask? Using a naive comparison, a computer might consider the fractions 1/2 and 2/4 to be different because their denominators and numerators are not equal. However, we can force the computer to consider them to be equivalent if we program in the correct logic.
In a language that implements derivation constraints, this is fairly straightforward. We simply write an interface and require that anything in the Set implement that interface:
interface IEquivalent<T>
{
bool IsEquivalent(T testItem);
}
class Set<T> where T : IEquivalent<T>
{
...
}
Unfortunately, doing this in C++ is a bit tougher. Lets say that we have a basic Set class (for the sake of being able to see the errors, we’ll include the complete code):
#include <vector>
template <class T>
class Set
{
private:
std::vector<T> _items;
public:
Set();
public:
void add(T item);
bool contains(T item);
size_t size();
public:
T operator[](int idx);
};
template <class T>
Set<T>::Set()
{
}
template <class T>
void Set<T>::add(T item)
{
if(!contains(item))
_items.push_back(item);
}
template <class T>
bool Set<T>::contains(T item)
{
for(size_t i=0; i<_items.size(); i++)
if(_items[i].IsEquivalent(item))
return true;
return false;
}
template <class T>
size_t Set<T>::size()
{
return _items.size();
}
template <class T>
T Set<T>::operator[](int idx)
{
return _items[idx];
}
This works great, but requires that our template parameter have the function IsEquivalent()–a difficult thing to enforce. To assist us, we can define an abstract class to represent an interface:
template <class T>
class IEquivalent
{
public:
virtual bool IsEquivalent(T other) = 0;
};
And then we can have anything contained in the set implement our interface:
#include <iostream>
#include "IEquivalent.h"
class Fraction : public IEquivalent<Fraction>
{
private:
double _num;
double _den;
public:
Fraction() : _num(1), _den(1) {}
Fraction(double num, double den) : _num(num), _den(den) {}
public:
virtual bool IsEquivalent(Fraction f) {
return (_num/_den) == (f._num/f._den);
}
void print() {
std::cout << _num << " / " << _den << std::endl;
}
};
And there we go. We now have a simple Set class that is able to hold any object that implements the IEquivalent interface. We can see it in action with a short example:
Set<Fraction> s;
s.add(Fraction(1,1));
s.add(Fraction(5,6));
s.add(Fraction(10,12));
s.add(Fraction(1,2));
s.add(Fraction(50,100));
s.add(Fraction(6,6));
s.add(Fraction(12,12));
s.add(Fraction(100000,100000));
for(size_t i=0; i<s.size(); i++)
s[i].print();
1 / 1 5 / 6 1 / 2 Press any key to continue . . .
And everything is great! Right?
Well, not quite. As was hinted on at the beginning of the post, this is not exactly ideal. The Set class works on anything that implements the IEquivalent interface, but we have no way to enforce this.
For example, if we declare a Set that does not implement the IEquivalent interface, it still works:
Set<string> MySoonToBeBrokenSet;
The only way to see any sort of error is to add code that calls the IsEquivalent function:
Set<string> MyBrokenSet;
MyBrokenSet.add("oops..");
Even when it breaks, we get a very poorly worded error message:
error C2039: 'IsEquivalent' : is not a member of 'std::basic_string<_Elem,_Traits,_Ax>'
Obviously we know what caused this, but what about someone who doesn’t know about the code? Sure, they could implement the function, but what happens if there are 4 functions in the interface that we rely on? People could mistakenly implement only functions that the compiler complains about, not realizing that there is an interface that they need to implement!
There has to be a better way…
Fortunately for us, there is. One solution that exists is to create a typedef in the interface and extend it in the Set class, as follows:
template <class T>
class IEquivalent
{
public:
virtual bool IsEquivalent(T other) = 0;
typedef int IsDerivedFromIEquivalent;
};//end of class IEquivalent
template <class T>
class Set
{
typedef typename T::IsDerivedFromIEquivalent IEquivalentGuard;
...
}
This works, but only to a certain extent. It does stop us from declaring a set using something that does not implement IEquivalent, but the error messages are less than ideal:
Set<string> MyBrokenSet;
error C2039: 'IsDerivedFromIEquivalent' : is not a member of 'std::basic_string<_Elem,_Traits,_Ax>' error C2146: syntax error : missing ';' before identifier 'IEquivalentGuard' error C4430: missing type specifier - int assumed. Note: C++ does not support default-int error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
Hmmm…a bit cryptic. Things do not improve when we use a built-in type (such as an integer) as the template parameter:
Set<int> MyBrokenSet;
error C2825: 'T': must be a class or namespace when followed by '::' error C2039: 'IsDerivedFromIEquivalent' : is not a member of '`global namespace'' error C2146: syntax error : missing ';' before identifier 'IEquivalentGuard' error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
Eeek.
We’re getting closer to our goal–users cannot create a Set using something that does not inherit from IEquivalent. The only problem now is that they will likely spend all day Googling error messages that are never going to help them.
Another problem with this technique is that we are making the assumption that we can modify the interface in the first place (not a good assumption).
Let’s look for another way.
Instead of using a hack involving typedef’s, lets just attempt to coerce our template argument into the correct type in the constructor like so:
template <class T>
Set<T>::Set()
{
IEquivalent<T>* typecheck = new T();
delete typecheck;
}
The syntax is pretty simple. So what happens because of this code? First, lets see what error message we get when we attempt to create a Set of strings:
Set<string> MyBrokenSet;
error C2440: 'initializing' : cannot convert from 'std::string *' to 'IEquivalent<T> *'
Seems pretty straightforward. What about if we try to create a Set of integers?
Set<int> MyBrokenSet;
error C2440: 'initializing' : cannot convert from 'int *' to 'IEquivalent<T> *'
Again, pretty straightforward! Now those of you who are fairly observant will notice that this solution requires that we have a default constructor on anything that we send into the Set class. What does the error message look like when we omit the default constructor from the Fraction class?
error C2512: 'Fraction' : no appropriate default constructor available
Again, we get a straightforward and easy to understand error message.
Is it perfect? Of course not. C++ is not C# and as a result we can only imitate those handy features of C#. However, this is a good way to prevent difficult errors in your template classes.
No Comments »