81 votos

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

Scott Meyers del Artículo 18 dice que para evitar la vector <bool> ya que no es un contenedor STL y la verdad es que no mantenga bools.

El código siguiente:

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

no va a compilar, violando el requisito de contenedores STL.

Error:

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

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

¿Qué vector<bool> consiste realmente?

El Artículo dice:

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

Puede ser usado como una alternativa a vector<bool>?

¿Alguien puede por favor explicar esto?

92voto

Mark B Puntos 60200

Por espacio de optimización de razones, el estándar de C++ (tan lejos como C++98) explícitamente llama vector<bool> como una norma especial recipiente donde cada bool usa solo un poco de espacio, en lugar de un byte como un normal bool (la aplicación de una especie de "dinámica bitset"). En cambio de esta optimización no ofrece todas las funciones y la interfaz normal de un contenedor estándar.

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

Por otro lado deque no tiene especialización llamado para que cada bool toma un byte y usted puede tomar la dirección del valor de retorno de operator[].

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

24voto

Ivan Smirnov Puntos 851

vector<bool> contiene valores booleanos en forma comprimida usando solo un poco de valor (y no de 8 como bool[] las matrices de hacer). No es posible devolver una referencia a un poco en c++, por lo que hay un especial de ayudante de tipo "bit de referencia", que proporciona una interfaz para algunos bits en la memoria y permite el uso de operadores estándar y modelos.

21voto

TemplateRex Puntos 26447

El problemas es que vector<bool> devuelve un proxy objeto de referencia en lugar de una verdadera referencia, de modo que C++98 del código de estilo bool * p = &v[0]; no se compilará. Sin embargo, C++moderno 11 auto p = &v[0]; puede ser hecho para compilar si operator& también devuelve un puntero de proxy objeto. Howard Hinnant ha escrito un post en el blog de detalle de las mejoras de algorítmico cuando el uso de tales proxy referencias y punteros.

Scott Meyers tiene un largo Artículo 30 en el Más Eficaz de C++ acerca de las clases de proxy. Usted puede venir a un largo camino de casi imitar el grupo builtin tipos: para cualquier tipo T, un par de servidores proxy (por ejemplo reference_proxy<T> y iterator_proxy<T>) puede ser mutuamente consistentes en el sentido de que reference_proxy<T>::operator&() y iterator_proxy<T>::operator*() son mutuamente inversas.

Sin embargo, en algún momento las necesidades de un mapa de los objetos proxy volver a comportarse como T* o T&. Para iterador proxies, uno puede sobrecargar operator->() y el acceso a la plantilla T's de la interfaz sin reimplementing toda la funcionalidad. Sin embargo, para referencia de los proxies, sería necesario sobrecargar operator.(), y eso no está permitido en C++ (aunque Sebastian Redl presentó una propuesta en BoostCon de 2013). Usted puede hacer un detallado trabajo de alrededor de un .get() miembro en el interior de la referencia proxy, o implementar todos los de T's de la interfaz dentro de la referencia (esto es lo que se hace para vector<bool>::bit_reference), pero este perderá el grupo builtin sintaxis o introducir definido por el usuario conversiones que no tienen incorporada la semántica para las conversiones de tipo (puede haber más de un usuario de conversión definido por el argumento).

TL;DR: no vector<bool> no es un contenedor debido a que la Norma requiere una referencia real, pero puede ser hecho a comportarse casi como un contenedor, al menos mucho más de cerca con C++11 (auto) que en C++98.

4voto

Alex Puntos 3973

Mira cómo se implementa. la STL se basa enormemente en plantillas y, por tanto, los encabezados contienen el código que hacer.

por ejemplo mira el stdc++ aplicación aquí.

también muy interesante, aunque no un stl conforme bit vector es el llvm::BitVector de aquí.

la esencia de la llvm::BitVector es una clase anidada llamado reference y adecuado sobrecarga de operadores para hacer la BitVector se comporta similar a vector con algunas limitaciones. El código siguiente es una interfaz simplificada para mostrar cómo BitVector esconde una clase llamada reference para hacer la implementación real casi se comportan como una matriz real de bool sin el uso de 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 tiene el buen 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 tiene un error, pruebe a ejecutar:

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

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

esto es muy simple llvm versión. std::vector<bool> tiene también el trabajo de los iteradores. por lo tanto la llamada for(auto i = b.begin(), e = b.end(); i != e; ++i) de trabajo. y también std::vector<bool>::const_iterator.

Sin embargo, todavía hay limitaciones en std::vector<bool> que le hace comportarse de manera diferente en algunos casos.

3voto

kvv Puntos 216

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

Vector de bool Esta es una versión especializada de vector, el cual es utilizado para los elementos de tipo bool y optimiza el espacio.

Se comporta igual que el no especializada versión de vector, con la siguientes cambios:

  • El almacenamiento no es necesariamente una matriz de valores bool, pero la implementación de la biblioteca puede optimizar el almacenamiento, de manera que cada valor es
    almacenados en un único bit.
  • Los elementos no son construidos mediante la asignación de objeto, pero su valor se establece directamente en el correcto bits en el almacenamiento interno.
  • Miembro de la función flip y una nueva firma para que los estados de intercambio.
  • Un especial tipo de miembro, de referencia, de una clase que accede a cada uno de los bits en el contenedor de almacenamiento interno con una interfaz que
    emula un bool referencia. Por el contrario, el tipo de miembro const_reference es una llanura de tipo bool.
  • El puntero y el iterador tipos que se utilizan en el contenedor no son necesariamente ni los punteros ni conforme iteradores, a pesar de que
    deberá simular la mayoría de su comportamiento esperado.

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

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

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X