std::vector：特殊化、权衡与替代方案

在《位标志与通过 std::bitset 进行位操作》中，我们介绍了 std::bitset 能够将 8 个布尔值压缩到一个字节中，并通过其成员函数对这些位进行修改。

std::vector 也有一项有趣的技巧：针对 std::vector<bool> 存在一个特殊实现，它同样可以将 8 个布尔值压缩到 1 个字节，从而在空间上更为节省。

【进阶读者】
当某个模板类针对特定模板实参提供不同实现时，这称为类模板特化（class template specialization）。我们将在《类模板特化》中进一步讨论该主题。

与专为位操作设计的 std::bitset 不同，std::vector<bool> 并不提供位操作的成员函数。

使用 std::vector

在大多数情况下，std::vector<bool> 的使用方式与普通 std::vector 相同：

#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 0 0 1 1
1 0 0 1 0

std::vector 的权衡

然而，std::vector<bool> 存在一些用户应当了解的权衡：

1. 较大的额外开销
   在作者机器上，sizeof(std::vector<bool>) 为 40 字节。因此，只有当存储的布尔值数量超过该架构下的开销时，才会真正节省内存。

2. 性能高度依赖实现
   标准并未强制要求实现必须优化，甚至未强制要求优化质量。根据 这篇文章，高度优化的实现可以显著快于其他方案；而实现不佳时则可能更慢。

3. 并非真正的 vector
   std::vector<bool> 不是一个 vector：

   • 不要求内存连续；
   • 不真正存储 bool 值，而是存储位集合；
   • 不符合 C++ 对容器的定义。

   尽管其在大多数情况下表现类似 vector，但与标准库的其余部分并不完全兼容。对其他元素类型有效的代码，可能对 std::vector<bool> 无效。例如：

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

   当 T 为 bool 时，上述代码将无法编译，因为 v[0] 返回的是代理对象，而非真正的 bool&。

避免使用 std::vector

现代共识是：std::vector<bool> 通常应当避免。其带来的性能收益往往不足以抵消因“并非真正容器”而产生的兼容性麻烦。

遗憾的是，这一优化版本默认启用，且无法通过任何开关换回一个“真正是容器”的非优化版本。社区已多次呼吁废弃 std::vector<bool>，并正在探讨未来可能的替代方案（如 std::dynamic_bitset）。

我们的建议

• 编译期已知位数、且数量适中（如 < 64k）
  使用 constexpr std::bitset，其接口简洁，满足位操作需求。

• 需要可变长布尔容器，且空间节省非刚需
  使用 std::vector<char>，其行为与普通容器一致。

• 需要动态位集并进行位运算
  优先选择第三方动态位集实现（如 boost::dynamic_bitset），它们不会伪装成标准容器。

最佳实践

在 constexpr std::bitset、std::vector<char> 或第三方动态位集中做出选择，而非使用 std::vector<bool>。