C++ Force Template Parameter

Question

I want this code to be possible.

template<typename K, typename T, typename Comparer>
class AVLTree
{
   ...
   void foo() {
       ...
       int res = Comparer::compare(key1, key2);
       ...
   }
   ...
};

Specifically, I want to force Comparer class to have a static int compare(K key1, K key2) function. I was thinking about using derivation, but could not find any ideas that can work with templates.

Thank you.

Answer 1

Did you try doing:

   int res = Comparer::compare(key1, key2);

In C++ Static functions can be called in two ways:

object.static_method(); // use dot operator

classname::static_method(); // use scope resolution operator

Answer 2

It would have to be Comparer::Compare, right? (Since you are calling a static function on a type).

Your Comparer class would have to be defined as follows:

template<typename K>
class Comparer
{
public:
    static bool Compare(K key, K key)
    {
     return true;
    }
};

Answer 3

You can't. But if use the function and the Comparer doesn't have it, your compile will fail and this is more or less what you want to happen. And yes, like others pointed out you want to call static as static.

Answer 4

Michael already mentioned that this will not compile if Comparer doesn't have the required member function.

If however you're more worried about concise error messages, use something like this to detect if the class has a required member function and combine it with something like Boost.StaticAssert:

template<typename K, typename T, typename Comparer>
class AVLTree
{
    BOOST_STATIC_ASSERT(HasCompareMethod<Comparer>::has);
    //...
};

Answer 5

I understand it you're looking for a better error message in case the template parameter doesn't fit the requirements of the template body. the language doesn't have an special mechanism for that built in, but people approximate it using libraries. see Boost Concept Check

Answer 6

The loose approach of having a compile time assertion around this is to take the address of Comparer::compare and assign it to a variable declared as int(K, K) *func.

That assignment will work if it's a static function, but will not work if it's a member function.

I am just contributing this, but I would take the approach of using the boost idioms as this is hand-rolled, so to speak.

Answer 7

As already pointed out, you can't force Compare to have a static member compare. If your comparer doesn't implement it, you just get an compiler error.

If you implement AVLTree like this it would be more elegant to declare Comparer as a template template parameter:

template <typename K>
class DefaultComparer
{
public:
    static bool compare(K k1, K k2)
    { return k1 == k2; }
};

template <typename K>
class MyComparer : public DefaultComparer<K>
{
public:
    static bool compare(K k1, K k2)
    { return k1 <= k2; }
};

template <typename K>
class InvalidComparer
{
public:
    static bool bar(K k1, K k2)
    { return k1 != k2; }
    // Doesn't implement compare()
};

// Compare is a template template paramenter with default template argument
// DefaultComparer
template <typename K, template <typename K> class Comparer = DefaultComparer>
class AVLTree
{
    K k1, k2;
public:
    AVLTree() : k1(0), k2(0) { } // ctor
    bool foo();
};

// Definiton of AVLTree::foo()
template <typename K, template <typename K> class Comparer>
bool AVLTree<K, Comparer>::foo()
{
    return Comparer<K>::compare(k1, k2);
}

int main(int argc, char *argv[])
{
    // Without template template parameters you 
    // would have to use AVLTree<int, DefaultComparer<int> >
    AVLTree<int> avltree;

    // instead of AVLTree<int, MyCompare<int> >
    AVLTree<int, MyComparer> avltree2;

    // Calling foo() will generate a compile error. 
    // But if you never call avltree3.foo() this will compile!
    AVLTree<int, InvalidComparer> avltree3;

    avltree.foo(); // calls DefaultComparer::compare
    avltree2.foo(); // calls MyComparer::compare
    avltree3.foo(); // fails to compile
}

see: http://codepad.org/OLhIPjed

Answer 8

Here's a more idiomatic and generic approach:

template<typename K, typename T>
class AVLTree
{
   ...
   template <typename Comparer>
   void foo(Comparer cmp) {
       ...
       int res = cmp(key1, key2);
       ...
   }
   ...
};

Comparer should not be a type that defines a static Compare method. It should be a type which can be called with function call syntax. That allows you to use function pointers of function objects, and it allows you to reuse the comparers already defined in the standard library, or in pretty much any other nontrivial C++ application. It allows you to use lambdas when they're added in C++0x.

As for forcing Comparer to behave as expected? The line int res = cmp(key1, key2); already ensures that. If you try to pass a type that can't be called in this way, you get a compile error.

The same was the case in your original code. If you passed a type that didn't have a static Compare method, you'd get a compile error. So your original code already solved the problem.