Чем обусловлена линейная сложность функции list::size()?

В действительности вопроса даже два. К некоторому для себя удивлению узнал, что временная сложность получения к-ва айтемов списка std::list::size() - линейная
C++98. Complexity: Up to linear. Источник
Не совсем понятно, чем это обусловлено. Для чего каждый раз подсчитывать свои айтемы?
И если в этом была необходимость в ранних стандартах, то за счет каких компромиссов удалось достичь гарантии константности в стандарте новом?
C++11. Complexity: Constant.

Ответ

Это следствие стародавнего "конфликта интересов" между функцими std::list::size() и std::list::splice().
Если делается частичный splice() из одного std::list в другой с требованием константного времени выполнения такого splice() (т.е. просто перецепить крайние элементы диапазона из одного списка в другой), то тогда невозможно будет сразу знать новые размеры контейнера-источника и контейнера-получателя, т.к. неизвестно сколько элементов перецепилось. Поэтому требование константного по времени splice() ведет к требованию линейного по времени size() - элементы в обоих контейнерах придется заново пересчитывать.
Если же наоборот потребовать константности времени size() (т.е. фактически потребовать хранимый размер), то тогда придется согласиться на более медленный splice(), который в вышеупомянутой ситуации за линейное время будет вычислять новые размеры контейнеров.
В С++98 этот вопрос был оставлен открытым. Реализациям разрешалось выбирать, где по их мнению константное время важнее - в size() или в splice()
В С++11 решили принять волевое решение: делаем хранимый размер, гарантируем size() за константное время и, так уж и быть, соглашаемся на линейное время в splice().
Именно этим и объясняется разница между С++98 и С++11.
P.S. Реализация стандартной библиотеки С++ в GCC изначально пошла по пути быстрого splice() и медленного size(). После того, как С++11 настоял на ином варианте, GCC исправил реализацию своего std::list, но тут же наткнулся на бинарную несовместимость версий библиотек из-за добавления нового поля в std::list. Изменение было тут же откачено, и по сей день std::list в GCC не соответствует требованиям С++11. std::list::size() там линеен.