データ構造の選択

異なるデータ構造が要件に応じて使用されますが、どのデータ構造を使用すればよいでしょうか？私はちょうど適切なデータ構造を選択する方法を知りたいですか？ありがとうデータ構造の選択

2010-12-20 Atul

それはどのような問題を解決するかによって異なります... – IProblemFactory

**要件**に従って異なるデータ構造が使用されています。 – Lazer

私はこの問題に対する簡単な答えを知らない。これはプログラマーになるための終わりのない道での学習プロセスの一部です。そしてそれは楽しいものの一つです。問題に使用できるデータ構造、パターン、アルゴリズムなどが異なることがよくあります。しかし、「ベスト」を見つけるには、時間、設計、経験、チームワーク、その他多くの要素が必要です。 –

このフローチャートは、C++でSTLのためですが、あなたは

ベクトルは動的配列

ある

リストがあるリンクリストをC.にSTLコンテナによってサポートされるデータ構造のいずれかを実装することができ
Dequeは、動的配列のリストのようなものです。sortは、その違いを分割します。
キューと優先度キューは、彼らが言うようなものです（通常キューはデキューの観点から実装され、優先度キューは通常、ベクトルまたはデキュー内のヒープの観点から実装されます）。
セット/マップ/マルチセット/マルチマップはすべて実装されています。平衡二分木の何らかの形を使用します。

アップデート2016：どうやら私はここにリンクするために使用される画像はリンク腐ってきましたが、あなたはこの質問にいくつかの同等の画像の上に見ることができます：In which scenario do I use a particular STL container?

出典

2010-12-20 19:15:18

ニート。しかし、順序のないコンテナの更新が必要です。 – SoapBox

+1 LOL。それはとても便利でした。私はそれを投稿するthougtを持ってほしければ。 – Casey

@SoapBox：順序付けられていないコンテナが実際に標準である場合、おそらく（私は作者ではありませんが、私は言うことはできません）。 –

どのデータ構造がどの要件を満たすために使用されているかを調べる必要があります。の場合は、オプションを指定して、いつ使用するか正確に教えてください。

詳細を知ったら、適切なデータ構造を（適切な確信を持って）選択することができます。

出典

2010-12-20 19:14:34

決定のどの部分が問題を引き起こしているかを知らなくても、答えるのは難しいです。

ほとんどの場合、保存する必要があるデータを保持する最小かつ単純なデータ構造が必要です。

トラブルが発生した特定のケースが1件ありましたか？

出典

2010-12-20 19:14:52

さて、バイナリツリーのようなものは、まれに何かを保存するための最小かつ単純な方法ではありませんが、それを実行するのに最も効果的な方法です。 –

さて、アルゴリズムよりもデータ構造そのものについてもっと考えていました。しかし、問題の質問が完全にはっきりしていないときには、それは間違いなく問題の一部です。 –

ないあなたが探しているものが、それはに依存します。

これは、保存するデータ、そのデータにアクセスする際の制約、実際にすばやく見ることができる必要があるかどうかによって異なります。データにあらゆる種類の並べ替えを維持する必要がありますか？後でソートする予定ですか？

データ構造（リンクされたリスト、マップ、セット）を選択した場合でも、その中にはさまざまなバリエーションがあり、それによってさらに意思決定が促進される可能性があります。親指の

私のルールはこれです：あなたは、あなたがより複雑なものが必要であることをそう知ることができるまで、その最も単純で

移動します。

出典

2010-12-20 19:17:38 Casey

皆さん、ありがとうございました....実際には、私はそれが練習と経験についてすべてであると理解しています。実際には私は解決策を知ることを試みていましたが、これは非常に不可能な問題です。とにかくもう一度感謝しています。 – Atul

データの保存を選択するデータ構造を迅速かつ効率的に検索することが懸念される場合は、選択したデータ構造を正当化する理由を挙げます。

出典

2014-02-06 15:11:15 user3280137

各データ構造は、アクションの種類ごとに異なるコストを持っていますあなた自身に尋ねる必要があります。

私は（私に「ボブ」と呼ばれる人物を与える）特定の要素を見つけることができるようにする必要がありますか？
私は注文を気にかけますか（つまり、定期的に最初か最後を見つけるか）？
私は最後のレコード以外のレコードを効率的に削除する必要がありますか？
ランダムアクセスが必要ですか（私に20番を与える）？
効率的なマルチスレッドの読み書きができるようにする必要がありますか？

注：リストにない質問はすべての実用的なデータストアはO（n）の時間ですべてのN elmentsにアクセスすることができますよう、「私は店のすべてを反復処理できるようにする必要がありません」

また

は、これらすべてのコメントが一般化したものである：

1への答えが「YES」の場合、その様々な非規則配列型構造（ベクトル、ソートされていない配列、リンクリスト）

場合を除外します2への答えが "はい"であれば、ハッシュベースの店舗（ハッシュマップなど）を排除します。検索効率を高めるために発注可能なものおそらく、ツリーセットや順序リストが必要です。

3.の答えが "yes"の場合、リストベース（ソートされていない配列、リンクされたリスト）を除外し、おそらくはツリーセット、順序付きリスト、またはハッシュマップが必要です。

4の答えが "yes"の場合、ハッシュマップとリンクされたリストは除外されます（注：これは1とは異なる質問です。ハッシュマップはインデックスに基づいてすべてを保存するため、）。

5の答えが "はい"の場合、特定の要件を持つ質問をするのはおそらく方法です。これは前の点で与えられたすべての答えを複雑にするためです（リンクリスト、ハッシュマップ、効率的な並列実装、ソートされたものはすべてパラレルでは難しい）。

なぜツリーセットがこれらすべてのオプションにあるのか疑問に思うのであれば、一般的には推奨されません。 2の答えが "いいえ"であれば、ハッシュマップは通常、コレクションの成長に合わせて要素を追加したり削除する時間がツリーセットよりもはるかに遅くなっているためです。同様に、他の質問のいずれかに対する回答が「いいえ」であれば、より良い推奨があります。

一般的に：ランダムアクセスが必要な場合は、ハッシュマップ。あなたがソートされたツリーセットを必要とするならば、リンクされたリスト。（これらはすべてストレートアレイと比較してメモリオーバヘッドがあるので、メモリは非常に限定的ではないと仮定しています）

出典

2014-10-03 06:24:03

答えて

関連する問題