18.避免使用vector<bool>

Posted on | In

前言

</br>
vector<bool>只有两个问题：

  1. 它不是一个STL容器
  2. 它没有容纳bool

vector<bool>的特点

STL的一个必要条件

STL容器的一个要求是：如果c是stl容器，且支持operator[],则以下代码可编译：

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

具体来说就是，如果你可以使用operator[]来得到Container<T>中的一个T对象，那你必然可以通过取它的地址而获得指向那个对象的指针。
看起来很正常的要求，但vector<bool>做不到。

vector<bool>的内存分布

vector是一个伪容器，并不保存真正的bool，而是打包bool以节约空间。确切的说，bool在vector内仅仅只占用了一个bit，我们无法创建指向单个bit的指针。

同样的，也不可能存在单个bit引用.为了解决这个问题，vector<bool>使用了proxy class（详见More Effective C++ 30),从本质上来说，vector看起来像这样：

1
2
3
4
5
6
7
template <typename Allocator>
vector<bool, Allocator> {
public:
    class reference {...}; //proxy class
    reference operator[](size_type n); //return a proxy object
    ...
}

这也说明了为什么上面的代码无法编译，因为返回的并不是bool类型，而是一个代理对象。

使用deque<bool>与bitset来替换vector

  1. deque<bool>
    deque提供了几乎所有vector所提供的成员函数（缺是reserve和capacity）。并且，deque<bool>是一个STL容器，它保存真正的bool值。
  2. bitset
    bitset不是一个STL容器，但它是C++标准库的一部分。其内存分布和vector<bool>差不多，其具体实现与应用可参照数据结构·Bitamap篇。