Boost C++ 库

……世界上最受推崇、设计最专业的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu，C++ 编码标准

Boost.Bloom - Boost C++ 函数库

介绍

Boost.Bloom 提供了类模板 boost::bloom::filter，它可以配置为实现经典的布隆过滤器以及文献中讨论的各种变体，例如块过滤器、多块过滤器等。

#include <boost/bloom.hpp>
#include <cassert>
#include <iostream>
#include <string>

int main()
{
  // Bloom filter of strings with 5 bits set per insertion
  using filter = boost::bloom::filter<std::string, 5>;

  // create filter with a capacity of 1'000'000 bits
  filter f(1'000'000);

  // insert elements (they can't be erased, Bloom filters are insert-only)
  f.insert("hello");
  f.insert("Boost");

  // elements inserted are always correctly checked as such
  assert(f.may_contain("hello") == true);

  // elements not inserted may incorrectly be identified as such with a
  // false positive rate (FPR) which is a function of the array capacity,
  // the number of bits set per element and generally how the boost::bloom::filter
  // was specified
  if(f.may_contain("bye")) { // likely false
    std::cout << "false positive\n";
  }
  else {
    std::cout << "everything worked as expected\n";
  }
}

支持的不同过滤器变体在编译时作为 boost::bloom::filter 实例化定义的一部分进行指定。Boost.Bloom 的实现重点是性能；可以利用 AVX2、Neon 和 SSE2 等 SIMD 技术来加速操作。

入门

请参阅网站部分，了解如何安装整个 Boost 项目或仅 Boost.Bloom 及其依赖项。

Boost.Bloom 是一个仅头文件库，因此不需要额外的构建阶段。需要 C++11 或更高版本。该库已验证可与 GCC 4.8、Clang 3.9 和 Visual Studio 2015（及更高版本）一起使用。您可以通过编译上面显示的示例程序来检查您的环境是否设置正确。

如果您不熟悉布隆过滤器，请参阅入门；否则，您可以直接跳到教程。

布隆过滤器（以其发明者 Burton Howard Bloom 命名）是一种概率数据结构，其中插入的元素可以 100% 准确地查找，而查找未插入的元素可能会以某种概率失败，这种概率称为过滤器的“**误报率**”或 FPR。这里的权衡是，布隆过滤器占用的空间比传统的非概率容器少得多（通常每个元素约 8-20 位），同时 FPR 可接受地低。过滤器的“**容量**”（以位为单位的大小）越大，产生的 FPR 越低。

通常，当对大型数据集进行精确检索成本高昂和/或无法在主内存中进行时，布隆过滤器可用于防止/缓解查询。

示例：加速数据库的失败请求

布隆过滤器和类似数据结构的一个主要应用是，当昂贵的磁盘/网络访问无法检索给定信息时，防止这些访问。例如，假设我们正在为访问时间为 10 毫秒的数据库开发前端，并且我们知道 50% 的请求不会成功（记录不存在）。插入一个查找时间为 200 纳秒且 FPR 为 0.5% 的布隆过滤器将使系统的平均响应时间从 10 毫秒减少到

(10 + 0.0002) × 50.25% + 0.0002 × 49.75% ≅ 5.03 毫秒，

也就是说，我们获得了 ×1.99 的整体加速。如果数据库包含 10 亿条记录，一个内存中过滤器，例如每个元素 8 位，将占用 0.93 GB，这完全可以实现。

图 1. 使用布隆过滤器改进数据库负访问时间。

应用领域包括 Web 缓存、字典压缩、网络路由和基因组学等。Broder 和 Mitzenmacher 提供了大量用例的评论，重点关注网络。

实现

经典布隆过滤器的实现包括一个包含 m 位的数组，最初设置为零。插入元素 x 归结为伪随机选择 k 个位置（借助 k 个独立的哈希函数）并将它们设置为一。

图 2. 经典布隆过滤器中的插入，其中 k = 6 个不同的哈希函数。插入 x 归结为将位置 10、14、43、58、1 和 39 的位设置为一，如 h₁(x), … , h₆(x) 所示。

要检查元素 y 是否在过滤器中，我们遵循相同的过程，并查看所有选定的位是否都设置为一。在示例图中，有两个未设置的位，这明确表明 y 未插入过滤器中。

图 3. 经典布隆过滤器中的查找。值 y 不在过滤器中，因为位置 20 和 61 的位未设置为一。

当由于其他不相关的插入而导致检查的位都设置为一时，就会发生误报。误报的概率随着我们向过滤器添加更多元素而增加，而对于给定数量 n 的插入元素，容量更大（更大的位数组）的过滤器将具有较低的 FPR。每次操作设置的位数 k 也影响 FPR，尽管以更复杂的方式：当数组稀疏填充时，较高的 k 值会改善（降低）FPR，因为我们有更多机会命中未设置的位；但是，如果 k 非常高，随着新元素的插入，数组将有越来越多的位设置为一，这最终将达到一个点，我们不如一个具有较低 k 从而具有较小比例设置位的过滤器。对于给定值 n 和 m，最佳 k 是\(\lfloor k_{\text{opt}}\rfloor\)或\(\lceil k_{\text{opt}}\rceil\)，其中

\(k_{\text{opt}}=\displaystyle\frac{m\cdot\ln2}{n},\)

最小 FPR 接近\(1/2^{k_{\text{opt}}} \approx 0.6185^{m/n}\)。有关更多详细信息，请参阅关于FPR 估计的附录。

图 4. FPR 与插入元素数量的关系，对于两个 m = 10⁵ 位的过滤器。k = 6（红色）在 n 较小的值下比 k = 2（蓝色）具有更好的（更低）FPR，但随着 n 的增长，最终会退化得更多。虚线显示了通过为每个 n 值选择最佳 k 值而获得的最小可实现 FPR。

经典过滤器的变体

块过滤器

布隆过滤器上的操作涉及访问内存中的 k 个不同位置，对于大型数组，这会导致 k 个 CPU 缓存未命中，并影响操作的性能。经典方法的一种变体称为“**块过滤器**”，它试图通过将所有位设置/检查集中在一个从整个数组中伪随机选择的 b 位小块中来最小化缓存未命中。如果块足够小，它将适合 CPU 缓存行，从而大大减少缓存未命中的数量。

图 5. 块过滤器。根据 h₀(x) 选择一个 b 位的块，所有后续的位设置都限制在那里。

缺点是，对于相同的 n、m 和 k 值，产生的 FPR 比经典过滤器差。直观地说，块过滤器降低了数组中位分布的均匀性，这最终损害了它们的概率性能。

图 6. FPR（对数刻度）与插入元素数量的关系，对于具有相同 k = 4，m = 10⁵ 位的经典过滤器和块过滤器。

这个想法的进一步变体是让操作选择 k 个块，每个块设置 k' 位。这再次会比每次操作 k·k' 位的经典过滤器具有更差的 FPR，但比普通的 k·k' 块过滤器有所改进。

图 7. 多重插入块过滤器。选择 k = 2 个块，每个块中设置 k' = 3 位。

多块过滤器

“**多块过滤器**”通过在连续的 b 大小块序列上进行位设置/检查来进一步推广块过滤器的方法，使得每个块恰好占用一位。这仍然保持了良好的缓存局部性，但相对于块过滤器改进了 FPR，因为设置为一的位在数组中分布更广。

图 8. 多块过滤器。根据 h₀(x) 选择 k' = 4 个连续块的范围，并在每个块中设置一个位为一。

多块过滤器也可以与多重插入结合使用。通常，对于每次操作的位数相同且 n 和 m 值相等的情况，经典布隆过滤器将具有更好（更低）的 FPR，其次是多块过滤器，然后是块过滤器。执行速度大致按相反顺序。当考虑带有多次插入的块/多块过滤器时，可用配置的数量迅速增加，您需要进行一些实验才能在（FPR、容量、速度）权衡空间中找到您喜欢的点。

教程

一个 boost::bloom::filter 可以被视为一个位数组，该数组被划分为“**子数组**”，这些子数组在插入时伪随机选择（基于哈希函数）：每个子数组都传递给一个“**子过滤器**”，该子过滤器根据一些相关策略标记其几个位。

请注意，尽管 boost::bloom::filter 模仿了容器的接口并提供了诸如 insert 之类的操作，但它实际上“**不是**”容器：例如，插入不涉及在数据结构中实际存储元素，而只是根据元素的哈希值在内部数组中设置一些位。

过滤器定义

template<
  typename T, std::size_t K,
  typename Subfilter = block<unsigned char, 1>, std::size_t Stride = 0,
  typename Hash = boost::hash<T>,
  typename Allocator = std::allocator<unsigned char>
>
class filter;

T：插入元素的类型。
K：每次插入标记的子数组数量。
Subfilter：使用的子过滤器类型。
Stride：连续子数组起始位置之间的字节距离。
Hash：T 的哈希函数。
Allocator：unsigned char 的分配器。

`子过滤器`

子过滤器定义了在位数组的选定子数组内设置或检查位的本地策略。它决定了每次操作修改的位数、它们在内存中的排列方式以及内存的访问方式。提供了以下子过滤器：

子过滤器描述优点缺点

子过滤器	描述	优点	缺点
`block<Block, K'>`	在 `Block` 类型的子数组中设置 `K'` 位	访问时间非常快	`Block` 越小，FPR 越差（越高）
`multiblock<Block, K'>`	在 `Block[K']` 子数组的每个元素中设置一个位	对于相同的 `Block` 类型，FPR 比 `block<Block, K'>` 更好（更低）	如果访问子数组时跨越缓存行边界，性能可能会下降
`fast_multiblock32<K'>`	统计上等同于 `multiblock<uint32_t, K'>`，但在编译时启用 SSE2、AVX2 或 Neon 时使用更快的基于 SIMD 的算法	当 SSE2/AVX2/Neon 可用时，始终优先于 `multiblock<uint32_t, K'>`	对于相同的 `K'`，FPR 比 `fast_multiblock64<K'>` 差（更高）
`fast_multiblock64<K'>`	统计上等同于 `multiblock<uint64_t, K'>`，但在编译时启用 AVX2 时使用更快的基于 SIMD 的算法	当 AVX2 可用时，始终优先于 `multiblock<uint64_t, K'>`	对于相同的 `K'`，比 `fast_multiblock32<K'>` 慢

block<Block, K'>

在 Block 类型的子数组中设置 K' 位

访问时间非常快

Block 越小，FPR 越差（越高）

multiblock<Block, K'>

在 Block[K'] 子数组的每个元素中设置一个位

对于相同的 Block 类型，FPR 比 block<Block, K'> 更好（更低）

如果访问子数组时跨越缓存行边界，性能可能会下降

fast_multiblock32<K'>

统计上等同于 multiblock<uint32_t, K'>，但在编译时启用 SSE2、AVX2 或 Neon 时使用更快的基于 SIMD 的算法

当 SSE2/AVX2/Neon 可用时，始终优先于 multiblock<uint32_t, K'>

对于相同的 K'，FPR 比 fast_multiblock64<K'> 差（更高）

fast_multiblock64<K'>

统计上等同于 multiblock<uint64_t, K'>，但在编译时启用 AVX2 时使用更快的基于 SIMD 的算法

当 AVX2 可用时，始终优先于 multiblock<uint64_t, K'>

对于相同的 K'，比 fast_multiblock32<K'> 慢

在上面的表格中，Block 可以是无符号整型（例如 unsigned char、uint32_t、uint64_t），也可以是 2^N 个无符号整型的数组（例如 uint64_t[8]）。通常，Block 越宽，产生的 FPR 越好（越低），但缓存局部性会变差，性能也可能因此受到影响。

请注意，boost::bloom::filter<T, K, subfilter<…, K'>> 每次操作设置/检查的总位数是 K * K'。默认配置 boost::bloom::filter<T, K> = boost::bloom::filter<T, K, block<unsigned char, 1>> 对应于经典布隆过滤器，在所有每次操作位数相同的过滤器中具有最佳（最低）FPR，但也是最慢的：每次设置/检查一个位都会访问一个新的子数组。请参阅基准测试部分以查看 FPR 和性能之间的不同权衡。

一旦选择了子过滤器，如果事先知道将要插入的元素数量，则可以将参数 K' 调整到其最佳值（最小 FPR），如专用部分所述；否则，只要结果 FPR 处于可接受的水平，通常会优先选择较低的 K' 值而不是较高的值，因为它们会更快。

`步幅`

正如我们所见，Subfilter 定义了 boost::bloom::filter 使用的子数组（对于 block<Block, K'> 是 Block，对于 multiblock<Block, K'> 是 Block[K']）：然后访问底层位数组的连续部分并将其视为这些子数组。Stride 参数控制连续子数组起始位置之间的字节距离。

当使用默认值 0 时，步幅会自动设置为子数组的大小，因此它们之间没有重叠。如果 Stride 设置为小于该大小的值，则相邻子数组会相互叠加：Stride 值越小，重叠程度越大，当 Stride 为 1 字节时发生最大重叠。

图 9. 两种不同的 Stride 配置：(a) 非重叠子数组，(b) 重叠子数组。
每个子数组都与相同颜色的步幅相关联。

事实证明，重叠相对于非重叠情况改进（降低）了生成的 FPR，其权衡是子数组可能未在内存中对齐，这可能会对性能产生负面影响。

`哈希`

与其他需要每次操作多个哈希函数的布隆过滤器实现不同，boost::bloom::filter 只使用一个哈希函数。默认情况下，使用 Boost.ContainerHash。如果您需要为自己的类型扩展 boost::hash，请查阅此库的专用部分。

当提供的哈希函数质量足够高时，它会按原样使用；否则，会对哈希值应用位混合后处理以改善其统计特性，从而使生成的 FPR 接近其理论极限。哈希函数通过 boost::hash_is_avalanching 特性确定为高质量（更精确地说，具有所谓的“**雪崩**”特性）。

容量

过滤器内部数组的大小在构造时指定

using filter = boost::bloom::filter<std::string, 8>;
filter f(1'000'000); // array of 1'000'000 bits
std::cout << f.capacity(); // >= 1'000'000

请注意，boost::bloom::filter 默认构造函数指定容量为零，这通常不会有太大用处——分配的数组为空。

我们可以不直接指定数组的容量，而是让库根据我们计划插入的元素数量和所需的 FPR 来计算它

// we'll insert 100'000 elements and want a FPR ~ 1%
filter f(100'000, 0.01);

// this is equivalent
filter f2(filter::capacity_for(100'000, 0.01));

当指定的 FPR 非常小，导致容量过大而无法容纳在内存中时，请务必小心。

// resulting capacity ~ 1.4E12, out of memory std::bad_alloc is thrown
filter f3(100'000, 1E-50);

一旦过滤器被构造，它的数组就被固定了（例如，它不会随着元素的插入而动态增长）。唯一改变它的方法是通过从不同的过滤器赋值/交换，或者使用 reset。

f.reset(2'000'000); // change to 2'000'000 bits and clears the filter
f.reset(100'000, 0.005); // equivalent to reset(filter::capacity_for(100'000, 0.005));
f.reset(); // null array (capacity == 0)

插入和查找

插入与传统容器的方式大致相同。

f.insert("hello");
f.insert(data.begin(), data.end());

当然，在此上下文中，“插入”不涉及将任何元素实际存储到过滤器中，而是根据这些元素的哈希值在内部数组中设置位。查找过程如下：

bool b1 = f.may_contain("hello"); // b1 is true since we actually inserted "hello"
bool b2 = f.may_contain("bye"); // b2 is most likely false

顾名思义，may_contain 即使在元素之前未插入的情况下也可能返回 true，也就是说，它可能产生误报——这是概率数据结构的本质。fpr_for 提供了误报率的估计。

// we have inserted 100 elements so far, what's our FPR?
std::cout<< filter::fpr_for(100, f.capacity());

请注意，在示例中我们外部提供了数字 100：boost::bloom::filter 不会跟踪已插入的元素数量——换句话说，它没有 size 操作。

一旦插入，就无法从过滤器中删除特定元素。我们只能完全清除过滤器。

f.clear(); // sets all the bits in the array to zero

过滤器组合

boost::bloom::filter 可以通过对其数组的位执行 OR 逻辑操作来组合。

filter f2 = ...;
...
f |= f2; // f and f2 must have exactly the same capacity

结果等同于一个“包含”f 和 f2 元素集合并集的过滤器。另一方面，AND 组合会产生一个包含元素“**交集**”的过滤器。

filter f3 = ...;
...
f &= f3; // f and f3 must have exactly the same capacity

对于 AND 组合，请注意，如果过滤器是从头开始仅插入公共元素而构建的，则生成的 FPR 通常会比那样差（更高）——在这种情况下不要相信 fpr_for。

直接访问数组

可以通过 array 成员函数直接访问位数组的内容，这可以用于过滤器序列化。

filter f1 = ...;
...

// save filter
std::ofstream out("filter.bin", std::ios::binary);
std::size_t c1=f1.capacity();
out.write(reinterpret_cast<const char*>(&c1), sizeof(c1)); // save capacity (bits)
boost::span<const unsigned char> s1 = f1.array();
out.write(reinterpret_cast<const char*>(s1.data()), s1.size()); // save array
out.close();

// load filter
filter f2;
std::ifstream in("filter.bin", std::ios::binary);
std::size_t c2;
in.read(reinterpret_cast<char*>(&c2), sizeof(c2));
f2.reset(c2); // restore capacity
boost::span<unsigned char> s2 = f2.array();
in.read(reinterpret_cast<char*>(s2.data()), s2.size()); // load array
in.close();

请注意，array() 是 unsigned char 的一个 span，而容量是以位为单位测量的，所以 array.size() 是 capacity() / CHAR_BIT。如果您在保存它的计算机之外的计算机上加载序列化过滤器，请注意两端的 CPU 架构必须具有相同的字节序才能使重建工作。

调试

Visual Studio Natvis

将 boost_bloom.natvis 可视化器添加到您的项目，以便用户友好地检查 boost::bloom::filter。

图 10. 使用 boost_bloom.natvis 查看 boost::bloom::filter。

GDB Pretty-Printer

boost::bloom::filter 附带一个专用的 pretty-printer，用于在使用 GDB 调试时进行可视化检查。

(gdb) print f
$1 = boost::bloom::filter with {capacity = 2000, data = 0x6da840, size = 250} = {[0] = 0 '\000',
  [1] = 0 '\000', [2] = 0 '\000', [3] = 0 '\000', [4] = 0 '\000', [5] = 1 '\001'...}

(gdb) # boost::bloom::filter does not have an operator[]. The following expression
(gdb) # is used in place of print f.array()[30]
(gdb) print f[30]
$2 = 128 '\200'

请记住在 GDB 中启用 pretty-printing（通常是一次性设置）

(gdb) set print pretty on

如果编译的二进制格式是 ELF 且未定义宏 BOOST_ALL_NO_EMBEDDED_GDB_SCRIPTS，则 pretty-printer 会自动嵌入到程序中；通过此命令（或默认情况下将其添加到您的 .gdbinit 配置文件中）可以为特定的 GDB 会话启用嵌入式 pretty-printer。

(gdb) add-auto-load-safe-path <path-to-executable>

除了使用嵌入式 pretty-printer 之外，您还可以显式加载 boost_bloom_printers.py 脚本。

(gdb) source <path-to-boost>/libs/bloom/extra/boost_bloom_printers.py

选择过滤器配置

Boost.Bloom 提供了大量的编译时和运行时配置选项，因此可能难以做出选择。如果您正在追求给定的 FPR 或心中有特定的容量，并且希望选择最合适的过滤器类型，以下图表可能会派上用场。

图 11. 不同过滤器类型的 FPR 与 c 关系图。

该图绘制了几个 boost::bloom::filter 的 FPR 与 c（容量 / 插入元素数量）的关系，其中 K 已设置为其最佳值（最小 FPR），如以下表格所示。

	c = 容量 / 插入元素数量
	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
`filter<T,1,block<uint32_t,K>>`	3	3	3	4	4	5	5	5	5	5	5	5	6	6	7	7	7	7	7	7	7
`filter<T,1,block<uint32_t,K>,1>`	2	3	4	4	4	4	5	5	5	6	6	6	6	6	6	6	7	7	7	7	7
`filter<T,1,block<uint64_t,K>>`	2	3	4	4	5	5	5	5	5	6	6	6	6	6	7	7	7	7	7	7	7
`filter<T,1,block<uint64_t,K>,1>`	2	3	4	4	4	5	6	6	6	7	7	7	7	7	8	8	8	8	8	9	9
`filter<T,1,multiblock<uint32_t,K>>`	3	3	4	5	6	6	8	8	8	8	9	9	9	10	13	13	15	15	15	16	16
`filter<T,1,block<uint64_t[8],K>>`	4	4	4	5	5	6	7	7	7	8	8	9	9	10	10	11	12	12	12	12	12
`filter<T,1,multiblock<uint32_t,K>,1>`	3	3	4	5	6	6	7	7	8	8	9	9	10	10	12	12	14	14	14	14	15
`filter<T,1,block<uint64_t[8],K>,1>`	3	3	4	5	6	6	7	7	7	8	8	8	10	11	11	12	12	12	12	12	13
`filter<T,1,multiblock<uint64_t,K>>`	4	4	5	5	6	6	6	7	8	8	10	10	12	13	14	15	15	15	15	16	17
`filter<T,1,multiblock<uint64_t,K>,1>`	3	3	4	5	5	6	6	7	9	10	10	11	11	12	12	13	13	13	15	16	16
`filter<T,K>`	3	4	4	5	5	6	6	8	8	9	10	11	12	13	13	13	14	16	16	16	17

我们来看看如何通过一个例子来使用它。假设我们计划插入 10M 个元素，并希望将 FPR 保持在 10⁻⁴。图表给了我们五个不同的 c 值（数组容量除以元素数量，在本例中为 10M）。

filter<T, K> → c ≅ 每个元素 19 位
filter<T, 1, multiblock<uint64_t, K>, 1> → c ≅ 每个元素 20 位
filter<T, 1, multiblock<uint64_t, K>> → c ≅ 每个元素 21 位
filter<T, 1, block<uint64_t[8], K>, 1> → c ≅ 每个元素 21 位
filter<T, 1, multiblock<uint32_t, K>, 1> → c ≅ 每个元素 21.5 位
filter<T, 1, block<uint64_t[8], K>> → c ≅ 每个元素 22 位
filter<T, 1, multiblock<uint32_t, K>> → c ≅ 每个元素 23 位

这些选项在空间使用和性能方面有不同的权衡。如果我们选择 filter<T, 1, multiblock<uint32_t, K>, 1> 作为折衷（或者更好的是 filter<T, 1, fast_multiblock32<K>, 1>），剩下的唯一一步就是查阅 c = 21 或 22 时表格中的 K 值，然后我们得到最终配置。

using my_filter=filter<std::string, 1, fast_multiblock32<14>, 1>;

生成的过滤器可以通过以下任一方式构造

// 1) calculate the capacity from the value of c we got from the chart
my_filter f((std::size_t)(10'000'000 * 21.5));

// 2) let the library calculate the capacity from n and target fpr
// expect some deviation from the capacity in 1)
my_filter f(10'000'000, 1E-4);

// 3) equivalent to 2)
my_filter f(my_filter::capacity_for(10'000'000, 1E-4));

基准测试

（更多结果请参见专用仓库。）

这些表格显示了在插入 1000 万个元素后，boost::bloom::filter<int, ...> 的几种配置的误报率和每次操作的执行时间（纳秒）。

ins.：插入。
succ. lkp.：成功查找（元素在过滤器中）。
uns. lkp.：不成功查找（元素不在过滤器中，尽管查找可能返回 true）。

过滤器以容量 c * N（位）构造，因此 c 是每个元素使用的位数。对于 c 和给定过滤器配置的每个组合，我们都选择了 K 的最佳值（产生最小 FPR 的值）。使用标准发布模式设置；Visual Studio 构建（/arch:AVX2）和 GCC/Clang 构建（-march=native）指示 AVX2，这使得 fast_multiblock32 和 fast_multiblock64 使用其 AVX2 变体。

GCC 14, x64

	`filter<int,K>`					`filter<int,1,block<uint64_t,K>>`					`filter<int,1,block<uint64_t,K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	6	2.1519	14.04	15.82	20.84	4	3.3467	5.82	6.50	6.54	5	3.0383	5.46	6.13	6.15
12	9	0.3180	47.65	52.28	27.38	5	1.0300	10.07	10.98	10.98	6	0.8268	11.52	12.52	12.49
16	11	0.0469	83.25	99.75	34.96	6	0.4034	18.34	18.38	18.39	7	0.2883	18.97	19.08	19.08
20	14	0.0065	125.12	135.16	39.56	7	0.1887	21.87	21.99	21.99	8	0.1194	22.85	25.21	25.17
	`filter<int,1,multiblock<uint64_t,K>>`					`filter<int,1,multiblock<uint64_t,K>,1>`					`filter<int,1,fast_multiblock32<K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4510	6.42	7.10	7.12	5	2.3157	7.23	8.98	8.96	5	2.7361	5.90	5.67	5.70
12	8	0.4207	13.45	17.14	17.16	8	0.3724	16.49	20.61	20.65	8	0.5415	7.63	7.92	7.97
16	11	0.0764	29.25	30.26	30.26	11	0.0642	34.90	35.52	35.29	11	0.1179	19.11	20.64	14.95
20	13	0.0150	38.40	39.18	39.20	14	0.0122	40.68	50.85	50.24	13	0.0275	22.00	23.66	16.68
	`filter<int,1,fast_multiblock32<K>,1>`					`filter<int,1,fast_multiblock64<K>>`					`filter<int,1,fast_multiblock64<K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4788	4.24	3.92	3.96	5	2.4546	5.59	5.86	5.89	5	2.3234	5.97	6.01	5.92
12	8	0.4394	8.19	8.03	8.03	8	0.4210	8.75	9.69	9.74	8	0.3754	11.13	12.23	12.20
16	11	0.0865	18.60	20.34	14.59	11	0.0781	24.65	25.86	21.31	11	0.0642	23.72	26.12	21.53
20	13	0.0178	21.80	23.56	16.42	13	0.0160	31.93	36.25	24.75	14	0.0110	31.64	36.52	25.04
	`filter<int,1,block<uint64_t[8],K>>`					`filter<int,1,block<uint64_t[8],K>,1>`					`filter<int,1,multiblock<uint64_t[8],K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.3292	7.58	8.62	15.62	6	2.2986	13.07	10.80	20.72	7	2.3389	15.28	15.27	15.29
12	7	0.4140	17.22	18.44	18.84	7	0.3845	22.19	21.28	20.79	10	0.3468	26.63	28.35	28.33
16	9	0.0852	27.39	27.86	21.79	10	0.0714	35.48	33.83	26.65	11	0.0493	45.00	49.14	49.05
20	12	0.0196	41.61	42.34	24.90	12	0.0152	50.90	50.31	28.79	15	0.0076	74.41	73.92	73.83

Clang 18, x64

	`filter<int,K>`					`filter<int,1,block<uint64_t,K>>`					`filter<int,1,block<uint64_t,K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	6	2.1519	13.57	14.12	20.85	4	3.3467	5.65	5.67	5.63	5	3.0383	5.42	6.03	5.98
12	9	0.3180	47.85	49.49	26.49	5	1.0300	11.03	10.97	10.98	6	0.8268	10.64	11.56	11.58
16	11	0.0469	83.54	85.35	31.09	6	0.4034	17.89	17.95	17.96	7	0.2883	17.23	19.07	19.08
20	14	0.0065	120.39	119.09	36.47	7	0.1887	21.98	21.72	21.72	8	0.1194	14.71	15.30	15.26
	`filter<int,1,multiblock<uint64_t,K>>`					`filter<int,1,multiblock<uint64_t,K>,1>`					`filter<int,1,fast_multiblock32<K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4510	4.32	5.17	5.21	5	2.3157	4.10	4.63	4.66	5	2.7361	3.56	3.45	3.44
12	8	0.4207	8.83	10.55	10.56	8	0.3724	9.91	12.46	12.52	8	0.5415	7.85	7.54	7.54
16	11	0.0764	19.62	22.72	22.75	11	0.0642	19.05	22.93	22.92	11	0.1179	15.19	16.32	12.45
20	13	0.0150	23.87	29.73	29.79	14	0.0122	24.92	30.80	30.80	13	0.0275	17.36	18.34	13.99
	`filter<int,1,fast_multiblock32<K>,1>`					`filter<int,1,fast_multiblock64<K>>`					`filter<int,1,fast_multiblock64<K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4788	3.72	3.38	3.36	5	2.4546	4.76	5.07	5.02	5	2.3234	5.27	5.37	5.25
12	8	0.4394	7.60	7.58	7.56	8	0.4210	8.66	9.24	9.27	8	0.3754	10.28	11.52	11.58
16	11	0.0865	14.43	16.09	11.92	11	0.0781	20.19	21.55	17.22	11	0.0642	18.83	21.05	16.85
20	13	0.0178	16.64	18.26	13.45	13	0.0160	25.12	29.48	20.08	14	0.0110	25.37	26.90	19.62
	`filter<int,1,block<uint64_t[8],K>>`					`filter<int,1,block<uint64_t[8],K>,1>`					`filter<int,1,multiblock<uint64_t[8],K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.3292	7.67	7.97	15.08	6	2.2986	13.91	10.27	19.76	7	2.3389	13.83	13.87	13.86
12	7	0.4140	17.06	15.61	17.52	7	0.3845	25.80	21.21	20.63	10	0.3468	31.17	32.58	32.61
16	9	0.0852	28.89	26.74	21.75	10	0.0714	36.21	32.66	24.97	11	0.0493	45.58	48.10	47.96
20	12	0.0196	43.30	35.81	24.25	12	0.0152	52.38	40.08	26.46	15	0.0076	78.06	72.34	72.55

Clang 15, ARM64

	`filter<int,K>`					`filter<int,1,block<uint64_t,K>>`					`filter<int,1,block<uint64_t,K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	6	2.1519	7.75	6.16	12.93	4	3.3467	2.05	1.99	2.00	5	3.0383	2.13	2.02	2.04
12	9	0.3180	13.15	11.04	16.16	5	1.0300	3.50	3.47	3.49	6	0.8268	3.22	3.16	3.09
16	11	0.0469	30.88	24.03	18.38	6	0.4034	6.66	6.31	6.56	7	0.2883	6.92	5.98	5.87
20	14	0.0065	53.83	40.29	20.91	7	0.1887	9.13	7.94	7.86	8	0.1194	7.69	6.46	6.74
	`filter<int,1,multiblock<uint64_t,K>>`					`filter<int,1,multiblock<uint64_t,K>,1>`					`filter<int,1,fast_multiblock32<K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4510	2.70	2.48	2.56	5	2.3157	2.70	2.59	2.58	5	2.7361	2.38	2.49	2.50
12	8	0.4207	3.76	4.62	4.28	8	0.3724	4.31	4.64	4.53	8	0.5415	2.75	3.44	3.49
16	11	0.0764	10.95	9.92	9.78	11	0.0642	10.68	9.53	9.51	11	0.1179	8.69	8.41	5.77
20	13	0.0150	15.22	12.68	12.37	14	0.0122	14.96	12.90	12.72	13	0.0275	10.43	11.08	6.61
	`filter<int,1,fast_multiblock32<K>,1>`					`filter<int,1,fast_multiblock64<K>>`					`filter<int,1,fast_multiblock64<K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4788	2.39	2.51	2.54	5	2.4510	2.72	2.51	2.55	5	2.3157	2.71	2.57	2.59
12	8	0.4394	2.94	3.10	3.03	8	0.4207	3.70	3.88	3.88	8	0.3724	4.26	4.68	4.39
16	11	0.0865	8.29	8.49	5.82	11	0.0764	10.94	9.88	9.73	11	0.0642	11.28	9.95	9.82
20	13	0.0178	10.41	10.88	6.60	13	0.0150	16.00	12.90	13.27	14	0.0122	15.77	13.47	13.55
	`filter<int,1,block<uint64_t[8],K>>`					`filter<int,1,block<uint64_t[8],K>,1>`					`filter<int,1,multiblock<uint64_t[8],K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.3292	4.64	4.30	11.29	6	2.2986	8.72	4.92	13.50	7	2.3389	8.87	6.65	6.71
12	7	0.4140	9.37	8.45	13.03	7	0.3845	13.33	7.80	12.91	10	0.3468	14.57	12.25	12.16
16	9	0.0852	16.42	13.68	14.25	10	0.0714	21.98	15.88	16.60	11	0.0493	26.05	21.96	23.13
20	12	0.0196	23.13	17.52	15.45	12	0.0152	28.91	22.21	17.26	15	0.0076	49.71	38.19	39.07

VS 2022, x64

	`filter<int,K>`					`filter<int,1,block<uint64_t,K>>`					`filter<int,1,block<uint64_t,K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	6	2.1519	11.10	11.87	15.76	4	3.3467	4.21	3.84	3.79	5	3.0383	4.72	4.58	4.52
12	9	0.3180	18.05	18.04	16.58	5	1.0300	6.22	5.70	5.67	6	0.8268	7.09	6.91	6.79
16	11	0.0469	68.24	79.45	25.94	6	0.4034	16.32	13.98	13.97	7	0.2883	16.42	16.00	16.02
20	14	0.0065	102.36	117.69	31.08	7	0.1887	20.87	19.33	19.26	8	0.1194	20.70	22.48	22.55
	`filter<int,1,multiblock<uint64_t,K>>`					`filter<int,1,multiblock<uint64_t,K>,1>`					`filter<int,1,fast_multiblock32<K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4510	6.10	4.69	4.60	5	2.3157	8.57	5.05	4.97	5	2.7361	3.17	2.40	2.31
12	8	0.4207	10.18	8.79	8.59	8	0.3724	14.85	9.56	9.29	8	0.5415	4.81	4.92	4.34
16	11	0.0764	26.70	23.24	23.54	11	0.0642	29.69	27.85	27.90	11	0.1179	14.92	16.50	11.60
20	13	0.0150	36.05	34.93	35.15	14	0.0122	39.81	38.16	38.14	13	0.0275	16.37	17.89	12.37
	`filter<int,1,fast_multiblock32<K>,1>`					`filter<int,1,fast_multiblock64<K>>`					`filter<int,1,fast_multiblock64<K>,1>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.4788	3.18	2.26	2.16	5	2.4546	4.08	3.48	3.43	5	2.3234	4.17	3.40	3.33
12	8	0.4394	5.21	5.56	4.70	8	0.4210	6.73	6.13	5.67	8	0.3754	7.65	6.64	5.69
16	11	0.0865	15.06	15.45	10.99	11	0.0781	23.17	18.49	15.69	11	0.0642	20.82	19.11	16.18
20	13	0.0178	16.74	17.88	12.32	13	0.0160	28.66	26.92	18.97	14	0.0110	28.58	26.87	19.11
	`filter<int,1,block<uint64_t[8],K>>`					`filter<int,1,block<uint64_t[8],K>,1>`					`filter<int,1,multiblock<uint64_t[8],K>>`
c	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.	K	FPR [%]	ins.	succ. lkp.	uns. lkp.
8	5	2.3292	7.72	7.43	11.95	6	2.2986	10.68	9.72	14.95	7	2.3389	11.52	10.03	10.06
12	7	0.4140	11.37	12.06	13.71	7	0.3845	14.52	13.96	14.46	10	0.3468	15.45	14.39	14.26
16	9	0.0852	25.26	25.52	19.68	10	0.0714	33.28	32.53	20.02	11	0.0493	41.18	40.24	40.31
20	12	0.0196	35.58	34.62	22.93	12	0.0152	42.87	41.63	22.03	15	0.0076	68.99	64.79	64.87

参考

`<boost/bloom.hpp>`

包含此参考中列出的所有其他头文件的便利头文件。

`<boost/bloom/filter.hpp>`

定义 boost::bloom::filter 和相关函数。

namespace boost{
namespace bloom{

template<
  typename T, std::size_t K,
  typename Subfilter = block<unsigned char, 1>, std::size_t Stride = 0,
  typename Hash = boost::hash<T>,
  typename Allocator = std::allocator<unsigned char>
>
class filter;

template<
  typename T, std::size_t K, typename SF, std::size_t S, typename H, typename A
>
bool operator==(
  const filter<T, K, SF, S, H, A>& x, const filter<T, K, SF, S, H, A>& y);

template<
  typename T, std::size_t K, typename SF, std::size_t S, typename H, typename A
>
bool operator!=(
  const filter<T, K, SF, S, H, A>& x, const filter<T, K, SF, S, H, A>& y);

template<
  typename T, std::size_t K, typename SF, std::size_t S, typename H, typename A
>
void swap(filter<T, K, SF, S, H, A>& x, filter<T, K, SF, S, H, A>& y)
  noexcept(noexcept(x.swap(y)));

} // namespace bloom
} // namespace boost

类模板 `filter`

boost::bloom::filter — 一种支持元素插入和“**概率性**”查找的数据结构，其中可以高度自信地确定元素在过滤器中，或者绝对确定不在过滤器中。查找错误地将不存在的元素分类为存在的概率称为过滤器的“**误报率**”（FPR）。

boost::bloom::filter 维护一个包含 m 位的内部数组，其中 m 是过滤器的“**容量**”。与传统容器不同，插入元素 x 不会在过滤器中存储 x 的副本，而是将数组中固定数量的位设置为一，这些位的位置是根据 x 的哈希值伪随机生成的。查找 y 只是检查与 y 相关联的所有位是否实际设置。

对于给定的过滤器，FPR 随着新元素的插入而增加。
对于给定数量的插入元素，容量更高的过滤器具有较低的 FPR。

按照惯例，如果过滤器的容量为零或内部数组中的所有位都设置为零，则称过滤器是“**空的**”。

提要

// #include <boost/bloom/filter.hpp>

namespace boost{
namespace bloom{

template<
  typename T, std::size_t K,
  typename Subfilter = block<unsigned char, 1>, std::size_t Stride = 0,
  typename Hash = boost::hash<T>,
  typename Allocator = std::allocator<unsigned char>
>
class filter
{
public:
  // types and constants
  using value_type                         = T;
  static constexpr std::size_t k           = K;
  using subfilter                          = Subfilter;
  static constexpr std::size_t stride      = see below;
  using hasher                             = Hash;
  using allocator_type                     = Allocator;
  using size_type                          = std::size_t;
  using difference_type                    = std::ptrdiff_t;
  using reference                          = value_type&;
  using const_reference                    = const value_type&;
  using pointer                            = value_type*;
  using const_pointer                      = const value_type*;

  // construct/copy/destroy
  filter();
  explicit filter(
    size_type m, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());
  filter(
    size_type n, double fpr, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());
  template<typename InputIterator>
    filter(
      InputIterator first, InputIterator last,
      size_type m, const hasher& h = hasher(),
      const allocator_type& al = allocator_type());
  template<typename InputIterator>
    filter(
      InputIterator first, InputIterator last,
      size_type n, double fpr, const hasher& h = hasher(),
      const allocator_type& al = allocator_type());
  filter(const filter& x);
  filter(filter&& x);
  template<typename InputIterator>
    filter(
      InputIterator first, InputIterator last,
      size_type m, const allocator_type& al);
  template<typename InputIterator>
    filter(
      InputIterator first, InputIterator last,
      size_type n, double fpr, const allocator_type& al);
  explicit filter(const allocator_type& al);
  filter(const filter& x, const allocator_type& al);
  filter(filter&& x, const allocator_type& al);
  filter(
    std::initializer_list<value_type> il,
    size_type m, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());
  filter(
    std::initializer_list<value_type> il,
    size_type n, double fpr, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());
  filter(size_type m, const allocator_type& al);
  filter(size_type n, double fpr, const allocator_type& al);
  filter(
    std::initializer_list<value_type> il,
    size_type m, const allocator_type& al);
  filter(
    std::initializer_list<value_type> il,
    size_type n, double fpr, const allocator_type& al);
  ~filter();
  filter& operator=(const filter& x);
  filter& operator=(filter&& x)
    noexcept(
	  std::allocator_traits<Allocator>::is_always_equal::value ||
      std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);
  filter& operator=(std::initializer_list<value_type> il);
  allocator_type get_allocator() const noexcept;

  // capacity
  size_type capacity() const noexcept;
  static size_type capacity_for(size_type n, double fpr);
  static double fpr_for(size_type n,size_type m)

  // data access
  boost::span<unsigned char>       array() noexcept;
  boost::span<const unsigned char> array() const noexcept;

  // modifiers
  void insert(const value_type& x);
  template<typename U>
    void insert(const U& x);
  template<typename InputIterator>
    void insert(InputIterator first, InputIterator last);
  void insert(std::initializer_list<value_type> il);

  void swap(filter& x)
    noexcept(std::allocator_traits<Allocator>::is_always_equal::value ||
             std::allocator_traits<Allocator>::propagate_on_container_swap::value);
  void clear() noexcept;
  void reset(size_type m = 0);
  void reset(size_type n, double fpr);

  filter& operator&=(const filter& x);
  filter& operator|=(const filter& x);

  // observers
  hasher hash_function() const;

  // lookup
  bool may_contain(const value_type& x) const;
  template<typename U>
    bool may_contain(const U& x) const;
};

} // namespace bloom
} // namespace boost

描述

模板参数

T

插入到过滤器中的元素的 cv-非限定对象类型。

K

每次插入或查找时，关联子过滤器被调用的次数。K 必须大于零。

子过滤器

一种子过滤器类型，提供将位设置/检查到过滤器内部数组的精确算法。子过滤器在宽度为 used-value-size<Subfilter> 的 K 个伪随机选择的数组部分（“**子数组**”）上每次操作调用 K 次。

步幅

连续子数组起始位置之间的字节距离。如果 Stride 指定为零，则实际距离自动选择为 used-value-size<Subfilter>（非重叠子数组）。否则，Stride 不得大于 used-value-size<Subfilter>。

哈希

一个关于 T 的哈希类型。

Allocator

一个 Allocator，其值类型为 unsigned char。

内部数组的分配和释放通过提供的分配器的内部副本完成。如果 stride 是 a = alignof(Subfilter::value_type) 的倍数，则数组按 max(64, a) 进行字节对齐。

如果 boost::hash_is_avalanching<Hash>::value 为 true 且 sizeof(std::size_t) >= 8，则哈希函数按原样使用；否则，会添加位混合后处理阶段，以牺牲额外的计算成本为代价提高哈希质量。

异常安全保证

除非明确注明，所有非 const 成员函数和以非 const 引用方式接受 boost::bloom::filter 的相关函数都提供基本异常保证，而所有 const 成员函数和以 const 引用方式接受 boost::bloom::filter 的相关函数都提供强异常保证。

除非明确注明，否则没有任何操作会抛出异常，除非该异常是由过滤器的 Hash 或 Allocator 对象（如果有）抛出的。

类型和常量

static constexpr std::size_t stride;

如果 Stride 参数被指定为非零，则等于 Stride。否则，等于 used-value-size<subfilter>。

构造函数

默认构造函数

filter();

使用 hasher() 作为哈希函数，allocator_type() 作为分配器构造一个空过滤器。

前置条件	`hasher` 和 `allocator_type` 必须是 DefaultConstructible。
后置条件	`capacity() == 0`.

容量构造函数

explicit filter(
  size_type m, const hasher& h = hasher(),
  const allocator_type& al = allocator_type());
filter(
  size_type n, double fpr, const hasher& h = hasher(),
  const allocator_type& al = allocator_type());

分别使用 h 和 al 的副本作为哈希函数和分配器构造一个空过滤器。

前置条件	`fpr` 介于 0.0 和 1.0 之间。
后置条件	如果 `m == 0`，则 `capacity() == 0`，否则 `capacity() >= m`（第一个重载）。 `capacity() == capacity_for(n, fpr)`（第二个重载）。

迭代器范围构造函数

template<typename InputIterator>
  filter(
    InputIterator first, InputIterator last,
    size_type m, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());
template<typename InputIterator>
  filter(
    InputIterator first, InputIterator last,
    size_type n, double fpr, const hasher& h = hasher(),
    const allocator_type& al = allocator_type());

使用 h 和 al 的副本作为哈希函数和分配器构造一个过滤器，并从 [first, last) 插入值。

前置条件	`InputIterator` 是一个引用 `value_type` 的 LegacyInputIterator。 `[first, last)` 是一个有效范围。 `fpr` 介于 0.0 和 1.0 之间。
后置条件	如果 `m == 0`，则 `capacity() == 0`，否则 `capacity() >= m`（第一个重载）。 `capacity() == capacity_for(n, fpr)`（第二个重载）。对于 `[first, last)` 中的所有值 `x`，`may_contain(x)`。

复制构造函数

filter(const filter& x);

构造一个过滤器，使用 x 的内部数组的副本、x.hash_function() 和 std::allocator_traits<Allocator>::select_on_container_copy_construction(x.get_allocator())。

后置条件	`*this == x`.

移动构造函数

filter(filter&& x);

构造一个过滤器，将 x 的内部数组传输到 *this，并使用从 x 的哈希函数和分配器移动构造的哈希函数和分配器。

后置条件	`x.capacity() == 0`.

带分配器的迭代器范围构造函数

template<typename InputIterator>
  filter(
    InputIterator first, InputIterator last,
    size_type m, const allocator_type& al);
template<typename InputIterator>
  filter(
    InputIterator first, InputIterator last,
    size_type n, double fpr, const allocator_type& al);

等同于 filter(first, last, m, hasher(), al)（第一个重载）或 filter(first, last, n, fpr, hasher(), al)（第二个重载）。

分配器构造函数

explicit filter(const allocator_type& al);

使用 hasher() 作为哈希函数，并使用 al 的副本作为分配器构造一个空过滤器。

前置条件	`hasher` 必须是 DefaultConstructible。
后置条件	`capacity() == 0`.

带分配器的复制构造函数

filter(const filter& x, const allocator_type& al);

构造一个过滤器，使用 x 的内部数组的副本、x.hash_function() 和 al。

后置条件	`*this == x`.

带分配器的移动构造函数

filter(filter&& x, const allocator_type& al);

如果 al == x.get_allocator()，则构造一个过滤器，将 x 的内部数组转移到 *this；否则，使用一个容量为 x.capacity() 的新内部数组并复制 x 的内部数组的值。新过滤器的哈希函数是从 x 的哈希函数移动构造的，分配器是 al 的副本。

后置条件	`x.capacity() == 0`.

初始化列表构造函数

filter(
  std::initializer_list<value_type> il,
  size_type m, const hasher& h = hasher(),
  const allocator_type& al = allocator_type());
filter(
  std::initializer_list<value_type> il,
  size_type n, double fpr, const hasher& h = hasher(),
  const allocator_type& al = allocator_type());

等同于 filter(il.begin(), il.end(), m, h, al)（第一个重载）或 filter(il.begin(), il.end(), n, fpr, h, al)（第二个重载）。

带分配器的容量构造函数

filter(size_type m, const allocator_type& al);
filter(size_type n, double fpr, const allocator_type& al);

等同于 filter(m, hasher(), al)（第一个重载）或 filter(n, fpr, hasher(), al)（第二个重载）。

带分配器的初始化列表构造函数

filter(
  std::initializer_list<value_type> il,
  size_type m, const allocator_type& al);
filter(
  std::initializer_list<value_type> il,
  size_type n, double fpr, const allocator_type& al);

等同于 filter(il, m, hasher(), al)（第一个重载）或 filter(il, n, fpr, hasher(), al)（第二个重载）。

析构函数

~filter();

释放内部数组并销毁内部哈希函数和分配器。

赋值

复制赋值

filter& operator=(const filter& x);

令 pocca 为 std::allocator_traits<Allocator>::propagate_on_container_copy_assignment::value。如果 pocca 为真，则将内部分配器 al 替换为 x.get_allocator() 的副本。如果 capacity() != x.capacity() 或 pocca && al != x.get_allocator()，则将内部数组替换为容量为 x.capacity() 的新数组。复制 x 内部数组的值。将内部哈希函数替换为 x.hash_function() 的副本。

前置条件	如果 `pocca`，则 `Allocator` 是 nothrow CopyAssignable。 `hasher` 是 nothrow Swappable。
后置条件	`*this == x`.
返回	`*this`.
异常安全性	强保证。

移动赋值

filter& operator=(filter&& x)
  noexcept(
    std::allocator_traits<Allocator>::is_always_equal::value ||
    std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value);

令 pocma 为 std::allocator_traits<Allocator>::propagate_on_container_move_assignment::value。如果 pocma，则将内部分配器替换为 x.get_allocator() 的副本。如果 get_allocator() == x.get_allocator()，则将 x 的内部数组传输到 *this；否则，将内部数组替换为容量为 x.capacity() 的新数组并复制 x 的内部数组的值。将内部哈希函数替换为 x.hash_function() 的副本。

前置条件	如果 `pocma`，则 `Allocator` 是 nothrow CopyAssignable。 `hasher` 是 nothrow Swappable。
后置条件	`x.capacity() == 0`.
返回	`*this`.
异常安全性	如指示的无抛出，否则强保证。

初始化列表赋值

filter& operator=(std::initializer_list<value_type> il);

清除过滤器并插入 il 中的值。

*this.

容量

size_type capacity() const noexcept;

后置条件	`capacity()` 是 `CHAR_BIT` 的倍数。
返回	内部数组的位大小。

容量估算

static size_type capacity_for(size_type n, double fpr);

前置条件	`fpr` 介于 0.0 和 1.0 之间。
后置条件	`filter(capacity_for(n, fpr)).capacity() == capacity_for(n, fpr)`. `capacity_for(n, 1.0) == 0`.
返回	当插入 `n` 个不同元素时，`filter` 达到误报率等于 `fpr` 所需容量的估计值。

FPR 估计

static double fpr_for(size_type n, size_type m);

后置条件	`fpr_for(n, m)` 介于 0.0 和 1.0 之间。 `fpr_for(n, 0) == 1.0`. `fpr_for(0, m) == 0.0` (如果 `m != 0`)。
返回	当将 `n` 个不同元素插入到容量为 `m` 的 `filter` 中时，产生的误报率的估计值。

数据访问

Array

boost::span<unsigned char>       array() noexcept;
boost::span<const unsigned char> array() const noexcept;

后置条件	`array().size() == capacity() / CHAR_BIT`.
返回	内部数组的 span。

修改器

插入

void insert(const value_type& x);
template<typename U> void insert(const U& x);

如果 capacity() != 0，则根据 hash_function()(x) 的值确定性地将内部数组中的 k * subfilter::k（不一定不同）位设置为一。

后置条件	`may_contain(x)`.
异常安全性	强保证。
注意	第二个重载仅在 `hasher::is_transparent` 是有效成员类型定义时参与重载决议。

插入迭代器范围

template<typename InputIterator>
  void insert(InputIterator first, InputIterator last);

等价于 while(first != last) insert(*first++)。

前置条件	`InputIterator` 是一个引用 `value_type` 的 LegacyInputIterator。 `[first, last)` 是一个有效范围。

插入初始化列表

void insert(std::initializer_list<value_type> il);

等价于 insert(il.begin(), il.end())。

Swap

void swap(filter& x)
  noexcept(std::allocator_traits<Allocator>::is_always_equal::value ||
           std::allocator_traits<Allocator>::propagate_on_container_swap::value);

令 pocs 为 std::allocator_traits<Allocator>::propagate_on_container_swap::value。交换内部数组和哈希函数与 x 的。如果 pocs 为真，则交换内部分配器与 x 的。

前置条件	`pocs \|\| get_allocator() == x.get_allocator()`. 如果 `pocs`，则 `Allocator` 是 nothrow Swappable。 `hasher` 是 nothrow Swappable。
异常安全性	无抛出。

清除

void clear() noexcept;

将内部数组中的所有位设置为零。

重置

void reset(size_type m = 0);
void reset(size_type n, double fpr);

第一个重载：如果根据 m 计算出的结果容量不等于 capacity()，则替换内部数组，并清除过滤器。
第二个重载：等价于 reset(capacity_for(n, fpr))。

前置条件	`fpr` 介于 0.0 和 1.0 之间。
后置条件	通常，`capacity() >= m`。如果 `m == 0` 或 `m == capacity()` 或 `m == capacity_for(n, fpr)` 对于某个 `n` 和 `fpr`，则 `capacity() == m`。
异常安全性	如果 `m == 0` 或 `capacity_for(n, fpr) == 0`，则无抛出，否则强保证。

与 AND 组合

filter& operator&=(const filter& x);

如果 capacity() != x.capacity()，则抛出 std::invalid_argument 异常；否则，将内部数组中每个位的值更改为该位与 x 中对应位进行逻辑 AND 操作的结果。

前置条件	`x` 和 `y` 的 `Hash` 对象是等价的。
返回	`*this`;
异常安全性	强保证。

与 OR 组合

filter& operator|=(const filter& x);

如果 capacity() != x.capacity()，则抛出 std::invalid_argument 异常；否则，将内部数组中每个位的值更改为该位与 x 中对应位进行逻辑 OR 操作的结果。

前置条件	`x` 和 `y` 的 `Hash` 对象是等价的。
返回	`*this`;
异常安全性	强保证。

观察器

get_allocator

allocator_type get_allocator() const noexcept;

内部分配器的副本。

hash_function

hasher hash_function() const;

返回	内部哈希函数的副本。

查找

may_contain

bool may_contain(const value_type& x) const;
template<typename U> bool may_contain(const U& x) const;

返回	当且仅当假想的 `insert(x)` 操作选择的所有位都设置为一。
注意	第二个重载仅在 `hasher::is_transparent` 是有效成员类型定义时参与重载决议。

比较

operator==

template<
  typename T, std::size_t K, typename S, std::size_t B, typename H, typename A
>
bool operator==(
  const filter<T, K, S, B, H, A>& x, const filter<T, K, S, B, H, A>& y);

前置条件	`x` 和 `y` 的 `Hash` 对象是等价的。
返回	当且仅当 `x.capacity() == y.capacity()` 且 `x` 和 `y` 的内部数组位wise相同。

operator!=

template<
  typename T, std::size_t K, typename S, std::size_t B, typename H, typename A
>
bool operator!=(
  const filter<T, K, S, B, H, A>& x, const filter<T, K, S, B, H, A>& y);

前置条件	`x` 和 `y` 的 `Hash` 对象是等价的。
返回	`!(x == y)`.

Swap

template<
  typename T, std::size_t K, typename S, std::size_t B, typename H, typename A
>
void swap(filter<T, K, S, B, H, A>& x, filter<T, K, S, B, H, A>& y)
  noexcept(noexcept(x.swap(y)));

等价于 x.swap(y)。

子过滤器

“**子过滤器**”实现了用于 boost::bloom::filter 的特定位设置（插入）和位检查（查找）算法。子过滤器对过滤器内部数组的称为“**子数组**”的部分进行操作。这些子数组的精确宽度静态地取决于子过滤器类型。

符合规范的子过滤器的完整接口并未公开，因此用户无法提供自己的子过滤器，只能使用库本身提供的子过滤器。以下是公开可用的接口。

Subfilter::k

结果	一个编译时 `std::size_t` 值，指示每次操作设置/检查的（不一定不同）位数。

typename Subfilter::value_type

结果	一个 cv-非限定的、TriviallyCopyable 类型，子过滤器将分配的子数组投影到该类型。

Subfilter::used_value_size

结果	一个编译时 `std::size_t` 值，表示用于位设置/检查的 `Subfilter::value_type` 有效部分的长度（假定从内存中最低地址开始）。
后置条件	大于零且不大于 `sizeof(Subfilter::value_type)`。
注意	可选。

used-value-size

template<typename Subfilter>
constexpr std::size_t used-value-size; // exposition only

used-value-size<Subfilter> 是 Subfilter::used_value_size（如果此嵌套常量存在），否则为 sizeof(Subfilter::value_type)。该值是给定子过滤器操作的子数组的有效字节大小。

`<boost/bloom/block.hpp>`

namespace boost{
namespace bloom{

template<typename Block, std::size_t K>
struct block;

} // namespace bloom
} // namespace boost

类模板 `block`

boost::bloom::block — 一种对整型进行操作的子过滤器。

提要

// #include <boost/bloom/block.hpp>

namespace boost{
namespace bloom{

template<typename Block, std::size_t K>
struct block
{
  static constexpr std::size_t k = K;
  using value_type               = Block;

  // the rest of the interface is not public

} // namespace bloom
} // namespace boost

描述

模板参数

Block

一种无符号整型或一个包含 2^N 个无符号整型元素的数组。

K

每次操作设置/检查的位数。必须大于零。

`<boost/bloom/multiblock.hpp>`

namespace boost{
namespace bloom{

template<typename Block, std::size_t K>
struct multiblock;

} // namespace bloom
} // namespace boost

类模板 `multiblock`

boost::bloom::multiblock — 一个关于整型数组的子过滤器。

提要

// #include <boost/bloom/multiblock.hpp>

namespace boost{
namespace bloom{

template<typename Block, std::size_t K>
struct multiblock
{
  static constexpr std::size_t k = K;
  using value_type               = Block[k];

  // the rest of the interface is not public

} // namespace bloom
} // namespace boost

描述

模板参数

Block

一种无符号整型或一个包含 2^N 个无符号整型元素的数组。

K

每次操作设置/检查的位数。必须大于零。

设置/检查的每个 K 位都位于 Block[K] 数组的不同元素中。

`<boost/bloom/fast_multiblock32.hpp>`

namespace boost{
namespace bloom{

template<std::size_t K>
struct fast_multiblock32;

} // namespace bloom
} // namespace boost

类模板 `fast_multiblock32`

boost::bloom::fast_multiblock32 — multiblock<std::uint32_t, K> 的更快替代品。

提要

// #include <boost/bloom/fast_multiblock32.hpp>

namespace boost{
namespace bloom{

template<std::size_t K>
struct fast_multiblock32
{
  static constexpr std::size_t k               = K;
  using value_type                             = implementation-defined;

  // might not be present
  static constexpr std::size_t used_value_size = implementation-defined;

  // the rest of the interface is not public

} // namespace bloom
} // namespace boost

描述

模板参数

`K`	每次操作设置/检查的位数。必须大于零。

fast_multiblock32<K> 在统计上等同于 multiblock<std::uint32_t, K>，但在编译时可用时利用选定的 SIMD 技术以更快地执行。目前支持：AVX2、小端 Neon、SSE2。非 SIMD 情况退回到常规 multiblock。

used-value-size<fast_multiblock32<K>> 是 4 * K。

`<boost/bloom/fast_multiblock64.hpp>`

namespace boost{
namespace bloom{

template<std::size_t K>
struct fast_multiblock64;

} // namespace bloom
} // namespace boost

类模板 `fast_multiblock64`

boost::bloom::fast_multiblock64 — multiblock<std::uint64_t, K> 的更快替代品。

提要

// #include <boost/bloom/fast_multiblock64.hpp>

namespace boost{
namespace bloom{

template<std::size_t K>
struct fast_multiblock64
{
  static constexpr std::size_t k               = K;
  using value_type                             = implementation-defined;

  // might not be present
  static constexpr std::size_t used_value_size = implementation-defined;

  // the rest of the interface is not public

} // namespace bloom
} // namespace boost

描述

模板参数

`K`	每次操作设置/检查的位数。必须大于零。

fast_multiblock64<K> 在统计上等同于 multiblock<std::uint64_t, K>，但在编译时可用时利用选定的 SIMD 技术以更快地执行。目前支持：AVX2。非 SIMD 情况退回到常规 multiblock。

used-value-size<fast_multiblock64<K>> 是 8 * K。

未来工作

Boost.Bloom 的审阅者和用户提出的一些功能正在考虑纳入库的未来版本。

批量操作

boost::bloom::filter 的每次插入/查找操作都可能涉及对内部位数组的一次或多次缓存未命中。遵循 Boost.Unordered 中批量访问的类似方法，我们可以流水线化多个操作，以便利用缓存未命中停顿来执行有用的计算。此功能的接口可能如下所示：

f.insert(first1, last1);
f.may_contain(first2, last2, [] (const value_type& x, bool res) {
  // x is (likely) in the filter if res == true
});

`try_insert`

为了避免插入已经存在的元素，我们现在必须执行

if(!f.may_contain(x)) f.insert(x);

这两个调用可以合并成一个可能更快、单次的操作。

bool res = f.try_insert(x); // returns true if x was not present

插入元素数量的估计

对于经典的布隆过滤器，实际插入的元素数量可以从数组中设置为一的位数\(B\)估计为

\(n\approx-\displaystyle\frac{m}{k}\ln\left(1-\displaystyle\frac{B}{m}\right),\)

这可用于实现成员函数 estimated_size。截至本文撰写之时，我们不知道如何将此公式扩展到块过滤器和多块过滤器的情况。关于这个问题，任何帮助都将不胜感激。

运行时指定 k

目前，每次操作设置的位数 k 在编译时配置。可以提供 boost::bloom::filter 的变体（或扩展），其中 k 的值在运行时指定，其权衡是其性能将比静态情况差（初步实验显示执行时间增加约 10-20%）。

备用过滤器

我们可以考虑添加额外的数据结构，例如布谷鸟和异或过滤器，它们更节省空间，并且可能更快。

附录 A：FPR 估计

对于经典的布隆过滤器，在某些简化假设下，理论误报率由以下公式给出：

\(\text{FPR}(n,m,k)=\left(1 - \left(1 - \displaystyle\frac{1}{m}\right)^{kn}\right)^k \approx \left(1 - e^{-kn/m}\right)^k\)对于大的\(m\),

其中\(n\)是插入过滤器中的元素数量，\(m\)其以位为单位的容量和\(k\)每次插入设置的位数（参见此公式的推导）。对于固定的逆负载因子\(c=m/n\)，表达式在

\(k_{\text{opt}}=c\cdot\ln2\)

处达到其最小值\(1/2^{k_{\text{opt}}} \approx 0.6185^{c}\)。最佳\(k\)，它必须是整数，是以下两者之一：\(\lfloor k_{\text{opt}}\rfloor\)或\(\lceil k_{\text{opt}}\rceil\).

在 boost::bloom::filter<T, K, block<Block, K'>> 形式的过滤器中，我们可以扩展 Putze 等人的方法来推导出（近似但非常精确的）公式

\(\text{FPR}_{\text{block}}(n,m,b,k,k')=\left(\displaystyle\sum_{i=0}^{\infty} \text{Pois}(i,nbk/m) \cdot \text{FPR}(i,b,k')\right)^{k},\)

其中

\(\text{Pois}(i,\lambda)=\displaystyle\frac{\lambda^i e^{-\lambda}}{i!}\)

是泊松分布的概率质量函数，平均值为\(\lambda\)和\(b\)是 Block 的位大小。如果使用 multiblock<Block,K'>，我们有

\(\text{FPR}_\text{multiblock}(n,m,b,k,k')=\left(\displaystyle\sum_{i=0}^{\infty} \text{Pois}(i,nbkk'/m) \cdot \text{FPR}(i,b,1)^{k'}\right)^{k}.\)

正如我们之前评论过的，通常情况下

\(\text{FPR}_\text{block}(n,m,b,k,k') \geq \text{FPR}_\text{multiblock}(n,m,b,k,k') \geq \text{FPR}(n,m,kk'),\)

也就是说，块过滤器和多块过滤器在每次插入设置相同位数的条件下，其 FPR 比经典过滤器差，但它们会更快。我们有特殊情况

\(\text{FPR}_{\text{block}}(n,m,b,k,1)=\text{FPR}_{\text{multiblock}}(n,m,b,k,1)=\text{FPR}(n,m,k),\)

这很容易从使用 {block|multiblock}<Block, 1> 的行为与经典布隆过滤器完全相同这一观察结果中得出。

我们不知道当 Stride 不是其“自然”大小 used-value-size<Subfilter> 时（即当子过滤器子数组重叠时），块过滤器和多块过滤器的 FPR 的任何封闭、简单公式。我们可以使用以下近似值（\(s\)= 以位为单位的 Stride）

\(\text{FPR}_{\text{block}}(n,m,b,s,k,k')=\left(\displaystyle\sum_{i=0}^{\infty} \text{Pois}\left(i,\frac{n(2b-s)k}{m}\right) \cdot \text{FPR}(i,2b-s,k')\right)^{k},\)
\(\text{FPR}_\text{multiblock}(n,m,b,s,k,k')=\left(\displaystyle\sum_{i=0}^{\infty} \text{Pois}\left(i,\frac{n(2bk'-s)k}{m}\right) \cdot \text{FPR}\left(i,\frac{2bk'-s}{k'},1\right)^{k'}\right)^{k},\)

其中替换\(b\)带有\(2b-s\)(或\(bk'\)带有\(2bk'-s\)对于多块过滤器）解释了由于重叠，影响特定位的哈希位置窗口会扩散的事实。请注意，当\(s\)取其默认值（块为 \(b\)，多块为 \(bk'\)）时，这些公式会简化为非重叠情况。这些近似值对于较低的\(k'\)值是可接受的，但随着\(k'\)的增长，往往会低估实际的 FPR。通常，对于典型的过滤器配置，使用重叠会将 FPR 提高（降低）0.6 到 0.9 倍。

\(\text{FPR}_{\text{block}}(n,m,b,s,k,k')\)and\(\text{FPR}_\text{multiblock}(n,m,b,s,k,k')\)是 boost::filter::fpr_for 实现使用的公式。

附录 B：实现说明

哈希混合

这是我们用于在哈希函数不具有雪崩特性时改进其统计特性的位混合后处理过程：

\(m\leftarrow\text{mul}(h,C)\),
\(h'\leftarrow\text{high}(m)\text{ xor }\text{low}(m)\),

其中\(\text{mul}\)表示两个 64 位因子的 128 位乘法，\(\text{high}(m)\)and\(\text{low}(m)\)分别是\(m\)的高 64 位字和低 64 位字，\(C=\lfloor 2^{64}/\varphi \rfloor\)and\(\varphi\)是黄金比例。

32 位模式

在内部，即使在 32 位模式下，用户提供的哈希函数生成 32 位输出时，我们也始终使用 64 位哈希值。为了将 32 位哈希值扩展到 64 位，我们使用与上面描述的相同的混合过程。

省去多个哈希函数

直接实现布隆过滤器，每次操作使用\(k\)位，需要\(k\)个不同且独立的哈希函数\(h_i(x)\)，这会带来重要的性能损失，特别是如果对象的哈希开销很大（例如字符串）。Kirsch 和 Mitzenmacher 展示了如何将此要求放宽到仅两个不同的哈希函数\(h_1(x)\)and\(h_2(x)\)线性组合为

\(g_i(x)=h_1(x)+ih_2(x).\)

我们未经正式论证地将此进一步放宽到只有一个初始哈希值\(h_0=h_0(x)\)，其中新值\(h_i\)通过非常廉价的混合方案从\(h_{i-1}\)计算。在下文中\(k\), \(k'\)是 boost::bloom::filter<T, K, {block|multiblock}<Block, K'>> 形式过滤器中的同名值，\(b\)是 sizeof(Block) * CHAR_BIT，并且\(r\)是过滤器中的子数组数量。

子数组位置

为了从中产生一个位置（即一个位于in\([0,r)\)范围内的数字\(h_{i-1}\)\(p\)），我们不使用直接但昂贵的程序\(p\leftarrow h_{i-1}\bmod r\)

，而是求助于 Lemire 的快速范围技术
\(m\leftarrow\text{mul}(h_{i-1},r),\)

\(p\leftarrow\lfloor m/2^{64} \rfloor=\text{high}(m).\)中产生一个位置（即一个位于为了使与哈希值的进一步使用去相关，我们产生template< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );\(h_{i-1}\)和

\(h_{i}\)

带有\(h_i\leftarrow c \cdot h_{i-1} \bmod 2^{64}=\text{low}(c \cdot h_{i-1}),\)其中 \(c=\text{0xf1357aea2e62a9c5}\)（64 位模式），\(c=\text{0xe817fb2d}\)（32 位模式）取自 Steele 和 Vigna。变换\(h_{i-1} \rightarrow h_i\)是一个简单的乘法同余生成器 over\(2^{64}\)。为了使这个 MCG 产生长周期，\(h_0\)必须是奇数，因此实现调整\(h_0\)到\(h_0'= (h_0\text{ or }1)\)，这使得\(h_i\)的最低有效位不适合伪随机化（它总是 1）。

位选择

在一个子过滤器内部，我们必须从\(k'\)生成\(h_i\)个在范围\([0,b)\)中的值（\(k'\)位的位置）。我们通过连续从中取出\(h_i\)\(\log_2b\)位来实现这一点，而不使用包含其最低有效位的部分（如前所述，它始终为一）。如果位用完（当\(k'> 63/\log_2b\)时发生），我们使用之前描述的混合过程生成新的哈希值template< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );与哈希值的进一步使用去相关，我们产生\(h_{i+1}\)

SIMD 算法

`fast_multiblock32`

使用 AVX2 时，我们一次选择最多 8 位，方法是创建一个包含 32 位值的 __m256i\((x_0,x_1,...,x_7)\)，其中每个\(x_i\)由哈希值的不同 5 位部分构造，并由此计算 __m256i\((2^{x_0},2^{x_1},...,2^{x_7})\)使用 _mm256_sllv_epi32。如果需要更多位，我们生成一个新哈希值，如前文所述并重复。

对于小端 Neon，算法类似，但计算使用两个 uint32x4_t 并行执行，因为 Neon 没有 256 位寄存器。

在 SSE2 的情况下，我们没有 _mm256_sllv_epi32 的 128 位等效物，因此我们使用以下略有趣的技术：一个形如

\(((x_0+127)\cdot 2^{23},(x_1+127)\cdot 2^{23},(x_2+127)\cdot 2^{23},(x_3+127)\cdot 2^{23}),\)

，其中每个\(x_i\)存在于\([0,32)\)的 __m128i 可以被 reinterpret_cast 到（即具有与）__m128（float 寄存器）

\((2^{x_0},2^{x_1},2^{x_2},2^{x_3}),\)

相同的二进制表示，从中我们可以通过 _mm_cvttps_epi32 获得我们所需的移位 1 的 __m128i。

`fast_multiblock64`

我们仅为 AVX2 提供 SIMD 实现，它依赖于两个并行的 __m256i 来生成多达 8 个带有移位 1 的 64 位值。对于 Neon 和 SSE2，通过 4 个 128 位寄存器进行模拟比非 SIMD multiblock<uint64_t, K> 慢。

发布说明

Boost 1.89

初始发布。

致谢

Peter Dimov 和 Christian Mazakas 在开发阶段审阅了大部分代码和文档。Sam Darwin 为 CI 设置和文档构建提供了支持。Braden Ganetsky 为 boost::bloom::filter 贡献了 GDB pretty-printer。

Boost 接受性评审于 2025 年 5 月 13 日至 22 日进行。非常感谢 Arnaud Becheler 的专家管理。以下人员参与了评审：Dmitry Arkhipov、David Bien、Claudio DeSouza、Peter Dimov、Vinnie Falco、Alexander Grund、Seth Heeren、Andrzej Krzemie&nacute;ski、Ivan Matek、Christian Mazakas、Rubén Pérez、Kostas Savvidis、Peter Turcan、Tomer Vromen。非常感谢他们提供的非常有益的反馈。

Boost.Bloom 于 2025 年 1 月至 6 月在卡塞雷斯和奥罗佩萨设计和编写。

版权和许可

本文件的

根据 Boost 软件许可证，版本 1.0 分发。