【C++】深入理解和高效使用STL：从基础到高级技巧

vector向量容器

底层数据结构：动态开辟的数组，每一次以原来空间大小的2倍进行扩容

增加

vector<int> vec;
vec.push_back(20);//末尾添加元素，时间复杂度O(1)
vec.insert(it,20);//it迭代器指向的位置添加一个元素20，时间复杂度O(n)
//这两种增加方式会导致容器的扩容

删除

vec.pop_back();//末尾删除元素O(1)
vec.erase(it);//删除迭代器指向的元素O(n)

查询

operator[]//下标随机访问·O(1)
iterator迭代器进行遍历
find，for_each
foreach =也是通过迭代器来实现的

注意：对容器进行连续插入或者删除操作（insert/erase）一定要更新迭代器，否则第一次insert/erase后，迭代器就会失效

常用方法介绍

size()
empty()
reserver(20); ：vector预留空间的，只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：容器扩容，不仅给容器开辟指定的大小内存空间，还会添加新的元素
swap:两个容器进行元素交换

deque双端队列

底层数据结构是动态开辟的二维数组 一维数组从2开始，以2倍的方式进行扩容，每次扩容后，原来第二维的数组从新的第一维数组下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加

增加

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要慢。

删除

que.pop_back();//从末尾删除元素O(1)
que.pop_front();//从首部删除元素O(1)
que.erase(it);//从it指向的位置删除元素O(n)

查询

iterator（连续的insert/erase一定要考虑迭代器失效问题）

list容器

底层数据结构：双向的循环链表 pre data next

增加

list<int>mylist;
mylist.push_back(20);//从末尾添加元素O(1)
mylist.push_front(2);//从首部添加元素O(1)
mylist.insert(it,20);//it指向的位置添加元素O(1)，链表中进行insert时先要进行一个query查询操作，对于链表来说，查询的操作效率就比较慢了。

删除

mylist.pop_back(20);//从末尾删除元素O(1)
mylist.pop_front(2);//从首部删除元素O(1)
mylist.erase(it,20);//it指向的位置删除元素O(1)，

查询

iterator连续的inseert和erase一定要考虑迭代器失效问题

deque和list，比vector容器多出来了增加删除函数的接口：push_front ，pop_front

特点

• vector特点：动态数组，内存是连续的，2倍的方式进行扩容，vectorvec;0-1-2-4-8…
• deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间。扩容的时候（第一维的数组进行2倍扩容）
• 问题：deque底层内存是否连续？答案：不是，每一个第二维是连续的

vector和deque之间的区别？

1. 底层数据结构不同
2. 前中后插入删除元素的时间复杂度：中间和末尾都是O(1)，vector对于前面的时间复杂度是O(n),deque对于前面的时间复杂度是O(1)
3. 对于内存的使用效率：vector需要的空间是连续的，deque可以分块进行数据存储，不必须是连续的内存空间
4. 对于中间进行insert或者erase：vector的效率要高于deque。因为deque不是连续的内存空间，删除/插入元素，相对复杂

f

• satck ：push入栈 pop出栈 top查看栈顶元素 empty判断栈空 size返回元素个数
• queue：push入队 pop出队 front查看队头元素 back查看队尾元素 empty判断队空 size返回元素个数 stack依赖于deque queue依赖于deque 问题来了，为什么他们不依赖于vector？？？

1. 对于vector的初始内存使用效率太低，没有deque好 vectorvec;0-1-2-4-8… deque是4096/sizeof（int） = 1024
2. 对于queue来说，需要支持尾部插入，头部删除时间复杂度是O(1)，如果依赖于vector，出队效率会贬低
3. 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（）的第二个形参绑定起来