标准库的归总

• 基于对象告诉我们要将函数和数据封装到一个类里，但标准库数据和算法是分离的，是不同的思想
• 数据结构+算法 —》 增删改查
  

容器 容器的共通能力和共通操作

1. 所有容器提供的都是“value语意”而非“reference语意”
   容器进行元素的安插操作时，内部实施的是拷贝操作，置于容器内。因此STL容器的每一个元素都必须能够被拷贝。如果你打算存放的对象不具有public copy构造函数，或者你要的不是副本（例如你要的是被多个容器共同容纳的元素〉，那么容器元素就只能是指针（指向对象）。
2. 根据迭代器获取元素
3. 调用者需保证传给操作函数的参数符合要求
4. swap仅是指针的交换（start,finish,end_of_storage）

顺序容器

• 元素按照放入顺序，容器有顺序之分

vector

• 支持随机存取
• 迭代器是随机存取迭代器，对任何一个STL算法都支持
• 末端添加或删除效率高，前端或中端改动元素效率一般
• vector优异性能的秘诀之一，就是配置比所容纳元素所需更多的容量。
• 一旦扩容vector元素相关所有reference、pointers、iterators都会失效
• 在很多版本中的vector，当你第一次安插元素时其就会一口气配置一大块内存(例如2K),所以如果你有一大堆vector，而每个vector的实际元素却寥寥无几，那么浪费的内存会相当多
• 既然vectors 的容量不会缩减，我们便可确定，即使删除元素，其references、pointers、iterators也会继续有效，继续指向动作发生前的位置。然而安插操作却可能使references、 pointers 、 iterators 失效
• swap修改的是指针（start、finish、end_of_storage），迭代器等会失效

capacity() 返回vector实际能够容纳的元素数量，等于end_of_storage - start 如果超越该数，即会发送扩容
reserve() 设置适当容量，其改变了end_of_storage的指向，reserve设置比当前size，则无事发生
std::vector(v).swap(v);  //可用于缩减容量

deque

• deque 的接口和vector几乎一样

一般与vector比较

• 两端都能快速修改元素
• 存取元素，deque内部结果会多一个中间过程，所以元素的存取和迭代器的动作会稍微慢一点
• 迭代器需要在不同的区块间跳转，所以必须是特殊的智能型指针，而非一般指针
• 迭代器属于random aceess iterator
• deque使用不止一块内存
• deque 的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。不过,是不是这么做,以及究竟怎么做，由实作版本定义之。

list

• list是一个带头节点的循环双向链表

关联容器

• 通过key，快速关联（搜寻）value
• 查找，结构从二叉树和哈希表出发

set

key不会重复

• 其底层是一个red-black tree
  红黑树在改变元素数量和元素搜寻方面很出色，它保证节点安插时最多只会做两个重新连接（调整），而且到达某一元素最长路径深度，最多只是最短路径深度的两倍。且自动排序使得二叉树搜寻函数算法具有对数复杂度
• 但是，自动排序造成sets和multisets的一个重要限制：你不能直接修改元素，因为这样会打乱原本正确的顺序。
  因此，要改变元素值，必须先删除旧元素，再插入新元素。
  

map

• key不会重复，key-value对应到数据库 key就是主键（不重复），value就是一个包含事物信息的结构体
  
• 根据key的排序准则自动将元素排序
• set，multisets,map，multimaps使用相同的数据结构，可以将set，multisets分别视为特殊的map和multimaps，其拥有set，multisets所有能力和操作函数

map和multimap

• map key不能重复，multimap key可以重复，其有自己的操作函数来处理管理重复的key对应的value区间
  

大数据容器移动拷贝构造和拷贝构造的效率

总结

• swap仅是指针的交换
• vector为什么移动拷贝和拷贝构造效率差距如此大，只要是因为其会扩容

hashtable 哈希表（散列表）

• hashtable的设计有多种（为了处理碰撞），链表法是相对较好的一种，其对应每一栏都可有一个链表
  
• rehash 当篮子数和所放置的元素个数相同，就进行rehash
• 处理key的哈希碰撞，利用哈希函数来运算一个key的代码来尽量产生相同的key

hashfunction

4.9版本后C++内部支持的hashfunction

• 整形的key = hashcode
• G2.9不支持字符串，其在G4.9开始支持
• 以下是hashfunction的接口
  
• template struct hash{}；//表示一个泛化模板
  

一个万用的hash funtion array

• _M_intance是数组名
  
• 数组typedef int T[100]

string

• string是一个类别名–》std::basic_string的别名
• 使用了引用计数的手段，拷贝共享—》copy on write
  
  

迭代器

• value type 迭代器所指对象的类型,Iterator_traits能根据容器的迭代器，萃取出元素类型value type
• difference type 表示两个迭代器之间的距离，也可以用来表示容器的最大容量，例如count()计数功能，其传回值就必须使用迭代器的difference type
• reference type
  • 常引用
  • 普通引用
• pointer type

随机存取迭代器对任何一个STL算法的都可以凑效

区间

• 所有算法都用来处理一个或多个区间内的元素。这样的区间可以(但非强行要求)涵盖容器内的全部元素。因此,为了得以操作容器元素的某个子集，我们必须将区间首尾当做两个参数传给算法，而不是一口气把整个容器传递进去。
• 用户必须确保两参数定义出来的区间是有效的，两个迭代器隶属同一个容器，而且前后放置正确（迭代器就像一般指针一样危险）
• 所有的算法处理都是半开区间 [ begin,end) ----- 包括起始元素位置但不包括末尾元素位置。其可避免对空集的另做处理。空集时begin=end

处理多个区间

有数个算法可以(或说需要）同时处理多个区间。
通常你必须设定第一个区间的起点和终点，至于其它区间，你只需设定起点即可，终点通常可由第一区间的元素数量推导出来。

谓词 算法 算法接口中的谓词参数

• 一元谓词参数是从区间中逐个取出
• 二元谓词参数

仿函数 其他补充 右值

STL中一般很少有人提及右值，但右值引用其是STL标准库效率提升的利器，如下

https://editor.csdn.net/md?articleId=121025037

noexcept

• vector容器的元素类的移动拷贝和移动赋值需要noexcept修饰