学习LLVM数据结构：ArrayRef

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

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

基本介绍

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

1	template<typename T> class ArrayRef;

llvm::ArrayRef 是一个轻量级的只读容器，主要用于引用一段连续的内存区域。
它的设计目标是提供高效的数据访问，而不需要拥有底层数据的所有权。这使得 ArrayRef 特别适合在函数参数中实用，从而避免了不必要的内存拷贝。

特点

只读：ArrayRef 不能修改其引用的数据，也不能添加新元素（另一个容器 MutableArrayRef 可以修改）。
轻量级：它只存储一个指向数据的指针和数据的长度，而不存储实际的数据，所以拷贝时非常高效。
按值传递：在传递 ArrayRef 时，实际上传递的是一个指针和其指向数据的长度，所以不需要再对其按引用传递。
操作一致：它的大多数操作，与 STL array 保持一致。

与标准库 array 对比

所有权：llvm::ArrayRef 不拥有其引用数据的所有权，只是对数据的引用；std::array 拥有数据的所有权，存储在栈上。
大小：llvm::ArrayRef 容量是动态的，可以引用任意长度的数组。但由于数组长度是静态的，所以从程序角度看，ArrayRef 的具体引用类型，容量是确定的；std::array 大小在编译期间固定，和 C 数组一样。
可变性：llvm::ArrayRef 是只读的，不能修改引用数据；std::array 允许修改其元素，提供完整的读写权限。
初始化：llvm::ArrayRef 的初始化更灵活，可以从 C 数组、std::array，std::vector 或其他顺序容器初始化。std::array 只能从初始化列表或在定义时使用构造函数初始化。
性能：llvm::ArrayRef 适合在高频传递参数时使用。std::array 默认按值拷贝，会带来开销，需要指定其引用类型作为参数类型。如果是 constexpr 修饰，编译器可以优化传参性能。

数据成员

由于llvm::ArrayRef 只拥有数据的引用，而不管理实际存储的空间，所以它实际上只是一个带有长度的指针。

template <typename T>
class ArrayRef {
private:
    const T* data = nullptr;
    size_t length = 0;
}

成员方法

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

构造

// 初始化一个元素长度 
int A1 = 1; llvm::ArrayRef Arr1{A1}; 

// 初始化指向一块数据首地址和数据长度 
int Ap[3] = {1, 2, 3}; llvm::ArrayRef Arr2{Ap}; 

// 通过两个指针作为区间来初始化 
int *Ap2 = Ap + 2; llvm::ArrayRef Arr3{Ap, Ap2}; 

// 通过 SmallVector 容器来构造 
llvm::SmallVector<int> Vec{1, 2, 3}; 
llvm::ArrayRef Arr4{Vec}; 

// 通过 std::vector 容器来构造 
std::vector STLVec{1, 2, 3}; 
llvm::ArrayRef Arr5{Vec}; 

// 通过 std::array 容器来构造 
std::array STLArr{1, 2, 3}; 
llvm::ArrayRef Arr6{STLArr}; 

// 通过初始化列表来构造 
llvm::ArrayRef Arr8{1, 2, 3};

迭代器

提供了迭代器 begin() 和 end() ，以及反向迭代器 rbegin() 和 rend() 。

元素访问

// 访问数据原始位置的操作 
const T *data = Arr.data(); 

// 访问数据长度的操作 
bool IsEmpty = Arr.empty(); 
size_t Length = Arr.size(); 

// 访问首尾元素 
const T& FirstEle = Arr.front(); 
const T& LastEle = Arr.back(); 

// 下标索引 
const T& Ele = Arr[I]; // assert 检查是否越界

比较

提供了 equals(ArrayRef RHS) 方法。
另一个语法糖是 operator== 运算符。

切片

// 截取从下标 1 的元素到末尾，作为新的 ArrayRef 返回 
llvm::ArrayRef NewArr = Arr.slice(1); 

// 截取两端元素 
llvm::ArrayRef NewArr2 = Arr.slice(1, 3); 

// 剪切前/后部分元素，剩余数组作为新的 ArrayRef 返回 
llvm::ArrayRef NewArr3 = Arr.drop_front(2); 
llvm::ArrayRef NewArr4 = Arr.drop_back(); // 默认是 1 个元素

构建

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

1	set(LLVM_LINK_COMPONENTS Support)

注意事项

引用失效

由于 llvm::ArrayRef 本身是一个引用类型，所以它会面临引用类型作为函数参数时，可能出现的引用失效问题。
同理，函数的返回类型不应该是 llvm::ArrayRef，如果返回的是函数局部对象，那么在 Caller 端，该对象引用的原始数据已失效；如果返回的是函数原始参数，这么做又没有意义。
另外，如果其引用的是一个动态数组，比如 std::vector，那么当动态数组扩容后，llvm::ArrayRef 引用可能会失效。
所以在使用它时，需要时刻思考它的引用对象，什么时候结束生命周期。

越界访问

llvm::ArrayRef 本身的访问不可能越界，但如果它引用的是一个动态数组，而动态数组的长度发生变化（缩小），那么 ArrayRef 的元素访问可能会发生越界问题。
这本质上也是引用失效问题。所以，最好的实践是只引用固定数组，比如用它代替 const std::array & 类型。