为任务选择正确的数据结构

LLVM /ADT/目录中有大量的数据结构，我们通常使用STL数据结构。本节描述在选择时应该考虑的权衡。

第一步是选择您自己的冒险:您想要顺序容器、类似于集合的容器还是类似于映射的容器?在选择容器时，最重要的是计划如何访问容器的算法属性。基于此，你应该使用:

• 如果需要基于另一个值高效地查找值，则使用类似于映射的容器。类映射容器还支持有效的包含查询(无论键是否在映射中)。类映射容器通常不支持有效的反向映射(值到键)。如果需要，可以使用两个映射。一些类似于映射的容器还支持按顺序高效地遍历键。类映射容器是最昂贵的一种，只有在需要这些功能之一时才使用它们。
• 如果您需要将一堆东西放入一个容器中，这个容器可以自动消除重复。一些类似集合的容器支持按排序顺序对元素进行有效的迭代。类集合容器比顺序容器更昂贵。
• 顺序容器提供了最有效的方法来添加元素，并跟踪它们添加到集合中的顺序。它们允许复制并支持有效的迭代，但不支持基于键的高效查找。
• 字符串容器是用于字符或字节数组的专用顺序容器或引用结构。
• 位容器提供了一种有效的方法来存储和执行数字id集上的set操作，同时自动消除重复。要存储的每个标识符，位容器最多需要1位。

一旦确定了容器的适当类别，您就可以通过明智地选择类别中的成员来微调内存使用、常量因素和缓存访问行为。请注意，常量因素和缓存行为可能很重要。例如，如果您有一个向量，它通常只包含几个元素(但是可以包含许多元素)，那么使用SmallVector比使用vector要好得多。这样做可以避免(相对)昂贵的malloc/free调用，这大大降低了向容器添加元素的成本

Sequential Containers (std::vector, std::list, etc)

根据您的需要，可以使用各种顺序容器。在本节中选择第一个可以做您想做的事情。

llvm/ADT/ArrayRef.h

llvm::ArrayRef类是接口中使用的首选类，该接口接受内存中元素的顺序列表并从其中读取数据。通过使用ArrayRef，可以向API传递一个固定大小的数组、一个std::vector、一个llvm::SmallVector以及内存中任何相邻的内容。

Fixed Size Arrays

固定大小的数组非常简单和快速。如果您确切地知道您有多少个元素，或者您对您有多少个元素有一个(低)上限，那么它们是很好的。

Heap Allocated Arrays

堆分配数组(new[] + delete[])也很简单。如果元素的数量是可变的，如果您知道在分配数组之前需要多少元素，如果数组通常很大(如果不是，请考虑一个小向量)，那么它们是很有用的。堆分配数组的成本是new/delete(又名malloc/free)的成本。还请注意，如果使用构造函数分配类型的数组，则将为数组中的每个元素运行构造函数和析构函数(重新调整大小的向量只构造实际使用的元素)。

llvm/ADT/TinyPtrVector.h

TinyPtrVector是一个高度专门化的集合类，当一个向量有零个或一个元素时，优化它以避免分配。它有两个主要限制:1)它只能保存指针类型的值，2)它不能保存空指针。

由于这个容器高度专门化，所以很少使用它。

llvm/ADT/SmallVector.h

SmallVector<type, N>是一个看起来和闻起来都像vector<Type>的简单类:它支持高效的迭代，以内存顺序排列元素(这样您就可以在元素之间执行指针算术)，支持高效的push_back/pop_back操作，支持对其元素的高效随机访问，等等。

SmallVector的主要优点是它为对象本身中的一些元素(N)分配了空间。因此，如果小向量动态地小于N，则不执行malloc。如果malloc/free调用比处理元素的代码昂贵得多，那么这将是一个巨大的胜利。

这是有利于向量”通常小”(如前辈的数量/继任者的一块通常小于8)。另一方面,这使得SmallVector本身的尺寸大,所以你不想分配很多(这样做会浪费很多空间)。因此，在堆栈上使用小向量是最有用的。

SmallVector还为alloca提供了一个很好的可移植性和高效的替代品。

SmallVector相对于std::vector还有一些其他的小优势，这使得SmallVector<type, 0>优于std::vector<type>

• vector是异常安全的，一些实现具有悲观的特性，当SmallVector移动元素时，它会复制这些元素。
• SmallVector理解llvm::is_trivially_copyable，并积极使用realloc。
• 许多LLVM api都将SmallVectorImpl作为out参数(参见下面的说明)。
• 在64位平台上，N = 0的SmallVector比std::vector小，因为它使用无符号(而不是void*)表示其大小和容量。

注意

最好使用SmallVectorImpl作为参数类型。

在不关心“小尺寸”(大多数?)的api中，更喜欢使用SmallVectorImpl类，它基本上就是一个“vector header”(和方法)，后面没有分配元素。注意，SmallVector<T,N>继承自SmallVectorImpl<T>，所以转换是隐式的，不需要花费任何代价。

// BAD: Clients cannot pass e.g. SmallVector<Foo, 4>.
hardcodedSmallSize(SmallVector<Foo, 2> &Out);
// GOOD: Clients can pass any SmallVector<Foo, N>.
allowsAnySmallSize(SmallVectorImpl<Foo> &Out);

void someFunc() {
  SmallVector<Foo, 8> Vec;
  hardcodedSmallSize(Vec); // Error.
  allowsAnySmallSize(Vec); // Works.
}

尽管它的名称中有“Impl”，但它的使用如此广泛，以至于它实际上不再是“实现的私有”了。像SmallVectorHeader这样的名称更合适。

std:vector<T>很受欢迎和尊重。但是，由于上面列出的优点，SmallVector<T,0>通常是更好的选择。当您需要存储超过UINT32_MAX的元素或与期望vector:)的代码进行接口时，vector仍然很有用。

关于std::vector:避免这样的代码:

for ( ... ) {
   std::vector<foo> V;
   // make use of V.
}

而是写成:

std::vector<foo> V;
for ( ... ) {
   // make use of V.
   V.clear();
}

在某种意义上，deque是std::vector的广义版本。与std::vector类似，它提供了常量时间随机访问和其他类似属性，但它也提供了对列表前端的有效访问。它不能保证内存中元素的连续性。

作为这种额外灵活性的交换，std::deque的常数因子成本显著高于std::vector。如果可能的话，使用std::vector或其他更便宜的工具。

std::list是一个非常低效的类，很少有用。它为插入其中的每个元素执行堆分配，因此具有非常高的常数因子，特别是对于小数据类型。list也只支持双向迭代，不支持随机访问迭代。

作为这种高成本的交换，std::list支持对列表两端的有效访问(与std::deque类似，但与std::vector或SmallVector不同)。此外，std::list的迭代器失效特性比vector类更强:在列表中插入或删除元素不会使迭代器或指向列表中其他元素的指针失效。

llvm/ADT/ilist.h

ilist<T>实现了一个“侵入式”的双链表。它是侵入性的，因为它要求元素存储并提供对列表的prev/next指针的访问。

ilist具有与std::list相同的缺点，而且还需要为元素类型实现ilist_traits，但是它提供了一些新的特性。特别是，它可以有效地存储多态对象，在插入或从列表中删除元素时通知traits类，并且ilists保证支持常量时间拼接操作。

这些属性正是我们想要的，比如指令和基本块，这就是为什么这些是用ilists实现的。

有关的兴趣类别可在下面的小节解释:

• ilist_traits
• iplist
• llvm/ADT/ilist_node.h
• Sentinels

llvm/ADT/PackedVector.h

适用于仅为每个值存储少量位的值向量。除了类向量容器的标准操作之外，它还可以执行“或”集合操作。

例如:

enum State {
    None = 0x0,
    FirstCondition = 0x1,
    SecondCondition = 0x2,
    Both = 0x3
};

State get() {
    PackedVector<State, 2> Vec1;
    Vec1.push_back(FirstCondition);

    PackedVector<State, 2> Vec2;
    Vec2.push_back(SecondCondition);

    Vec1 |= Vec2;
    return Vec1[0]; // returns 'Both'.
}

ilist_traits

ilist_traits<T>是ilist<T>的定制机制。iplist<T>(因此ilist<T>)公开派生自这个traits类。

iplist

iplist<T>是ilist<T>的基础，因此支持稍微窄一点的接口。值得注意的是，没有来自T&的插入器。

ilist_traits<T>是这个类的公共基础，可以用于多种定制。

llvm/ADT/ilist_node.h

ilist_node<T>以默认方式实现了ilist(和类似容器)所期望的正向和反向链接。

ilist_nodes被嵌入到节点类型T中，通常T公开派生自ilist_node。

Sentinels

ilists还有另一个必须考虑的特色。要成为c++生态系统中的好公民，它需要支持标准容器操作，例如开始和结束迭代器等。此外，在非空ilists的情况下，操作符—必须在end迭代器上正确工作。

这个问题唯一合理的解决方案是分配一个所谓的哨点和介入列表，后者作为最终迭代器，提供到最后一个元素的反向链接。但是，符合c++约定的操作符c++在哨兵之外是非法的，而且也不能取消对它的引用。

这些约束允许ilist自由地实现如何分配和存储标记。相应的策略由ilist_traits决定。默认情况下，每当需要一个标记时，T就会得到堆分配。

虽然默认策略在大多数情况下是足够的，但是当T不提供默认构造函数时，它可能会崩溃。此外，在许多伊利斯特的例子中，相关哨兵的内存开销被浪费了。为了缓解大量的t哨兵的情况，有时会使用一个技巧，导致幽灵般的哨兵。

幽灵哨兵是通过特殊制作的ilist_traits获得的，它将哨兵与内存中的ilist实例叠加在一起。指针算法用于获取与ilist的这个指针相对的标记符。ilist由一个额外的指针进行扩展，该指针充当标记的反向链接。这是幽灵哨兵中唯一可以合法进入的区域

其他顺序容器选项

其他STL容器也是可用的，比如std::string。

还有各种STL适配器类，如std::queue、std::priority_queue、std::stack等。它们提供了对底层容器的简化访问，但不影响容器本身的成本。

类字符串容器

在C和c++中有多种传递和使用字符串的方法，LLVM添加了一些可供选择的新选项。在这个列表中选择第一个选项来做你需要做的，它们是根据它们的相对成本排序的。

注意，通常不希望将字符串作为const char* s传递。它们有很多问题，包括它们不能表示嵌入的nul(“0”)字符，而且没有有效的长度可用。“const char*”的一般替换是StringRef。

有关为api选择字符串容器的更多信息，请参见字符串传递。

llvm/ADT/StringRef.h

StringRef类是一个简单的值类，它包含一个指向字符和长度的指针，并且与ArrayRef类非常相关(但是专门用于字符数组)。因为StringRef携带一个长度，所以它可以安全地处理包含nul字符的字符串，获得长度不需要strlen调用，而且它甚至有非常方便的api来分割和分割它所表示的字符范围。

StringRef非常适合传递已知为活动的简单字符串，因为它们是C字符串文本、std::string、C数组或小向量。每一种情况都有一个到StringRef的有效隐式转换，这不会导致执行动态strlen。

StringRef有几个主要的限制，使得更强大的字符串容器更有用：

• 您不能直接将StringRef转换为’ const char* ‘，因为没有办法添加尾随nul(不像在各种更强的类上添加.c_str()方法)。
• StringRef不拥有或保留底层字符串字节。因此，它很容易导致悬空指针，并且在大多数情况下不适合嵌入数据结构(相反，使用std::string或类似的东西)。
• 出于同样的原因，如果方法“计算”结果字符串，则StringRef不能用作方法的返回值。相反,使用std:: string。
• StringRef不允许您更改指向字符串的字节，也不允许您从范围中插入或删除字节。对于这样的编辑操作，它与Twine类互操作。

由于其优点和局限性，函数接受StringRef和对象上的方法返回指向其拥有的某个字符串的StringRef是非常常见的。

llvm/ADT/Twine.h

Twine类用作api的中间数据类型，这些api希望获取一个可以通过一系列连接内联构建的字符串。Twine通过在堆栈上形成Twine数据类型的递归实例(一个简单的值对象)作为临时对象，将它们链接到一个树中，然后在使用Twine时将其线性化。Twine只能作为函数的参数使用，并且应该始终作为常量引用，例如：

void foo(const Twine &T);
...
StringRef X = ...
unsigned i = ...
foo(X + "." + Twine(i));

这个例子形成了一个类似“blarg.4”的字符串。通过将值连接在一起，并且不构成包含“blarg”或“blarg.”的中间字符串。
因为Twine是用栈上的临时对象构造的，而且这些实例在当前语句的末尾被销毁，所以它本质上是一个危险的API。例如，这个简单的变量包含未定义的行为，可能会崩溃：

void foo(const Twine &T);
...
StringRef X = ...
unsigned i = ...
const Twine &Tmp = X + "." + Twine(i);
foo(Tmp);

因为临时任务在调用之前就被销毁了。也就是说，Twine的效率比中间的std::string临时函数要高得多，而且它们在StringRef中工作得非常好。只是要意识到它们的局限性。

llvm/ADT/SmallString.h

SmallString是SmallVector的子类，它添加了一些方便的api，比如+=，它接受StringRef的api。SmallString避免在预分配的空间足够容纳其数据时分配内存，并且在需要时回调一般堆分配。因为它拥有自己的数据，所以使用它非常安全，并且支持字符串的完全变异。

和SmallVector一样，SmallString的最大缺点是它们的sizeof。虽然它们针对小字符串进行了优化，但它们本身并不特别小。这意味着它们对于堆栈上的临时刮擦缓冲区非常有效，但通常不应该放到堆中:很少看到SmallString作为频繁分配的堆数据结构的成员或按值返回。

std::string

标准的C++ std::string类是一个非常通用的类，它(像SmallString)拥有它的底层数据。sizeof(std::string)非常合理，因此它可以嵌入到堆数据结构中并按值返回。另一方面,std::string是非常低效的内联编辑(如连接一堆东西在一起),因为它是标准库提供的主机的性能特征取决于很多标准库(如libc++和MSVC提供一个高度优化的字符串类,GCC包含一个很慢实现)。

std::string的主要缺点是，几乎所有使它们变大的操作都可以分配内存，这是很慢的。因此，最好使用SmallVector或Twine作为划痕缓冲区，然后使用std::string保存结果。

类集合容器(std::set, SmallSet, SetVector, etc)

当需要将多个值规范化为一个表示形式时，类集容器非常有用。如何做到这一点有几种不同的选择，提供了各种各样的权衡。

A sorted ‘vector’

如果您打算插入很多元素，然后执行很多查询，一个很好的方法是使用std::vector(或其他顺序容器)和std::sort+std::unique来删除重复项。如果您的使用模式有这两个不同的阶段(insert then query)，并且可以很好地选择顺序容器，那么这种方法就非常有效。

这种组合提供了几个很好的特性:结果数据在内存中是连续的(对于缓存局部性很好)，分配很少，易于寻址(最终向量中的迭代器只是索引或指针)，并且可以通过标准的二分查找(例如std::lower_bound;如果您希望整个元素范围的比较相等，请使用std::equal_range)。

llvm/ADT/SmallSet.h

如果您有一个类似于集合的数据结构，通常比较小，并且其元素也比较小，那么SmallSet<type, n=””>是一个不错的选择。</type,>这个集合有空间容纳N个元素(因此，如果这个集合动态地小于N，则不需要malloc流量)，并通过简单的线性搜索访问它们。当集合超过N个元素时，它分配一个更昂贵的表示，以保证有效的访问(对于大多数类型，它返回到std::set，但是对于指针，它使用的是更好的SmallPtrSet。

这个类的神奇之处在于，它可以非常高效地处理小集合，但是可以优雅地处理非常大的集合，而不会降低效率。

llvm/ADT/SmallPtrSet.h

SmallPtrSet具有SmallSet的所有优点(并且SmallPtrSet透明地实现了一个SmallSet指针集)。如果执行了N次以上的插入，就会分配一个二次探测的哈希表，并根据需要进行增长，从而提供非常高效的访问(常数时间插入/删除/查询，常数因素较少)，并且对malloc流量非常吝啬。

注意，与std::set不同，SmallPtrSet的迭代器在插入发生时无效。此外，迭代器访问的值不会按排序顺序访问。

llvm/ADT/StringSet.h

StringSet是一个围绕StringMap的瘦包装器，它允许有效地存储和检索惟一字符串。

在功能上类似于SmallSet， StringSet还支持迭代。(迭代器取消对StringMapEntry的引用，因此需要调用i->getKey()来访问StringSet的项。)另一方面，StringSet不支持SmallSet和SmallPtrSet支持的范围插入和复制构造。

llvm/ADT/DenseSet.h

DenseSet是一个简单的二次探测哈希表。它擅长于支持小值:它使用一个分配来保存当前插入到集合中的所有对。注意，DenseSet对值类型的要求与DenseMap相同。

llvm/ADT/SparseSet.h

SparseSet包含少量由中等大小的无符号键标识的对象。它使用大量内存，但提供的操作几乎与向量一样快。典型的键是物理寄存器、虚拟寄存器或编号的基本块。

SparseSet对于需要快速清除/查找/插入/删除以及在小集合上快速迭代的算法非常有用。它不用于构建复合数据结构。

llvm/ADT/SparseMultiSet.h

SparseMultiSet向SparseSet添加了多集行为，同时保留了SparseSet所需的属性。与SparseSet一样，它通常使用大量内存，但提供的操作几乎与向量一样快。典型的键是物理寄存器、虚拟寄存器或编号的基本块。

SparseMultiSet对于需要非常快速地清除/查找/插入/删除整个集合，以及迭代共享密钥的元素集的算法非常有用。它通常比使用复合数据结构(例如向量的向量向量，向量的映射)更有效。它不用于构建复合数据结构。

llvm/ADT/FoldingSet.h

FoldingSet是一个聚合类，它非常擅长于独特的昂贵的创建对象或多态对象。它是一个链接哈希表与入侵链接(需要从FoldingSetNode继承惟一的对象)的组合，使用SmallVector作为其ID进程的一部分。

考虑这样一种情况，您希望为复杂对象(例如，代码生成器中的节点)实现“getOrCreateFoo”方法。客户希望生成的类的描述(它知道的操作码和操作数),但我们不希望“新”节点,然后试着把它插入一组却发现它已经存在,此时我们需要删除它并返回的节点已经存在。

为了支持这种客户机风格，FoldingSet使用FoldingSetNodeID(它封装了SmallVector)执行查询，该id可用于描述我们想要查询的元素。查询要么返回与ID匹配的元素，要么返回一个不透明的ID，该ID指示插入应该在何处进行。ID的构造通常不需要堆流量。

因为FoldingSet使用入侵链接，所以它可以支持集合中的多态对象(例如，可以将SDNode实例与loadsdnode混合)。由于元素是单独分配的，指向元素的指针是稳定的:插入或删除元素不会使指向其他元素的指针失效。

std:set是一门合理的综合性课程，它在很多方面都不错，但在任何方面都很好。set为插入的每个元素分配内存(因此malloc非常密集)，并且通常为集合中的每个元素存储三个指针(因此为每个元素增加了大量的空间开销)。它提供了保证的log(n)性能，从复杂性的角度来看，这并不是特别快(特别是当比较集合的元素非常昂贵时，比如字符串)，并且在查找、插入和删除方面有非常高的常数因子。

set的优点是它的迭代器是稳定的(从集合中删除或插入元素不会影响迭代器或指向其他元素的指针)，并且保证对集合的迭代是有序的。如果集合中的元素很大，那么指针和malloc流量的相对开销就不是什么大问题，但是如果集合中的元素很小，那么std::set几乎从来都不是一个好的选择。

llvm/ADT/SetVector.h

LLVM的SetVector是一个适配器类，它结合了您对集合类容器和顺序容器的选择，它提供了一个重要的属性，即使用惟一(忽略重复元素)和迭代支持高效插入。它通过在类集合容器和序列容器中插入元素来实现这一点，使用类集合容器进行惟一，使用序列容器进行迭代。

SetVector与其他集合的不同之处在于，保证迭代的顺序与插入到SetVector中的顺序相匹配。这个属性对于指针集之类的东西非常重要。因为指针值是不确定的(例如，在不同的机器上运行不同的程序)，所以在集合中的指针上迭代将不会有一个定义良好的顺序。

SetVector的缺点是，它需要的空间是普通集合的两倍，并且具有来自类集合容器和它所使用的顺序容器的常数因子之和。只有在需要以确定的顺序遍历元素时才使用它。SetVector在(线性时间)之外删除元素的代价也很高，除非使用它的“pop_back”方法，因为后者更快。

SetVector是一个适配器类，默认为底层容器使用std::vector和一个大小为16的SmallSet，因此非常昂贵。然而,“llvm / ADT / SetVector。h”还提供了一个SmallSetVector类，它默认使用指定大小的SmallVector和SmallSet。如果您使用这种方法，并且您的集合动态地小于N，那么您将节省大量堆流量。

llvm/ADT/UniqueVector.h

UniqueVector类似于SetVector，但是它为插入集合的每个元素保留一个唯一的ID。它内部包含一个map和一个vector，并且为插入集合的每个值分配一个唯一的ID。

UniqueVector非常昂贵:它的成本是维护map和vector的成本之和，它具有很高的复杂度，高的常量因子，并且产生了大量的malloc流量。这是应该避免的。

llvm/ADT/ImmutableSet.h

ImmutableSet是一个基于AVL树的不可变(函数)集实现。添加或删除元素是通过一个工厂对象完成的，并会创建一个新的ImmutableSet对象。如果给定的内容已经存在一个ImmutableSet，则返回现有的;将等式与FoldingSetNodeID进行比较。添加或删除操作的时间和空间复杂度与原始集合的大小成对数关系。

没有返回集合元素的方法，只能检查成员关系。

其他可选的类set容器

STL提供了其他几个选项，比如std::multiset和各种“hash_set”，比如容器(无论是来自c++ TR1还是来自SGI库)。我们从不使用hash_set和unordered_set，因为它们通常非常昂贵(每次插入都需要一个malloc)，而且非常不可移植。

如果您对消除重复不感兴趣，那么multiset非常有用，但是它具有std::set的所有缺点。排序向量(不删除重复项)或其他方法几乎总是更好。

类Map容器(std::map, DesnseMap, etc)

当您希望将数据关联到键时，类似于映射的容器非常有用。像往常一样，有很多不同的方法可以做到这一点。😃

A sorted ‘vector’

如果您的使用模式遵循严格的先插入后查询方法，那么您可以简单地使用与集合类容器的排序向量相同的方法。惟一的区别是，查询函数(使用std::lower_bound来获得有效的log(n)查找)应该只比较键，而不是键和值。这与集合的排序向量具有相同的优点。

llvm/ADT/StringMap.h

字符串通常用作映射中的键，并且很难有效地支持它们:它们是可变长度的，长时散列和比较效率低，复制成本高，等等。StringMap是一个专门用于处理这些问题的容器。它支持将任意字节范围映射到任意其他对象。

StringMap实现使用一个按四次探查的散列表，其中bucket存储指向分配给堆的条目的指针(以及其他一些东西)。映射中的条目必须进行堆分配，因为字符串的长度是可变的。字符串数据(key)和元素对象(value)与元素对象之后的字符串数据存储在同一个分配中。这个容器保证“(char*)(&Value+1)”指向值的键字符串。

由于以下几个原因，StringMap非常快:二次探测是非常高效缓存查找,在桶散列值的字符串不重新计算时查找一个元素,StringMap很少有接触无关的对象的内存时查找值(即使哈希碰撞发生),哈希表的增长不会再计算字符串的哈希值已经在表中,并在地图中每一对是存储在一个单一的分配(字符串数据存储在相同的分配价值的一对)。

StringMap还提供了接受字节范围的查询方法，因此只有在将值插入表中时，它才会复制字符串。

但是，不能保证StringMap迭代顺序是确定的，因此任何需要使用std::map的使用都应该使用std::map。

llvm/ADT/IndexedMap.h

IndexedMap是一个专门的容器，用于将小密集整数(或可映射到小密集整数的值)映射到其他类型。它在内部实现为一个向量，带有一个映射函数，该函数将键映射到密集整数范围。

这对于LLVM代码生成器中的虚拟寄存器之类的情况非常有用:它们有一个密集的映射，而编译时常量(第一个虚拟寄存器ID)可以抵消这个映射。

llvm/ADT/DenseMap.h

DenseMap是一个简单的二次探测哈希表。它擅长支持小键和值:它使用一个分配来保存当前插入到映射中的所有对。DenseMap是将指针映射到指针，或者将其他小类型映射到其他小类型的好方法。

但是，您应该注意到DenseMap的几个方面。与map不同，每当插入发生时，DenseMap中的迭代器都会失效。此外，由于DenseMap为大量键/值对分配空间(默认从64开始)，如果键或值很大，则会浪费大量空间。最后，如果还不支持DenseMapInfo，则必须为所需的键实现DenseMapInfo的部分专门化。这需要告诉DenseMap关于它内部需要的两个特殊标记值(永远不能插入到映射中)。

DenseMap的find_as()方法支持使用备用键类型进行查找操作。这在构造普通键类型很昂贵，但与之相比很便宜的情况下非常有用。DenseMapInfo负责为所使用的每个备用键类型定义适当的比较和散列方法。

llvm/IR/ValueMap.h

ValueMap是围绕DenseMap将值*s(或子类)映射到另一类型的包装器。当一个值被删除或RAUW ‘ed时，ValueMap将更新自己，以便将键的新版本映射到相同的值，就像键是WeakVH一样。通过将配置参数传递给ValueMap模板，您可以准确地配置这是如何发生的，以及这两个事件上还会发生什么。

llvm/ADT/IntervalMap.h

IntervalMap是用于小键和值的紧凑映射。它映射键间隔而不是单个键，并将自动合并相邻的间隔。当映射只包含几个间隔时，将它们存储在映射对象本身以避免分配。

IntervalMap迭代器非常大，因此不应该将它们作为STL迭代器传递。重量级迭代器允许较小的数据结构。

map具有与std::set相似的特性:它为插入到map中的每对数据使用一个分配，它提供了log(n)查找和一个非常大的常量因子，并对map中的每对数据施加3个指针的空间惩罚，等等。

map在键或值非常大时最有用，如果需要按排序顺序迭代集合，或者需要在map中使用稳定的迭代器(即，如果插入或删除另一个元素，它们不会失效)。

llvm/ADT/MapVector.h

MapVector<keyt,valuet>提供了DenseMap接口的子集。</keyt,valuet>主要的区别是迭代顺序保证为插入顺序，这使得它对于指针映射上的非确定性迭代是一种简单(但有些昂贵)的解决方案。

它是通过将键映射到键值对向量中的索引来实现的。这提供了快速查找和迭代，但有两个主要缺点:密钥存储两次，删除元素需要线性时间。如果需要删除元素，最好使用remove_if()批量删除它们。

llvm/ADT/IntEqClasses.h

IntEqClasses提供了小整数等价类的紧凑表示。最初，0…范围内的每个整数。n-1有它自己的等价类。可以通过将两个类代表传递给join(a, b)方法来联接类。当findLeader()返回相同的代表时，两个整数位于同一个类中。

一旦所有等价类都形成，映射就可以被压缩，因此每个整数0…n-1映射到范围为0的等价类数。m-1，其中m为等价类的总数。地图必须解压后才能重新编辑。

llvm/ADT/ImmutableMap.h

ImmutableMap是一个基于AVL树的不可变(函数)映射实现。添加或删除元素是通过一个工厂对象完成的，并会创建一个新的ImmutableMap对象。如果给定密钥集已经存在一个ImmutableMap，则返回现有的密钥集;将等式与FoldingSetNodeID进行比较。添加或删除操作的时间和空间复杂度与原始映射的大小成对数关系。

Other Map-Like Container Options

STL提供了其他几个选项，比如std::multimap和各种“hash_map”，比如容器(无论是来自c++ TR1还是来自SGI库)。我们从不使用hash_set和unordered_set，因为它们通常非常昂贵(每次插入都需要一个malloc)，而且非常不可移植。
如果您想将键映射到多个值，则使用multiap非常有用，但是它具有std::map的所有缺点。排序向量或其他方法几乎总是更好的。

位存储容器(BitVector, SparseBitVector)

与其他容器不同，只有两个位存储容器，选择何时使用每个位存储容器相对比较简单。

一个额外的选项是std::vector:我们不鼓励使用它，原因有两个:1)许多通用编译器(例如通用可用的GCC版本)中的实现非常低效;无论如何，请不要使用它。

BitVector

位向量容器为操作提供了一组动态大小的位。它支持单独的位设置/测试，以及设置操作。set操作花费时间O(位向量的大小)，但是操作一次执行一个单词，而不是一次执行一个位。与其他容器相比，这使得用于set操作的位向量非常快。当您期望集位的数目很高(即密集集)时，使用位向量。

SmallBitVector

SmallBitVector容器提供了与BitVector相同的接口，但是它针对只需要少量位(少于25位)的情况进行了优化。它还透明地支持较大的位计数，但效率略低于普通位向量，因此，SmallBitVector只应在很少使用较大的计数时使用。

此时，SmallBitVector不支持set操作(and, or, xor)，其操作符[]不提供可分配的lvalue。

SparseBitVector

SparseBitVector容器非常类似于BitVector，但有一个主要的区别:只存储设置的位。这使得稀疏位向量在集合稀疏时比位向量的空间效率更高，并且使得集合操作O(集合位的数量)而不是O(宇宙的大小)。SparseBitVector的缺点是，随机位的设置和测试是O(N)，对于较大的SparseBitVector，这可能比BitVector慢。在我们的实现中，按顺序设置或测试位(向前或向后)是O(1)最坏的情况。测试和设置128位内的位(取决于大小)的当前位也是O(1)。一般来说，在稀疏位向量中测试/设置位是O(到最后一个设置位的距离)。