EVAP 2

TEMA:
"CONTENEDORES BITSET" 

•  PREAMBULO

Los contenedores tipo bitset están pensados para almacenar bits. Es decir, conjuntos de N valores 0/1 denominados máscaras de bits ("Bitmask types"). En cierto sentido un bitset es el contenedor más simple del mundo, contiene un número máximo N(determinado en el momento de su definición) de elementos tipo bit. Podríamos considerar que un bitset es como una matriz de bits, de forma que podría establecerse un cierto paralelismo:

bit mb[125]; // L1: matriz de bits de 125 elementos
bitset <125> bs; // L2: bitset de 125 elementos 

Naturalmente la sentencia L1 es solo didáctica, no es posible en C++ porque no existe un tipo bit nativo. En cambio L2 si es correcta; define un contenedor bs de tipo bitset de 125 elementos.

La clase proporciona una serie de métodos y operadores para manipular los miembros del contenedor. Dada la naturaleza de sus miembros, estas operaciones son muy limitadas, como cambiar un valor 0 por un 1 y cosas por el estilo. Son las operaciones de bits ("Bitwise operations") que hemos tenido ocasión de ver anteriormente

Nota: al referirse a los valores de los miembros, además de cero y uno, es frecuente encontrar expresiones como fijar("set") poner a 1, y limpiar ("reset/clear") poner a cero.

Podría pensarse que este contenedor es innecesario, ya que los campos de bits pueden ser adecuadamente representados por los tipos enteros sin signo int, short y long, y manejados mediante los operadores estándar de manejo de bits. Sin embargo, los objetos de la clase bitset presentan ciertas ventajas. Entre otras, que pueden manejar campos de bits de cualquier longitud, mientras que los operadores estándar de manejo de bits quedan restringidos como máximo a los tipos long. Además, a cambio de un inevitable incremento del código respecto al que se deriva de utilizar directamente tipos simples, se consigue mayor comodidad de manejo. Por ejemplo, es posible crear directamente una máscara de bits en la forma: 

      string s1 = "10101101";
     bitset<16> bs1(s1);
     bitset<16> bs2("10101101");
     bitset<16> bs1(s1);
     bitset<16> bs2("10101101");
                  

Mientras que la construcción de una máscara equivalente utilizando los métodos convencionales nos obligaría a hacer: 

      unsigned short mb = 62125; 

lo que supone contar en binario para establecer que el número 62125 es el que corresponde a la máscara de bits deseada.

En cierto modo, este contenedor es un caso excepcional dentro de la STL. En el sentido que no proporciona ningún iterador para recorrer sus elementos. Pero esto no significa que no puede aplicársele ninguno de los algoritmos ofrecidos por la librería. Como en el caso de las matrices, sus elementos pueden ser accedidos mediante el operador subíndice [ ], que permite utilizarlo como si fuese un puntero, y por ende, un iterador.

•  LA CLASE BITSET   

La descripción de esta familia de tipos responde al prototipo siguiente 

      template <size_t N> class bitset { }; 

El tipo size_t depende de la implementación. Pero en el compilador Borland C++ 5.5 está definido como: 

      typedef unsigned int size_t; 

Habida cuenta que en el citado compilador: 

      #define UINT_MAX ULONG_MAX // maximum unsigned int value 

y que: 

      #define ULONG_MAX 4294967295UL // maximum unsigned long value

parece razonable pensar que este tipo de contenedor permite almacenar un número suficientemente grande de elementos (4 Gbits) para cubrir la mayoría de las necesidades prácticas.

La definición se encuentra en el fichero <bitset> que responde al siguiente esquema: 

      template <size_t N> class bitset;
     template <size_t N> bitset<N>
        operator&(const bitset<N>&, const bitset<N>&);
     template <size_t N> bitset<N>
        operator|(const bitset<N>&, const bitset<N>&);
     template <size_t N> bitset<N>
        operator^(const bitset<N>&, const bitset<N>&);
     template <class charT, class traits, size_t N>
        basic_istream<charT, traits>&
        operator>>(basic_istream<charT, traits>& is, bitset<N>& x);
     template <class charT, class traits, size_t N>
        basic_ostream<charT, traits>&
        operator<<(basic_ostream<charT, traits>& os, const bitset<N>&x);     template <size_t N> bitset<N>        operator&(const bitset<N>&, const bitset<N>&);     template <size_t N> bitset<N>        operator|(const bitset<N>&, const bitset<N>&);     template <size_t N> bitset<N>        operator^(const bitset<N>&, const bitset<N>&);     template <class charT, class traits, size_t N>        basic_istream<charT, traits>&        operator>>(basic_istream<charT, traits>& is, bitset<N>& x);     template <class charT, class traits, size_t N>        basic_ostream<charT, traits>&        operator<<(basic_ostream<charT, traits>& os, const bitset<N>&x); 

Como puede verse, aparte de la definición de la plantilla bitset propiamente dicha, esta cabecera contiene la definición de otras funciones-operador auxiliares para realizar operaciones entre objetos de tipo bitset. Por supuesto, todas estas definiciones se realizan el subespacio std. Observe que estas funciones-operador están definidas como funciones externas (no son métodos de la clase).

Como veremos a continuación, además de los anteriores, la clase bitset dispone de otra serie de métodos públicos auxiliares que permiten realizar diversas operaciones sobre los objetos (bits) alojados en estos contenedores. Pero debe recordar que la mayoría de operadores binarios solo son aplicables cuando el tamaño (número de bits) de ambos operandos coincide.

• CREACIÓN 

La clase ofrece tres constructores que permiten creación de contenedores bitset de tres formas distintas. En todas ellas es preciso especificar el tamaño máximo N que adoptará el contenedor . A partir de su creación pueden usarse menos bits del tamaño máximo, pero este número es fijo, no puede crecer, por lo que es preciso prever desde el principio el número máximo de elementos que deban almacenarse en el contenedor (a este número lo denominaremos tamaño del contenedor).

      bitset<N> bs1; // usa constructor por defecto
     bitset<N> bs2(310UL); // usa constructor explícito
     bitset<N> bs3("1011010011"); // usa Constructor explícito     bitset<N> bs2(310UL); // usa constructor explícito     bitset<N> bs3("1011010011"); // usa Constructor explícito

Los miembros del bitset se consideran numerados lo mismo que las matrices. Es decir, de 0 a N-1, y también como en aquellas su tamaño N debe ser conocida en tiempo de compilación!!. La organización de bits es de izquierda a derecha, de forma que si consideramos el bitset la representación de un entero sin signo, el valor del bit b[i] es 2i

      size_t N1 = 10;
     const size_t N2 = 10;
     bitset<N1> bs1; // Error!!
     bitset<N2> bs2; // Ok.
     bitset<10> bs3; // Ok. (mejor)     const size_t N2 = 10;     bitset<N1> bs1; // Error!!     bitset<N2> bs2; // Ok.     bitset<10> bs3; // Ok. (mejor) 

Como veremos a continuación, el estándar no define un constructor-copia ni un operador de asignación para la clase , por lo que la utilización de las expresiones: 

      bitset<N> bs2 = bs1; // usar constructor-copia
     bs2 = bs1; // usar operador de asignación     bs2 = bs1; // usar operador de asignación 

supone usar los métodos proporcionados "de oficio" por el compilador.

•  MÉTODOS PÚBLICOS

La clase bitset cuenta con una serie de utilidades estándar para manejo de los elementos del contenedor. Por supuesto, aparte de los constructores, la mayoría son utilidades de manejo de bits ("bitwise"). Aunque la clase no ofrece ningún iterador específico, hay algunas otras; incluso de entrada/salida.

Debe recordar que algunos operadores binarios solo son utilizables entre operandos (bitsets) de igual tamaño. 

4.1 Tres constructores: 

bitset(); bitset(unsigned long val); template<class charT, class traits, class Allocator> explicit bitset( const basic_string<charT,traits,Allocator>& str, typename basic_string<charT,traits,Allocator>::size_type pos = 0, typename basic_string<charT,traits,Allocator>::size_type n = basic_string<charT,traits,Allocator>::npos); 

4.2 Dos utilidades de E/S, que permiten introducir datos directamente desde el flujo de entrada y mostrarlos en el de salida: 

template <class charT, class traits, size_t N> basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, bitset<N>& x); template <class charT, class traits, size_t N> basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x); 

4.3 Varios operadores y funciones auxilares para manejo de bits: 

bitset<N>& operator&=(const bitset<N>& rhs); bitset<N>& operator|=(const bitset<N>& rhs); bitset<N>& operator^=(const bitset<N>& rhs); bitset<N>& operator<<=(size_t pos); bitset<N>& operator>>=(size_t pos); bitset<N> operator~() const; bitset<N> operator<<(size_t pos) const; bitset<N> operator>>(size_t pos) const; bitset<N>& flip(); bitset<N>& flip(size_t pos); 

4.4 Operadores relacionales de igualdad y desigualdad para comparar contenedores: 

bool operator==(const bitset<N>& rhs) const; bool operator!=(const bitset<N>& rhs) const;
4.5 Utilidades auxiliares y elemento de acceso:
reference operator[](size_t pos); unsigned long to_ulong() const; template <class charT, class traits, class Allocator> basic_string<charT, traits, Allocator> to_string() const; size_t count() const; size_t size() const; bool test(size_t pos) const; bool any() const; bool none() const; bitset<N>& set(); bitset<N>& set(size_t pos, int val = true); bitset<N>& reset();bitset<N>& reset(size_t pos); 

4.6 A continuación se muestra un resumen y un breve ejemplo de uso. 

Constructores: 

bitset(); 

C-1: Constructor por defecto. Instancia un objeto de la clase bitset<N> iniciando a cero todos sus elementos. 

Ejemplo:
bitset<125> bs1;
bitset(unsigned long val) 

C-2: Constructor que acepta un unsigned long como argumento. Crea un objeto de la clase bitset<N> que contiene la imagen de bits del argumento. Si sobra espacio porque N es mayor que la longitud necesaria, los bits restantes son puestos a cero. 

Ejemplo:
bitset<125> bs2(64312UL);
template<class charT, class traits, class Allocator> explicit bitset( const basic_string<charT,traits,Allocator>& str, typename basic_string<charT,traits,Allocator>::size_type pos = 0, typename basic_string<charT,traits,Allocator>::size_type n = basic_string<charT,traits,Allocator>::npos); 

C-3: Constructor explícit que acepta un string str como argumento principal y otros dos argumentos numéricos adicionales pos y n, que tienen valores por defecto. El primero recibe el valor 0; el segundo el valor npos, que corresponde con el valor strlen(str)-pos. Estos dos últimos argumentos permiten especificar si se utilizarán todos los miembros del string str o npos caracteres desde la posición pos hasta el final.

Los elementos de la cadena deben ser solo 0 o 1. El tamaño del bitset debe ser suficiente para albergar la cadena utilizada como argumento. En caso que sea mayor, los bits restantes se ponen a cero. 

Ejemplo
bitset<16> bs1("10010110101");bitset<16> bs2("10a10110101"); // Error! (se lanza excepción)bitset<16> bs3("10010110101", 3);bitset<16> bs4("10010110101", 3, 4);          Resultados:
000001001011 0101
0000000010110101
0000000000001011

• OPERADORES

bool operator==(const bitset<N>& rhs) const; 

Operador de igualdad; devuelve un bool. Cierto si todos los bits de ambos operandos coinciden. Falso en caso contrario. Solo está definido entre contenedores de igual tamaño. 

Ejemplo:
if (bs1 == bs2) { /* ... */ }
booloperator!=(const bitset<N>& rhs) const;} 

Operador relacional inverso al anterior. Permite expresiones como:
if (bs1 != bs2) { /* ... */ }


bitset<N>& operator&=(const bitset<N>& rhs); 

La expresión bs1 &= bs2; es en realidad una operación compuesta and_eq de un bitand seguido de una asignación: 

bs1 = (bs1 & bs2); 

El resultado es que todos los bits del Lvalue cuyos correspondientes en el Rvalue son 0, son puestos a cero. El resto permanece inalterado. 

bitset<N>& operator|=(const bitset<N>& rhs);

 Este operador binario se corresponde con una operación or_eq . Un bitor seguido de una asignación, de forma que las dos expresiones son equivalentes:
bs1 |= bs2;bs1 = (bs1 | bs2);El resultado es que todos los bits del Lvalue cuyos correspondientes en el Rvalue son 1 son puestos a uno. El resto permanece sin cambio.
bitset<N>& operator^=(const bitset<N>& rhs);
Corresponde a una operación xor_eq ;un OR exclusivo (xor) seguido de una asignación. Las dos expresiones que siguen son equivalentes:
bs1 ^= bs2;bs1 = (bs1 ^ bs2);El resultado es que son cambiados todos los bits del Lvalue cuyos correspondientes en el Revalueso son 1. El resto permanece sin cambio
bitset<N>& operator<<=(size_t pos);
Esta es una operación compuesta, corresponde a una operación de desplazamiento de bits seguido de una asignación:
bs1 <<= bs2;bs1 = (bs1 << bs2);
El resultado es que se sustituye cada bit de posición i el Lvalue por otro valor según el siguiente criterio:
Si: i < pos, se sustituye por un 0.
Si: i >= pos, se sustituye por el valor del bit en la posición i - pos.
bitset<N>& operator>>=(size_t pos);
Este operador binario define una operación compuesta correspondiente a un desplazamiento de bits seguido de una asignación:
bs1 >>= bs2;bs1 = (bs1 >> bs2);
El resultado es que se sustituye cada bit de posición i el Lvalue es sustituido por otro valor según el siguiente criterio:
Si: pos >= N - i, se sustituye por un 0.
Si: pos < N - i, se sustituye por el valor del bit en la posición i + pos.
bitset<N> operator<<(size_t pos) const;
Devuelve:
bitset<N>(*this) <<= pos
bitset<N> operator>>(size_t pos) const;Devuelve:
bitset<N>(*this) >>= pos.
Ejemplo:
bitset<32> bs2(64312UL); cout << "Imagen: " << bs2 << endl; cout << "Imagen: " << (bs2>>1) << endl; cout << "Imagen: " << (bs2<<1) << endl; Salida:
Imagen: 00000000000000001111101100111000Imagen: 00000000000000000111110110011100Imagen: 00000000000000011111011001110000
bitset<N> operator~() const;

Es el operador unario de complemento a uno. Construye un nuevo objeto x bitset <N> y lo inicializa con el valor del operando. A continuación cambia los valores de todos los bits, de forma que el objeto devuelto es el complemento a uno del argumento
Ejemplo:
bitset<32> bs2(64312UL);cout << "Imagen: " << bs2 << endl; cout << "Imagen: " << ~bs2 << endl;Salida:
Imagen: 00000000000000001111101100111000Imagen: 11111111111111110000010011000111

bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs);
Operador binario que obtiene el AND lógico de lhs y rhs. Devuelve el valor:
bitset<N>(lhs) &= rhs.

bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs);Operador binario que obtiene el OR lógico de lhs y rhs. Devuelve el valor
bitset<N>(lhs) |= rhs
bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs);

Obtiene el XOR lógico de lhs y rhs. Devuelve el valor
bitset<N>(lhs) ^= rhstemplate <class charT, class traits, size_t N> basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, bitset<N>& x);