Std :: forward_list and sequence concept requirements

Question

Is there any reason why the standardization committee decided to implement the API std::forward_listso that it does not meet the requirements of the container concept Sequence?

The conceptual requirements Sequencestate that the container must be compatible with expressions such as:

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

... where itis an iterator, vis an element, a nis an integer, and a begin/endis a range of iterators.

There is no reason this API is not possible with a singly linked list, because functions insertrequire an iterator starting position. But for some reason, it std::forward_listhas features insert_afterthat violate compatibility with the Sequence concept.

Is there a reason for this?

Answer 1

The reason is that it is extremely inefficient for inserting in front of an element in a separately linked list: you have to start from the very beginning and iterate until you find the right place to insert, pasting O(n)instead of constant time.

Compare why they do not provide operator[]in std::list, because it will take linear time. Just as it listdoes not meet the requirements of random access compared to vector, it forward_listdoes not meet all the requirements of the sequence compared to list.