http://blog.163.com/zhoumhan_0351/blog/static/3995422720103892031806/

bit_vector位向量容器

bit_vector容器的每个元素是一个 bit 位值，取 0 或 1，连续分配在以字为单位的字节块中。

如图所示，假设为bit位分配了连续的3个机器字的空间，共6个字节，16×3＝48个 bit。为了对灰色的 bit 位进行读写，Bit_reference 结构体使用了一个标志 bit 位所在字的M_p指针变量，它的类型为unsigned int*，正好作为一个字的指针类型。此外，还使用一个M_mask变量，标记bit位在这个字中的偏移量。对于图所示的情形，M_p指向灰色bit位所在的第2个字，M_mask为0010000000000000，唯一的一个“1”，表示当前读写的bit位的位置。

实现代码可参见SGI的stl_bvector.h文件。
二、应用
类同vector,只是由以前的一个数据类型（如int等）变成bool型对象。如：下面的 insert 函数，在pos位置前插入一个新的bit位元素，元素值由x给出。 
iterator insert(iterator pos, bool x)//x为0或1
利用bit_vector位向量容器，可直观地对整型数据的bit位进行处理。一串bit位数据可直接逐位写入容器，而不需要先将若干bit位转换为整数才可写入某个整型变量。 
从实现源码来看，bit_vector容器与vector基本上具有相同的接口，只是bit_vector的迭代器稍为复杂些，需要通过bit位所在的字和字中的偏移量给出当前bit位的位置。总的来说，bit_vector容器的功能，vector<bool>也可以实现，只是使用vector要用一个字节表示一个bit。明显地，从算法的空间复杂度考虑，vector<boo>不及bit_vector划算。