使用带有boost变量的声明进行递归 [英] Recursive using declaration with boost variant

问题描述

我试图表示一种树状递归数据结构，其中每个节点可能是两种不同数据类型之一。我使用boost变体来容纳每个节点上可能出现的两种类型。

I am trying to represent a tree-like recursive data structure where each node may be one of two different data types. I employ the boost variant to "house" the two types that might be present at each node.

但是，我遇到了一个问题。我要严格使用'using'指令声明所有这些类型，所以当我了解节点的递归性质时，由于typedef / using可能不使用递归，所以它会失败。

However, I run into a problem. I'm declaring all these types strictly with 'using' directives, so when I get to the recursive nature of a node, it fails since typedef/using may not use recursion.

如何完成此操作？

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或LeafNode组成的单个变体时，它将在变体中生成一个变体。

I have explored using the boost::make_recursive_variant but the type it creates (A) is not quite what I need, as that makes a variant within a variant when instead I want a (B) single variant consisting of either an InnerNode or LeafNode.

(A) boost_variant<boost_variant<InnerNode, LeafNode>, LeafNode>
(B) boost_variant<InnerNode, LeafNode>

推荐答案

简单答案（请参见下面的提示）

您可以使用 make_recursive_variant ：

在Coliru上直播

#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 {} },
    };
}

TIPS

为什么要完全区分内叶节点？在我看来，叶节点只是具有值而不是子节点的节点：

TIPS

Why distinguish inner/leaf nodes at all? Seems to me leaf nodes are just nodes with a value instead of children:

在Coliru上直播

#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 {} },
    };
}

不带递归变量

您可以通过判断充分的前瞻性声明：

Without Make-Recursive-Variant

You can with a well judged forward declare:

在Coliru上直播

#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 。

More Elegant + More Efficient

If you use an unordered_map that can be instantiated when the mapped-type is still incomplete¹, you don't need the performance hit of recursive_wrapper at all.

在此过程中，我们可以使构造函数更智能，树的构造更加简洁：

In the process, we can make the constructor smarter and the tree construction even more succinct:

在Coliru上直播

#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将其添加到标准库规范中）

---

¹ (I think c++17 added that to the standard library specs)

这篇关于使用带有boost变量的声明进行递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！