c++ - qvector

QVector vs QList (5)

De QtList doc:

QList para ser utilizado en la mayoría de los casos. Para estructuras con miles de elementos, permite una inserción eficiente en el medio y proporciona acceso indexado. prepend() y append() muy rápido ya que la memoria está preasignada en ambos extremos de la matriz interna. QList<T> es una matriz de puntero de tipo T. Si T tiene un puntero o un tipo de puntero compartido Qt, el objeto se almacena directamente en una matriz
QVector es preferible en el caso de una gran cantidad de append() o insert() de elementos nuevos con un tamaño mayor que un puntero ya que QVector asigna memoria para sus elementos en una única asignación de pila. Para QList , la inserción de un nuevo elemento requiere la asignación de memoria del nuevo elemento en el montón. En resumen, si desea que los elementos ocupen posiciones de memoria adyacentes, o si sus elementos son más grandes que un puntero y desea evitar la sobrecarga de QVector en el montón individualmente en el momento de la inserción, utilice QVector .

Tengo una lista de enteros que necesito iterar, pero una matriz es inadecuada. ¿Cuáles son las diferencias entre vectores y listas y hay algo que necesite saber antes de elegir un tipo?

Para que quede claro, he leído los documentos QT, pero este es el alcance de lo que sé:

QList, QLinkedList y QVector proporcionan una funcionalidad similar. Aquí hay una descripción general:
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 tu ejecutable.
Si necesita una lista vinculada real, con garantías de inserciones de tiempo constante en el medio de la lista e iteradores a elementos en lugar de índices, use QLinkedList.
Si desea que los elementos ocupen posiciones de memoria adyacentes, use QVector.

En QVector es similar a std::vector . QLinkedList es similar a std::list . QList es un vector basado en índice, pero la posición de memoria no está garantizada (como std::deque ).

QVector es como una matriz que puede cambiar de tamaño (aumentar o disminuir), pero viene con transacciones pesadas, computación y tiempo.

Por ejemplo, si desea agregar un elemento, se crea una nueva matriz, todos los elementos se copian a la nueva matriz, el nuevo elemento se agrega al final y la matriz anterior se elimina. Y viceversa para eliminar también.

Sin embargo, QLinkedList funciona con punteros. Por lo tanto, cuando se crea un nuevo elemento, solo se asigna un nuevo espacio de memoria y se vincula al único fragmento de memoria. Como funciona con punteros, es más rápido y eficiente.

Si tiene una lista de elementos que no espera cambiar mucho de tamaño, QVector probablemente sea bueno, pero generalmente QLinkedList se usa para la mayoría de los propósitos.

QVector es en su mayoría análogo a std::vector , como se puede adivinar por el nombre. QList está más cerca de boost::ptr_deque , a pesar de la aparente asociación con std::list . No almacena objetos directamente, sino que almacena punteros para ellos. Obtiene todos los beneficios de inserciones rápidas en ambos extremos, y las reasignaciones implican barajar punteros en lugar de copiar constructores, pero pierden la localidad espacial de un std::deque real o std::vector y obtienen muchas asignaciones de montón. Tiene algunas decisiones para evitar las asignaciones de montón para objetos pequeños, recuperando la localidad espacial, pero por lo que entiendo, solo se aplica a cosas más pequeñas que una int .

QLinkedList es análogo a std::list y tiene todos los inconvenientes. En términos generales, esta debería ser su última elección de un contenedor.

La biblioteca QT favorece mucho el uso de objetos QList , por lo que favorecerlos en su propio código a veces puede evitar un tedio innecesario. El uso extra del montón y el posicionamiento aleatorio de los datos reales teóricamente puede doler en algunas circunstancias, pero a menudo es imperceptible. Así que sugeriría usar QList hasta que el perfil sugiera cambiar a un QVector . Si espera que la asignación contigua sea importante [léase: está interactuando con el código que espera una T[] lugar de una QList<T> ] que también puede ser una razón para comenzar con QVector desde el QVector .

Si está preguntando sobre contenedores en general, y acaba de utilizar los documentos QT como referencia, entonces la información anterior es menos útil.

Un std::vector es una matriz que puede cambiar de tamaño. Todos los elementos se almacenan uno al lado del otro, y puede acceder a elementos individuales rápidamente. La desventaja es que las inserciones solo son eficientes en un extremo. Si coloca algo en el medio, o al principio, debe copiar los otros objetos para hacer espacio. En la notación big-oh, la inserción al final es O (1), la inserción en cualquier otro lugar es O (N), y el acceso aleatorio es O (1).

Un std::deque es similar, pero no garantiza que los objetos estén almacenados uno al lado del otro, y permite que la inserción en ambos extremos sea O (1). También requiere que se asignen trozos más pequeños de memoria a la vez, lo que a veces puede ser importante. El acceso aleatorio es O (1) y la inserción en el medio es O (N), lo mismo que para un vector . La localidad espacial es peor que std::vector , pero los objetos tienden a agruparse para que obtenga algunos beneficios.

Una std::list es una lista enlazada. Requiere la mayor cantidad de carga de memoria de los tres contenedores secuenciales estándar, pero ofrece una inserción rápida en cualquier lugar ... siempre que sepa por adelantado dónde debe insertar. No ofrece acceso aleatorio a elementos individuales, por lo que debe iterar en O (N). Pero una vez allí, la inserción real es O (1). El mayor beneficio de std::list es que puede unirlos rápidamente ... si mueve un rango completo de valores a una std::list diferente, toda la operación es O (1). También es mucho más difícil invalidar las referencias en la lista, lo que a veces puede ser importante.

Como regla general, prefiero std::deque a std::vector , a menos que necesite poder pasar los datos a una biblioteca que espera una matriz sin formato. std::vector está garantizado contiguo, por lo que &v[0] funciona para este fin. No recuerdo la última vez que utilicé una std::list , pero fue casi seguro porque necesitaba el guarete más fuerte sobre referencias válidas.

Las cosas han cambiado

Ahora estamos en Qt 5.8 y las cosas han cambiado, entonces la documentación. Da una respuesta clara y diferente a esta pregunta:

QVector debería ser su primera opción predeterminada. QVector generalmente dará mejor rendimiento que QList, porque QVector siempre almacena sus elementos secuencialmente en la memoria, donde QList asignará sus elementos en el montón a menos que sizeof (T) <= sizeof (void *) y T hayan sido declarados como Q_MOVABLE_TYPE o un Q_PRIMITIVE_TYPE que usa Q_DECLARE_TYPEINFO.
Vea los pros y los contras de utilizar QList para obtener una explicación. Sin embargo, QList se utiliza en todas las API Qt para pasar parámetros y devolver valores. Use QList para interactuar con esas API.