Compile-time pure virtual functions

Question

I've tried implementing a list container, and decided to move some general functions like sum() to base class, so that I can reuse them later in other containers.

All the base support class needs are three methods empty(), head() and tail. I can't make those pure virtual because support class will never be instantiated. But it still has to use those methods to implement its own methods like sum().

I tried something like this:

#include <iostream>
using namespace std;

template<typename T>
class StatsSupport {
public:
    T sum(void) const {
        if (empty()) {
            return T(0);
        } else {
            return head() + tail()->sum;
        }
    }

    // other methods
};

template<typename T>
class List : public StatsSupport<T> {
public:
    // constructors etc.

    bool empty(void) const {return head_ != NULL;}
    const T& head(void) const {return *head_;}
    const List<T>& tail(void) const {return *tail_;}

    // other methods
private:
    T* head_;
    List<T> *tail_;
};

But trying to use sum() gets me compilation error

prog.cpp:8:13: error: there are no arguments to 'empty' that depend on a template parameter, so a declaration of 'empty' must be available [-fpermissive]
   if (empty()) {
             ^

for each of empty(), head() and tail().

Any advice?

Answer 1

I might miss the point of the question but will give my 5 cents to it anyway :)

The reasoning behind the solution I show below is, that often people new to OOP (in C++) think that they must use inheritance to get things done.

But especially in C++, this is but one way and often not the best way to achieve composition.

While in the majority of cases, the overhead cost of virtual functions does not really matter, the code below shows a way to yield container expansions without using inheritance and without using virtual functions. The weak point of the approach is that the "container function contract" is only implicitly visible.

template <class _X>
class ContainerTypeA < _X >
{
public:
    typedef _X value_type;
    typedef ContainerTypeA<_X> container_type;

    const _X & Head() const
    {
        // return head of this containers content.
    }
    container_type Tail() const
    {
        // return the tail (all elements after the first element in a new instance.
    }
    bool IsEmpty() const
    {
        return true; // return whether or not this container is empty.
    }
};

template <class _X>
class ContainerTypeB < _X >
{
public:
    typedef _X value_type;
    typedef ContainerTypeB<_X> container_type;

    const _X & Head() const
    {
        // return head of this containers content.
    }
    container_type Tail() const
    {
        // return the tail (all elements after the first element) in a new instance.
    }
    bool IsEmpty() const
    {
        return true; // return whether or not this container is empty.
    }
};

// Note: In stead of the class with static member functions, this could 
// as well be a namespace with template-functions inside.
template < class _ContainerT >
class ContainerStats<_ContainerT>
{
    static _ContainerT::value_type Sum(const _ContainerT & container)
    {
        // Implement sum - possibly in the recursive way you did in your question.
    }
    // more expansion functions...
};

Answer 2

The problem is that StatsSupport cannot find the empty, head etc. functions because these neither exist in its nor in the global scope. StatsSupport does not know about the functions that exist in the derived class.

Basically there are two ways to solve this:

• Runtime polymorphism, where you add a virtual destructor to StatsSupport and add declarations for empty, head etc. which are pure virtual.
• Compile time polymorphism via using CRTP as mentioned in the comments. I will focus on the latter.

So basically StatsSupport needs to get a way to access functions of the derived class. This can be done by adding the type of the derived class as template parameter, which is called CRTP:

template<class Derived, typename T>
class StatsSupport {
public:
    T sum(void) const {
        if (derived()->empty()) {
            return T(0);
        } else {
            return derived()->head() + derived()->tail()->sum;
        }
    }

    // other methods
    private:
        Derived *derived()
        {
            return static_cast<Derived*>(this);
        }
        const Derived *derived() const
        {
            return static_cast<const Derived*>(this);
        }
};

template<typename T>
class List : public StatsSupport<List<T>, T> { // with some changes could be simplified to StatsSupport<List<T>> but this it ouf of scope of this question

I am using a function for derived instead of a member to keep the class const correct.

Of course another alternative would be a different design relying on algorithms. There you move sum and all the other functions of StatsSupport into global namesapce and would then access them like sum(my_container_instance). A more STL like way would be to use iterators. Then you could use std::accumulate to do the summing.

Answer 3

That's a serious design issue: Your StatSupport defines some general functions, but relies on specifics of its child classes.

So when StatSupport gets compiled, it doesn't even know that there is some head() and tail(). That's why you get the error message

Now imagine that one day you want to define other containers that shall inherit from StatSupport, for example your own Vector or Map, or DataBase. These data structures will not have a head and a tail.

Basically there are two main orientations you may take:

• define in your StatSupport some virtual functions for iterating through the data structure.
• or better, use in your data structures some iterators (like they exist for standard containers) and define some template functions (sum, average, etc...) that use iterators to browse through your container.

In the latter case, you wouldn't need inheritance to benefit from generic functions.