std::vector<bool>

vector有一个有趣的技巧。std::vector<bool>有一个特殊实现，它会以类似将8个布尔值压缩到一个字节中的方式，更有效地节省布尔值所需空间。

与为位操作而设计的std::bitset不同，std::vector<bool>缺少位操作成员函数。

使用std::vector<bool>

在大多数情况下，std::vector<bool>的工作方式与普通std::vector类似：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

#include <iostream>
#include <vector>

int main()
{
    std::vector<bool> v { true, false, false, true, true };
    
    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    // 将索引 4 位置的值改为 false
    v[4] = false;

    for (int i : v)
        std::cout << i << ' ';
    std::cout << '\n';

    return 0;
}

在作者的64位机器上，打印：

1
2

1 0 0 1 1
1 0 0 1 0

std::vector<bool>权衡

然而，std::vector<bool>有一些需要注意的权衡。

首先，std::vector<bool>有相当高的开销（sizeof(std::vector<bool>) 在作者的机器上是40个字节），因此除非分配的布尔值数量足以抵消这部分结构开销，否则不会节省内存。

其次，std::vector<bool>的性能高度依赖实现（因为实现甚至不需要进行优化，更不用说把优化做好了）。根据本文，高度优化的实现可能比替代方案快得多。然而，优化不佳的实现会更慢。

第三，也是最重要的一点，std::vector<bool>并不是真正的vector（它在内存中不需要连续），它也不包含bool值（而是包含一组bit），并且不满足C++对容器的定义。

尽管在大多数情况下，std::vector<bool>的行为类似于vector，但它与标准库的其余部分并不完全兼容。能与其他元素类型一起使用的代码，可能无法与std::vector<bool>一起使用。

例如，当T是除bool之外的任何类型时，以下代码都有效：

1
2
3
4
5
6

template<typename T>
void foo( std::vector<T>& v )
{
    T& first = v[0]; // 获取第一个元素的引用
    // 对first做一些操作
}

避免std::vector<bool>

现代共识是，通常应该避免使用std::vector<bool>，因为它不是一个合适的容器，而性能提升通常不值得承受这些不兼容带来的麻烦。

不幸的是，std::vector<bool>的优化版本默认启用，并且没有办法禁用。已经有人提议废弃std::vector<bool>，并且正在确定压缩bool vector未来可能是什么样子（可能作为未来的std::dynamic_bitset）。

我们的建议如下：

1. 当在编译时已知所需的比特数，没有超过中等数量的布尔值要存储（例如，低于64k），并且有限的运算符和成员函数集（例如，缺少迭代器支持）满足您的要求时，请使用（constexpr）std::bitset。
2. 当您需要一个可调整大小的布尔值容器并且不需要节省空间时，首选std::vector<char>。该类型的行为类似于普通容器。
3. 当需要动态比特集并对其执行位操作时，使用支持动态比特集的第三方实现（如boost::dynamic_bitset）。这样的类型不会假装自己是标准库容器。