vlambda博客
学习文章列表

但凡上网搜索下关于 std::vector<bool> 的讨论，基本都是吐槽它的实现，分不清这么设计是feature还是bug。此外，由于 std::vector<bool> 也经常应用在leetcode刷题中。因此，本期就来聊下它的底层实现，来帮助你正确的使用它。

前言

std::vector<bool>，是类 sd::vector<T,std::allocator<T>> 的部分特化，为了节省内存，内部实际上是按bit来表征bool类型。从底层实现来看，std::vector<bool> 可视为动态的std::bitset，只是接口符合 std::vector，换个名字表达为 DynamicBitset 更为合理，也许就没那么多吐槽了。

下面，就从源码角度一点点解开剖析。

loOK后端

深入了解后端架构、分布式系统

29篇原创内容

Official Account

_Bit_type

先来看看是怎么存储bit的。

在C++标准中，并没有单独的bit类型。GNU-STL使用一个typedef，将 unsigned long 定义为 _Bit_type，如此，一个_Bit_type 就有64 bit，也就可以存储64个bool类型变量。

在X86-64位CPU上，unsigned long 类型在 MSVC中4个字节，在GCC中8个字节。

 typedef unsigned long _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 就必须满足两点：

1. std::_Bit_reference能隐式转换为bool类型
2. 能接受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, 
           typename _Distance = ptrdiff_t,
           typename _Pointer = _Tp*, 
           typename _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中，有两个字段：

1. _M_p：指向数据体实体，和 std::_Bit_reference  中的 _M_p 相同；
2. _M_offset：指示当前正遍历到 _M_p中第 _M_offset 个bit（从0开始计数），这和 std::_Bit_reference中的 _M_mask字段含义不同。

还有三个比较重要的成员函数：

1. _M_bump_up：前进一位，是后面实现 ++operator重载的基础；
2. _M_bump_down：后退一位，是后面实现 --operator重载的基础；
3. _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，重载 --  和 ++  操作以及解引用等运算操作。

类 std::_Bit_iterator的部分实现及注释如下。

  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 的数据存储，里面有三个字段：

1. _M_start：指向内存的首地址，即 begin() 函数的返回值；
2. _M_finish：下一个元素要插入的位置，即 end() 函数的返回值；
3. _M_end_of_stroage：整个可用内存区间是 [_M_start, _M_end_of_storage)， _M_end_of_stroage指向的就是这块内存的最后一个bit的后一个位置。

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 继承了两个类：

1. _Bit_alloc_type：负责分配内存
2. std::_Bvector_impl_data：负记记录内存的使用情况

如此，才使 std::_Bvector_impl 成为实现std::vector<bool>的核心：

1. _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函数，可以看看我之前写的一期 【】，在里面详细分析过。

   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>。

2. 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两个函数。

_M_initialize

_M_initialize 函数，其输入参数__n  对于函数使用者来说表达的是__n个bool类型，但是对于设计者而言，__n是被视为__n个bit。这个函数主要有两步：

1. 调用基类 std::_Bvector_base 的 _M_allocate 函数分配内存；
2. 使用 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 ：

1. 当 __n 是 _S_word_bit 的整倍数， _M_end_of_storage 指向的地址就是 __q + __n / _S_word_bit；
2. 否则，就是指向了 __q + __n / _S_word_bit + 1。

因此，_M_end_of_storage 指向的就是可使用内存的下一个字节，整个可用内存区间是[_M_start, _M_end_of_storage)。

_M_initialize_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函数为例。

1. 先检测当前是否还有可用内存，即 _M_finish._M_p != _M_end_of_storage ，如果还有则直接在 _M_finish._M_offset 位置处构造对象；
2. 否则，需要扩容，再插入。这由 _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; }

_M_insert_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[]

最后，再完整地分析下赋值流程，更好地将前文的知识穿起来。

  std::vector<bool> vb(3); 
  vb[1] = true;   // 由如下两步完成

1. 获得 _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。

2. 给_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>的源码分析，到此为止，下期再见。

一个热爱技术Up主