1.什么是STL

STL英文全称(standard template library)，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。

       STL最初由惠普实验室开发，于 1998 年被定为国际标准，正式成为 C++ 程序库的重要组成部分。值得一提的是，如今 STL 已完全被内置到支持 C++ 的编译器中，无需额外安装，这可能也是 STL 被广泛使用的原因之一。

       STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，STL 基本上达到了各种存储方法和相关算法的高度优化。

STL包含容器（Containers）分配器（Allocators）算法（Algorithm）迭代器（Iterators）适配器（Adapters）仿函数（Functors）6个部分，我们重点掌握容器，迭代器和算法就可以。

2.容器

2.1 顺序式容器

顺序式容器包括vector,list,deque,queue,priority_queue,stack等

• vector：动态数组，从末尾能快速插入与删除，直接访问任何元素

• list: 双链表,从任何地方快速插人与删除。

• deque: 双向队列,从前面或后面快速插人与删除,直接访问任何元素。

• queue:队列,先进先出。

• priority_queue: 优先队列,最高优先级元素总是第一个出列。

• stack:栈，后进先出。

2.2 关联式容器

• 关联式容器包括 set、multiset、map、multimap 等。

• set:集合，快速查找,不允许重复值。

• multiset: 快速查找，允许重复值。

• map:一对一映射,基于关键字快速查找,不允许重复值,。

• multimap:一对多映射,基于关键字快速查找,允许重复值。

3.迭代器

stl模板中算法和容器是分离的。

我们对容器最常做的操作就是遍历容器中的元素，对于不同的容器，其内部的结构各异，但是它们本质上都是一串存储数据的存储单元，所以每种算法对数据的遍历操作是类似的，我们使用泛型技术将遍历方法设计成适合所有容器的通用算法，从而将容器和算法分离开。

简单来讲，迭代器和C++的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

4.算法

algorithm是C++标准程序库中的一个头文件，定义了C++ STL标准中的基础性的算法(均为函数模板)。定义了设计用于元素范围的函数集合。任何对象序列的范围可以通过迭代器或指针访问。

5.应用

5.1 各容器的使用特点总结

• vector 头部与中间插入和删除效率较低，在尾部插入和删除效率高，支持随机访问。

• deque 是在头部和尾部插入和删除效率较高，支持随机访问，但效率没有 vector 高。

• list 在任意位置的插入和删除效率都较高，但不支持随机访问。

• set 由红黑树实现，其内部元素依据其值自动排序，每个元素值只能出现一次，不允许重复，且插入和删除效率比用其他序列容器高。

• map 可以自动建立 Key - value 的对应，key 和 value 可以是任意你需要的类型，根据 key 快速查找记录。

5.2 在实际使用过程中建议

• 如果需要高效的随机存取，不在乎插入和删除的效率，使用 vector。

• 如果需要大量的插入和删除元素，不关心随机存取的效率，使用 list。

• 如果需要随机存取，并且关心两端数据的插入和删除效率，使用 deque。

• 如果打算存储数据字典，并且要求方便地根据 key 找到 value，一对一的情况使用 map，一对多的情况使用 multimap。

• 如果打算查找一个元素是否存在于某集合中，唯一存在的情况使用 set，不唯一存在的情况使用 multiset。

5.3各容器的时间复杂度分析

• vector 在头部和中间位置插入和删除的时间复杂度为 O(N)，在尾部插入和删除的时间复杂度为 O(1)，查找的时间复杂度为 O(1)；

• deque 在中间位置插入和删除的时间复杂度为 O(N)，在头部和尾部插入和删除的时间复杂度为 O(1)，查找的时间复杂度为 O(1)；

• list 在任意位置插入和删除的时间复杂度都为 O(1)，查找的时间复杂度为 O(N)；

• set 和 map 都是通过红黑树实现，因此插入、删除和查找操作的时间复杂度都是 O(log N)。