ACM模板：C++编程新手指南与代码优化

ACMer

5星 · 超过95%的资源需积分: 16 59 浏览量更新于2024-07-20 12 收藏 2.91MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

7.1.1 关于queue

stack（栈）和queue（队）是在程序设计中经常会󰉁到的数据容，STL为我们提供

的stack（栈）和queue（队）的实现。

准确的说，STL中的stack和queue同于vector、list等容，󰖳是对这些容进󰢩重新的

包装。这󰮟我们去深讨论STL的stack和queue的实现细节，󰖳是来解些他们的基本使󰉁。

queue模版类的定义在<queue>头件中。

7.1.2 使󰉁queue

queue与stack相似，queue模版类也需要两个模版参数，个元素类型，个容类型，元

素类型时必须的，容类型时可选的，默认为deque类型。

定义queue对象：

queue<int> q;

queue<double> qq;

queue的基本操作：

q.push(x); // 队

q.pop(); // 出队

q.front(); // 访问队󰶳元素

q.back(); // 访问队尾元素

q.empty(); // 判断队是否为空

q.size(); // 访问队中的元素个数

7.2.1 关于priority_queue

在<queue>头件中，还定义另个󰴬常有󰉁的模版类priority_queue（优先队）。优先

队与队的差别在于优先队是按照队的顺序出队，󰖳是按照队中元素的优先权出队（默

认为者优先，也可以通过指定算来指定󰙵的优先顺序）。

7.2.2 使󰉁priority_queue

priority_queue模版类有三个模版参数，第个是元素类型，第个是容类型，第三个是

较算。其中后两者都可以忽󰉝，默认容为vector，默认算为less，即的往前排，的往后排

（出队时尾元素先出队）。

定义priority_queue对象：

priority_queue<int> q;

priority_queue<pair<int, int> > qq; // 注意在两个尖括号之间定要󰉙空格，防误判

priority_queue<int, vector<int>, greater<int> > qqq; // 定义的先出队

priority_queue的基本操作与queue的󰉝微同。

priority_queue的基本操作：

q.empty() // 如果队为空，则返回true，否则返回false

q.size() // 返回队中元素的个数

q.pop() // 删除队󰶳元素，但返回其值

q.top() // 返回具有最󰷼优先级的元素值，但删除该元素

q.push(item) // 在基于优先级的适当位置插新元素

初学者在使󰉁priority_queue时，最困难的可能就是如何定义较算。如果是基本数据类

型，或已定义较运算符的类，可以直接使󰉁STL的less算和greater算——默认为使󰉁less算

。如果要定义󰙵的较算，法有多种，这󰮟介绍其中种：重载较运算符。优先队试

图这两个元素x和y代较运算符（对于less算，调󰉁x < y，对于greater算，调󰉁x > y），若

结果为真，则x排在y前󰴯，y将先出队，反之，则y排在x前󰴯，x将先出队。

Ex（算实现示）:

#include <iostream>

v 1.1 2016.12.5

! /!16 358

8.2 使󰉁map

可以将map看作是由Key标识元素的元素集合，这类容也被称为“关联容”，可以通过个

Key值来快速决定个元素，因此󰴬常适合于需要按照Key值查找元素的容。

map模版类需要四个模版参数，第个是键值类型，第个是元素类型，第三个是较算

，第四个是分配类型。其中键值类型和元素类型是必要的。

定义map对象：

map<string, int> m;

map的基本操作：

/* 向map中插元素 */

m[key] = value; // [key]操作是map很有特󰚬的操作,如果在map中存在键值为

key的元素对, 则返回该元素对的值域部分,否则将会创建个键值为key的元素对,值域为默认值。

所以可以󰉁该操作向map中插元素对或修改已经存在的元素对的值域部分。

m.insert(make_pair(key, value)); // 也可以直接调󰉁insert法插元素对,insert操作会返回个

pair,当map中没有与key相匹配的键值时,其ﬁrst是指向插元素对的迭代,其second为true;若

map中已经存在与key相等的键值时,其ﬁrst是指向该元素对的迭代,second为false。

/* 查找元素 */

int i = m[key]; // 要注意的是,当与该键值相匹配的元素对存在时,会创建键

值为key（当另个元素是整形时，m[key]=0）的元素对。

map<string, int>::iterator it = m.ﬁnd(key); // 如果map中存在与key相匹配的键值时,ﬁnd操作将返

回指向该元素对的迭代,否则,返回的迭代等于map的end()(参󰤁vector中提到的begin()和end()

操作)。

/* 删除元素 */

m.erase(key); // 删除与指定key键值相匹配的元素对,并返回被删除的元素的个数。

m.erase(it); // 删除由迭代it所指定的元素对,并返回指向下个元素对的迭代。

/* 其他操作 */

m.size(); // 返回元素个数

m.empty(); // 判断是否为空

m.clear(); // 清空所有元素

Ex_One:

#include <iostream>

#include <map>

using namespace std;

typedef map<int, string, less<int> > M_TYPE

typedef M_TYPE::iterator M_IT

typedef M_TYPR::const_iterator M_CIT

int main()

{

M_TYPR myTestMap;

myTestMap[3] = "No.3";

myTestMap[5] = "No.5";

myTestMap[1] = "No.1";

v 1.1 2016.12.5

! /!18 358

cout << key << " is " << it->second << endl;

cout << "Erased " << m.erase(key) << endl;

}

return 0;

}

9. STL iterator

9.1 关于iterator

iterator（迭代）是󰉁于访问容中元素的指示，从这个意义上说，iterator（迭代）相

当于数据结构中所说的“遍历指针”，也可以把iterator（迭代）看作是种泛化的指针。

STL中关于iterator（迭代）的实现和使󰉁时相当复杂的，这󰮟我们暂时去详细讨论关于

iterator（迭代）的实现和使󰉁，󰖳只对iterator（迭代）做点简单的介绍。

简单的说，STL中有以下类iterator（迭代）：

输iterator（迭代），在容的连续区内向前移动，可以读取容内任意值；

输出iterator（迭代），把值写进它所指向的容中；

前向iterator（迭代），读取队中的值，并可以向前移动到下个位置(++p, p++)；

双向iterator（迭代），读取队中的值，并可以向前后遍历容；随机访问向iterator（迭

代），可以直接以下标式对容进󰢩访问，vector的iterator（迭代）就是这种iterator（迭代

）；

流iterator（迭代），可以直接输、输出流中的值。

9.2 使󰉁iterator

每种STL容都有󰙵的iterator（迭代）类，下󰴯先来看段简单的示代码：

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector<int> s;

for (int i = 0; i < 10; i++)

{

s.push_back(i);

}

for (vector<int>::iterator it = s.begin(); it != s.end(); it++)

{

cout << *it << " ";

}

cout << '\n';

return 0;

}

vector的begin()和end()法都会返回个vector::iterator对象，分别指向vector的󰶳元素位置

和尾元素的下个位置（我们可以称之为结束标志位）。

对个iterator（迭代）对象的使󰉁与个指针变󰮢的使󰉁极为相似，或者可以这样说，指针就是

个󰴬常标准的iterator（迭代）。

Ex:

#include <iostream>

v 1.1 2016.12.5

! /!20 358

剩余357页未读，继续阅读

f_zyj

粉丝: 2993
资源: 24

ACM模板：C++编程新手指南与代码优化

ACM模板-f_zyj v

ACM模板-f_zyj 更新（内含 v 1.1 和 v 2.1 的 .pages 格式和 .pdf 格式）

acm模板（全）

ACM-ICPC模板整理

acm7060f-301T50

上海交通大学acm 模板

ACM-ICPC真题

中山大学acm模板.pdf

acm模板整理和使用方法

acm-icpc国际大学生程序设计竞赛 知识与入门

上海交通大学 acm模板

aws cli 上传证书到acm

linux 内核配置CONFIG_USB_CONFIGFS_ACM、CONFIG_USB_CONFIGFS_NCM、CONFIG_USB_CONFIGFS_RNDIS

ACM-ICPC赛题

acm.hi-54.com答案

SELECT avg(ontime) count from acm_operatelog ORDER BY modify_time DESC LIMIT 100；报错ERROR: column "acm_operatelog.modify_time" must appear in the GROUP BY clause or be used in an aggregate function LINE 1: ...(ontime) count from acm_operatelog ORDER BY modify_tim...

链接：https://ac.nowcoder.com/acm/problem/22001 来源：牛客网 任意给出一个小数，编程求不小于它的最小整数与不大于它的最大整数。 即求出这个小数往下取整与往上取整的值。

int ACM(int M, int N) { if (M==0) return N+1; else if (N==0) return ACM(M-1,1); else return ACM(M-1,ACM(M,N-1)); } 调用 cout<<ACM(2,2) 上述代码结果是多少

最新资源

acm-icpc国际大学生程序设计竞赛知识与入门

链接：https://ac.nowcoder.com/acm/problem/22001 来源：牛客网任意给出一个小数，编程求不小于它的最小整数与不大于它的最大整数。即求出这个小数往下取整与往上取整的值。