type
status
date
slug
summary
tags
password
category
Property
May 26, 2024 10:17 AM
icon
什么是STL?
除了从
C
标准库保留下来的一些功能之外,C++
还提供了一个基于模板实现的标准库模板(Standard Template Library
,简称STL
)STL
基于模板实现了一些面向序列数据的表示以及常用的操作STL
支持了一种抽象的编程模式
- 隐藏了一些低级的程序元素,如数组、链表、循环等
STL包含什么?
- 容器类模板:容器用于存储序列化的数据,如:向量、队列、栈、集合等。
- 算法(函数)模板:算法用于对容器中的数据元素进行一些常用操作,如:排序、统计等。
- 迭代器类模板
- 抽象的指针
- 迭代器是容器和算法之间的桥梁
学习目标
- 熟知STL中的各种容器的名称和特点
- 熟知STL中提供了哪几类常用的算法
- 熟悉常用容器以及常用算法的常用API接口
- 对于不太常用的或者已经忘记的API,能够在需要的时候查文档或者再次翻阅教程解决问题
1. #include <vector>
vector
是变长数组,支持随机访问,不支持在任意位置 O(1) 插入。为了保证效率,元素的增删一般应该在末尾进行。1.2
size/empty
size
函数返回vector的实际长度(包含的元素个数),empty
函数返回一个bool
类型,表明vector
是否为空。二者的时间复杂度都是 O(1)。
所有的STL容器都支持这两个方法,含义也相同,之后我们就不再重复给出。1.3
clear
clear
函数把vector
清空。1.4 迭代器
迭代器就像STL容器的“指针”,可以用星号*操作符解除引用。
一个保存
int
的vector
的迭代器声明方法为:vector<int>::iterator it;
vector
的迭代器是“随机访问迭代器”,可以把vector
的迭代器与一个整数相加减,其行为和指针的移动类似。可以把vector
的两个迭代器相减,其结果也和指针相减类似,得到两个迭代器对应下标之间的距离。1.5
begin/end
begin
函数返回指向vector
中第一个元素的迭代器。例如a
是一个非空的vector
,则*a.begin()
与a[0]
的作用相同。所有的容器都可以视作一个“前闭后开”的结构,
end
函数返回vector
的尾部,即第n 个元素再往后的“边界”。*a.end()
与a[n]
都是越界访问,其中n = a.size()
。下面两份代码都遍历了vector<int> a,并输出它的所有元素。
1.6
front/back
front
函数返回vector
的第一个元素,等价于a.begin()
和a[0]
。
back
函数返回vector
的最后一个元素,等价于*a.end()
和a[a.size() – 1]
。1.7
push_back()
和pop_back()
a.push_back(x)
把元素x
插入到vector a
的尾部。
b.pop_back()
删除vector a
的最后一个元素。2 #include <queue>
头文件
queue
主要包括循环队列queue
和优先队列priority_queue
两个容器。2.1 声明
2.2 循环队列
queue
2.3 优先队列
priority_queue
3. #include <stack>
头文件
stack
包含栈。声明和前面的容器类似。
4. #include <deque>
双端队列
deque
是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector
和queue
的结合。与vector
相比,deque
在头部增删元素仅需要 O(1)的时间;与queue
相比,deque
像数组一样支持随机访问。
5. #include <set>
头文件
set
主要包括set
和multiset
两个容器,分别是“有序集合”和“有序多重集合”,即前者的元素不能重复,而后者可以包含若干个相等的元素。set
和multiset
的内部实现是一棵红黑树,它们支持的函数基本相同。5.1 声明
5.2
size/empty/clear
与vector
类似5.3 迭代器
set
和multiset
的迭代器称为“双向访问迭代器”,不支持“随机访问”,支持星号*
解除引用,仅支持++
和--
两个与算术相关的操作。设
it
是一个迭代器,例如set<int>::iterator it
;若把
it ++
,则it
会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中,排在it
下一名的元素。同理,若把it --
,则it
将会指向排在“上一个”的元素。5.4
begin/end
返回集合的首、尾迭代器,时间复杂度均为 O(1)O(1)。s.begin()
是指向集合中最小元素的迭代器。s.end()
是指向集合中最大元素的下一个位置的迭代器。换言之,就像vector一样,是一个“前闭后开”的形式。因此-- s.end()是指向集合中最大元素的迭代器。5.5
insert
s.insert(x)
把一个元素x
插入到集合s
中,时间复杂度为 O(logn)。在
set
中,若元素已存在,则不会重复插入该元素,对集合的状态无影响。5.6
find
s.find(x)
在集合s
中查找等于x
的元素,并返回指向该元素的迭代器。若不存在,则返回s.end()
。时间复杂度为 O(logn)。5.7
lower_bound/upper_bound
这两个函数的用法与find类似,但查找的条件略有不同,时间复杂度为 O(logn)。s.lower_bound(x)
查找大于等于x
的元素中最小的一个,并返回指向该元素的迭代器。s.upper_bound(x)
查找大于x
的元素中最小的一个,并返回指向该元素的迭代器。5.8
erase
设it
是一个迭代器,s.erase(it)
从s
中删除迭代器it
指向的元素,时间复杂度为 O(logn)
。设
x
是一个元素,s.erase(x)
从s
中删除所有等于x的元素,时间复杂度为 O(k+logn),其中 k是被删除的元素个数。5.9
count
s.count(x)
返回集合s
中等于x
的元素个数,时间复杂度为 O(k+logn),其中 k 为元素x的个数。5.10
#include <unorderd_set>
5.11
#include<bitset>
0 1 二进制串6. #include <map>
map
容器是一个键值对key-value
的映射,其内部实现是一棵以key
为关键码的红黑树。Map
的key
和value
可以是任意类型,其中key必须定义小于号运算符。6.1 声明
6.2
size/empty/clear/begin/end
均与set
类似。6.3
insert/erase
与set
类似,但其参数均是pair<key_type, value_type>
。6.4
find
h.find(x)
在变量名为h
的map
中查找key
为x
的二元组。6.5
[]
操作符
h[key]
返回key
映射的value
的引用,时间复杂度为 O(logn)。[]
操作符是map
最吸引人的地方。我们可以很方便地通过h[key]
来得到key
对应的value
,还可以对h[key]
进行赋值操作,改变key
对应的value
。6.6
#include<unordered_map>
pair
常用操作:
- 求x的第k位数字 x >> k & 1
- lowbit(x) = x & -x,返回x的最后一位1
2. 常用库函数
2.1
reverse
翻转
翻转一个vector
:reverse(a.begin(), a.end());
翻转一个数组,元素存放在下标1 ~ n
:reverse(a + 1, a + n + 1);
2.2 unique
去重
返回去重(只去掉相邻的相同元素)之后的尾迭代器(或指针),仍然为前闭后开,即这个迭代器是去重之后末尾元素的下一个位置。该函数常用于离散化,利用迭代器(或指针)的减法,可计算出去重后的元素个数。把一个
vector
去重:int m = unique(a.begin(), a.end()) – a.begin();
把一个数组去重,元素存放在下标1 ~ n:int m = unique(a + 1, a + n + 1) – (a + 1);
2.3
random_shuffle
随机打乱
用法与reverse
相同。2.4
sort
对两个迭代器(或指针)指定的部分进行快速排序。可以在第三个参数传入定义大小比较的函数,或者重载“小于号”运算符。
把一个
int
数组(元素存放在下标1 ~ n)从大到小排序,传入比较函数:把自定义的结构体
vector
排序,重载“小于号”运算符:2.5
lower_bound/upper_bound
二分lower_bound
的第三个参数传入一个元素x
,在两个迭代器(指针)指定的部分上执行二分查找,返回指向第一个大于等于x
的元素的位置的迭代器(指针)。upper_bound
的用法和lower_bound
大致相同,唯一的区别是查找第一个大于x
的元素。当然,两个迭代器(指针)指定的部分应该是提前排好序的。在有序
int
数组(元素存放在下标1 ~ n)中查找大于等于x的最小整数的下标:int i = lower_bound(a + 1, a + 1 + n, x) - a;
在有序vector<int>中查找小于等于x的最大整数(假设一定存在):int y = *--upper_bound(a.begin(), a.end(), x);