我试图表示一个树状递归数据结构,其中每个节点可能是两种不同数据类型之一。我使用 boost 变体来“容纳”每个节点上可能存在的两种类型。
但是,我遇到了一个问题。我严格使用“using”指令声明所有这些类型,因此当我了解节点的递归性质时,它会失败,因为 typedef/using 可能不使用递归。
如何实现这一目标?
using LeafData = int; // just for illustration
using LeafNode = std::unordered_map<std::string, LeafData>;
using InnerNode = std::unordered_map<std::string, boost_variant<InnerNode, LeafNode>>; // this is problematic since I'm using InnerNode recursively
我已经探索过使用 boost::make_recursive_variant 但它创建的类型 (A) 并不完全是我所需要的,因为这在变体中创建了一个变体,而我想要一个 (B) 由 InnerNode 组成的单个变体或叶节点。
(A) boost_variant<boost_variant<InnerNode, LeafNode>, LeafNode>
(B) boost_variant<InnerNode, LeafNode>
最佳答案
直接回答(请参阅下面的提示)
您可以使用 make_recursive_variant
做您想做的事:
#include <boost/variant.hpp>
#include <unordered_map>
struct LeafData {
int _i;
LeafData(int i) : _i(i) {}
}; // just for illustration
using LeafNode = std::unordered_map<std::string, LeafData>;
using Node = boost::make_recursive_variant<
LeafNode,
std::unordered_map<std::string, boost::recursive_variant_>
>::type;
using Inner = std::unordered_map<std::string, Node>;
int main() {
Node tree = Inner {
{ "a", LeafNode { { "one", 1 }, { "two", 2 }, { "three",3 } } },
{ "b", Inner {
{ "b1", LeafNode { { "four", 4 }, { "five", 5 }, { "six", 6 } } },
{ "b2", LeafNode { { "seven", 7 }, { "eight", 8 }, { "nine", 9 } } },
}
},
{ "c", LeafNode {} },
};
}
提示
为什么要区分内部节点/叶节点?在我看来,叶节点只是具有值而不是子节点的节点:
#include <boost/variant.hpp>
#include <unordered_map>
struct Data {
int _i;
Data(int i) : _i(i) {}
}; // just for illustration
using Tree = boost::make_recursive_variant<
Data,
std::unordered_map<std::string, boost::recursive_variant_>
>::type;
using Node = std::unordered_map<std::string, Tree>;
int main() {
Tree tree = Node {
{ "a", Node { { "one", 1 }, { "two", 2 }, { "three",3 } } },
{ "b", Node {
{ "b1", Node { { "four", 4 }, { "five", 5 }, { "six", 6 } } },
{ "b2", Node { { "seven", 7 }, { "eight", 8 }, { "nine", 9 } } },
}
},
{ "c", Node {} },
};
}
没有 Make-Recursive-Variant
您可以通过良好判断的前向声明:
#include <boost/variant.hpp>
#include <unordered_map>
struct Data {
int _i;
Data(int i) : _i(i) {}
}; // just for illustration
struct Node;
using Tree = boost::variant<Data, boost::recursive_wrapper<Node> >;
struct Node : std::unordered_map<std::string, Tree> {
using base = std::unordered_map<std::string, Tree>;
using base::base; // inherit constructor
};
int main() {
Tree tree = Node {
{ "a", Node { { "one", 1 }, { "two", 2 }, { "three",3 } } },
{ "b", Node {
{ "b1", Node { { "four", 4 }, { "five", 5 }, { "six", 6 } } },
{ "b2", Node { { "seven", 7 }, { "eight", 8 }, { "nine", 9 } } },
}
},
{ "c", Node {} },
};
}
更优雅+更高效
如果您使用 unordered_map
当映射类型仍然不完整时可以实例化,您不需要 recursive_wrapper
的性能影响完全没有。
在这个过程中,我们可以让构造函数更加智能,让树的构造更加简洁:
#include <boost/variant.hpp>
#include <boost/unordered_map.hpp>
struct Data {
int _i;
Data(int i = 0) : _i(i) {}
}; // just for illustration
struct Node : boost::variant<Data, boost::unordered_map<std::string, Node> > {
using Map = boost::unordered_map<std::string, Node>;
using Base = boost::variant<Data, Map>;
using Base::variant;
using Base::operator=;
Node(std::initializer_list<Map::value_type> init) : Base(Map(init)) {}
};
int main() {
auto tree = Node {
{ "a", { { "one", 1 }, { "two", 2 }, { "three", 3 } } },
{ "b", {
{ "b1", { { "four", 4 }, { "five", 5 }, { "six", 6 } } },
{ "b2", { { "seven", 7 }, { "eight", 8 }, { "nine", 9 } } },
}
},
{ "c", {} },
};
}
(我认为 c++17 将其添加到标准库规范中)
关于c++ - 带有 boost 变体的递归 using 声明,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48122683/