STL容器及其简单应用(stack、priority_queue、vector、deuqe、list、map/multimap、set/multiset)

网友投稿 214 2022-11-16

STL容器及其简单应用(stack、priority_queue、vector、deuqe、list、map/multimap、set/multiset)

目录

​​前言​​​​【1】stack操作以及应用​​

​​stack的几个核心接口​​​​利用stack完成进制转换​​

​​【2】priority_queue操作以及应用​​

​​priority_queue的几个核心接口​​​​利用priority_queue完成合并果子问题​​

​​【3】vector操作以及应用​​

​​vector的几个核心接口​​​​利用vector完成随机排序​​

​​【4】deuqe(双向队列)操作以及应用​​

​​deuqe的特点以及核心接口​​​​利用deuqe处理数据​​

​​【5】list(双向链表)操作以及应用​​

​​list的特点​​​​双向链表实现数据的输入与求和​​

​​【6】map/multimap操作以及应用​​

​​map/multimap的几个特点以及功能接口​​​​map/multimap应用：优惠购物​​

​​【7】set/multiset(集合/多重集合)操作以及应用​​

​​set/multiset的几个特点​​​​利用set完成随机数的产生以及排序​​

​​总结​​

前言

前几天回老家没事儿在新华书店乘凉，无意翻到《c++信息学奥林匹克竞赛入门与提高》，拍了几张照片，顺便学点c++的知识。 现整理如下： 关于STL的知识可以先看看百度百科：​​​STL(模板库)_百度百科​​

【1】stack操作以及应用

stack的几个核心接口

向栈中压入一个元素（push）、 取栈顶元素的值（top）、 弹出栈顶元素（pop）、 清空栈（empty）、 判断栈是否为空（isEmpty）

利用stack完成进制转换

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//stack应用//输入：十进制数n,转换成r进制数输出（2<=r<=16）const string t = "0123456789ABCDEF";int main(){ stacks; int n, r, x; cin >> n >> r; while (n != 0) { x = n % r;//求余数 s.push(x);//将余数压入栈顶 n = n / r;//缩小r倍 } while (!s.empty()) { cout << t[s.top()]; //转换成r进制数位 s.pop(); //弹出栈顶元素，即移除元素 }}

【2】priority_queue操作以及应用

priority_queue的几个核心接口

利用priority_queue完成合并果子问题

问题描述以及分析：在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把 所有的果子合成一堆。每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重力之和。 算法分析: 如有3种果子,数目依次为1,9，2。可以先将1,2堆合并,新堆数目为3,耗费体力为3。接着﹐将新堆 与数量为9的堆合并，又得到新的堆，数目为12,耗费体力为12。 所以多多总共耗费体力=3＋12=15。可以证明15为最小的体力耗费值。 类似于堆操作（完全二叉树），优先级高的优先处理 代码实现：

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//最小值优先（升序处理）使用动态数组vector递增参数排序，相当于最小值优先priority_queue, greater > q;//从小到大的优先级队列，可将greater改为less，即为从大到小,int main(){ int i, n, ans = 0, t1 = 0, t2 = 0, t3 = 0, x; cin >> n; for (i=0;i> x; q.push(x); //进队，把一个元素压入队尾 } //所有元素压入队列中之后自动排序 for (i = n;i > 1;i--) //合并次数共计n-1次 { t1 = q.top(); //取最小的元素 q.pop(); //此元素出队列 t2 = q.top(); //取第二小的元素 q.pop(); //此元素出队列 t3 = t1 + t2; //合并果子数（合并较小的2个） ans +=t3; //求果子数目之和 q.push(t3); //入队列 //每一次循环，都会自动排序 } cout << ans << endl; return 0;}

【3】vector操作以及应用

vector的几个核心接口

常用操作

效果

vectorc

产生一个空的vetcor

c.size()

返回元素个数

front()

返回第一个元素的引用，不检查元素是否存在

back()

返回最后一个元素的引用，不检查元素是否存在

begin()

返回一个迭代器，指向第一个元素

end()

返回一个迭代器，指向最后一个元素之后

c.insert(pos,e)

在pos位置插入元素e的副本，并返回新元素的位置

c.push_back(e)

在尾部添加一个元素e的副本

c.pop_back(e)

移除最后一个元素但不返回最后一个元素

c.erase(pos)

删除pos位置的元素，返回下一个元素的位置

c.clear()

移除所有元素，清空容器

利用vector完成随机排序

#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;void Swap(int& a, int& b){ int c = a; a = b; b = c;}void random_arrange(int a[], int len){ int i; srand(time(NULL)); for (i = 0; i < len; i++) { Swap(a[i], a[rand() % (i + 1)]); }}void print(int a[], int len){ for (int i = 0; i < len; i++) cout << a[i] << " "; cout << endl;}int main(void){ int a[] = { 1,2,3,4,5,6,7,8,9 }; int len = sizeof(a) / sizeof(int); int i = 0; cout << "before arrange" << endl; print(a, len); //random_arrange(a, len); vector se; //这里的vector要是换成set会报错 while (se.size() < len) se.push_back(a[i++]); random_shuffle(se.begin(), se.end()); cout << "after arrange" << endl; for (i = 0; i < len; i++) cout << se[i] << " "; cout << endl; return 0;}

【4】deuqe(双向队列)操作以及应用

deque(双向队列)和vector非常相似，操作接口功能模块基本一致。它采用动态数组来管理元素，提供随机存取，可以在头尾两段快速插入和删除元素。

deuqe的特点以及核心接口

deque支持随机存取，可以使用迭代器或[ ]符号 deque支持在头部和尾部存储数据

操作

效果

c,push_back(e)

在尾部添加一个元素e的副本

c.push_front(e)

在头部添加一个元素e的副本

c.pop_back()

移除最后一个元素但不返回最后一个元素

c.pop_front()

移除第一个元素但不返回第一个元素

利用deuqe处理数据

#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int main(){ //deque(int nSize,const T& t):创建一个deque,元素个数为nSize,且值均为t deque< int>d(10, 1); deque< int>::iterator it; int x, y; cin >> x >> y; d.push_front(y); d.push_back(x); cout << "d[0]=" << d[0] << endl; cout << "d[11]=" << d[11] << endl; cout << "d.front()=" << d.front() << endl; cout << "d.back()=" << d.back() << endl; for (it = d.begin();it != d.end();it++) { cout << *it << " "; } cout << endl; return 0;}

【5】list(双向链表)操作以及应用

list的特点

双向链表将元素按顺序存储在链表中。与动态数组vector相比，它允许快速地插入与删除，但是随机访问却比较慢。 特点：

使用双向链表管理元素，数据元素可以使任意类型T list只能通过迭代器遍历数据（不支持随机存取，不能使用[ ]） 在任何位置上执行元素的插入和移除都非常快

双向链表实现数据的输入与求和

#include #include #include #include #include #include #include #include #includeusing namespace std;listlist1;int main(){ list::iterator iter; //从双向链表list1前面向容器中添加数据 list1.push_front(5); list1.push_front(8); //从双向链表list1后面向容器中添加数据 list1.push_back(7); list1.push_back(9); //从前向后显示list1中的数据 cout << "list1 data" << endl; for (iter = list1.begin();iter != list1.end();iter++) { cout << *iter << " "; } cout << endl; //求和 int result = accumulate(list1.begin(),list1.end(),0); cout << "Sum" << result << endl; return 0;}

【6】map/multimap操作以及应用

map是STL关联式容器，它提供映射关系（第一个关键字，第二个关键值）的数据处理能力，通常用它来快速处理映射相关的数据集，map数据结构内部是一棵红黑树（平衡二叉树），它具有对数据自动排序的功能，我们可以快速高效处理容器中的数据，时间复杂度为logN。对于访问的迭代器来说，仅能修改关键值，不能修改key。

map/multimap的几个特点以及功能接口

元素包含两部分(key,value),key和value可以是任意类型 根据元素的key自动对元素排序，因此根据元素的key可以进行很快定位 不能直接改变元素的key,可以通过[ ]直接存取元素值 map中不允许key相同的元素，multimap允许key相同的元素

操作

效果

map.c

产生空的map

c.size()

返回元素个数

count(key)

返回键值==key的元素个数

find(key)

返回键值==key 的第一个元素，找不到的话返回end

lower_bound(key)

返回键值>=key的第一个元素

upper_bound(key)

返回键值>key的第一个元素

equal_range(key)

返回键值==key的元素区间

c.insert(pos,e)

在pos位置为起点插入e的副本，并返回新元素的位置

c.erase(val)

移除所有值为val的元素，返回移除元素个数

map/multimap应用：优惠购物

问题描述：某购物网站平台进行优惠活动，每件商品当天第一个订单可以打75折。这天网站先后依次接受到了(N<100 000)个订单，订单的数据形式是:商品名价格(单价*数量)，商品名是长度不超过20请按商品名字典序输出当天的每种商品名和其售出的总价。

【7】set/multiset(集合/多重集合)操作以及应用

set(集合)是将容器内所有元素都能更具其键值自动排序，set元素的键值就是实值。set不允许两个元素有相同的键值，multiset可以有相同的键值。

set/multiset的几个特点

set使用平衡二叉树管理元素（红黑树） set的每个元素值必须唯一，系统会自动将数据排序。他支持插入、删除、查找等操作，所有的操作都在logN时间之内完成，效率比较高。 set和multiset的区别是：set插入的元素不能相同，而multiset可以相同 操作指令同map

利用set完成随机数的产生以及排序

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;//生成n个指定范围a~b中的不重复随机数（a<=b<=10000）int main(){ sets; int n, a, b,x; cin >> n >> a >>b; while (s.size() < n) { x = rand() % (b - a + 2) + a; //产生的随机数 s.insert(x); //在集合中插入元素（自动去重处理） } cout << "输出（默认升序+去重）：" << endl; set::iterator it1; //正向迭代器 for (it1 = s.begin();it1 != s.end();it1++) cout << *it1 << " "; cout << endl; return 0;}

总结

无

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。

标签：接口
上一篇:实例详解SpringMVC入门使用
下一篇:基于CDH（Cloudera Distribution Hadoop）的大数据平台搭建
相关文章

 发表评论

暂时没有评论，来抢沙发吧~