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

Question

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.

Answer 1

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

• Recursive containers
• Type Erasure

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.”</p>

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;
}