0xzhang的博客

踩坑std::vector<bool>

· 0xzhang

缘由§

同事的程序中是C/C++与Fortran混用，有很多地方使用动态内存，似乎有内存泄漏，一时也没有发现问题所在。

不过说到不如直接用容器包起来传给Fortran内核。就试了试使用std::vector<bool>，然后编译都没有通过。大概包括这样的编译错误信息

error: invalid initialization of non-const reference of type ’bool&’ from an rvalue of type ‘std::vector<bool>::reference {aka std::_Bit_reference}’

查了查资料，vector<bool>中并非以bool为单位进行存储的，而是采用按位存储。那这样取出来指针，在其它地方以bool类型处理，自然不正确。

不是已经有std::bitset了，std::vector<bool>与之性能如何？std::vector<bool>还是容器吗？为了了解更多奇怪的知识，参考一些资料，记录在此文中。

std::vector<bool>§

To optimize space allocation, a specialization of vector for bool elements is provided.

为了优化空间，提供了vector的布尔类型特化版本。

以下内容主要参考【2】中公众号博主loOK后端的文章。

_Bit_type§

GNU-STL中这样定义存储位的类型。std::vector<bool> 使用unsigned long 作为按位存储bool值的基本类型。

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

typedef unsigned long _Bit_type;

std::_Bit_reference§

确定了std::vector<bool>的基本存储类型，由于按位存储，并不与基本类型相兼容，需要映射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;

类std::_Bit_reference支持以下功能，以和bool类型兼容

  1. 隐式转换为bool类型
  2. 接受bool类型赋值

std::_Bit_iterator§

std::vector<bool>自然也不能使用std::vector<T>中的迭代器。

std::vector<bool> 中对每个bit的移动操作是基于类 std::_Bit_iterator类实现的，它的基类是std::_Bit_iterator_base。

类 std::_Bit_iterator_base ，继承了迭代器类 std::iterator，而std::iterator是个空类，其中定义了一些 typedef。

类std::Bit_iterator 就是其基类std::_Bit_iterator_base 的wrapper，重载 -- 和 ++ 操作以及方括号、解引用等运算符。

std::_Bvector_base§

std::vector<bool>的基类是std::_Bvector_base。

在类std::_Bvector_base 中还有两个内嵌类：

std::_Bvector_impl_data§

类 std::_Bvector_impl_data 记录了 std::_Bvector_base 的数据存储，里面有三个字段：

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

std::_Bvector_impl§

类std::_Bvector_impl 继承了两个类：

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

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

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::vector<bool, _Alloc>§

std::vector<bool> 的默认内存分配器仍然是std::allocaotr<bool>，这就解释了类std::_Bvector_base中需要通过 __alloc_traits 获得std::allocator<_Bit_type>的必要性。

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

性能§

【3】中博主wpcockroach在msvc下，对bool、char、int三种类型的vector测试了100万次尾插和访问的耗时，bool的vector耗时超出char、int类型40倍以上。

【4】中的问题关于std::vector<bool>的性能，答主Jerry Coffin给出了不同的答案。他认为通常的问题所在是，std::vector<bool>与std::vector<T>, T isn't bool不同，std::vector<bool>不是一个容器。但这并不意味着Herb Sutter所说的避免使用std::vector<bool>或者用std::vector<char>代替std::vector<bool>总是正确。

是否使用std::vector<bool>与问题规模和缓存大小相关。Jerry分别使用1亿数据和1000万数据测试，测试bool和char两种类型的vector使用埃拉托斯特尼筛法中标记素数时的性能。可以看出在1亿数据规模下，使用char类型的vector会慢一些，而在1000万数据规模下，char类型的结果会慢3倍以上。

这里认为std::vector<char>占用了更大空间导致缓存性能不佳。不过，也许对于更大规模，char类型的vector将会反超？

这里没有再详细列出不同测试者的硬件配置（如处理器、缓存等）和软件环境（如编译器及版本），这个问题可以说是和时间或者说机器相关的，处理器的缓存总是伴随时间变化，那么这个问题的答案并非一成不变的。

【5】中的问题关于如何选择std::vector<bool>、std::vector<char>、std::vector<int>和std::set<bool>作为位图，答主MSN认为在不考虑机器和访问方式的情况下。对于std::vector<bool>和std::bitset，变量中的移位算法开销很大，取决于需要可以重写迭代相关运算符进行优化。对于非常稀疏的数据，存储索引的std::vector<bool>是最佳选择。对于零散的数据，应该使用哈希集合而非vector。

【6】中测试并比较了std::vector<bool>和std::bitset的性能，并提供了自己实现的打包版本。

小结§

  1. 从性能方面考虑，何时使用std::vector<bool>？如果能够在编译期确定元素数目，最好使用std::bitset。如果能在运行期确定元素数目，可以使用 boost::dynamic_bitset。为了实现动态变化，还得用到vector。为节省空间可以用std::vector<bool>，为了兼容容器可以使用std::vector<char>，两者的速度取决于具体的环境和问题。一种思路是，使用std::vector<std::bitset<sizeof(size_t)>>节省空间，尽管为了计算偏移的模运算成本很高。

  2. std::vector<bool>不是容器。std::vector<bool>不满足容器和顺序容器要求，不适用于应用于STL容器的一些算法，可能会导致编译期或运行期错误。例如，std::vector<bool>::iterator并非bool*类型，是特定实现的，并不符合标准迭代器的要求；std::vector<bool>::reference并非bool类型，而是与bool兼容的代理数据结构，负责在bit和bool值之间进行映射，这种情况下std::vector<bool>永远不能返回bool&。

    由于内存地址并不以bit为单位，bit在计算机上实际是不可寻址的。

    【8】中验证了std::vector<bool>可以使用的符合STL语义的接口。

    【2】中博主wpcockroach在博文中展示，使用Range-based循环访问并赋值时，出现非预期的行为，通过局部变量进行赋值竟可以影响到std::vector<bool>中存储的数据。问题的原因是？（复现了，还没有查）

  3. Boost并未特化实现bool类型的vector容器。Boost.Container版本的vector并未特化bool类型。 boost::dynamic_bitset相比std::bitset，可以在运行期指定大小来创建，但是不能像std::vector<bool>表示的动态数组那样去插入元素。

参考资料§

  1. std::vector - cppreference.com
  2. 踩坑记 (3) | 源码分析 std::vector 设计，学会合理使用 (qq.com) - loOK后端
  3. 说一说vector - wpcockroach - 博客园 (cnblogs.com) - wpcockroach
  4. c++ - Is using a vector of boolean values slower than a dynamic bitset? - Stack Overflow - Jerry Coffin
  5. c++ - Choosing between set vs. vector vs. vector to use as a bitmap (bitset / bit array) - Stack Overflow - MSN
  6. Bartek's coding blog: Packing Bools, Performance tests (bfilipek.com)
  7. Holding Bits - Thinking in C++ 2nd ed Volume 2 (mit.edu) - Bruce Eckel
  8. On vector -- Howard Hinnant : Standard C++ (isocpp.org)
  9. dynamic_bitset - 1.36.0 (boost.org)
  10. GotW #50: Using Standard Containers - Herb Sutter