为什么vector<bool>不是标准STL容器

Why isn’t vector<bool> a STL container?

不使用vector<bool>的原因

vector<bool>的替代解决方案

替代方案：
其中，第3种方案的确在LeetCode刷题的时候看到过。毕竟很多时候需要一个visited数组存储是否访问过某个位置，如果只是这个功能的话，用vector<char>存储，然后’0’和’1’分别表示尚未访问和访问过也可以，当然vector<int>也可以。但下面还是bitset更节省空间，毕竟是以bit位的方式处理的。但是bitset只能表示一维的，所以多层vector的时候还是考虑方案3、4。

1.std::bitset —— 固定数组存放
bitset
std::bitset 与vector <bool>非常相似：它包含一组位bit，并能在常数时间内对每个位进行访问。
但 std::bitset 与vector <bool>有两个主要区别。
首先， std::bitset 的大小不能更改： std::bitset 的模板参数N（用于指定 std::bitset 中的位数）必须为整数常量。
其次，位不是序列Sequence。 实际上，它根本不是STL容器。 例如，它没有迭代器，也没有begin（）和end（）成员函数。 相反， std::bitset 的位操作接口类似于无符号整数的位操作接口。 它定义了按位算术运算符，例如＆=，| =和^ =。
通常，位0是最低有效位，位N-1是最高有效位。
示例：

#include <bitset>

int main() {
  const bitset<12> mask(2730ul);
  cout << "mask =      " << mask << endl;

  bitset<12> x;

  cout << "Enter a 12-bit bitset in binary: " << flush;
  if (cin >> x) {
    cout << "x =        " << x << endl;
    cout << "As ulong:  " << x.to_ulong() << endl;
    cout << "And with mask: " << (x & mask) << endl;
    cout << "Or with mask:  " << (x | mask) << endl;
  }
}

输出：

//  The output is:
//
//  mask =      101010101010
//  Enter a 12-bit bitset in binary: 1010101011101110
//  x =        101010101110
//  As ulong:  2734
//  And with mask: 101010101010
//  Or with mask:  101010101110

因此，可以通过bitset<N> 声明size_t = N的bitset，同时可以用unsigned long数对其进行初始化，比如这里的const bitset<12> mask(2730ul);的2730ul，就是101010101010。

2. boost::dynamic_bitset<> —— 动态可变的数组存放
boost::container::vector
dynamic_bitset类表示一组位bit。它通过operator []提供对单个位值的访问，并提供可应用于基本内置整数类型的所有按位运算符，例如operator＆和operator <<。集合中的位数是在运行时通过dynamic_bitset构造函数的参数指定的。

dynamic_bitset类与std :: bitset类几乎相同。区别在于，dynamic_bitset的大小（位数）是在构造dynamic_bitset对象的过程中在运行时指定的，而std :: bitset的大小是在编译时通过整数模板参数指定的。

dynamic_bitset设计要解决的主要问题是代表有限集的子集。每个位代表有限集的元素是否在子集中。这样，dynamic_bitset的按位运算（例如operator＆和operator |）对应于设置运算（例如相交和并集）。

举例1：

#include <iostream>
#include <boost/dynamic_bitset.hpp>

int main()
{
    boost::dynamic_bitset<> x(5); // all 0's by default
    x[0] = 1;
    x[1] = 1;
    x[4] = 1;
    for (boost::dynamic_bitset<>::size_type i = 0; i < x.size(); ++i)
        std::cout << x[i];
    std::cout << "\n";
    std::cout << x << "\n";


    return 0;
}

输出：

//  The output is:
//
//  11001
//  10011

举例2：

#include <iostream>
#include <boost/dynamic_bitset.hpp>

int main()
{
  const boost::dynamic_bitset<> b0(2, 0ul);
  std::cout << "bits(0) = " << b0 << std::endl;

  const boost::dynamic_bitset<> b1(2, 1ul);
  std::cout << "bits(1) = " << b1 << std::endl;

  const boost::dynamic_bitset<> b2(2, 2ul);
  std::cout << "bits(2) = " << b2 << std::endl;

  const boost::dynamic_bitset<> b3(2, 3ul);
  std::cout << "bits(3) = " << b3 << std::endl;

  return 0;
}

输出：

//  Sample output:
//
//  bits(0) = 00
//  bits(1) = 01
//  bits(2) = 10
//  bits(3) = 11

3.vector<char>或vector<int>
很多时候需要一个visited数组存储是否访问过某个位置，如果只是这个功能的话，用vector<char>存储，然后’0’和’1’分别表示尚未访问和访问过，当然vector<int>也可以。

4. deque
deque<bool>来取代vector<bool>