C++ Defining Tree Node Data Structure with std::pair Template Specialization

2
votes

Consider the following (C++) code

class A {...};

namespace std
{
    template<>
    struct hash<A>
    {
        size_t operator() (const A& a) const
        {
            // returns unique hash based on components of A
        };
    };
}

class B
{
    std::unordered_map<A, B> *children; //ignore the fact that its a pointer for now
};

When I compile, the compiler tells me that std::pair<_T1, _T2>::second has incomplete type (among other errors), which I assume is my fault for declaring it in B, however I don't know how I should do it correctly.

1
c++c++11stl
can you provide the code you are trying to compile? including the definition of B? – user1708860
Please provide executable example. – zch
@sehe Actually I realized that my example is too generic. If I create an executable example using this, it compiles, so I need to pinpoint more specifically. I will do my best to narrow it down – bathtub

1 Answers

4
votes

I think the standard library doesn't in general (have to) support incomplete types.

As I remember, Boost Container library explicitely supports this, though:

Containers of Incomplete Types

What about standard containers? Containers of incomplete types have been under discussion for a long time, as explained in Matt Austern's great article (The Standard Librarian: Containers of Incomplete Types):

“Unlike most of my columns, this one is about something you can't do with the C++ Standard library: put incomplete types in one of the standard containers. This column explains why you might want to do this, why the standardization committee banned it even though they knew it was useful, and what you might be able to do to get around the restriction.”

All containers offered by Boost.Container can be used to define recursive containers.

See it Live on Coliru

#include <boost/container/vector.hpp>
#include <boost/container/list.hpp>
#include <boost/container/map.hpp>
#include <boost/container/stable_vector.hpp>
#include <boost/container/string.hpp>

using namespace boost::container;

struct data
{
   int               i_; 
   vector<data>      v_; //A vector holding still undefined class 'data'
   list<data>        l_; //A list holding still undefined 'data'
   map<data, data>   m_; //A map holding still undefined 'data'

   friend bool operator <(const data &l, const data &r)
   { return l.i_ < r.i_; }
};

struct tree_node
{
   string name;
   string value;

   //children nodes of this node
   list<tree_node>        children_;
};

int main()
{
   //a container holding a recursive data type
   stable_vector<data> sv;
   sv.resize(100);

   //Let's build a tree based in
   //a recursive data type
   tree_node root;
   root.name  = "root";
   root.value = "root_value";
   root.children_.resize(7);
   return 0;
}