vlambda博客
学习文章列表

踩坑记 (3) | 源码分析 std::vector<bool> 设计,学会合理使用


全程高能


但凡上网搜索下关于 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 更为合理,也许就没那么多吐槽了。

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

踩坑记 (3) | 源码分析 std::vector<bool> 设计,学会合理使用
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<boolvb(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(00) {}
    _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_traitsrebind函数,可以看看我之前写的一期 【】,在里面详细分析过。

    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(00);
      }
      
      // 指向第一个未使用的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<boolvb(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_referenceoperator=函数,仅改变需要改变的那位,对其他bit不会改变。

_Bit_reference& _Bit_reference::operator=(bool __x) noexcept
{
  if (__x)
    *_M_p |= _M_mask;  
  else
    *_M_p &= ~_M_mask;
  return *this;
}


踩坑记 (3) | 源码分析 std::vector<bool> 设计,学会合理使用

接近尾声


经过上面的源码分析,最后我们再来看看一个问题:一个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>的源码分析,到此为止,下期再见。






END




一个热爱技术Up主