¿Std::list::size() es verdaderamente O(n) en implementaciones modernas?

Recientemente, algunos desarrolladores han sugerido que std::list::size() tiene una complejidad de tiempo lineal (O(n)). Sin embargo, según el estándar C, la complejidad no está definida y puede variar según la implementación.

En versiones anteriores del estándar C (C 03), se recomendaba que la operación size() tuviera una complejidad constante. (O(1)). Sin embargo, con la introducción del C 11, se convirtió en un requisito para todos los contenedores estándar. La Tabla 96 del estándar C 11 establece explícitamente que .size() debe tener una complejidad constante para todos los contenedores.

Históricamente, la biblioteca libstdc de GCC implementó size() con complejidad O(n) usando std::distance(begin (), end()), como se describe en la entrada del blog que citó. Sin embargo, en el modo C 11, este comportamiento ha cambiado:

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

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

En GCC 5.0 y superiores, la función size() utiliza una estructura de datos interna para realizar un seguimiento del número de elementos, lo que efectivamente hace que la operación sea O(1). Esto se alinea con el requisito C 11 para todos los contenedores estándar.

Es importante tener en cuenta que algunos casos de uso específicos aún pueden generar una complejidad O(n) para size(), pero para la gran mayoría de usuarios, el la operación debe ser de tiempo constante.