YiFei YiFei -4 years ago 97
C++ Question

Clear initialization for nested associative container with unknown recursion levels

Basically I would like to have some container, that resembles something like

std::unordered_map<std::string, std::variant<unsigned, /*self_type*/>>
. In this container, the unsigned value is a terminal node, while the
self_type
represents a subtree, that shall be searched further until terminal node.

This could, however, be implemented with one extra wrapper class.

struct node {
std::unordered_map<std::string,
std::variant<unsigned, std::unique_ptr<node>>> children;
};


Fair enough, but I'd want to initialize it as a normal
std::unordered_map
with nested intializer list. For example:

{
{
"str1",
{
{"strstr1", 1},
{"strstr2", 2}
}
},
{"str2", 3}
}


Suggestions for a more appropriate data structure are also welcome.

Answer Source

Solution 1 - using wrapper class:

struct node {
    using myvar = boost::variant< unsigned, boost::recursive_wrapper< node > >;
    using childmap = std::unordered_map< std::string, myvar >;

    node() {}

    node( std::initializer_list< childmap::value_type > il ) :
        children( il ) {}

    childmap children;
};

I'm using boost::variant here since I don't have std::variant available. The boost::recursive_wrapper is required because boost::variant normally requires a complete type, but at this point node is still incomplete.

boost::recursive_wrapper is nothing magic. It's just a wrapper around a pointer! As we know, a pointer can be declared for an incomplete type without issues. This wrapper class just hides the fact that a pointer is used by taking care of allocation, deallocation and providing value semantics. It has special support by boost::variant that makes the wrapper completely transparent, so the variant can be used as if there is no wrapper class at all.

Usage:

node n {
    { "foo", 1 },
    { "bar", 2 },
    { "baz", node {
        { "bim", 3 },
        { "bam", 4 }}
    }
};

n.children[ "fum" ] = 5;
n.children[ "fup" ] = node{{ "fap", 6 }};

The explicit "node" in the initializer list is required because the variant contructor can't deduce the type from the nested initializer list.

Demo: http://coliru.stacked-crooked.com/a/123c59a3523c39ed

Solution 2 - deriving from unordered_map:

This removes the need for the "children" member.

struct nodemap :
    std::unordered_map< 
        std::string, 
        boost::variant< unsigned, boost::recursive_wrapper< nodemap > > >
{
    using base = std::unordered_map< 
        std::string, 
        boost::variant< unsigned, boost::recursive_wrapper< nodemap > > >;

    // Forward all constructors of the base class.
    using base::base;
};

Usage:

nodemap n{
    { "foo", 1 },
    { "bar", 2 },
    { "baz", nodemap{
        { "bim", 3 },
        { "bam", 4 }}
    }};

n[ "fum" ] = 5;
n[ "fup" ] = nodemap{{ "fap", 6 }};

More usage examples:

// Add something to a child nodemap. 
boost::get<nodemap>( n[ "baz" ] )[ "fap" ] = 7;

// This will throw a boost::bad_get exception because n[ "foo" ] is not a nodemap.
//boost::get<nodemap>( n[ "foo" ] )[ "fap" ] = 8;

// To avoid this problem, we can check if the child actually is a nodemap:
if( nodemap* pn = boost::get<nodemap>( &n[ "foo" ] ) )
{
    (*pn)[ "fap" ] = 8; 
}

Demo: http://coliru.stacked-crooked.com/a/69914ec5646129f2

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download