STL- 容器特点总结

关于 STL

• STL即标准模板库（Standard Template Library）。
• STL包含 6大组件+13个头文件。

  六大组件：容器、算法、迭代器、仿函数、适配器、分配器
  这六大组件的交互关系：
     container（容器） 通过 allocator（配置器） 取得数据储存空间。
     algorithm（算法）通过 iterator（迭代器）存取 container（容器） 内容。
     functor（仿函数） 可以协助 algorithm（算法） 完成不同的策略变化。
     adapter（配接器） 可以修饰或套接 functor（仿函数）。

• 通常来说 STL 的核心三个组件是容器、算法、迭代器。这三个组件包含了诸多常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。
   

1. 序列式容器

• 特点: 元素在容器中的位置与元素的值无关，将元素插入容器时，指定在什么位置，元素就会位于什么位置。
• 序列是容器有: array、vector、deque、list、forward_list

 
 I. vector

• 采用连续存储结构，底层通过数组实现，当内存空间不够时，会重新申请一块足够大的内存，把旧内存空间中的所有元素都拷贝进新内存空间中去，同时释放旧的空间。GCC是二倍扩容，VS13是1.5倍扩容
   
• 插入: push_back、emplace_back，复杂度O(1)；
      insert、emplace，复杂度O(N)；
• 删除: pop_back，复杂度O(1)；
      erase，复杂度O(N)；
• 存取: operator=、at、front、back，复杂度O(1)；

 II. deque

• deque双端队列，底层采用多个连续的存储块，在一个映射结构中对这些内存块及顺序进行跟踪。
   
• 插入: push_back、push_front、emplace_back、emplace_front，复杂度O(1)；
      insert、emplace，复杂度O(N)；
• 删除: pop_back、pop_front，复杂度O(1)；
      erase，复杂度O(N)；
• 存取: operator=、at、front、back，复杂度O(1)；

 III. list

• List使用非连续的内存空间进行存储，具有双链表结构，不支持根据下标随机存取元素。
   
• 插入: push_back、push_front、emplace_back、emplace_front、insert、emplace，复杂度O(1)；
• 删除: pop_back、pop_front、erase，复杂度O(1)；
      remove、remove_if、unique，复杂度O(N)；
• 存取: front、back， 复杂度O(1)；
      查找元素需要遍历容器，复杂度O(N)；

2. 关联式容器

• 特点: 当元素被插入到关联式容器中时，元素位置取决于容器内部特定规则的排序准则以及元素值，和插入次序无关
• 序列是容器有: set、unordered_set、multiset、unordered_multiset 以及 map、unordered_map、multimap、unordered_multimap。

 
 I. set

• set内部采用红黑树实现，容器内部的数据都是有序的，容器中元素的值不能在容器进行修改，但可以对元素进行插入、删除操作。元素值本身val 就是键-key。因此容器中元素是唯一的。
   
• 插入: insert、emplace、emplace_hint，复杂度O(logN)；
• 删除: erase，复杂度O(logN)；
• 查询: find、count，复杂度O(logN)；

 II. unordered_set

• unordered_set内部基于哈希表实现，容器内部的数据都是无序的，容器中元素的值不能在容器进行修改，但可以对元素进行插入、删除操作。元素值本身val 就是键-key。因此容器中元素是唯一的。
   
• 插入: insert、emplace、emplace_hint，复杂度O(1)；
• 删除: erase，复杂度O(1)；
  查询: find、count，复杂度O(1)；

 III. map

• map内部采用红黑树实现，容器内部元素是有序的，且元素都是成对出现，.first 是关键字(key)，容器中key具有唯一性。.second是该关键字的值(value)
   
• 插入: insert、emplace、emplace_hint，复杂度O(logN)；
• 删除: erase，复杂度O(logN)；
• 查询: find、count，复杂度O(logN)；

 
 Ⅳ. unordered_map

• unordered_map内部基于哈希表实现，容器内部元素无序，且元素都是成对出现，.first 是关键字(key)，容器中key具有唯一性。.second是该关键字的值(value)。
   
• 插入: operator[]、insert、emplace、emplace_hint，复杂度O(1)；
• 删除: erase，复杂度O(1)；
• 访问: find、count、at、operator[]，复杂度O(1)；

3. 容器适配器

• 特点: 容器适配器是一个封装了序列容器的类模板，它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配容器现有的接口来提供不同的功能。
• 序列是容器有:
• stack:是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入后出（LIFO）的压入栈。
• queue:是一个封装了 deque<T> 容器的适配器类模板，默认实现的是一个先入先出（LIFO）的队列。可以为它指定一个符合确定条件的基础容器。
• priority_queue:是一个封装了 vector<T> 容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。

 
 I. stack

• stack是一个先进后出（FILO）的容器，故stack不提供元素的任何迭代器操作。容器只能从容器的一端（栈顶）进行插入、删除、访问操作。
   
• 插入: insert、emplace，复杂度O(1)；
• 删除: pop，复杂度O(1)；
• 查询: top，复杂度O(1)；

 II. queue

• queue是一个先进先出（FIFO）容器适配器，故 queue 不提供元素的任何迭代器操作。容器只能访问头元素和为元素。只能在容器的末尾添加新元素，只能从头部移除元素。
   
• 插入: push、emplace，复杂度O(1)；
• 删除: pop，复杂度O(1)；
  查询: front，复杂度O(1)；

 III. priority_queue

• priority_queue内部保持堆结构（其内部默认是大顶堆），容器内部元素是有序的，容器只能访问头元素top()。只能在容器的末尾添加新元素，只能从头部移除元素。
   
• 插入: emplace、push，复杂度O(1)；
• 删除: pop，复杂度O(1)；
• 查询: top，复杂度O(1)；