I'm limited to C++17. I need to make a tree structure (not necessarily binary) that can be deep copied into 2 independent clones. Currently, I have an interface Node class where there's 2 implementations:

1. An Operation class holds an enum representing the boolean operation to perform on its std::vector<std::unique_ptr<Node>> operands. These make up the branches in the tree.

2. A Condition class holds the data that will be compared when it's told to evaluate. These make up the leaves in the tree.

Lastly, I have an Event class with a std::unique_ptr that points to the root Node of this tree. Both an Operation or Condition may be the root of the tree.

I've followed this blog post in regard to properly cloning a std::unique_ptr, but I don't quite know how to maintain the polymorphic part of the Event and Operation classes' copy constructors. Is having these copy constructors an inherent part of my problem?

#include <algorithm>
#include <memory>
#include <string>
#include <vector>

namespace tree
{
struct Node
{
    // Virtual clone function to make a new std::unique_ptr
    // with a copy of the contents of the old std::unique_ptr
    // Both std::unique_ptrs will be independent of each other
    virtual std::unique_ptr<Node> clone() const = 0;

    std::string name;
};

enum class Boolean
{
    And,
    Or,
    Xor
};

struct Operation : public Node
{
    // Copy constructor (because copying a std::vector is non-trivial)
    // that will allocate a new std::vector of the same size and clone
    // new std::unique_ptrs from the other std::vector
    Operation(const Operation &other) : op(other.op), nodes(other.nodes.size())
    {
        std::transform(other.nodes.cbegin(), other.nodes.cend(), nodes.begin(),
            [](const auto &old) {
                // This line has the compilation error because Node is abstract,
                // but I need this for the polymorphism, correct?
                return op ? std::make_unique<Node>(old->clone()) : nullptr;
            });
    }
    
    // Clones this class
    virtual std::unique_ptr<Node> clone() const override
    {
        return std::make_unique<Operation>(*this);
    }
    
    Boolean op;
    // Can hold any number of other Operation or Condition objects
    std::vector<std::unique_ptr<Node>> nodes;
};

struct Condition : public Node
{
    // Clones this class
    virtual std::unique_ptr<Node> clone() const override
    {
        return std::make_unique<Condition>(*this);
    }
    
    int datum;
};

struct Event
{
    Event(std::string name) : name(name) {}
    // This line has the same compilation error
    Event(const Event &other) : name(other.name), root(std::make_unique<Node>(other.root->clone())) {}
    std::string name;
    std::unique_ptr<Node> root;
};
} // tree

I'm limited to C++17. I need to make a tree structure (not necessarily binary) that can be deep copied into 2 independent clones. Currently, I have an interface Node class where there's 2 implementations:

1. An Operation class holds an enum representing the boolean operation to perform on its std::vector<std::unique_ptr<Node>> operands. These make up the branches in the tree.

2. A Condition class holds the data that will be compared when it's told to evaluate. These make up the leaves in the tree.

Lastly, I have an Event class with a std::unique_ptr that points to the root Node of this tree. Both an Operation or Condition may be the root of the tree.

I've followed this blog post in regard to properly cloning a std::unique_ptr, but I don't quite know how to maintain the polymorphic part of the Event and Operation classes' copy constructors. Is having these copy constructors an inherent part of my problem?

#include <algorithm>
#include <memory>
#include <string>
#include <vector>

namespace tree
{
struct Node
{
    // Virtual clone function to make a new std::unique_ptr
    // with a copy of the contents of the old std::unique_ptr
    // Both std::unique_ptrs will be independent of each other
    virtual std::unique_ptr<Node> clone() const = 0;

    std::string name;
};

enum class Boolean
{
    And,
    Or,
    Xor
};

struct Operation : public Node
{
    // Copy constructor (because copying a std::vector is non-trivial)
    // that will allocate a new std::vector of the same size and clone
    // new std::unique_ptrs from the other std::vector
    Operation(const Operation &other) : op(other.op), nodes(other.nodes.size())
    {
        std::transform(other.nodes.cbegin(), other.nodes.cend(), nodes.begin(),
            [](const auto &old) {
                // This line has the compilation error because Node is abstract,
                // but I need this for the polymorphism, correct?
                return op ? std::make_unique<Node>(old->clone()) : nullptr;
            });
    }
    
    // Clones this class
    virtual std::unique_ptr<Node> clone() const override
    {
        return std::make_unique<Operation>(*this);
    }
    
    Boolean op;
    // Can hold any number of other Operation or Condition objects
    std::vector<std::unique_ptr<Node>> nodes;
};

struct Condition : public Node
{
    // Clones this class
    virtual std::unique_ptr<Node> clone() const override
    {
        return std::make_unique<Condition>(*this);
    }
    
    int datum;
};

struct Event
{
    Event(std::string name) : name(name) {}
    // This line has the same compilation error
    Event(const Event &other) : name(other.name), root(std::make_unique<Node>(other.root->clone())) {}
    std::string name;
    std::unique_ptr<Node> root;
};
} // tree

• c++
• c++17
• polymorphism
• unique-ptr

• 1 Re: "This line has the same compilation error" - Event doesn't have a member variable named b – Ted Lyngmo Commented 14 hours ago
• Do these pointers really need to be unique? I can't answer that question, but you need to think about it. – Tim Roberts Commented 14 hours ago
• 2 I'd guess that std::make_unique<Node>(op->clone()) should just be op->clone() – Alan Birtles Commented 14 hours ago
• I'm limited to C++17. praise all the deities you know, even the ones you don't like. I often don't get to use anywhere close to C++17 – user4581301 Commented 14 hours ago
• 1 In the Event copy constructor, root(std::make_unique<Node>(other.root->clone())) should be root(other.root->clone()) – Remy Lebeau Commented 14 hours ago

2 Answers 2

You already know how to clone a polymorphic object. You just need to use the cloning functionality correctly in your copy constructors. You should not be using std::make_unique<Node>() to copy a clone, just use the clone as-is, eg:

struct Operation : public Node
{
    ...

    Operation(const Operation &other) : ..., nodes(other.nodes.size())
    {
        std::transform(other.nodes.cbegin(), other.nodes.cend(), nodes.begin(),
            [](const auto &node) -> std::unique_ptr<Node> {
                return node ? node->clone() : nullptr;
            }
    }
    
    ...
};

struct Event
{
    ...

    Event(const Event &other) : ..., root(other.root ? other.root->clone() : nullptr) {}

    ...
};

Alternatively, you can use a helper function to make the cloning a little cleaner:

// helper
std::unique_ptr<Node> cloneNode(const std::unique_ptr<Node> &node) {
    return node ? node->clone() : nullptr;
}


struct Operation : public Node
{
    ...

    Operation(const Operation &other) : ..., nodes(other.nodes.size())
    {
        std::transform(other.nodes.cbegin(), other.nodes.cend(), nodes.begin(), cloneNode);
    }
    
    ...
};

struct Event
{
    ...

    Event(const Event &other) : ..., root(cloneNode(other.root)) {}

    ...
};

std::make_unique<Node> needs Node to be complete, because it has to look for Nodes constructors. But Node is abstract and can't be constructed by itself.

Move construction of a std::unique_ptr<Node>, on the other hand, merely copies a pointer.

Change the line to:

return op ? op->clone() : nullptr;

And similar for the other line.

Live Demo