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

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

ACM模板-f_zyj是一位ACMer在2016年12月1日分享的一份精心整理的竞赛编程模板。这份模板的初衷是为了提高编程效率和代码质量，使其易于阅读和理解。作者花费大量时间进行格式化和修正，力求让代码既符合标准写法，又具有正确性、可读性和严谨性。模板主要针对C++语言，因为作者偏好C++，并且是专门为ACM（算法竞赛）设计的。模板的创建过程并非原创，而是基于社区内广泛接受的算法和数据结构代码优化，这些代码经过多人的不断迭代和完善。模板包含了8种主要的分类，如STL（Standard Template Library，标准模板库）部分，这是C++编程的重要组成部分，用于处理各种数据结构和算法。然而，分类的设定可能存在主观性，作者欢迎读者提出改进意见或推荐更优的代码，以便模板能够持续地学习和成长。此外，模板的更新和维护将在作者的个人博客进行，读者如有疑问或建议可以通过博客留言或私信与作者交流。这份模板的重要性在于提供了一个起点，帮助参赛者组织和优化他们的代码，以便在有限的时间内解决复杂的问题。总结来说，ACM模板-f_zyj是一个实用的工具，旨在提升ACMer们的编程效率，通过共享和交流，推动整个社区的技术进步。模板的使用者可以根据自己的需求进行微调，使之适应个人编程风格和比赛要求。

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

粉丝: 2992
资源: 24

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

下载ACM模板-f_zyj.zip，高积分证明其价值

ACM竞赛模板整理与优化-f_zyj v 2.1

ACM竞赛模板-f_zyj v 2.11：编程必备资源

ACM模板-f_zyj.zip_ACM模板_ACM模板-f_zyj_CSDN积分_acm必备模板_f_zyj ACM

ACM模板-f_zyj v

ACM模板-f_zyj v 2.11

ACM模板-f_zyj v 2.1.pdf

ACM:包含 ACM模板-f_zyj v 2.1，以及个人平时训练的代码……

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

bryce1010-ACM-Template:人一我百，人十我万，追逐青春的梦想，怀着自信的心，永不放弃！by kuangbin （Bryce1010 ACM模板）

最新资源