黑科技--位集--bitset

自从上次网赛发现这么个东西之后,深深地感受到了bitset的强大,0.0。

正常的bool占用1字节空间,bitset可以把这个缩到1bit,空间上8倍优化。正常用起来可能会跟位运算状态压缩类似,但是其中的每个位又能进行单独操作,所以确实相当方便。

下面是原版的文档:

class template

std::bitset

template <size_t N> class bitset;

Bitset

Abtsetstores bits (elements with only two possible values: 0 or 1, true or false, …).  //位集用于存储0、1元素。

The class emulates an array of bool elements, but optimized for space allocation: generally, each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char).  //这种类模拟了bool数组,但是单个元素占空间只有1bit。(!!好东西有木有!!)

Each bit position can be accessed individually: for example, for a given bitset named foo, the expression foo[3] accesses its fourth bit, just like a regular array accesses its elements. But because no elemental type is a single bit in most C++ environments, the individual elements are accessed as special references type (seebitset::reference).  //每个位都能被独立访问。(!!好东西有木有!!)

Bitsets have the feature of being able to be constructed from and converted to both integer values and binary strings (see its constructor and membersto_ulong andto_string ). They can also be directly inserted and extracted from streams in binary format (see applicable operators).  //这货还提供转化成其他类型的函数(!!好东西有木有!!)

Thesize of a bitset is fixed at compile-time (determined by its template parameter). For a class that also optimizes for space allocation and allows for dynamic resizing, see the bool specialization ofvector (vector).

Template parameters

N

Size of the bitset, in terms of number of bits. It is returned by member functionbitset::size.size_t is an unsigned integral type.  //大小由位数决定,并且可以引用内置函数直接查询某一bitset的大小

Member types

referenceReference-like type (public member class )

Member functions

(constructor)
Construct bitset (public member function )

applicable operators
Bitset operators (function )

Bit access

operator[]
Access bit (public member function )  //访问位集中的元素可以直接像访问数组一样完成

count
Count bits set (public member function )  //计数有多少位

size
Return size (public member function )  //返回空间大小

test
Return bit value (public member function )  //返回…这什么东西?

any
Test if any bit is set (public member function )  //返回位集中是否有元素1

none
Test if no bit is set (public member function )  //返回位集是否全空

all
Test if all bits are set (public member function )  //返回位集是否全满

Bit operations

set
Set bits (public member function )  //设置位

reset
Reset bits (public member function )  //清空位集

flip
Flip bits (public member function )  //位集元素置反

Bitset operations

to_string
Convert to string (public member function )

to_ulong
Convert to unsigned long integer (public member function )

to_ullong
Convert to unsigned long long (public member function )

Non-member function overloads

applicable operatorsBitset operators (function )

Non-member class specializations

hash Hash for bitset (class template specialization )

主要操作测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
#include<bitset>

using namespace std;

int main()
{
bitset<1000> a;

a[100]=1; //直接赋值
cout << a.count() << endl; //计数1的个数
cout << a.size() << endl; //返回空间大小
cout << a.test(1) << endl;
cout << a.test(100) << endl; //判断第i位是否为1
cout << a.any() << endl; //是否非空
cout << a.none() << endl; //是否全空
cout << a.all() << endl; //是否全满

a.set(2); //与赋值相同
cout << a[2] << endl; //直接访问,与test相同

a.reset(); //清空
cout << a.count() << endl;
cout << a.none() << endl;

a.flip(); //反置
cout << a.count() << endl;
cout << a.all() << endl;
}

输出结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
1
1000
0
1
1
0
0
1
0
1
1000
1
0%