避免使用vector

避免使用vector<bool>
 
做为一个STL容器，vector<bool>有两个问题．第一，它不是一个真正STL容器，第二，它并不保存bool类型．
除此以外，并没有太多东西与本节题目有关（译注，还不够多吗）

一个东西不能成为一个STL容器,只因为会有人说它是一个(译注,:( ).一个东西要成为STL容器,必须满足所有
列于C++标准23.1节的容器要求.在这些要求中,有这样一条:如果C是一个T类型元素容器,并且C支持operator[]
那么以下代码必须能够编译:

T *p = &c[0]; // initialize a T* with the address
       // of whatever operator[] returns

换句话说,如果你使用operator[]来得到Container中的一个T对象,你可以对它取地址从而得到一个指针.
(假设T没有重载opeartor&.译注:原句为This assumes that T hasn't perversely overloaded operators.
从意译)因此,如果vector<bool>可能成为容器,那么,这些代码必须编译通过:

vector<bool> v;
bool *pb = &v[0]; // initialize a bool* with the address of
                  // what vector<bool>::operator[] returns

但是它不能编译.不能的原因是vector<bool>是一个伪容器(pseudo-container),它并不保存真正的bool,而是
打包bool以节省空间.在一个典型的实现中,每一个"bool"保存在"vector"中都是一个"bit",8-bit的一个字节
将保存8个bool.从内部来看,vector<bool>使用了与位域(bitfields)相同的思想来表示需要保存的bool值.

与bool值相似,位域也只有两个值,但有它俩之间有一个重要的不同:可以创建指向真正的bool型的指针,但指
向单独一位的指针却非法.

考虑到指向单独一位的指针非法,这为vector<bool>的设计摆出了难题.因为vector::operator[]的返回值
是T&类型.如果vector<bool>保存真正的bool值,这不成问题.但是因为它没有,vector<bool>::operator[]
(译注:原文为()疑误)不知如何返回一位的引用,并不存在这样的东西.

为了解决它,vector::operator[]返回一个对象,其行为类似于位的引用,也称为代理对象.(仅使用STL,
你并不需要明白什么是代理.它是一项值得了解的C++技术.关于代理的信息,参考More Effective C++的Item30
还有Gamma等人(就是GoF)的设计模式一书中Proxy章节).深入本质来看,vector<bool>可能类似于这样:

 template <typename Allocator>
 vector<bool, Allocator> {
 public:
 class reference {...}; // class to generate proxies for
    // references to individual bits
 reference operator[](size_type n); // operator[] returns a proxy
 …
 }

现在,这些代码不能编译的原因就很明显了.

vector<bool> v;
bool *pb = &v[0]; // error! the expression on tne right is
    // of type vector<bool>::reference*,
    // not bool*

因为它不能编译,所以vector不满足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(参见Item 16),但是vector<bool>也不能作这一点
因为没用可移植的方法取得vector<bool>中的数据.(Item16中的技术不能在vector上编译.因为这种技术依赖于
能够取得容器元素的指针.我提到过vector<bool>中不保存bool值吧?)

第二个vector<bool>的代替物是bitset.bitset不是一个STL容器,但它是C++标准库的一部分.与STL容器不同,它的大小
(元素总数)在编译期固定.因此,它不支持插入和删除元素,近一步,因为它不是一个STL容器,它也不支持iterator.
与vector<bool>类似,它使用一个压缩的表示法,使得每个值只占用一位.它提供vector<bool>的特殊成员函数,还包含
一系列操作位集(collection of bits)的特殊成员函数.如果不在乎没有迭代器和动态大小,那么bitset也许正合你意.

现在我们来讨论那个贵族的失败的实验,正是它将非STL容器的vector<bool>留在了标准库中.我早先提到代码对象在C++
程序设计中十分有用.C++标准委员会的成员当然也意识到了,他们决定开发vector<bool>做为一个演示.它说明STL如何
支持包含通过代理访问元素的容器.一但这个例子出现在标准中,而且它说明得很详细,开发者将有一个参考,来实现自己
的基于代理的容器.

可是,最终他们发现,不可能创建一种基于代理的容器,它满足所有STL容器的需要.因为某种原因,他们失败了,而开发中
的这个例子留在了标准中.也许有人将探寻vector<bool>存在的原因,但现实地说,这不影响什么.重要的是:vector<bool>
不满足STL容器的需要;你最好不要使用它;deque<bool>和bitset是基本能满足你的需要vector<bool>代替品.