What is the best way to make a nested list in C++?

user_62163 0
Viewed 355

For those who know Python, the best way to explain what I want is by analogy:

[1, [2, 3], 4, [5, [6]], 7]

Obviously, I can implement my own class (template) to do this, but if the standard library has already invented this wheel, I want to avoid re-inventing it (or at least, avoid putting my half-baked re-invented version in my project).

data-structures c++
2 Answers

Under the hood, a python list is a dynamically reallocating array, i.e. the same sort of thing as a std::vector, and its elements are dynamic, i.e. the same sort of thing as std::any. So the most direct analogue of this code would be

using p = std::vector<std::any>;

auto myList = p { 1, p { 2, 3 }, 4, p { 5, p { 6 } }, 7};
user_24624370

So your value will have a type that either holds an int or a vector of values of the same type.

This can be achieved with std::variant with a struct to allow for the recursive nature of the type (and with one more constructor to allow initializing it with your desired syntax)

template<typename T>
struct nested_list : std::variant<std::vector<nested_list<T>>, T> {
    using std::variant<std::vector<nested_list<T>>, T>::variant;

    nested_list(std::initializer_list<nested_list> ilist)
        : std::variant<std::vector<nested_list<T>>, T>(
              std::in_place_index<0>, ilist) {}

    // You can also add some helper methods like "get_vector", "is_vector", etc.
};

Usage example:

template<typename T>
std::ostream& operator<<(std::ostream& os, const nested_list<T>& lst) {
    if (auto* v = std::get_if<0>(&lst)) {
        os << '{';
        bool first = true;
        for (const auto& child : *v) {
            if (first) first = false;
            else os << ", ";
            os << child;
        }
        os << '}';
    } else if (auto* e = std::get_if<1>(&lst)) {
        os << *e;
    } else {
        os << "<valueless by exception>";
    }
    return os;
}

int main() {
    nested_list<int> x = {1, {2, 3}, 4, {5, {6}}, 7};
    std::cout << x << '\n';
}
user_57546560
Related