std::list c++ 是顺序的，那么它如何在序列中的任何位置进行插入和擦除操作需要恒定的时间
std::list c++ is sequential then how it can take constant time for insert and erase operations anywhere within the sequence
在我阅读的 C++ 参考资料中 "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions."
我怀疑它是否是顺序的，那么删除和插入我们必须顺序遍历以到达该节点的 node.Any 方式如何花费恒定的时间。删除节点取决于它的位置
O(1) 指的是 inserting/erasing 个节点的复杂度，前提是您 已经拥有该节点 的句柄（以迭代器的形式）。在给定第一个迭代器的情况下，获取列表的第 i 个元素的迭代器是 O(N)。
在判断 std::list 与 std::vector 的相对优点时，这一点经常被忽视。但请注意，插入和删除元素 return 迭代器可用于进一步的 insert/erase 操作。
在给定节点之前插入（我们称之为pos）或作为最后一个节点或删除给定节点是一个常数时间操作。
std::list可以实现为双向链表。序列容器不应与连续内存要求混淆。
因为列表没有排序。如果仔细观察，将元素放入列表的实际功能是 list::insert(hint, element) (http://www.cplusplus.com/reference/list/list/insert/)。 IE。对于每次插入，添加元素的位置都是已知的，因此是常数时间。
例如list::push_front(element) 是 insert(begin(), element).
的缩写
[这主要是评论，但不适合边距]
请注意，std::list 不能实现为单个链表来满足复杂性要求：
- 即使你已经有了一个 单链表节点的句柄，你也不能在恒定时间内在它之前插入（resp。擦除它）（因为你需要访问上一个节点）。
这就是为什么 std::forward_list 只提供 insert_after 和 erase_after。
在我阅读的 C++ 参考资料中 "Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions." 我怀疑它是否是顺序的，那么删除和插入我们必须顺序遍历以到达该节点的 node.Any 方式如何花费恒定的时间。删除节点取决于它的位置
O(1) 指的是 inserting/erasing 个节点的复杂度，前提是您 已经拥有该节点 的句柄（以迭代器的形式）。在给定第一个迭代器的情况下，获取列表的第 i 个元素的迭代器是 O(N)。
在判断 std::list 与 std::vector 的相对优点时，这一点经常被忽视。但请注意，插入和删除元素 return 迭代器可用于进一步的 insert/erase 操作。
在给定节点之前插入（我们称之为pos）或作为最后一个节点或删除给定节点是一个常数时间操作。
std::list可以实现为双向链表。序列容器不应与连续内存要求混淆。
因为列表没有排序。如果仔细观察，将元素放入列表的实际功能是 list::insert(hint, element) (http://www.cplusplus.com/reference/list/list/insert/)。 IE。对于每次插入，添加元素的位置都是已知的，因此是常数时间。
例如list::push_front(element) 是 insert(begin(), element).
[这主要是评论，但不适合边距]
请注意，std::list 不能实现为单个链表来满足复杂性要求：
- 即使你已经有了一个 单链表节点的句柄，你也不能在恒定时间内在它之前插入（resp。擦除它）（因为你需要访问上一个节点）。
这就是为什么 std::forward_list 只提供 insert_after 和 erase_after。