C++实现BitMap位图类
2022/3/1 22:22:26
本文主要是介绍C++实现BitMap位图类,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
bitmap意为位图,它的每一位用于存放状态,适用于大规模并且不重复的数据,判断某个数据是否存在于位图之中。
之前看过一道腾讯的面试题,有两组数据分别是40亿个QQ号码和60亿个QQ号码,需要查找它们之间重合的数据。如果使用暴力查找一一匹配的话,时间和空间是都吃不消,时间和空间的复杂度很高,很不适用;如果使用分治法分批处理的话,内存可以降低,但是时间复杂度依然很高,也不太适用。如果使用位图的话,就可以很好的解决这个问题,时间空间上都吃的消。
在C++中,整型占32位4个字节。如果使用暴力查找和分治法的话,每个数据都需要占这么多内存,但是如果使用位图,每32个数据只需要占一个整型的内存,在整型的每个位上存储某个数据的是否存在的状态,存在为1,不存在则为0,用第一个整型保存0-31的状态,第二个整型就用来保存32-63的状态,以此类推,直接节省了32倍的内存空间,而查找单个元素的时候时间复杂度只有恐怖的O(1),非常之快!
存储数据的大小应为 size/32+1,num/32作为数据访问下标,num%32作为数据所在的比特位,设置数据需要把该数据对应的比特位置1,删除则置0,查找就判断该数据对应的比特位是否为1。
实现代码如下(BitMap.hpp):
#pragma once #include <assert.h> class BitMap { public: //构造函数 BitMap(const size_t & range) { assert(range >= 0); if (bits != nullptr) { delete[] bits; } count = range; size = range / 32 + 1; bits = new unsigned int[size]; } //析构函数 ~BitMap() { delete[] bits; } //初始化数据,把所有数据置0 void init() { for (int i = 0; i < size; i++) bits[i] = 0; } //增加数据到位图 void add(const size_t & num) { assert(count > num); int index = num / 32; int bit_index = num % 32; bits[index] |= 1 << bit_index; } //删除数据到位图 void remove(const size_t & num){ assert(count > num ); int index = num / 32; int bit_index = num % 32; bits[index] &= ~(1 << bit_index); } //查找数据到位图 bool find(const size_t & num) { assert(count > num); int index = num / 32; int bit_index = num % 32; return (bits[index] >> bit_index) & 1; } //位图相关数据 private: unsigned int* bits=nullptr; int size; int count; };
使用方法如下:
#include "BitMap.hpp" #include <iostream> int main() { BitMap bitmap(1024); bitmap.init(); bitmap.add(432); bitmap.add(1022); std::cout << bitmap.find(1022) << std::endl; std::cout << bitmap.find(432) << std::endl; std::cout << bitmap.find(3) << std::endl; bitmap.remove(1022); std::cout << bitmap.find(1022) << std::endl; getchar(); return 0; }
输出结果:
关注微信公众号: 笑马编程 后台发送:C++资料,
即可领取C++相关学习资料哦!
这篇关于C++实现BitMap位图类的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享