vector向量容器
底层数据结构：动态开辟的数组，每一次以原来空间大小的2倍进行扩容
增加
代码语言：javascript复制vector<int> vec;
vec.push_back(20);//末尾添加元素，时间复杂度O(1)
vec.insert(it,20);//it迭代器指向的位置添加一个元素20，时间复杂度O(n)
//这两种增加方式会导致容器的扩容删除
代码语言：javascript复制vec.pop_back();//末尾删除元素O(1)
vec.erase(it);//删除迭代器指向的元素O(n)查询
代码语言：javascript复制operator[]//下标随机访问·O(1)
iterator迭代器进行遍历
find，for_each
foreach =也是通过迭代器来实现的注意：对容器进行连续插入或者删除操作（insert/erase）一定要更新迭代器，否则第一次insert/erase后，迭代器就会失效
常用方法介绍
代码语言：javascript复制size()
empty()
reserver(20); ：vector预留空间的，只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：容器扩容，不仅给容器开辟指定的大小内存空间，还会添加新的元素
swap:两个容器进行元素交换deque双端队列
底层数据结构是动态开辟的二维数组 一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组从新的第一维数组下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加
增加
代码语言：javascript复制deque<int> que;
que.push_back(20);//从末尾添加元素 O(1)
que.push_front(20);//从首部添加元素O(1)
que.insert(it,20);//it指定的位置添加元素由于deque的第二维内存空间不是连续的，所以在deque中间进行元素的insert或者erase，造成元素移动的时候比vector要慢。
删除
代码语言：javascript复制que.pop_back();//从末尾删除元素O(1)
que.pop_front();//从首部删除元素O(1)
que.erase(it);//从it指向的位置删除元素O(n)查询
代码语言：javascript复制iterator（连续的insert/erase一定要考虑迭代器失效问题）list容器
底层数据结构：双向的循环链表 pre data next
增加
代码语言：javascript复制list<int>mylist;
mylist.push_back(20);//从末尾添加元素O(1)
mylist.push_front(2);//从首部添加元素O(1)
mylist.insert(it,20);//it指向的位置添加元素O(1)，链表中进行insert时先要进行一个query查询操作，对于链表来说，查询的操作效率就比较慢了。删除
代码语言：javascript复制mylist.pop_back(20);//从末尾删除元素O(1)
mylist.pop_front(2);//从首部删除元素O(1)
mylist.erase(it,20);//it指向的位置删除元素O(1)，查询
代码语言：javascript复制iterator连续的inseert和erase一定要考虑迭代器失效问题deque和list，比vector容器多出来了增加删除函数的接口：push_front ，pop_front
特点
- vector特点：动态数组，内存是连续的，2倍的方式进行扩容，vectorvec;0-1-2-4-8…
- deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间。扩容的时候（第一维的数组进行2倍扩容）
- 问题：deque底层内存是否连续？答案：不是，每一个第二维是连续的
vector和deque之间的区别？
- 底层数据结构不同
- 前中后插入删除元素的时间复杂度：中间和末尾都是O(1)，vector对于前面的时间复杂度是O(n),deque对于前面的时间复杂度是O(1)
- 对于内存的使用效率：vector需要的空间是连续的，deque可以分块进行数据存储，不必须是连续的内存空间
- 对于中间进行insert或者erase：vector的效率要高于deque。因为deque不是连续的内存空间，删除/插入元素，相对复杂
f
- satck ：push入栈 pop出栈 top查看栈顶元素 empty判断栈空 size返回元素个数
- queue：push入队 pop出队 front查看队头元素 back查看队尾元素 empty判断队空 size返回元素个数 stack依赖于deque queue依赖于deque 问题来了，为什么他们不依赖于vector？？？
- 对于vector的初始内存使用效率太低，没有deque好 vectorvec;0-1-2-4-8… deque是4096/sizeof（int） = 1024
- 对于queue来说，需要支持尾部插入，头部删除时间复杂度是O(1)，如果依赖于vector，出队效率会贬低
- vector需要大片连续的空间内存，而deque只要分段的内存，当存储大量数据时，deque的内存利用率会更高
priority_queue: push 入队 pop出队 top查看队顶元素 empty判断队空 size返回元素个数 底层默认的数据结构是：大根堆
priority_queue依赖于vector。为什么呢? 底层默认把数据组成一个大根堆结构，在一个内存连续的数组上构建一个大根堆或者小根堆的（按照编号存储），分段的内存空间存储（编号重复）就没有意义了。
泛型算法 = template 迭代器 函数对象
- 特点一：泛型算法的参数接收的都是迭代器
- 特点二：泛型算法的参数还可以接受函数对象（c函数指针） sort find find_if binary_search for_each
- 绑定器 二元函数对象 == 一元函数对象 bind1st：把二元函数对象的operator（）的第一个形参绑定起来 bind2st：把二元函数对象的operator（）的第二个形参绑定起来
