社区首页 >专栏 >移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.哈希(3)(布隆过滤器和位图）

移情别恋c++ ദ്ദി˶ｰ̀֊ｰ́ ) ——14.哈希(3)(布隆过滤器和位图）

hope kc

发布于 2024-10-24 00:42:26

14300

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

在 C++ 中，bitset 和 Bloom Filter 是两种重要的数据结构，分别用于处理位操作和概率性数据存储。接下来，我们将详细探讨这两种结构的定义、实现、应用场景及其优缺点。

一、C++ 中的 `bitset`

1. 定义

bitset 是 C++ 标准库中的一个类模板，主要用于管理固定大小的位集合。它能够在一个单一的对象中存储多个二进制位，非常适合用于需要高效存储和快速访问位信息的场景。

2. 基本特性

固定大小：创建 bitset 时需要指定大小，一旦定义，大小不能改变。
位操作：支持与、或、异或等位操作。
高效存储：每个位占用一个比特空间，内存使用效率高。
访问便利：支持下标操作，可以直接通过索引访问某个位。

3. 使用示例

#include <iostream>
#include <bitset>

int main() {
    std::bitset<8> bset; // 创建一个大小为8的bitset

    bset.set(1); // 设置第1位为1
    bset.set(3); // 设置第3位为1
    std::cout << "Bitset: " << bset << std::endl; // 输出：00001010

    bset.flip(2); // 翻转第2位
    std::cout << "After flip: " << bset << std::endl; // 输出：00001110

    std::cout << "Size: " << bset.size() << std::endl; // 输出：8
    std::cout << "Count of set bits: " << bset.count() << std::endl; // 输出：3

    return 0;
}

4. 应用场景

标记数据：适用于需要标记大量布尔值的场景，比如图的遍历。
内存管理：用于管理大量的开关状态。
算法优化：在某些算法中，如快速查找、去重等场景中，能够提高性能。

5. 优缺点

优点：

内存占用少，速度快。
支持丰富的位操作，灵活性强。

缺点：

大小固定，无法动态调整。
仅适用于较小规模的位操作。

6.模拟实现

#include<iostream>
#include<vector>
using namespace std;

namespace zone
{
	template<size_t n>
	class bitset
	{

		bitset()
		{
			bit.resize(N / 32 + 1, 0);//记得要加1；
		}
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			bit[i] |= 1 << j;//要求第j个比特位是1，其余位都是0
			//因为vs是小端存储，1是这样：(低）01 00 00 00（高），而左移并不是向左移动，而是向高位移动！！！！
		}

		void reset(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			bit[i] &= ~(1 << j);//要求第j个比特位是0，其余位都是1，与上文要求相反，可以直接取反
		}


		bool test(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			return bit[i] &(1<<j);//这里很巧妙，如果原位置上是0，那么返回就是false（0），如果不是0，则无论是多少，都返回true（非零）
		}

	private:
		vector<int> bit;
	};



}

二、Bloom Filter