媒体播放列表的数据结构？
Data structure for a media playlist?
乍一看双链表似乎很合理，但当我开始实施时，我遇到了跟踪当前位置的问题。我使用了 std::list 迭代器，但处理极端情况（见下一部分）变得很痛苦。
所以这是对 DS 的要求：
- 保留元素的顺序
- 中间有效插入
- Insertions/erases 不要使迭代器无效
- O(N)次随机访问不成问题
链表最适合它。
当前位置游标（迭代器）的要求：
- 双向
- 最初表示
end位置
- 当iterator在
end位置时，最后插入元素后，下一次iterator advance会移动到这个元素。如果之前播放列表为空，则行为相同
- 反之亦然：开始时的迭代器，
push_front，向后移动到新添加的元素
实施它的最佳做法是什么？有没有它的库 (C++)？
std::list是一个容器，支持在容器的任意位置进行常量时间插入和移除元素。不支持快速随机访问（在您的情况下这不是问题）。它通常以双向链表的形式实现。与 std::forward_list 相比，此容器提供双向迭代功能，但 space 效率较低。
在列表中或跨多个列表添加、移除和移动元素不会使迭代器或引用无效。只有当相应的元素被删除时，迭代器才会失效。
从我的角度来看 std::list 非常适合您描述的问题。
乍一看双链表似乎很合理，但当我开始实施时，我遇到了跟踪当前位置的问题。我使用了 std::list 迭代器，但处理极端情况（见下一部分）变得很痛苦。 所以这是对 DS 的要求：
- 保留元素的顺序
- 中间有效插入
- Insertions/erases 不要使迭代器无效
- O(N)次随机访问不成问题
链表最适合它。
当前位置游标（迭代器）的要求：
- 双向
- 最初表示
end位置 - 当iterator在
end位置时，最后插入元素后，下一次iterator advance会移动到这个元素。如果之前播放列表为空，则行为相同 - 反之亦然：开始时的迭代器，
push_front，向后移动到新添加的元素
实施它的最佳做法是什么？有没有它的库 (C++)？
std::list是一个容器，支持在容器的任意位置进行常量时间插入和移除元素。不支持快速随机访问（在您的情况下这不是问题）。它通常以双向链表的形式实现。与 std::forward_list 相比，此容器提供双向迭代功能，但 space 效率较低。
在列表中或跨多个列表添加、移除和移动元素不会使迭代器或引用无效。只有当相应的元素被删除时，迭代器才会失效。
从我的角度来看 std::list 非常适合您描述的问题。