¿Por qué vector<bool> no es un contenedor STL?
El artículo 18 del libro de Scott Meyers STL efectivo: 50 formas específicas de 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 boolarchivos s.
El siguiente código:
vector <bool> v;
bool *pb =&v[0];
no se 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 esto como alternativa a vector<bool>?
¿Alguien puede explicar esto?
Por razones de optimización del espacio, el estándar C++ (que se remonta a C++98) llama explícitamente vector<bool>a 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 se puede tomar la dirección de un bit dentro de un byte, cosas como operator[]no pueden devolver bool&un objeto proxy que permite manipular el bit particular en cuestión. Dado que este objeto proxy no es un bool&, no puede asignar su dirección a un bool*como lo haría 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, dequeno tiene ninguna especialización, 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 porque utiliza un tamaño de fragmento pequeño para deques, lo que significa que usar deque como sustituto no siempre es la respuesta correcta.
El problema es que vector<bool>devuelve un objeto de referencia proxy en lugar de una referencia verdadera, por lo que el código de estilo C++98 bool * p = &v[0];no se compila. Sin embargo, auto p = &v[0];se puede compilar el C++ 11 moderno 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 utilizar dichas referencias y punteros de proxy.
Scott Meyers tiene un artículo 30 largo en C++ más efectivo sobre clases de proxy. Se 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>) pueden hacerse 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 asignar los objetos proxy para que se comporten como T*o T&. Para los proxies iteradores, 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, sería necesario sobrecargar operator.(), y eso no está permitido en el C++ actual (aunque Sebastian Redl presentó una propuesta de este tipo en BoostCon 2013). Puede crear una solución alternativa detallada como un .get()miembro dentro del proxy de referencia, o implementar toda la Tinterfaz de dentro de la referencia (esto es lo que se hace para vector<bool>::bit_reference), pero esto perderá la sintaxis incorporada o introducirá conversiones definidas por el usuario que no tiene semántica incorporada para 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 (automático) que en C++98.
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 existe un tipo de ayuda especial, "referencia de bit", que le proporciona una interfaz para algún bit en la memoria y le permite usar operadores y conversiones estándar.
Muchos consideran que la vector<bool>especialización es un error.
En un artículo "Desaprobación de piezas de biblioteca vestigiales en C++ 17"
hay una propuesta para
reconsiderar la especialización parcial de vectores .
Ha habido una larga historia de que la especialización parcial bool de std::vector 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. Esto podría abordarse con una redacción cuidadosa. El problema más importante es que la especialización (empaquetada) de vectores ofrece una optimización importante que los clientes de la biblioteca estándar realmente buscan, 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 sobre Evolución de la Biblioteca.
