STL 顺序容器,如向量、双端、列表支持插入在给定迭代器之前插入元素以支持语句,例如
vector.insert(std::end(container), 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的链接。