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

"best way" seems like we should just close as opinion based. Do you just want `std::list`? — Bill Lynch, Jul 21 '21 at 05:27
What are your requirements? What is your definition of "best"? It seems you already have an implementation, what's wrong with it? — Alan Birtles, Jul 21 '21 at 05:35
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++. — paddy, Jul 21 '21 at 05:36
Is that a [tree](https://stackoverflow.com/questions/205945/why-does-the-c-stl-not-provide-any-tree-containers) of `int`? — Bob__, Jul 21 '21 at 05:41
Please provide a real world scenario depends on your requirement. Elaborate on your requirement. — Louis Go, Jul 21 '21 at 05:59
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. — Swift - Friday Pie, Jul 21 '21 at 06:03

score 6 · Answer 1 · answered Jul 21 '21 at 05:59

6

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

answered Jul 21 '21 at 05:59

Daniel McLaury

4,047
1
15
37

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)? – allyourcode Jul 21 '21 at 06:01
3

@allyourcode Are you talking about a tree? – Djeurissen Jul 21 '21 at 06:02
3

@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]. – Daniel McLaury Jul 21 '21 at 06:02
@allyourcode: i.e. that is a totally different question – Daniel McLaury Jul 21 '21 at 06:05
3

@allyourcode 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](https://www.boost.org/doc/libs/1_76_0/libs/graph/doc/index.html). Or, depending on your exact requirements, maybe just `std::(multi)set` will do. – alagner Jul 21 '21 at 06:23

score 2 · Accepted Answer · edited Jul 22 '21 at 21:39

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

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. — allyourcode, Jul 22 '21 at 21:37
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? — allyourcode, Jul 22 '21 at 21:48
@allyourcode You are exactly right about what that constructor does. See this for more details https://en.cppreference.com/w/cpp/utility/variant/variant (specifically the 7th constructor). It wouldn't be ambiguous with `nested_list`, since `int` can't be constructed from any `std::initializer_list`, but it could be ambiguous for some other type. — Artyer, Jul 23 '21 at 11:21

score 0 · Answer 3 · answered Aug 22 '23 at 02:00

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

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

3 Answers3