vector<bool>不是存储bool类型元素的vector容器!

前面章节中,已经详细介绍了 vector<T> 容器的功能和用法。特别需要提醒的是,在使用 vector 容器时,要尽量避免使用该容器存储 bool 类型的元素,即避免使用 vector<bool>。

具体来讲,不推荐使用 vector<bool> 的原因有以下 2 个:
  1. 严格意义上讲,vector<bool> 并不是一个 STL 容器;
  2. vector<bool> 底层存储的并不是 bool 类型值。

读者可能会感到有些困惑,别着急,继续往下读。

vector<bool>不是容器

值得一提的是,对于是否为 STL 容器,C++ 标准库中有明确的判断条件,其中一个条件是:如果 cont 是包含对象 T 的 STL 容器,且该容器中重载了 [ ] 运算符(即支持 operator[]),则以下代码必须能够被编译:
T *p = &cont[0];
此行代码的含义是,借助 operator[ ] 获取一个 cont<T> 容器中存储的 T 对象,同时将这个对象的地址赋予给一个 T 类型的指针。

这就意味着,如果 vector<bool> 是一个 STL 容器,则下面这段代码是可以通过编译的:
//创建一个 vector<bool> 容器
vector<bool>cont{0,1};
//试图将指针 p 指向 cont 容器中第一个元素
bool *p = &cont[0];
但不幸的是,此段代码不能通过编译。原因在于 vector<bool> 底层采用了独特的存储机制。

实际上,为了节省空间,vector<bool> 底层在存储各个 bool 类型值时,每个 bool 值都只使用一个比特位(二进制位)来存储。也就是说在 vector<bool> 底层,一个字节可以存储 8 个 bool 类型值。在这种存储机制的影响下,operator[ ] 势必就需要返回一个指向单个比特位的引用,但显然这样的引用是不存在的。

C++ 标准中解决这个问题的方案是,令 operator[] 返回一个代理对象(proxy object)。有关代理对象,由于不是本节重点,这里不再做描述,有兴趣的读者可自行查阅相关资料。

同样对于指针来说,其指向的最小单位是字节,无法另其指向单个比特位。综上所述可以得出一个结论,即上面第 2 行代码中,用 = 赋值号连接 bool *p 和 &cont[0] 是矛盾的。

由于 vector<bool> 并不完全满足 C++ 标准中对容器的要求,所以严格意义上来说它并不是一个 STL 容器。可能有读者会问,既然 vector<bool> 不完全是一个容器,为什么还会出现在 C++ 标准中呢?

这和一个雄心勃勃的试验有关,还要从前面提到的代理对象开始说起。由于代理对象在 C++ 软件开发中很受欢迎,引起了 C++ 标准委员会的注意,他们决定以开发 vector<bool> 作为一个样例,来演示 STL 中的容器如何通过代理对象来存取元素,这样当用户想自己实现一个基于代理对象的容器时,就会有一个现成的参考模板。

然而开发人员在实现 vector<bool> 的过程中发现,既要创建一个基于代理对象的容器,同时还要求该容器满足 C++ 标准中对容器的所有要求,是不可能的。由于种种原因,这个试验最终失败了,但是他们所做过的尝试(即开发失败的 vector<bool>)遗留在了 C++ 标准中。

至于将 vector<bool> 遗留到 C++ 标准中,是无心之作,还是有意为之,这都无关紧要,重要的是让读者明白,vector<bool> 不完全满足 C++ 标准中对容器的要求,尽量避免在实际场景中使用它!

如何避免使用vector<bool>

那么,如果在实际场景中需要使用 vector<bool> 这样的存储结构,该怎么办呢?很简单,可以选择使用 deque<bool> 或者 bitset 来替代 vector<bool>。

要知道,deque 容器几乎具有 vecotr 容器全部的功能(拥有的成员方法也仅差 reserve() 和 capacity()),而且更重要的是,deque 容器可以正常存储 bool 类型元素。

有关 deque 容器的具体用法,后续章节会做详细讲解。

还可以考虑用 bitset 代替 vector<bool>,其本质是一个模板类,可以看做是一种类似数组的存储结构。和后者一样,bitset 只能用来存储 bool 类型值,且底层存储机制也采用的是用一个比特位来存储一个 bool 值。

和 vector 容器不同的是,bitset 的大小在一开始就确定了,因此不支持插入和删除元素;另外 bitset 不是容器,所以不支持使用迭代器。

有关 bitset 的用法,感兴趣的读者可查阅 C++ 官方提供的 bitset使用手册