STL简介

STL（Standard TemplateLibrary），即标准模板库，从根本上说，STL是一些“容器”的集合，这些“容器”有list、vector、set、map等，STL也是算法和其他一些组件的集合。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。

STL包含了诸多在计算机科学领域里常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming）。在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。

STL六大组件

容器（Containers）：各种数据结构，如Vector，Deque，List，Set，Map，用来存放数据，STL容器是一种Class Template,就体积而言，这一部分很像冰山载海面的比率。
算法（Algorithms）：各种常用算法，如Sort，Search，Copy，Erase，从实现的角度来看，STL算法是一种Function Templates。
迭代器（Iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”，共有五种类型，以及其它衍生变化，从实现的角度来看，迭代器是一种将：Operators*，Operator->，Operator++，Operator–等相关操作予以重载的Class Template。所有STL容器都附带有自己专属的迭代器，只有容器设计者才知道如何遍历自己的元素，原生指针（Native pointer）也是一种迭代器。
仿函数（Functors）：即函数对象，行为类似函数，可作为算法的某种策略（Policy）,从实现的角度来看，仿函数是一种重载了Operator()的Class 或 Class Template。一般函数指针可视为狭义的仿函数。
配接器（适配器）（Adapters）：一种用来修饰容器（Containers）或仿函数（Functors）或迭代器（Iterators）接口的东西，例如：STL提供的Queue和Stack，虽然看似容器，其实只能算是一种容器配接器，因为它们的底部完全借助Deque，所有操作有底层的Deque供应。改变Functor接口者，称为Function Adapter；改变Container接口者，称为Container Adapter；改变Iterator接口者，称为Iterator Adapter。配接器的实现技术很难一言蔽之，必须逐一分析。
分配器（Allocators）：即空间配置器，负责空间配置与管理，从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的Class Template。

顺序容器(vector、queue、list)

vector

vector是表示可变大小数组的序列容器，底层是内存可进行二倍扩容的数组。
和数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

deque（double-ended queue）

两端都能快速插入元素和删除元素（vector只在尾端快速进行此类操作）。
存取元素时，deque的内部结构会多一个间接过程，所以元素的存取和迭代器的动作会稍稍慢一些。
迭代器需要在不同区块间跳转，所以必须是特殊的智能型指针，非一般指针。
在对内存区块有所限制的系统中（例如PC系统），deque可以内含更多元素，因为它使用不止一块内存。因此deque的max_size()可能更大。
deque不支持对容量和内存重分配时机的控制。特别要注意的是，除了头尾两端，在任何地方插入或删除元素，都将导致指向deque元素的任何指针、引用、迭代器失效。不过，deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。
deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。

list

list就是一个带头结点的双向非循环链表，list将元素按顺序储存在链表中。
与vector相比, 访问随机元素不如vector快，随机的插入元素比vector快。
对每个元素分配空间，所以不存在空间不够，重新分配的情况。
list可以快速地在所有地方添加删除元素，但是只能快速地访问最开始与最后的元素。

关联容器（set、multiset、map、multimap）

关联容器和顺序容器的根本不同在于：关联容器中的元素是按关键字来保存和访问的，而顺序容器中的元素则是按它们在容器中的位置来顺序保存和访问的。

multiset

multiset 是排序好的集合（元素已经进行了排序），并且允许有相同的元素。
不能直接修改 multiset 容器中元素的值。因为元素被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。因此，如果要修改 multiset 容器中某个元素的值，正确的做法是先删除该元素，再插入新元素。

set

set 和 multiset 类似，差别在于set中不能有重复的元素 。multiset 的成员函数 set 中也都有。
同样不能直接修改 set 容器中元素的值。
由于不能有重复元素，所以set中插入单个元素的insert成员函数与multiset中的有所不同

multimap

multimap 的每个元素都分为关键字和值两部分，容器中的元素是按关键字排序的，并且允许有多个元素的关键字相同。
不能直接修改 multimap 容器中的关键字。因为 multimap 中的元素是按照关键字排序的，当关键字被修改后，容器并不会自动重新调整顺序，于是容器的有序性就会被破坏，再在其上进行查找等操作就会得到错误的结果。
multimap 中的元素都是pair 模板类的对象。元素的 first 成员变量也叫“关键字”，second 成员变量也叫“值”。multimap 容器中的元素是按关键字从小到大排序的。

map

map 和 multimap 十分类似，区别在于 map 容器中元素的关键字不能重复。multimap 有的成员函数，map 都有。
此外，map 还有成员函数 operator[]：T & operator[] (Key k);

该成员函数返回 first 值为 k 的元素的 second 部分的引用。如果容器中没有元素的 first 值等于 k，则自动添加一个 first 值为 k 的元素。如果该元素的 second 成员变量是一个对象，则用无参构造函数对其初始化。