首页 > 源码分析std::vector<bool>设计,学会合理使用
头像
fibonaccii
编辑于 2021-06-07 21:47
+ 关注

源码分析std::vector<bool>设计,学会合理使用

> 导读:天天刷题,怎么能不知道 std::vector<bool> 设计呢。

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

前言

std::vector<bool>,是类 sd::vector<t,std::allocator<t>&gt; 的部分特化,为了节省内存,内部实际上是按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_referencestd::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 &amp;) = default;

    ///@brief 隐式转成 bool
    ///       bool state = vb[1]; 触发的就是此函数
    operator bool() const noexcept
    { return !!(*_M_p &amp; _M_mask); }

    ///@brief 将 _M_p 的 _M_mask 位,设置为 _x 状态
    ///        vb[1] = true; 触发的就是此函数
    _Bit_reference&amp; operator=(bool __x) noexcept
    {
      if (__x)
        *_M_p |= _M_mask;  // 1
      else
        *_M_p &amp;= ~_M_mask;
      return *this;
    }

    // @brief 这个函数实际上调用了:
    //   1. 先调用了 operator bool() const noexcept
    //   2. 在调用了 _Bit_reference&amp; operator=(bool __x) noexcept
    _Bit_reference&amp; operator=(const _Bit_reference &amp;__x) noexcept
    { return *this = bool(__x); }

    bool operator==(const _Bit_reference &amp;__x) const
    { return bool(*this) == bool(__x); }

    bool operator&lt;(const _Bit_reference &amp;__x) const
    { return !bool(*this) &amp;&amp; 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&amp;">
   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&amp;                            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字段含义不同,_M_mask是指示 _M_offset 处的bit是0还是1。

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

  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 &lt; 0)
      {
        __n += int(_S_word_bit);
        --_M_p;
      }
      _M_offset = static_cast<unsigned int>(__n);
    }

    /** 下面是关于迭代器的比较运算重载 **/

    bool operator==(const _Bit_iterator_base &amp;__i) const
    { return _M_p == __i._M_p &amp;&amp; _M_offset == __i._M_offset; }

    bool operator&lt;(const _Bit_iterator_base &amp;__i) const
    { return _M_p &lt; __i._M_p || (_M_p == __i._M_p &amp;&amp; _M_offset &lt; __i._M_offset); }

    bool operator!=(const _Bit_iterator_base &amp;__i) const
    { return !(*this == __i); }

    bool operator&gt;(const _Bit_iterator_base &amp;__i) const
    { return __i &lt; *this; }

    bool operator&lt;=(const _Bit_iterator_base &amp;__i) const
    { return !(__i &lt; *this); }

    bool operator&gt;=(const _Bit_iterator_base &amp;__i) const
    { return !(*this &lt; __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 &lt;&lt; _M_offset); }

    /// @brief 索引
    reference operator[](difference_type __i) const
    { return *(*this + __i); }

    /** 下面是运算符重载 **/

    /// @brief 每次前进一个bit
    iterator&amp; operator++()
    {
      _M_bump_up();
      return *this;
    }

    /// @brief 每次后退一个bit
    iterator&amp; operator--()
    {
      _M_bump_down();
      return *this;
    }

    iterator&amp; operator+=(difference_type __i)
    {
      _M_incr(__i);
      return *this;
    }

    iterator&amp; 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指向的就是这块内存的最后一个可使用字节的后一个位置。

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&amp;&amp; __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 &amp;&amp;__x) noexcept
      {
        this-&gt;_M_start = __x._M_start;
        this-&gt;_M_finish = __x._M_finish;
        this-&gt;_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&lt;_Alloc&gt;::template rebind&lt;_Bit_type&gt;::other  _Bit_alloc_type;

    因此,_Bit_alloc_type 实际上就是 std::allocator&lt;_Bit_type&gt;

    如果不了解 类__gnu_cxx::__alloc_traitsrebind函数,可以看看我之前写的一期 提高C++程序员的自我修养 from 剖析STL内存分配器,在里面详细分析过。

    by the way

    std::vector<bool> 的全称是 std::vector<bool, std::allocator<bool>&gt;,最初传入的分配器是std::allocator<bool>,是为bool类型变量分配内存的。

    但由STL对bool类型做了特化,内部并不是存储bool类型,而是_Bit_type类型,因此 std::allocator 现在需要为_Bit_type类型分配内存,这就需要通过 rebind 函数来获得获得 std::allocator&lt;_Bit_type&gt;

  2. std::_Bvector_impl_data

    _Bit_alloc_type 负责获得_Bit_type类型的内存分配器 std::allocator&lt;_Bit_type&gt;,而所得的内存就是由 _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&lt;_Bit_alloc_type&gt;::value)
      : _Bit_alloc_type() { }

      _Bvector_impl(const _Bit_alloc_type &amp;__a) noexcept
      : _Bit_alloc_type(__a) { }

      ///@brief 默认的移动构造函数就满足了,因为 
      ///  1. _Bit_alloc_type 是个空基类
      ///  2. _Bvector_impl_data 已经实现了移动构造函数
      _Bvector_impl(_Bvector_impl&amp;&amp;) = default;

      /// @brief 获得 _M_end_of_storage 指向的地址
      _Bit_type* _M_end_addr() const noexcept {
        if (this-&gt;_M_end_of_storage)
          return std::__addressof(this-&gt;_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&lt;_Alloc&gt;::template rebind&lt;_Bit_type&gt;::other  _Bit_alloc_type;
    typedef typename __gnu_cxx::__alloc_traits&lt;_Bit_alloc_type&gt;                            _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&amp; __a) : _M_impl(__a) { }
    _Bvector_base(_Bvector_base &amp;&amp;) = default;

    ~_Bvector_base()
    { this-&gt;_M_deallocate(); }

    /// @brief  获取内存分配器,实质就是子类对象转换为父类
    _Bit_alloc_type&amp; _M_get_Bit_allocator() noexcept
    { return this-&gt;_M_impl; }

    /// @brief 由 std::allocator&lt;_Bit_type&gt; 构造 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 &amp;&amp;__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"> &gt;
  class vector : protected _Vector_base&lt;_Tp, _Alloc&gt;  { 
   //...   
  };

  // 第一个参数特化为bool
  template <typename _alloc>
  class vector<bool, _alloc> : protected _Bvector_base&lt;_Alloc&gt; { 
    typedef _Bvector_base&lt;_Alloc&gt;            _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 &amp;__a = allocator_type())
    : vector(__n, false, __a) // 委托构造函数
    { }

    vector(size_type __n, const bool &amp;__value, const allocator_type &amp;__a = allocator_type())
    : _Base(__a)
    {
      _M_initialize(__n);
      _M_initialize_value(__value);
    }

    reference operator[](size_type __n)
    {
      return *iterator(this-&gt;_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&lt;_Bit_type&gt;的必要性。

std::vector<bool>的构造函数,主要是调用了_M_initialize_M_initialize_value两个函数。

Minitialize

_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-&gt;_M_allocate(__n);                    // 分配__n个字节的内存
        this-&gt;_M_impl._M_end_of_storage = __q + _S_nword(__n);        // 内存末尾
        this-&gt;_M_impl._M_start = iterator(std::__addressof(*__q), 0); // 内存首地址
      }
      else {
        this-&gt;_M_impl._M_end_of_storage = _Bit_pointer();
        this-&gt;_M_impl._M_start = iterator(0, 0);
      }

      // 指向第一个未使用的bit
      this-&gt;_M_impl._M_finish = this-&gt;_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)

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-&gt;_M_impl._M_start._M_p)
        __builtin_memset(__p, 
                         __x ? ~0 : 0,
                         (this-&gt;_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-&gt;_M_impl._M_finish._M_p != this-&gt;_M_impl._M_end_addr())
        *this-&gt;_M_impl._M_finish++ = __x;
      else
        _M_insert_aux(end(), __x);
   }  

   iterator end() noexcept
   { return this-&gt;_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-&gt;_M_impl._M_finish._M_p != this-&gt;_M_impl._M_end_addr()) {
      // 将 [__position, _M_finish) 后移动一位
      std::copy_backward(__position, 
                         this-&gt;_M_impl._M_finish,
                         this-&gt;_M_impl._M_finish + 1);
      // 将 __x 插入在 __position 位置
      *__position = __x;
      ++this-&gt;_M_impl._M_finish; 
    }
    else {
      /*** 需要扩容 ***/

      const size_type __len = _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
      _Bit_pointer __q = this-&gt;_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-&gt;_M_deallocate();
      // 调整地址
      this-&gt;_M_impl._M_end_of_storage = __q + _S_nword(__len);
      this-&gt;_M_impl._M_start = __start;
      this-&gt;_M_impl._M_finish = __finish;
    }
  }

operator[]

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

获得 _Bit_reference 对象

首先根据__n 定位到具体的第几个_Bit_type对象及其具体的某位,最终返回的是 _Bit_reference类型:

  *iterator(this-&gt;_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 &lt;&lt; _M_offset); }

也就是说,返回的_Bit_reference对象的_M_mask字段中, 仅需要改变值的那位是1,其他位置都是0。

_Bit_reference对象赋值

此时调用的是_Bit_referenceoperator=函数,仅改变需要改变的那位,对其他bit不会改变。

_Bit_reference&amp; _Bit_reference::operator=(bool __x) noexcept
{
  if (__x)
    *_M_p |= _M_mask;  
  else
    *_M_p &amp;= ~_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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐