0

繰り返しキーがあるため、マルチマップを作成しました。しかし、後続のより高いキーが整列された新しいマルチマップを生成できるように、効率的な操作を行いたいと考えています。これが私が意味することです：

これは私が持っているものです:

key        values
11          qwer
11          mfiri
21          iernr
21          ghfnfjf
43          dnvfrf

これが私が達成したいことです

key        values
11          qwer,iernr
11          mfiri,iernr
21         iernr,dnvfrf
21          ghfnfjf,dnvfrf
43          dnvfrf

約1000万件のエントリがあるので、効率的なものを探しています。

上記の値では、「qwer,iernr」は 1 つの文字列です。

4

4 に答える 4

2

これを行う簡単な方法は次のとおりです。

auto cur = map.begin();
auto next = map.upper_bound(cur->first);

for(; next != map.end(); next = map.upper_bound(cur->first))
{
    for(; cur != next; ++cur)
    {
        cur->second += ", ";
        cur->second += next->second;
    }
}

...与えられたstd::multimap<int, std::string> map;

ただし、10m以上の要素を変換する操作は、超高速にはなりません。

于 2013-01-18T21:55:24.267 に答える
0

ユージーンに同意する！また、equal_range（） stl :: multimapに関する次のリファレンスも参照してください-データのグループを取得するにはどうすればよいですか？

于 2013-01-18T21:56:19.740 に答える
0

これを行うには、新しいマップを順番に構築しながら、マップを単純に反復処理する必要があります。

これは、次の 2 つのレベルで実行できます。

for (auto it=map.cbegin(); it != map.cend(); ) 
{ 
    // The inner loop is over all entries having the same key
    auto next_key_it=find_next_key_after(it);
    for (; it != next_key_it; ++it) {
         new_map.emplace_hint(new_map.end(), it->first, new_value(it->second, next_key_it));
    }
}

new_value 関数 (またはラムダ) は、値の変換を行います (または、2 番目のパラメーターが map.end() の場合は行わない)。

find_next_key_after(it) 関数は map.upper_bound(it->first) と同じものを返しますが、異なるキーを持つ最初のエントリの線形検索として実装することもできます。

それは、使用する（予想される）キー分布に依存します-キーが限られた回数だけ繰り返される場合、線形検索の方が優れています。異なるキーの数が制限されていて、キーの範囲が等しい場合は、upper_bound の方が適している可能性があります。

複雑さを保証するには、線形検索の方が優れています。アルゴリズム全体の複雑さは O(n) になります。これはあなたが得ることができるのと同じくらい効率的です。

于 2013-01-18T22:16:18.583 に答える
0

簡単な方法でうまくいくようです。マップ要素は昇順で配置されます (比較演算子が適切であると仮定します)。したがって、等しい範囲を通過し、範囲の直後の要素の値でそれらを変更するだけで、必要なことが行われます。

マップを複製し (オリジナルが必要な場合)、最初の要素を取得equal_range()し、そのキーを取得し、範囲内の 2 番目の反復子の値で値を変更します (最後の反復子でない限り)。equal_range()2 番目のイテレータのキーを取得します。繰り返す。

于 2013-01-18T21:48:02.800 に答える