位图的应用

应用2：找到只出现一次的整数

给定100亿个整数，找到只出现一次的整数

我们设置两个bitset来控制出现的次数

00代表出现0次

01代表出现1次

10代表出现两次及以上

	template<size_t N>
	class twobitset
	{
	public:

		void set(size_t x)
		{
			if (_bit1.test(x) == false && _bit2.test(x) == false)		//00->01
				_bit2.set(x);

			else if (_bit1.test(x) == false && _bit2.test(x) == true)	//01->10
			{
				_bit1.set(x);
				_bit2.reset(x);
			}
			else if (_bit1.test(x) == true && _bit2.test(x) == false)	//10->11
			{
				_bit2.set(x);
			}
			
		}


		void print()
		{
			for (size_t i = 0; i < N; i++)
			{
				if (_bit1.test(i) == false && _bit2.test(i) == true)				//01
					cout << i << " ";
			}

			cout << endl;
		}

	private:
		bitset<N> _bit1;		//自动调用该类的构造函数
		bitset<N> _bit2;
	};

虽然是100亿，但是只需要开 size_t -1就可以，因为数据重复（整数的范围就这些）

应用三：找交集

给你两个文件，分别有100亿个整数，只有1G内存，如何找到两个文件的交集

解决：将数据分别映射到两个位图，如果test之后都为true，那么就是交集

位图的应用

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

STL中的位图

C++的bitset数据并不是每一位都占用一个字节，而是通过优化使得每个位只占用1 bit的空间。（这是STL中的标准吗？）

是的，这是C++标准库中bitset的设计原则。bitset是一种专门用于处理位操作的数据结构，它通过将多个位压缩到一个字节中来实现空间优化。每个元素只占用1 bit的空间，而不是传统的bool类型通常占用的1字节空间。

这种设计使得bitset在处理大量二进制数据时非常高效，因为它减少了内存消耗并提高了访问速度。由于bitset直接操作位级别，而非字节级别，因此它可以提供更快的位操作性能。

需要注意的是，虽然bitset本身的大小不是固定的，但它的元素大小始终为1 bit。这意味着无论bitset的大小如何，每个元素的存储空间都是相同的。

缺陷：只能处理整型（数据需要/ %）