我们可以在遍历时插入到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).