データ構造の選択

Question

私はC++を使用しています.40のユーザー名を格納したいとします。単純に配列を使用します。しかし、私が40000のユーザ名を保存したいのであれば、これはまだ検索速度に関しては良い考えですか？この速度を向上させるにはどのデータ構造を使用する必要がありますか？

Answer 1

挿入および削除の要件を指定する必要があります。シーケンス内の任意の場所に物事を取り除いて挿入する必要がありますか？

また、なぜ順番に検索する必要がありますか？ハッシュテーブル参照に適していない検索を行っていますか？

現在、私はdequeまたはlistを提案しています。多くの場合、アルゴリズムの最も簡単な実装を実現するインタフェースを備えたコンテナを選択し、パフォーマンスが不十分で必要なスピードアップが得られる場合にのみ選択肢を変更することをお勧めします。

vectorには2つの主な利点がありますが、頻繁なコピーを防止するためにベクトルが過剰に割り当てられ、オブジェクトが連続して格納されるためシーケンシャルアクセスが高速になる傾向があります。これらはまた、その短所です。成長するベクターには再配置とコピーが必要であり、ベクターの終わり以外の場所からの挿入や除去にもコピーが必要です。連続したストレージは、軽度のメモリ断片化であっても満足することが難しいため、多数のオブジェクトまたは大きなオブジェクトを持つベクタには問題が発生します。

listは、連続した記憶域を必要としませんが、通常、リストノードは2つのポインタ（ほとんどの実装で）のオブジェクトごとのオーバーヘッドを持ちます。これは、非常に小さいオブジェクトのリスト（例えば、ポインタのリストでは、各ノードはデータアイテムの3倍のサイズである）において重要であり得る。リストの途中からの挿入や削除は非常に安く、リストノードは作成したメモリに移動する必要はありません。

dequeは、チャンクストレージを使用するため、ベクターに似たオブジェクトごとのオーバーヘッドは低くなりますが、断片化されたメモリスペースでは同じ問題が発生しません。それはしばしばコレクションのための非常に良い選択であり、しばしば見落とされます。

Answer 2

std :: vectorとstd :: listはこのタスクに適しているようです。手前のレコードの最大数がわかっている場合は、配列を使用できます。

Answer 3

逐次検索と保存が必要な場合は、listが適切なコンテナです。

また、vectorも悪い選択ではありません。

Answer 4

おおまかに言えば、vectorからlistを好むか、Cスタイルの配列を禁止します。

ベクトルが塗りつぶされたら、sortアルゴリズムを使用して正しく順序付けされていることを確認します。 find,binary_searchまたはlower_boundのいずれかを使用して、特定のレコードを検索できます。 findを使用するようにソートする必要はありません。

Answer 5

リソースが制約された環境（埋め込みプラットフォーム、電話機など）を使用している場合を除き、真剣です。 std::mapを使用して、並べ替えや検索をする手間を省き、コンテナにすべての処理をさせます。これはソートされたツリー構造、おそらくバランス（例：Red-Black）の可能性があります。これは良い検索パフォーマンスが得られることを意味します。データのサイズが1つまたは2つのポインタのサイズに近い場合を除き、選択するデータ構造のメモリオーバーヘッドは無視できます。あなたのグラフィックカードにはおそらくあなたが考えているデータのために使い果たしようとするより多くのメモリがあります。

他の人はあなたが/データを削除（=>リスト）を挿入する必要があるかどうかに応じて、map使用std::vectorまたはstd::listを使用したくない場合は、バニラの配列を使用するには非常に少ない良い理由がある言ったようにしませんか（= >ベクトル）

実際にすべてのデータがメモリに必要な場合は、sqlite経由でディスクに保存することをお勧めします。また、メモリアクセスの場合はsqliteを使用してください。それはあなたのデータで何をする必要があるかによって異なります。