什么，这不是 container，这是一个压缩 bool block。我们这个压缩 bool block 体积小方便存储，声明一个，push_back() 会变大，怎么 push 都 push 不满，用来压位，压位，压位都是很好用的，你看内存分布像满天繁星一样，放在电脑里 push_back() 变多变乱，碎片很多的。operator [] 以后，是一条变小变 safety 的 std::vector::reference，你看它怎么引用都引用不出来，不可修改随时销毁，使用 1e8 次都没问题，赛时切题带上它非常方便，用它 auto&，再 range_based_for，std::allocator_traits::construct，world leg tree。什么？在哪里写？下方 Dev-C++，写五次 CE 五次，还包 WA。

vector<bool> 不是一个 STL 容器。它也不保存 bool 类型的值。

依据 Effective STL, Item 18，若容器 c 是一个 T 类型元素容器，并且有 operator[]，那么以下代码必须能通过编译：

T *p = &c[0];

然而，对于 vector<bool>，

vector<bool> vb{false, true, false, true};
bool *p = &vb[0];

tmp.cpp:13:20: error: taking address of rvalue [-fpermissive]
   13 |     bool *p = &vb[0];
      |                ~~~~^
tmp.cpp:13:15: error: cannot convert 'std::vector<bool>::reference*' to 'bool*' in initialization
   13 |     bool *p = &vb[0];
      |               ^~~~~~
      |               |
      |               std::vector<bool>::reference*

究其原因，vector<bool> 更像位域(bitfield)。在实现上，为了节省内存空间，其内部打包 bool 类型，将其映射到 bit（这是 C++ 设计上的一个历史遗留问题）。由于指向单独 1bit 的指针非法，因此 vector<bool>::operator 返回被称作代理迭代器(proxy iterator)的对象。该对象可以被转换为 bool 类型。

vector<bool> vb{false, true, false, true};
auto b = vb[1];

等价于

using std::vector<bool>::reference = std::_Vb_reference<std::_Wrap_alloc<std::allocator<unsigned int>>> ;
std::vector<bool>::reference b = vb[1];

有必要注意的是，如果 vb 被销毁，则 b 会成为一个悬垂引用(dangling reference)。此时所有对 b 的操作都属于 ub。

std::vector<bool>::reference 内部应该使用了类似于 mask 位运算的方式来映射到位。

对于 range-based for，由于代理迭代器返回的不是一个左值，也会导致问题。

假如我们有

vector<bool> vb{false, true, false, true};
for(auto it : vb) cout << it << " ";

这是合适的。然而，若是

vector<bool> vb{false, true, false, true};
for(auto & it : vb) cout << it << " ";

这就会引发编译错误。

error: cannot bind non-const lvalue reference of type 'std::_Bit_reference&' to an rvalue of type 'std::_Bit_iterator::reference'

我们只能利用 const reference (const auto &) 或者 auto &&。这里的 auto && 应该是 Scott Meyers 所谓的 universal reference。

Effective Modern C++, Item6 中提到了一个例子。我现在将其更具体地表达。假设我们有一个函数，因为各种原因而设计为返回 vector<bool>。其中，返回值的每一个位置代表不同的意义。

vector<bool> f()
{
    vector<bool> res;
    res.push_back(true);
    res.push_back(false);
    res.push_back(true);
    res.push_back(false);
    return res;
}
// ...
bool b = f()[0];

这没有任何问题。

然而，如果在这里用 auto 推导 b 的类型，尽管不会有任何编译错误，但是会出现 ub。

vector<bool> f()
{
    vector<bool> res;
    res.push_back(true);
    res.push_back(false);
    res.push_back(true);
    res.push_back(false);
    return res;
}

int main()
{
    auto b = f()[0];
    cout << b;
    return 0;
}

0

让我们一步步看使用 auto 会发生什么。f() 返回一个临时的 vector<bool> 对象。operator[] 作用在其上，得到一个类型为 std::vector<bool>::reference 的代理迭代器。auto 因此将 b 的类型推导为 std::vector<bool>::reference，并将此迭代器赋给它。此后，临时的 vector<bool> 对象被自动销毁。指向它的 b 就成为了悬垂指针。

如果一定要使用 auto，可以显式初始化类型（话说这样写有任何必要吗？）：

auto b = static_cast<bool>(f()[0]);