C++与STL入门

从C到C++:happy:

头文件

stdio.h变成了cstdio

string.h变成了cstring

math.h变成了cmath

ctype.h变成了cctype

总结就是在前面添加一个c，去掉.h

说明：

ctype.h或cctype中的函数。实际上没什么用，我们都能用条件判断语句来实现。

C++框架

#include <iostream>
#include <algorithm>
//algorithm头文件提供了一些常用的算法
using namespace std;    //将std里的名字导入默认空间
const int maxn = 10;    //C语言不允许用const变量（或者说变量）来定义数组长度，C++则可以用静态变量了。
int A[maxn];    //c++里定义数组长度时可以放const的常量。而不一定需要define了。
int main(){
    int a,b;
    while(cin >> a >> b){
        cout << min(a,b) << "\n";
    }
    return 0;
}

说明：

1. iosteam 提供了输入输出流。

2. algorithm，中文是“算法”，提供了常用算法，例如代码中的min。常用函数如下：

   1. sort
   2. swap
   3. max
   4. min

3. 如果不引入std命名空间，程序就会变成这样

   1. ```cpp

      include

      include

int main(){ int a,b; while(std::cin >> a >> b){ std::cout << std::min(a,b) << “\n”; } return 0; }

4. 
C语言不允许用const变量（或者说变量）来定义数组长度，C++则可以用静态变量了。
5. 
cin>>a是从标注输入中读取a，返回值是一个读取了a的新流。
6. 
cin很方便，但是速度慢，不如scanf。
7. 
多个bool类型，用true和false表示真和假。
<a name="3b61c966"></a>
### 引用
```c
#include <iostream>
#include <algorithm>
using namespace std;
void swap2(int &a,int &b){
    int t;
    t = a;
    a = b;
    b = t;
} 
int main(){
    int a = 3,b = 4;
    swap2(a,b);
    cout << a << " " << b << "\n";
    return 0;
}

说明：

1. 在参数前加一个&，就表示这个参数是引用传递的。而不是普通的值传递。

2. 这样的话，在函数中修改形参的值，也会修改到实参的值。

3. algorithm中有了swap函数，功能非常强大，不仅同时支持int、double等内置类型，还支持用户自己编写的结构体类型。

字符串

此部分内容需要另外详细学习。

C++中有一个string类型，用来替代C语言中的字符数组（当然，字符数组的形式也是可以使用）。

特点：

1. 头文件string
2. string类型可以直接用“+”进行字符串连接，而不需要使用strcat函数。

例题：

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream> 
using namespace std;
int main(){
    string line;
    /*
    C 有 fgets()，gets() 函数，gcc编译器扩展定义了getline()函数。
    用于读取一行字符，包括换行符和字符串终止符。
    */
    //从输入流读取一行放进line中 
    getline(cin,line);
    cout << line;
    return 0;
}

getline的参数是 一个输入流和一个string类型的字符串，返回值是获取到的字符串长度。

注意：C++中不能使用gets来读一行字符串了！

例题2：

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream> 
using namespace std;
int main(){
    string line;
    while(getline(cin,line)){
        int sum = 0,x;
        //获取流
        stringstream ss(line);
        while(ss >> x)sum+=x;//这里把它当成scanf来理解
        cout << sum << "\n";
    }
    return 0;
}

这里有面向对象的特性。

虽然string和sstream很方便，但string很慢，sstream更慢。

结构体

此部分内容需要另外详细学习。

#include <iostream>
using namespace std;
struct Point{
    int x,y;
    //构造函数，参数默认值为0;Point()相当于Point(0,0). 
    Point(int x=0,int y=0){
        this->x = x;
        this->y = y;
    }
};
//operator为重载操作符
//为结构体定义加法 
Point operator + (const Point &A,const Point &B){
    return Point(A.x+B.x, A.y+B.y);
}
//定义这个结构体的流输出方式。 
ostream &operator << (ostream &out,const Point &p){
    out << "(" << p.x << "," << p.y << ")";
    return out;
}
int main(){
    //测试结构体
    Point one,two(1,2);
    one.x = 3;
    one = one + two;
    cout << one << "\n";
    return 0;
}

模板

前面加个template <typename T>

之后函数内的类型都用T来替换

这样做使得函数支持不同的类型。

例子：

普通swap

void swap(int &a, int &b) {
    int temp = a;
    a =  b;
    b = temp;
}

模板swap

template<typename  T>
void swap(T &t1, T &t2) {
    T temp;
    temp = t1;
    t1 = t2;
    t2 = temp;
}

书上例题

#include <iostream>
using namespace std;
template <typename T>
struct Point{
    T x,y;
    //初始化列表方法 
    Point(T x=0,T y=0):x(x),y(y){
    }
};
template <typename T>
Point<T> operator + (const Point<T> &A,const Point<T> &B){
    return Point<T>(A.x+B.x, A.y+B.y);
}
template <typename T>
ostream &operator << (ostream &out,const Point<T> &p){
    out << "(" << p.x << "," << p.y << ")";
    return out;
}
int main(){
    //测试结构体
    Point<int> a(1,2),b(3,4);
    Point<double> c(1.1,2.2),d(3.3,4.4);
    cout << a+b << " " << c+d << "\n";
    return 0;
}

在实际的算法竞赛中，选手很少亲自编写模板。但是模板能更好地理解STL。

C++11说明

在dev-c中使用c11的方法。

第一步：点击工具-编译选项

第二步：打钩并输入命令：-std=c++11

然后就可以愉快地使用了！

STL初步

排序和检索

排序

1.sort函数包含在头文件为#include<algorithm> 的c++标准库中，调用标准库里的排序方法可以实现对数据的排序，但是sort函数是如何实现的，我们不用考虑！

2.sort函数的模板有三个参数：

void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

（1）第一个参数first：是要排序的数组的起始地址。

（2）第二个参数last：是结束的地址（最后一个数据的后一个数据的地址）

（3）第三个参数comp是排序的方法：可以是从升序也可是降序。如果第三个参数不写，则默认的排序方法是从小到大排序。

注意：comp 可以是 C++ STL 标准库提供的排序规则（比如 std::greater），也可以是自定义的排序规则。

升序排序

#include <cstdio>
#include <algorithm>//sort函数在其中 
using namespace std;
const int maxn = 10000;
int main(){
    int n,a[maxn];
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n);
    for(int i=0;i<n;i++)printf("%d ",a[i]);
    return 0;
}

降序排序

#include <cstdio>
#include <algorithm>//sort函数在其中
#include <functional>//greater在其中 
using namespace std;
const int maxn = 10000;
int main(){
    int n,a[maxn];
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    sort(a,a+n,greater<int>());
    for(int i=0;i<n;i++)printf("%d ",a[i]);
    return 0;
}

说明：

1. 注意greater在functional里面，它重载了 () 运算符。
2. greater是一个模板类，所以要输入一个类型。
3. 第二个参数有2写法，第一种如上述代码。
4. 与greater对应的就是less，但是sort函数默认就是升序排序，所以没有使用的必要。

查找

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

书上例题

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000;
int main(){
    int n,q,kase,x;//n个数，q个问题
    int a[maxn];
    while(scanf("%d%d",&n,&q)==2){
        printf("CASE# %d:\n",++kase);
        //输入n个数 
        for(int i=0;i<n;i++)scanf("%d",&a[i]);
        sort(a,a+n);//排序
        //处理问题 
        while(q--){
            scanf("%d",&x);//输入x 
            int p = lower_bound(a,a+n,x)-a;//寻找x
            if(a[p] == x)printf("%d found at %d\n",x,p+1);
            else printf("%d not found\n",x);
        } 
    }
    return 0;
}

还有一个unique函数可以删除有序数组中的重复元素，后面的例题将展现其用法。

容器

认识容器

简单的理解容器，它就是一些模板类的集合，但和普通模板类不同的是，容器中封装的是组织数据的方法（也就是数据结构）。STL 提供有 3 类标准容器，分别是序列容器、排序容器和哈希容器，其中后两类容器有时也统称为关联容器。它们各自的含义如下表所示：

迭代器（iterator）

遍历容器，常用迭代器来实现。

迭代器和 C++ 的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素。

常用的迭代器按功能强弱分为以下五种，重点是后三种。

1. 输入迭代器
2. 输出迭代器
3. 前向迭代器
4. 双向迭代器
5. 随机访问迭代器

输入迭代器和输出迭代器比较特殊，它们不是把数组或容器当做操作对象，而是把输入流/输出流作为操作对象。

1. 前向迭代器（forward iterator）
   假设 p 是一个前向迭代器，则 p 支持 p，p，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。

2. 双向迭代器（bidirectional iterator）
   双向迭代器具有正向迭代器的全部功能，除此之外，假设 p 是一个双向迭代器，则还可以进行 —p 或者 p— 操作（即一次向后移动一个位置）。

3. 随机访问迭代器（random access iterator）
   随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

• p+=i：使得 p 往后移动 i 个元素。
• p-=i：使得 p 往前移动 i 个元素。
• p+i：返回 p 后面第 i 个元素的迭代器。
• p-i：返回 p 前面第 i 个元素的迭代器。
• p[i]：返回 p 后面第 i 个元素的引用。

以下是不同容器指定的迭代器类型

注意，容器适配器 stack 和 queue 没有迭代器，它们包含有一些成员函数，可以用来对元素进行访问。

注意栈和队列没有迭代器，他们使用一些成员函数，实现遍历。

迭代器的四种定义方式：

代码示例：

//遍历 vector 容器。
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
    vector<int> v{1,2,3,4,5,6,7,8,9,10}; //v被初始化成有10个元素
    cout << "第一种遍历方法：" << endl;
    //size返回元素个数
    for (int i = 0; i < v.size(); ++i)
        cout << v[i] <<" "; //像普通数组一样使用vector容器
    //创建一个正向迭代器，当然，vector也支持其他 3 种定义迭代器的方式
       cout << endl << "第二种遍历方法：" << endl;
       vector<int>::iterator i;
    //用 != 比较两个迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << " ";
       cout << endl << "第三种遍历方法：" << endl;
    for (i = v.begin(); i < v.end(); ++i) //用 < 比较两个迭代器
        cout << *i << " ";
       cout << endl << "第四种遍历方法：" << endl;
    i = v.begin();
    while (i < v.end()) { //间隔一个输出
        cout << *i << " ";
        i += 2; // 随机访问迭代器支持 "+= 整数"  的操作
    }
}

不定长数组：vector

简单说明

vector 容器是 STL 中最常用的容器之一，vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

vector 容器以类模板 vector（ T 表示存储元素的类型）的形式定义在 头文件中

创建方式

下列代码语句展示了创建的操作。（以下代码默认引入了std命名空间）

vector<double> values;    //创建
vector<double> values(20);    //创建并指定元素个数
values.reserve(20);    //改变容量
vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};    //初始化的同时设置默认值
vector<double> values(20, 1.0);    //创建、指定元素个数、指定默认值，20个都为1.0。不指定默认值，默认值为0
std::vector<char>value1(5, 'c');
std::vector<char>value2(value1);    //也可以通过复制另外一个vector的方式创建
//复制另一个数组或vector的部分，数组直接放收尾地址，vector通过begin或end函数放地址
int array[]={1,2,3};    
std::vector<int>values(array, array+2);//values 将保存{1,2}
std::vector<int>value1{1,2,3,4,5};
std::vector<int>value2(begin(value1),begin(value1)+3);//value2保存{1,2,3}

如果指定了大小，就可以直接用a[i]来访问，否则必须push_back了数据之后才能访问。

成员函数

如果忘记了某个函数，也不要惊慌，打开api手册，搜索Vectors，就能找到所有的成员函数了。

用法代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    //初始化一个空vector容量
    vector<char>value;
    //向value容器中的尾部依次添加 S、T、L 字符
    value.push_back('S');
    value.push_back('T');
    value.push_back('L');
    //调用 size() 成员函数容器中的元素个数
    printf("元素个数为：%d\n", value.size());
    //使用迭代器遍历容器
    for (auto i = value.begin(); i < value.end(); i++) {
        cout << *i << " ";
    }
    cout << endl;
    //向容器开头插入字符
    value.insert(value.begin(), 'C');
    cout << "首个元素为：" << value.at(0) << endl;
    return 0;
}

输出结果为：

元素个数为：3
S T L
首个元素为：C

书上例题：放木块

输入n，得到编号为0n-1的位置。现对这些木块进行操作，操作分为四种。

1、move a onto b：把木块a、b上方的木块放回各自的原位，再把a放到b上；

2、move a over b：把a上方的木块放回各自的原位，再把a放到b所在的木块的堆的上面；

3、pile a onto b：把b上方的木块放回各自的原位，再把a连同a上的木块整体移到b上；

4、pile a over b：把a连同a上方木块移到b所在的木块的堆的上面。

当输入quit时，结束操作并输出0~n-1的位置上的木块情况

代码

#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
const int maxn = 30;
int n;
vector<int> pile[maxn];//每个pile是一个vector 
//找木块a所在的pile和height，以引用的形式返回 
void find_block(int a,int &p,int &h){
    for(p=0;p<n;p++){
        for(h=0;h<pile[p].size();h++){
            if(pile[p][h]==a)return;
        }
    }
}
//把第p堆高度为h的木块上方的所有木块移回原位 
void clear_above(int p,int h){
    for(int i=h+1;i<pile[p].size();i++){
        int b = pile[p][i];
        pile[b].push_back(b);//把木块放回原位
        //pile[p].pop_back();//p堆删除该元素。 
    }
    pile[p].resize(h+1);//pile只应保留下标0~h的元素
    //因为高度从0开始，所以要保留h+1的长度。 
}
//把第p堆高度为h及其上方的木块整体移动到p2堆的顶部 
void pile_onto(int p,int h,int p2){
    for(int i=h;i<pile[p].size();i++){
        pile[p2].push_back(pile[p][i]);
        //pile[p].pop_back();//p堆删除该元素。
    }
    pile[p].resize(h);//p堆保留h个. 
}
void print(){
    for(int i=0;i<n;i++){
        printf("%d:",i);
        for(int j=0;j<pile[i].size();j++)printf(" %d",pile[i][j]);
        printf("\n");
    }
}
int main(){
    int a,b;
    //n个木块 
    cin >> n;
    string s1,s2;
    for(int i=0;i<n;i++){
        pile[i].push_back(i);//每堆木块放一个木块 
    }
    //输入指令，例如move 9 onto 1 
    while(1){
        cin >> s1;
        if(s1=="quit")break;
        cin >> a >> s2 >> b;
        int pa,pb,ha,hb;
        find_block(a,pa,ha);//找到木块a所在堆pa和木块a的高度ha 
        find_block(b,pb,hb);//找到木块b所在堆pb和木块b的高度hb
        if(pa == pb)continue;//自己对自己操作，不能做到，跳到下个指令。 
        if(s2 == "onto")clear_above(pb,hb);//如果s2指令是onto，将b上方的木块归位
        if(s2 == "move")clear_above(pa,ha);//如果s1指令是move，将a上方的木块归位
        pile_onto(pa,ha,pb);//将a上方的木块移到b的上面。     
    }
    print();
    return 0;
}

键值对：pair

简单说明

1. 头文件是，但一般不需要添加，因为iostream里面包含了。
2. pair就想只包含两个成员变量的结构体变量。而且这两个变量类型是泛型的。
3. pair的第一个元素是first，第二个元素是second，做算法时，为了方便，会通过define给他重新命名，例如x和y。
4. 使用sort对pair进行排序，默认首先关注first，按照升序排序，其次再关注second。

使用方式

#include <iostream>
#include <utility>      // pair
#include <string>       // string
using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    pair <string, double> pair1;
    // 调用第 2 种构造函数
    pair <string, string> pair2("STL教程","http://c.biancheng.net/stl/");  
    // 调用拷贝构造函数
    pair <string, string> pair3(pair2);
    //调用移动构造函数
    pair <string, string> pair4(make_pair("C++教程", "http://c.biancheng.net/cplus/"));
    // 调用第 5 种构造函数
    pair <string, string> pair5(string("Python教程"), string("http://c.biancheng.net/python/"));  
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: "<< pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl;
    cout << "pair5: " << pair5.first << " " << pair5.second << endl;
    return 0;
}

程序输出结果为：

pair1: 0
pair2: STL教程 http://c.biancheng.net/stl/
pair3: STL教程 http://c.biancheng.net/stl/
pair4: C++教程 http://c.biancheng.net/cplus/
pair5: Python教程 http://c.biancheng.net/python/

算法实战：全球变暖

https://www.acwing.com/problem/content/1235/

代码：

/*
思路：
1. 扫描初始有几个岛屿，并判断该岛屿是否可淹没
2. 淹没前岛数- 淹没后岛数 = res
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
const int N = 1002;
typedef pair<int, int> PII;
int n;
char a[N][N];   //初始地图
bool st[N][N];  //判重数组
const int dir[4][2] = {
        {-1,0},{0,1},{1,0},{0,-1},
};
bool check(int x,int y){   //判断是否是可淹没陆地
    for (int i = 0; i < 4; i++) {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];
        if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
        if(a[tx][ty] == '.') return true;   //周围发现海了，可淹没
    }
    return false;   //周围没发现海，不可淹没
}
//每进一次bfs都是一个新岛屿，返回之后是否会被淹没
bool bfs(PII start) {
    bool merge = true;
    queue<PII> que;
    st[start.x][start.y] = true;
    que.push(start);
    while (!que.empty()) {
        PII cur = que.front();
        que.pop();
        //如果发现了一块不可淹没的陆地，那么它就是不可淹没岛屿
        if(!check(cur.x,cur.y)) {
            merge = false;
        }
        for (int i = 0; i < 4; i++) {
            int tx = cur.x + dir[i][0];
            int ty = cur.y + dir[i][1];
            if (tx < 0 || ty < 0 || tx >= n || ty >= n) continue;
            if (a[tx][ty] == '.') continue;
            if (st[tx][ty]) continue;
            st[tx][ty] = true;
            que.push({ tx,ty });
        }
    }
    return merge;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%s", a[i]);
    int qnum = 0, hnum = 0;   //淹没前的岛屿数量，淹没后岛屿数量
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (a[i][j] == '#' && st[i][j]==false) {
                //找到一个新岛屿
                qnum ++;
                //如果不会被淹没，那么hnum+1
                if(!bfs({ i, j })) hnum ++;
            }
        }
    }
    cout << qnum - hnum << endl;
    return 0;
}

集合：set

简单说明

1. 每个元素必须各不相同，相同的会自动合并。
2. 自动排序（升序排序）

成员函数

使用方法

#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
    //创建空set容器
    std::set<std::string> myset;
    //空set容器不存储任何元素
    cout << "1、myset size = " << myset.size() << endl;
    //向myset容器中插入新元素
    myset.insert("http://c.biancheng.net/java/");
    myset.insert("http://c.biancheng.net/stl/");
    myset.insert("http://c.biancheng.net/python/");
    cout << "2、myset size = " << myset.size() << endl;
    //利用双向迭代器，遍历myset
    for (auto iter = myset.begin(); iter != myset.end(); ++iter) {
        cout << *iter << endl;
    }
    return 0;
}

程序执行结果为：

1、myset size = 0
2、myset size = 3
http://c.biancheng.net/java/
http://c.biancheng.net/python/
http://c.biancheng.net/stl/

书上例题：安迪的词典

安迪的第一个字典

输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出。单词不区分大小写。

代码

#include <cstdio>
#include <iostream>
#include <set>
#include <string>
#include <sstream>
using namespace std;

set<string> dict;//string集合

int main(){
    string s,buf;
    //到空格就断 
    while(cin >> s){
        for(int i=0;i<s.length();i++){
            if(s[i]>='A'&&s[i]<='Z')s[i] = s[i]-'A'+'a';
            else if(s[i]>='a'&&s[i]<='z');
            else s[i] = ' ';
        }
        stringstream ss(s);
        while(ss >> buf)dict.insert(buf);
    }
    for(set<string>::iterator it = dict.begin(); it!= dict.end(); it++){
        cout << *it << "\n";
    }
    return 0;
}

算法实战：日期问题

https://www.acwing.com/problem/content/1231/

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

const int table[13] = {
    0,31,28,31,30,31,30,31,31,30,31,30,31,
};

set<int> st;

bool check(int year,int mon,int day){
    if(year < 1960 || year > 2059) return false;//特判 

    if(mon < 1 || mon > 12) return false;
    int leap = 0;
    if(mon == 2){
        if(year%4==0&&year%100!=0 || year%400==0) leap++;
    }
    if(day < 1 || day > table[mon] + leap) return false;

    return true;
}

int main() {
    int n1,n2,n3;
    scanf("%d/%d/%d",&n1,&n2,&n3);
    int cnt = 0;
    //年月日
    int year = n1, mon = n2, day = n3;
    if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
    if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);
    //月日年
    mon = n1, day = n2, year = n3;
    if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
    if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);
    //日月年
    day = n1, mon = n2, year = n3;
    if(check(1900+year,mon,day)) st.insert((1900+year)*10000 + mon*100 + day);
    if(check(2000+year,mon,day)) st.insert((2000+year)*10000 + mon*100 + day);

    for(set<int>::iterator it = st.begin(); it != st.end(); it++) {
        int num = *it;
        printf("%d-%02d-%02d\n",num/10000,num/100%100,num%100);
    }

    return 0;
}

映射：map

简单说明

map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。

成员函数

使用方法

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

int main() {
    //创建空 map 容器，默认根据个键值对中键的值，对键值对做降序排序
    std::map<std::string, std::string, std::greater<std::string>>myMap;
    //调用 emplace() 方法，直接向 myMap 容器中指定位置构造新键值对
    myMap.emplace("C语言教程","http://c.biancheng.net/c/");
    myMap.emplace("Python教程", "http://c.biancheng.net/python/");
    myMap.emplace("STL教程", "http://c.biancheng.net/stl/");
    //输出当前 myMap 容器存储键值对的个数
    cout << "myMap size==" << myMap.size() << endl;
    //判断当前 myMap 容器是否为空
    if (!myMap.empty()) {
        //借助 myMap 容器迭代器，将该容器的键值对逐个输出
        for (auto i = myMap.begin(); i != myMap.end(); ++i) {
            cout << i->first << " " << i->second << endl;
        }
    }  
    return 0;
}

程序执行结果为：

myMap size==3
STL教程 http://c.biancheng.net/stl/
Python教程 http://c.biancheng.net/python/
C语言教程 http://c.biancheng.net/c/

遍历map

for(map<string,int>::iterator it = cnt.begin(); it!=cnt.end() ; it++){
        cout << it->first << ":" << it->second << "\n";
    }

输入一些单词，找出所有满足如下条件的单词：该单词不能通过字母重排，得到输入文 本中的另外一个单词。在判断是否满足条件时，字母不分大小写，但在输出时应保留输入中 的大小写，按字典序进行排列（所有大写字母在所有小写字母的前面）。

代码

/*
ladder came tape soon leader acme RIDE lone Dreis peat
ScAlE orb eye Rides dealer NotE derail LaCeS drIed
noel dire Disk mace Rob dries
#
*/

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

//key为string存单词,value 为int存次数 
map<string,int> cnt;
vector<string> words;

//标准化：将字符串全部化为小写，再按ascii排序 
string repr(const string &s){
    string ans = s;
    for(int i=0;i<ans.length();i++){
        if(ans[i]>='A' && ans[i]<='Z')
            ans[i] = ans[i]-'A'+'a';
    }
    sort(ans.begin(),ans.end());
    return ans;
}

int main(){
    int n = 0;
    string s;
    while(cin >> s){
        if(s[0] == '#')break;
        //将单词添加进单词vector 
        words.push_back(s);
        string r = repr(s);//标准化该单词 
        //inc该标准化单词的次数 
        if(!cnt.count(r))cnt[r] = 0;
        cnt[r]++;
    }
    vector<string> ans;
    for(int i=0;i<words.size();i++){
        //如果该单词的标准化单词的个数为1
        //说明不能通过单词重排，得到另一个单词
        if(cnt[repr(words[i])] == 1){
            //在结果vector中添加 
            ans.push_back(words[i]);
        }    
    }
    //对结果vector排序 
    sort(ans.begin(),ans.end());
    //输出
    for(int i=0;i<ans.size();i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

算法实战：十六进制转八进制

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述
　　给定n个十六进制正整数，输出它们对应的八进制数。

输入格式
　　输入的第一行为一个正整数n （1<=n<=10）。
　　接下来n行，每行一个由0F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。

输出格式
　　输出n行，每行为输入对应的八进制正整数。

【注意】
　　输入的十六进制数不会有前导0，比如012A。
　　输出的八进制数也不能有前导0。

样例输入
　　2
　　39
　　123ABC

样例输出
　　71
　　4435274

【提示】
　　先将十六进制数转换成某进制数，再由某进制数转换成八进制。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;

const int maxn = 100010;
string hs,bs,os;//存十六进制、二进制、八进制 

map<char,string> table;//16到2的映射 
map<string,char> table2;//2到8的映射 

//初始化映射关系 
void init() {
    table['0'] = "0000";
    table['1'] = "0001";
    table['2'] = "0010";
    table['3'] = "0011";
    table['4'] = "0100";
    table['5'] = "0101";
    table['6'] = "0110";
    table['7'] = "0111";
    table['8'] = "1000";
    table['9'] = "1001";
    table['A'] = "1010";
    table['B'] = "1011";
    table['C'] = "1100";
    table['D'] = "1101";
    table['E'] = "1110";
    table['F'] = "1111";

    table2["000"] = '0';
    table2["001"] = '1';
    table2["010"] = '2';
    table2["011"] = '3';
    table2["100"] = '4';
    table2["101"] = '5';
    table2["110"] = '6';
    table2["111"] = '7';
}

//删除开头多余的0
void deleteZero(string& str) {
    while(str[0] == '0') {
        str.erase(0,1);
    }
}

void BinToOct() {
    //当二进制串不是3的倍数，给它补足
    while (bs.size() % 3 != 0) {
        bs = "0" + bs;
    }
    //初始化os
    os = ""; 
    //每3个二进制位对应一个八进制串 
    for (int i = 0; i < bs.size(); i+=3) {
        string str = bs.substr(i, 3);
        os += table2[str];
    }
    //删除开头多余的0 
    deleteZero(os); 
}

void HexToBin() {
    //初始化bs
    bs = ""; 
    //遍历十六进制串，每个十六进制字符转换成二进制串 
    for (int i = 0; i < hs.size(); i++) {
        bs += table[hs[i]];
    }
    //删除开头多余的0 
    deleteZero(bs); 
}

int main() {
    init();
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> hs;
        HexToBin();
        BinToOct();
        cout << os << endl; 
    }
    return 0;
}

栈：stack

成员函数

使用方法

#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
    //构建 stack 容器适配器
    list<int> values{ 1, 2, 3 };
    stack<int, list<int>> my_stack(values);
    //查看 my_stack 存储元素的个数
    cout << "size of my_stack: " << my_stack.size() << endl;
    //将 my_stack 中存储的元素依次弹栈，直到其为空
    while (!my_stack.empty())
    {  
        cout << my_stack.top() << endl;
        //将栈顶元素弹栈
        my_stack.pop();
    }
    return 0;
}

书上例题：集合栈计算机

有一个专门为了集合运算而设计的“集合栈”计算机。该机器有一个初始为空的栈，并且支持以下操作：
PUSH：空集“{ }“入栈
DUP：把当前栈顶元素复制一份后再入栈
UNION：出栈两个集合，然后把二者的并集入栈。
INTERSECT：出栈两个集合，然后把二者的交集入栈。
*ADD：出栈两个集合，然后把先出栈的集合加入到后出栈的集合中，把结果入栈。
每次操作之后，输出栈顶集合的大小（即元素个数）。例如：栈顶元素是A={ { }，{{ }} }，下一个元素是B={ { }，{{{ }}} },则：
UNION操作得到：{ { }，{{ }}，{{{ }}} }，输出3.
INTERSECT操作得到：{ { } },输出1.
ADD操作得到：{{ }, {{{ }}}, {{ },{{ }}} }.，输出3

分析
本题的集合并非简单的整数或字符串集合，而是集合的集合。很难直接表示，所以为方便起见，为每个不同的集合分配一个唯一的ID
，则每个集合表示为所包含元素（集合）的ID集合。这样就可以用STL中的set<int>来表示，而整个栈则是一个stack<int>。

1. 在进行操作时，使用map将每种集合与对应ID相关联，既可完成查找ID，也可判定是否出现新集合。
2. 使用vector作为存储每种集合的cache，当map中没有相应的ID时，向vector加入一个set<int>元素，并将下标作为ID进行唯一标识。
3. 使用vector将Set存储：可以用ID查询到对应的set。这样通过map和vector实现set到ID的双射。
4. 最后 ，输出栈顶集合的大小（元素个数）。

代码

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <set>
#include <stack>
#include <map>
#include <vector>
#include <iterator>
using namespace std;

typedef set<int> Set; 
map<Set,int> id_cache;//集合对应id 
vector<Set> set_cache;//集合库，根据id取集合，id刚好是vector的下标 

int find_id(Set x){
    //如果找到了x的id，那么返回该集合的id 
    if(id_cache.count(x)) return id_cache[x];
    //否则添加进集合库，给该集合对应一个id 
    set_cache.push_back(x);//添加进新集合
    //新id为集合库的长度-1，即id为该集合从0开始的下标。 
    id_cache[x] = set_cache.size() - 1;
    return id_cache[x]; //返回该集合的id 
}

int main(){
    stack<int> s;//做一个栈，栈中存的是集合的id 
    int n;
    cin >> n;//输入指令个数
    for(int i = 0; i < n; i++){
        string op;
        cin >> op;//输入指令 
        if(op[0] == 'P')s.push(find_id(Set()));//一个空的集合入栈。 
        else if(op[0] == 'D')s.push(s.top());//取栈顶元素再入栈
        else{
            //出栈两个集合 
            Set x1 = set_cache[s.top()];s.pop();
            Set x2 = set_cache[s.top()];s.pop();
            Set x;
            //两个集合的并集放入x 
            if(op[0] == 'U')set_union(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            //两个集合的交集放入x 
            if(op[0] == 'I')set_intersection(x1.begin(),x1.end(),x2.begin(),x2.end(),inserter(x,x.begin()));
            if(op[0] == 'A'){
                x = x2;//存一下x2 
                x.insert(find_id(x1));//x添加x1 
            }
            //将x入栈
            s.push(find_id(x));
        } 
        cout << set_cache[s.top()].size() << endl;
    }
    return 0;
}

队列：queue

成员函数

说明：

1. 最重要的函数如下：

   1. 增加：push
   2. 删除：pop
   3. 查询：front
   4. 查询长度：size

注意：和 stack 一样，queue 也没有迭代器，因此访问元素的唯一方式是遍历容器，通过不断移除访问过的元素，去访问下一个元素。

使用方法

#include <iostream>
#include <queue>
#include <list>
using namespace std;
int main()
{
    //构建 queue 容器适配器
    std::deque<int> values{ 1,2,3 };
    std::queue<int> my_queue(values);//{1,2,3}
    //查看 my_queue 存储元素的个数
    cout << "size of my_queue: " << my_queue.size() << endl;
    //访问 my_queue 中的元素
    while (!my_queue.empty())
    {
        cout << my_queue.front() << endl;
        //访问过的元素出队列
        my_queue.pop();
    }
    return 0;
}

算法实战：献给阿尔吉侬的花束

https://www.acwing.com/problem/content/1103/

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N = 210;

int R,C;    //地图行数列数
char map[N][N];
int dist[N][N]; //从起点到(i,j)的长度

int bfs(PII start,PII end) {
    //定义队列
    queue<PII> que;
    //长度初始为-1，表示没有遍历到
    memset(dist,-1,sizeof dist);//每个字节全为-1，即二进位全为1 

    dist[start.x][start.y] = 0;
    //start入列
    que.push(start);

    while(que.size()){
        //取头 
        PII t = que.front(); 
        que.pop();

        //遍历四个方向,上右下左 
        const int dir[4][2] = {
            {-1,0},{0,1},{1,0},{0,-1},
        };
        for(int i = 0; i < 4; i++) {
            int tx = t.x + dir[i][0];
            int ty = t.y + dir[i][1];
            if(tx < 0 || ty < 0 || tx >= R || ty >= C) continue;    //超地图边界，跳出 
            if(map[tx][ty] == '#') continue;    //墙跳出
            if(dist[tx][ty] != -1) continue;    //有长度了，说明遍历过了，跳出

            //计算长度，如果找到目标，直接返回长度 
            dist[tx][ty] = dist[t.x][t.y] + 1;
            if(end.x == tx && end.y == ty) return dist[tx][ty];

            //添加队列
            que.push({tx,ty});
        }
    }
    //如果没找到，返回-1 
    return -1;
}

int main() {
    int T;  //T组数据 
    cin >> T;

    while(T--) { 
        scanf("%d%d",&R,&C);
        for(int i = 0; i < R; i++) scanf("%s",map[i]);
        //开始找起点和终点
        PII start,end;
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(map[i][j] == 'S') start = {i,j};
                else if(map[i][j] == 'E') end = {i,j};
            }
        }
        //从起点宽搜终点，获得最小步数 
        int step = bfs(start,end);
        //输出最小步数
        if(step == -1) printf("oop!\n");
        else printf("%d\n",step);
    }

    return 0;
}