実装方法についての考え方は？

Question

私は非常に古いCコードをC++に移植しており、配列内に実装されたリンクリストを介して実行しています。この要素は単純な構造です。

インデックスとしてわかっている場合は、配列として、データにすばやくアクセスできます。リンクされたリストのアスペクトは、要素を移動させ、リストから「削除」することができます。エレメントは、使用頻度に基づいてリスト内で移動できます（MRUの場合は上、LRUの場合は下）。

私はこれを実装するために、別の配列を使うよりも良い方法を見つけるのが好きです。私はSTLを使いたいと思いますが、どのコンテナを使うのが最適かはわかりません。

いずれかの考えがありますか？

Answer 1

これは、リンクされたリストであるので、あなたはおそらくstd::list ...

を使用する必要があります親指のルールは、あなたが、リスト内のランダムな位置に要素を挿入する必要がある場合、リンクされたリストを使用したいということですかランダムな要素をリストから削除します。主にリストの最後に要素を追加/削除する必要がある場合は、std::vectorを使用する必要があります。リストの先頭または最後に要素を追加または削除する必要がある場合は、std::dequeを使用してください。

ここでは、確率について話しています。青い月に一度std::vectorの中に要素を挿入する必要がある場合は、おそらく問題ありません。しかし、これを常に行う必要がある場合は、ベクトルが常に要素を移動し、おそらくメモリを再割り当てする必要があるため、パフォーマンスに大きな影響を与えます。一方、ベクトルを使用する利点は、その要素がメモリ内で連続していることで、キャッシュのために単純にトラバースする必要がある場合は、パフォーマンスが大幅に向上します。

Answer 2

はこちらをご覧ください：

http://linuxsoftware.co.nz/cppcontainers.html

は、あなたが底に右のコンテナを選択するためのフローチャートあります。

Answer 3

このリストのデータはポインタなので、リンクされたリストを使用するのはどうしてですか？小さなPODの場合、通常は最初にstd::vectorが最善の賭けとなり、プロセッサキャッシュを使ったデータの局所性が良好であるため、理論的にはリンクリストを改善する必要がある場合でも連結リストよりも優れています。私はstd::vectorを選択して、パフォーマンス上の問題があることを示すプロファイリングがあり、std::listのパフォーマンスが向上するまで表示されます。