2

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.

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.

How to accomplish this?

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

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>
rkemp
  • 278
  • 3
  • 14

3 Answers3

4

Straight Answer (see below for tips)

You can do what you want you want using make_recursive_variant:

Live On 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

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

Live On 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:

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

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:

Live On 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", {} },
    };
}

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

sehe
  • 374,641
  • 47
  • 450
  • 633
  • Thank you for the detailed response. In response to your TIPS, as to why LeafNodes are distinguished from InnerNodes, it is because of how I wish to construct and traverse the tree. The structure of the tree is not known ahead of time, instead it grows dynamically. Leafs actually contain a map of atomic counters, and I need to create that same set of cntrs for every leaf. It doesn't make sense for those cntrs to exist at InnerNodes, though I contemplated having diff types of cntrs at InnerNodes, but the set (map) of counters must be known ahead of time, to create a leaf if one didn't exist – rkemp Jan 08 '18 at 17:25
  • How would the last example look when I also want floats as leaf data type? – Reza Apr 09 '19 at 09:08
  • @Reza II assume your problem is with the implicit conversions between int/float? Thank the C legacy overlords for that bit of good fortune (cough). Maybe you can ease the pain using UDLs? http://coliru.stacked-crooked.com/a/e13ba6511fce0686 – sehe Apr 09 '19 at 09:46
  • @sehe I tried to [add a std::vector type](http://coliru.stacked-crooked.com/a/a4bb6dfab2d5c08e) but I fail with the initializer list. It would also be nice to have the `[]` for setting values. – Reza Apr 09 '19 at 13:22
  • @Reza how about http://coliru.stacked-crooked.com/a/4742e3ba7f00a2d9 for a start? – sehe Apr 09 '19 at 22:43
  • @Reza Or even completely implicit: http://coliru.stacked-crooked.com/a/15b57edc15bdace7. If you're looking for JSON, see e.g. https://stackoverflow.com/a/27749360/85371 Adding indexer accessors should be as simple as: http://coliru.stacked-crooked.com/a/d5a21e26aa7987d5 – sehe Apr 09 '19 at 23:06
  • How do I (randomly) access the `tree` object? I assumed since its a map, the access operator ```[]``` or some of the normal map accessors/manipulators ```at()```, ```find()``` would work, but I cannot figure it out. – mzoll Apr 07 '21 at 09:42
  • @mzoll Answered here: https://stackoverflow.com/questions/22274705/c-nested-map/22276706?noredirect=1#comment118410421_22276706 - however do keep in mind that when e.g. JSON array indexing looks like random access, it isn't in practice (barring implementation specific optimizations). Just to keep in mind. – sehe Apr 07 '21 at 14:36
0

You are going to need a pointer, the variant is either a leaf data or a pointer to another leaf.

SoronelHaetir
  • 14,104
  • 1
  • 12
  • 23
  • You have the right idea, but not the right experience for a helpful answer. Boost facilitates what you describe so you do *not* have to deal with the pointers (and the correctness/exception safety issues with that). Besides in my answer you see ways to avoid the indirection in the first place [since the chosen container is node-based and hence serves as the point of indirection]. – sehe Jan 07 '18 at 03:12
0

I was able to get the boost::make_recursive_variant approach to work, but it required an additional handler to the variant visitor.

using LeafData = int; // just for illustration
using LeafNode = std::unordered_map<std::string, LeafData>;
using InnerNode = std::unordered_map<std::string, boost::make_recursive_variant<boost::recursive_variant_, LeafNode>::type>;

The variant visitor required handling three types, LeafNode, InnerNode, AND, the InnerNode::mapped_type (which is the recursive variant), then the compiler seemed happy. Not sure if this will "work" though, so need to run and see how behaves.

rkemp
  • 278
  • 3
  • 14