问题是推荐的使用方式是什么std::list实现 O(1) 删除列表项？
通常，当我选择双向链表时，我希望能够在 O(1) 时间内从列表中删除一个元素，然后在 O(1) 时间内将其移动到不同的列表。如果该元素有自己的prev and next指针，没有真正的技巧可以完成工作。如果列表是双向链接的循环列表，则删除不一定需要知道包含该项目的列表。
As per 迭代器失效规则 https://stackoverflow.com/q/6438086/315052, std::list迭代器非常耐用。所以，在我看来，使用时得到了我想要的行为std::list我自己的项目是在我的类中存储一个迭代器以及包含列表。
class Item {
typedef std::shared_ptr<Item> Ptr;
struct Ref {
std::list<Ptr>::iterator iter_;
std::list<Ptr> *list_;
};
Ref ref_;
//...
};
这有一个缺点，我需要创建我自己的装饰版本std::list知道更新ref_每当该项目添加到列表中时。我想不出一种不需要嵌入式迭代器的方法，因为没有嵌入式迭代器意味着擦除将首先引发 O(n) 查找操作。
获得 O(1) 擦除的推荐方法是什么std::list？或者，是否有更好的方法来实现目标？
过去，我通过实现自己的列表数据结构来实现这一点，其中放置在列表中的项目有自己的下一个和上一个指针。管理这些指针是很自然的，因为它们是列表操作本身所固有的（我的列表实现的 API 调整指针）。如果我想使用 STL，实现此目的的最佳方法是什么？我提出了嵌入迭代器的稻草人建议。有更好的方法吗？
如果需要具体的用例，请考虑计时器实现。创建计时器后，会将其放入适当的列表中。如果被取消，则希望有效地去除它。 （这个特定的示例可以通过标记而不是删除来解决，但它是实现取消的有效方法。）可根据要求提供其他用例。
我探索的另一种选择是融合std::list with a std::unordered_map为指针类型创建专门的列表。这是更重量级的（因为哈希表），但提供了一个在接口级别非常接近标准容器的容器，并且使我能够以 O(1) 的方式擦除列表元素。稻草人提案中唯一缺少的功能是指向当前包含该项目的列表的指针。我已将当前的实施放在代码审查 https://codereview.stackexchange.com/q/31886征求意见。
