Using std::variant with recursion, without using boost::recursive_wrapper

Question

I'd like to replace boost::variants with C++17 std::variant and get rid of boost::recursive_wrapper, to remove dependency on boost completely in following code. How may I do that?

#include <boost/variant.hpp> #include <type_traits>  using v = boost::variant<int, boost::recursive_wrapper<struct s> >; struct s {     v val; };  template<template <typename...> class R, typename T, typename ... Ts> auto reduce(T t, Ts ... /*ts*/) {     return R<T, Ts...>{t}; }  template<typename T, typename F> T adapt(F f) {     static_assert(std::is_convertible_v<F, T>, "");     return f; }  int main() {     int  val1 = 42;     s    val2;     auto val3 = adapt<v>(reduce<boost::variant>(val1, val2)); } 

There are two generic functions: first function reduce chooses at runtime which argument to return (here it just returns first argument for brevity), second function adapt converts a value of type F to a value of type T.

In this example reduce returns an object of type boost::variant<int, s> which is then converted to an object of type boost::variant<int, boost::recursive_wrapper<s> >.

Answer 1

boost::variant will heap allocate in order to have part of itself be recursively defined as itself. (It will also heap allocate in a number of other situations, uncertain how many)

std::variant will not. std::variant refuses to heap allocate.

There is no way to actually have a structure containing a possible variant of itself without a dynamic allocation, as such a structure can easily be shown to be infinite in size if statically declared. (You can encode the integer N by having N recursions of not-the-same: no fixed size buffer can hold an infinite amount of information.)

As such, the equivalent std::variant stores a smart pointer of some kind placeholder of a recursive instance of itself.

This may work:

struct s; using v = std::variant< int, std::unique_ptr<s> >; struct s {   v val;   ~s(); }; inline s::~s() = default; 

and failing that, try:

struct destroy_s; struct s; using v = std::variant<int, std::unique_ptr<s, destroy_s> >; struct s {   v val;   ~s(); }; struct destroy_s {   void operator()(s* ptr){ delete ptr; } }; inline s::~s() = default; 

It does mean that client code has to knowingly interact with the unique_ptr<s> and not the struct s directly.

If you want to support copy semantics, you'll have to write a value_ptr that does copies, and give it the equivalent of struct copy_s; to implement that copy.

template<class T> struct default_copier {   // a copier must handle a null T const* in and return null:   T* operator()(T const* tin)const {     if (!tin) return nullptr;     return new T(*tin);   }   void operator()(void* dest, T const* tin)const {     if (!tin) return;     return new(dest) T(*tin);   } }; template<class T, class Copier=default_copier<T>, class Deleter=std::default_delete<T>,   class Base=std::unique_ptr<T, Deleter> > struct value_ptr:Base, private Copier {   using copier_type=Copier;   // also typedefs from unique_ptr    using Base::Base;    value_ptr( T const& t ):     Base( std::make_unique<T>(t) ),     Copier()   {}   value_ptr( T && t ):     Base( std::make_unique<T>(std::move(t)) ),     Copier()   {}   // almost-never-empty:   value_ptr():     Base( std::make_unique<T>() ),     Copier()   {}    value_ptr( Base b, Copier c={} ):     Base(std::move(b)),     Copier(std::move(c))   {}    Copier const& get_copier() const {     return *this;   }    value_ptr clone() const {     return {       Base(         get_copier()(this->get()),         this->get_deleter()       ),       get_copier()     };   }   value_ptr(value_ptr&&)=default;   value_ptr& operator=(value_ptr&&)=default;    value_ptr(value_ptr const& o):value_ptr(o.clone()) {}   value_ptr& operator=(value_ptr const&o) {     if (o && *this) {       // if we are both non-null, assign contents:       **this = *o;     } else {       // otherwise, assign a clone (which could itself be null):       *this = o.clone();     }     return *this;   }   value_ptr& operator=( T const& t ) {     if (*this) {       **this = t;     } else {       *this = value_ptr(t);     }     return *this;   }   value_ptr& operator=( T && t ) {     if (*this) {       **this = std::move(t);     } else {       *this = value_ptr(std::move(t));     }     return *this;   }   T& get() { return **this; }   T const& get() const { return **this; }   T* get_pointer() {     if (!*this) return nullptr;     return std::addressof(get());   }   T const* get_pointer() const {     if (!*this) return nullptr;     return std::addressof(get());   }   // operator-> from unique_ptr }; template<class T, class...Args> value_ptr<T> make_value_ptr( Args&&... args ) {   return {std::make_unique<T>(std::forward<Args>(args)...)}; } 

Live example of value_ptr.