¿Es list :: size () realmente O (n)?

Recientemente, noté que algunas personas mencionaron que std::list::size() tiene una complejidad lineal.
Según algunas fonts , de hecho, esto depende de la implementación, ya que el estándar no dice cuál debe ser la complejidad.
El comentario en esta entrada del blog dice:

En realidad, depende de qué STL estás usando. Microsoft Visual Studio V6 implementa size () como {return (_Size); } mientras que gcc (al menos en las versiones 3.3.2 y 4.1.0) lo hace como {return std :: distance (begin (), end ()); } El primero tiene velocidad constante, el segundo tiene o (N) velocidad

  1. Así que mi suposición es que para el size() multitud VC ++ size() tiene complejidad constante ya que Dinkumware probablemente no habrá cambiado ese hecho desde VC6. ¿Estoy allí?
  2. ¿Qué aspecto tiene actualmente en gcc ? Si es realmente O (n), ¿por qué los desarrolladores decidieron hacerlo?

Respuesta Pre-C ++ 11

Tiene razón en que la norma no establece cuál debe ser la complejidad de list :: size (); sin embargo, sí recomienda que “tenga una complejidad constante” (Nota A en la Tabla 65).

Aquí hay un artículo interesante de Howard Hinnant que explica por qué algunas personas piensan que list :: size () debería tener O (N) complejidad (básicamente porque creen que O (1) list :: size () hace que list :: splice () tenga O (N) complejidad) y por qué una lista O (1) :: size () es una buena idea (en opinión del autor):

Creo que los puntos principales en el documento son:

  • hay pocas situaciones en las que el mantenimiento de un conteo interno para que list::size() pueda ser O (1) hace que la operación de empalme se vuelva lineal
  • probablemente haya muchas más situaciones en las que alguien pueda desconocer los efectos negativos que pueden ocurrir porque llaman a un size() O (N) size() (como el ejemplo en el que se llama a list::size() mientras se mantiene un locking).
  • que en lugar de permitir size() sea ​​O (N), en aras de la “menor sorpresa”, la norma debería requerir que cualquier contenedor que implemente size() implemente de forma O (1). Si un contenedor no puede hacer esto, no debería implementar size() en absoluto. En este caso, el usuario del contenedor se dará cuenta de que el size() no está disponible, y si aún desea o necesita obtener el número de elementos en el contenedor, aún puede usar container::distance( begin(), end()) para obtener ese valor, pero serán completamente conscientes de que se trata de una operación O (N).

Creo que tiendo a estar de acuerdo con la mayoría de sus razonamientos. Sin embargo, no me gusta su adición propuesta a las sobrecargas de splice() . Tener que pasar una n que debe ser igual a la distance( first, last) para obtener un comportamiento correcto parece una receta para errores difíciles de diagnosticar.

No estoy seguro de qué debería o podría hacerse para seguir adelante, ya que cualquier cambio tendría un impacto significativo en el código existente. Pero tal como está, creo que el código existente ya se ha visto afectado: el comportamiento puede ser bastante diferente de una implementación a otra para algo que debería estar bien definido. Tal vez el comentario de Onebyone sobre tener el tamaño “en caché” y marcado conocido / desconocido podría funcionar bien – obtienes un comportamiento O (1) amortizado – la única vez que obtienes un comportamiento O (N) es cuando la lista es modificada por algunas operaciones de empalme () . Lo bueno de esto es que los implementadores pueden hacerlo hoy sin un cambio en el estándar (a menos que me falta algo).

Hasta donde yo sé, C ++ 0x no está cambiando nada en esta área.

En C ++ 11 se requiere que para cualquier contenedor estándar, la operación .size() debe completarse en complejidad “constante” (O (1)). (Tabla 96 – Requisitos del contenedor). Anteriormente, en C ++ 03 .size() debería tener complejidad constante, pero no es necesario (consulte ¿Es std :: string size () una operación O (1)? ).

El cambio en el estándar es introducido por n2923: especificando la complejidad del tamaño () (Revisión 1) .

Sin embargo, la implementación de .size() en libstdc ++ todavía usa un algoritmo O (N) en gcc hasta 4.8:

  /** Returns the number of elements in the %list. */ size_type size() const _GLIBCXX_NOEXCEPT { return std::distance(begin(), end()); } 

Consulte también ¿Por qué std :: list es más grande en c ++ 11? para el detalle por qué se mantiene de esta manera.

Actualización : std::list::size() es correctamente O (1) cuando se usa gcc 5.0 en modo C ++ 11 (o superior).


Por cierto, .size() en libc ++ es correctamente O (1):

 _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT {return base::__sz();} ... __compressed_pair __size_alloc_; _LIBCPP_INLINE_VISIBILITY const size_type& __sz() const _NOEXCEPT {return __size_alloc_.first();} 

He tenido que buscar en la lista :: tamaño de gcc 3.4 antes, así que puedo decir esto:

  1. usa std :: distancia (cabeza, cola)
  2. std :: distance tiene dos implementaciones: para los tipos que satisfacen RandomAccessIterator, usa “tail-head”, y para los tipos que simplemente satisfacen InputIterator, usa un algoritmo O (n) que se basa en “iterator ++”, contando hasta que alcanza el valor cola.
  3. std :: list no satura a RandomAccessIterator, por lo que el tamaño es O (n).

En cuanto al “por qué”, solo puedo decir que std :: list es apropiado para problemas que requieren acceso secuencial. Almacenar el tamaño como una variable de clase introduciría una sobrecarga en cada inserción, eliminación, etc., y ese desperdicio es un gran no-no por la intención del STL. Si realmente necesita un tamaño de tiempo constante (), use std :: deque.

Personalmente, no veo el problema de que el empalme sea O (N) como la única razón por la cual se permite que el tamaño sea O (N). No pagas por lo que no usas es un lema importante de C ++. En este caso, mantener el tamaño de la lista requiere un incremento / decremento adicional en cada inserción / borrado, ya sea que controle el tamaño de la lista o no. Esta es una pequeña sobrecarga fija, pero aún es importante considerarla.

Verificar el tamaño de una lista rara vez es necesario. Iterando de principio a fin sin preocuparse por el tamaño total es infinitamente más común.

Yo iría a la fuente . La página STL de SGI dice que está permitido tener una complejidad lineal. Creo que las pautas de diseño que siguieron fueron para permitir que la implementación de la lista sea lo más general posible y, por lo tanto, para permitir una mayor flexibilidad en el uso de listas.

Este informe de errores: [C ++ 0x] std :: list :: size complexity , captura en detalles insoportables el hecho de que la implementación en GCC 4.x es tiempo lineal y cómo la transición a tiempo constante para C ++ 11 fue lenta en venir (disponible en 5.0) debido a problemas de compatibilidad ABI.

La página de manual para la serie GCC 4.9 todavía incluye el siguiente descargo de responsabilidad:

El soporte para C ++ 11 aún es experimental y puede cambiar de manera incompatible en versiones futuras.


Aquí se hace referencia al mismo informe de error: ¿Debería std :: list :: size tener una complejidad constante en C ++ 11?

Si usa listas correctamente, probablemente no note ninguna diferencia.

Las listas son buenas con estructuras de big data que desea reorganizar sin copiar, o para datos que desea mantener punteros válidos después de la inserción.

En el primer caso, no hay diferencia, en el segundo preferiría la implementación antigua (más pequeña) de tamaño ().

De todos modos, std es más acerca de la corrección y el comportamiento estándar y la “facilidad de uso” que la velocidad bruta.