C++ 使用 std::pair 模板特化定义树节点数据结构

Question

考虑以下 (C++) 代码

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

当我编译时，编译器告诉我 std::pair<_T1, _T2>::second 的类型不完整(以及其他错误)，我认为这是我在 B 中声明它的错误，但我没有知道我应该如何正确地做到这一点。

Answer 1

我认为标准库一般不(必须)支持不完整的类型。

不过，据我所知，Boost Container 库明确支持这一点:

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

Boost.Container 提供的所有容器都可以用来定义递归容器。

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