c++ - std::forward_list 和序列概念要求

Question

标准委员会选择为 std::forward_list 实现 API 是否有某种原因使其不满足序列 容器概念要求？

Sequence 概念要求指定容器必须与以下表达式兼容:

c.insert(it, v);    // insert at position
c.insert(it, n, v); // fill insert
c.insert(it, begin, end);  // insert range

... 其中it是一个迭代器，v是一个元素，n是一个整数，begin/end 是一个迭代器范围。

这个 API 没有理由不能用于单链表，因为 insert 函数需要一个迭代器起始位置。但出于某种原因，std::forward_list 具有 insert_after 函数，这破坏了与 Sequence 概念的兼容性。

这有什么原因吗？

Answer 1

原因是在单向链表中before插入一个元素是非常低效的:你必须从头开始迭代，直到找到请求插入的位置，使插入 O(n)而不是常数时间。

比较为什么他们不在 operator[] 中提供 std::list 因为这需要线性时间。正如list相比于vector不满足随机访问的要求一样，forward_list相比于list也不满足所有的序列要求。