学习LLVM数据结构：SmallSet

在现代 C++ 程序开发中，选择合适的数据结构，对于程序性能和内存安全都至关重要。LLVM 项目中，有一大块内容便是设计用于内部开发的高效数据结构。

本系列文章以 cppreference 的格式，介绍这些实用的数据结构。你既可以将其作为学习参考，也可以作为学习 LLVM 的补充材料。

在现代编程语言开发中，集合（Set）是一种非常有用的数据结构，它可以高效存储唯一元素。本文介绍一种更轻量级的集合实现：SmallSet。它非常适合存储少量元素，同时保持出色的性能和内存效率。

基本介绍

SmallSet 是一种小型集合类型，它实现了基本的集合操作，比如插入、删除和查找等。它的设计目标是优化在存储小规模数据时的性能和内存占用，它结合了小对象优化和动态内存调节技术，非常适合频繁访问的小集合场景。
如果你已经对 SmallVector 有了解，那么 SmallSet 和它有着类似的实现思路。

llvm::SmallSet 定义在 llvm/ADT/SmallSet.h 头文件中。
它的声明为：

1 2	template<typename T, unsigned N, typename C = std::less<T>> class SmallSet;

当集合中存储的元素数量少于模板参数 N 时，将采取更优化的存储策略；如果数量超出指定范围后，采用和 std::set 一样的实现方案（事实上，其内部直接调用了 std::set 来管理数据）。
并不建议给 N 的值过大，所以在实现中，限制了 N <= 32，因为小对象优化利用了 SmallVector 来管理数据，其搜索效率是线性的，如果数据量过大，则会失去作为集合的高效查找的属性。如果希望管理更多的数据，使用 DenseSet 是一个替代的方案。
第三个模板参数是自定义比较函数，默认是使用 std::less，它将用于在集合内部做元素排序和查找时的比较规则，它会传给内部管理数据的 std::set 使用。我们知道，集合内部通常使用平衡二叉树来优化检索效率，所以需要元素比较算法的支持。

特点

关联容器：和 std::set 一样，SmallSet 满足符合集合类型的特征。
小规模数据优化：SmallSet 内部使用了一个 SmallVector 来存储少量数据（小于 32 个），从而在小规模数据时，避免了构建和维护二叉树结构带来的性能开销。
操作一致：它和 std::set 拥有一样的操作接口。

与标准库 set 的对比

性能优势：在数据量较小时，由于不会涉及到分配二叉树结构和自平衡等开销，性能会优于 std::set。
退化时性能损失：当容器中存储元素超出给定值后，需要将原来的数据拷贝或移动到 std::set 容器中，这带来了瞬时的性能下降。所以，需要谨慎决定 N 的大小。
可能浪费空间：当数据量较小时，SmallSet 采用 SmallVector 作为内部的数据存储类型，如果 N 值大于实际存储的元素数量，会带来空间浪费。
只适合小规模数量集合：它适合使用在简单场景，尤其是基本明确容量，且需要快速创建和销毁集合时。尽量让其工作在小数据优化状态，当数据量较大时，使用 std::set 更合适。

数据成员

整个 SmallSet 的主要成员有：

template<typename T, unsigned N, typename C = std::less<T>> 
class SmallSet {   
  SmallVector<T, N> Vector; // 用来存储小规模数据   
  std::set<T, C> Set; // 数据量超出 N 后，存放数据 
};

成员方法

这里罗列部分常用的方法，完整列表和实现细节请参考 llvm/ADT/SmallSet.h 中的代码。

构造

使用默认构造函数，因为我们不会在构造集合时初始化整个集合。

1	SmallSet<int> theSet;

迭代器

因为有两个存储位置，所以我们不得不为这个容器类型实现自己的迭代器。使用方法和常规迭代器相同，支持 begin() end() 访问元素。

插入

1	std::pair<const_iteraotr, bool> ret = theSet.insert(5);

如果插入元素时，是小数据模式，便手动实现一个不含重复元素的 SmallVector 插入；否则，直接插入 std::set，如果 SmallVector 容量超出 N，则将 SmallVector 中全部数据转移到 std::set 中。
返回一个 std::pair，第一个值是指向这个元素的迭代器，第二个值是标记是否插入成功，如果插入失败，表示相同值已存在，第一个值将是指向那个相同值的迭代器。

删除

1	theSet.erase(5);

和插入相反的动作，但数据量缩减到小于 N 并不会退化回小数据优化模式。

查找

1	auto existed = theSet.contains(10);

计数

1 2	auto elements = theSet.size(); auto ele = theSet.count(10); // 因为是集合，只会返回 0 或 1，表示这个元素值的数量

比较

支持几种比较运算符的使用。

注意事项

不保证异常安全

SmallSet 不是异常安全的。和标准库 std::set 不同。

不合适的预分配大小

和 SmallVector 一样，在声明类型时，如果给定的 N 值相对较大，会存在内存空间的浪费；但如果给定的值过小，又发挥不出 SmallSet 容器的性能优势，反而带来性能下降。

迭代器失效

虽然集合容器作为一种非线性容器，不会在插入和删除元素时，导致其他迭代器失效，但我们应该注意到 SmallSet 中存在 SmallVector 和数据量变大导致内存扩展时的问题。所以，SmallSet 中的操作是可能导致迭代器失效的。

元素为指针类型

SmallSet 的实现中，特别针对当元素类型 T 为指针类型时，一种特化的实现方案，它将完全采用 SmallPtrSet 来实现。后者拥有前者的所有特质，区别在于，当发生内存扩展时，它的实现是一个哈希表（而没有使用 std::set）。因为指针和普通元素的一个区别是，指针不需要排序，且比较代价更大，如果做动态再平衡，开销比普通元素更大。

性能

不适合存储大量数据

首先，模板参数 N 不能超过 32，否则会导致编译失败，N 值较大时，检索元素的效率会降低（SmallVector 中线性查找复杂度），所以实现上强行约束了最大值。
其次，它本身也不适合存储大量元素，尽量避免存储超出 N 值的元素数量。大量数据时，它使用 std::set 管理数据，反而还带来了当数据扩展时的瞬时性能下降问题。

添加和删除元素

添加和删除元素会带来性能开销，一方面是保证元素唯一性和当数据量较大时 std::set 的再平衡开销，另一方面时当数据扩展时（添加元素），所有 SmallVector 元素复制或移动到 std::set 的开销。
当插入数据的数量少于 N 时，不会带来动态分配开销，因为构造时已经分配了 N 这么大的内存。