Hmmm ... de la otra respuesta, ¿parece que el vector no se implementa como una lista vinculada? Estoy en lo cierto? Estoy usando esta lista como una colección que tendrá una rotación bastante alta de objetos agregados y eliminados. ¿Es esta matriz realmente la mejor implementación? ¿O hay una versión de lista vinculada?
interstar
4
@interstar - absolutamente correcto. Si realmente desea la semántica de lista vinculada, utilice std::list, aunque perderá la indexabilidad (no operator[]), por lo que no es realmente una matriz. listque tiene sus propias idiosincrasias, por lo que a vectormenudo es una mejor opción. En los contenedores estándar de C ++, tendrá que comprometerse de una forma u otra. Mire deque, eso puede ofrecer un mejor rendimiento para usted. Es (relativamente) fácil de medir vectorvs dequevs, listya que son en gran medida intercambiables en el código; solo use un typedef para su contenedor, por ejemplo typedef vector<MyObj> MyList.
Steve Townsend
bueno, probaré el vector primero. Porque index es útil. Si es demasiado lento, puedo moverme a la lista vinculada. Gracias
interstar
2
@interstar, ArrayListcomo puede adivinar por el nombre, tampoco está implementado como una lista vinculada. Puede que estés pensando en LinkedList. Además, incluso si tiene una rotación bastante alta de objetos agregados y eliminados de la lista, vectoraún podría ser más rápido que listsiempre que asigne suficiente espacio inicialmente para que no necesite reasignar (es decir, darle el espacio máximo que debería necesitar).
Kyle Strand
@KyleStrand Eso es interesante. Siempre asumí que ArrayList significaba "una cosa similar a una matriz que se implementa como una lista vinculada", en lugar de una "cosa similar a una lista vinculada que se implementa como una matriz".
Interstar
58
Un par de puntos adicionales se reutilizan vectoraquí.
A diferencia de ArrayListy Arrayen Java, no es necesario hacer nada especial para tratar a vectorcomo una matriz: se garantiza que el almacenamiento subyacente en C ++ es contiguo y se puede indexar de manera eficiente.
A diferencia de ArrayList, a vectorpuede contener de manera eficiente tipos primitivos sin encapsulación como un objeto completo.
Al retirar elementos de un vector, tenga en cuenta que los elementos que están encima del elemento eliminado deben moverse hacia abajo para preservar el almacenamiento contiguo. Esto puede resultar caro para contenedores grandes.
Si almacena objetos complejos en el, asegúrese de vectorque su constructor de copia y sus operadores de asignación sean eficientes. Bajo las sábanas, C ++ STL los usa durante la limpieza del contenedor.
Consejos sobre reserve()almacenamiento inicial (es decir, en la construcción del vector o en el momento de la inicialización) para minimizar la reasignación de memoria en la extensión posterior que se transfiere de Java a C ++.
Respuestas:
Utilice la
std::vectorclase de la biblioteca estándar.fuente
std::list, aunque perderá la indexabilidad (nooperator[]), por lo que no es realmente una matriz.listque tiene sus propias idiosincrasias, por lo que avectormenudo es una mejor opción. En los contenedores estándar de C ++, tendrá que comprometerse de una forma u otra. Miredeque, eso puede ofrecer un mejor rendimiento para usted. Es (relativamente) fácil de medirvectorvsdequevs,listya que son en gran medida intercambiables en el código; solo use un typedef para su contenedor, por ejemplotypedef vector<MyObj> MyList.ArrayListcomo puede adivinar por el nombre, tampoco está implementado como una lista vinculada. Puede que estés pensando enLinkedList. Además, incluso si tiene una rotación bastante alta de objetos agregados y eliminados de la lista,vectoraún podría ser más rápido quelistsiempre que asigne suficiente espacio inicialmente para que no necesite reasignar (es decir, darle el espacio máximo que debería necesitar).Un par de puntos adicionales se reutilizan
vectoraquí.A diferencia de
ArrayListyArrayen Java, no es necesario hacer nada especial para tratar avectorcomo una matriz: se garantiza que el almacenamiento subyacente en C ++ es contiguo y se puede indexar de manera eficiente.A diferencia de
ArrayList, avectorpuede contener de manera eficiente tipos primitivos sin encapsulación como un objeto completo.Al retirar elementos de un
vector, tenga en cuenta que los elementos que están encima del elemento eliminado deben moverse hacia abajo para preservar el almacenamiento contiguo. Esto puede resultar caro para contenedores grandes.Si almacena objetos complejos en el, asegúrese de
vectorque su constructor de copia y sus operadores de asignación sean eficientes. Bajo las sábanas, C ++ STL los usa durante la limpieza del contenedor.Consejos sobre
reserve()almacenamiento inicial (es decir, en la construcción del vector o en el momento de la inicialización) para minimizar la reasignación de memoria en la extensión posterior que se transfiere de Java a C ++.fuente