c++ - 我们可以在遍历时插入STL列表吗

Question

我有一个我正在遍历的项目列表。在遍历新项目时，它们会被创建，它们应该被插入到同一个列表的不同适当位置。

我正在使用 std::list，因为它的插入时间(有序)是 log(N)。

这会导致任何问题吗，因为我在向容器中插入时使用了迭代器？请注意，插入也可以发生在当前迭代器位置的旁边。

如果这不起作用，我还有哪些其他选择？我们是否有针对此类事件的设计模式或最佳实践？

Answer 1

是的，您可以使用 list::insert 插入给定迭代器的列表中的给定位置.

以下将插入值 3 作为列表中的第二项:

list<int> stuff(/*...*/);
auto it = stuff.begin();
++it;
stuff.insert (it,3);

具体来说，list::insert 函数会在传递给它的迭代器之前插入一个项目。这是插入列表的最常见方式。

但是请注意，std::list 的插入时间不是 O(log(n))。在 std::list 的任何位置(给定迭代器)插入一个元素的复杂度为 O(1)。