Является ли std::list::size() действительно O(n) в современных реализациях?

Недавно некоторые разработчики предположили, что std::list::size() имеет линейную временную сложность (O(n)). Однако согласно стандарту C сложность не определена и может варьироваться в зависимости от реализации.

В более ранних версиях стандарта C (C 03) операции size() рекомендовалось иметь постоянную сложность. (О(1)). Однако с появлением C 11 он стал обязательным для всех стандартных контейнеров. В таблице 96 стандарта C 11 явно указано, что .size() должна иметь постоянную сложность для всех контейнеров.

Исторически библиотека libstdc GCC реализовала size() со сложностью O(n), используя std::distance(begin (), end()), как описано в цитируемой вами записи блога. Однако в режиме C 11 это поведение изменилось:

size_type
size() const _GLIBCXX_NOEXCEPT
{ return __size_alloc_.first(); }

_LIBCPP_INLINE_VISIBILITY
const size_type& __sz() const _NOEXCEPT
    {return __size_alloc_.first();}

В GCC 5.0 и выше функция size() использует внутреннюю структуру данных для отслеживания количества элементов, эффективно выполняя операцию O(1). Это соответствует требованиям C 11 для всех стандартных контейнеров.

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