¿Por qué vector <bool> no es un contenedor STL?

El artículo 18 del libro de Scott Meyers Effective STL: 50 Specific Ways to Mejorar el uso de la biblioteca de plantillas estándar dice que se debe evitar, vector <bool>ya que no es un contenedor STL y en realidad no contiene bools.

El siguiente código:

vector <bool> v; 
bool *pb =&v[0];

no compilará, violando un requisito de los contenedores STL.

Error:

cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization

vector<T>::operator []Se supone que el tipo de retorno es T&, pero ¿por qué es un caso especial para vector<bool>?

¿En qué vector<bool>consiste realmente?

El artículo dice además:

deque<bool> v; // is a STL container and it really contains bools

¿Se puede utilizar como alternativa a vector<bool>?

¿Alguien puede explicar esto?

Por razones de optimización del espacio, el estándar C ++ (desde C ++ 98) llama explícitamente vector<bool>como un contenedor estándar especial donde cada bool usa solo un bit de espacio en lugar de un byte como lo haría un bool normal (implementando una especie de "conjunto de bits dinámico"). A cambio de esta optimización, no ofrece todas las capacidades e interfaz de un contenedor estándar normal.

En este caso, dado que no puede tomar la dirección de un bit dentro de un byte, cosas como operator[]no pueden devolver un, bool&sino devolver un objeto proxy que permite manipular el bit en particular en cuestión. Dado que este objeto proxy no es un bool&, no puede asignar su dirección a una bool*como podría hacerlo con el resultado de dicha llamada de operador en un contenedor "normal". A su vez, esto significa que bool *pb =&v[0];no es un código válido.

Por otro lado deque, no tiene ninguna especialización de este tipo, por lo que cada bool toma un byte y puede tomar la dirección del valor devuelto operator[].

Finalmente, tenga en cuenta que la implementación de la biblioteca estándar de MS es (posiblemente) subóptima ya que usa un tamaño de fragmento pequeño para deques, lo que significa que usar deque como sustituto no siempre es la respuesta correcta.

vector<bool>contiene valores booleanos en forma comprimida usando solo un bit por valor (y no 8 como lo hacen las matrices bool []). No es posible devolver una referencia a un bit en c ++, por lo que hay un tipo de ayuda especial, "referencia de bit", que le proporciona una interfaz para algún bit en la memoria y le permite utilizar operadores y conversiones estándar.

El problema es que vector<bool>devuelve un objeto de referencia de proxy en lugar de una referencia verdadera, por lo que el código de estilo C ++ 98 bool * p = &v[0];no se compilará. Sin embargo, el C ++ 11 moderno auto p = &v[0];se puede compilar si operator&también devuelve un objeto de puntero proxy . Howard Hinnant ha escrito una publicación de blog que detalla las mejoras algorítmicas al usar tales referencias y punteros de proxy.

Scott Meyers tiene un artículo 30 extenso en C ++ más efectivo sobre clases de proxy. Puede recorrer un largo camino para casi imitar los tipos incorporados: para cualquier tipo dado T, un par de proxies (por ejemplo, reference_proxy<T>y iterator_proxy<T>) se pueden hacer mutuamente consistentes en el sentido de que reference_proxy<T>::operator&()y iterator_proxy<T>::operator*()son inversos entre sí.

Sin embargo, en algún momento es necesario volver a mapear los objetos proxy para que se comporten como T*o T&. Para los proxies de iterador, se puede sobrecargar operator->()y acceder a la Tinterfaz de la plantilla sin volver a implementar toda la funcionalidad. Sin embargo, para los proxies de referencia, necesitaría sobrecargar operator.(), y eso no está permitido en C ++ actual (aunque Sebastian Redl presentó dicha propuesta en BoostCon 2013). Puede hacer una solución detallada como un .get()miembro dentro del proxy de referencia, o implementar toda Tla interfaz dentro de la referencia (esto es lo que se hace paravector<bool>::bit_reference), pero esto perderá la sintaxis incorporada o introducirá conversiones definidas por el usuario que no tienen semántica incorporada para las conversiones de tipos (puede tener como máximo una conversión definida por el usuario por argumento).

TL; DR : no vector<bool>no es un contenedor porque el Estándar requiere una referencia real, pero se puede hacer que se comporte casi como un contenedor, al menos mucho más cerca con C ++ 11 (auto) que en C ++ 98.

Muchos consideran que la vector<bool>especialización es un error.

En un documento "Deprecating Vestigial Library Parts in C ++ 17"
hay una propuesta para reconsiderar la especialización parcial vectorial .

Ha habido una larga historia de la especialización parcial bool de std :: vector que no satisface los requisitos del contenedor y, en particular, sus iteradores no satisfacen los requisitos de un iterador de acceso aleatorio. Se rechazó un intento anterior de desaprobar este contenedor para C ++ 11, N2204 .

Una de las razones del rechazo es que no está claro qué significaría desaprobar una especialización particular de una plantilla. Eso podría abordarse con una redacción cuidadosa. El problema más importante es que la especialización (empaquetada) de vector ofrece una optimización importante que los clientes de la biblioteca estándar buscan genuinamente, pero que ya no estaría disponible. Es poco probable que podamos desaprobar esta parte del estándar hasta que se proponga y acepte una instalación de reemplazo, como N2050 . Desafortunadamente, actualmente no se ofrecen propuestas revisadas de este tipo al Grupo de Trabajo de Evolución de las Bibliotecas.

Mira cómo se implementa. el STL se basa en gran medida en plantillas y, por lo tanto, los encabezados contienen el código que contienen.

por ejemplo, mire la implementación de stdc ++ aquí .

También es interesante, aunque no es un vector de bits conforme a stl, el llvm :: BitVector de aquí .

la esencia de llvm::BitVectores una clase anidada llamada referencey una sobrecarga de operador adecuada para hacer que el BitVectorcomportamiento sea similar vectorcon algunas limitaciones. El siguiente código es una interfaz simplificada para mostrar cómo BitVector oculta una clase llamada referencepara hacer que la implementación real se comporte casi como una matriz real de bool sin usar 1 byte para cada valor.

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

este código aquí tiene las buenas propiedades:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

Este código en realidad tiene una falla, intente ejecutar:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

no funcionará porque assert( (&b[5] - &b[3]) == (5 - 3) );fallará (dentro llvm::BitVector)

esta es la versión llvm muy simple. std::vector<bool>también tiene iteradores de trabajo. así la llamada for(auto i = b.begin(), e = b.end(); i != e; ++i)funcionará. y también std::vector<bool>::const_iterator.

Sin embargo, todavía existen limitaciones std::vector<bool>que hacen que se comporte de manera diferente en algunos casos.

Esto proviene de http://www.cplusplus.com/reference/vector/vector-bool/

Vector of bool Esta es una versión especializada de vector, que se utiliza para elementos de tipo bool y optimiza el espacio.

Se comporta como la versión no especializada de vector, con los siguientes cambios:

• El almacenamiento no es necesariamente una matriz de valores bool, pero la implementación de la biblioteca puede optimizar el almacenamiento para que cada valor se
  almacene en un solo bit.
• Los elementos no se construyen utilizando el objeto asignador, pero su valor se establece directamente en el bit adecuado en el almacenamiento interno.
• Cambio de función de miembro y nueva firma para cambio de miembro.
• Un tipo de miembro especial, referencia, una clase que accede a bits individuales en el almacenamiento interno del contenedor con una interfaz que
  emula una referencia bool. Por el contrario, el tipo de miembro const_reference es un bool simple.
• Los tipos de puntero e iterador utilizados por el contenedor no son necesariamente ni punteros ni iteradores conformes, aunque
  simularán la mayor parte de su comportamiento esperado.

Estos cambios proporcionan una interfaz peculiar a esta especialización y favorecen la optimización de la memoria sobre el procesamiento (que puede o no adaptarse a sus necesidades). En cualquier caso, no es posible instanciar la plantilla no especializada de vector para bool directamente. Soluciones alternativas para evitar que este rango use un tipo diferente (char, unsigned char) o contenedor (como deque) para usar tipos de envoltura o especializarse más en tipos de asignador específicos.

bitset es una clase que proporciona una funcionalidad similar para matrices de bits de tamaño fijo.