C++标准库类型 bitset及其应用
---旧文整理---
bitset 对象用每一个bit位存储0或1,可以用来标记存在或者不存在,位置下标和存储内容组成一个key-value对。用bit标记的好处就是可以节省内存空间,特别是应用于海量数据处理中。
例如以下几个问题:(1) 已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数 ;(2) 2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数;(3) 某人有8角的邮票5张,1元的邮票4张,1元8角的邮票6张,用这些邮票中的一张或若干张可以得到多少种不同的邮资?
以上3个问题的共同点都可以归结为:在一大堆数中找出不重复的个数——去重复问题。对于问题(3),在6*5*7个整数中去重复,我们可以用char数组或int数组存取,内存的节省不是那么明显;但对于(1)和(2),就很有必要采用bieset类库了。(1)中:8位最大为99 999 999,如果用每一个bit表示一个号码是否存在,假如每个号码平均出现1次,理论上只需要100M个bit(12.5MB)的内存。
1 #include<iostream> 2 #include<bitset> // bitset类库声明 3 using namespace std; 4 5 int main() 6 { 7 const unsigned int a = 189; // 最大邮资188角 8 bitset<a> bitvec; // 生成bitset对象 9 10 int x = 0, y = 0, z = 0; 11 for (x = 0; x <= 5; ++x){ 12 for (y = 0; y <= 4; ++y){ 13 for (z = 0; z <= 6; ++z){ 14 bitvec[8 * x + 10 * y + 18 * z] = 1; 15 } 16 } 17 } 18 19 int count = 0; 20 for (x = 0; x<a; ++x) 21 if (bitvec[x]) 22 count++; 23 cout << "共有: " << count 24 << " 种邮资组合" << endl; 25 26 return 0; 27 }
参考链接:
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。