c++ - STL 顺序容器支持 insert (before) 而 forward_list 支持 insert_after

Question

STL 顺序容器，如 vector、deque、list 支持插入以在给定迭代器之前插入元素，以支持如下语句

vector.insert(std::end(container), container2.begin(), container2.end())

而 forward_list 支持 insert_after。为什么 STL 维护者必须做出这种设计选择？

Answer 1

forward_list 被实现为单链表。列表中的每个节点都有一个指向列表中下一个元素的指针。 (注意:指针在这里是一个通用术语)。

这意味着在列表中向后移动是不可能的。您可以从列表的开头开始，然后向前移动，直到找到其链接指向您拥有的项目的元素，但这很昂贵。以这种方式插入列表是一个O(N) 操作(相对于O(1))

所有其他容器(vector、string、deque、map、set、list等)都支持在容器中向前向后遍历，所以很容易找到“之前”的item。 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 提供的链接。