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::bitsettemplate <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 —
本文地址:http://com.8s8s.com/it/it1817.htm