【数据结构】中的位图详解

朴灿烈づ我的快乐病毒、 2022-06-17 10:15 310阅读 0赞

定义：

位图法就是bitmap的缩写。所谓bitmap，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

优缺点：

(1)可读性差

(2)位图存储的元素个数虽然比一般做法多，但是存储的元素大小受限于存储空间的大小。位图存储性质：存储的元素个数等于元素的最大值。比如， 1K 字节内存，能存储 8K 个值大小上限为 8K 的元素。（元素值上限为 8K ，这个局限性很大！）比如，要存储值为 65535 的数，就必须要 65535/8=8K 字节的内存。要就导致了位图法根本不适合存 unsigned int 类型的数（大约需要 2^32/8=5 亿字节的内存）。

(3)位图对有符号类型数据的存储，需要 2 位来表示一个有符号元素。这会让位图能存储的元素个数，元素值大小上限减半。 比如 8K 字节内存空间存储 short 类型数据只能存 8K\*4=32K 个，元素值大小范围为 -32K~32K 。

接口的实现：

#include<iostream>
    using namespace std;
    #include<vector>
    class BitSet
    {
    public:
    	BitSet(size_t range)
    	{
    		_a.resize(range >> 5 + 1, 0);
    	}
    	void Set(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		_a[index] |= (1 << pos);
    	}
    
    	void Reset(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		_a[index] = ~(1 << pos);
    	}
    
    	bool Test(size_t num)
    	{
    		size_t index = num >> 5;
    		size_t pos = num % 32;
    		return _a[index] & (1 << pos);
    	}
    
    
    protected:
    	vector<int> _a;
    };
    
    
    void Test()
    {
    	BitSet s1(-1);
    	s1.Set(1);
    	s1.Set(8);
    	s1.Set(32);
    }
    int main()
    {
    	Test();
    	system("pause");
    	return 0;
    }