Последовательные контейнеры STL поддерживают вставку (до), тогда как forward_list поддерживают вставку

Question

Последовательные контейнеры STL, такие как vector, deque, list поддерживают вставку для вставки элементов перед заданным итератором для поддержки операторов типа

vector.insert(std::end(container), container2.begin(), container2.end())

Принимая во внимание, что forward_list поддерживает insert_after. Почему сопровождающие STL должны были сделать этот выбор дизайна?

Answer 1

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. Спасибо Говарду Хиннанту за ссылку.