Implementing an abstract class as a interface for other classes without vtable overhead

Question

I want to make interface classes ForwardIterator, BiderctionalIterator and RandomAccessIterator, each one of them has some operators (all of them are pure virtual and not implemented). Now if I want to implement an iterator for a container, I just inherit from the right iterator and get the help of the compiler if I accidently forgot to implement some functions/operators. Doing it with pure virtual functions works perfectly but It has the overhead of vtable which is unnecessary since the all code needs can be defined in compile time.

template <typename T>
struct ForwardIterator{
    virtual T operator++() = 0;
    virtual T operator++(int) = 0;
};

template <typename T>
struct BidirectionalIterator: public ForwardIterator<T>{
    virtual T operator--() = 0;
    virtual T operator--(int) = 0;
};

template <typename T>
struct RandomAccessIterator: public Bidirectional<T>{
    virtual T operator+(int) = 0;
    virtual T operator-(int) = 0;
};

// Custom Iterator Implementation

class MyCustomRandomAccessIterator
   : public RandomAccessIterator<MyCustomRandomAccessIterator>{
    // get errors if I miss some function definitions.
    // but it has vtable !!!

};

You might look at [does-static-polymorphism-make-sense-for-implementing-an-interface](https://stackoverflow.com/questions/20771210/does-static-polymorphism-make-sense-for-implementing-an-interface/20772541#20772541). — Jarod42, Dec 25 '20 at 14:07

max66 · Accepted Answer · 2020-12-25T12:51:45.300

If I understand correctly, you want to be sure that some methods are implemented in the final derived classes but without using the classic way (abstract inheritance) because it's too heavy.

My first idea was simply declare and not define the methods

template <typename T>
struct ForwardIterator {
    T operator++ ();
    T operator++ (int);
};

so when you use the methods

MyCustomRandomAccessIterator  i;

++i;

you get a linker error.

But you get a linker error (and I suppose you prefer a compilation error) and only when you use a forgotten method, so if you forget a single method can be difficult detect it (you need to use it with an object).

So my idea, maybe not perfect, is delete the methods, add a constructor and check the existence of the methods in the final class.

I mean... something as

template <typename T>
struct ForwardIterator {
    T operator++ () = delete;
    T operator++ (int) = delete;

    ForwardIterator ()
     {
       static_assert( sizeof(decltype(std::declval<T>()++)), "!" );
       static_assert( sizeof(decltype(++std::declval<T>())), "!" );
     }
};

This way you get all compilation errors (maybe, if you want, with meaningful error messages, better than "!") simply declaring an object of your class

MyCustomRandomAccessIterator  i;

// ++i; // no needs of invoke the forgotten methods to get the errors

The following is a full compiling example

#include <utility>

template <typename T>
struct ForwardIterator {
    T operator++ () = delete;
    T operator++ (int) = delete;

    ForwardIterator ()
     {
       static_assert( sizeof(decltype(std::declval<T>()++)), "!" );
       static_assert( sizeof(decltype(++std::declval<T>())), "!" );
     }
};

template <typename T>
struct BidirectionalIterator: public ForwardIterator<T> {
    T operator-- () = delete;
    T operator-- (int) = delete;

    BidirectionalIterator ()
     {
       static_assert( sizeof(decltype(std::declval<T>()--)), "!" );
       static_assert( sizeof(decltype(--std::declval<T>())), "!" );
     }
};

template <typename T>
struct RandomAccessIterator: public BidirectionalIterator<T>{
    T operator+ (int) = delete;
    T operator- (int) = delete;

    RandomAccessIterator ()
     {
       static_assert( sizeof(decltype(std::declval<T>()+0)), "!" );
       static_assert( sizeof(decltype(std::declval<T>()-0)), "!" );
     }
 };

// Custom Iterator Implementation

struct MyCustomRandomAccessIterator
   : public RandomAccessIterator<MyCustomRandomAccessIterator> {

   // with `if 0` (forgetting definition of requested methods) you get
   // a lot of compilation errors   
#if 1
    MyCustomRandomAccessIterator operator++ ()
     { return *this; } 

    MyCustomRandomAccessIterator operator++ (int)
     { return *this; } 

    MyCustomRandomAccessIterator operator-- ()
     { return *this; } 

    MyCustomRandomAccessIterator operator-- (int)
     { return *this; } 

    MyCustomRandomAccessIterator operator+ (int)
     { return *this; } 

    MyCustomRandomAccessIterator operator- (int)
     { return *this; } 
#endif
};

int main()
 {
   // simply declaring i you get a lot of errors, in case of no 
   // methods definitions
   MyCustomRandomAccessIterator  i;
 }

That's very smart solution. I assume that there are no memory or performance overhead, right ? — 0xDEADC0DE, Dec 25 '20 at 13:32
@0xDEADC0DE - Memory or performance overhead? No, I suppose there isn't (but I'm not an expert in practical compiler implementation so verify yourself with your compiler). — max66, Dec 25 '20 at 13:37

Yamahari · Answer 2 · 2020-12-25T11:53:20.950

0

What you want is the curiously recurring template pattern https://en.m.wikipedia.org/wiki/Curiously_recurring_template_pattern It allows for static polymorphism, i.e. you can cast the 'this' pointer to a pointer of child class for which you pass the type as a template parameter and call methods from the child class in the base class without a vtable. To differentiate the type of iterator you also pass a iterarator tag corresponding to the type as a template argument to the base class.This is how Boost.STLInterfaces works for example (https://www.boost.org/doc/libs/1_74_0/doc/html/stl_interfaces.html).

edited Dec 25 '20 at 11:53

answered Dec 25 '20 at 11:44

Yamahari

1,926
9
25

This looks like it should have been a comment instead unless you explain how it'll help. – Ted Lyngmo Dec 25 '20 at 11:45
Added a bit of explanation although the wiki page already explains it very well – Yamahari Dec 25 '20 at 11:50
1

And how does that help verify the type when just creating a `MyCustomRandomAccessIterator` object? – StoryTeller - Unslander Monica Dec 25 '20 at 11:52

Implementing an abstract class as a interface for other classes without vtable overhead

2 Answers2

Linked