5.1.1e1 bitset
§1 Preámbulo
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
( 4.9.3).
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.
(32 bits en la mayoría de plataformas
2.2.4). 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");
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.
§2 La clase bitset
La descripción de esta familia de tipos responde al prototipo siguiente (su interfaz se muestra en la página adjunta
class bitset):
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);
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.
§3 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 (ver el prototipo de la plantilla
). 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
Los miembros del bitset se consideran numerados
lo mismo que las matrices. Es decir, de 0 a N-1 (ver ejemplo
), 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)
Como veremos a continuación, el estándar no define un constructor-copia
( 4.11.2d4) ni un operador de
asignación para la clase [1], por lo que la utilización de las expresiones:
bitset<N> bs2 = bs1; // usar constructor-copia
bs2 = bs1; // usar operador de asignación
supone usar los métodos proporcionados "de oficio" por el compilador.
§4 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( |
|
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:
0000010010110101 |
|
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 ( 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
( 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
( bs1 ^= bs2; bs1 = (bs1 ^ bs2); El resultado es que son cambiados todos los bits del Lvalue cuyos correspondientes en el Rvalue 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:
|
|
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:
|
|
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); Salida: Imagen: 00000000000000001111101100111000 |
|
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); Salida: Imagen: 00000000000000001111101100111000 |
|
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) ^= rhs |
|
template <class charT, class traits, size_t N> basic_istream<charT, traits>& operator>>(basic_istream<charT, traits>& is, bitset<N>& x); |
|
Este operador permite entradas formateadas. Extrae
N caracteres simples [2]
del flujo de entrada is, y se almacenan en un objeto temporal de tipo string
( x = bitset<N>(str) El resultado es que el bitset utilizado como argumento x contiene N bits equivalentes a los caracteres del flujo de entrada ('0' es transformado en 0 y '1' en 1). Los caracteres son extraídos del flujo hasta que se de alguna de las siguientes circunstancias:
Ejemplo: bitset<16> bs3; Salida después de introducir la secuencia 1001010100110101001110101010101: bs3 contiene: 1001010100110101 |
|
template <class charT, class traits, size_t N> basic_ostream<charT, traits>& operator<<(basic_ostream<charT, traits>& os, const bitset<N>& x); |
|
Devuelve: os << x.template to_string<charT,traits,allocator<charT> >() Ver a continuación la declaración del método to_string(
Ejemplo: bitset<32> bs2(64312UL); |
|
Métodos: |
|
bitset<N>& set(); |
|
Método que pone a 1 todos los elementos del objeto sobre el que opera. Ejemplo: bs1.set(); |
|
bitset<N>& set(size_t pos, int val = 1); |
|
Esta versión sobrecargada del método anterior requiere que el argumento pos sea válido. En caso contrario, si corresponde a un elemento no válido del contenedor, se lanza una excepción. El método fija el valor del elemento pos según el valor señalado por val. (observe que este argumento tiene un valor por defecto). Si val es cero, se almacena un cero (0). En caso contrario se almacena un uno (1). El ejemplo que sigue pone a 1 el quinto elemento del contenedor bs2: bs2.set(5); |
|
bitset<N>& reset(); |
|
Este método hace el efecto contrario que set
( Ejemplo: bs1.reset(); |
|
bitset<N>& reset(size_t pos); |
|
Pone a cero el miembro señalado por el argumento pos, que debe ser una posición válida. Ejemplo: bs2.reset(5); |
|
bitset<N>& flip(); |
|
Este método cambia el valor de todos los miembros del contenedor sobre el que opera (1s por 0s y 0s por 1s). Ejemplo: bs2.flip(); |
|
bitset<N>& flip(size_t pos); |
|
Cambia el valor del miembro de la posición señalada por el
argumento. pos debe ser una
posición válida. En caso contrario se lanza una excepción out_of_range
(§5 Ejemplo: bs2.flip(5); |
|
unsigned long to_ulong() const; |
|
Devuelve un entero sin signo con el valor del patrón de bits almacenado en el contenedor.
Si este valor no puede ser representado por un unsigned long, se lanza una excepción overflow_error
(§5 Ejemplo: bitset<125> bs2(64312UL); |
|
template <class charT, class traits, class Allocator> basic_string<charT, traits, Allocator> to_string() const; |
|
Este método devuelve un string de N caracteres que corresponden con los bits del bitset. Cada carácter del string es '1' o '0' según el valor del bit correspondiente. viene determinado por el valor de la posición de su bit correspondiente. La posición de los caracteres del string
es la imagen especular de los bits del bitset; en el sentido que el
carácter de posición 0 corresponde con el bit de posición N-1, y el
carácter N-1 corresponde con el primer bit (pos 0). En cierta forma, este método realiza la operación inversa del
constructor C-3 Debe advertirse que este método es una función genérica (plantilla) que no acepta argumentos, por lo que su utilización puede requerir una calificación explícita, ya que en determinadas condiciones el compilador no puede deducir los parámetros de plantilla necesarios. Ejemplo: bitset<32> bs2(64312UL); puede ser necesario utilizar la sentencia L1 en la forma [3]: string s2 = bs2.template to_string(); Ejemplo: cout << bs2.to_string; Aquí es necesario utilizar una instanciacion explicita, dado que el compilador es incapaz de deducirla del contexto (en nuestro caso deseamos una cadena de caracteres): cout << bs2.template to_string <char, char_traits<char>, allocator<char> >(); Ejemplo: string s2 = bs2.to_string(); Salida: Imagen: 00000000000000001111101100111000
Una forma más elegante para obtener la misma salida utilizando una instanciación explícita del método: cout << "Imagen: " ; Nota: Observe el espacio entre los dos ángulos finales > > |
|
size_t count() const; |
|
Devuelve el número de elementos del objeto. Ejemplo: bitset<16> bs3; Salida: bs3 Contiene 0 elementos |
|
size_t size() const; |
|
Devuelve el tamaño del contenedor. Ejemplo: bitset<16> bs3; Salida: bs3 puede contener 16 elementos máximo |
|
bool test(size_t pos) const; |
|
Este método devuelve un booleano cierto/falso según el valor del bit de posición
pos
sea 1 o 0 respectivamente. El valor pos debe ser válido (estar dentro del rango aceptable para el bitset).
En caso contrario se lanza una excepción out_of_range
(§5 Ejemplo: bitset<8> bs4(string("00000011")); Salida: Valor de bs4: 3 |
|
bool any() const; |
|
Este método devuelve un bool true si algún elemento del contenedor es 1. Falso en caso contrario. Ejemplo: bitset<8> bs4(string("00000011")); Salida: Contiene algún 1?: Cierto!! |
|
bool none() const; |
|
Similar al anterior. Devuelve un bool cierto si no contiene ningún 1. Falso en caso de contener alguno. Ejemplo: bitset<8> bs4(string("00000011")); Salida: Contiene algún 1?: Falso!! |
§5 Errores
Las funciones relacionadas con esta clase pueden generar tres tipos de excepciones estándar como consecuencia de situaciones erróneas, lo que significa que nuestra aplicación debería estar preparada para capturarlas en caso de producirse. Son las siguientes:
- invalid_argument
(
1.6.1a). Como consecuencia de un error por uso de argumentos no válidos.
- out_of_range
(
1.6.1a). Error por valores fuera de rango.
- overflow_error
(
1.6.1a). Errores de desbordamiento.
[1] Algunos compiladores puede que ofrezcan este constructor, aunque no está contemplado en el Estándar. Por ejemplo, Borland C++ 5.5 y MS Visual C++ si ofrecen un constructor-copia que responde al prototipo
bitset(const bitset<N>& bs);
[2] Los caracteres son considerados tipo char de 8 bits (no wchar_t anchos
2.2.1a1).
[3] Los detalles dependen del compilador y del grado de su "inteligencia" para manejar las plantillas.