C 13-STL模板
在线练习： http://noi.openjudge.cn/ https://www.luogu.com.cn/
大纲要求
【 3 】算法模板库中的函数：min、max、swap、sort 【 4 】栈 (stack)、队列 (queue)、链表 (list)、 向量（vector）等容器
1.函数模板
泛型编程
不再是针对某种类型，能适应广泛的类型 如下的交换函数：
代码语言：javascript复制#include <iostream>
using namespace std;
//交换int类型
void Swap(int& left, int& right)
{
int temp = left;
left = right;
right = temp;
}
//利用C 支持的函数重载交换double类型
void Swap(double& left, double& right)
{
double temp = left;
left = right;
right = temp;
}
main()
{
int int_left=1,int_right=2;
double dou_left=5.0,dou_right=6.0;
Swap(int_left,int_right);
printf("int_left-->%d,int_right-->%d n",int_left,int_right);
Swap(dou_left,dou_right);
printf("dou_left-->%f,dou_right-->%f",dou_left,dou_right);
}
使用函数重载虽然可以实现不同类型的交换函数，但是有以下几个不好的地方： 重载的函数仅仅是类型不同，代码复用率比较低，只要有新类型出现时，就需要用户自己增加对应的函数，使得代码重复性高，过渡冗余 代码的可维护性比较低，一个出错可能所有的重载均出错 那能否告诉编译器一个模子，让编译器根据不同的类型利用该模子来生成代码呢？
函数模板
函数模板代表了一个函数家族，该函数模板与类型无关，在使用时被参数化，根据实参类型产生函数的特定类型版本。
函数模板的格式如下:
代码语言：javascript复制template<typename T1, typename T2,......,typename Tn>
返回值类型 函数名(参数列表)
{
//……
}注意：typename是用来定义模板参数关键字，也可以使用class(切记：不能使用struct代替class)
代码语言：javascript复制#include <iostream>
using namespace std;
template<typename T>
void Swap(T& rx, T& ry) {
T tmp = rx;
rx = ry;
ry = tmp;
}
main()
{
int int_left=1,int_right=2;
double dou_left=5.0,dou_right=6.0;
Swap(int_left,int_right);
printf("int_left-->%d,int_right-->%d n",int_left,int_right);
Swap(dou_left,dou_right);
printf("dou_left-->%f,dou_right-->%f",dou_left,dou_right);
}
问题：我上述交换函数调用过程中的Swap都是调用的同一个函数吗？ 当然不是，这里我三次Swap不是调用同一个函数，其实我Swap的时候根据不同的类型通过模板定制出专属你的类型的函数，然后再调用， 如下图：
面向对象
代码语言：javascript复制#include<iostream>
#include<cstring>
//#include<bits/stdc .h>
using namespace std;
class Person
{
public:
char* _name;
int _sex;
int _age;
/*
系统默认C 在类中普通成员方法第一个参数是类的指针，不可以手动写
类的普通成员方法的形参列表第一个参数是this指针，默认不感知，不可以手动写
类的普通成员方法使用的成员前面默认加上this->,不感知，也可以手动写
*/
//构造函数
Person(/*Person *const this*/const char* name, int sex, int age)
{
_name = new char[strlen(name) 1];
strcpy_s(_name, strlen(name) 1, name);
_sex = sex;
_age = age;
}
//没有参数的构造函数称为默认构造函数
Person()
{
cout << "Person()" << endl;
}
//拷贝构造函数
//要传&不能直接传对象，如果没有&，相当于Person src=per直接拷贝过程，从而进入死递归;
Person(Person& src)
{
_name = new char[strlen(src._name) 1];
strcpy_s(_name, strlen(src._name) 1, src._name);
_age = src._age;
cout << "Person(Person& src)" << endl;
}
//等号运算符重载
Person& operator=(const Person& src)
{
cout << "Person& operator=(const Person& src)" << endl;
//防止自赋值
if (&src == this)
{
return *this;
}
//防止内存泄漏
delete[]_name;
//防止浅拷贝
_name = new char[strlen(src._name) 1];
strcpy_s(_name, strlen(src._name) 1, src._name);
_sex = src._sex;
_age = src._age;
return *this;
}
//析构函数
~Person()
{
if (NULL != _name)
{
delete[]_name;
_name = NULL;
cout << "~Person()" << endl;
}
}
void eat()
{
cout << _name << " eat eat eat ······" << endl;
}
void run()
{
cout << _name << " run run run ······" << endl;
}
void sleep()
{
cout << _name << " sleep sleep sleep ······" << endl;
}
void show()
{
cout << "name:" << _name << endl;
cout << "sex:" << _sex << endl;
cout << "age:" << _age << endl;
}
};
int main()
{
//生成对象的过程叫做构造，自动调用构造函数
Person per(/*&per*/"zhangsan",32,1);
//Person per1;//ok
//Person per1();//error,编译器不知道是函数声明还是构造对象
//用一个已经存在的对象构造一个正在生成的对象
//叫做拷贝构造
Person per1(per);//等价于Person per1=per
Person per2 = per;
//per.show(/*&per*/);
//per.eat(/*&per*/);
//per.run(/*&per*/);
//per.sleep(/*&per*/);
//cout << "==========================" << endl;
//per1.show();
//per._name[4] = '8';
//per.show();
//per1.show();
//用已存在的对象给已存在的对象赋值
per1 = per = per2;//赋值
//per1.show();
per = per;
}
类模板
类模板的作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来代表。
格式：
代码语言：javascript复制template<typename T>代码语言：javascript复制template声明创建模板 typename表明其后面的符号是一种数据类型，可以用class代替 T是通用的数据类型，名称可以替换，通常为大写字母
#include<iostream>
using namespace std;
//类模板
template<class NameType, class AgeType>
class Person
{
public:
Person(NameType name, AgeType age)
{
this->m_Age = age;
this->m_Name = name;
}
void showPerson()
{
cout << "name: " << this->m_Name << "age: " << this->m_Age << endl;
}
NameType m_Name;
AgeType m_Age;
};
void test01()
{
Person<string, int> p1("孙悟空", 999);
p1.showPerson();
}
int main()
{
test01();
system("pause");
return 0;
}
2.算法模板库中的函数:min、max、swap、sort
使用algorithm头文件，需要在头文件下加一行“using namespace std”
1.max()、min()、abs()
max(x,y)和min(x,y)分别返回x和y中的最大值和最小值，且参数必须是两个(可以是浮点数)。如果想要返回三个数x、y、z的最大值，可以使用max(x,max(y,z)的写法。
abs(x)返回x的绝对值。注意：x必须是整数，浮点型的绝对值请用math头文件下的fabs。
代码语言：javascript复制#include<cstdio>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
int x=1,y= -2;
float xf=1.0,yf=-2.10;
printf("%d %dn",max(x,y),min(x,y));
printf("%d %dn",abs(x),abs(y));
printf("%.2f %.2fn",abs(xf),abs(yf));
printf("%.2f %.2fn",fabs(xf),fabs(yf));
return 0;
}
3.swap()
代码语言：javascript复制// This program demonstrates the use of the swap function template.
#include <iostream>
#include <string>
#include <algorithm> // Needed for swap
using namespace std;
int main ()
{
// Get and swap two chars
char firstChar, secondChar;
cout << "Enter two characters: ";
cin >> firstChar >> secondChar;
swap(firstChar, secondChar);
cout << firstChar << " " << secondChar << endl;
// Get and swap two ints
int firstInt, secondInt;
cout << "Enter two integers: ";
cin >> firstInt >> secondInt;
swap(firstInt, secondInt);
cout << firstInt << " " << secondInt << endl;
// Get and swap two strings
cout << "Enter two strings: ";
string firstString, secondString;
cin >> firstString >> secondString;
swap(firstString, secondString);
cout << firstString << " " << secondString << endl;
return 0;
}
3.sort()
在C 中，sort()函数常常用来对容器内的元素进行排序，先来了解一下sort()函数。
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
int a[4]={1,5,0,2};
int main()
{
// cin>>a[1]>>a[2]>>a[3];
sort(a 1,a 4);
cout<<a[3]<<' '<<a[2]<<' '<<a[1];
return 0;
}
sort()函数有三个参数：
第一个是要排序的容器的起始迭代器。 第二个是要排序的容器的结束迭代器。 第三个参数是排序的方法，是可选的参数。
默认的排序方法是从小到大排序，也就是less<Type>()，还提供了greater<Type>()进行从大到小排序。这个参数的类型是函数指针，less和greater实际上都是类/结构体，内部分别重载了()运算符，称为仿函数，所以实际上less<Type>()和greater<Type>()都是函数名，也就是函数指针。我们还可以用普通函数来定义排序方法。
如果容器内元素的类型是内置类型或string类型，我们可以直接用less<Type>()或greater<Type>()进行排序。但是如果数据类型是我们自定义的结构体或者类的话，我们需要自定义排序函数，有三种写法：
重载 < 或 > 运算符：重载 < 运算符，传入less<Type>()进行升序排列。重载 > 运算符，传入greater<Type>()进行降序排列。这种方法只能针对一个维度排序，不灵活。 普通函数：写普通函数cmp，传入cmp按照指定规则排列。这种方法可以对多个维度排序，更灵活。 仿函数：写仿函数cmp，传入cmp<Type>()按照指定规则排列。这种方法可以对多个维度排序，更灵活。
重写操作符号
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
struct Person {
int id;
int age;
Person(int id,int age):id(id),age(age){}
//重载<运算符，进行升序排列
bool operator < (const Person& p2) const {
return id < p2.id;
}
//重载>运算符，进行降序排列
bool operator > (const Person& p2) const {
return id > p2.id;
}
};
int main()
{
Person p1(1, 10), p2(2, 20), p3(3, 30);
vector<Person> ps;
ps.push_back(p2);
ps.push_back(p1);
ps.push_back(p3);
sort(ps.begin(), ps.end(), less<Person>());
for (int i = 0; i < 3; i ) {
cout << ps[i].id << " " << ps[i].age << endl;
}
cout << endl;
sort(ps.begin(), ps.end(), greater<Person>());
for (int i = 0; i < 3; i ) {
cout << ps[i].id << " " << ps[i].age << endl;
}
cout << endl;
}
普通函数
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
struct Person {
int id;
int age;
Person(int id,int age):id(id),age(age){}
};
//普通函数
bool cmp(const Person& p1, const Person& p2) {
if (p1.id == p2.id) return p1.age >= p2.age;
return p1.id < p2.id;
}
int main()
{
Person p1(1, 30), p2(2, 20), p3(1, 20),p4(3, 30), p5(3, 40);
vector<Person> ps;
ps.push_back(p2);
ps.push_back(p1);
ps.push_back(p3);
ps.push_back(p4);
ps.push_back(p5);
sort(ps.begin(), ps.end(), cmp);//传入函数指针cmp
for (int i = 0; i < 5; i ) {
cout << ps[i].id << " " << ps[i].age << endl;
}
}
仿函数
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
struct Person {
int id;
int age;
Person(int id, int age) :id(id), age(age) {}
};
//仿函数
struct cmp {
bool operator()(const Person& p1, const Person& p2) {
if (p1.id == p2.id) return p1.age >= p2.age;
return p1.id < p2.id;
}
};
int main()
{
Person p1(1, 30), p2(2, 20), p3(1, 20),p4(3, 30), p5(3, 40);
vector<Person> ps;
ps.push_back(p2);
ps.push_back(p1);
ps.push_back(p3);
ps.push_back(p4);
ps.push_back(p5);
sort(ps.begin(), ps.end(), cmp()); //传入函数指针cmp()
for (int i = 0; i < 5; i ) {
cout << ps[i].id << " " << ps[i].age << endl;
}
}
3.STL-栈 (stack)、队列 (queue)、链表 (list)、向量（vector）等容器
3.1STL 标准模板库-栈 (stack)
代码语言：javascript复制#include <stack>功能描述： 栈容器常用的对外接口
构造函数：
代码语言：javascript复制stack<T> stk; //stack采用模板类实现， stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数赋值操作：
代码语言：javascript复制stack& operator=(const stack &stk); //重载等号操作符数据存取：
代码语言：javascript复制push(elem); //向栈顶添加元素（注意入栈是push而非push_back
pop(); //从栈顶移除第一个元素
top(); //返回栈顶元素大小操作：
代码语言：javascript复制empty(); //判断堆栈是否为空
size(); //返回栈的大小#include <stack>
#include <iostream>
using namespace std;
//栈容器常用接口
void test01()
{
//创建栈容器 栈容器必须符合先进后出
stack<int> s;
//向栈中添加元素，叫做 压栈 入栈
s.push(10);
s.push(20);
s.push(30);
cout <<"栈的大小为：" << s.size() << endl;
while (!s.empty()) {
//输出栈顶元素
cout << "栈顶元素为： " << s.top() << endl;
//弹出栈顶元素
s.pop();
}
cout << "栈的大小为：" << s.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
stack<char> st;
int main()
{
string s;
cin>>s;
int m=s.length();
for(int i=0;s[i]!='@'&&i<m;i )
{
if(st.empty()) //排除可能出现的例如)（ab）(的情形
{
if(s[i]==')')
{
cout<<"NO";
return 0;
}
}
if(s[i]=='(')
{
st.push('(');
}
else if(s[i]==')')
{
st.pop();
}
}
if(!st.empty())
{
cout<<"NO";
}
else
{
cout<<"YES";
}
return 0;
}#include<bits/stdc .h>
using namespace std;
int main()
{
int c,tot=0;//tot初始化
while((c=getchar())!='@')
{
if(c=='(')tot ;
else if(c==')')tot--;
if(tot==-1)break;//防止误判
}
if(tot==0)cout<<"YES";//括号匹配要在正反括号数量相等的前提下
else cout<<"NO";
return 0;
}3.2STL 标准模板库-向量（vector）
代码语言：javascript复制STL 标准模板库，由惠普实验室提供，里面集成了常用的数据结构类模板和算法函数模板等。 容器：用来存储各类型数据的数据结构。 迭代器：类似于专门用来指向容器成员的指针，用来遍历、操作、管理容器中的成员，可以大大提高容器的访问速度。 算法：STL实现了常见的排序、查找算法。 STL-栈 (stack)、队列 (queue)、链表 (list)、向量（vector）等容器
#include <vector> vector是变长数组，支持随机访问，不支持在任意位置O(1)插入。为了保证效率，元素的增删一般应该在末尾进行。
1. 初始化方法：
a. 通过赋值方式初始化：
代码语言：javascript复制std::vector<int> v1 = {1, 2, 3, 4, 5}; // 初始化一个包含5个元素的vector
std::vector<std::string> v2 = {"hello", "world"}; // 初始化一个包含2个字符串的vectorb. 通过构造函数方式初始化：
代码语言：javascript复制std::vector<int> v3(10); // 初始化一个包含10个元素的vector，每个元素的值为0
std::vector<int> v4(5, 2); // 初始化一个包含5个元素的vector，每个元素的值为2
std::vector<std::string> v5(3, "hello"); // 初始化一个包含3个字符串的vector，每个字符串的值为"hello"c. 通过拷贝方式初始化：
代码语言：javascript复制std::vector<int> v6(v1); // 将v1中的元素拷贝到v6中2. 常用操作函数：
1. 插入元素：
代码语言：javascript复制std::vector<int> v7 = {1, 2, 3};
v7.push_back(4); // 在vector的末尾插入一个元素
v7.insert(v7.begin() 2, 5); // 在vector的第3个位置插入一个元素，值为52. 删除元素：
代码语言：javascript复制std::vector<int> v8 = {1, 2, 3,4,5};
v8.pop_back(); // 删除vector的最后一个元素
v8.erase(v8.begin() 1); // 删除vector的第2个元素
v8.erase(a.begin() 1,a.begin() 3); //删除a中第1个（从第0个算起）到第2个元素，也就是说删除的元素从a.begin() 1算起（包括它）一直到a.begin() 3（不包括它）3. 访问元素：
代码语言：javascript复制std::vector<int> v9 = {1, 2, 3};
int x = v9[1]; // 获取vector的第2个元素
int y = v9.at(2); // 获取vector的第3个元素，如果越界会抛出异常
int z = v9.front(); // 获取vector的第1个元素
int w = v9.back(); // 获取vector的最后一个元素4. 修改元素：
代码语言：javascript复制std::vector<int> v10 = {1, 2, 3};
v10[1] = 4; // 修改vector的第2个元素的值为4
v10.at(2) = 5; // 修改vector的第3个元素的值为5，如果越界会抛出异常5. 返回大小：size/empty
size函数返回vector的实际长度（包含的元素个数），empty函数返回一个bool类型，表明vector是否为空。二者的时间复杂度都是O(1)。 所有的STL容器都支持这两个方法，含义也相同，之后我们就不再重复给出。
6. clear
clear函数把vector清空。
7. 迭代器
代码语言：javascript复制迭代器就像STL容器的“指针”，可以用星号“*”操作符解除引用。 一个保存int的vector的迭代器声明方法为：
vector<int>::iterator it;vector的迭代器是“随机访问迭代器”，可以把vector的迭代器与一个整数相加减，其行为和指针的移动类似。可以把vector的两个迭代器相减，其结果也和指针相减类似，得到两个迭代器对应下标之间的距离。
8. begin/end
begin函数返回指向vector中第一个元素的迭代器。例如a是一个非空的vector，则*a.begin()与a[0]的作用相同。 所有的容器都可以视作一个“前闭后开”的结构，end函数返回vector的尾部，即第n个元素再往后的“边界”。*a.end()与a[n]都是越界访问，其中n=a.size()。
下面两份代码都遍历了vector<int>a，并输出它的所有元素。
代码语言：javascript复制#include <iostream>
#include <vector>
using namespace std;
int main()
{
std::vector<int> v9 = {1, 2, 3};
int x = v9[1]; // 获取vector的第2个元素
int y = v9.at(2); // 获取vector的第3个元素，如果越界会抛出异常
int z = v9.front(); // 获取vector的第1个元素
int w = v9.back(); // 获取vector的最后一个元素
for (int i = 0; i < v9.size(); i ) cout << v9[i] << endl;
for (vector<int>::iterator it = v9.begin(); it != v9.end(); it ) cout << *it << endl;
return 0;
}
统计数组中的元素案例
代码语言：javascript复制#include<iostream>
using namespace std;
//算法 负责统计某个元素出现多少次
int mycount(int* start,int * end,int val)
{
int num = 0;
while (start != end)
{
if (*start == val)
num ;
start ;
}
return num;
}
int main()
{
//数组 容器
int arr[] = { 1,2,4,5,3,8,9,1,4,4 };
int* pBegin = arr;//指针 迭代器
int* pEnd = &arr[(sizeof(arr) / sizeof(arr[0]))];
int num = mycount(pBegin, pEnd, 4);
cout << num << endl;
return 0;
}统计数组中的元素案例-vector版本
代码语言：javascript复制#include<iostream>
#include<vector>//动态数组 容器vector
#include<algorithm>//算法
using namespace std;
//回调函数
void myprint(int v)
{
cout << v << endl;
}
//stl基本语法
void text01()
{
//定义容器
vector<int> v;
v.push_back(10);
v.push_back(34);
v.push_back(40);
v.push_back(40);
//通过STL提供的for_each算法
//容器提供迭代器
//vector<int>::iterator迭代器类型
vector<int>::iterator pBegin = v.begin();
vector<int>::iterator pEnd = v.end();
//容器中可能存在基础的数据类型，也可以放自定义的数据类型
//for_each（start，end，回调函数）
//算法
for_each(pBegin, pEnd, myprint);
//计数
int count1 = count(v.begin(), v.end(),40);
cout << "元素40在数组中出现的次数为 " << count1 << endl;
}
class Person
{
public:
int age;
int id;
Person(int age,int id):age(age),id(id)
{
}
};
void text02()
{
//创建容器，类型为person
vector<Person> v;
Person p1(30, 1), p2(23, 2), p3(54, 3), p4(30,4);
v.push_back(p1);
v.push_back(p2);
v.push_back(p3);
v.push_back(p4);
//自己写算法遍历
for (vector<Person>::iterator it = v.begin(); it != v.end(); it )
{
cout << (*it).age << " " << (*it).id << endl;
}
}
int main()
{
text01();//基本数据类型
text02();//类
return 0;
}
3.3 STL 标准模板库-队列queue
队列的概述
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
基于数组的循环队列实现
以数组作为底层数据结构时，一般讲队列实现为循环队列。这是因为队列在顺序存储上的不足：每次从数组头部删除元素（出队）后，需要将头部以后的所有元素往前移动一个位置，这是一个时间复杂度为O（n）的操作：
STL中的队列实现
参考:https://blog.csdn.net/weixin_43361652/article/details/113353918
队列先进先出 头文件：
代码语言：javascript复制<queue>常用操作：
代码语言：javascript复制queue<int> q：建立一个队列q，其内部元素类型是int。
q.push(a)：将元素a插入到队列q的末尾。
q.pop()：删除队列q的队首元素。
q.front()：查询q的队首元素。
q.back()：查询q的队尾元素。
q.size()：查询q的元素个数。
q.empty()：查询q是否为空。
#include <iostream>
#include <queue>
using namespace std;
int main()
{
// 定义一个队列，存放 int 类型的数据
queue<int> q;
// 将一些数据入队
for (int i = 1; i <= 5; i ) {
q.push(i);
}
// 输出队列中的元素个数
cout << "Size of queue: " << q.size() << endl;
// 输出队列中的所有元素
cout << "Queue elements: ";
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
// 输出队列中的元素个数
cout << "nSize of queue: " << q.size() << endl;
return 0;
}
参考:https://blog.csdn.net/weixin_44572229/article/details/120016366
代码语言：javascript复制#include <queue>头文件queue主要包括循环队列queue和优先队列priority_queue两个容器。
声明
代码语言：javascript复制queue<int> q;
struct rec{…}; queue<rec> q; //结构体rec中必须定义小于号
priority_queue<int> q; // 大根堆
priority_queue<int, vector<int>, greater<int> q; // 小根堆
priority_queue<pair<int, int>>q;循环队列 queue与优先队列 priority_queue
循环队列 queue
代码语言：javascript复制push 从队尾插入
pop 从队头弹出
front 返回队头元素
back 返回队尾元素优先队列 priority_queue
代码语言：javascript复制push 把元素插入堆
pop 删除堆顶元素
top 查询堆顶元素（最大值）双端队列deque
代码语言：javascript复制include <deque>双端队列deque是一个支持在两端高效插入或删除元素的连续线性存储空间。它就像是vector和queue的结合。与vector相比，deque在头部增删元素仅需要O(1)的时间；与queue相比，deque像数组一样支持随机访问。
代码语言：javascript复制begin/end，返回deque的头/尾迭代器
front/back 队头/队尾元素
push_back 从队尾入队
push_front 从队头入队
pop_back 从队尾出队
pop_front 从队头出队
clear 清空队列队列案例
T1333 : Blah数集 【题目描述】 大数学家高斯小时候偶然间发现一种有趣的自然数集合Blah，对于以a为基的集合Ba定义如下： (1)a是集合Ba的基，且a是Ba的第一个元素； (2)如果x在集合Ba中，则2x 1和3x 1也都在集合Ba中； (3)没有其他元素在集合Ba中了。 现在小高斯想知道如果将集合Ba中元素按照升序排列，第N个元素会是多少？ 【输入】 输入包括很多行，每行输入包括两个数字，集合的基a(1≤a≤50))以及所求元素序号n(1≤n≤1000000)。 【输出】 对于每个输入，输出集合Ba的第n个元素值。 【输入样例】 1 100 28 5437
【输出样例】 418 900585
【答案&代码】
代码语言：javascript复制#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6 5;
typedef long long ll;
ll a[N]; // 定义一个long long 数组
int main(){
int m,n;
// 把输入的第一个元素作为基数 第二个元素作为序号
while(cin>>a[1]>>n){
int rear=1,two=1,three=1;
// 重复n次
while(rear<n){
// t1赋值为2*第n个元素 1
// t2赋值为3*第n个元素 1
// t赋值为t1和t2中的最小值
int t1=a[two]*2 1,t2=a[three]*3 1,t=min(t1,t2);
// 如果t1>t2，three 否则 two
if(t1>t2)three ;
else two ;
// 如果 a[rear]<t
if(a[rear]<t)a[ rear]=t;
}
cout<<a[rear]<<endl;
}
return 0;
}队列版本
代码语言：javascript复制#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
using std::queue;
int ans[1000005];
// a为集合的基 n为第n个元素
int f(int a,int n)
{
queue<int>Q1,Q2;
int f=1,x=a;
// memset
// 所需头文件：#include<string.h>
//作用：给ans数组前n项所有内存赋值为0，注意，这里只取a的低8位，即a%6，也就是说memset是按照字节赋值的。
memset(ans,0,sizeof(ans));
for(int i=1; i<=n; i )
{
// “f ”是先进行取值，后进行自增“1”
ans[f ]=x;
// 每次都把当前的元素的2x 1和3x 1都放在两个队列中 单个队列是有序的
// 需要以此比较每个队列中的首元素大小，然后放在数组中
Q1.push(2*x 1),Q2.push(3*x 1);
// Q1.front返回队列头部元素
if(Q1.front()<Q2.front())
x=Q1.front(),Q1.pop();
else if(Q1.front()==Q2.front())
x=Q1.front(),Q1.pop(),Q2.pop();
else
x=Q2.front(),Q2.pop();
}
return ans[n];
}
int main(void)
{
int a,n;
while(scanf("%d%d",&a,&n)!=EOF)
printf("%dn",f(a,n));
return 0;
}
3.4 STL 标准模板库-链表list
list定义
List是stl实现的双向链表，与向量(vectors)相比, 它允许快速的插入和删除，但是随机访问却比较慢。使用时需要添加头文件
代码语言：javascript复制#include <list>list定义和初始化
代码语言：javascript复制 list<int>lst1; //创建空list
list<int> lst2(5); //创建含有5个元素的list
list<int>lst3(3,2); //创建含有3个元素的list
list<int>lst4(lst2); //使用lst2初始化lst4
list<int>lst5(lst2.begin(),lst2.end()); //同lst4list常用操作
代码语言：javascript复制 list常用操作函数
Lst1.assign() 给list赋值
Lst1.back() 返回最后一个元素
Lst1.begin() 返回指向第一个元素的迭代器
Lst1.clear() 删除所有元素
Lst1.empty() 如果list是空的则返回true
Lst1.end() 返回末尾的迭代器
Lst1.erase() 删除一个元素
Lst1.front() 返回第一个元素
Lst1.get_allocator() 返回list的配置器
Lst1.insert() 插入一个元素到list中
Lst1.max_size() 返回list能容纳的最大元素数量
Lst1.merge() 合并两个list
Lst1.pop_back() 删除最后一个元素
Lst1.pop_front() 删除第一个元素
Lst1.push_back() 在list的末尾添加一个元素
Lst1.push_front() 在list的头部添加一个元素
Lst1.rbegin() 返回指向第一个元素的逆向迭代器
Lst1.remove() 从list删除元素
Lst1.remove_if() 按指定条件删除元素
Lst1.rend() 指向list末尾的逆向迭代器
Lst1.resize() 改变list的大小
Lst1.reverse() 把list的元素倒转
Lst1.size() 返回list中的元素个数
Lst1.sort() 给list排序
Lst1.splice() 合并两个list
Lst1.swap() 交换两个list
Lst1.unique() 删除list中相邻重复的元素链表list案例
代码语言：javascript复制#include <iostream>
#include <list>
#include <numeric>
#include <algorithm>
using namespace std;
typedef list<int> LISTINT;
typedef list<int> LISTCHAR;
int main()
{
//用LISTINT创建一个list对象
LISTINT listOne; //声明i为迭代器
LISTINT::iterator i;
listOne.push_front(3);
listOne.push_front(2);
listOne.push_front(1);
listOne.push_back(4);
listOne.push_back(5);
listOne.push_back(6);
cout << "listOne.begin()--- listOne.end():" << endl;
for (i = listOne.begin(); i != listOne.end(); i)
cout << *i << " ";
cout << endl;
LISTINT::reverse_iterator ir;
cout << "listOne.rbegin()---listOne.rend():" << endl;
for (ir = listOne.rbegin(); ir != listOne.rend(); ir )
{
cout << *ir << " ";
}
cout << endl;
int result = accumulate(listOne.begin(), listOne.end(), 0);
cout << "Sum=" << result << endl;
cout << "------------------" << endl;
//用LISTCHAR创建一个list对象
LISTCHAR listTwo;
//声明i为迭代器
LISTCHAR::iterator j;
listTwo.push_front('C');
listTwo.push_front('B');
listTwo.push_front('A');
listTwo.push_back('D');
listTwo.push_back('E');
listTwo.push_back('F');
cout << "listTwo.begin()---listTwo.end():" << endl;
for (j = listTwo.begin(); j != listTwo.end(); j)
cout << char(*j) << " ";
cout << endl;
j = max_element(listTwo.begin(), listTwo.end());
cout << "The maximum element in listTwo is: " << char(*j) << endl;
system("pause");
return 0;
}
3.5 STL 标准模板库-集合set
代码语言：javascript复制include <set>头文件set主要包括set和multiset两个容器，分别是“有序集合”和“有序多重集合”，即前者的元素不能重复，而后者可以包含若干个相等的元素。set和multiset的内部实现是一棵红黑树，它们支持的函数基本相同。
声明
代码语言：javascript复制set<int> s;
struct rec{…}; set<rec> s; // 结构体rec中必须定义小于号
multiset<double> s;size/empty/clear 与vector类似
迭代器 set和multiset的迭代器称为“双向访问迭代器”，不支持“随机访问”，支持星号(*)解除引用，仅支持” ”和–“两个与算术相关的操作。 设it是一个迭代器，例如set::iterator it; 若把it ，则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中，排在it下一名的元素。同理，若把it–，则it将会指向排在“上一个”的元素。
代码语言：javascript复制begin/end
返回集合的首、尾迭代器，时间复杂度均为O(1)。
s.begin() 是指向集合中最小元素的迭代器。s.end() 是指向集合中最大元素的下一个位置的迭代器。换言之，就像vector一样，是一个“前闭后开”的形式。因此–s.end()是指向集合中最大元素的迭代器。
代码语言：javascript复制insert
s.insert(x)把一个元素x插入到集合s中，时间复杂度为O(logn)。
在set中，若元素已存在，则不会重复插入该元素，对集合的状态无影响。
finds.find(x) 在集合s中查找等于x的元素，并返回指向该元素的迭代器。若不存在，则返回s.end()。时间复杂度为O(logn)。
代码语言：javascript复制lower_bound/upper_bound
这两个函数的用法与find类似，但查找的条件略有不同，时间复杂度为 O(logn)。s.lower_bound(x) 查找大于等于x的元素中最小的一个，并返回指向该元素的迭代器。 s.upper_bound(x) 查找大于x的元素中最小的一个，并返回指向该元素的迭代器。
代码语言：javascript复制erase设it是一个迭代器，s.erase(it) 从s中删除迭代器it指向的元素，时间复杂度为O(logn) 设x是一个元素，s.erase(x) 从s中删除所有等于x的元素，时间复杂度为O(k logn)，其中k是被删除的元素个数。
代码语言：javascript复制count
s.count(x) 返回集合s中等于x的元素个数，时间复杂度为 O(k logn)，其中k为元素x的个数。3.6 STL 标准模板库-字典map
代码语言：javascript复制#include <map>map容器是一个键值对key-value的映射，其内部实现是一棵以key为关键码的红黑树。Map的key和value可以是任意类型，其中key必须定义小于号运算符。
声明
代码语言：javascript复制map<key_type, value_type> name;
map<string , int >mapstring;
map<int ,string >mapint;
map<sring, char>mapstring;
map< char ,string>mapchar;
map<char ,int>mapchar;
map<int ,char >mapint；
//例如：
map<long, long, bool> vis;
map<string, int> hash;
map<pair<int, int>, vector<int>> test;基本操作:
代码语言：javascript复制begin() 返回指向map头部的迭代器
clear(） 删除所有元素
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数size/empty/clear/begin/end均与set类似。
Insert/erase与set类似，但其参数均是pair<key_type, value_type>。
find: h.find(x) 在变量名为h的map中查找key为x的二元组。
[]操作符 h[key] 返回key映射的value的引用，时间复杂度为O(logn)。 []操作符是map最吸引人的地方。我们可以很方便地通过h[key]来得到key对应的value，还可以对h[key]进行赋值操作，改变key对应的value。
案例
代码语言：javascript复制#include <iostream>
#include <list>
#include <numeric>
#include <algorithm>
#include<map>
using namespace std;
int main()
{
// 初始化map
map<int,string> maplive;
maplive.insert(pair<int,string>(102,"aclive"));
maplive.insert(map<int,string>::value_type(321,"hai"));
maplive[112]="April";//map中最简单最常用的插入添加！
// 获取map迭代器
map<int,string >::iterator l_it;;
l_it=maplive.find(112);
if(l_it==maplive.end())
cout<<"we do not find 112"<<endl;
else cout<<"wo find 112"<<endl;
cout<<"---------------"<<endl;
//迭代数据、遍历数据
std::map<int,string>::iterator itTmp_3;
for(itTmp_3 = maplive.begin(); itTmp_3 != maplive.end(); itTmp_3)
{
std::cout << "key:" << itTmp_3 -> first << " " << "value:" << itTmp_3 ->second << "n";
}
for(auto temp : maplive)
{
//输出键值key
std::cout << temp.first << "n";
}
for(auto tem : maplive)
{
//输出键值对应的Value
std::cout << tem.second << "n";
}
cout<<"---------------"<<endl;
// map<int,string >::iterator l_it;
l_it=maplive.find(112);
if(l_it==maplive.end())
cout<<"we do not find 112"<<endl;
else maplive.erase(l_it); //delete 112;
//迭代数据、遍历数据
// std::map<int,string>::iterator itTmp_3;
for(itTmp_3 = maplive.begin(); itTmp_3 != maplive.end(); itTmp_3)
{
std::cout << "key:" << itTmp_3 -> first << " " << "value:" << itTmp_3 ->second << "n";
}
for(auto temp : maplive)
{
//输出键值key
std::cout << temp.first << "n";
}
for(auto tem : maplive)
{
//输出键值对应的Value
std::cout << tem.second << "n";
}
cout<<"---------------"<<endl;
return 0;
}
