条款18：避免使用vector<bool>

优质

小牛编辑

140浏览

2023-12-01

条款18：避免使用vector<bool>

做为一个STL容器，vector<bool>确实只有两个问题。第一，它不是一个STL容器。第二，它并不容纳bool。除此以外，就没有什么要反对的了。

一个东西不能成为STL容器只因为会有人会说它是。一个东西要成为STL容器就必须满足所有在C++标准23.1节中列出的容器必要条件。在这些要求中有这样一条：如果c是一个T类型对象的容器，且c支持operator[]，那么以下代码必须能够编译：

T *p = &c[0];			// 无论operator[]返回什么，
				// 都可以用这个地址初始化一个T*

换句话说，如果你使用operator[]来得到Container<T>中的一个T对象，你可以通过取它的地址而获得指向那个对象的指针。（假设T没有倔强地重载一些操作符。）然而如果vector<bool>是一个容器，这段代码必须能够编译：

vector<bool> v;
bool *pb = &v[0];			// 用vector<bool>::operator[]返回的
				// 东西的地址初始化一个bool*

但它不能编译。因为vector<bool>是一个伪容器，并不保存真正的bool，而是打包bool以节省空间。在一个典型的实现中，每个保存在“vector”中的“bool”占用一个单独的比特，而一个8比特的字节将容纳8个“bool”。在内部，vector<bool>使用了与位域（bitfield）等价的思想来表示它假装容纳的bool。

正如bool，位域也只表现为两种可能的值，但真的bool和化装成bool的位域之间有一个重要的不同：你可以创建指向真的bool的指针，但却禁止有指向单个比特的指针。

引用单个比特也是禁止的，这为vector<bool>接口的设计摆出了难题。因为vector<T>::operator[]的返回值应该是T&。如果vector<bool>真正容纳bool，这不成问题，但因为它没有，vector<bool>::operator[]需要返回指向一个比特的引用，而并不存在这样的东西。

为了解决这个难题，vector<boo>::operator[]返回一个对象，其行为类似于比特的引用，也称为代理对象。（如果仅使用STL，你并不需要明白什么是代理对象，但它是一项值得了解的C++技术。关于代理对象的信息，参考《More Effective C++》的条款30，还有Gamma等人的《设计模式》[6]中的“Proxy”章节。）深入本质来看，vector<bool>看起来像这样：

template <typename Allocator>
vector<bool, Allocator> {
public:
	class reference {...};			// 用于产生引用独立比特的代理类
	reference operator[](size_type n);		// operator[]返回一个代理
	...
}

现在，这段代码不能编译的原因就很明显了：

vector<bool> v;
bool *pb = &v[0];			// 错误！右边的表达式是
				// vector<bool>::reference*类型，
				// 不是bool*

因为它不能编译，所以vector<bool>不满足STL容器的必要条件。是的，vector<bool>是在标准中，是的，它几乎满足了所有STL容器的必要条件，但是几乎还不够好。你写的有关STL容器的模板越多，会越深刻地认识到这一点。那天会来的。我保证，当你会写出一个模板，它只在取容器元素的地址时会产生一个指向包含类型的指针时才能工作，到那时，你将突然明白容器和几乎是容器之间的区别。

也许你想知道为什么vector<bool>存在于标准中，而它并不是一个容器。答案是与一个失败的高贵实验有关，但让我们推迟一下那个讨论，我有一个更紧迫的问题。如果vector<bool>应避免，因为它不是一个容器，那当我需要一个vector<bool>时应该用什么？

标准库提供了两个替代品，它们能满足几乎所有需要。第一个是deque<bool>。deque提供了几乎所有vector所提供的（唯一值得注意的是reserve和capacity），而deque<bool>是一个STL容器，它保存真正的bool值。当然，deque内部内存不是连续的。所以不能传递deque<bool>中的数据给一个希望得到bool数组的C API^[1]（参见条款16），但你也不能让vector<bool>做这一点，因为没有可移植的取得vector<bool>中数据的方法。（条款16中用于vector的技术不能在vector<bool>上通过编译，因为它们依赖于能够取得指向容器中包含的元素类型的指针。我提到过vector<bool>中不保存bool值吧？）

第二个vector<bool>的替代品是bitset。bitset不是一个STL容器，但它是C++标准库的一部分。与STL容器不同，它的大小（元素数量）在编译期固定，因此它不支持插入和删除元素。此外，因为它不是一个STL容器，它也不支持iterator。但就像vector<bool>，它使用一个压缩的表示法，使得它包含的每个值只占用一比特。它提供vector<bool>特有的flip成员函数，还有一系列其他操作位集（collection of bits）所特有的成员函数。如果不在乎没有迭代器和动态改变大小，你也许会发现bitset正合你意。

现在我们来讨论那个失败的高贵实验，它遗留下的残渣就是STL非容器的vector<bool>。我前面提到代理对象在C++软件开发中十分有用。C++标准委员会的成员当然也明白，他们决定开发vector<bool>做为说明STL可以支持包含通过代理访问元素的容器的演示。它们的理由很从分，有了这个例子在标准中，开发者将有一个现成的参考来实现自己的基于代理的容器。

唉，他们发现的是不可能创建满足所有STL容器的需要的基于代理的容器。但因为某种原因，他们没有尝试在标准中再开发一个。你可以去推测为什么保留vector<bool>，但现实地说，这没关系。重要的是：vector<bool>不满足STL容器的必要条件，你最好不要使用它；而deque<bool>和bitset是基本能满足你对vector<bool>提供的性能的需要的替代数据结构。

^[1] 这可能是C99 API，因为bool只在这个版本的C语言中才加入。