std :: forward_list и требования к концепции последовательности

Question

Есть ли какая-то причина, по которой комитет по стандартам решил реализовать API для std::forward_list, так что он не соответствует требованиям концепции контейнера Sequence?

В 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

Причина заключается в том, что это крайне неэффективно для вставки перед тем элемент в односвязный список: Вы должны начать с самого начала и итерации, пока вы не найти запрашиваемую место для вставки, что делает вставку O(n) вместо постоянной времени ,

Сравните, почему они не предоставляют operator[] в std::list, потому что это займет линейное время. Точно так же, как list не отвечает требованиям случайного доступа по сравнению с vector, forward_list не отвечает всем требованиям последовательности по сравнению с list.