std::forward_list and sequence concept requirements

Question

Is there some reason why the standards committee chose to implement the API for std::forward_list so that it doesn't meet the Sequence container concept requirements?

The Sequence concept requirements specify that the container must be compatible with expressions like:

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

... where it is an iterator, v is an element, and n is an integer, and begin/end is an iterator range.

There's no reason this API isn't possible with a singly-linked list, since the insert functions require an iterator starting position. But for some reason std::forward_list has the insert_after functions, which break compatibility with the Sequence concept.

Is there some reason for this?

Answer 1

The reason is that it's extremely inefficient to insert before an element in a singly linked list: You have to start at the beginning and iterate until you find the requested place to insert, making the insert O(n) instead of constant time.

Compare to why they don't provide operator[] in std::list because it would take linear time. Just as list doesn't meet the requirements of random access compared to vector, forward_list doesn't meet all the requirements of sequence compared to list.