深入学习STL标准模板库

C++ STL standard template libaray 标准模板库

一、标准容器

顺序容器

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); 删除it迭代器指向的元素 O(n)
查询：
operator[] 下标的随机访问 vec[5] O(1)
iterator 迭代器进行遍历
find，for_each
foreach => 底层通过iterator来实现的
常用方法介绍:
size()
empty()
reserve(20)：vector预留空间的 只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize(20)：容器扩容用的 不仅给容器底层开辟指定大小的内存空间，还会会添加新的元素
swap：两容器进行元素交换

注意1：resize和reserver的区别
reserve预留空间 只给容器底层开辟指定大小的内存空间，并不会添加新的元素
resize：容器扩容 不仅给容器底层开辟指定大小的内存空间，还会添加新的元素

	vector<int> ve;
	ve.reserve(20);//预留内存空间 
	cout<<ve.empty()<<endl;//输出 1 
	cout<<ve.size()<<endl;//输出 0
	
	ve.push_back(1); 
	ve.push_back(2); 
	ve.push_back(3); 
	for(int x:ve) cout<<x<<" ";//输出 1 2 3

	vector<int> ve;
	ve.resize(10);//开辟空间 添加元素
	cout<<ve.empty()<<endl;//输出 0 
	cout<<ve.size()<<endl;//输出 10 
	
	ve.push_back(1); 
	ve.push_back(2); 
	ve.push_back(3); 
	for(int x:ve) cout<<x<<" ";//输出 0 0 0 0 0 0 0 0 0 0 1 2 3

注意2：vector调用clear()或者size(0),会清除容器内的所有元素，但是不会释放内存,如果想释放内存需要调用shrink_to_fit()函数

	vector<int> ve{1,2,3,4,5,6,7,8,9,10};
	cout<<ve.size()<<endl;//输出10 
	cout<<ve.capacity()<<endl;//输出10
	
	ve. clear(); //ve.resize(0);
	cout<<ve.size()<<endl;//输出0 
	cout<<ve.capacity()<<endl;//输出10
	
	cout<<"ve[2]="<<ve[2]<<endl;//输出3 因为元素清空了 内存没有清空 
	
	ve.shrink_to_fit();
	cout<<ve.size()<<endl;//输出0 
	cout<<ve.capacity()<<endl;//输出0

注意3：对容器进行连续插入或者删除操作(insert/erase)，一定要更新迭代器，否则第一次insert或者erase完成，迭代器就失效了，比如下面代码经典错误

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<int> ve{1,2,3,4,5,6,7,8,9,10};
	//把容器中所有的偶数删除
	auto it = ve.begin();
	for(;it!=ve.end();it++) 
	{
		if(*it%2==0)
		{
			ve.erase(it);//错误迭代器已经失效了 
		}
	}
	for(int x:ve)
	{
		cout<<x<<" ";//输出为空
	}
    return 0;
}

正确写法：

#include <iostream>
#include <vector>
using namespace std;
int main() {
	vector<int> ve{1,2,3,4,5,6,7,8,9,10};
	//把容器中所有的偶数删除
	auto it = ve.begin();
	while(it!=ve.end())
	{
		if(*it%2==0)
		{
			it = ve.erase(it);//删除之后返回迭代器位置 
		}else//迭代器指向的不是偶数才后移 
		{
			++it;
		}
	}
	
	for(int x:ve)
	{
		cout<<x<<" ";//输出1 3 5 7 9 
	}cout<<endl;
	
	//给vector容器中所有的奇数前面都添加一个小于奇数1的偶数 
	for(it=ve.begin();it!=ve.end();++it)
	{
		if(*it%2!=0)
		{
			it = ve.insert(it,*it-1);//插入之后返回新的迭代器位置 
			++it;//迭代器需要向后多移动一次保证不重复插入 
		}
	}
	for(int x:ve)
	{
		cout<<x<<" ";//输出0 1 2 3 4 5 6 7 8 9 
	}
    return 0;
}

deque

底层数据结构：动态开辟的二维数组（二维双端队列），一维数组从大小2开始，以2倍的方式进行扩容，每次扩容后，原来的二维数组(固定长度)，从新的第一维数组的下标oldsize/2开始存放，上下都预留相同的空行，方便支持deque的首尾元素添加

注意：deque底层每一个第二维本身是连续的，但是所有的二维不是连续的，是重新new出来的(分段连续)

底层原理：
一般编译器默认大小
#define MAP_SIZE 2 第一维度大小
#define QUE_SIZE 4096/sizeof(T) 第二维度大小 T为数据类型

1.初始的队头队尾指针在队列中间（双端队列方便两头都可以插入删除）

2.随着元素的插入队头队尾指针移动

3.当队列满的时候，开辟新的二维空间

4.当所有队列满的时候进行2倍扩容(二维会放在一维中间位置)


操作：
deque<int> deq;
增加：
deq.push_back(20); 从末尾添加元素 O(1) 可能扩容
deq.push_front(20);从首部添加元素 O(1) 可能扩容
deq.insert(it,20); it指向的位置添加元素 O(n) 可能扩容

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

查询搜索
iterator （连续的insert和erase一定要考虑迭代器失效的问题）

list

底层数据结构：双向的循环列表

list mylist;
增加：
mylist.push_back(20); 从末尾添加元素 O(1) 可能扩容
mylist.push_front(20);从首部添加元素 O(1) 可能扩容
mylist.insert(it,20); it指向的位置添加元素 O(1) 可能扩容 往往需要先query查询操作
对于链表来说，查询操作效率就比较慢

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

查询搜索
iterator （连续的insert和erase一定要考虑迭代器失效的问题）

vector deque list对比

vector特点：动态数组，内存连续，2倍的方式进行扩容
deque特点：动态开辟的二维数组空间，第二维是固定长度的数组空间，扩容的时候(第一维的数组进行2倍扩容)
list特点：双向循环链表

vector和deque之间的区别？

1.底层数据结构：
2.前中后插入删除元素的时间复杂度：中间O(n)，末尾都是O(1)， 前插deque O(1) vector O(n)
3.对于内存的使用效率：vector需要的内存空间必须连续，deque可以分块进行数据存储，不需要内存必须连续
4.在中间进行insert或者erase，虽然时间复杂度都是O(n),但是vector都是连续空间比较方便，deque的第二维内存空间不是连续的，所以在deque中间进行元素的inset或者erase，指令肯定更多，造成元素移动的时候比vector要慢
deque和list比vector容器多出来的增加删除函数接口：push_front() pop_front()

vector和list之间的区别？
数组和链表的区别
数组：增加删除O(n) 查询O(n) 随机访问O(1)
链表：增加删除O(1) 查询(n)

容器适配器

stack

queue

priority_queue

关联容器

无序关联容器 链表哈希表 增删查O(1)

unordered_set

unordered_multiset

unordered_map

unordered_multimap

有序关联容器 红黑树 增删查 O(log2n) n是底数(树的层数 树的高度)

set

multiset

map

mutimap

二、近容器

数组

string

bitset(位容器)

三、迭代器

iterator和const iterator

reverse_iterator和const_reverse_iterator

四、函数对象

greater

less

五、泛型算法

sort、find、find_if、binary_search、for_each