c++ - std::list c++ 是顺序的，那么它如何在序列中的任何位置进行插入和删除操作需要恒定的时间

Question

在 C++ 引用资料中，我读到“列表是序列容器，允许在序列中的任何位置进行恒定时间插入和删除操作，以及双向迭代。” 我怀疑它是否是顺序的，那么删除和插入节点如何花费恒定的时间。我们必须按顺序遍历到达该节点的任何方式。删除节点取决于它的位置

Answer 1

O(1) 指的是插入/删除节点的复杂性，前提是您已经拥有该节点的句柄(以迭代器的形式)。给定指向第一个元素的迭代器，获取指向列表第 i 个元素的迭代器的时间复杂度为 O(N)。

在判断 std::list 与 std::vector 的相对优点时，这一点经常被忽视。但请注意，插入和删除元素都会返回可用于进一步插入/删除操作的迭代器。