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

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

  1. 学习LLVM数据结构：ArrayRef
  2. 学习LLVM数据结构：SmallVector
  3. 学习LLVM数据结构：StringRef
  4. 学习LLVM数据结构：SmallSet

基本介绍

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

1
2
template<typename T, unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value> 
class SmallVector;

llvm::SmallVector 是一个可变长数组，类似于 std::vector，同时它对较小长度的数组做了优化。
它的内存管理方式采用局部缓存的设计思路，在对象内部预留一小块空间，用于存储数据。当数据量超出预留空间的大小时，才会将数据放在堆上。它本身保存一部分元素，这便使得在小数组中，避免进行堆分配的操作，提高了效率。
注意到，它带有一个含默认值的模板参数 N，它用来指定预留空间的大小，默认不指定时，编译器会自动选择一个合理的阈值（通常考虑依据是栈空间的占用情况）。

特点

  • 顺序容器：SmallVector 是一个顺序容器，可以在末尾添加和删除元素，可以通过下标访问任意元素。
  • 小长度数组优化：它结合了定长数组在栈上快速分配和动态数组在堆上的灵活性，当管理的数据长度小于阈值（默认值或声明时给定值），会将数据保存在栈上，从而避免堆分配和内存管理带来的性能开销。
  • 操作一致：它的大多数操作，和 STL vector 保持一致。

与标准库 vector 的对比

  • 性能优势：在数据量较小时，由于不会涉及到堆内存分配和管理的开销，性能会优于 std::vector。另外，它可以识别平凡可复制的特性，从而更细粒度地做内存管理。
  • 退化时的性能损失：当发生从栈到堆的退化时，llvm::SmallVector 会带来数据拷贝的开销。所以需要仔细考虑阈值的设定。
  • 可能浪费空间：llvm::SmallVector 会在定义时预分配设定的 N 的空间，如果实际数据少于 N，那么会存在空间浪费的问题。std::vector 也存在类似问题。

继承结构

简单的继承结构如：

继承结构图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
template <typename T, unsigned N> 
class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {};

// 只用于管理一块内置数组 
template <typename T, unsigned N> 
class SmallVectorStorage {}; 

// 实现了大多数操作方法 
template <typename T> 
class SmallVectorImpl : public SmallVectorTemplateBase<T> {}; 

// SmallVectorTemplateBase 有两种模板类，分别针对类型是否时 POD 做实现 
template <typename T, bool = (is_trivially_copy_constructible<T>::value) && 
                             (is_trivially_move_constructible<T>::value) && 
                             std::is_trivially_destructible<T>::value> 
class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {};
template <typename T> 
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {};

// 不涉及 POD 的部分 
// 第二个模板参数是一个 dummy 参数，只用来解决当 ArrayRef 作为类型时，避免空长度时无法实例化的问题 
template <typename T, typename = void> 
class SmallVectorTemplateCommon : public SmallVectorBase<SmallVectorSizeType<T>> {};

// 最基础的类，管理几个数据成员，Size_T 是对类型 size 的推导 
template <typename Size_T> 
class SmallVectorBase {};

SmallVector 继承自 SmallVectorImpl 和 SmallVectorStorage，其中 SmallVectorImpl 实现了大多数通用的操作代码和管理长度等属性的数据成员。它继承的 SmallVectorTemplateBase、SmallVectorTemplateCommon 和 SmallVectorBase 都是用来就完成模板实例化时的公共代码，这里先按下不表。
SmallVectorStorage 实现了堆内联存储的静态数组的分配和管理，它是一个 POD 类型，只含有数据。这也有利于编译器为特定长度的数组做专门的优化。
通过这种分离，SmallVectorImpl 可以用于不同模板类的复用，而 SmallVectorStorage 又可以方便的做模板特化（不同的 N）。这样，减少了模板实例化时的实例化数量，降低了编译空间占用，提高编译效率，是一种在很多 C++ 工程中普遍用到的实现技巧。

我们再回头看 SmallVectorImpl 的继承结构，它的父类中，SmallVectorBase 作为最底层的类，提供了最基本的功能，包括类型的数据，比如 size 和 capacity，一些辅助函数和虚函数定义。它作为整个继承体系的根，定义了所有 SmallVector 最通用的接口和行为。
SmallVectorTemplateCommon<T, void> 抽取了 SmallVectorTemplateBase 的实现，它实现了不依赖于 T 是否是 POD 类型的代码。而与 POD 类型相关的代码实现，放在了 SmallVectorTemplateBase 中。
SmallVectorTemplateBase 针对的就是非平凡的类型，根据是否可复制、可移动，又实例化了不同的模板类。它在正确性和性能之间达成平衡，在避免错误的同时，为大多数非平凡类型提供在元素操作上的最优性能。

数据成员

忽略多层级的继承结构，整个 SmallVector 中包含几个主要的成员：

1
2
3
4
5
6
7
8
9
10
11
class SmallVectorBase { 
protected: 
  // 指向向量中第一个元素的指针 
  void *BeginX; 

  // 向量内存空间的总长度   
  size_t Size; 

  // 预分配的空间大小   
  size_t Capacity; 
};

这 3 个成员决定了索引数据和判断优化阈值。
另外，对于小长度数组，还需要分配内置的存储空间：

1
2
3
4
template <typename T, unsigned N> 
struct SmallVectorStorage { 
  alignas(T) char InlineElts[N * sizeof(T)]; 
}

成员方法

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

构造

1
2
3
4
5
6
7
8
9
10
11
12
// 创建一个空的容器，inline storage 大小为 4 
llvm::SmallVector<int, 4> vec1; 

// 指定数值和长度 
llvm::SmallVector<int, 4> vec2(3, 10); // 包含 3 个值为 10 的元素 

// 拷贝构造 
llvm::SmallVector<int, 4> vec3 = vec2; 

// 从 vector 中构造 
std::vector<int> stdVec = {1, 2, 3, 4}; 
llvm::SmallVector<int, 4> vec4(stdVec.begin(), stdVec.end());

迭代器

和 std::vector 一样，也提供了前向迭代器和反向迭代器，以及对应带 const 的版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
llvm::SmallVector<int, 4> vec = {1, 2, 3, 4, 5}; 

// 前向迭代器 
for (llvm::SmallVector<int, 4>::iterator it = vec.begin(); it != vec.end(); ++it) {
  std::cout << *it << " "; 
} 
std::cout << std::endl; 

// 使用 const 前向迭代器 
for (llvm::SmallVector<int, 4>::const_iterator it = vec.cbegin(); it != vec.cend(); ++it) {
  std::cout << *it << " "; 
} 
std::cout << std::endl; 

// 使用 range for loop 
for (int ele : vec) {
  std::cout << ele << " "; 
} 
std::cout << std::endl;

元素访问

1
2
3
4
5
6
7
8
9
10
11
llvm::SmallVector<int, 4> = {1, 2, 3, 4, 5}; 

// 支持下标进行随机访问 
std::cout << vec[0] << std::endl; vec[1] = 0; 

// 使用 at() 方法，内部会做越界检查 
try {
  std::cout << vec.at(2) << std::endl; 
} catch (const std::out_of_range &e) { 
  std::cerr << "Error: " << e.what() << std::endl; 
}

比较

支持常见的几种比较运算符，其中，大于、小于操作的比较逻辑采用通用的序列比较算法，在序列长度相同时，比较对应元素的大小或字典序。

元素操作

基础元素操作与 std::vector 相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
llvm::SmallVector<int, 4> vec; 

// 末尾添加元素 
vec.push_back(1); 

// 移除末尾元素 
vec.pop_back(); 

// 在指定位置插入元素，需要元素移动，所以性能可能较差 
vec.insert(it, 10); // it 是一个有效的迭代器 

// 溢出指定位置元素，同样可能有性能问题 
vec.erase(it); 

// 清除所有元素 
vec.clear(); 

// 返回向量中元素的数量 
vec.size(); 

// 返回向量中的容量，也就是 Capacity 的值 
vec.capacity(); 

// 检查是否为空 
vec.empty(); 

// 改变向量大小 
vec.resize(5); // 调整为 5 个元素 

// 预留指定容量的内存 
vec.reserve(10);

构建

使用 llvm::SmallVector 容器，需要引入 Support 组件，如：

1
set(LLVM_LINK_COMPONENTS Support)

注意事项

不保证异常安全

SmallVector 本身并不是异常安全的。这一点和 std::vector 不同，标准库容器能保证异常安全性。

不合适的预分配大小

如果在定义 SmallVector 时，指定栈上预分配容量 N 非常大，可能会导致栈溢出，需要根据实际情况选择合适的 N ，避免栈溢出。
如果预分配容量 N 不合理，导致使用容器对象时，总是会发生退化到堆的问题，那么重复的数据拷贝，也会带来性能问题。

迭代器失效

和其他顺序容器类型一样，使用迭代器时，插入和删除操作可能会导致迭代器失效。尤其是还需要考虑因为插入元素导致 SmallVector 重新分配内存（栈到堆的退化和堆到堆的重新分配），迭代器都会失效。
resize 操作也会导致迭代器失效。

自定义类型的内存管理

如果 SmallVector 存储的是自定义类型，那么需要确保自定义类型有着正确的构造、移动和拷贝操作，不正确的实现会导致内存泄漏等问题。
如果自定义类型是引用类型，那么使用 SmallVector 管理时，需要确保自定义类型的析构函数中，能够正确释放内存。如果 SmallVector 管理的是指针，还需要自定义析构器来处理指针指向的内存。

使用 SmallVectorImpl 作为参数类型

如果需要传递一个 SmallVector 的容器对象时，形参参数建议使用 SmallVectorImpl，后者没有带有 SmallVectorStorage，所以不会实际分配空间，同时也不需要声明函数时指定 N 值，这无论从效率角度看，还是使用便利性，都非常有价值。比如：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 这种声明需要指定 N 
funcWithVec(llvm::SmallVector<int, 4> &Arg); 
// 而这种声明不需要指定 N
funcWithVecImpl(llvm::SmallVectorImpl<int> &Arg);  

llvm::SmallVector<int, 4> vec1; 
llvm::SmallVector<int, 8> vec2; 

funcWithVec(vec1); // 正常  
funcWithVec(vec2); // 编译报错 

funcWithVecImpl(vec1); // 正常 
funcWithVecImpl(vec2); // 正常

性能

不适合用于存储大量元素

虽然 SmallVector 可以在堆上动态分配内存，但它的设计关注点还是在管理小数据量的动态数组。如果已知数量比较大的动态数组，使用 std::vector 即可。
同理，也不适合管理单个元素内存较大的数据类型。

拷贝成本

使用 SmallVector 需要多留意它可能发生从内部存储到堆上退化时的性能问题。尤其是元素类型本身的拷贝开销比较大时，一个合适的 N 就显得尤为重要。
请保证你的设计中，大多数情况下，都不会发生这种拷贝。

添加和删除元素

添加和删除元素会带来性能开销，一方面是为了保证顺序性，操作位置之后的元素需要移动位置；另一方面，如果发生向堆的退化或堆内存的重新分配，也会带来性能问题。
尽量使用 emplace_back 代替 push_back，以避免不必要的拷贝或移动操作，提高性能。

另见

无。

参考资料

本文同步发布在知乎账号下：学习LLVM数据结构-SmallVector - 知乎