STL 顺序容器(如向量、双端队列、列表)支持 insert 在给定迭代器之前插入元素以支持诸如
矢量.插入(std::end(容器),container2.begin(),container2.end())
而forward_list支持insert_after。为什么 STL 维护者必须做出这样的设计选择?
forward_list被实现为单链表。列表中的每个节点都有一个指向列表中下一个元素的指针。(注:这里指针是一个通用术语)。
这意味着不可能在列表中向后移动。您可以从列表的开头开始,然后向前移动,直到找到链接指向您拥有的项目的元素,但这很昂贵。以这种方式插入列表是一个O(N)操作(与 相反O(1))
所有其他容器(vector、string、deque、map、set、list等)都支持在容器中向前和向后遍历,因此很容易找到“之前”的项目。 forward_list才不是。
insert(list_iter, x)至于名字,如果插在前面list_iter,insert(forward_list_iterator, x)插在位置后面会比较混乱。所以设计师给它们起了不同的名字。
[后来] 这在 的原始提案中进行了讨论forward_list,可以在以下位置找到:http ://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2448.html 。感谢 Howard Hinnant 提供的链接。