5

私は C++ を使用してstd::multimapおり、2 つの異なるキーをループする必要があります。2 つの範囲を作成し、それらの範囲を別々にループする以外に、これを行う効率的な方法はありますか?

これは私が今やっている方法です：

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range;
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2;

// get the range of String key
range = multimap.equal_range(key1);
range2 = multimap.equal_range(key2);

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it)
{
    ...
}
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}
4

3 に答える 3

3

もちろん、ブーストはこれを行います。Boost.Range とそのjoin機能を使用すると、必要なものが得られます。詳細については、ブースト範囲ライブラリ: 2 つの範囲を順次トラバースするを参照してください。

于 2011-09-07T15:29:56.080 に答える
3

最初に使用したコードは最も単純です。

同じループで 2 つの範囲を反復処理したい場合は、2 つの反復子範囲を取り、最初の範囲を反復し、完了するまで 2 番目の範囲に切り替えるカスタム反復子を作成できます。すべての反復子メンバーを自分で実装する必要があるため、これはおそらく価値があるよりも面倒です。

編集：私はこれを考えすぎていました。2 つのループを 1 つのループに変更するのは簡単です。

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it)
{
    if (it == range.second)
    {
        it = range2.first;
        if (it == range2.second)
            break;
    }
    ...
}
于 2011-09-07T15:27:06.580 に答える
0

C++-11 (Visual Studio 10+、gcc-4.5+) にアクセスでき、使用が許可されている場合autoは、真の宝石です。

// get the range of String key
auto range = multimap.equal_range(key1);
auto range2 = multimap.equal_range(key2);

for (auto it = range.first; it != range.second; ++it)
{
    ...
}
for (auto it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

とにかく、キーをテストして、key2 != key1 の場合にのみ 2 番目のループを実行します。ループ内で毎回イテレータをチェックすると、いくらかコストがかかります。

最初の範囲と 2 番目の範囲の std::set_difference により、コードが合理化される場合があります。2 つの範囲を std::set_union し、back_inserter を介してセットに挿入して、コピーを 1 つだけ取得するのでしょうか。

いくつかの実験が順調に進んでいる可能性があります。最初の推測をミックスに入れることを忘れないでください。速度の点でちょうど良いことに驚くかもしれません。通常、範囲が非常に長いか、ループ操作にコストがかかる場合を除き、余分な簿記の頭痛の種になる価値はありません。

于 2011-09-07T19:38:57.203 に答える