C++ vector : La excepción a tantas, tantas reglas


Ejemplo

El estándar (sección 23.3.7) especifica que se proporciona una especialización del vector<bool> , que optimiza el espacio al empaquetar los valores bool , de modo que cada uno ocupa solo un bit. Dado que los bits no son direccionables en C ++, esto significa que varios requisitos en el vector no se colocan en el vector<bool> :

  • No se requiere que los datos almacenados sean contiguos, por lo que no se puede pasar un vector<bool> a una API de C que espera una matriz bool .
  • at() , operator [] y la anulación de referencias de los iteradores no devuelven una referencia a bool . Más bien, devuelven un objeto proxy que (de manera imperfecta) simula una referencia a un bool al sobrecargar sus operadores de asignación. Como ejemplo, es posible que el siguiente código no sea válido para std::vector<bool> , porque al eliminar la referencia a un iterador no se devuelve una referencia:
C ++ 11
std::vector<bool> v = {true, false};
for (auto &b: v) { } // error

De manera similar, las funciones que esperan un bool& argumento no se pueden usar con el resultado del operator [] o at() aplicado al vector<bool> , o con el resultado de la desreferenciación de su iterador:

  void f(bool& b);
  f(v[0]);             // error
  f(*v.begin());       // error

La implementación de std::vector<bool> depende tanto del compilador como de la arquitectura. La especialización se implementa empaquetando n booleanos en la sección más baja de la memoria. Aquí, n es el tamaño en bits de la memoria direccionable más baja. En la mayoría de los sistemas modernos esto es de 1 byte u 8 bits. Esto significa que un byte puede almacenar 8 valores booleanos. Esta es una mejora sobre la implementación tradicional donde 1 valor booleano se almacena en 1 byte de memoria.

Nota: el siguiente ejemplo muestra los posibles valores bitwise de bytes individuales en un vector<bool> tradicional vs. optimizado. Esto no siempre será cierto en todas las arquitecturas. Sin embargo, es una buena manera de visualizar la optimización. En los ejemplos siguientes, un byte se representa como [x, x, x, x, x, x, x, x].

Tradicional std::vector<char> almacena 8 valores booleanos:

C ++ 11
std::vector<char> trad_vect = {true, false, false, false, true, false, true, true};

Representación bitwise:

[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]

Specialized std::vector<bool> almacena 8 valores booleanos:

C ++ 11
std::vector<bool> optimized_vect = {true, false, false, false, true, false, true, true};

Representación bitwise:

[1,0,0,0,1,0,1,1]

Observe en el ejemplo anterior, que en la versión tradicional de std::vector<bool> , 8 los valores booleanos ocupan 8 bytes de memoria, mientras que en la versión optimizada de std::vector<bool> , solo usan 1 byte de memoria. Esta es una mejora significativa en el uso de la memoria. Si necesita pasar un vector<bool> a una API de estilo C, es posible que deba copiar los valores a una matriz o encontrar una mejor manera de usar la API, si la memoria y el rendimiento están en riesgo.