1

いくつかのエントリをコンテナに挿入する必要がありますが、エントリに以前に挿入されたエントリの 1 つと共通する 2 つの特定の属性がある場合、それは重複と見なされます。

トリッキーな部分は、だまされたものを見つけた場合に備えて、これらの属性値を共有するエントリをコンテナーの一部にしたくないということです (最初のものでさえ、最初に発見されたのでだめではありませんでした) .

ペアの 2 つの属性をキーとして (2 つの属性に適切に定義された operator== があると仮定して) マルチマップを使用し、すべてのエントリにインデックスを付けるための値としてエントリへのポインタを使用することを考えていました。

すべてのエントリをスキャンしてマルチマップを満たすと、マルチマップ全体を反復処理し、equal_range と std::distance を追加して、出力コンテナーに 1 回出現するエントリのみを追加します。

標準の stl コンテナとツールのみを使用するか、最終的にライブラリをブーストしたいと仮定すると、効率の点でそれを行うための最良の方法はありますか?

typedef std::pair<attribute1,attribute2> key;
multimap<key, entry*> multimap;
typedef multimap<key, entry*>::iterator MultimapIter; 

// process all the entries and fullfill the multimap

MultimapIter iter;
for(iter = multimap.begin(); iter != multimap.end(); ++iter)
{
    std::pair<MultimapIter,MultimapIter> keyRange = 
            multimap.equal_range(iter->first);

    if(std::distance(keyRange.first, keyRange.second) != 1)
        iter = --keyRange.second;
    else
        // Fill the output container with the entry
}

// Destroy the multimap
4

1 に答える 1

1

次のように、(マルチマップではなく) マップを使用します。

マイマップをマップします。
for (すべてのエントリ)
{
  ペア::反復子、ブール> res = mymap.insert(entry);
  if (!res->second)
  {
    // 値は挿入されません。重複がすでにここにある必要があります。
    // エントリ ポインタをゼロにして重複をマーク
    iter->first->second = NULL;
  }
}
// ここで、mymap からゼロ ポインターを使用してすべてのアイテムを削除すると、一意のエントリが残っているマップが作成されます。
于 2012-11-22T17:33:15.287 に答える