乍一看，双链表似乎是合理的，但当我开始实现时，我遇到了跟踪当前位置的问题。我已经使用了std::list迭代器，但是处理极端情况(参见下一部分)变得很痛苦。以下是DS的要求:
- 保持元素顺序
- 中间有效插入
- 插入/删除不会使迭代器失效
- O(N)随机访问不是问题
链表最适合它。
当前位置游标(迭代器)的要求:
- 双向
- 初始表示
end位置 - 当迭代器位于
end位置时，在末尾插入元素后，下一个迭代器前进将其移动到该元素。如果之前的播放列表为空，也会有相同的行为 - 相反的情况也一样:迭代器在开始，
push_front，向后移动将会找到新添加的元素
实现它的最佳实践是什么?有相关的库吗(c++)?
std::list是一个支持常量时间插入和从容器中的任何位置删除元素的容器。不支持快速随机访问(这在您的情况下不是问题)。它通常被实现为一个双链表。与std::forward_list相比，该容器提供了双向迭代能力，但空间效率较低。
在列表内或跨多个列表添加、移除和移动元素不会使迭代器或引用失效。只有在删除相应元素时，迭代器才失效。
在我看来，std::list非常适合你所描述的问题。