É std::list::size() verdadeiramente O(n) em implementações modernas?

Recentemente, alguns desenvolvedores sugeriram que std::list::size() tem uma complexidade de tempo linear (O(n)). Porém, de acordo com o padrão C, a complexidade não é definida e pode variar dependendo da implementação.

Nas versões anteriores do padrão C (C 03), a operação size() era recomendada para ter complexidade constante (O(1)). Contudo, com a introdução do C 11, tornou-se um requisito para todos os recipientes padrão. A Tabela 96 do padrão C 11 afirma explicitamente que .size() deve ter complexidade constante para todos os contêineres.

Historicamente, a biblioteca libstdc do GCC implementou size() com complexidade O(n) usando std::distance(begin (), end()), conforme descrito na entrada do blog que você citou. Porém, no modo C 11, esse comportamento mudou:

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

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

No GCC 5.0 e superior, a função size() usa uma estrutura de dados interna para controlar o número de elementos, tornando efetivamente a operação O(1). Isso se alinha com o requisito C 11 para todos os contêineres padrão.

É importante observar que alguns casos de uso de nicho ainda podem levar à complexidade O(n) para size(), mas para a grande maioria dos usuários, o a operação deve ser em tempo constante.