c++ - QList vs QVector revisado

qt qt5

Question

Mi pregunta es básicamente cuándo elegir QVector y cuándo elegir QList como su contenedor Qt. Lo que ya sé:

1. Qt docs: clase QList

Para la mayoría de los propósitos, QList es la clase correcta para usar. Su API basada en índices es más conveniente que la API basada en iteradores de QLinkedList, y generalmente es más rápida que QVector debido a la forma en que almacena sus elementos en la memoria. También se expande a menos código en su ejecutable.

2. Lo mismo está escrito en esta muy popular Q&A: QVector vs QList . También favorece a QList.

3. Pero: en la reciente Cumbre Mundial Qt 2015, KDAB presentó "Por qué QList es perjudicial", esto es básicamente aquí:

QList considerado dañino

No use QList, use Q_DECLARE_TYPEINFO

Por lo que entiendo, la idea es que QList para casi todos los tipos es ineficiente cuando se asignan nuevos elementos en el montón. Cada vez que agrega un elemento nuevo, se llama new (una vez por elemento) y esto es ineficiente en comparación con QVector .

Es por eso que ahora estoy tratando de entender: ¿es QVector que debemos elegir como contenedor predeterminado?

Answer 1

Si el tamaño del tipo de elemento de QList es mayor que el tamaño del puntero, QList funciona mejor que QVector porque no almacena los objetos de forma secuencial, sino que almacena secuencialmente los punteros para acumular copias.

Tiendo a decir lo contrario. Va a estar mucho peor, al pasar por los artículos. Si lo almacena como punteros en el montón, ¿no estará QList mucho peor que QVector? La razón por la que el almacenamiento secuencial (QVector todo el tiempo) es tan bueno es que es fácil de almacenar en caché, una vez que almacena los punteros, pierde la localidad de los datos, comienza a tener fallas de caché y es horrible para el rendimiento.

El contenedor "predeterminado" IMHO debería ser un QVector (o std :: vector), si está preocupado por una gran cantidad de reasignación, preasigne una cantidad razonable, pague el costo de una vez y se beneficiará a largo plazo.

Utilice el * Vector por defecto, si tiene problemas de rendimiento, perfílelo y cambie según sea necesario.

Answer 2

En Qt 5.7, la documentación se modificó en relación con el tema tratado aquí. En QVector ahora se afirma:

QVector debe ser su primera opción por defecto. QVector<T> generalmente dará un mejor rendimiento que QList<T> , porque QVector<T> siempre almacena sus elementos secuencialmente en la memoria, donde QList<T> asignará sus elementos en el montón a menos que sizeof(T) <= sizeof(void*) y se ha declarado que T es Q_MOVABLE_TYPE o Q_PRIMITIVE_TYPE utilizando Q_DECLARE_TYPEINFO .

Se refieren a este artículo de Marc Mutz .

Así que el punto de vista oficial ha cambiado.

Answer 3

Imagina, que tenemos la clase DataType.

QVector - matriz de objetos, tales como:

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList: matriz de punteros a objetos, como:

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

Por lo tanto, el acceso directo por índice será más rápido para QVector:

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

Pero el intercambio será más rápido para QList, si sizeof (DataType)> sizeof (DataType *):

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object
// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

Por lo tanto, si necesita acceso directo sin cambiar las operaciones entre elementos (como la ordenación, por ejemplo), o sizeof (DataType) <= sizeof (DataType *), lo mejor es usar QVector. En otro caso usar QList.

Answer 4

QList es el mejor contenedor posible para usar en general, como indica la documentación. Si el tamaño del tipo de los elementos es <= del tamaño del puntero = máquina y OS bit = 4 u 8 bytes, entonces los objetos se almacenan de la misma manera que QVector - secuencialmente en la memoria. Si el tamaño del tipo de elemento de QList es mayor que el tamaño del puntero, QList funciona mejor que QVector porque no almacena los objetos de forma secuencial, sino que almacena secuencialmente los punteros para acumular copias. En el caso de 32 bits, la imagen es la siguiente:

sizeof( T ) <= sizeof( void* )
=====
QList< T > = [1][1][1][1][1]
or
[2][2][2][2][2]
or
[3][3][3][3][3]
or
[4][4][4][4][4] = new T[];
sizeof( T ) > sizeof( void* )
=====
QList< T > = [4][4][4][4][4] = new T*[]; // 4 = pointer''s size
| | ... |
new T new T new T

En caso de que desee que sus objetos se distribuyan secuencialmente en la memoria sin importar el tamaño de sus elementos, como suele ser el caso con la programación OpenGL, entonces debe usar QVector.

Aquí hay una descripción detallada de las partes internas de QList.

Answer 5

QList se comporta de manera diferente según lo que haya dentro (consulte la struct MemoryLayout código fuente struct MemoryLayout ):

• si sizeof T == sizeof void* y T se define Q_MOVABLE_TYPE , entonces QList<T> comporta exactamente como QVector , es decir, los datos se almacenan de forma contigua en la memoria.

• si sizeof T < sizeof void* y T se define Q_MOVABLE_TYPE , entonces QList<T> cada entrada para sizeof void* , y pierde la compatibilidad de diseño con QVector.

• en todos los demás casos, QList<T> es una lista vinculada y, por lo tanto, lenta en algún grado.

Este comportamiento es lo que hace que QList<T> casi siempre sea una mala elección, ya que, dependiendo de los detalles ingeniosos, QList<T> es realmente una lista o un vector. Eso es un mal diseño de API y propenso a errores. (Por ejemplo, se encontrará con errores si tiene una biblioteca con una interfaz pública que utiliza una QList<MyType> internamente y en su interfaz pública. sizeof MyType is < sizeof void* , pero digamos que olvidó declarar MyType como Q_MOVABLE_TYPE . Más adelante, querrá agregar Q_MOVABLE_TYPE . Esto es incompatible con los binarios, lo que significa que ahora tiene que volver a compilar todo el código que usa su biblioteca, ya que el diseño de la memoria de QList<MyType> cambió en la API pública. pierda esto e introduzca un error. Esto ilustra bastante bien por qué QList es una mala elección aquí.)

Dicho esto, QList todavía no es del todo malo: probablemente hará lo que usted desea en la mayoría de los casos, pero quizás haga el trabajo entre bastidores de manera diferente a lo que podría esperar.

La regla de oro es:

• En lugar de QList, use QVector<T> o QVector<T*> , ya que explícitamente dice lo que quiere. Puedes combinar eso con std::unique_ptr .

• En C ++ 11 y en adelante, incluso se considera mejor usar simplemente std::vector , ya que se comportará correctamente en un bucle de rango basado en rango . (QVector y QList pueden separarse y, por lo tanto, realizar una copia profunda).

Puede encontrar todos estos detalles y más en una here y en el video de Olivier Goffart .

Answer 6

Qt anuncia QList como el "gato de todos los comercios", pero la otra mitad de ese dicho es "maestro de ninguno". Yo diría que QList es un buen candidato si planea agregarse a ambos extremos de la lista, y esos no son más grandes que un puntero, ya que QList reserva espacio antes y después. De eso se trata, me refiero a las buenas razones para usar QList .

QList almacenará automáticamente los objetos "grandes" como punteros y asignará los objetos en el montón, lo que puede considerarse bueno si usted es un bebé, que no sabe cómo declarar un QVector<T*> y usar la asignación dinámica. Esto no es necesariamente algo bueno, y en algunos casos solo aumentará el uso de la memoria y agregará una indirección adicional. En mi opinión, siempre es una buena idea ser explícito acerca de lo que desea, ya sea punteros o instancias. Incluso si desea una asignación de montón, siempre es mejor asignarlo usted mismo y simplemente agregar el puntero a la lista que construir el objeto una vez, luego tener copia construir eso en el montón.

Qt le devolverá una QList en una gran cantidad de lugares con gastos generales, por ejemplo, cuando obtiene hijos de QObject o busca niños. En este caso, no tiene sentido usar un contenedor que asigne espacio antes del primer elemento, ya que es una lista de objetos que ya están allí, no es algo que probablemente prefiera. Tampoco me gusta mucho la ausencia de un método de cambio de resize() .

Imagine una situación en la que tenga un objeto con un tamaño de 9 bytes y una alineación de bytes en un sistema de 64 bits. Es "demasiado" para QList por lo que en su lugar usará un puntero de 8 bytes + sobrecarga de CPU para la asignación lenta del montón + sobrecarga de memoria para la asignación del montón. Usará el doble de la memoria y con una dirección adicional para el acceso, difícilmente ofrecerá ventajas de rendimiento como se anuncia.

Por eso, QVector no puede convertirse repentinamente en el contenedor "predeterminado" (no se cambian los caballos en la mitad de la carrera), es una cuestión heredada, ya que Qt es un marco tan antiguo, y aunque muchas cosas han quedado en desuso, se realizan cambios en los valores predeterminados ampliamente utilizados no siempre son posibles, no sin romper mucho código o producir un comportamiento no deseado. Bien o mal, es probable que QList continúe siendo el valor predeterminado en todo Qt 5, y probablemente también en la próxima versión principal. La misma razón por la que Qt continuará utilizando punteros "tontos", durante años después de que los punteros inteligentes se hayan convertido en una necesidad y todos estén llorando por lo malos que son los punteros simples y por qué no deberían usarse nunca.

Dicho esto, nadie te obliga a utilizar QList en tu diseño. No hay ninguna razón por la que QVector no deba ser su contenedor predeterminado. Yo mismo no uso QList ninguna parte, y en las funciones Qt que devuelven una QList simplemente uso como un elemento temporal para mover cosas a un QVector .

Además, y esto es solo mi opinión personal, pero encuentro muchas decisiones de diseño en Qt que no necesariamente tienen sentido, ya sea que el rendimiento o la memoria utilicen la eficiencia o la facilidad de uso, y en general hay una gran cantidad de marcos e idiomas a los que les gusta promover sus formas de hacer las cosas, no porque sea la mejor manera de hacerlo, sino porque es su forma de hacerlo.

Por último, si bien no menos importante:

Para la mayoría de los propósitos, QList es la clase correcta para usar.

Realmente se reduce a cómo se entiende esto. En este contexto, "la derecha" no significa "lo mejor" o "lo óptimo", sino "lo suficientemente bueno" como en "lo hará, aunque no sea lo mejor". Especialmente si no sabes nada sobre las diferentes clases de contenedores y cómo funcionan.

Para la mayoría de los propósitos, QList hará.

Para resumir las cosas:

QList PROs

• tiene la intención de anteponer objetos que no sean más grandes que el tamaño de un puntero, ya que reserva algo de espacio en el frente
• tiene la intención de insertar en la mitad de los objetos de la lista (sustancialmente) más grandes que un puntero (y estoy siendo generoso aquí, ya que puede usar fácilmente QVector con punteros explícitos para lograr lo mismo y más barato, sin copia adicional), ya que al cambiar el tamaño La lista, no se moverán objetos, solo punteros.

QList

• no tiene un método resize() , reserve() es una trampa sutil, ya que no aumentará el tamaño válido de la lista, incluso si el acceso al índice funciona, cae en la categoría UB, además, no podrá iterar esa lista
• hace una copia adicional y asigna un montón cuando el objeto es más grande que un puntero, lo que también podría ser un problema si la identidad del objeto es importante
• utiliza una dirección indirecta adicional para acceder a objetos más grandes que un puntero
• tiene sobrecarga de tiempo de CPU y uso de memoria debido a los dos últimos, también menos fácil de almacenar en caché
• viene con una sobrecarga adicional cuando se usa como un valor de retorno de "búsqueda", ya que no es probable que se antepase o se agregue a eso
• solo tiene sentido si el acceso al índice es una necesidad, para una mejora óptima de la inserción y el inserto, una lista vinculada podría ser una mejor opción.

Los CON superan ligeramente a los PRO, lo que significa que, si bien el uso "casual" de QList puede ser aceptable, definitivamente no desea usarlo en situaciones donde el tiempo de CPU y / o el uso de la memoria son un factor crítico. En general, QList es más adecuado para el uso perezoso y descuidado, cuando no desea considerar el contenedor de almacenamiento óptimo para el caso de uso, que normalmente sería un QVector<T> , un QVector<T*> o una QLinkedList (y excluyo los contenedores "STL", ya que estamos hablando de Qt, los contenedores Qt son igual de portátiles, a veces más rápidos y, sin duda, más fáciles y más limpios de usar, mientras que los contenedores std son innecesariamente detallados).

Answer 7

QList es una matriz de void* .

En su funcionamiento normal, los elementos new en el montón y almacena un puntero a ellos en la matriz void* . Como una lista enlazada, eso significa que las referencias (pero, a diferencia de las listas enlazadas, ¡no los iteradores!) A los elementos contenidos en la lista siguen siendo válidas en todas las modificaciones del contenedor hasta que el elemento se elimine nuevamente del contenedor. De ahí el nombre "lista". Esta estructura de datos se denomina lista-matriz y se usa en muchos lenguajes de programación donde cada objeto es de tipo de referencia (por ejemplo, Java). Es una estructura de datos muy hostil al caché, como todos los contenedores basados ​​en nodos.

Pero el cambio de tamaño de la lista de arreglos se puede tener en cuenta en una clase auxiliar independiente de tipo ( QListData ), que se supone que guarda un tamaño de código ejecutable. En mis experimentos, es casi imposible predecir cuál de QList , QVector o std::vector produce el código menos ejecutable.

Este habría sido un buen tipo de datos para los muchos tipos de referencia de Qt, como QString , QByteArray , etc., que consisten en nada más que un puntero pimpl. Para estos tipos, QList obtuvo una optimización importante: cuando el tipo no es más grande que un puntero (y tenga en cuenta que esta definición depende del tamaño del puntero de la plataforma (32 o 64 bits), en lugar de objetos de asignación de montón, los objetos se almacenan en las void* ranuras directamente.

Sin embargo, esto solo es posible si el tipo se puede reubicar de forma trivial . Eso significa que se puede reubicar en la memoria usando memcpy . La reubicación aquí significa que tomo un objeto, lo memcpy en otra dirección y, crucialmente, no ejecuto el destructor del objeto anterior.

Y aquí es donde las cosas empezaron a ir mal. Porque a diferencia de Java, en C ++, una referencia a un objeto es su dirección . Y mientras que en la QList original, las referencias permanecieron estables hasta que el objeto se eliminó de la colección nuevamente, al colocarlas en la matriz void* esta propiedad ya no contiene. Esto ya no es una "lista" para todos los propósitos y propósitos.

Sin embargo, las cosas siguieron saliendo mal porque permitieron que los tipos que son estrictamente más pequeños que un void* se QList en una QList . Pero el código de administración de memoria espera elementos del tamaño del puntero, por lo que QList agrega relleno (!). Eso significa que una QList<bool> en plataformas de 64 bits se ve así:

[ | | | | | | | [ | | | | | | | [ ...
[b| padding [b| padding [b...

En lugar de colocar 64 bools en una línea de caché, como hace QList , QList solo administra 8 .

Las cosas salieron mal fuera de toda proporción cuando los documentos comenzaron a llamar a QList un buen contenedor predeterminado. No es. Los estados originales de STL :

Vector es la clase de contenedor STL más simple y, en muchos casos, la más eficiente.

El STL efectivo de Scott Meyer tiene varios elementos que comienzan con "Preferir std::vector over ...".

Lo que es cierto en general, C ++ no está repentinamente mal solo porque está usando Qt.

Qt 6 solucionará ese error de diseño en particular. Mientras tanto, use QVector o std::vector .