1

目前我正在努力处理应该包含自己的地图。但是我不知道编译时嵌套的深度。

std::map<Key, std::map<Key, std::map<Key, std::map<Key, ...>>>>

有没有办法在不无限重复自己的情况下实现这个目标？

4

4 回答 4

7

自引用数据结构的金锤是指针的使用。在您的特定情况下，要实现一棵树，您可以这样做：

template <typename Key, typename Value>
struct Node {
   Value data;
   std::map< Key, std::shared_ptr<Node> > child;
// ...
};

树中的每个节点都包含一个值和一组Node通过共享指针映射维护的子节点。std::map要求（根据标准）存储的类型是完整的，但只shared_ptr需要类型在创建时是完整的，这允许这种数据结构。普通的Node*也可以，但是您必须手动管理内存。

于 2012-10-12T16:27:55.577 回答
1

一个简单的 xml 实现：Node 扩展了一个自身的列表

  class Node :
     public std::unordered_map< std::string, std::list< Node > >
  {
  public:

     Node( const std::string & tag_ ) : tag( tag_ ){}

     void print( const std::string & indent ) const
     {
        std::cout << indent << '<' << tag;
        if( ! attributes.empty())
        {
           for( std::unordered_map< std::string, std::string >::const_iterator it2 = attributes.begin(); it2 != attributes.end(); ++it2 )
           {
              std::cout << ' ' << it2->first << "=\"" << it2->second << "\" ";
           }
        }
        std::cout << '>' << std::endl;
        if( ! text.empty())
        {
           std::cout << indent << text << std::endl;
        }
        for( Node::const_iterator it1 = begin(); it1 != end(); ++it1 )
        {
           const std::list< Node > & lst = it1->second;
           for( std::list< Node >::const_iterator it2 = lst.begin(); it2 != lst.end(); ++it2 )
           {
              (*it2).print( indent + '\t' );
           }
        }
        std::cout << indent << "</" << tag << '>' << std::endl;
     }

     std::string                                    tag;
     std::string                                    text;
     std::unordered_map< std::string, std::string > attributes;
  };

  int _tmain(int argc, _TCHAR* argv[])
  {
     Node title( "title" );
     title.text = "Title of the html page";

     Node head( "head" );
     head["title"].push_back( title );

     Node html( "html" );
     html["head"].push_back( head );

     Node body( "body" );
     body.attributes["bgcolor"] = "#F0F0F0";
     Node p1( "p" );
     p1.text = "Creativity and imagination are limitless.";
     body["p"].push_back( p1 );
     Node p2( "p" );
     p2.text = "Don't listen to the annoying guys who say your projects are dreams";
     body["p"].push_back( p2 );
     html["body"].push_back( body );

     html.print( "" );

     /* Result:
     <html>
             <head>
                     <title>
                     Title of the html page
                     </title>
             </head>
             <body bgcolor="#F0F0F0" >
                     <p>
                     Creativity and imagination are limitless.
                     </p>
                     <p>
                     Don't listen to the annoying guys who say your projects are dreams
                     </p>
             </body>
     </html>
     */
      return 0;
  }

由于根本没有定义虚拟方法，因此不需要虚拟析构函数。

于 2012-10-12T15:48:27.110 回答
1

我不认为您可以在 C++ 中以完全类型安全的方式编写实际类型，因为实例化模板时使用的所有类型在实例化模板时必须是完整的，而您基本上需要做的就是类似：

typedef boost::variant<Value, std::map<Key, ExtendedValue> > ExtendedValue;
typedef std::map<Key, ExtendedValue> MyMap;

这会导致模板依赖关系中的递归：为了实例化std::map，ExtendedValue必须是完整的，但为了实例化ExtendedValue，std::map必须是完整的。

您应该能够使用以下方法创建类型安全性较低的版本：

typedef std::map<Key, boost::any> MyMap;

只要您放入地图的所有内容都具有类型Valueor MyMap，这应该可以工作。（我在 Java 中做过类似的事情，映射类型是Object.）

或者，您可以映射到包含指向映射的指针的 boost::variant，而不是映射本身。但是，除非您将地图包装在一个类中，否则即使这样也很难命名。您可以轻松地前向声明一个类，并使用指向它的指针，但是在至少知道模板中使用的类型之前，您不能声明模板的实例化。因此，您必须编写如下内容：

class MyMap;
typedef boost::variant<Value, MyMap*> ExtendedValue;
class MyMap : private std::map<Key, ExtendedValue>
{
public:
    using ...;
};

由于您必须使用指针，因此无论如何这可能是要走的路；然后，您可以包装您需要的成员函数，以确保正确的成员管理。（在这种情况下，类似的函数operator[]可能必须返回一个代理，以便您可以拦截写入并进行分配。）

于 2012-10-12T15:58:04.247 回答
0

缺少代数数据类型，递归变体可以满足您的需求：

using data_type = boost::make_recursive_variant<
    Value
    , std::map<Key, boost::recursive_variant_>
>::type;

LWS 上的演示。

请注意，这允许在运行时才知道“形状”（换句话说，递归深度）的值。

虽然还有其他方法可以使用 Boost.Variant 声明和使用递归类型，但我建议您查看文档以找出最适合您的情况的方法。

（特别是通过使用std::map<Value, data_type>作为顶级类型而不是data_type它本身，我禁止叶子，即形状为 的值Value。但这只是为了方便使用 的std::initializer_list构造函数std::map。）

于 2012-10-12T16:52:46.423 回答