位图（c++）

1.位图概念

和哈希一样，都是一个表来记录某个元素的个数或者存在与否；不同的是哈希使用的计算机定义的完整空间向数组的int类型；而位图则是时使用的一个或者多个（不会太多）bit位来表示表示一个数字的个数或者存在与否。

2.位图的实现

第一步定义空间.
位图由于是使用bit位来记录的，但是单个bit位无法开出来，所以我们先可以使用int定义出来空间（即定义一个可以下位图的空间）；

第二步定义类中的接口
构造函数：

输入函数：

删除函数：

查找函数：

解释i和j：
这里删除函数和输入函数的i表示的是：数x在数组的第几个数；
这里删除函数和输入函数的j表示的是：数x在数组的第i个数的第几个bit位；

代码

	//位图template<size_t N>class bitset{public:bitset(){//_bits.resize(N/32+1,0);_bits.resize((N >> 5) + 1, 0);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};

3.应用（解决整形存在或次数问题）

3.1存在问题

在【42，39】中是否存在39，40，41，42；
头文件和上面的一样

template<size_t N>class bitset{public:bitset(){//_bits.resize(N/32+1,0);_bits.resize((N >> 5) + 1, 0);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};

源文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"bitset.h"
int main()
{bit::bitset<100> bs;bs.set(40);bs.set(39);cout << bs.test(38) << endl;cout << bs.test(39) << endl;cout << bs.test(40) << endl;cout << bs.test(41) << endl;cout << bs.test(42) << endl << endl;return 0;
}

3.2次数问题

题目：查找【1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 】中出现一次和两次的数字
对比存在问题需将插入函数和输出函数修改即可修改在下：
头文件：

 template<size_t N>class twobitset{public:void set(size_t x){//00->01//01->10//10->11//11->不变if (_bs1.test(x) == false && _bs2.test(x) == false){_bs2.set(x);}else if (_bs1.test(x) == false && _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}else if (_bs1.test(x) == true && _bs2.test(x) == false){_bs1.set(x);_bs2.set(x);}}void Print(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << "1->" << i << endl;}else if (_bs1.test(i) == true && _bs2.test(i) == false){cout << "2->" << i << endl;}}cout << endl;}private:bitset<N> _bs1;bitset<N> _bs2;};

源文件：

int main()
{int a[] = { 1,4,7,9,44,88,1,4,88,99,78,5,7 ,7,7,7 };bit::twobitset<100> bs;for (auto e : a){bs.set(e);}bs.Print();return 0;
}

5.搜索的方法对比：