The Standard Librarian: Bitsets and Bit Vectors
Matt Austern
http://www.cuj.com/experts/1905/austern.htm?topic=experts
在 C++里，你能如愿地玩弄位元，而且甚至不用到宏。
------------------------------------------------------------------------------
编过程的人都熟悉布尔选项标志：将一组选项处理成一个整体，将它们打包进一个word，为每个选项使用一个位。比如，要设置Unix文件的许可权限，你可能类似于这样写：
chmod("my_file",
S_IWUSR | S_IRUSR |
S_IRGRP | S_IROTH);
每个常量对应一个位；通过用“位或”操作组合它们，你能够一次就指定很多选项。
将多个选项位打包进一个word的行为非常常见。这个技巧被用于很多地方，在Unix和Win32的API中，在C++标准运行库的ios_base格式化标志中，并且它的一些形式容易在大型的程序中出现。位元的集合是很重要的。
不难理解为什么这个技巧很常见：另外一种实现方法是，用数组或结构，每个选项对应一个不同的字段，这比较笨拙并且浪费内存。然而，有时候这个技巧会造成麻烦。首先，某些运算可能是笨拙的：设置一个被命名的位还比较直接（flags |= S_IRGRP），但清除一个位(flages &= ~S_IWGRP)多少有些丑陋。你能测试一个位是否被置位，通过将它掩模：if (falgs & S_IWUSR)；但当心犯“显式”测试的错误：if ((flags & S_IWUSR) == true)，或更糟的if (flags & S_IWUSR == ture)。对应于命名的位，对于编号的位，同样笨拙：需要使用类似于flags &= ~(1 << n)这样的表达式，通常还要加上强制类型转换。最后，这个技巧难以括大到有很多选项的情况：一旦标志的数目超过long的位数，就需要另谋它路了。
因为位元的集合很重要，所以C++标准运行库提供了对它们的显式支持－－事实上，有几种支持。有时你将会仍然想使用低层次的位操作（并且，某些时候你不得不这么做，如果你正在和C语言API交互)，但是在绝大部份情况下，C++运行库中的版本会更合适。它们有一些小问题，但绝大部份很容易绕过。
bitset
类std::bitset出现在C++标准第23章“关联容器”中。这不是它应该出现的正确位置，因为bitset与set和map这样的关联容器没有任何关系，它甚至没有满足STL容器的最基本的需求。把bitset当做一个整数会更好，它的每个的位都能单独访问－－但它不受long的长度的限制。bitset的长度大小在编译期决定（位元的数目是模板参数），但是没有上限：bitset<32>是32位长，bitset<1000>是1000。
你用过的整型位操作对bistset继续有效，并且，为了方便，还新增了一些操作。举例来说，你能写b1 ^ b2来进行“位或”运算(至少在b1和 b2长度相同时)。操作单个位有两个不同的接口：你可以用b.set(n)设定第n个位，用b.reset(n)清除它，并且用if (b.test(n))测试它；或者，几乎等价地，你可以把bitset当做一个数组，用b[n] = true，b[n] = false，和if (b[n])来实现相同的操作。(称“几乎”，是因为有一个小小的差异：数组版本不进行越界检查，而set()/reset()/test()版本进行。如果传给set()/reset()/test()的参数太大，将得到out_of_range异常。)
如果你用的bitset大小适当，直觉上你能将它当作一个整数：有一个构造函数以从unsigned long创建一个bitset，还有一个成员函数to_ulong()以从bitset获得一个unsigned long。当然，你不能直接使用这个构造函数以初始化超过unsigned long范围的位；同样，你不能用to_ulong()提取超过unsigned long的位。(如果你试着做了， 并且超过unsigned long的任何一位被置位了，那么to_ulong()将会抛出一个异常)。然而，如果需要，你能通过使用移位和掩模来绕开这些限制：
const int N =
sizeof(unsigned long) * CHAR_BIT;
unsigned long high = 0x7B62;
unsigned long low = 0x1430;
std::bitset<2*N> b
= (std::bitset<2*N>(high) << N) |
std::bitset<2*N>(low);
...
const std::bitset<2*N>
mask((unsigned long)(-1));
low = (b & mask).to_ulong();
high = (b >> N).to_ulong();
第0个位被定义为最低有效位，所以，举例来说，如果你写:
std::bitset<4> b(0xA);
被置位的位是b[1]和b[3]。
很容易用bitset替代传统的选项标志：只要在头文件中申明一个bitset对象以替代整数常量。我们已经说到了使用bitset的两个好处：你得到比long所能表示的更多的标志，你能用更容易和更安全的方法来操作每个位。另外一个是，bitset给你一个转换机制，以在bitset和文字表述间双向转换。
首先，bitset提供了常用的I/O操作。这个程序，
#include <bitset>
#include <iostream>
int main() {
std::bitset<12> b(3432);
std::cout << "3432 in binary is "
<< b << std::endl;
}
给出了直观的结果：
3432 in binary is 110101101000.
输入操作以同样的方法工作：它读入一个“1”和“0”组成的字符串，将它们转换为一个bitset。
其次，你能将bitsets转换成字符串或从字串转换而来：有一个接受一个string参数的构造函数，和bitset<>::to_string()成员函数。唉，虽然这些转换很有用，但细节表明它非常不方便。接受string的构造函数和to_string()成员函数都是成员模板，因为运行库的std::basic_string类本身就是模板；平常的字符串类，std::string是basic_string<char>的一个别名。
这些成员模板的通用性受C++的一些晦涩的规则的不幸影响。你必须写：
std::bitset<6>(std::string("110101"));
而不是
std::bitset<6>("110101");
仅将字符串文字“110101”直接传入的版本，将会给出编译期错误，因为编译器不知道该实例化出成员模板的什么版本。同样地，如果b 是bitset，你不能只是写：
std::string s = b.to_string();
你必须改用这种实在恐怖的形式：
std::string s
= b.template to_string<char,
std::char_traits<char>,
std::allocator<char> >();
(是的，那个看起来可笑的template关键字真的是必须的。)
当然，在实践中，你不应该用这样的东西污染你的代码。除非真的需要和多种字符类型合作，你可以将恐怖的语法细节封装入辅助函数：
template <std::size_t N>
std::bitset<N>
from_string(const std::string& s) {
return std::bitset<N>(s);
}
template <std::size_t N>
std::string
to_string (const std::bitset<N>& b) {
return b.template to_string<char,
std::char_traits<char>,
std::allocator<char> >();
}
vector<bool>
bitset确实有一个重要限制：它有一个固定的长度。你可以有比long更长的bitset，但你必须事先指定它的大小。对选项标志集之类的东西，这很好，但用于其它目的就不怎么合适了。假如，你正在以复杂的顺序处理一个巨大的条款集，并且你需要掌握已经看过哪些。这要求一个布尔值的数组，有理由使用“压缩”的数组，每个元素用一个位，但bitset就不再是合理的选择了。你正在处理的条款的数目直到运行时才能知道，并且条款甚至可能增加或移除。
C++标准运行库中另外一个管理位集合的机制是vector<bool>，vector<>模板的一个特化。在某些方面，vector<bool>与bitset非常象：每个元素用一个位表示，让你能使用数组的语法（比如，v[3] = true）来访问单个位。不同之处是bitset使用它自己的特有机制，而vector<bool>使用平常的STL接口。你能使用resize()成员函数改变元素的数目，或用push_back()增加新元素，就象其它vector<T>一样。
虽然vector<bool>没有对位运算提供特别的支持，你仍然可以使用平常的STL泛型算法和functor来完成这些操作。比如，不是写 v3 = v1 & v2 ，你可以写：
std::vector<bool> v3(v1.size());
std::transform(v1.begin(), v1.end(),
v2.begin(), v3.begin(),
std::logical_and<bool>());
同样地，将vector<bool>按bitset的operator<<相同的格式输出，你再一次能使用一个STL泛型算法：
std::copy(v.rbegin(), v.rend(),
std::ostream_iterator<char> (std::cout));
(这个代码依赖于一个事实，默认情况，bool的输出使用“1”和“0”而不是“true”和“false”。同样也注意到，我们正在使用 rbegin()和rend()以按逆序拷贝vector<bool>。这是bitset输出时的方式：bitset在打印时最左边的数是b[N-1]，而不是b[0]。)
只要有可能，你应该总是优先使用bitset而不是vector<bool>：与支持通用目的的vector接口的数据结构相比，固定大小的数据结构会有更好的性能，同时在空间和时间上。(在我运行过的一个时间测试中，bitset比vector快了几乎5倍。) 如果所管理的位集大小未不能事先预知，你就需要使用vector<bool>。
看起来还有一个情况应该用vector<bool>而不是bitset：当与STL泛型算法交互很重要时。STL泛型算法使用选择子，而vector<bool>提供了选择子（我们在上面的例子里看到了v.begin()和v.end()），bitset没有。你能用数组语法访问bitset中的单个位，但它没有begin()和end()成员函数。
然而，你不应该让这个缺乏阻止你！虽然bitset没有STL容器的接口，它仍然是一个非常好的(固定大小的)容器。如果使用bitset有意义，并且如果你还需要选择子，那么你可以定义一个简单的“下标选择子”适配器，以将选择子表述（比如*i）转换为数组表述（比如b[n]）。
实现很显然：维护一个下标和指向容器的指针。其细节，大部分就是我们在实现random iterator时所用到的，见于Listing 1。我们也定义一些非成员的辅助函数，begin()和end()，它们接受一个bitset为参数。(我们在Listing 1中显示的iterator不像它可能的那样通用：如果我们愿意接受稍微有些笨重的接口，我们就能定义一个能与任何类似与数组的类型合作的类了。一个通用目的下标选择子适配器在处理pre-STL容器类时常常有用，有时，即使是处理STL容器比如vector时都很有用。)
使用bitset_iterator，bitset现在能与STL组件交互：比如，你能将一个bitset拷贝入vector<bool>：
std::bitset<10> b;
...
std::vector<bool>
b(begin(b), end(b));
然而，如果你仔细看过Listing 1，你可能已经注意到bitset_iterator的一个问题：名字是一个谎言，因为bitset_iterator并不真的是一个iterator。如果i是一个iterator，那么*i应该返回i所指对象的引用。bitset_iterator没有这样做：const bitset_iterator返回bool，而不是const bool&，而可修改版本的bitset_iterator返回一个类型是bitset<>::reference的代理对象，而不是bool&。
因为位不是可独立寻址的，这是我们所能做的最好了；事实上，vector<bool>::iterator也以完全相同的方式行动的－－再一次，这意味着vector<bool>不是一个真正的STL容器。说bitset_iterator 和vecotr<bool>::iterator是iterator并不十分正确，但两者都足够接近于iterator了，所以它们能被用于很多( 不所有的!)期望iterator的地方。
总结
布尔值的数组在大程序中很常见，并且C++标准运行库提供了几个方法来表示这样的数组。我没有列全所有的可能：比如，你能使用valarray<bool>，在某些情况下它很适于表示一个稀疏的位向量，就象set<size_t>一样。
很多时候，无论如何，最容易的方法是使用std::bitset。如果你在编译期知道你的布尔数组应该多大，或至少能指定一个合理的上限，那么bitset更简单，更有效率。在bitset的接口上有些讨厌的问题，但藉由一些辅助函数，很容易绕过它们。
Listing 1 - bitset_iterator, an iterator adaptor class for std::bitset
template <bool flag, class IfTrue, class IfFalse>
struct IF;
template <class IfTrue, class IfFalse>
struct IF<true, IfTrue, IfFalse> {
typedef IfTrue val;
};
template <class IfTrue, class IfFalse>
struct IF<false, IfTrue, IfFalse> {
typedef IfFalse val;
};
template <std::size_t N, bool is_const>
class bitset_iterator {
private:
typedef std::bitset<N> Bitset;
typedef typename IF<is_const, const Bitset, Bitset>::val
qBitset;
typedef std::random_access_iterator_tag
iterator_category;
typedef bool value_type;
typedef std::ptrdiff_t difference_type;
typedef typename IF<is_const, const bool, bool>::val*
pointer;
typedef typename IF<is_const,
bool,
typename bitset::reference>::val
reference;
qBitset* B;
std::size_t n;
public:
bitset_iterator() : B(), n() { }
bitset_iterator(qBitset& b, std::size_t sz)
: B(&b), n(sz) { }
bitset_iterator(const bitset_iterator<N, false>& x)
: B(x.B), n(x.n) { }
bitset_iterator& operator=(const bitset_iterator& x) {
B = x.B;
n = x.n;
}
public:
reference operator*() const { return (*B)[n]; }
reference operator[](std::ptrdiff_t x) const {
return (*B)[n + x];
}
bitset_iterator& operator++() { ++n; return *this; }
bitset_iterator operator++(int) {
++n;
return bitset_iterator(*B, n-1);
}
bitset_iterator& operator--() { --n; return *this; }
bitset_iterator operator--(int) {
--n;
return bitset_iterator(*B, n+1);
}
bitset_iterator operator+(std::ptrdiff_t x) const {
return bitset_iterator(*B, n + x);
}
bitset_iterator& operator+=(std::ptrdiff_t x) {
n += x;
return *this;
}
bitset_iterator operator-(std::ptrdiff_t x) const {
return bitset_iterator(*B, n - x);
}
bitset_iterator& operator-=(std::ptrdiff_t x) {
n -= x;
return *this;
}
public:
friend bool operator==(bitset_iterator x,
bitset_iterator y) {
return x.B == y.B && x.n == y.n;
}
friend bool operator!=(bitset_iterator x,
bitset_iterator y) {
return !(x == y);
}
friend bool operator<(bitset_iterator x,
bitset_iterator y) {
return x.n < y.n;
}
friend bool operator>(bitset_iterator x,
bitset_iterator y) {
return y < x;
}
friend bool operator<=(bitset_iterator x,
bitset_iterator y) {
return !(y < x);
}
friend bool operator>=(bitset_iterator x,
bitset_iterator y) {
return !(x < y);
}
friend std::ptrdiff_t operator-(bitset_iterator x,
bitset_iterator y) {
return x.n - y.n;
}
friend bitset_iterator operator+(std::ptrdiff_t n1,
bitset_iterator x) {
return bitset_iterator(*x.B, x.n + n1);
}
};
template <std::size_t N>
bitset_iterator<N, true>
begin(const std::bitset<N>& b) {
return bitset_iterator<N, true>(b, 0);
}
template <std::size_t N>
bitset_iterator<N, true>
end(const std::bitset<N>& b) {
return bitset_iterator<N, true>(b, N);
}
template <std::size_t N>
bitset_iterator<N, false>
begin(std::bitset<N>& b) {
return bitset_iterator<N, false>(b, 0);
}
template <std::size_t N>
bitset_iterator<N, false>
end(std::bitset<N>& b) {
return bitset_iterator<N, false>(b, N);
}
— End of Listing —
