recursive template inheritance code duplication

Question

#include <iostream>

template< class T, unsigned S >
struct my_iterator;

template< class T >
struct my_iterator< T, 1 >
{ 
    T* p;
};

template< class T, unsigned S >
struct my_iterator : my_iterator< T, S / 2 >
{
    static_assert ((S & (S - 1)) == 0, "S must be a power of 2");

    using my_iterator< T, S / 2 >::p;

    unsigned burp() {return (*p) + S;}
};

int main()
{
    int v = 10;

    my_iterator< int, 8 > a;
    a.p = &v;
    std::cout << a.burp() << std::endl;

    my_iterator< int, 4 >& b = a;
    std::cout << b.burp() << std::endl;

    my_iterator< int, 1 > c;
    c.p = &v;
    std::cout << c.burp() << std::endl; // error: no member named 'burp'

    return 0;
}

This will fix the error:

template< class T >
struct my_iterator< T, 1 >
{ 
    unsigned burp() {return (*p) + 1;}

    T* p;
};

but in my real code I have many methods, not just burp, all dependent on S and p, that would all need to be implemented twice, once in the general class and once in the specialization. Is there any way to avoid the duplicate code? I saw this similar question:

Avoiding code duplication in a specialized template

but the answer will not work in my case because I'll end up with many copies of p, one at each level of the recursive hierarchy.

score 3 · Accepted Answer · answered Jul 18 '14 at 20:48

Another option, if you have a recursion stop value of 1 which you want to still use, you can just move the stop value to 0...
This way my_iterator<T,1> still has the default implementation.

    template< class T, unsigned S >
    struct my_iterator;

    template< class T >
    struct my_iterator< T, 0 >
    { 
        T* p;

    };

    template< class T, unsigned S >
    struct my_iterator : my_iterator< T, S / 2 >
    {
        static_assert ((S & (S - 1)) == 0, "S must be a power of 2");

        using my_iterator< T, S / 2 >::p;

        unsigned burp() {return (*p) + S;}
    };

Such a simple solution, thanks! Also, in this case I wouldn't want to be able to call any methods with S==0 anyway, it wouldn't make sense, so this works out perfectly. — atb, Jul 18 '14 at 20:53

Jarod42 · Answer 2 · 2014-07-20T08:30:08.937

1

An other way is to move specific stuff in an other structure:

template <typename T> struct opt_ptr { T* p; };

// to be able to use std::conditional with non instantiated type.
template <typename T> struct identity { using type = T; };

template<typename T, unsigned S>
struct my_iterator :
    std::conditional<S == 1,
                     identity<opt_ptr<T>>,
                     identity<my_iterator<T, S / 2>>>::type::type
{
    static_assert ((S & (S - 1)) == 0, "S must be a power of 2");

    using opt_ptr<T>::p; // Note that you may use this->p to avoid this line

    unsigned burp() {return *p + S;}
    // Other methods using S and p.
};

edited Jul 20 '14 at 08:30

answered Jul 18 '14 at 21:00

Jarod42

203,559
14
181
302

`my_iterator` inheriting from itself is also a problem. – Casey Jul 19 '14 at 00:17
1

@atb: only `opt_ptr` has `T* p;`, all others are empty classes. – Jarod42 Jul 19 '14 at 12:22
What stops the recursive inheritance? Wouldn't I still need a specialization of my_iterator or my_iterator? – atb Jul 19 '14 at 13:26
@atb: you're right, recursion has to be stopped with an empty `my_iterator`... (or use other tricks for conditional inheritance) – Jarod42 Jul 19 '14 at 13:36

Yochai Timmer · Answer 3 · 2014-07-18T20:19:44.653

0

You could pass down S to the base template, and move the method there.

template< class T, unsigned S, unsigned N >
struct my_iterator;

template< class T, unsigned S >
struct my_iterator< T,S, 1 >
{  
    unsigned burp() {return (*p) + S;}

    T* p;
};

template< class T, unsigned S, unsigned N = S >
struct my_iterator : my_iterator< T, S, N / 2 >
{
    static_assert ((S & (S - 1)) == 0, "S must be a power of 2");

    using my_iterator< T,S, N / 2 >::p;

};

edited Jul 18 '14 at 20:19

answered Jul 18 '14 at 20:09

Yochai Timmer

48,127
24
147
185

You also have to redefine the base template to take three parameters. – David G Jul 18 '14 at 20:13
@atb ok, i've opened my VS to get a compiling version of what i meant. – Yochai Timmer Jul 18 '14 at 20:20
This does avoid the duplication but it changes the functionality. I can't cast `my_iterator< int, 8 >` to `my_iterator< int, 4 >` anymore and this is a requirement of the design. I can cast it to `my_iterator< int, 8, 4 >` but then burp returns the wrong value. – atb Jul 18 '14 at 20:30
@atb Do you need the recursion all the way down to 1 ? – Yochai Timmer Jul 18 '14 at 20:42
Yes I do. I know I could get the same functionality without any inheritance, using `reinterpret_cast`, but I'm trying to do this the "right" way. I'm trying to work something out with an additional non-specialized base class and conditional inheritance with `std::conditional`...but no luck so far. – atb Jul 18 '14 at 20:47

recursive template inheritance code duplication

3 Answers3