STL--位图的介绍与使用
目录
bitset的介绍
位图的引入
位图的概念
位图的应用
bitset的使用
bitset的定义方式
bitset成员函数
bitset运算符的使用
bitset的介绍
位图的引入
给40亿不重复的无符号整形,每排过序.给一个无符号整数,如何快速判断一个数是否在这40亿个数中?
要判断一个数是否在某一堆数中,我们可能想到如下办法:
- 将这一对数进行排序,然后通过二分查找的方法判断该数是否在这一堆数中.
- 将这一堆数插入到unordered_set容器中,然后调用find函数判断该数是否在这一堆数中.
单从方法上来看,这两种方法都是可以的,而且效率也不错,第一种方法的时间复杂度是O(NlogN),第二种方法的时间复杂度O(N).
但问题是这里有40亿个数,若是我们将这些数全部加载到内存当中,那么将会占用16G的空间,空间消耗很大的,因此从空间消耗来看,上面这两种方法实际都是不可行的.
位图解决.
实际在这个问题当中,我们只需要判断一个数在或是不在,即只有两种状态,那么我们可以用一个比特位来表示数据是否存在,如果比特位1表示存在,比特位0表示不存在.比如:
无符号整数总共有2^32个,因此记录这些数就需要2^32个比特位,也就是512M的内存空间,内存消耗大大减少.
位图的概念
所谓位图.就是用每以为存放某一种状态,适用于海里数据,数据无重复的场景.通常是用来判断某个数据存不存在的.
位图的应用
常见的位图应用如下:
- 快速查找某个数据是否存在一个集合中.
- 排序.
- 求两个集合的交集并集等.
- 操作系统中磁盘块标记.
- 内核中信号标志位(信号屏蔽和未决信号).
bitset的使用
bitset的定义方式
方式一:构造一个16位的位图,所有位都初始化为0.
bitset<16> bs1;方式二:构造一个16为的位图,根据所给值初始化位图的前n为.
bitset<16> bs2(0xfa5);//0000111110100101方式三:构造一个16位的位图,根据字符串在的0/1序列初始化位图的前n位
bitset<16> bs3(string("10111001"));//0000000010111001bitset成员函数
bitset中常用的成员函数如下:
示例如下:
int main()
{
bitset<9> bs;
bs.set(2);
bs.set(4);
cout << bs << endl;//000010100
bs.flip();//反转所有位
cout << bs << endl;//111101011
cout << bs.count() << endl;//7
cout << bs.test(3) << endl;//1
bs.reset(0);//清空第0位
cout << bs << endl;//111101010
bs.flip(7);//第7位反转
cout << bs << endl;// 101101010
cout << bs.size() << endl;//9
cout << bs.any() << endl;//1
bs.reset();//清空所有位
cout << bs.none() << endl;//1
bs.set();//设置所有位
cout << bs.all() << endl;//1
return 0;
}注意:使用成员函数set,reset,filp时,若指定了某一位则操作该位,若未指定则操作所有位.
bitset运算符的使用
一,bitset中>> <<运算符的使用.
bitset容器对>> <<运算符进行了重载,我们可以直接使用>> <<运算符对bitset容器定义出来的对象进行输入和输出操作.
int main()
{
bitset<8> bs;
cin >> bs;//10110
cout << bs << endl;//00010110
return 0;
}二,bitset中赋值运算符,关系运算符,复合运算符,单目运算符的使用.
bitset容器中不仅对赋值运算符和一些关系运算符进行了重载,而且对符合运算符和单目运算符进行了重载,我们可以直接使用这些运算符对各个位图进行操作.
包括如下运算符:
- 赋值运算符:=.
- 关系运算符:== !=
- 符合运算符:&= |= ^= <<= >>=
- 单目运算符:~
int main()
{
bitset<8> bs1(string("10101010"));
bitset<8> bs2(string("10101010"));
bs1 >>= 1;
cout << bs1 << endl;//01010101
bs2 |= bs1;
cout << bs2 << endl;//11111111
return 0;
}三,bitset中位运算符的使用
bitset容器中同时也对三位运算符进行了重载,我们可以直接使用& | ^对各位图进行操作.
int main()
{
bitset<8> bs1(string("10101010"));
bitset<8> bs2(string("01010101"));
cout << (bs1 & bs2) << endl;//00000000
cout << (bs1 | bs2) << endl;//11111111
cout << (bs1 ^ bs2) << endl;//11111111
return 0;
}四,bitset中[]运算符的使用
bitset容器中对[]运算符进行了重载,我们可以直接使用[]对指定位进行访问或修改.
int main()
{
bitset<8> bs(string("10101010"));
cout << bs[0] << endl;//0;
bs[0] = 1;
cout << bs << endl;//10101011
return 0;
}