【No.8】蓝桥杯工具函数模板|迭代器|vector|queue|map|set|银行问题|费里的语言|快递分拣(C++)

• 迭代器讲解
• 线性表的使用
• 队列的使用
• 集合（set）的使用
• 映射（map）的使用

迭代器（Iterator）

迭代器是 C++ 的知识，但是下面讲容器就要用到这一点，所以我们必须要提前讲一下。迭代器的知识点很复杂，了解即可，当然有余力可以深究，了解就能做题，实现方式看容器讲解。
对于数组我们可以采用指针进行访问，但是对于其他的存储空间连续的数据结构或者说是存储单元我们就需要找到另一种方式来替代指针的行为作用，从而达到对于非数组的数据结构的访问和遍历，于是我们定义了一种新的变量叫做迭代器。
定义：
迭代器是一种检查容器内元素并遍历元素的数据类型。
迭代器提供对一个容器中的对象的访问方法，并且定义了容器中对象的范围。
迭代器和指针的区别：
容器和string有迭代器类型同时拥有返回迭代器的成员。
如：容器有成员 .begin() 和 .end()，其中 .begin() 成员复制返回指向第一个元素的迭代器，即指向第一个元素的“地址”，而 .end() 成员返回指向容器尾元素的下一个位置的迭代器。
[1,2,3]
即 .begin() 指向的是第一个合法元素的位置，也就是1，.end() 指向是容器后第一个不合法元素的地址，也就是3后面的一个位置。
相应的还有容器反向迭代器成员 .rbegin() .rend()，.rbegin() 返回容器的元素前最后一个不合法的地址，也就是1前面的位置，rend() 返回容器的最后一个合法地址，也就是3所在的位置。

容器迭代器的使用

每种容器类型都定义了自己的迭代器类型：

如 vector：vector<int>::iterator iter;//定义一个名为iter的变量

数据类型是由 vector<int> 定义的 iterator 类型。简单说就是容器类定义了自己的 iterator 类型，用于访问容器内的元素。每个容器定义了一种名为 iterator 的类型，这种类型支持迭代器的各种行为。

Vector 容器（类）

线性表中有 Vector 和 list，两者作用比较相似。
vector是随机访问的，可以当作数组去使用，list不行，list随机访问的时间是$O(n)$的，而vector是$O(1)$的，所以会选择vector而不是list
Vector 的主要作用就是可变长度的数组，就把他当成数组使用即可，非常简单，也非常方便。
C++ 的 Vector 使用：

#include <vector>   //头文件
vector<int> a;      //定义了一个int类型的vector容器a
vector<int> b[100]; //定义了一个int类型的vector容器b组
//定义100个容器，每个容器是无限可放的
//vector里可以放入自定义类型
struct rec
{
    ···
};
vector<rec> c;            //定义了一个rec类型的vector容器c
vector<int>::iterator it; //vector的迭代器，与指针类似

具体操作如下：

a.size()       //返回实际长度（元素个数），O(1)复杂度
a.empty()      //容器为空返回1，否则返回0，O(1)复杂度
a.clear()      //把vector清空
a.begin()      //返回指向第一个元素的迭代器，*a.begin()与a[0]作用相同
a.end()        //越界访问，指向vector尾部，指向第n个元素再往后的边界
a.front()      //返回第一个元素的值，等价于*a.begin和a[0]
a.back()       //返回最后一个元素的值，等价于*--a.end()和a[size()-1]
a.push_back(x) //把元素x插入vector尾部
a.pop_back()   //删除vector中最后一个元素

遍历的方式有两种：

1. 迭代器使用与指针类似，可如下遍历整个容器。

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

 for ( auto it=a.begin() ; it!=a.end() ; it++ )
 cout<<*iterator<<endl;

2. 当成数组使用。

for( int i=0;i<a.size();i++) cout<<a[i]<<endl;

快递分拣

快递员需要对快递进行分拣，现在小李是一名快递员，他想要你帮他设计一个程序用于快递的分拣，按城市分开。
现在有以下输入：

单号 省份
请你将单号按照城市分开，并输出。
城市按照输入顺序排序
单号按照输入顺序排序

样例如下：

输入

10

10124214 北京
12421565  上海
sdafasdg213 天津
fasdfga124 北京
145252  上海
235wtdfsg 济南
3242356fgdfsg 成都
23423 武汉
23423565f 沈阳
1245dfwfs 成都

输出

北京 2
10124214
fasdfga124
上海 2
12421565
145252
天津 1
sdafasdg213
济南 1
235wtdfsg
成都 2
3242356fgdfsg
1245dfwfs
武汉 1
23423
沈阳 1
23423565f

解题思路

首先我们要知道中国城市肯定在 1000 个以内，但是单号我们不确定，我们不可能每个数组开 10000 个，那样内存不够，所以就用到了vector，他的容量是动态申请的，在比赛中我们可以理解为无限制。

• 第一步：我们创建一个 vector 用于保存地址

vector<string> city;

• 第二步：我们创建一个 vector 组用于存放单号

vector<string> dig[1000];

• 第三步：我们定义一个映射函数，因为你的城市可能会再次出现，你需要知道之前有没有。
• 第四步：我们开始读入操作并按照顺序进行存放

完整代码

#include<iostream>
#include<vector>
using namespace std;

vector<string> city;      //放城市
vector<string> dig[1000]; //放属于这个city单号

int Myfind(string s)  //找到它是第几个city的数字
{
    for(int i=0;i<city.size();i++)
    {
        if(city[i]==s) return i;
    }
    return -1;
}
int main()
{

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string d,c;
        cin>>d>>c;   //输入城市单号
        int flag=Myfind(c);
        if(flag==-1){  //如果没找到返回-1
            city.push_back(c);  //城市换一个新的
            dig[city.size()-1].push_back(d);  //size是从1开始的，对应的dig是从0开始的，所以size()-1，把单号换新的
        }
        else  dig[flag].push_back(d); //找到的话，把它放到所属城市的容器里面
    }
    for(int i=0;i<city.size();i++)
    {
        cout<<city[i]<<" "<<dig[i].size()<<endl;  //输出city和属于city的容器的大小
        for(int j=0;j<dig[i].size();j++)
            cout<<dig[i][j]<<endl;   //输出容器的内容
    }
}

队列 Queue

从左侧进，从右侧出
定义方式：在 C++ 里所有容器的定义方式基本一致。

queue<string> myqueue;
queue<int> myqueue_int;

成员函数:

• front()：返回 queue 中第一个元素的引用。
• back()：返回 queue 中最后一个元素的引用。
• push(const T& obj)：在 queue 的尾部添加一个元素的副本。
• pop()：删除 queue 中的第一个元素。
• size()：返回 queue 中元素的个数。
• empty()：如果 queue 中没有元素的话，返回 true。

CLZ 的银行。

第一行 M 次操作（M<1000）
第二行 到 第M+1行 输入操作

格式：

	IN name V
	OUT V
	IN name2 N
	OUT N

即 第一个字符串为操作
是IN进入排队和OUT 出队
IN 排队 跟着两个字符串为姓名和权限V或N
OUT 为出队即完成操作，V和N代表那个窗口完成了操作

输出：M次操作后V队列和N队列中姓名，先输出V队列后输出N队列。

样例：

输入：

5
IN xiaoming N
IN Adel V
IN laozhao N
OUT N
IN CLZ V

输出：

Adel
CLZ
laozhao

代码

#include <iostream>
#include <queue>
using namespace std;

queue<string> V;  //一个vip队列
queue<string> N;  //一个普通队列

int main()
{
    int M;
    cin>>M;  //输入M次操作

    while(M--)
    {
        string op,name,type;
        cin>>op;     //先输入op
        if(op=="IN") //是进队
        {
            cin>>name>>type;  //输入名字和属于哪个队

            if(type=="V")     //属于v队，进v队
                V.push(name);

            else              //属于n队，进n队
                N.push(name);
        }
        else   //不是入队，就是出队
        {
            cin>>type;  //输入哪个队

            if(type=="V")  //属于v队，v出队
                V.pop();
            else
                N.pop();  //属于n队，n出队

        }
    }

	//输出队列
    while(V.size())  //当队列中有元素时
    {
        cout<<V.front()<<endl;  //输出队首
        V.pop();  //把它出队
    }
    while(N.size())
    {
        cout<<N.front()<<endl;
        N.pop();
    }
}

Map 映射

map 是一个关联容器，它提供一对一的 hash。

• 第一个可以称为关键字(key)，每个关键字只能在 map 中出现一次
  • 函数中的x变量
• 第二个可能称为该关键字的值(value)
  • 根据x，一定能找到y
    map 以模板（泛型）方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。
    Map 主要用于资料一对一映射的情況，map 在 C++ 的內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在 map 内部所有的数据都是有序的。
    比如，像是管理班级内的学生，Key 值为学号，Value 放其他信息的结构体或者类。
    定义方式：

map<char, int> mymap1;
map<string, int> mymap2;

一般用法：

1. 看容量。

int map.size();//查询map中有多少对元素
bool empty();// 查询map是否为空

2. 插入。

    map.insert(make_pair(key,value));
    //或者
    map.insert(pair<char, int>(key, value))
    //或者
    map[key]=value

3. 取值。

map<int, string> map;

//如果map中没有关键字2233，使用[]取值会导致插入
//因此，下面语句不会报错，但会使得输出结果结果为空
cout<<map[2233]<<endl;

//但是使用使用at会进行关键字检查，因此下面语句会报错
map.at(2016) = "Bob";

4. 遍历操作

map<string, string>::iterator it;
for (it = mapSet.begin(); it != mapSet.end(); ++it)
{
    cout << "key" << it->first << endl;
    cout << "value" << it->second << endl;
}

5. 查找操作

m.count(key)：//由于map不包含重复的key，因此m.count(key)取值为0，或者1，表示是否包含。
m.find(key)：//返回迭代器，判断是否存在。

弗里石的的语言

小发明家弗里想创造一种新的语言，众所周知，发明一门语言是非常困难的，首先你就要克服一个困难就是，有大量的单词需要处理，现在弗里求助你帮他写一款程序，判断是否出现重复的两个单词。

有重复就输出重复单词，没有重复就输出 NO，
多个重复输出最先出现的哪一个。

输入：
第 1行，输入 N，代表共计创造了多少个单词
第 2 行至第 N+1 行，输入 N 个单词

格式：

fjsdfgdfsg
fdfsgsdfg
bcvxbxfyres

现在有以下样例输入：
样例 1

输入：

6
1fagas
dsafa32j
lkiuopybncv
hfgdjytr
cncxfg
sdhrest

输出：

NO

样例 2

输入：

5
sdfggfds
fgsdhsdf
dsfhsdhr
sdfhdfh
sdfggfds

输出：

sdfggfds

题目解析

使用映射解题

代码

 #include <iostream>
 #include <map>
 using namespace std;

map<string,bool> mp;
int main ()
{

    int n;
    string ans="NO";  //先定一个答案NO
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string word;
        cin>>word;   //输入单词
        if(mp.count(word)){  //计算出现的次数，如果有这个单词
            ans=word;  //输出
            break;
        }

        else mp[word]=1;  
    }
    cout<<ans<<endl;   //都处理完了，输出NO就可以了

}

Set 使用

在C++中，set是一个基于红黑树实现的关联容器，它可以自动将元素排序并保持唯一性。
默认情况下，set使用元素类型的<运算符来比较和排序其元素。
要一个自定义的排序准则，可以在声明set时指定一个比较函数或函数对象。

测试

#include <bits/stdc++.h>
using namespace std;

// 1.set 的定义 set<数据类型> 变量名

set<int> intSet;
set<string> stringSet;

int main()
{
    string s1="测试1";
    string s2="测试2";
    string s3="测试3";

    //2. 插入操作
    stringSet.insert(s3);
    stringSet.insert(s1);

    //5. 返回集合元素数量
    printf("前2次插入操作完成后的元素数量为%d\n",stringSet.size());
    stringSet.insert(s2);
    printf("前3次插入操作完成后的元素数量为%d\n",stringSet.size());

    //6.遍历整个集合，借助迭代器实现
    //定义方式   容器类型< type> ::iterator name
    set<string> ::iterator  setStringIterator;
    for(setStringIterator=stringSet.begin();setStringIterator!=stringSet.end();setStringIterator++)
        cout<<*setStringIterator<<" ";
    puts("");

    //3. 删除操作
    stringSet.erase(s3);
    printf("删除操作完成后的元素数量为%d\n",stringSet.size());

    for(setStringIterator=stringSet.begin();setStringIterator!=stringSet.end();setStringIterator++)
        cout<<*setStringIterator<<" ";
    puts("");

    //4. 判断是否由此元素
    if(stringSet.count(s2)!=0) cout<<"存在元素"<<s2<<endl;
}

运行结果

前两次插入操作完成后的元素数量为2
前两次插入操作完成后的元素数量为3
测试1 测试2 测试3
删除操作完成后的元素数量为2
测试1 测试2
存在元素测试2

Process finished with exit code 0

自定义排序准则：

要使用自定义排序准则，你可以定义一个比较函数或者更常见的是定义一个比较类（比较函数对象），然后将其作为第二个模板参数传递给set。

使用比较类（函数对象）

定义一个比较类通常更灵活，因为它可以持有状态（虽然在大多数排序场景中不需要）。

#include <iostream>
#include <set>

// 比较类
struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 降序排序
    }
};

int main() {
    std::set<int, Compare> s;

    s.insert(3);
    s.insert(1);
    s.insert(4);
    s.insert(2);

    for (int x : s) {
        std::cout << x << " ";
    }

    return 0;
}

在这个例子中，set使用提供的比较准则来排序其元素。在第二个例子中，我们定义了一个比较类，并将其作为set的模板参数。