c++ - 在 C++ 中转换树

Question

我有一个由不同类型的节点组成的异构 n 叉树，例如:

class Node { }

class Subnode1 : public Node
{

}

class Subnode2 : public Node
{
private:
  unique_ptr<Subnode1> child;

public:
  Subnode1* getChild() { return child.get(); }
}

class Subnode4 : public Subnode2 { }

class Subnode3 : public Node
{
private:
  list<unique_ptr<Subnode2>> children;
public:
  // getter
}

// etc

该结构可以包含任意数量的节点类型，将来会扩展。

我实现了一种访问树的方法，它允许我自定义访问每个节点时要执行的操作，这基本上是以这种方式实现的:

void genericVisit(Node* node) {
  if (dynamic_cast<Subnode2>(node))
    visit(static_cast<Subnode2*>(node));
  // etc
}

virtual void visit(Subnode2* node) {
  if (node->getChild())
    genericVisit(node->getChild());
}

// etc

它很好地遍历树，但现在我需要能够用其他子树替换子树，所以我正在考虑在不改变结构太多的情况下遵循的最佳方法。

最好的解决方案是让 getter 直接返回 unique_ptr<Subnode2>&这样我就可以访问唯一指针，并且可以在访问智能指针时更改它的内容。这会起作用但是unique_ptr不是多态的，并且无法将调用分派(dispatch)给最专门的方法，例如:

void genericVisit(unique_ptr<Node>& node) { // NON WORKING CODE
  if (dynamic_cast<unique_ptr<Subnode2>&>(node))
    visit(static_cast<unique_ptr<Subnode2>&>(node));
  // etc
}

所以我想知道这可能是解决问题的最佳方法，注意在遍历树时，只要我更改当前子树的内容而不更改父节点中对该节点的引用，(这将是通过使用 unique_ptr 允许)我没有看到任何问题。

Answer 1

因为我认为评论不足以传达所有信息:

@Jack you can (Sean Parent: should) use shared_pointer<const Node> there, and copy as required for changes. Immutability for the win! That said, perhaps you can do without the inheritance altogether? Make things simpler and potentially more efficient – sehe 6 hours ago

我想我会以相反的顺序稍微演示一下这两个方面:

1. 关于对树使用静态多态性:让我们定义一棵树，其中叶节点可以是字符串或用户定义的结构:

   struct Data {
       double x,y,z;
   };
   
   using Node = make_recursive_variant<std::string, Data, std::vector<recursive_variant_> >::type;
   using Nodes = std::vector<Node>;
   

   下面所有测试中使用的示例树现在定义为:

   Node tree = Nodes {
       "hello",
       Data { 1,2,3 },
       Nodes {
           "more nested",
           Nodes {
               Data { 2,3,4 },
               Data { 3,4,5 },
               Data { 4,5,6 },
           },
           "nodes"
       }
   };
   

   Boost Variant 非常适合通过访问进行转换。例如，让我们编写一个访问者来反转树中的所有 节点，因此包括字符串和Data{x,y,z}。 -> Data{z,y,x} :

   struct reverser : static_visitor<Node> {
       Node operator()(Node const& tree)      const { return apply_visitor(*this, tree); }
       Node operator()(std::string const& s)  const { return std::string(s.rbegin(), s.rend()); }
       Node operator()(Data const& d)         const { return Data {d.z, d.y, d.x}; }
       Node operator()(Nodes const& children) const {
           Nodes revchildren;
           std::transform(children.rbegin(), children.rend(), back_inserter(revchildren), *this);
           return revchildren;
       }
   };
   
   Node reverse(Node const& tree) {
       return reverser()(tree);
   }
   

   查看现阶段的简化演示 Live On Coliru

   • 我添加了一个 print访客，以便您可以看到结果是什么
   • 它甚至对树进行往返测试 ( tree == reverse(reverse(tree)) )

   ---

2. 现在您会注意到 1. 下的树具有值语义，这意味着反向操作会生成一个完全独立的树拷贝。

   我继续并添加了一个类似的 SharedTree :

   using SNode = boost::shared_ptr<
           boost::make_recursive_variant<
               std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_>
           > >::type>;
   
   using Node  = SNode::element_type;
   using Nodes = std::vector<SNode>;
   

   当您操作这些树的拷贝时，两个拷贝都会发生变化，因为它们共享节点(下面的演示程序将一个节点添加到一个 SharedTree 并观察到另一个也发生变化)

3. 现在是 Sean Parent方法:使用 shared_ptr<T const>

   namespace CowTree {
       using SNode = boost::shared_ptr<
               boost::make_recursive_variant<
                   std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_ const>
               > >::type const>;
   
       using Node  = SNode::element_type;
       using Nodes = std::vector<SNode>;
   }
   

   这样做的好处是制作拷贝的成本很低，但是您不可能修改节点:您总是必须深度复制子树才能修改其值的任何方面。为了证明这一点，我做了一个大写的转换 string叶节点，其他一切保持不变:

   template <typename SNode, typename Nodes = std::vector<SNode> >
   struct upper_caser : boost::static_visitor<SNode> {
       SNode operator()(SNode const& tree)            const { 
           return apply_visitor(boost::bind(*this, boost::ref(tree), _1), *tree); 
       }
       // dispatch
       SNode operator()(SNode const&, std::string const& value) const {
           std::string xformed;
           std::transform(value.begin(), value.end(), back_inserter(xformed), [](uint8_t c) { return std::toupper(c); });
           return boost::make_shared<typename SNode::element_type>(xformed);
       }
       SNode operator()(SNode const& node, Nodes const& children)  const {
           Nodes xformed; // TODO optimize
           std::transform(children.begin(), children.end(), back_inserter(xformed), *this);
   
           return (equal(children, xformed))
               ? node
               : boost::make_shared<typename SNode::element_type>(xformed);
       }
       template <typename V> SNode operator()(SNode const& node, V const&) const {
           return node;
       }
   };
   
   template <typename SNode>
   SNode ucase(SNode const& tree) {
       return upper_caser<SNode>()(tree);
   }
   

   如您所见，转换是完全通用的，可以与 SharedTree 一起使用与 CowTree 一样好- 因为没有任何值(value)会发生变化。显然，使用 CowTree更安全，因为它保证了不变性。

   测试程序主动检查

   • 原文cow当我们得到它时树不会改变 ucased转变。
   • 它还会检查未更改的子树是否确实共享(未被克隆)

---

完整程序

Live On Coliru

#include <boost/variant.hpp>

namespace Tree {
    struct Data {
        double x,y,z;
    };

    using Node  = boost::make_recursive_variant<std::string, Data, std::vector<boost::recursive_variant_> >::type;
    using Nodes = std::vector<Node>;

    namespace Operations {
        struct reverser : boost::static_visitor<Node> {
            Node operator()(Node const& tree)       const { return apply_visitor(*this, tree); }
            Node operator()(Data const& d)          const { return Data {d.z, d.y, d.x}; }
            Node operator()(std::string const& s)   const { return std::string(s.rbegin(), s.rend()); }
            Node operator()(Nodes const& children)  const {
                Nodes revchildren;
                std::transform(children.rbegin(), children.rend(), back_inserter(revchildren), *this);
                return revchildren;
            }
        };

        Node reverse(Node const& tree) {
            return reverser()(tree);
        }
    }

    using Operations::reverse;
}

// For our demo, let's implement `operator <<` with a manipulator
#include <iostream>
namespace IO {
    namespace detail {
        using namespace boost;

        // this pretty prints the tree as C++ initializer code
        struct print_visitor : static_visitor<void> {
            print_visitor(std::ostream& os, std::string const& indent = "\n") : _os(os), _indent(indent) {}

            // concrete types
            void operator()(std::string const& s)  const { _os << '"' << s << '"'; }
            void operator()(Tree::Data const& d)   const { _os << "Data {" << d.x << "," << d.y << "," << d.z << '}'; }

            // generics to cater for both direct and shared tree nodes
            template <typename T>     void operator()(shared_ptr<T> const& sp)       const { (*this)(*sp); }
            template <typename T>     void operator()(shared_ptr<const T> const& sp) const { (*this)(*sp); }
            template <typename... Ts> void operator()(variant<Ts...> const& tree)    const { apply_visitor(*this, tree); }

            template <typename Node>
            void operator()(std::vector<Node> const& children) const {
                _os << "Nodes {";

                print_visitor subnode(_os, _indent + "  ");
                for(auto& n : children) {
                    _os << subnode._indent;
                    subnode(n);
                    _os << ",";
                }

                _os << _indent << '}';
            }
        private:
            std::ostream& _os;
            mutable std::string _indent;
        };

        template <typename NodeType>
        struct print_manip {
            print_manip(NodeType const& n) : _node(n) {}
            friend std::ostream& operator<<(std::ostream& os, print_manip const& m) {
                return print_visitor(os)(m._node), os << ";";
            }

            private:
            NodeType const& _node;
        };
    }

    template <typename NodeType>
        detail::print_manip<NodeType> print(NodeType const& node) { 
            return node; 
        }
}

#include <boost/make_shared.hpp>

namespace Support {
    namespace detail {
        template <typename SNode, typename Nodes = std::vector<SNode> >
        struct share_visitor : boost::static_visitor<SNode> {
            SNode operator()(Tree::Node const& tree)      const { return apply_visitor(*this, tree); }

            SNode operator()(Tree::Nodes const& children) const {
                Nodes shared;
                std::transform(children.begin(), children.end(), back_inserter(shared), *this);
                return boost::make_shared<typename SNode::element_type>(shared);
            }

            template <typename LeafNode>
            SNode operator()(LeafNode const& v) const { return boost::make_shared<typename SNode::element_type>(v); }
        };
    }
}

#include <boost/bind.hpp>

namespace SharedTree {
    using Tree::Data;

    using SNode = boost::shared_ptr<
            boost::make_recursive_variant<
                std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_>
            > >::type>;

    using Node  = SNode::element_type;
    using Nodes = std::vector<SNode>;

    namespace Operations {
        template <typename SNode, typename Nodes = std::vector<SNode> >
        struct upper_caser : boost::static_visitor<SNode> {
            SNode operator()(SNode const& tree)            const { 
                return apply_visitor(boost::bind(*this, boost::ref(tree), _1), *tree); 
            }
            // dispatch
            SNode operator()(SNode const&, std::string const& value) const {
                std::string xformed;
                std::transform(value.begin(), value.end(), back_inserter(xformed), [](uint8_t c) { return std::toupper(c); });
                return boost::make_shared<typename SNode::element_type>(xformed);
            }
            SNode operator()(SNode const& node, Nodes const& children)  const {
                Nodes xformed; // TODO optimize
                std::transform(children.begin(), children.end(), back_inserter(xformed), *this);

                return (equal(children, xformed))
                    ? node
                    : boost::make_shared<typename SNode::element_type>(xformed);
            }
            template <typename V> SNode operator()(SNode const& node, V const&) const {
                return node;
            }
        };

        template <typename SNode>
        SNode ucase(SNode const& tree) {
            return upper_caser<SNode>()(tree);
        }
    }

    using Operations::ucase;

    SNode share(Tree::Node const& tree) {
        return Support::detail::share_visitor<SNode>()(tree);
    }
}

namespace CowTree {
    using Tree::Data;

    using SNode = boost::shared_ptr<
            boost::make_recursive_variant<
                std::string, Data, std::vector<boost::shared_ptr<boost::recursive_variant_ const>
            > >::type const>;

    using Node  = SNode::element_type;
    using Nodes = std::vector<SNode>;

    SNode share(Tree::Node const& tree) {
        return Support::detail::share_visitor<SNode>()(tree);
    }
}

#include <boost/lexical_cast.hpp> // for the roundtrip test

namespace Support {
    template <typename NodeType1, typename NodeType2>
    bool tree_equal(NodeType1 const& a, NodeType2 const& b) {
        using IO::print;
        return boost::lexical_cast<std::string>(print(a)) == 
            boost::lexical_cast<std::string>(print(b));
    }
}

int main() {
    using namespace Tree;
    using IO::print;
    using Support::tree_equal;

    Node tree = Nodes {
        "hello",
        Data { 1,2,3 },
        Nodes {
            "more nested",
            Nodes {
                Data { 2,3,4 },
                Data { 3,4,5 },
                Data { 4,5,6 },
            },
            "nodes"
        }
    };

    std::cout << "Before transformation: \n" << print(tree)          << "\n";
    std::cout << "After transformation:  \n" << print(reverse(tree)) << "\n";

    Node roundtrip = reverse(reverse(tree));
    std::cout << "Roundtrip tree_equal: "    << std::boolalpha       << tree_equal(tree, roundtrip) << "\n";

    std::cout << "//////////////////////////////////////////////////\n";
    std::cout << "// manipulate SharedTree \"copies\"\n";
    auto shared = SharedTree::share(tree);
    std::cout << "Shared: "          << print(shared)            << "\n";
    std::cout << "Equal to source: " << tree_equal(tree, shared) << "\n";

    auto shared2 = shared;

    using boost::get;
    using boost::make_shared;
    get<SharedTree::Nodes>(*shared).push_back(make_shared<SharedTree::Node>("added to a shared tree"));

    std::cout << "Shared2 after changing shared: " << print(shared2)              << "\n";
    std::cout << "Shared trees equal: "            << tree_equal(shared, shared2) << "\n";
    std::cout << "Not equal to source: "           << tree_equal(tree, shared)    << "\n";

    std::cout << "//////////////////////////////////////////////////\n";
    std::cout << "// now let's see about CowTree\n";
    auto cow = CowTree::share(tree);
    std::cout << "Cow: "                 << print(cow)            << "\n";
    std::cout << "Equal to source: "     << tree_equal(tree, cow) << "\n";

    auto ucased = SharedTree::ucase(cow);
    std::cout << "Ucased: "              << print(ucased)           << "\n";
    std::cout << "Equal to cow source: " << tree_equal(ucased, cow) << "\n";

   /*
    *    The 
    *
    *        Nodes {
    *            Data { 2,3,4 },
    *            Data { 3,4,5 },
    *            Data { 4,5,6 },
    *        },
    *
    *    subtree should still be shared, because it wasn't touched:
    */
    std::cout << "Subtree from ucased: " << print(get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1]) << "\n";
    std::cout << "Subtree from cow: "    << print(get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow   )[2])[1]) << "\n";
    std::cout << "Subtrees match: "      << tree_equal(
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1],
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[1])
        << "\n";
    // unchanged nodes should be shared:
    std::cout << "Subtrees shared: " << (
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[1].get() ==
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[1].get())
        << "\n";
    // changed nodes aren't shared:
    std::cout << "Siblings unshared: " << (
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*ucased)[2])[2].get() !=
            get<CowTree::Nodes>(*get<CowTree::Nodes>(*cow)   [2])[2].get())
        << "\n";
    std::cout << "Parents unshared: " << (
            get<CowTree::Nodes>(*ucased)[2].get() !=
            get<CowTree::Nodes>(*cow)   [2].get())
        << "\n";
    std::cout << "Roots unshared: " << ( ucased.get() != cow.get())
        << "\n";
}

输出:

Before transformation: 
Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
After transformation:  
Nodes {
  Nodes {
    "sedon",
    Nodes {
      Data {6,5,4},
      Data {5,4,3},
      Data {4,3,2},
    },
    "detsen erom",
  },
  Data {3,2,1},
  "olleh",
};
Roundtrip tree_equal: true
//////////////////////////////////////////////////
// manipulate SharedTree "copies"
Shared: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
Equal to source: true
Shared2 after changing shared: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
  "added to a shared tree",
};
Shared trees equal: true
Not equal to source: false
//////////////////////////////////////////////////
// now let's see about CowTree
Cow: Nodes {
  "hello",
  Data {1,2,3},
  Nodes {
    "more nested",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "nodes",
  },
};
Equal to source: true
Ucased: Nodes {
  "HELLO",
  Data {1,2,3},
  Nodes {
    "MORE NESTED",
    Nodes {
      Data {2,3,4},
      Data {3,4,5},
      Data {4,5,6},
    },
    "NODES",
  },
};
Equal to cow source: false
Subtree from ucased: Nodes {
  Data {2,3,4},
  Data {3,4,5},
  Data {4,5,6},
};
Subtree from cow: Nodes {
  Data {2,3,4},
  Data {3,4,5},
  Data {4,5,6},
};
Subtrees match: true
Subtrees shared: true
Siblings unshared: true
Parents unshared: true
Roots unshared: true