c++treerecursive-datastructures

Replace pointers with std::optional in a recursive data structure

Is it possible to replace pointers with std::optional in a recursive data structure?

For example, how would I replace the following pointer based Tree

template< typename T >
struct Tree {
    T data;
    Tree* left;
    Tree* right;
};

with a Tree that uses std::optional instead of pointers?

I have tried this:

template< typename T >
struct Tree {
    T data;
    std::optional< Tree< T > > left;
    std::optional< Tree< T > > right;
};

but the compiler greeted me with several screens of error messages about incomplete type Tree<int> used in type trait expression.

Solution

  • It doesn't work this way. The idea behind std::optional<> is that it already contains storage for Tree<T>. Your Tree<T> would be of infinite size this way.