LLVM SmallVector
简介
SmallVector 是一个动态可变长数组，为数组比较小的情况进行了优化。它在类中（实际是在末尾）包含 N 个元素（in-place，在位元素），当元素数量少于这个 N 的时候，数据保存在类中，从而避免了堆的内存分配。这样在数组较小的时候很快很节省，变大了也能够支持。
代码定义
头文件位于llvm/ADT/SmallVector.h
文件中定义有：
- 类
SmallVectorBase-- 不含模板部分的公共基类，提供给各个SmallVectorXXX<>做基类 - 模板类
SmallVectorTemplateCommon，派生自SmallVectorBase - 模板类
SmallVectorTemplateBase，派生自 SmallVectorTemplateCommon<T>-
SmallVectorTemplateBase<T, true>特化版本，针对 POD 数据优化。
-
- 模板类
SmallVectorImpl，派生自SmallVectorTemplateBase<T, is_pod>-
swap()模板方法，赋值操作符重载。
-
- 模板类
SmallVector，派生自SmallVectorImpl<T>-
SmallVector<T, 0>特化版本
-
概述
模板类 SmallVector<T> 从 SmallVectorImpl 派生：
template <typename T, unsigned N> // 注1
class SmallVector : public SmallVectorImpl<T> {
U InlineElts[NUM]; // 注2
this() // 多个构造，用计算出来的可容纳 T 元素的数量 NumTsAvailable 调用基类构造。
}
- 注1：N 表示要 in-place 容纳 N 个 T 元素。
- 注2：根据 N 计算出需要多少个 U 的空间能够存放下 N 个 T 元素，空间需求为 N*sizeof(T)。计算结果为 NUM。原代码中有几个 enum 用于做此计算：
- NumInlineEltsElts -- InlineElts[] 数组大小，以使得有足够的空间容纳 N 个 T 元素。
- NumTsAvailable -- 表示实际申请的空间可以存放的 T 类型元素的数量。
- 基本功能都在基类中实现了，因此此类比较简单。参见
SmallVectorImpl
实现机理
SmallVector 使用在类里面的空间(in-place空间)保存 N个 T 元素。当 push 更多元素的时候，grow() 函数将从堆中申请空间容纳更多元素。这种实现优化了当大部分情况元素数量都少于等于 N 的时候，不用从堆中分配内存，从而得到空间上的优化。
特化版本
- SmallVector 提供针对 N == 0 的特化版本，保证在不完整的 T 类型(incomplete)时也能实例化（此时不需要访问 T 的成员变量）。
设计目的
- 为了优化内存的分配，针对元素数一般小于 N 的时候，能够不用昂贵的内存分配、释放操作。
- 针对 POD 也有构造、移动、析构等优化。也即为了得到最佳程序性能而设计。
网友评论