2

次のような unordered_set があります。

unordered_set <long> valueSet;

/*the following insertion is done in order (from 1 to 10000), 
 *unordered_set will keep the elements based on the insertion order, right, 
 *just like in a vector ?
**/

for(long i = 1; i <= 10000;++i)
{
        valueSet->insert(i);
}

次に、その unordered_set 内の要素の約 85% を消去する別の関数を実行しました。(消去される要素は、この関数のロジックに依存しますが、すべての要素が最初に順番に挿入されたので問題ではありません)。

unordered_set のいくつかの要素を消去した後、その unordered_set にまだ残っている最後の要素を出力したいと思います。たとえば、要素 9997、9998、9999、および 10000 が消去されているため、このセットに残っている最大の要素は 9996 です。これを行う方法は?
基本セットを使用する場合、次のことができます。

set <long>::reverse_iterator it = valueSet.rbegin();
cout << *it << endl;

セットにはreverse_iteratorとrbegin()がありますが、これはunordered_setには存在しません。基本セットを作成しなかった理由は、要素サイズを 10^8 まで拡大する必要があるためです。通常のセット (赤黒木に基づく) を使用すると、実際にパフォーマンスが低下します (特に、挿入と削除を扱う場合)。これどうやってするの？最終的に残った unordered_set をベクターにコピーすることはできますが、もちろん時間がかかります。よりスマートな方法を使用してこれを達成するにはどうすればよいですか? 次のようなこともできないことに気付きました：

unordered_set <long>::iterator it = valueSet.end();
//operator -- does not exist here in the unordered_set
it--;
4

4 に答える 4

1

unordered set は、順序付けされていないことを意図しています。イテレータを使用する際に要素が表示される順序は、任意/非決定論的であると想定する必要があります。これは、順序に関する特定の動作は、定義上、移植性がなく、完全に実装固有であることを意味します。今はたまたま順番に並んでいるかもしれませんが、十分な操作を行うと、別の順番になる可能性があります。イテレータを提供する唯一の理由は、任意の順序で要素ごとに処理できるようにするためです。

最初から std::vector を使用しないのはなぜですか?

于 2011-10-07T18:27:48.607 に答える
1

ケーキを持って食べることはできません。

順序付けられていないコンテナーは、要素を順序付けられていない方法で (通常はhash table内に) 格納するため、予測可能な方法でそれらを反復処理することはできません。特に、挿入された順序で要素を保存しません。

順序を気にしない場合は、std::dequeorの方が適していますstd::vector(前に挿入する必要がある場合は、前者をお勧めします)。

于 2011-10-07T19:01:26.940 に答える
1

あなたのコメントから私が集めたものから、std::bitsetまたはそれに対応する動的なboost::dynamic_bitsetを使用するのが適切なはずです。O(1) の挿入と削除、および最大要素を決定するための O(N) (線形検索による) が得られます。せいぜい削除操作と同じ数の検索ステップを実行する必要があるため、最大値を見つけることは O(1) に償却されると主張することさえできます。

于 2011-10-07T18:58:41.807 に答える
0

削除されたアイテムをベクターに保存します。完了したら、ヒープに変換します。(O(n)、n は削除された項目の数) 次に、削除されていない最大の要素が見つかるまで、ヒープから最大値を繰り返し削除します。これは O(m log n) です。ここで、m は最大値と答えの差です。

于 2011-10-08T18:49:16.577 に答える