このデータのどのデータ構造ですか？

Question

私は基本的なOOP C++コースのプロジェクトを書いています。私はタイプMedia（そして派生物Book、Movie、Album）のオブジェクトのセットを実装しなければなりません。これらのセットの操作は、要素を追加すること、特定の要素を削除すること（必ずしも最初または最後ではない）、セットを検索すること（複数の結果を返すことができる）です。並べ替える必要はありませんが、私はそれが良い追加だと思った。

私は最高のデータ構造になりますか？単純な配列、ベクトルまたはリスト？ （私は実装を書く必要がありますが、標準クラスは使用できません。） 大きなデータセットを扱っているわけではないので、私は実際に効率やメモリ消費を心配していませんが、私がなぜ特定のデータ構造を選んだのかを説明してください。

アイテムの削除と追加にはListが適していると考えましたが、ベクトルには検索関数（インデックスの配列を返す可能性がある）に役立つインデックス演算子[]があります。

Answer 1

家庭の仕事としては、最初に単純なリンクリストを使用することをお勧めします。検索のために、見つかったアイテムのポインタまたはイテレータ（ListクラスがSTLコンテナと互換性がある場合）を返すことができます。あなたのケースでは、複数のサブクラスがあります。基本クラスのポインタ、つまりコンテナ内にMediaを配置する必要があります。はいの場合は、メモリの管理方法を検討する必要があります。例えば要素が削除されたときにメモリを解放します。

Answer 2

気にしない場合は、単にtwo dimensional arrayまたはlinked listを使用してください。私はこの状況で可能な限り最高だと思う。

Answer 3

私はバイナリツリーとして実装されたリストでそれを行います。
検索機能では、ポインタの配列を返すことができます。

Answer 4

効率性やメモリ消費について気にしない場合は、最も単純な実装である配列を選択する必要があります。新しいアイテムを最後に挿入し、配列の最後のものをギャップに移動してアイテムを削除します。配列全体を反復して検索します。

効率性を気にしていた場合は、ハッシュテーブルまたはバランスツリーを実装することができます。

Answer 5

あなたのケースでは、最良のコンテナは地図だと思います。各メディアにはこのメディアのキーであるID（書籍ISBNなど）があります。そのため、同じIDの2冊の本を地図と正確には区別できません。