数据结构—位图

1.概述

位图(bitmap)是一种非常常用的结构，在索引、数据压缩等方面有广泛应用。本文介绍了位图的实现方法。

2.自己实现

在位图中，每个元素为“0”或“1”，表示其对应的元素不存在或者存在

 1 //位图
 2 #pragma once
 3 #include<vector>
 4 class BitMap
 5 {
 6 public:
 7     BitMap()
 8         :_size(0)
 9     {}
10     BitMap(size_t size)
11         :_size(0)
12     {
13         //_array开辟多一个空间，如size=36/32=1;需要两块空间才能放下
14         _array.resize((size >> 5) + 1);
15     }
16     bool Set(size_t x)
17     {
18         size_t index = x >> 5;
19         size_t num = x % 32;
20         if (_array[index] & (1 << num))
21         {
22             return false;
23         }
24         _array[index] |= (1 << num);
25         _size++;
26         return true;
27     }
28     bool Reset(size_t x)
29     {
30         size_t index = x >> 5;
31         size_t num = x % 32;
32         if (_array[index] & (1 << num))
33         {
34             _array[index] &= ~(1 << num);
35             _size--;
36             return true;
37         }
38         return false;
39     }
40     size_t size()
41     {
42         return _size;
43     }
44     void Resize(size_t size)
45     {
46         _array.resize(size);
47     }
48     bool Test(size_t x)
49     {
50         size_t index = x >> 5;
51         size_t num= x % 32;
52 
53         return _array[index] & (1 << num);
54     }
55 private:
56     vector<size_t> _array;
57     size_t _size;
58 };
59 void Test1()
60 {
61     BitMap bm(65);
62     bm.Set(1);
63     bm.Set(9);
64     bm.Set(34);
65 
66     cout << "1?" << bm.Test(1) << endl;
67     cout << "2?" << bm.Test(2) << endl;
68     cout << "9?" << bm.Test(9) << endl;
69     cout << "34?" << bm.Test(34) << endl;
70 
71     bm.Reset(33);
72     bm.Reset(4);
73 
74     cout << "1?" << bm.Test(1) << endl;
75     cout << "2?" << bm.Test(2) << endl;
76     cout << "9?" << bm.Test(9) << endl;
77     cout << "34?" << bm.Test(34) << endl;
78 }