c++ - bool - ¿Por qué es std:: vector contiguo?
vector bool c++ (5)
Además del hecho de que el estándar lo define como contiguo, ¿por qué es std :: vector contiguo?
Si se queda sin espacio, debe reasignar un nuevo bloque y copiar el bloque anterior al nuevo antes de continuar.
¿Y si no fuera contiguo? Cuando el almacenamiento se llena, simplemente asignaría un nuevo bloque y mantendría el bloque anterior. Al acceder a través de un iterador, sería simple>, <verifica en qué bloque está el índice y lo devuelve. De esta forma no es necesario copiar la matriz cada vez que se queda sin espacio.
¿Esto realmente funcionaría / sería mejor? ¿O me estoy perdiendo algo?
Al hacer que std::vector contiguo, se puede tratar de manera muy similar a una matriz. Sin embargo, también es de tamaño variable. Su tamaño es definible en tiempo de ejecución, en lugar de tiempo de compilación. Además, se puede usar un vector para asignar memoria a funciones que requieren un búfer. La ventaja de esto es que la memoria se liberará por el vector cuando se salga del alcance. Por ejemplo, cuando se usa ReadFile se puede usar un vector para crear un búfer:
unsigned int bytesRead = 0;
std::vector<char> buffer(fileSize);
// open file, etc.
ReadFile(hFileIn, buffer.data(), buffer.size(), &bytesRead, nullptr);
Tenga en cuenta que los data son nuevos en C ++ 11. En el código anterior probablemente verá un equivalente &(buffer.at(0)) o &(buffer[0]) que devuelve la dirección del primer elemento.
Un std::deque sería un mejor ajuste para lo que estás describiendo.
Como complemento de las otras respuestas (están bastante completas), hay una situación en la que prefiere que los vectores no sean contiguos: cuando necesita cambiar el tamaño de un vector al mismo tiempo. Es por eso que Intel Thread Building Block proporciona tbb :: concurrent_vector, que es más o menos lo que dijiste que esperarías
"Cuando el almacenamiento se llena, solo asignaría un nuevo bloque y mantendría el antiguo. Al acceder a través de un iterador, sería sencillo>, <comprueba para ver en qué bloque está el índice y lo devuelve".
Luego, una comparación entre tbb :: concurrent_vector y std :: vector le daría una mejor comprensión de las ventajas (velocidad) y desventajas (no puede crecer std :: vector al mismo tiempo) de la memoria contigua. Espero que tbb :: concurrent_vector esté mejor optimizado que std :: deque y esa es la razón por la que tbb :: concurrent_vector vs std :: vector es una comparación más justa.
Hay algunas razones para esto:
En primer lugar, la iteración sobre un contenedor contiguo es mucho más rápida que sobre un contenedor no contiguo debido a dos factores: el primero es la predicción de bifurcaciones : el procesador no necesita deshacerse de su canalización cada vez que termina de leer uno de los subgrupos. contenedores, y menos reinicios de tubería significa un código más rápido. La segunda es que es mucho más fácil almacenar en caché un bloque de memoria contiguo que un montón de pequeños bloques surtidos, lo que hace que sea mucho más probable que la matriz se almacene en caché en su totalidad.
En segundo lugar, hay una gran cantidad de código C ++ escrito que debe interactuar con el código C, y una gran cantidad de ese código esperará un espacio contiguo de memoria al recibir una matriz / búfer, porque esa es la forma menos dependiente de la implementación de la estructura de datos. para hacerlo. Cuando interactúa con el código que espera buffers / arreglos constantemente, la sobrecarga de convertir su std::deque en un array toma su peaje en comparación con el paso prácticamente instantáneo de un std::vector a un array (que puede ser básicamente dando un puntero a la matriz interna).
Todo esto justifica la existencia de un contenedor contiguo. Como han dicho otros, cuando no necesita una iteración rápida o contiguo de memoria, siempre puede usar un std::deque .
La biblioteca estándar de C ++ también define un contenedor similar a una matriz no contigua: std::deque<T> . La iteración sobre un std::deque<T> es mucho más lenta que la iteración sobre un std::vector<T> . Si la operación es bastante trivial, puede ser algo 5 veces más lenta: estos son los tiempos reales que obtengo al comparar la acumulación de una secuencia de números enteros. ¡Este es el costo que está pagando por una representación no contigua!
La razón de esta desaceleración bastante pronunciada es que gcc sabe cómo vectorizar el bucle en un std::vector<int> pero no para un std::deque<int> . Incluso sin vectorización, la iteración es aproximadamente un 30% más lenta. Es decir, el costo bastante pequeño de las std::vector<T> de std::vector<T> realidad no importa mucho.
Si std::vector no garantizase la contigüidad, se inventaría un nuevo contenedor que lo hizo.
La garantía de continuidad facilita la interoperabilidad con el código existente que espera una matriz contigua, y también ofrece un rendimiento muy bueno porque es fácil de almacenar en caché. (La inserción / eliminación en el medio es en la práctica muy rápida para tamaños moderados debido a esto).
Copiar la matriz en la expansión es sorprendentemente barato: si agrega un vector a un millón de elementos de uno en uno, cada elemento se habrá copiado en promedio una vez.