C++常用容器分享(算法题,掌握这些就够了)

vector

是什么

连续的顺序存储结构，其实就是一个可变数组
想使用的话记得 #include<vector>

怎么用

初始化语法 vector<类型> 名字(长度,初始值)

演示一下

// 一维的vector 
vector<int> arr; // 不指定里面有多少个元素
vector<int> arr(100); // 指定里面有100个元素 这100个元素都是默认值 0
vector<int> arr(100, 1); // 指定里面有100个元素，每个元素指定为1

// 二维的vector 
vector<vector<int>> arr;  // 不初始化行列  
vector<vector<int>> arr(100, vector<int>()); // 100行 但是没初始化列数
vector<vector<int>> arr(100, vector<int>(100, 1)); // 100行100列 每个值都是1

常用的操作

列举一下

arr.push_back(1) // 把1插入到这个vector的尾部   长度 +1 
arr.pop_back() // 把最后一个元素删除了   长度  -1    
arr.size() // 获取长度
arr.clear() // 清空
arr.empty() // 返回值是bool 是空的就返回true
arr.resize(新长度, 默认值) 
// 如果是缩短，则删除多余的值  如果是扩大，且指定了默认值，则新元素均为默认值（旧元素不变）

stack

是什么

通过二次封装双端队列 (deque) 容器，实现先进后出的栈数据结构。
想使用的话记得 #include<stack>

怎么用

初始化 stack<类型> 名字

常用操作

// stk是我们初始化好的栈
stk.push(1) // 把 1进栈
stk.pop() //  把栈顶元素出栈   注意 这个没法取到栈顶元素  只是把他扔出去
stk.top() //  取到栈顶元素
stk.size() // 获得栈的大小
stk.empty() 

注意 ：

1. 没有 clear resize 方法
2. 不能取内部元素 不能遍历

queue

是什么

通过二次封装双端队列 (deque) 容器，实现先进先出的队列数据结构。
使用记得 #include<queue>

怎么用

初始化 queue<类型> que

que.push() // 入队
que.pop() // 出队
que.front() // 取队首 
que.back() // 取队尾
que.size() // 大小
que.empty() 

注意:

1. 没有 clear resize 方法
2. 不能取内部元素 不能遍历

优先队列

是什么

一个持续维护元素有序性的队列 也就是一个堆
提供常数时间的最大元素查找，对数时间的插入与提取，底层原理是二叉堆。
使用记得 #include<queue>

怎么用

初始化 priority_queue<类型, 容器,比较器>
类型: 要存储的数据类型
容器: 存储数据的底层容器,默认是vector, 写算法题就保持默认就行了
比较器: 默认是less<类型> 类型 可以自定义 默认的话就是初始了一个大顶堆 堆顶元素最大

综上,写算法题常见的两种初始化方式如下

priority_queue<int> que; // 默认的 只写类型就行了 大顶堆
priority_queue<int,vector<int>,greater<int>> que // 自定义的就要全都写上  小顶堆

常用操作

que.push(1) // 进堆
que.pop() // 出堆
que.top() // 取堆顶
que.size // 队列大小
que.empty();  // 判空

注意:

1. 不能遍历 不能取里面的某一个元素 只能取堆顶元素

set

是什么

提供对数时间的插入、删除、查找的集合数据结构。底层原理是红黑树。
还可以去重 有的时候去重会用他
一共有三种set

分别是:

set: 去重 有序(从小到大)
multiset: 不去重 有序(从小到大)
unordered_set: 去重 无序

怎么用

初始化 set<类型,比较器> st
比较器默认是 less<类型> 也就是从小到大

所以有下面两种初始化的方式

set<int> st // 从小到大
set<int,greater<int>> st // 从大到小

常用方法:

st.insert() // 插入元素
st.erase()  // 删除元素
st.find()  // 查找元素   返回的是一个迭代器 如果元素存在 返回指向这个元素的迭代器 不存在就返回末尾的迭代器
auto it = st.find() 
cout << *it << endl  // 要这么用 才能拿到查找的这个元素

st.count()  // 查找元素存在不存在  返回1就是存在
// size() clear() empty() 均存在

他是可以遍历的！！

// 方法1  用迭代器遍历
for(set<int>::iterator it = st.begin(); it != st.end(); ++it) 
for(auto it = st.begin(); it != st.end(); ++it) 
//方法2   增强for循环
for(auto x : st)

注意：

1. 虽然可以遍历 但是不能用下标访问数据
2. 遍历的时候只能读 不能修改元素
3. 迭代器不能像vector一样相减直接得到下标

map

是什么

提供对数时间的有序键值对结构。底层原理是红黑树。

有三种比较常用
map: 键去重 键有序(从小到大)
multimap: 键不去重 键有序(从小到大)
unordered_map: 键去重 键无序

怎么用

初始化:

map<int,int> mp // 键从小到大
map<int,int,greater> mp // 键从大到小

三种遍历和取值方法

// 迭代器
for(auto it = mp.begin(); it != mp.end(); ++it)
    cout << it -> first << it -> second << endl
// 增强for循环
for(auto x: mp)
    cout << x.first << x.second << endl
//架构化绑定的增强for循环
for(auto x: mp)
    cout << x << v << endl

常用方法:

mp[1] = 2 // 增加新的键值对   修改已经有的
mp.find(元素) // 查找元素返回迭代器
mp.erase()
mp.count()
size    empty   clear 都有

注意：

1. 如果使用中括号 访问map时对应的键不存在,那么就会新增这个键，设置为默认值， 所以中括号会影响键的存在性
2. 不能像vector一样相减得到下标

以上就是我认为做算法题必须要掌握的容器知识啦QWQ