8

重複したデータがたくさんあるので、重複を排除したいと思います。たとえば、[1、1、3、5、5、5、7]は[1、3、5、7]になります。

std::mapまたはstd::setのいずれかを使用してこれを処理できるようです。ただし、（a）すべての値をコンテナーに挿入する方が速いのか、（b）コンテナーに既に存在するかどうかを確認し、存在しない場合にのみ挿入する方が速いかどうかはわかりません-挿入は非常に効率的ですか？より良い方法があるとしても...これを行うための迅速な方法を提案できますか？

別の質問-私がそれらに保存しているデータが整数ほど些細なものではなく、代わりにカスタムクラスである場合、std :: mapはどのようにしてデータを適切に保存（ハッシュ）して、operator [を介して高速アクセスできるようにしますか？ ]？

4

5 に答える 5

11

std::mapハッシュを使用しません。 std::unordered_mapそうですが、それはC++11です。 std::mapどちらも、std::set提供したコンパレータを使用します。クラステンプレートには、このコンパレータのデフォルトがあります。これは、要約するとoperator<比較になりますが、独自のコンパレータを提供することもできます。

キーと値の両方を保存する必要がない場合（必要ないように見えます）はstd::set、より適切であるため、単にを使用する必要があります。

この規格は、内部でどのデータ構造mapをset使用するかについては述べておらず、認証者のアクションには特定の時間計算量があることだけを示しています。実際には、私が知っているほとんどの実装はツリーを使用しています。

operator[]またはを使用する場合は時間計算量に違いはありませんが、アイテムが見つからない場合は、またはinsertを使用する前に、その後に続くを使用します。後者は、セットにアイテムを挿入するための2つの別々の検索を意​​味します。insertoperator[]searchinsert

于 2012-10-10T19:01:22.247 に答える
7

関連するinsert()コンテナのいずれかでfind()、オブジェクトが存在するかどうかを確認してから、オブジェクトを挿入します。要素をに挿入するだけstd::set<T>で、重複をかなり効率的に取り除くことができます。

セットのサイズと、一意の値に対する重複の比率によっては、オブジェクトをstd::vector<T>、に入れてから、と一緒にstd::sort()使用して重複を取り除く方が速い場合があります。std::unique()std::vector<T>::erase()

于 2012-10-10T19:00:18.177 に答える
2

何回やればいいの？

挿入が通常の場合：

//*/
std::set<int> store;
/*/
// for hash:
std::unordered_set<int> store;
//*/
int number;

if ( store.insert(number).second )
{
  // was not in store
}

一度記入した場合：

std::vector<int> store;
int number;

store.push_back(number);
std::sort(store.begin(),store.end());
store.erase(std::unique(store.begin(),store.end()),store.end() );

// elements are unique
于 2012-10-10T19:00:19.070 に答える
0

std::mapおよびの一般的な実装戦略std::set、つまりバランスの取れた二分探索木を想定すると、挿入とルックアップの両方で、キーがあるべき場所を見つけるためにツリートラバーサルを実行する必要があります。したがって、失敗したルックアップとそれに続く挿入は、単に挿入する場合の約2倍の速度になります。

std :: mapは、operator []を介した高速アクセスのためにデータを適切に保存（ハッシュ）する方法を教えてください。

指定した比較関数（または、カスタムタイプでstd::lessオーバーロードした場合に機能する）を使用します。operator<いずれにせよ、はハッシュテーブルではstd::mapありません。std::set

于 2012-10-10T18:59:19.940 に答える
0

std::set私の知る限り、std::mapどちらも赤黒木として実装されています。そして、おそらく挿入のみを使用する方が高速です（ルックアップ時間が2倍になるため、両方とも高速になります）。

またmap、をset使用しますoperator <。クラスが定義している限り、operator <それらをキーとして使用できます。

于 2012-10-10T19:01:41.257 に答える