搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 昊天码字 > C++中常用的STL容器总结一

C++中常用的STL容器总结一

昊天码字 2020-08-02

YOU CAN DRINK ALL YOU LIKE, BUT IN THE MORNING YOU GET HEADACHE WITH THE SAME PROBLEMS.


0x71 C++STL(1)

本节介绍STL中vector、queue、priority_queue、deque、set、multiset、map、bitset八种算法竞赛中比较有用的容器。

头文件vector

vector支持随机访问,即对于任意的下标0<=i<n,可以像数组一样用[i]取值。但它不是链表,不支持在任意位置O(1)插入,为了保证效率,元素的增删一般应该在末尾进行。

声明

#include<vector>
vector<int> a;
vector<int> a[233]; //相当于第一维长度233,第二维长度动态变化的int数组
struct rec{};
vector<rec> c; //自定义的结构体也可以保存在vector数组中

size/empty

时间复杂度为O(1),所有的容器都支持这两种方法,含义也都相同,之后就不再重复给出。

clear

清空vector

迭代器

迭代器就像STL容器中的指针,可以用星号*操作符解除引用。

一个保存int的vector迭代器声明方法为:

vector<int>::iterator it;

vector迭代器是随机访问的迭代器,可以把vector迭代器与一个整数相加减,其行为和指针的移动类似。可以把vector的两个迭代器相减,其结果也和指针相减类似,得到两个迭代器对应下标之间的距离。

begin/end

begin函数返回指向vector中的第一个迭代器。例如a是一个非空的vector,则*begin()与a[0]作用相同。

所有的容器都可以视作为一个前闭后开的结构,end函数返回vector的尾部,即第n个数再往后的边界。*a.end()与a[n]都是越界访问,其中n=a.size()。

for (vector<int>::iterator it =  a.begin(); it != a.end(); i++) {
    cout << *it << endl;
}

front/back

front返回vector的第一个元素,等价于*a.begin()和a[0]。

back返回vector的最后一个元素,等价于*--a.end()和a[a.size() -  1]。

push_back/pop_back()

a.push_back(x) 把元素x插入到vector a的尾部。

a.pop_back() 删除vector 的最后一个元素。

用vector代替邻接表保存有向图

const int MAX_EDGES = 100010;
vector<int> ver[MAX_EDGES], edge[MAX_EDGES];

// 保存从x到y权值为z的有向边
void add(int x, int y, int z) {
    ver[x].push_back(y);
    edge[x].push_back(z);
}

// 遍历从x出发的所有边
for (int i = 0; i < ver[x].size(); i++) {
    int y = ver[x][i], z = edge[x][i];
    // 有向边(x, y, z)
}

头文件queue

头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。

声明

queue<int> q;
struct rec{}; queue<rec> q;
priority_queue<int> q;
priority_queue<pair<intint>> q;

循环队列queue

方法 描述 示例 时间复杂度
push 入队(从队尾) a.push(element) O(1)
pop 出队(从队头) a.pop() O(1)
front 队头元素 int x = q.front(); O(1)
back 队尾元素 int y = q.back()l O(1)

优先队列priority_queue

priority_queue可理解为一个大根堆。

方法 描述 示例 时间复杂度
push 把元素插入堆 q.push(x); O(log n)
pop 删除堆顶元素 q.pop(); O(log n)
top 查询堆顶元素(最大值) int x = q.top(); O(1)

重载“<”运算符

priority_queue中存储的元素类型必须定义小于号,较大的元素会被放在堆顶。内置的int,string等基本类型本身就可以比较大小,若用自定义的结构体类型,则需要重载“<”运算符。

例如下面的poi结构体保存了二维平面上点的坐标和编号,比较大小时,先比较横坐标,再比较纵坐标,并且考虑了精度误差:

struct poi{int id; double x, y;};
const int eps = 1e-8;

bool operator <(const poi &a, const poi &b) {
    return a.x + eps < b.x || a.x < b.x + eps && a.y < b.y;
}

priority_queue实现小根堆

priority_queue实现小根二叉堆的方式一般有两种。

对于int等内置数值类型,可以把要插入的元素的相反数放入堆中。等从堆中取出元素时,再把它取相反数变回原来的元素。这样就相当于把小的放在堆顶。

例如要插入1、2、3三个数时,改为插入-1、-2、-3.此时-1最大,处于堆顶,把-1取出后再变回-(-1),相当于取出了最小的1。

更为通用的解决方案是,建立自定义结构体类型,重载小于号,但是当做大于号来编写函数,例如:

struct rec {int id; double value; };

bool operator <(const rec &a, const rec &b) {
    return a.value > b.value;
}

这样priority_queue会认为大的更小,小的更大,从而实现大根堆时,value较小的rec元素会被放在堆顶。

懒惰删除法

STL的优先队列不支持删除堆中任意元素,这给我们带来了许多不便。

懒惰删除法(又称延迟删除法)就是一种应对策略。当遇到删除操作时,仅在优先队列之外做一些特殊的记录(例如记录元素的最新值),用于辨别那些堆中尚未清除的过时元素。当从堆顶取出最值时,再检查最值元素是不是过时的,若是,则重新取出下一个最值。换言之,元素的删除被延迟到堆顶进行。

头文件deque

双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比,deque在头部增删元素仅需要O(1)的时间;与queue相比,deque像数组一样支持随机访问。

方法 描述 示例 时间复杂度
[] 随机访问 与vector类似 O(1)
begin/end deque的头/尾迭代器 与vector迭代器类似 O(1)
front/back 对头/队尾元素 与queue类似 O(1)
push_back 从队尾入队 q.push_back(x); O(1)
push_front 从队头入队 q.push_front(y); O(1)
pop_front 从对头出队 q.pop_front(); O(1)
pop_back 从队尾出队 q.pop_back(); O(1)
clear 清空队列 q.clear(); O(n)

set头文件

头文件set主要包括set和multiset两个容器,分别是有序集合和有序多重集合,即前者的元素不能重复,而后者可以包含若干个相等的元素。set和multiset的内部实现是一颗红黑树(平衡树的一种),它们支持的函数基本相同。

声明

set<int> s;
struct rec{...}; set<rec> s;
multiset<double> s;

与优先队列一样,set和multiset存储的元素必须定义小于号运算符。

size/empty/clear

与vector类似,分别为元素个数、是否为空、清空。前两者的时间复杂度为O(1)。

迭代器

set和multiset的迭代器称为双向访问迭代器,不支持随机访问,支持星号*解除引用,仅支持++和--两个与运算相关的操作。

设it是一个迭代器,例如:

set<int>::iterator it;

若把it++,则it会指向下一个元素。这里的下一个是指在元素从小到大排序的结果中,排在it下一名的元素。同理,若把it--,则it将会指向排在上一个的元素。

请注意,执行++和--操作的时间复杂度都是O(log n)。执行操作前后,务必仔细检查,避免迭代器指向的位置超出首、尾迭代器之间的范围。

begin/end

返回集合的首、尾迭代器,时间复杂度为O(1)。

s.begin()是指向集合中最小元素的迭代器。

s.end()是指向集合中最大元素的下一个位置的迭代器,换而言之,就像vector一样,是一个前闭后开的形式,因此--s.end()是指向集合中最大元素的迭代器。

insert

s.insert(x)是指把一个元素x插入到集合s中,时间复杂度为O(log n)。

在set中,若元素已存在,则不会重复插入该元素,对集合状态无影响。

下面的代码把n个整数插入有序多重集合multiset,并从小到大输出,时间复杂度为O(nlog n),相当于进行了一次排序。假设n个整数目前存储在数组a[1~n]中。

multiset<int> s;
for (int i = 1; i <= n; i++) s.insert(a[i]);
for (multiset<int>::iterator it = s.begin(); it != s.end(); it++) {
    cout << *it <<endl;
}

find

s.find(x)在集合s中查找等于x的元素,并返回指向该元素的迭代器。若不存在,则返回s.end()。时间复杂度为O(log n)。

lower_bound/upper_bound

这两个函数的用法与find类似,但查找的条件有所不同,时间复杂度为O(log n)。

s.lower_bound()查找>=x的元素中最小的一个,并返回指向该元素的迭代器。

s.upper_bound()查找>x的元素中最小的一个,并返回指向该元素的迭代器。

erase

设it是一个迭代器,s.erase(it)从s中删除迭代器it指向的元素,时间复杂度为O(log n)。

设x是一个元素,s.erase(x)从s中删除所有等于x的元素,时间复杂度为O(k+log n),其中k为被删除的元素个数。

如果想从multiset中删掉至多一个等于x的元素,可以执行:

if ((it = s.find()) != s.end()) s.erase(it);

count

s.count(x)返回集合s中等于x的元素个数,时间复杂度为O(k + log n),其中k为元素x的个数。



版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《C++中常用的STL容器总结一》的版权归原作者「昊天码字」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注昊天码字微信公众号

昊天码字微信公众号:a13019949390

昊天码字

手机扫描上方二维码即可关注昊天码字微信公众号

昊天码字最新文章

精品公众号随机推荐