29

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

Rakete1111
  • 47,013
  • 16
  • 123
  • 162
sms
  • 1,014
  • 10
  • 20

1 Answers1

26

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

sehe
  • 374,641
  • 47
  • 450
  • 633
Yakk - Adam Nevraumont
  • 262,606
  • 27
  • 330
  • 524
  • I don't quite see why do you need to `clone` when you could just assign (in other words - `noisy::operator=` is never called), but thats ok, because this is not what I'm asking for. You see, Boost (including Boost.Variant) made by experts, and there is an existing practice (recursive variants). Now std::variant is getting standardized without recursion as if it is not essential. What I would like to see is an explanation of why recursion support is not important and to make it more concrete I give a code example for you to modify (to prevent answers like "use unique_ptr, promblem solved"). – sms Sep 13 '16 at 17:10
  • 2
    @sms That is explained in paragraph 1 and 2: because it was decided that `std::variant` does not use the heap. Paragraph 3 concludes why `std::variant` could not have the recursive structure you want, regardless of the trick you are using. `std::variant` has different operational semantics than `boost::variant`. Among other things, it is almost-never-empty instead of never-empty like `boost`. The cost for `boost::variant` is that it will invoke the equivalent of `new` way more often, while `std::variant` is a tagged union that stores its data inside itself. `value_ptr` provides a solution. – Yakk - Adam Nevraumont Sep 13 '16 at 17:21
  • My `value_ptr` emulates value semantics while storing a pointer. `clone` is needed to implement `value_ptr(value_ptr const&)`. As it happens, it also provides an easy to write `operator=`. An allocation can be avoided there by using `operator=` on the stored value: we could make this conditional on `operator=` being legal. I went with the simpler code. I'll add a variant. – Yakk - Adam Nevraumont Sep 13 '16 at 17:26
  • 2
    @Yakk: I disagree with your conclusions here. Yes, `Boost.Variant` will heap-allocate on occasion. But that isn't what makes its variant type permit recursion; that's all done through `recursive_wrapper`, which implements the effective equivalent of your `value_ptr`. The standard library could have provided a similar recursive_wrapper class without affecting the definition of `std::variant` at all. Indeed, you can use `boost::recursive_wrapper` with `std::variant` without problems. – Nicol Bolas Sep 13 '16 at 17:34
  • 1
    @sms: "*What I would like to see is an explanation of why recursion support is not important*" That's not what your question *asked*. You asked for how to avoid using Boost while still getting recursive behavior. – Nicol Bolas Sep 13 '16 at 17:45
  • @NicolBolas Ah, I misunderstood recursive_wrapper: I thought it was understood *by `variant`*. Ie, like [make_recursive_variant](http://www.boost.org/doc/libs/1_55_0/doc/html/boost/make_recursive_variant.html) does magic on the types. My bad. I'll edit `value_ptr` a touch. – Yakk - Adam Nevraumont Sep 13 '16 at 17:52
  • If I substitute `boost::variant` with `std::variant` and `boost::recursive_wrapper` with `value_ptr` I get an error "static assertion failed" in `adapt` function because `std::variant` is not convertible to `std::variant>`. – sms Sep 14 '16 at 16:14
  • @sms pass in a `value_ptr` instead of an `s`? Presumably `std` doesn't permit implicit pairwise variant conversion, while `boost` does; both seem like a reasonable position. (Also note that `value_ptr` being implicitly convertible-from `s` was a late addition above after I read `recursive_wrapper`, check that yours has that). – Yakk - Adam Nevraumont Sep 14 '16 at 16:46
  • 2
    This seems like an awful lot of trouble in order to avoid using boost's excellent recursive_wrapper. Confirms my position that boost is a better standard than the standard. – Richard Hodges Oct 13 '17 at 07:21
  • Why use `std::unique_ptr<>` here and not `std::shared_ptr<>`? Often, in such data structures you want to have multple sub-trees being shared between tree instances. – BitTickler Aug 15 '22 at 10:15
  • @BitTickler I might be willing to make it immutable pointers, but shared ownership of read-write state is both madness and an invitation for reference count cycles. Shared (mutable) ownership should only be used when you have a solid proven business case for it, as it makes lifetime insanely difficult to understand, and in C++ developers are in charge of lifetime. (Immutable objects make this a million times easier; which removes most of my objections to it.) – Yakk - Adam Nevraumont Aug 15 '22 at 15:13
  • @Yakk indeed - when writing this, I had immutability in mind. Namely something towards `persistent data structures` (https://en.wikipedia.org/wiki/Persistent_data_structure#:~:text=In%20computing%2C%20a%20persistent%20data,itself%20when%20it%20is%20modified.) – BitTickler Aug 15 '22 at 15:48