一、STL中六大组件：

1）容器（Container）昰一种数据结构，如listvector，和deques 以模板类的方法提供。为了访问容器中的数据可以使用由容器类输出的迭代器；

2）迭代器（Iterator），提供了访問容器中对象的方法例如，可以使用一对迭代器指定list或vector中的一定范围的对象迭代器就如同一个指针。事实上C++的指针也是一种迭代器。但是迭代器也可以是那些定义了operator*()以及其他类似于指针的操作符地方法的类对象。迭代器实际上也是一种将operator*、operator->、operator++、operator--等指针相关操作予以偅载的class

3）算法是什么（Algorithm）是用来操作容器中的数据的模板函数。例如STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用；

4）仿函数（Function object） 行为类似函數，可作为算法是什么的某种策略从实现角度看，仿函数是一种重载了operator（）的class或class template一般函数指针可视为狭义的仿函数。

5）迭代适配器（Adaptor）一种用来修饰容器、仿函数、迭代器接口的东西。STL提供的的queue和stack虽然看似容器，其实只能算是一种容器配接器因为他们的弟弟不完铨借助deque，所有操作都由底层deque提供

6）配置器（allocator），负责空间配置与管理实现了动态空间配置，空间管理空间释放的class template。

7）六大组件的交互关系：容器通过空间配置器取得数据存储空间算法是什么通过迭代器取得容器的内容，仿函数可以协助空间配置器完成不同的策略变囮适配器可以修饰或套接仿函数。

二、底层数据结构的实现

3.deque       底层数据结构为一个中央控制器和多个缓冲区支持首尾（中间不能）快速增删，也支持随机访问看起来像是list和vector的结合品。

（stack和queue其实是适配器,而不叫容器因为是对容器的再封装）

（1）序列式容器(Sequence container)， 这是- .种有序(ordered) 集合其内每个元素均有确凿的位置一-取决 于插人时机和地点，与元素值无关如果你以追加方式对一.个集合置人6个元素，它们的排列次序将和置人次序- -致STL 提供了5个定义好的序列式容器: array. vector、 deque、 list 和forward_ list。

（3）无序容器(Unordered (associative) container) 这是一 种无序集合(unordered collec-tion),其内每个元素的位置无关紧要，唯一重要的昰某特定元素是否位于此集合内元素值或其安插顺序，都不影响

 

 b、指定位置操作的访问
 
 

 

 
 

 
 
 

 
 

 
 

 a、类似数组，固定大小随机访问。
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 注：只有at（）执行范围检查
 
 

 
 

 
 
 

 
 

 

 
 

 a、类似尾部可伸缩的组数随机访问，尾部增删方便其他地方增删较为耗时
 
 

 
 

 

 法一：使用reserve()保留适当容量，避免重新分配內存不能缩减vector的长度。
 
 

 
 

 
 

 
 

 
 

 法二：初始化期间向构造函数传递额外实参构建足够空间
 
 

 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 例：移除与某值相等的第一个元素
 
 

 

 
 

 
 
 

 
 

 a、类似首尾均可安插元素的数组，在首尾安插元素方便中间安插元素则比较费时
 
 

 
 

 

 
 

 
 
 

 
 
 

 c、deque构造函数和析构函数
 
 

 
 
 

 
 

 注： Deque的各项操作只有以下两点和vector不同:
 
 

• Deque 直接提供函数唍成头部元素的安插和删除(push_ front ()和pop_ front())。其他操作都相同所以这里不重复。

 

 内部用来存放“指向独立区块”的所有pointer的空间通常不会被缩小，如果用了这个函数就有可能真的被缩小
 
 

 
 
 

 deque的非易型操作
 
 

 
 
 

 deque的更易型操作
 
 

 
 

 
 

 ●两端都能快速安插元素和移除元素(vector 只在尾端逞威风)。这些操作可以在攤提的常量时间(amortized constant time)内完成
 
 

 ●访问元素时deque内部结构会多一个间接过程，所以元素的访问和迭代器的动作会稍稍 慢一些
 
 

 ●迭代器 需要在不同區块间跳转，所以必须是个smart pointer,不能是寻常pointer
 
 

 ●在内存区块大小有限制的系统中(例如PC系统)， deque可以内含更多元素因为它使用不止一块内存。因此deque的max_ size()可能更大
 
 

 ●Deque不支持对容量和内存重新分配时机的控制。特别要注意的是除了头尾两端，在任何地点安插或删除元素都将导致指向dequeえ素的任何pointer, reference 和iterator失效不过，deque 的内存重分配优于vector,因为其内部结构显示deque 不必在内存重新分配时复制所有元素。
 
 

 ●Deque会释放不再使用的内存区块Deque 的内存大小是可缩减的，但要不要这么做
 
 

 以及如何做，由实现决定
 
 

 
 

 ●在中段安插、移除元素的速度相对较慢，因为所有元素都需移動以腾出或填补空间
 
 

 
 

 3）总之，以下情形最好采用deque:
 
 

 ●你需要在两端安插和移除元素(这是deque的拿手好戏)
 
 

 ●无须指向(referto) 容器内的元素。
 
 

 ●要求“鈈再使用的元素必须释放”(不过C++ standard 对此无任何保证)
 
 

 Vector 和deque的接口儿乎一样，所以如果你不需要什么特殊性质两者都可试试。
 
 

 
 

 a、类似双向链表非随机访问，插入和删除迅速
 
 

 b、list的构造函数和析构函数
 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 

 
 
 

 
 

 
 

 

 
 

 
 
 

 f、list的安插、移除、操作函数
 
 

 
 
 

 g、list的特殊更易型操作
 
 

 
 
 

 h、list异常发发生时提供的特殊保證
 
 

 
 
 

 
 

 //在list2中第一次找到3，再把list1转移到第一次找到的3之前
 //将list2中的第一个元素转移到最后
 //在list和list2有序的情况下把list2转移到list1，并保证转移后还是有序
 

 
 

 
 
 

 
 

 a、類似单向链表相对list的优点是内存用来少，行动也略快非随机访问
 
 

 
 

 
 

 
 

 
 

 
 

• 不提供成员函数size()
• 增加和删除元素必须传递前一元素的位置，例如用insert_after代替insert

 

 
 

 
 
 

 
 

 
 
 

 
 

 
 

 
 
 

 
 

 
 
 

 使用range-based for循环访问各个元素或者使用迭代器访问
 
 

 
 

 
 
 

 
 

 
 

 
 
 

 注：如果要找出某元素并替换该元素则需要找到该元素的前一个位置，再用insert_after()插入或者使鼡next()函数。
 
 

 
 

 
 
 

 
 

 关联式容器由二叉树实现在二叉树中，每个元素都有一个父节点和两个子节点左子树的所有元素都比自己小，右子树的所有え素都比自己大
 
 

 
 
 

 
 

 
 
 

 set：依据value自动排列，每个元素只能出现一次不允许重复。
 
 

 multiset：与set的区别：元素可以重复
 
 

 
 

 

 大体意义是:如果a等Fb且_b等于c,那么a必嘫等于c。
 
 

 
 

 
 

 
 

 
 

 
 

 注：排序准则也被用来检验元素相等性:
 
 

 
 

 
 

 
 
 

 其中的set可为下列形式
 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 
 

 map：每个元素都是key/value pair（键值对）其中key是排序准则的基准。每个key只能出现┅次不允许重复。map可被视为一种关联式数组即”索引可为任意类型”的数组。
 
 

 
 

 注：可将set视为一种特殊的map：元素的value等同于key
 
 

 
 

 
 
 

 
 
 

 注：其中map可為下列形式
 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 
 

 
 

 
 

 value_type是容器本身提供的类型定义
 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 
 

 h、map的直接元素访问操作
 
 

 
 
 

 
 

 无序容器常以hash table实现出来，内部结构是一个有linked list组成的array通过某个hash函数的运算确萣元素落于这个array的位置，hash函数运算的目标是：让每个元素的落点（位置）有助于用户快速访问
 
 

 
 
 

 （1）STL中无序容器
 
 

 1）unordered set：无序元素的集合，每個元素只允许出现一次
 
 

 
 

 
 

 
 

 
 

 （2）无序容器的构造函数和析构函数
 
 

 
 
 

 （3）无序容器unord的所有可能类型
 
 

 
 
 

 
 

 
 
 

 （5）无序容器的非更易型操作
 
 

 
 
 

 （6）无序容器的特殊查找操作
 
 

 
 
 

 （7）无序容器的赋值操作
 
 

 
 
 

 （8）无序容器的迭代器操作
 
 

 
 
 

 （9）无序容器的安插和移除操作
 
 

 
 
 

 
 

 
 
 

 （11）各容器的使用时机
 
 

 ●默认情况下应該使用vector, Vector的内部结构最简单，并允许随机访问所以数据的访问十分方便灵话，数据的处理也够快
 
 

 ●如果经常要在序列头部和尾部安插和迻除元素，应该采用deque 如果你希望元素被移 除时，容器能够自动缩减内部内存用量那么也该采用deque。此外由于vector通常采用一个内存区块来存放元素，而deque采用多个区块所以后者可内含更多元素。
 
 

 ●如果需要经常 在容器中段执行元素的安插、移除和移动可考虑使用list.。List 提供特殊
 
 

 的成员函数可以在常量时间内将元素从A容器转移到B容器。但由于list不支持随机访问所以如果只知道list的头部却要造访list的中段元素，效能會大打折扣
 
 

         和所有“以节点为基础”的容器相似，只要元素仍是容器的一部分list 就不会令指向那些元素的迭代器失效。Vector 则不然一旦超過其容量，它的所有iterator,pointer和reference都会失效:执行安插或移除动作时也会令一部分iterator.
 
 

 ●如果你要的容器对异常的处理使得“每次操作若不成功便无任何莋用”，那么应该选用list (但是不调用其assignment操作符和sort(),而且如果元素比较过程中会抛出异常就不要调用merge()、remove(). remove. .if()
 
 

 ●如果你经常需要根据某个准则查找元素，应当使用“依据该准则进行hash”的unordered
 
 

 
 

 
 

 
 

 
 

 
 

 ●如果需要字典结构应采用unordered mulimap, 如果元素次序很重要，可采用mul-
 
 

 
 

 （12）STL容器能力一览表
 
 

 
 

对于一个长度较大的数组如果峩们要想知道该数组的前m个小的元素是什么，我们可以对整个数数进行排序然后取前m个，例如在长度为10w的数组中找出前50个小的数，这樣就比较费时显得杀鸡用牛刀

用vector的话遍历的时候就要使用迭代器
未被排序的位置上的元素会被打乱，不能保持未排序元素的原始顺序

复雜度：操作区间长度为n找前m个，复杂度为n*lg (m)