为什么vector <bool>不是STL容器?
斯科特·迈耶斯(Scott Meyers)的书“ 有效的STL”第18条:改善标准模板库的使用的50个具体方法是为了避免vector <bool>
因为它不是一个STL容器,它并不真正成为bools。
以下代码:
vector <bool> v; bool *pb =&v[0];
不会编译,违反了STL容器的要求。
错误:
cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization
vector<T>::operator []
返回types应该是T&,但为什么它是vector<bool>
的特殊情况?
vector<bool>
真的包含了什么?
该项目进一步说:
deque<bool> v; // is a STL container and it really contains bools
这可以用作vector<bool>
的替代方法吗?
谁能解释一下吗?
为了空间优化的原因,C ++标准(早在C ++ 98中)明确地调用了vector<bool>
作为一个特殊的标准容器,其中每个bool只使用一位空间而不是一个字节作为正常的布尔(实现一种“dynamic的比特级”)。 作为交换这个优化它不提供一个普通标准容器的所有function和接口。
在这种情况下,由于你不能在一个字节中取一个位的地址,所以诸如operator[]
东西不能返回一个bool&
而是返回一个代理对象,允许操纵特定的位。 由于这个代理对象不是一个bool&
,你不能把它的地址分配给一个bool*
就像你在“普通”容器上调用这个操作符的结果一样。 这又意味着bool *pb =&v[0];
是无效的代码。
另一方面deque
没有任何这样的专门化,所以每个布尔需要一个字节,你可以从operator[]
返回值的地址。
最后要注意的是,MS标准库的实现(可以说是)次优的,因为它使用一个很小的块大小作为deques,这意味着使用deque作为替代并不总是正确的答案。
vector<bool>
包含压缩forms的布尔值,只使用一个值作为值(而不是bool []数组如何操作)。 在c ++中不可能返回一个引用,所以有一个特殊的辅助types“位参考”,它为您提供了一些内存中的接口,并允许您使用标准的操作符和强制转换。
问题是vector<bool>
返回一个代理引用对象而不是一个真正的引用,所以C ++ 98风格的代码bool * p = &v[0];
不会编译。 然而,现代的C + + 11与auto p = &v[0];
如果operator&
也返回一个代理指针对象可以编译。 Howard Hinnant写了一篇博客文章,详细介绍了使用这种代理引用和指针时的algorithm改进。
Scott Meyers在“ 更有效的C ++”中有关于代理类的第30项。 对于任何给定typesT
,都可以用很长的一段时间来模拟内buildtypes:一对代理(例如reference_proxy<T>
和iterator_proxy<T>
)可以在reference_proxy<T>::operator&()
和iterator_proxy<T>::operator*()
是彼此相反的。
但是,有时需要将代理对象映射回T*
或T&
。 对于迭代器代理,可以重载operator->()
并访问模板T
的接口,而不必重新实现所有的function。 然而,对于引用代理,你需要重载operator.()
,这在目前的C ++中是不允许的(尽pipeSebastian Redl在BoostCon 2013上提出了这样的提议 )。 你可以在引用代理里做一个像.get()
成员一样的详细的变通办法,或者在引用内部实现所有T
的接口(这就是为vector<bool>::bit_reference
),但是这样会要么丢失内置语法,要么引入用户定义的转换,这些转换对于types转换没有内置的语义(每个参数最多可以有一个用户定义的转换)。
TL; DR :没有vector<bool>
不是一个容器,因为Standard需要一个真正的引用,但是它可以做得几乎像一个容器,至less比C ++ 11(auto)更接近C ++ 98。
这来自http://www.cplusplus.com/reference/vector/vector-bool/
boolvector这是vector的专用版本,用于booltypes的元素并优化空间。
它的行为就像vector的非特化版本,有以下变化:
- 存储不一定是一个布尔值的数组,但是库实现可以优化存储,使得每个值都是
存储在一个位。- 元素不是使用分配器对象构造的,但是它们的值直接设置在内部存储器的适当位上。
- 成员函数翻转和成员交换的新签名。
- 一个特殊的成员types,引用,一个访问容器内部存储器中个别位的类,它具有一个接口
模拟一个bool参考。 相反,成员typesconst_reference是一个普通的布尔。- 容器使用的指针和迭代器types不一定是指针,也不一定是迭代器,虽然它们是
应该模拟大部分的预期行为。这些变化提供了一个古怪的界面,这种专业化和青睐内存优化处理(这可能会或可能不适合您的需要)。 在任何情况下,都不可能直接为bool实例化非特化的向量模板。 避免使用不同types(char,unsigned char)或容器(如deque)来使用包装器types或进一步专用于特定分配器types的解决方法。
bitset是为固定大小的位数组提供类似function的类。
看看它是如何实施的。 STL在模板上大量构build,因此头文件包含了他们所做的代码。
比如看看这里的stdc ++实现。
也很有趣,即使不符合位vector是从这里 llvm :: BitVector 。
llvm::BitVector
的本质是一个称为reference
的嵌套类和适当的运算符重载,使得BitVector
行为类似于具有某些限制的vector
。 下面的代码是一个简化的界面,显示BitVector如何隐藏一个名为reference
的类,使真正的实现几乎像一个真正的数组bool,而不是每个值使用1个字节。
class BitVector { public: class reference { reference &operator=(reference t); reference& operator=(bool t); operator bool() const; }; reference operator[](unsigned Idx); bool operator[](unsigned Idx) const; };
这里的代码有很好的属性:
BitVector b(10, false); // size 10, default false BitVector::reference &x = b[5]; // that's what really happens bool y = b[5]; // implicitly converted to bool assert(b[5] == false); // converted to bool assert(b[6] == b[7]); // bool operator==(const reference &, const reference &); b[5] = true; // assignment on reference assert(b[5] == true); // and actually it does work.
这段代码实际上有一个缺陷,尝试运行:
std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator
assert( (&b[5] - &b[3]) == (5 - 3) );
将失败(在llvm::BitVector
)
这是非常简单的llvm版本。 std::vector<bool>
也有工作迭代器。 因此,调用for(auto i = b.begin(), e = b.end(); i != e; ++i)
将起作用。 还有std::vector<bool>::const_iterator
。
然而,在std::vector<bool>
中仍然有一些限制,使得它在某些情况下performance不同。
许多人认为vector<bool>
专业化是一个错误。
在一篇论文“在C ++ 17中废弃残留库部件”
有一个build议重新考虑vector部分专业化 。
std :: vector的bool部分专业化已经有很长的历史,不能满足容器需求,尤其是它的迭代器不能满足随机访问迭代器的要求。 C ++ 11, N2204拒绝了之前的这个容器的尝试。
拒绝的原因之一是,不清楚模板的特定专业化意味着什么。 这可以用谨慎的措词加以解决。 更大的问题是vector的(包装)专业化提供了标准库的客户真正寻求但不再可用的重要优化。 在build议和接受替代设施(如N2050)之前,我们不太可能贬低这部分标准。 不幸的是,目前还没有向图书馆演进工作组提出这样的修改build议。