C++笔记---位图

1. 位图的概念

位图（Bitmap）是一种基于位操作的数据结构，用于表示一组元素的集合信息。它通常是一个仅包含0和1的数组，每个元素对应一个二进制位，若该元素存在，则对应的位为1；若不存在，则为0。位图的这种表示方式使得它能够在存储上以极高的空间效率来管理大规模数据。位图特别适用于需要频繁查询和更新的场景，如数据库索引、图像处理和网络协议等。

简单来说，就是一个采用直接定址法的哈希表，只不过一个bit位映射一个数。

底层通常是一个存储整形的数组或vector，将其中的整形数据连起来看作一个存储bit位的数组。下标为n的bit位为1代表n存在，为0代表n不存在。

这样一来，位图存储一个数据的消耗仅为一个bit位，相比于红黑树和哈希表，在对大量的整形数据的进行增删查改时，位图的优势就十分明显了。

优点：增删查改效率极高，空间复杂度低。

缺点：只适用于整型。

2. 位图的实现

STL的 "bitset" 就是位图，其有三个主要接口：set(插入)，reset(删除)，test(查找)。

bitset - C++ Reference

位图的实现比较简单，就不过多介绍了。

namespace lbz
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
			:_bs(N / 32 + 1, 0)
		{}

		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			_bs[i] |= (1 << j);
		}

		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			
			_bs[i] &= ~(1 << j);
		}

		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;

			return _bs[i] & (1 << j);
		}
	private:
		vector<int> _bs;
	};

 注意，这里无需在意大小端的问题，因为bit 位的下标只是假想的下标。

我们只需要算出代表x的bit位是哪一个整形中的第几个，并保证各个接口采用相同的逻辑查找即可。

3. 位图的应用

3.1 检查数据是否存在

eg：给40亿个不重复的无符号整数，没排过序。如何判断某个无符号数是否在这40亿个数中？（腾讯、百度等公司出过的面试题）。

思路1：暴力遍历--->时间复杂度O(N)，太慢

思路2：排序+二分查找--->时间复杂度O(N * logN) + O(logN)，排序消耗大，但是排好序之后可以进行多次查找。

但是上面两种思路都存在着一个问题，那就是需要将40亿个整数存到内存中。

40亿个整数约等于16GB，考虑到电脑中的其他进程，开出这么大的一个数组显然是不现实的。

这时候就可以使用位图来解决，位图中开辟 "UINT_MAX" 个字节(数据范围为0~UINT_MAX)，并将数据存储到位图中。此时，数据对内存的占用就可以降低到500MB左右，且查找效率为O(1)。

3.2 计算数据个数

eg：给100亿个不重复的无符号整数，没排过序。如何找出出现次数小于2的数据？

一个bit位只能判断存不存在，如果要计数，就只能用多个比特位来映射一个数。

这里，我们可以采用包装多个位图的方式来实现，第一个位图存储第一个bit位，第二个位图存储第二个bit位，以此类推。

template<size_t N>
class two_bitset
{
public:
	void set(size_t x)
	{
		bool bit1 = _bs1.test(x);
		bool bit2 = _bs2.test(x);

		if (!bit1 && !bit2)// 00 + 1
		{
			_bs2.set(x);
		}
		else if (!bit1 && bit2)// 01 + 1
		{
			_bs1.set(x);
			_bs2.reset(x);
		}
		else if (bit1 && !bit2)// 10 + 1
		{
			_bs2.set(x);
		}
	}

	void reset(size_t x)
	{
		_bs1.reset(x);
		_bs2.reset(x);
	}

	int test(size_t x)
	{
		bool bit1 = _bs1.test(x);
		bool bit2 = _bs2.test(x);

		if (!bit1 && !bit2)// 00
		{
			return 0;
		}
		else if (!bit1 && bit2)// 01
		{
			return 1;
		}
		else if (bit1 && !bit2)// 10
		{
			return 2;
		}
		else
		{
			return 3;
		}
	}
private:
	bitset<N> _bs1;
	bitset<N> _bs2;
};

先简单介绍一下，之后可能更新。