c++ - español - ¿Por qué vector<bool> no es un contenedor STL?

vector c++ español

Question

Elemento 18 del libro de Scott Meyers Effective STL: 50 formas específicas de mejorar el uso de la biblioteca de plantillas estándar para evitar el vector <bool> ya que no es un contenedor STL y realmente no contiene bools.

El siguiente código:

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

no compilará, violando el requisito de contenedores STL.

Error:

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

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

¿En qué consiste realmente el vector<bool> ?

El artículo dice además:

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

¿Se puede usar esto como una alternativa al vector<bool> ?

¿Alguien puede explicar esto?

Answer 1

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

Scott Meyers tiene un artículo largo 30 en C + + más efectivo sobre clases de proxy. Puede recorrer un largo camino para casi imitar los tipos integrados: 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 mutuamente inversos.

Sin embargo, en algún punto uno necesita mapear los objetos proxy para comportarse como T* o T& . Para los proxies de iterador, uno puede sobrecargar el operator->() y acceder a la interfaz de la plantilla T sin volver a implementar toda la funcionalidad. Sin embargo, para los proxies de referencia, necesitaría sobrecargar al operator.() , Y eso no está permitido en el C ++ actual (aunque Sebastian Redl presentó dicha propuesta en BoostCon 2013). Puede hacer un trabajo detallado como un miembro .get() dentro del proxy de referencia, o implementar toda la interfaz de T dentro de la referencia (esto es lo que se hace para vector<bool>::bit_reference ), pero esto pierda la sintaxis incorporada o introduzca conversiones definidas por el usuario que no tengan semántica integrada para las conversiones de tipo (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 (automático) que en C ++ 98.

Answer 2

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

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

Se comporta como la versión no especializada del 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 sea
  almacenado en un solo bit
• Los elementos no se construyen utilizando el objeto asignador, pero su valor se establece directamente en el bit apropiado en el almacenamiento interno.
• Copia de función de miembro y una nueva firma para intercambio 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 simple bool.
• Los tipos de puntero e iterador utilizados por el contenedor no son necesariamente punteros ni iteradores conformes, aunque
  simulará la mayor parte de su comportamiento esperado.

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

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

Answer 3

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

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

también interesante, aunque no es un vector de bits conforme stl es el llvm :: BitVector desde here .

la esencia de llvm::BitVector es una clase anidada llamada reference y sobrecarga del operador adecuada para hacer que el BitVector comporte de forma similar al vector con algunas limitaciones. El siguiente código es una interfaz simplificada para mostrar cómo BitVector oculta una clase llamada reference para hacer que la implementación real casi se comporte 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 bonitas 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 un defecto, intenta 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 de llvm::BitVector )

esta es la versión de llvm muy simple. std::vector<bool> también tiene iteradores de trabajo. por lo tanto, 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 hay limitaciones en std::vector<bool> que hace que se comporte de manera diferente en algunos casos.

Answer 4

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

En un documento titulado "Deprecating Vestigial Library Parts in C ++ 17"
Hay una propuesta para Reconsiderar la especialización parcial de vectores .

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 que no satisfacen los requisitos de un iterador de acceso aleatorio. Un intento anterior de depreciar este contenedor fue rechazado para C ++ 11, N2204 .

Una de las razones del rechazo es que no está claro lo que significaría desaprobar una especialización particular de una plantilla. Eso podría abordarse con una redacción cuidadosa. El problema más grande es que la especialización (empaquetada) del vector ofrece una optimización importante que los clientes de la biblioteca estándar realmente buscan, pero que ya no estarán disponibles. Es poco probable que podamos desaprobar esta parte de la norma hasta que se proponga y acepte una instalación de reemplazo, como N2050 . Lamentablemente, actualmente no se ofrecen propuestas revisadas al Grupo de trabajo de evolución de la biblioteca.

Answer 5

Por motivos de optimización del espacio, el estándar C ++ (tan atrás como C ++ 98) explícitamente llama 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 un tipo de "conjunto de bits dinámico"). A cambio de esta optimización, no ofrece todas las capacidades y la interfaz de un contenedor estándar normal.

En este caso, como no puede tomar la dirección de un bit dentro de un byte, cosas como operator[] no pueden devolver un bool& en su lugar, devolver un objeto proxy que permita manipular el bit en cuestión. Como este objeto proxy no es un bool& , no puede asignar su dirección a un bool* como lo haría con el resultado de una llamada de ese 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 llamada así que cada bool toma un byte y puede tomar la dirección del valor devuelto por el operator[] .

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

Answer 6

vector<bool> contiene valores booleanos en forma comprimida usando solo un bit para el 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 algunos bits en la memoria y le permite usar operadores y moldes estándar.