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++实现BitMap位图类

关注微信公众号:  笑马编程  后台发送:C++资料,

即可领取C++相关学习资料哦!

 

上一篇:KMP


下一篇:2022/1/18 链表|| 19. 删除链表的倒数第 N 个结点