Proper C++ type for nested list of arbitrary and variable depth?

Question

I'm trying to port some code from Python to C++. The Python code has a function foo that can take nested lists of ints, with variable list depth. For example, these are legitimate function calls to foo:

foo([ [], [[]], [ [], [[]] ] ])
foo([1])
foo([ [1], [2, 3, [4, 5]], [ [6], [7, [8, 9], 10] ] ])

What should the method signature(s) be for a C++ method that can accept this kind of argument?

Answer 1

Here's a way that's pretty simple to define and use:

#include <variant>
#include <vector>

struct VariableDepthList : std::variant<std::vector<VariableDepthList>, int> {
private:
    using base = std::variant<std::vector<VariableDepthList>, int>;
public:
    using base::base;
    VariableDepthList(std::initializer_list<VariableDepthList> v) : base(v) {}
};

This is based on the fact that your type is either an int or a list of (the same type), adding an initializer_list constructor just for ease of use.

You might want to add some helper function like is_vector()/is_value() too.

Here is an example using it:

#include <iostream>

void foo(const VariableDepthList& v) {
    // Use like a variant. This is a print function
    if (auto* as_vector = std::get_if<std::vector<VariableDepthList>>(&v)) {
        if (as_vector->empty()) {
            std::cout << "[]";
            return;
        }
        std::cout << "[ ";
        bool first = true;
        for (const auto& el : *as_vector) {
            if (!first) {
                std::cout << ", ";
            }
            first = false;

            foo(el);
        }
        std::cout << " ]";
    } else {
        auto* as_int = std::get_if<int>(&v);
        std::cout << *as_int;
    }
}

int main() {
    foo({});
    std::cout << '\n';
    foo({ 1 });
    std::cout << '\n';
    foo({ {}, {{}}, { {}, {{}} } });
    foo( {{1},{2,3,{4,5}},{{6},{7,{8,9},10}}} );
    std::cout << '\n';
}

Answer 2

Here's my take on it

#include <iostream>
#include <variant>
#include <vector>

// A class containing either a T or a nest<T>
template<class T>
struct nest {
    auto cbegin() const { return d.cbegin(); }
    auto cend() const { return d.cend(); }
    auto begin() const { return d.cbegin(); }
    auto end() const { return d.cend(); }
    auto begin() { return d.begin(); }
    auto end() { return d.end(); }

    std::vector<std::variant<T, nest<T>>> d;
};

namespace detail {
template<class... Ts> // helper type for visitor
struct overloaded : Ts... { using Ts::operator()...; };

template<class... Ts> // deduction guide for helper type
overloaded(Ts...) -> overloaded<Ts...>;

template<class T>
void foo_helper(const std::variant<T, nest<T>>& n) {
    std::visit(overloaded {
        [](const T& v) { std::cout << v; },
        [](const nest<T>& v) { foo(v); }
    }, n);
};
} // namespace detail

template<class T>
void foo(const nest<T>& list) {
    auto it = list.begin();
    std::cout << '[';
    if(it != list.end()) {
        detail::foo_helper(*it);
        for(++it; it != list.end(); ++it) {
            std::cout << ',';
            detail::foo_helper(*it);
        }
    }
    std::cout << ']';
}

int main() {
    std::cout << "[[1],[2,3,[4,5]],[[6],[7,[8,9],10]]] <- what we aim for\n";

    foo(nest<int>{{nest<int>{{1}},
                   nest<int>{{2, 3, nest<int>{{4, 5}}}},
                   nest<int>{{nest<int>{{6}},
                   nest<int>{{7, nest<int>{{8,9}}, 10}}}}}} );
}

Output:

[[1],[2,3,[4,5]],[[6],[7,[8,9],10]]] <- what we aim for
[[1],[2,3,[4,5]],[[6],[7,[8,9],10]]]