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

#cpp #алгоритм #cpp11 #stl

В действительности вопроса даже два. К некоторому для себя удивлению узнал, что временная
сложность получения к-ва айтемов списка std::list::size() - линейная 


  C++98. Complexity: Up to linear. Источник


Не совсем понятно, чем это обусловлено. Для чего каждый раз подсчитывать свои айтемы?

И если в этом была необходимость в ранних стандартах, то за счет каких компромиссов
удалось достичь гарантии константности в стандарте новом?


  C++11. Complexity: Constant.

    

Ответы

Ответ 1

Это следствие стародавнего "конфликта интересов" между функцими 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()
там линеен.