Base case specialization for recursive variadic template

243 views Asked by At

My target is to define a Recursive class, templated on an int N and one or more types T, ...Ts, which should behave like a std::pair with

  • a std::array of N items of type T as the first,
  • and, as second, an optional std::vector of Recursive instances templated on the same N and on the remaining template arguments Ts....

In trying to write down the class given the above requirements, I've come up with this non-working code (where I've also defined some necessary, as they help a lot, aliases for two instantiations of Recursive), and I don't know if I have mis-designed what I described above (or if it is an ill-formed description!), or if I'm misusing the language syntax.

#include <array>
#include <boost/hana/fwd/optional.hpp>
#include <boost/hana/optional.hpp>
#include <string>
#include <utility>
#include <vector>

template <int N, typename T1, typename T2, typename ...Ts>
struct Recursive
    : std::pair<std::array<T1, N>, 
                boost::hana::optional<std::vector<Recursive<N, T2, Ts...>>>> {};

template <int N, typename T>
struct Recursive<N, T> : std::array<T, N> {};

template<typename ...T>
using Recursive2 = Recursive<2u, T...>;

template<typename ...T>
using Recursive3 = Recursive<3u, T...>;

int main() {
    using boost::hana::nothing;
    Recursive2<int> x(std::make_pair(std::array<int, 2>{0,0}, nothing));
}

I'll add some troubleshooting that I've done so far. In the following the template specilization seems to work just fine.

#include <iostream>

template <int N, typename T, typename ...Ts>
struct Recursive {
    void operator()(){ std::cout << "general\n"; }
};

template <int N, typename T>
struct Recursive<N, T> {
    void operator()(){ std::cout << "specialized\n"; }
};

template<typename ...T>
using Recursive2 = Recursive<2u, T...>;

template<typename ...T>
using Recursive3 = Recursive<3u, T...>;

int main() {
    Recursive2<int>{}();
    Recursive2<int>{}();
    Recursive2<int,int>{}();
}
3

There are 3 answers

6
Jarod42 On BEST ANSWER

You have several issues:

  • Your specialization doesn't match your primary template

    template <int N, typename T1, typename T2, typename ...Ts> struct Recursive; requires at least 3 parameters. I think it should be a specialization and primary template should be:

    template <int N, typename T1, typename ...Ts>
    struct Recursive;
    
  • template <int N, typename T> struct Recursive<N, T> doesn't behave like a std::pair (as you state your requirement, else your usage is wrong), you probably want something like:

    template <int N, typename T>
    struct Recursive<N, T> : std::pair<std::array<T, N>, decltype(boost::hana::nothing)>
    
  • You need to "forward" the constructors of the base class, (Composition instead of inheritance might be an option too, or traits to define type to use) or change way to construct the object.

Result is:

template <int N, typename T1, typename ...Ts>
struct Recursive;

template <int N, typename T1, typename T2, typename ...Ts>
struct Recursive<N, T1, T2, Ts...>
    : std::pair<std::array<T1, N>,
                boost::hana::optional<std::vector<Recursive<N, T2, Ts...>>>
                            >
{
    using std::pair<
        std::array<T1, N>,
        boost::hana::optional<std::vector<Recursive<N, T2, Ts...>>>>::pair;
};

template <int N, typename T>
struct Recursive<N, T>
    : std::pair<std::array<T, N>, decltype(boost::hana::nothing)>
{
    using std::pair<std::array<T, N>, decltype(boost::hana::nothing)>::pair;
};

template<typename ...T>
using Recursive2 = Recursive<2u, T...>;

template<typename ...T>
using Recursive3 = Recursive<3u, T...>;

int main() {
    using boost::hana::nothing;
    Recursive2<int> x(std::make_pair(std::array<int,2>{0,0}, nothing));
}

Demo

0
max66 On

Your error is that, first, you've declared Recursive receiving at least one integer and two or more types and, then, you've declared a partial specialization receiving one integer and exactly one type.

Error because the specialization can't receive only one type when the main template is declared receiving two types or more.

Can be counter-intuitive but a solution can be declare Recursive receiving only one type or more (and this become the ground case of the recursion) and the specialization receiving two types or more

template <int N, typename T1, typename...>
struct Recursive : std::array<T1, N>
 { };

template <int N, typename T1, typename T2, typename ...Ts>
struct Recursive<N, T1, T2, Ts...>
   : std::pair<std::array<T1, N>,
               boost::hana::optional<std::vector<Recursive<N, T2, Ts...>>>>
 { };

The following is little modified (std::size_t instead of int for sizes; std::optional instead of boost::hana::optional) but fully compiling example

#include <array>
#include <optional>
#include <string>
#include <utility>
#include <vector>

template <std::size_t N, typename T1, typename...>
struct Recursive : std::array<T1, N>
 { };

template <std::size_t N, typename T1, typename T2, typename ...Ts>
struct Recursive<N, T1, T2, Ts...>
   : std::pair<std::array<T1, N>,
               std::optional<std::vector<Recursive<N, T2, Ts...>>>>
 { };

template<typename ...T>
using Recursive2 = Recursive<2u, T...>;

template<typename ...T>
using Recursive3 = Recursive<3u, T...>;

int main ()
 {
    Recursive2<int> x{std::array<int, 2u>{0,0}};
    Recursive3<int, long> y{{std::array<int, 3u>{0,0,0}, {}}};
 }
2
Enlico On

I'm adding my own answer because I did find a solution (a bit before receiving the two answers; using std::optional is a late change I made accroding to one of the answers, though). However, in my solution I had to declare and define the constructor for the general and specialized templates, which makes me think it is not as good a solution as the other answers. But why not posting it?

#include <cassert>
#include <iostream>
#include <array>
#include <optional>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>

template <int N, typename T, typename ...Ts>
struct Recursive : std::pair<std::array<T, N>,
                             std::optional<std::vector<Recursive<N, Ts...>>>
                   > {
    template<typename ...Args>
    Recursive(Args&& ...args) : std::pair<std::array<T, N>,
                                std::optional<std::vector<Recursive<N, Ts...>>>
                  >(args...) {}
};

template <int N, typename T>
struct Recursive<N, T> : std::array<T, N> {
    template<typename ...Args>
    Recursive(Args&& ...x) : std::array<T, N>(x...) {}
};


template<typename ...T>
using Recursive2 = Recursive<2u, T...>;

template<typename ...T>
using Recursive3 = Recursive<3u, T...>;

int main() {
    std::array<std::string, 2> twoStrings{"hello","Hello"};
    std::array<char, 2> twoChars{'h', 'H'};

    Recursive2<std::string> s{twoStrings};
    assert(s == twoStrings);

    std::vector<Recursive2<char>> vecOfTwoChars{twoChars, twoChars, twoChars};

    Recursive2<std::string, char> sc{twoStrings, vecOfTwoChars};
    assert(sc.first == twoStrings);
    assert(sc.second->size() == 3);
    assert(sc.second == vecOfTwoChars);
    assert(sc.second.value()[0] == twoChars);

}