How to Generate Arbitrarily Nested Vectors in C++?

Question

In C++, is it possible to generate a nested vector of depth (dimension) equal to a user defined input? For example, were a user to input an integer of value 2, one's program might create an object of type vector< vector< vector<int> > >. Obviously, there are numerous other ways one could easily achieve a similar behavior in C++, but I am purely interested as to whether or not the actual generation of an arbitrarily nested vector is possible. Initially, I thought this would be rather trivial, but my implementations all failed in rather curious ways.

#include<iostream>
#include<vector>

using namespace std;

template<typename A> void vec_print(vector<A> in){
    cout << "{";
    for(typename vector<A> :: iterator i = in.begin(); i != in.end(); ++i){
        cout << *i << ", ";
    }
    cout << "}" << endl;
}

template<typename B> void vec_print(vector< vector<B> > in){
    cout << "{";
    for(typename vector< vector<B> > :: iterator i = in.begin(); i != in.end(); ++i){
        vec_print(*i); cout << ", ";
    }
    cout << "}" << endl;
}

template<typename T> auto generate(unsigned int d){
    if(d == 0){
        vector<T> in;
        return in;
    }
    return generate< vector<T> >(d - 1);
}

int main(){
    unsigned int d = 0;
    cin >> d;
    vec_print(generate<int>(d));
    return 0;
}

Initially, I thought this may work, though I was rather suspect of it on account of my understanding of how C++ compilers handle template functions. Using the g++ compiler with the --std=c++11 flag, prior to crashing, the g++ compiler recursively spewed errors informing me that function return type deduction was only available under the C++17 specification. Attempting to compile this program with the --std=c++17 flag resulted in no errors, but the compiler simply crashing. I suspect the compiler attempted to generate an infinite number of, or possibly 2^31, template functions, though I would have hoped for it to have handled this with an error warning of infinite template function generation as opposed to silently dying.

Answer 1

The standard sets a limit of nested template instantiation depth (1024) a conforming program should not exceed. An implementation is not required to enforce or diagnose this limit or any other implementation limit though. It can simply fail to compile any program that is "too large".

Both gcc and clang can use a flag to set a user-defined limit to template instantiation depth. In order to see what's going on, use

g++ -std-c++17 -ftemplate-depth-20 yourprogram.cpp >& gcc.log

and see how large the resulting log file is. Then increase the depth to 21 and do it again. Do it couple more times, then extrapolate your findings to -ftemplate-depth-1024.

Of course compiler crashing is a QoI issue and should be considered a bug. Regardless of that, your program is not conforming because it exceeds an implementation quantity.

If you want to handle vectors of arbitrary number of dimensions, you cannot use a recursive template. You have to resort to other techniques that entail setting the dimension at run time rather than at compile time.

Answer 2

struct element_t;

struct element_t {
  ~element_t() {}
  using element_p = std::shared_ptr<element_t>;
  using data_t = std::variant< std::vector<element_p>, int >;
  data_t data;
  element_t(element_t const&)=default;
  element_t(data_t in):data(std::move(in)) {}
  element_t()=default;
};

element_t::data_t generate( unsigned int x ) {
  if (x==0) return {unsigned{0}};
  auto ptr = std::make_shared<element_t>(generate(x-1));
  auto vec = std::vector<element_t::element_p>{ptr};
  element_t::data_t r(vec);
  return r;
}

test code:

void print( element_t::data_t const& in ) {
    std::visit(
        [](auto const& e)
        {
            if constexpr( std::is_same< decltype(e), int const& >{} ) {
                std::cout << e << "\n";
            } else {
                for (const auto& x:e) {
                    if (!x)
                    {
                        std::cout << "null\n";
                    }
                    else
                    {
                        std::cout << "nest\n";
                        print(x->data);
                        std::cout << "unnest\n";
                    }
                }
            }
        },
        in
    );
}
int main() {
    auto r = generate(10);
    print(r);
}

Live example