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の素朴な実装：ノードはそれ自体のリストを拡張します

  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インスタンス化するには、が完了している必要があります。ExtendedValuestd::map

以下を使用して、タイプセーフ性の低いバージョンを作成できるはずです。

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

Valueマップに入力するすべてにタイプまたはが含まれている限り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 に答える