C++ STL相关容器详解

C++ STL相关容器详解

vector：

一种随机访问的数组类型，他提供了对数组元素的快速、随机访问，以及在序列尾部快速、随机的插入和删除操作。它在需要时可以改变其大小，也就是说大小可变的向量，比较灵活。可取代C++语言本身提供的传统数组。提供随机存储能力。操作尾端元素的速度最快。由于所有元素占用连续空间，所以一旦进行插入或者删除动作，有可能使原本的某些 iterators失效。

list:

这是一个双向链表容器，完成了标准的C++数据结构中链表的所有功能。它不支持随机访问的数组类型，因为STL以双向链表的方式实现list对象，所以访问链表元素要指针从链表的某个端点开始。插入和删除操作所花的时间是固定的，也就是说，list对象插入和删除一个元素所需要的时间与该元素在链表中的位置无关。在任何位置做插入和删除动作都很快，不像vector只局限于尾端，而deque只局限于两端才有高效率。由于各元素并不占用连续空间，所以一旦进行插入或者删除动作，原本的iterators任然有效。注意，许多只在元素搬移的STL algorithms用于list身上会有不佳的效率。幸好这些STL algorithms 都有对应的list member functions 可以替代。后者之所以会有比较好的效率，原因是他们只操作指标，而非真正去拷贝或者移动元素。

queue:

这是一种队列容器，它采用deque和list对象创建一个先进先出(FIFO)的容器，它实际上完成了标准的C++数据结构中的队列所有功能。不提供随机存储能力。行为与特性都很类似vector，但因为是双向开口，所以操作两端元素的速度都很快，不像vectoer只在操作尾端元素时才有高效率。由于所有元素占用连续空间，所以一旦进行插入或者删除动作，有可能是原本的某些iterators失效。

stack:

这是一种栈容器，完成了标准的C++数据结构中栈的所有功能。也就是说，它通过vector、deque或者list对象创建了一个先进后出的容器。stack特性是先进后出(FILO: First In, Last Out)。

deque:

这是一种随机访问的数据类型，提供了在序列两端快速插入和删除操作的功能，他可以再需要的时候修改器自身大小。也就是说这是一种双端队列容器，完成了标准的C++数据结构中队列的所有功能。queue特性是先进先出。

priority_queue:

这是一种按值排序的队列容器。它使用vector或者deque对象创建了一个排序队列。priority_queue特性是依优先权来谁是下一个元素。

set:

这是一种随机存取的集合容器。其关键词和数据元素是同一个值，也就是说它不能包含重复的元素。set经过排序的结构体，以某个可指定的排序方式排序，每个元素第一无二。由于已经排序，所以搜寻速度极快。但也因此不允许我们直接修改某个元素的内容，因为这可能会影响排序。修改元素内容的正确的作法是，先将该元素删除，再加入（此时使用新值）。set通常是以平衡二叉树(balanced binary tree)来存储（但并不是强制规定），甚至是以red-black trees来完成。

multiset:

其关键词和数据元素也是同一个值，但和set不同的以及最大的区别在于这是一种允许出现重复元素的集合容器。multiset允许元素重复。

map:

其是一种关联数组容器，它包含成对数据的容器，其中一个值是实际数据值，另外一个是用来寻找数据的关键值，一个特定的关键词只能与一个元素相关联。map是由一对一对的键值（key/value）所组成的排序结构体，键值独一无二。map通常是以balanced binary tree来实现，但并不强制规定。事实上map的内部结构通常与set是一样的，因此我们可以将set视为一种特殊的map，其键值和实值是相同的，所以map和set几乎拥有完全相同的能力。

multimap:

这是一种允许出现重复关键之的关联数组容器，然而与map对象不同，它的一个关键词可以与多个元素相联系，multimap允许键值重复。

hash table:

这并不是C++ Standard规范内的一容器（因标准委员会作业时间的关系），但是它对于大量数据的搜索而言，很实用也很重要。有许多STL实作品例如SGI都涵盖了它。通常STL产品厂商会提供4中hash tables: hash_set、hash_multiset、hash_map、hash_multimap。