> 导读：天天刷题，怎么能不知道 std::vector<bool> 设计呢。
但凡上网搜索下关于 std::vector<bool> 的讨论，基本都是吐槽它的实现，分不清这么设计是feature还是bug。此外，由于 std::vector<bool> 也经常应用在牛客网刷题中。因此，本期就来聊下 它的底层实现，来帮助你正确的使用它。
前言
std::vector<bool>，是类 sd::vector<t,std::allocator<t>> 的部分特化，为了节省内存，内部实际上是按bit来表征bool类型。从底层实现来看，std::vector<bool> 可视为动态的std::bitset，只是接口符合 std::vector，换个名字表达为 DynamicBitset 更为合理，也许就没那么多吐槽了。
下面，就从源码角度一点点解开困惑。
_Bit_type
先来看看是怎么存储bit的。
在C++标准中，并没有单独的bit类型。GNU-STL使用一个typedef，将 unsigned long 定义为 _Bit_type，如此，一个_Bit_type 就有64bit，也就可以存储64个bool类型变量。
> 注意：在X86-64位CPU上，unsigned long 类型在 MSVC中4个字节，在GCC中8个字节。
typedef unsigned long _Bit_type; // _Bit_type
enum
{
_S_word_bit = int(__CHAR_BIT__ * sizeof(_Bit_type)) // 一个 _Bit_type 类型能存储 _S_word_bit 个bit
}; 因此，当 std::vector<bool>要存储__n个bool类型时，底层实际上只需要__n个bit。
那__n个bit对应多少个_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); } by the way
顺带考虑个问题，下面的demo中，vb 调用多少次push_back函数才会发生扩容？
std::vector<bool> vb(10);
由于 std::vector<bool> 底层是将 _Bit_type 中的bit映射成 bool类型的，也就是说分配一个_Bit_type对象，最终就能存储64个bool类型，因此上面的demo中，vb调用 push_back函数64次后才会发生扩容，而不是10次。
std::_Bit_reference
讲完了_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;
因此，为了让 operator[] 的返回值能和bool类型变量表现得一致，std::_Bit_reference 就必须满足两点：
std::_Bit_reference能隐式转换为bool类型- 能接受bool类型赋值
简而言之，就是下面的demo能编译过：
std::vector<bool> vb(3); bool state = vb[1]; // 1: OK vb[1] = true; // 2: OK
在类 std::_Bit_reference 内部有两个字段：
_M_p：_Bit_type*类型，指向的_Bit_tpe类型数据内存_M_mask：_Bit_type类型，用于指示_M_p的每一位是0还是1，即false 还是 true
通过这两个字段，将一个bool类型变量映射到_M_p上的某个bit。
类 std::_Bit_reference 的实现及注释如下。
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;
///@brief 隐式转成 bool
/// bool state = vb[1]; 触发的就是此函数
operator bool() const noexcept
{ return !!(*_M_p & _M_mask); }
///@brief 将 _M_p 的 _M_mask 位，设置为 _x 状态
/// vb[1] = true; 触发的就是此函数
_Bit_reference& operator=(bool __x) noexcept
{
if (__x)
*_M_p |= _M_mask; // 1
else
*_M_p &= ~_M_mask;
return *this;
}
// @brief 这个函数实际上调用了：
// 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::_Bit_iterator_base
自然，std::vector<t> 中的迭代器也不能用于 std::_Bit_reference，需要重新实现。
std::vector<bool> 中对每个bit的移动操作是基于 类 std::_Bit_iterator类实现的，它的基类是std::_Bit_iterator_base。
struct _Bit_iterator : public _Bit_iterator_base { /***/ }; 类 std::_Bit_iterator_base ，继承了迭代器类 std::iterator，而std::iterator是个空类，其中定义了一些 typedef：
struct _Bit_iterator_base : public std::iterator<std::random_access_iterator_tag, bool> ;
template<typename _category, typename _tp, _distance="ptrdiff_t," _pointer="_Tp*," _reference="_Tp&">
struct iterator
{
typedef _Category iterator_category;
typedef _Tp value_type;
typedef _Distance difference_type;
typedef _Pointer pointer;
typedef _Reference reference;
}; 因此，继承的基类 std::iterator<std::random_access_iterator_tag, bool>，实例化后如下：
struct std::iterator<std::random_access_iterator_tag, bool>
{
typedef std::random_access_iterator_tag iterator_category;
typedef bool value_type;
typedef ptrdiff_t difference_type;
typedef bool* pointer;
typedef bool& reference;
}; 说完迭代器基类，下面来看看 std::_Bit_iterator_base 的实现。
类 std::_Bit_iterator_base中，有两个字段：
_M_p：指向数据体实体，和std::_Bit_reference中的_M_p相同；_M_offset：指示当前正遍历到_M_p中第_M_offset个bit（从0开始计数）。这和std::_Bit_reference中的_M_mask字段含义不同，_M_mask是指示_M_offset处的bit是0还是1。
还有三个比较重要的成员函数：
_M_bump_up：前进一位，是后面实现++operator重载的基础；_M_bump_down：后退一位，是后面实现--operator重载的基础；_M_incr：实现operator+=、operator-=重载。
类 std::_Bit_iterator_base的完整实现及注释如下。
struct _Bit_iterator_base : public std::iterator<std::random_access_iterator_tag, bool>
{
_Bit_type* _M_p;
unsigned int _M_offset;
_Bit_iterator_base(_Bit_type *__x, unsigned int __y)
: _M_p(__x), _M_offset(__y) {}
/// @brief 前进一个bit，如果当前_M_p遍历完，则到下一个 _Bit_type* 对象
void _M_bump_up()
{
if (_M_offset++ == int(_S_word_bit) - 1)
{
_M_offset = 0;
++_M_p;
}
}
/// @brief 后退一个bit，如果到达 _M_p 的首地址，则进入到前一个 _Bit_type* 对象
void _M_bump_down()
{
if (_M_offset-- == 0)
{
_M_offset = int(_S_word_bit) - 1;
--_M_p;
}
}
/// @brief 前进 __i 个bit
void _M_incr(ptrdiff_t __i)
{
difference_type __n = __i + _M_offset;
_M_p += __n / int(_S_word_bit);
__n = __n % int(_S_word_bit);
if (__n < 0)
{
__n += int(_S_word_bit);
--_M_p;
}
_M_offset = static_cast<unsigned int>(__n);
}
/** 下面是关于迭代器的比较运算重载 **/
bool operator==(const _Bit_iterator_base &__i) const
{ return _M_p == __i._M_p && _M_offset == __i._M_offset; }
bool operator<(const _Bit_iterator_base &__i) const
{ return _M_p < __i._M_p || (_M_p == __i._M_p && _M_offset < __i._M_offset); }
bool operator!=(const _Bit_iterator_base &__i) const
{ return !(*this == __i); }
bool operator>(const _Bit_iterator_base &__i) const
{ return __i < *this; }
bool operator<=(const _Bit_iterator_base &__i) const
{ return !(__i < *this); }
bool operator>=(const _Bit_iterator_base &__i) const
{ return !(*this < __i); }
}; std::_Bit_iterator
类std::Bit_iterator 就是其基类std::_Bit_iterator_base 的wrapper，重载 -- 和 ++ 操作以及解引用等运算操作。
struct _Bit_iterator : public _Bit_iterator_base
{
typedef _Bit_reference reference;
typedef _Bit_reference* pointer;
typedef _Bit_iterator iterator;
_Bit_iterator() : _Bit_iterator_base(0, 0) {}
_Bit_iterator(_Bit_type* __x, unsigned int __y) : _Bit_iterator_base(__x, __y) {}
iterator _M_const_cast() const
{ return *this; }
/// @brief 解引用运算符，返回的也是 std::_Bit_reference 类型
reference operator*() const
{ return reference(_M_p, 1UL << _M_offset); }
/// @brief 索引
reference operator[](difference_type __i) const
{ return *(*this + __i); }
/** 下面是运算符重载 **/
/// @brief 每次前进一个bit
iterator& operator++()
{
_M_bump_up();
return *this;
}
/// @brief 每次后退一个bit
iterator& operator--()
{
_M_bump_down();
return *this;
}
iterator& operator+=(difference_type __i)
{
_M_incr(__i);
return *this;
}
iterator& operator-=(difference_type __i)
{
*this += -__i;
return *this;
}
//...
}; std::_Bvector_base
介绍完上面的迭代器部分，下面就进入std::vector<bool>实现相关，其基类是std::_Bvector_base。
在类std::_Bvector_base 中还有两个内嵌类：
std::_Bvector_impl_data：用于记录当前std::vector<bool>底层内存使用情况、元素个数等。std::_Bvector_impl：实现std::vector<bool>的核心。
下面，从这个两个类开始讲述。
std::_Bvector_impl_data
类 std::_Bvector_impl_data 记录了 std::_Bvector_base 的数据存储，里面有三个字段：
_M_start：指向内存的首地址，即begin()函数的返回值；_M_finish：下一个元素要插入的位置，即end()函数的返回值；_M_end_of_stroage：整个可用内存区间是[_M_start, _M_end_of_storage)，_M_end_of_stroage指向的就是这块内存的最后一个可使用字节的后一个位置。
std::_Bvector_impl_data 的实现及注释如下。
struct _Bvector_impl_data
{
_Bit_iterator _M_start; // 迭代器
_Bit_iterator _M_finish; // 迭代器
_Bit_pointer _M_end_of_storage; // 指针
_Bvector_impl_data() noexcept
: _M_start(),
_M_finish(),
_M_end_of_storage()
{ }
/// @brief 移动构造函数
_Bvector_impl_data(_Bvector_impl_data&& __x) noexcept
: _M_start(__x._M_start),
_M_finish(__x._M_finish),
_M_end_of_storage(__x._M_end_of_storage)
{ __x._M_reset(); }
void _M_move_data(_Bvector_impl_data &&__x) noexcept
{
this->_M_start = __x._M_start;
this->_M_finish = __x._M_finish;
this->_M_end_of_storage = __x._M_end_of_storage;
__x._M_reset();
}
void _M_reset() _GLIBCXX_NOEXCEPT
{
_M_start = _M_finish = _Bit_iterator();
_M_end_of_storage = _Bit_pointer();
}
}; std::_Bvector_impl
类std::_Bvector_impl_data 只具有记录内存使用情况的三个字段，那谁来分配内存？
类std::_Bvector_impl 继承了两个类：
_Bit_alloc_type：负责分配内存std::_Bvector_impl_data：负记记录内存的使用情况
如此，才使 std::_Bvector_impl 成为实现std::vector<bool>的核心：
_Bit_alloc_type
类
_Bit_alloc_type，实际上是类std::_Bvector_base中的一个typedef：typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Bit_type>::other _Bit_alloc_type;
因此，
_Bit_alloc_type实际上就是std::allocator<_Bit_type>。如果不了解 类
__gnu_cxx::__alloc_traits、rebind函数，可以看看我之前写的一期 提高C++程序员的自我修养 from 剖析STL内存分配器，在里面详细分析过。by the way
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>。std::_Bvector_impl_data
_Bit_alloc_type负责获得_Bit_type类型的内存分配器std::allocator<_Bit_type>，而所得的内存就是由_Bvector_impl_data中的字段来记录。
因此，std::_Bvector_impl 继承了上面两个类后，就完整了。
类std::_Bvector_impl的完整实现及注释如下。
struct _Bvector_impl: public _Bit_alloc_type, _Bvector_impl_data
{
public:
_Bvector_impl() noexcept(is_nothrow_default_constructible<_Bit_alloc_type>::value)
: _Bit_alloc_type() { }
_Bvector_impl(const _Bit_alloc_type &__a) noexcept
: _Bit_alloc_type(__a) { }
///@brief 默认的移动构造函数就满足了，因为
/// 1. _Bit_alloc_type 是个空基类
/// 2. _Bvector_impl_data 已经实现了移动构造函数
_Bvector_impl(_Bvector_impl&&) = default;
/// @brief 获得 _M_end_of_storage 指向的地址
_Bit_type* _M_end_addr() const noexcept {
if (this->_M_end_of_storage)
return std::__addressof(this->_M_end_of_storage[-1]) + 1;
return 0;
}
}; 说完两个内嵌类，下面来看看 std::_Bvector_base本身。
它只有一个字段：
_Bvector_impl _M_impl;
而整个类 std::_Bvector_base ，主要是针对_M_impl 的内存操作，并无数据操作:
_M_allocate函数：分配内存_M_deallocate函数：释放使用_M_allocate函数分配的内存- 其他一些辅助函数
完整的代码，见代码注释。
template <typename _alloc>
struct _Bvector_base
{
typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Bit_type>::other _Bit_alloc_type;
typedef typename __gnu_cxx::__alloc_traits<_Bit_alloc_type> _Bit_alloc_traits;
typedef typename _Bit_alloc_traits::pointer _Bit_pointer;
struct _Bvector_impl_data { /** ... **/ };
struct _Bvector_impl { /** ... **/ };
public:
typedef _Alloc allocator_type; // std::allocator<bool>
_Bvector_base() = default;
_Bvector_base(const allocator_type& __a) : _M_impl(__a) { }
_Bvector_base(_Bvector_base &&) = default;
~_Bvector_base()
{ this->_M_deallocate(); }
/// @brief 获取内存分配器，实质就是子类对象转换为父类
_Bit_alloc_type& _M_get_Bit_allocator() noexcept
{ return this->_M_impl; }
/// @brief 由 std::allocator<_Bit_type> 构造 std::allocator<bool>
allocator_type get_allocator() const noexcept
{ return allocator_type(_M_get_Bit_allocator()); }
protected:
_Bvector_impl _M_impl; //!!! 唯一字段
/// @brief 分配 _s_nword(__n) 个字节的内存
_Bit_pointer _M_allocate(size_t __n)
{ return _Bit_alloc_traits::allocate(_M_impl, _S_nword(__n)); }
/// @brief 析构内存
void _M_deallocate() {
if (_M_impl._M_start._M_p) {
const size_t __n = _M_impl._M_end_addr() - _M_impl._M_start._M_p;
_Bit_alloc_traits::deallocate(_M_impl,
_M_impl._M_end_of_storage - __n,
__n);
_M_impl._M_reset();
}
}
void _M_move_data(_Bvector_base &&__x) noexcept
{ _M_impl._M_move_data(std::move(__x._M_impl)); }
static size_t _S_nword(size_t __n)
{ return (__n + int(_S_word_bit) - 1) / int(_S_word_bit); }
};
std::vector<bool, _alloc>
好嘞，终于讲解到 std::vector<bool>了，它就是个部分特化的类：
// 原型
template<typename _tp, typename _alloc="std::allocator<_Tp"> >
class vector : protected _Vector_base<_Tp, _Alloc> {
//...
};
// 第一个参数特化为bool
template <typename _alloc>
class vector<bool, _alloc> : protected _Bvector_base<_Alloc> {
typedef _Bvector_base<_Alloc> _Base;
//...
public:
typedef _Alloc allocator_type; // std::allocator<bool>
//...
protected:
using _Base::_M_allocate;
using _Base::_M_deallocate;
using _Base::_S_nword;
using _Base::_M_get_Bit_allocator;
explicit vector(size_type __n, const allocator_type &__a = allocator_type())
: vector(__n, false, __a) // 委托构造函数
{ }
vector(size_type __n, const bool &__value, const allocator_type &__a = allocator_type())
: _Base(__a)
{
_M_initialize(__n);
_M_initialize_value(__value);
}
reference operator[](size_type __n)
{
return *iterator(this->_M_impl._M_start._M_p + __n / int(_S_word_bit),
__n % int(_S_word_bit));
}
//...
}; 因此，std::vector<bool> 的默认内存分配器仍然是std::allocaotr<bool>，这就解释了上面的基类std::_Bvector_base中通过 __alloc_traits 获得std::allocator<_Bit_type>的必要性。
而std::vector<bool>的构造函数，主要是调用了_M_initialize、_M_initialize_value两个函数。
Minitialize
_M_initialize 函数，其输入参数__n 对于函数使用者来说表达的是__n个bool类型，但是对于设计者而言，__n是被视为__n个bit。这个函数主要有两步：
- 基类
std::_Bvector_base的_M_allocate函数分配内存； - 使用
std::_Bvector_impl_data类的成员变量来记录这块内存的使用情况。
先看下整体实现。
template <typename _alloc>
void vector<bool, _alloc>::_M_initialize(size_type __n)
{
if (__n) {
_Bit_pointer __q = this->_M_allocate(__n); // 分配__n个字节的内存
this->_M_impl._M_end_of_storage = __q + _S_nword(__n); // 内存末尾
this->_M_impl._M_start = iterator(std::__addressof(*__q), 0); // 内存首地址
}
else {
this->_M_impl._M_end_of_storage = _Bit_pointer();
this->_M_impl._M_start = iterator(0, 0);
}
// 指向第一个未使用的bit
this->_M_impl._M_finish = this->_M_impl._M_start + difference_type(__n);
} 由于std::vector<bool>内部是按照_Bit_type为基本类型进行存储的，_S_nword(__n) 计算的是存储__n 个bit至少需要几个 _Bit_type 。因此，_M_end_of_storage ：
- 当
__n是_S_word_bit的整倍数，_M_end_of_storage指向的地址就是__q + __n / _S_word_bit； - 否则，就是指向了
__q + __n / _S_word_bit + 1。
因此，_M_end_of_storage 指向的就是可使用内存的下一个字节，整个可用内存区间是[_M_start, _M_end_of_storage)。
Minitialize_value
由_M_initialize_value函数，为[_M_start,_M_end_of_storage)初始化为 __x。
///@brief 为[start, end_of_storage) 区间全部赋值为 __x
void _M_initialize_value(bool __x)
{
if (_Bit_type* __p = this->_M_impl._M_start._M_p)
__builtin_memset(__p,
__x ? ~0 : 0,
(this->_M_impl._M_end_addr() - __p) * sizeof(_Bit_type));
} push_back
最后，再来看看 std::vector<bool> 是怎么添加元素的，下面以push_back函数为例。
- 先检测当前是否还有内存，即
_M_finish._M_p != _M_end_of_storage，如果还有则直接在_M_finish._M_offset位置处构造对象； - 否则，需要扩容，再插入。这由
_M_insert_aux函数完成。
完整如下：
template <typename _alloc>
void vector<bool, _alloc>::push_back(bool __x)
{
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
*this->_M_impl._M_finish++ = __x;
else
_M_insert_aux(end(), __x);
}
iterator end() noexcept
{ return this->_M_impl._M_finish; } Minsert_aux
_M_insert_aux函数，表达的语义是 __pos位置插入__X，自然就需要考虑[_M_start, _M_end_addr)区间是否还有多余的内存了。
template <typename _alloc>
void vector<bool, _alloc>::_M_insert_aux(iterator __position, bool __x)
{
if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) {
// 将 [__position, _M_finish) 后移动一位
std::copy_backward(__position,
this->_M_impl._M_finish,
this->_M_impl._M_finish + 1);
// 将 __x 插入在 __position 位置
*__position = __x;
++this->_M_impl._M_finish;
}
else {
/*** 需要扩容 ***/
const size_type __len = _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
_Bit_pointer __q = this->_M_allocate(__len); // 新的内存
iterator __start(std::__addressof(*__q), 0); // 指向新的内存首地址
// [_M_start, __pos) 移动到 __start 开始的位置
iterator __i = _M_copy_aligned(begin(), __position, __start);
// 将 __x 赋值给 __i 位置的值
*__i++ = __x;
// [_pos, _M_finish) 移动到 __i 开始的位置
iterator __finish = std::copy(__position, end(), __i);
// 释放原来的内存
this->_M_deallocate();
// 调整地址
this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
this->_M_impl._M_start = __start;
this->_M_impl._M_finish = __finish;
}
} operator[]
最后，再完整地分析下赋值流程，更好地将前文的知识穿起来。
获得 _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 的operator=函数，仅改变需要改变的那位，对其他bit不会改变。
_Bit_reference& _Bit_reference::operator=(bool __x) noexcept
{
if (__x)
*_M_p |= _M_mask;
else
*_M_p &= ~_M_mask;
return *this;
} 经过上面的源码分析，最后我们再来看看一个问题：一个std::vector<bool>对象占据多少字节？
sizeof(std::vector<bool>{}); // ??? 其大小等效于：
sizeof(std::_Bvector_impl_data); sizeof(_M_start); // 12 padding // 16 sizeof(_M_finish); // 28 padding // 32 sizeof(_M_end_of_storage); // 40
因此，经过字节对齐后，一个std::vector<bool>的大小是40个字节。
std::vector<bool>的源码分析，到此为止。</bool,></bool,></bool,></bool,></bool,></bool,></std::random_access_iterator_tag,></std::random_access_iterator_tag,></std::random_access_iterator_tag,></std::random_access_iterator_tag,></t,std::allocator
全部评论
(1) 回帖