【C++位图】构建灵活的空间效率工具

用户11305458

发布于 2024-10-09 17:26:31

980

发布于 2024-10-09 17:26:31

文章被收录于专栏：学习

在计算机科学中，位图（Bitmap）是一种高效的空间管理数据结构，广泛应用于各种场景，如集合操作、图像处理和资源管理。与传统的数据结构相比，位图通过使用二进制位来表示元素的存在与否，从而显著降低存储空间的消耗。然而，尽管位图的原理简单，其实现与操作却可能面临诸多挑战。

在本文中，我们将深入探讨如何在 C++ 中封装位图数据结构，重点介绍其基本操作、性能优化以及实际应用。通过封装，我们不仅可以提高代码的可读性和可维护性，还能为后续的功能扩展打下坚实的基础。让我们一起来揭开位图的神秘面纱，探索其在现代编程中的价值。

位图

位图的基本概念

位图（Bitmap）是一种用于高效表示集合的数据结构，其核心思想是使用二进制位来指示某个元素是否存在。在位图中，每个元素对应一个二进制位，若该元素存在，则对应的位为1；若不存在，则为0。这种表示方式使得位图能够在存储上以极高的空间效率来管理大规模数据。位图特别适用于需要频繁查询和更新的场景，如数据库索引、图像处理和网络协议等。在这些应用中，位图不仅能节省存储空间，还能提高算法的执行速度。假如我们有几十亿个数据需要在当中查找某个数，我们需要在当中查看某个数是否存在，很容易想到的方法是先用数组存起来，然后再进行排序，排序之后利用二分进行查找，如果单看时间复杂度其实是不大的，这里的问题其实不在算法上，而是在我们该如何存储着几十亿个数据，假如我们有四十亿个数据如果存储起来也需要16g的内存，消耗是相当大的，所以我们就引入了位图用来处理海量数据，这40亿个数据我们可以用40亿个比特位来表示，比特位只有1和0,1表示存在0表示不存在。40亿个比特位大约500mb，节省了将近33倍的空间，效率是相当大的。

如何用位图表示数据

我们是无法操作比特位的，C++操作内存的最小单位是字节，所以我们只能通过位运算来控制比特位，所以我们用 int类型的vector来控制。

我们通过一个vector控制，每个int位可以控制32个数。

位图的基本操作

位图有三个核心接口：reset，set还有一个test。 reset表示将指定数对应的比特位设置为0。 set表示将指定数对应的比特位设定为1。 test表示检测指定数对应的比特位是0还是1，如果是0返回0，如果是1返回1。

首先对位图我们需要一个：

std::vector<int> _bs;

set

void set(size_t x)
{
	size_t i = x / 32，j = x % 32;
	//需要把这个整形的第j位标记为1
	//bs或等于1左移七位
	_bs[i] |= (1 << j);
}

先将给定数的位置算出来，i表示在第几个int，j表示在比特位的第多少位。由于这里我们需要将第j位设置为1，而且不能动其他位，所以可以想到位运算（|）,先将1左移j位（左移不是表示向左移动，而是表示低位向高位移动），由于两个数进行按位或运算是如果有1结果就是1，0|1也是1,0|0也是0，所以这里不会改变其他位的数。

reset

void reset(size_t x)
{
	size_t i = x / 32, j = x % 32;
	//标记为0左移j位然后取反，直接与等
	_bs[i]  &= (~(1 << j));
}

reset和set很相似，set需要将当前位置设置为1,reset是要将指定数对应的比特位设置为0，所以我们会想到位运算&，还是先找到对应的byte位，然后将1移到对应的数的比特位的位置，因为两个数的&运算的特点是只要有0就是0，两个都为1才是1，所以这里只需要将除对应比特位以外的所有位置变为1然后将对应比特位位置变为0即可。

test

bool test(size_t x)
{
	size_t i = x / 32, j = x % 32;
	//取到j位置的值
	return _bs[i] & (1 << j);
}

test只需要取到对应数的比特位即可。

封装位图的设计

//飞类型模版参数
template<size_t N>
class bit_set
{
public:
	bit_set()
	{
		//一个整数是32个位，所以这里要n个位需要除以32
		//向上取整(如果开60个位60/32=1,那么久少开了一个位）
		_bs.resize(N / 32 + 1);
	}
	//位图的三个核心接口
	//x映射的位标记为1
	void set(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		//需要把这个整形的第j位标记为1
		//bs或等于1左移七位
		_bs[i] |= (1 << j);
	}
	//把之前标记的位标记为0
	void reset(size_t x)
	{
		size_t i = x / 32, j = x % 32;
		//标记为0左移j位然后取反，直接与等
		_bs[i]  &= (~(1 << j));
	}
	//x映射的位置是0返回假，是1返回真
	bool test(size_t x)
	{
		size_t i = x / 32, j = x % 32;
		//取到j位置的值
		return _bs[i] & (1 << j);
	}
private:
	//C/C++中定义的最小单位是一个字节
	//一个int是32个位
	std::vector<int> _bs;
};