STL,英文全称 standard template library,中文可译为 标准模板库或者泛型库,其包含有大量的模板类和模板函数,是 C++ 提供的一个基础模板的集合,用于完成诸如输入 / 输出、数学计算等功能。
vector 容器是 STL 中最常用的容器之一,vector 实现的是一个动态数组,即可以进行元素的插入和删除。
vector 常被称为 向量容器,在尾部插入或删除元素,时间复杂度为 O(1)
;而在容器头部或者中部插入或删除元素,时间复杂度为 O(n)
。
vector<int> nums; # 空 vector
nums.resize(20); # 指定大小
vector<int> nums(20); # 创建时指定大小,默认初始值都为 0
vector<int> nums(20,1); # 创建时指定大小,初始值为 1
vector<int> nums {1, 2, 3, 4, 5};
size() # 返回元素个数
empty() # 返回是否为空
clear() # 清空
front()/back() # 第一个/最后一个元素
push_back()/pop_back() # 插入/移除最后一个元素
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
insert() # 插入元素到 vector 中
resize() # 改变 vector 元素数量的大小
[] # 下标访问
支持比较运算,按字典序
pair 专门用来将 2 个普通元素 first 和 second 创建成一个新元素 <first, second>
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以 first 为第一关键字,以 second 为第二关键字(字典序)
string 是 C++ 标准库的一个重要的部分,主要用于字符串处理。
string s1; # 默认初始化,空串
string s2(s1); # 使用s1初始化s2
string s3("Hello"); # 字符串初始化
string s4(n,'c'); # 使用 n 个字符 'c' 初始化
size()/length() # 返回字符串长度
empty() # 判空
clear() # 清空
substr(pos,len) # 返回pos开始长度为len的子串
find(s)/rfind(s) # 查找 s 第一次/最后一次出现位置
+= # 重载 += 运算符
[] # 下标访问
字典序比较
queue 只能在容器的末尾添加新元素,只能从头部移除元素,FIFO 准则
size() # 返回队列中元素的个数
empty() # 判空
push() # 向队尾插入一个元素
front() # 返回队头元素
back() # 返回队尾元素
pop() # 弹出队头元素
priority_queue, 优先队列,元素按照一定的规则排列有序,在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。默认是大根堆
size() # 返回队列中元素的个数
empty() # 判空
push() # 插入一个元素
top() # 返回堆顶元素
pop() # 弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q;
deque, 双端队列,允许在容器头部/尾部快速插入和删除
size() # 返回队列中元素的个数
empty() # 判空
clear() # 清空
front()/back() # 返回第一个/最后一个元素
push_back()/pop_back() # 在尾部加入/删除一个元素
push_front()/pop_front() # 在头部加入/删除一个元素
[] # 下标访问
stack 实现了一个先进后出(FILO)的数据结构
size() # 返回栈中元素的个数
empty() # 判空
push() # 向栈顶插入一个元素
top() # 返回栈顶元素
pop() # 弹出栈顶元素
集合中以一种特定的顺序保存唯一的元素,自动递增去重。
unordered_set,multiset 类似
size() # 返回集合中元素的个数
empty() # 判空
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
find(val) # 查找值为 val 的元素
count(val) # 查找值为 val 的元素的个数
insert() # 插入元素到集合
erase() # 删除集合中的元素
lower_bound(val) # 返回指向第一个大于或等于val的元素的迭代器
upper_bound(val) # 返回指向第一个大于val的元素的迭代器
map 容器存储的都是 pair 对象,包含 “关键字 / 值” 对
unordered_map,multimap 类似
size() # 返回map中元素的个数
empty() # 判空
begin()/end() # 返回第一个元素/最末元素下一个位置的迭代器
find(key) # 查找键为 key 的键值对
count(key) # 查找键为 key 的键值对的个数
insert() # 插入键值对
erase() # 删除键值对
lower_bound(key) # 返回指向第一个大于或等于key的元素的迭代器
upper_bound(key) # 返回指向第一个大于key的元素的迭代器
[] # 重载 [] 运算符