メディアプレイリストのデータ構造ですか？

Question

最初の視点では、二重リンクリストは妥当と思われますが、実装を開始した時点で、現在の位置を追跡する問題に直面しました。私はstd :: list iteratorを使用しましたが、極端なケース（次の部分を参照）を扱うことは苦痛になりました。 は、だからここにDSのための要件は次のとおりです。

• で要素の順序
• 効果的な挿入を保持真ん中
• 挿入/イテレータ
• O（N）のランダムアクセスではありませんを無効にしていない消去されます問題

リンクされたリストが最適です。現在位置カーソル（イテレータ）用

要件：

• 双方向
• end位置に反復子は、最後に要素を挿入した後、次のイテレータ予めが移動する時に最初end位置
• を示しそれをこの要素に渡す。以前にプレイリストが逆の場合も同様
空だった場合と同じ動作：初めにイテレータ、 push_front、後方に移動すると、新しく追加された要素を移動します

は、それを実装するためのベストプラクティスは何ですか？そのためのライブラリがありますか（C++）？

Answer 1

std::listは、コンテナ内のどこからでも要素の一定時間の挿入と削除をサポートするコンテナです。高速ランダムアクセスはサポートされていません（あなたの場合は問題ありません）。これは、通常、二重リンクリストとして実装されます。 std::forward_listと比較すると、このコンテナは双方向反復機能を提供しますが、スペース効率は低下します。

リスト内または複数のリストにわたって要素を削除して移動しても、イテレータまたは参照は無効になりません。反復子は、対応する要素が削除されたときにのみ無効化されます。

私の見解から、std::listは、あなたが記述した問題に最適です。