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

Question

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).

Peta

"best way" seems like we should just close as opinion based. Do you just want std::list<std::any>? – Proxy

What are your requirements? What is your definition of "best"? It seems you already have an implementation, what's wrong with it? – Violette

How about an actual practical example of why you want this? The suggestion above is basically giving you what you ask for, but it's not the kind of thing one would typically use in C++. Pythonic techniques and data structures don't tend to translate very well into C++. – Lachrymose

Is that a tree of int? – Wherewithal

Please provide a real world scenario depends on your requirement. Elaborate on your requirement. – Edmundson

that's the problem with script language approach, where resources and time used aren't taken in account. Can you do it? Just do, do not define why or what you require.. whatever it is , it likely can be done in about same efficiency. – Roice

Answer 1

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';
}

Rentfree

Wow! I'm pretty surprised that you can make nested_list inherit from something that is derived from nested_list! To me, that the main key to this solution. – Peta

I've been trying to learn variant. I understand the basic concept, but things like in_place_index kind of confuses me. I guess what you are saying there is to use the first (i.e. index 0 of two) possible types, namely vector<...> ? I guess this is needed because otherwise it might be (or definitely is?) ambiguous which type variant is supposed to choose during initialization? – Peta

@Peta You are exactly right about what that constructor does. See this for more details en.cppreference.com/w/cpp/utility/variant/variant (specifically the 7th constructor). It wouldn't be ambiguous with nested_list<int>, since int can't be constructed from any std::initializer_list<T>, but it could be ambiguous for some other type. – Rentfree

Answer 2

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};

Cytochemistry

Nice! I did not know about any. But what if I want all the "leaf" elements to be of the same type (e.g. int)? – Peta

@Peta Are you talking about a tree? – Kharif

@allyourcode: Then what you're doing is actually very different from the python example you cited, because python will just as well let you write something like [1.0, [2, 3], "four", [lambda x: 5, [6]], 7]. – Cytochemistry

@allyourcode: i.e. that is a totally different question – Cytochemistry

@Peta the main question is: do you care about the possibility to nest arrays in arrays, or to be able to store every type possible (or both?). Because there is a plethora of options depending on you exact requirements: e.g. already mentioned std::any, std::variant can also work here. But it seems to me that you're looking for a custom data structure like tree/graph. If so, you can try boost. Or, depending on your exact requirements, maybe just std::(multi)set will do. – Anthropogenesis

Answer 3

Probably not the best answer, but you can also try something like this:

class NestedList {
 private:
  std::variant<std::vector<NestedList>, int> data;

 public:
  // default constructor
  NestedList() {
    data = std::vector<NestedList>(); // create empty vector
  }

  // int constructor
  NestedList(int data) : data(data) {}

  // vector constructor 
  NestedList(const std::vector<NestedList>& data) : data(data) {}

  // check if this is a vector
  bool isVector() {
    return data.index() == 0;
  }

  // getting data in different forms 
  // (requires you to check isVector beforehand)
  // for int
  int getInt() { 
    return std::get<int>(data);
  }

  // for vector
  std::vector<NestedList>& getVector() {
    std::vector<NestedList>& dataref = std::get<std::vector<NestedList>>(data);
    return dataref;
  }

  // optional methods...
};

To access a specific element that is deep inside somewhere, you can do:

  NestedList inside({4, 5, 6}); // to add inside n
  NestedList n({1, 2, inside}); // initialize with three elements

  int myInt = n.getVector()[2].getVector()[2].getInt(); // gives 6

Commutate