std::unique_ptr, Default Copy Constructor, and Abstract Class

Question

I have class representing a tree object that uses unique pointers, some nodes that make up the tree, and a function that constructs pointers to an abstract node class based on some arguments (It makes pointers to subclasses, since abstract node is abstract)

class AbstractNode
{
    vector<unique_ptr<AbstractNode>> children;
public:
    AbstractNode(arguments...);
    // other stuff...
};
class Tree
{
    unique_ptr<AbstractNode> baseNode;
    // other stuff...
}
unique_ptr<AbstractNode> constructNode(AbstractNodeTypes type);

There are a variety of subclasses of abstractNode that will be contained in the tree. The subclasses provide different implementations for some virtual functions in that class.

I want to be able to copy my tree by creating a new set of nodes with the same class types that are distinct copies of the nodes in the original tree.

---

Here is the problem:

If I write my own copy constructor for the AbstractNode class that deep copies the children, I'll have to write copy constructors for all of the subclasses of AbstractNode, which seems annoying since the only thing that won't copy correctly are the children pointers. It will also be annoying to use copy constructors here because I will need to cast the children to the correct types before I call them, I think.

Is there some way I can get the compiler to let me use the default copy constructor to set up everything except for the children. It can leave those as null pointers or something? Then I can write a simpler function that just recursively adds children to copy a tree.

If that is impossible, is there any non-ugly solution to this problem that anyone knows of?

Answer 1

The typical way to solve this problem is to have a virtual clone function similar to what Kerrek SB describes in his answer. However I would not bother writing your own value_ptr class. It is simpler to just reuse std::unique_ptr as your question presents. It will require a non-default copy constructor in AbstractNode, but does not require explicit or unsafe casting:

class AbstractNode
{
    std::vector<std::unique_ptr<AbstractNode>> children;
public:
    AbstractNode() = default;
    virtual ~AbstractNode() = default;
    AbstractNode(AbstractNode const& an)
    {
        children.reserve(an.children.size());
        for (auto const& child : an.children)
            children.push_back(child->clone());
    }

    AbstractNode& operator=(AbstractNode const& an)
    {
        if (this != &an)
        {
            children.clear();
            children.reserve(an.children.size());
            for (auto const& child : an.children)
                children.push_back(child->clone());
        }
        return *this;
    }

    AbstractNode(AbstractNode&&) = default;
    AbstractNode& operator=(AbstractNode&&) = default;
    // other stuff...

    virtual
        std::unique_ptr<AbstractNode>
        clone() const = 0;
};

Now a ConcreteNode can be implemented. It must have a valid copy constructor which may be defaulted depending upon what data members ConcreteNode adds to the mix. And it must implement clone(), but that implementation is trivial:

class ConcreteNode
    : public AbstractNode
{
public:
    ConcreteNode() = default;
    virtual ~ConcreteNode() = default;
    ConcreteNode(ConcreteNode const&) = default;
    ConcreteNode& operator=(ConcreteNode const&) = default;
    ConcreteNode(ConcreteNode&&) = default;
    ConcreteNode& operator=(ConcreteNode&&) = default;
    // other stuff...

    virtual
        std::unique_ptr<AbstractNode>
        clone() const override
        {
            return std::unique_ptr<AbstractNode>(new ConcreteNode(*this));
        }
};

I suggest having clone return a unique_ptr instead of a raw pointer just to ensure that there is no chance that a new'd pointer is ever exposed without an owner.

For completeness I've also shown what the other special members would look like.

At first I was thinking that C++14's make_unique would be nice to use here. And it can be used here. But personally I think in this particular example it really doesn't carry its weight. Fwiw, here is what it would look like:

    virtual
        std::unique_ptr<AbstractNode>
        clone() const override
        {
            return std::make_unique<ConcreteNode>(*this);
        }

Using make_unique you have to first construct a unique_ptr<ConcreteNode>, and then rely on the implicit conversion from that to unique_ptr<AbstractNode>. This is correct, and the extra dance probably will get optimized away as soon as inlining is fully enabled. But the use of make_unique just seems like an unnecessary obfuscation here when what you really clearly need is a unique_ptr<AbstractNode> constructed with a new'd ConcreteNode*.

Answer 2

Instead of using unique_ptr, you may wish to roll your own implementation of a value_ptr. Those designs have been proposed regularly in the past, but until we have a standardized version, either roll your own or find an existing implementation.

It would look a bit like this:

template <typename T> struct value_ptr
{
    T * ptr;
    // provide access interface...

    explicit value_ptr(T * p) noexcept : ptr(p) {}

    ~value_ptr() { delete ptr; }

    value_ptr(value_ptr && rhs) noexcept : ptr(rhs.ptr)
    { rhs.ptr = nullptr; }

    value_ptr(value_ptr const & rhs) : ptr(rhs.clone()) {}

    value_ptr & operator=(value_ptr && rhs) noexcept
    {
        if (&rhs != this) { delete ptr; ptr = rhs.ptr; rhs.ptr = nullptr; }
        return *this;
    }

    value_ptr & operator=(value_ptr const & rhs)
    {
        if (&rhs != this) { T * p = rhs.clone(); delete ptr; ptr = p; }
        return *this;
    }

};

You can build your tree from a set of clonable nodes.

struct AbstractNode
{
    virtual ~AbstractNode() {}
    virtual AbstractNode * clone() const = 0;

    std::vector<value_ptr<AbstractNode>> children;
};

struct FooNode : AbstractNode
{
    virtual FooNode * clone() const override { return new FooNode(this); }
    // ...
};

Now your nodes are copyable automatically without the need for you to write any explicit copy constructors. All you need to do is to maintain discipline by overriding clone in every derived class.

Answer 3

The normal pattern for this is a virtual clone method through your hierarchy.

If that is impossible, is there any non-ugly solution to this problem that anyone knows of?

You can also use template instantiation of a clone function based on copy constructors. Here's a solution I use in a web server I'm writing (pet project):

#pragma once

#include <memory>
#include <cassert>
#include <functional>
#include <stdexcept>
#include <vector>

namespace stdex {
    inline namespace details {

        /// @brief Deep copy construct from (Specialized&)*src
        ///
        /// @retval nullptr if src is nullptr
        /// @retval Specialized clone of *src
        ///
        /// @note Undefined behavior src does not point to a Specialized*
        template<typename Base, typename Specialized>
        Base* polymorphic_clone (const Base* src) {
            static_assert(std::is_base_of<Base, Specialized>::value,
                "Specialized is not a specialization of Base");

            if (src == nullptr)
                return nullptr;
            return new Specialized{ static_cast<const Specialized&>(*src) };
        }
    }

    /// @brief polymorphic reference interface over a base class
    ///
    /// Respects polymorphic behavior of class ref.
    /// Instances have deep copy semantics (clone) and
    /// "[const] Base&" interface
    ///
    /// @note Not regular: no trivial way to implement non-intrusive equality
    ///
    /// @note safe to use with standard containers
    template<typename Base>
    class polymorphic final
    {
    public:

        /// Functor capable to convert a Base* to it's specialized type
        /// and clone it (intrusive implementation can be used)
        typedef std::function<Base* (const Base*)>  clone_functor;

        /// @brief construct (takes ownership of ptr)
        template<typename Specialized, typename CloneSpecialized>
        polymorphic(Specialized* ptr, CloneSpecialized functor) noexcept
        : instance_{ptr}, clone_{std::move(functor)}
        {
            static_assert(std::is_base_of<Base, Specialized>::value,
            "Specialized is not a specialization of Base");
            static_assert(
            std::is_constructible<clone_functor, CloneSpecialized>::value,
            "CloneSpecialized is not valid for a clone functor");
        }

        // not implemented: UB cloning in case client provides specialized ptr
        // polymorphic(Base* ptr);

        polymorphic()
        : polymorphic{ nullptr, clone_functor{} }
        {
        }

        polymorphic(polymorphic&&) = default;

        polymorphic(const polymorphic& other)
        : polymorphic{std::move(other.clone())}
        {
        }
        polymorphic& operator=(polymorphic other)
        {
            std::swap(instance_, other.instance_);
            std::swap(clone_, other.clone_);
            return *this;
        }

        ~polymorphic() = default;

        /// @brief Cast to contained type
        /// @pre instance not moved
        /// @pre *this initialized with valid instance
        operator Base&() const
        {
            assert(instance_.get());
            return *instance_.get();
        }

        /// @brief Cast to contained type
        /// @pre instance not moved
        /// @pre *this initialized with valid instance
        operator const Base&() const
        {
            assert(instance_.get());
            return *instance_.get();
        }

    private:
        polymorphic clone() const
        {
            return polymorphic{
                clone_(instance_.get()), clone_functor{clone_}
            };
        }

        std::unique_ptr<Base>   instance_;
        clone_functor           clone_;
    };

    template<typename Base, typename Specialized, typename CF>
    polymorphic<Base> to_polymorphic(Specialized&& temp, CF functor)
    {
        static_assert(std::is_base_of<Base, Specialized>::value,
        "Specialized is not a specialization of Base");

        typedef typename polymorphic<Base>::clone_functor clone_functor;

        auto    ptr_instance = std::unique_ptr<Base>{
            new Specialized{std::move(temp)}
        };
        auto    clone_instance = clone_functor{std::move(functor)};

        return polymorphic<Base>{ptr_instance.release(), clone_instance};
    }

    template<typename Base, typename Specialized>
    polymorphic<Base> to_polymorphic(Specialized&& temp)
    {
        static_assert(std::is_base_of<Base, Specialized>::value,
        "Specialized is not a specialization of Base");

        return to_polymorphic<Base,Specialized>(
            std::move(temp), details::polymorphic_clone<Base,Specialized>
        );
    }

    template<typename Base, typename Specialized, typename ...Args>
    polymorphic<Base> to_polymorphic(Args ...args)
    {
        static_assert(std::is_constructible<Specialized, Args...>::value,
        "Cannot instantiate Specialized from arguments");

        return to_polymorphic<Base,Specialized>(
            std::move(Specialized{std::forward<Args...>(args...)}));
    }

    template<typename Base> using polymorphic_vector =
    std::vector<polymorphic<Base>>;

    template<typename Base, typename ...Args>
    polymorphic_vector<Base> to_polymorphic_vector(Args&& ...args)
    {
        return polymorphic_vector<Base>{to_polymorphic<Base>(args)...};
    }

} // stdex

Example use:

stdex::polymorphic_vector<view> views = // explicit type for clarity
    stdex::to_polymorphic_vector(
        echo_view{"/echo"}, // class echo_view : public view
        directory_view{"/static_files"} // class directory_view : public view
    );

for(auto& v: views)
    if(v.matches(reuqest.url())) // bool view::matches(...);
        auto response = view.handle(request); // virtual view::handle(...) = 0;

Limitations of this:

If you use multiple inheritance DO NOT USE stdex::details::polymorphic_clone. Write an implementation based on dynamic_cast instead, and use to_polymorphic(Specialized&& temp, CF functor).

Answer 4

If you want to use the default behavior for part of your class, and only enhance it with non-standard behavior for the rest, consider functionally and organisationally splitting your class:

Put all those elements where you want the default-behavior into their own sub-object (inherited or composited), so you can easily use the default-special-function for them, and add the rest outside that sub-object.

Implementation left as an exercise for the interested reader.