std::vector< bool >因为底层不是直接存储了1字节的bool,而是存储了bit位,通常导致使用方式不当会产生奇奇怪怪的问题,所以总结一下。
std::vector< bool >的源码分析
std::vector<bool>,是类 sd::vector<T,std::allocator<T>> 的部分特化,为了节省内存,内部实际上是按bit来表征bool类型。从底层实现来看,std::vector<bool> 可视为动态的std::bitset,只是接口符合 std::vector,换个名字表达为 DynamicBitset 更为合理。
_Bit_type:std::vecotr<bool>实际存储的底层数据类型的bit大小
在C++标准中,并没有单独的bit类型。
GNU-STL使用一个typedef,将 unsigned long 定义为 _Bit_type,这样一个_Bit_type 就有64bit,也就可以存储64个bool类型变量。
typedef unsigned long _Bit_type; // _Bit_typeenum{_S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type))// 一个 _Bit_type 类型能存储 _S_word_bit 个bit// 注意:在X86-64位CPU上,unsigned long 类型在 MSVC中4个字节(不太符合常规),在GCC中8个字节。};
因此,当 std::vector<bool>要存储__n个bool类型时,底层实际上只需要__n个bit。
那__n个bit对应多少个_Bit_type呢?
static成员函数_S_nword:求需要多少个_Bit_type
在 std::_Bvector_base 类中有个static成员函数 _S_nword ,其返回值就是 __n 个bit所需的 _Bit_type个数。
// std::_Bvector_base 后文分析template <typename _Alloc>size_t _Bvector_base::_S_nword(size_t __n){ return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
std::_Bit_reference:实现bool与_Bit_type的映射
怎么将一个bool类型变量映射到_Bit_type中每一个bit,这由类 std::_Bit_reference 实现的。
类 std::_Bit_reference 是 std::vector<bool> 中的基本存储单位。 比如,std::vector<bool>的 operator[]函数返回值类型就是std::_Bit_reference,而不是 bool 类型 。
typedef _Bit_reference reference;reference operator[]( size_type pos );
const_reference operator[]( size_type pos ) const;
使用auto对std::vector<bool>进行推导,获得的是std::_Bit_reference 类型,而不是bool类型。
为了让 operator[] 的返回值能和bool类型变量表现得一致,std::_Bit_reference 就必须满足两点:
- std::_Bit_reference能隐式转换为bool类型
- 能接受bool类型赋值
在类 std::_Bit_reference 内部有两个字段:
_M_p:_Bit_type*类型,指向的 _Bit_type 类型数据内存
_M_mask:_Bit_type类型,用于指示_M_p的每一位是0还是1,即false 还是 true
通过这两个字段,将一个bool类型变量映射到_M_p上的某个bit。
struct _Bit_reference{_Bit_type* _M_p;_Bit_type _M_mask;_Bit_reference(_Bit_type *__x, _Bit_type __y): _M_p(__x), _M_mask(__y) {}_Bit_reference() noexcept : _M_p(0), _M_mask(0) {}_Bit_reference(const _Bit_reference &) = default;// 隐式转成 bool// bool state = vb[1]; 触发的就是此函数operator bool() const noexcept{ return !!(*_M_p & _M_mask); }// 将 _M_p 的 _M_mask 位,设置为 _x 状态// vb[1] = true; 触发的就是此函数_Bit_reference& operator=(bool __x) noexcept{if (__x)*_M_p |= _M_mask; // 1else*_M_p &= ~_M_mask;return *this;}// 这个函数实际上调用了:// 1. 先调用了 operator bool() const noexcept// 2. 在调用了 _Bit_reference& operator=(bool __x) noexcept_Bit_reference& operator=(const _Bit_reference &__x) noexcept{ return *this = bool(__x); }bool operator==(const _Bit_reference &__x) const{ return bool(*this) == bool(__x); }bool operator<(const _Bit_reference &__x) const{ return !bool(*this) && bool(__x); }void flip() noexcept{ *_M_p ^= _M_mask; }};
剩余源码分析见原文。
内存分配总结
std::vector<bool> 的全称是 std::vector<bool, std::allocator<bool>>,最初传入的分配器是std::allocator<bool>,是为bool类型变量分配内存的。
但由STL对bool类型做了特化,内部并不是存储bool类型,而是_Bit_type类型,因此 std::allocator 现在需要为_Bit_type类型分配内存,这就需要通过 rebind 函数来获得 std::allocator<_Bit_type> 。
源码分析总结
获得 _Bit_reference 对象
首先根据__n 定位到具体的第几个_Bit_type对象及其具体的某位,最终返回的是 _Bit_reference类型:
*iterator(this->_M_impl._M_start._M_p + __n / int(_S_word_bit),__n % int(_S_word_bit));
注意,返回的_Bit_reference 是由如下函数得到的:
reference std::_Bit_iterator::operator*() const{ return reference(_M_p, 1UL << _M_offset); }
也就是说,返回的_Bit_reference对象的_M_mask字段中, 仅需要改变值的那位是1,其他位置都是0。
给_Bit_reference对象赋值
_Bit_reference& _Bit_reference::operator=(bool __x) noexcept
{if (__x)*_M_p |= _M_mask; else*_M_p &= ~_M_mask;return *this;
}
此时调用的是_Bit_reference 的operator=函数,仅改变需要改变的那位,对其他bit不会改变。