C++ std::vector<bool>的用法（附带实例）

在 C++ 中，我们可以使用 std::bitset 来处理固定大小的位序列。然而，有时 std::bitset 并不是一个好的选择，因为在编译时我们并不知道位的数量，并且仅仅定义一个包含足够多位的集合并不是一个好主意，因为你可能会陷入一种情况，即数字实际上不够大。

标准的替代方法是使用 std::vector<bool> 容器，这是 std::vector 的特化，具有空间和速度优化，因为实现实际并不存储布尔值，而是存储每个元素的单个位。

然而，出于这个原因，std::vector<bool> 不符合标准容器或序列容器的要求，std::vector<bool>::iterator 也不符合前向迭代器的要求。因此，这种特化不能用于期望使用 vector 的泛型代码。

作为 vector，它的接口与 std::bitset 的接口不同，并且不能被视为数字的二进制表示。不能直接从数字或字符串构造 std::vector<bool>，也不能将其转换为数字或字符串。

C++ vector<bool>的基本用法

vector<bool> 类在头文件 <vector> 的 std 命名空间中可用。

要操作 std::vector<bool>，请使用与处理 std::vector<T> 相同的方法，如以下示例所示：
1) 创建一个空 vector：

std::vector<bool> bv; // []

2) 向 vector 中添加位：

bv.push_back(true);  // [1]
bv.push_back(true); // [1, 1]
bv.push_back(false); // [1, 1, 0]
bv.push_back(false); // [1, 1, 0, 0]
bv.push_back(true); // [1, 1, 0, 0, 1]

3) 设置单个位的值：

bv[3] = true;    // [1, 1, 0, 1, 1]

4) 使用通用算法：

auto count_of_ones = std::count(bv.cbegin(), bv.cend(), true);

5) 从 vector 中删除位：

bv.erase(bv.begin() + 2); // [1, 1, 1, 1]

C++ vector<bool>的工作原理

std::vector<bool> 不是标准 vector，因为它被设计为通过为每个元素存储单个位而不是布尔值来提供空间优化。因此，它的元素不是存储在连续序列中，不能被布尔数组所代替。原因如下：
1) 索引操作符无法返回对特定元素的引用，因为元素不是单独存储的：

std::vector<bool> bv;
bv.resize(10);
auto& bit = bv[0];  // error

2) 解引用迭代器不能产生 bool 类型的引用，原因与前面提到的相同：

auto& bit = *bv.begin(); // error

3) 不能保证可以同时从不同的线程独立地操作单个位。

4) vector 数组不能用于需要前向迭代器的算法，如 std::search()。

5) 如果某些通用代码需要本列表中提到的任何操作，则无法在预期使用 std::vector<T> 的通用代码中使用 vector 数组。

std::vector<bool> 的替代方案是 std::deque<bool>，它是一个标准容器（双向队列），满足所有容器和迭代器的要求，可以与所有标准算法一起使用。然而，它没有 std::vector<bool> 提供的空间优化。

std::vector<bool> 接口与 std::bitset 差异很大。如果你希望以类似的方式编写代码，则可以在 std::vector<bool> 上创建一个包装器，让它看起来尽可能地像 std::bitset。

下面的实现提供了类似于 std::bitset 中的成员：

class bitvector
{
    std::vector<bool> bv;
public:
    bitvector(std::vector<bool> const & bv) : bv(bv) { }
    bool operator[](size_t const i) { return bv[i]; }

    inline bool any() const {
        for (auto b : bv) if (b) return true;
        return false;
    }

    inline bool all() const {
        for (auto b : bv) if (!b) return false;
        return true;
    }

    inline bool none() const { return !any(); }

    inline size_t count() const {
        return std::count(bv.cbegin(), bv.cend(), true);
    }

    inline size_t size() const { return bv.size(); }

    inline bitvector & add(bool const value) {
        bv.push_back(value);
        return *this;
    }

    inline bitvector & remove(size_t const index) {
        if (index >= bv.size())
            throw std::out_of_range("Index out of range");
        bv.erase(bv.begin() + index);
        return *this;
    }

    inline bitvector & set(bool const value = true) {
        for (size_t i = 0; i < bv.size(); ++i)
            bv[i] = value;
        return *this;
    }

    inline bitvector& set(size_t const index, bool const value = true) {
        if (index >= bv.size())
            throw std::out_of_range("Index out of range");
        bv[index] = value;
        return *this;
    }

    inline bitvector & reset() {
        for (size_t i = 0; i < bv.size(); ++i) bv[i] = false;
        return *this;
    }

    inline bitvector & reset(size_t const index) {
        if (index >= bv.size())
            throw std::out_of_range("Index out of range");
        bv[index] = false;
        return *this;
    }

    inline bitvector & flip() {
        bv.flip();
        return *this;
    }

    std::vector<bool>& data() { return bv; }
};

这只是一个基本实现，如果你想使用这样的包装器，应该添加额外的方法，例如位逻辑操作、移位和流的读写等。

然而，使用前面的代码，我们可以编写以下示例：

bitvector bv;
bv.add(true).add(true).add(false); // [1, 1, 0]
bv.add(false);                    // [1, 1, 0, 0]
bv.add(true);                    // [1, 1, 0, 0, 1]

if (bv.any()) std::cout << "has some 1s" << '\n';
if (bv.all()) std::cout << "has only 1s" << '\n';
if (bv.none()) std::cout << "has no 1s" << '\n';
std::cout << "has " << bv.count() << " 1s" << '\n';

bv.set(2, true);               // [1, 1, 1, 0, 1]
bv.set();                       // [1, 1, 1, 1, 1]

bv.reset(0);                   // [0, 1, 1, 1, 1]
bv.reset();                    // [0, 0, 0, 0, 0]

bv.flip();                     // [1, 1, 1, 1, 1]

这些示例与使用 std::bitset 的示例非常相似，这个 bitvector 类具有一个兼容 std::bitset 的 API，但对于处理可变大小的位序列很有用。