C 转 C++ 刷题教程 | 栖迟於一丘

本文章与其说是 C++ 的 STL 容器使用，其实是在准备算法刷题时总结的一些 API 调用，后来更多的是用 Java，虽说算法不应该和语言挂钩，但不得不承认在刷力扣或是 PAT 算法考试时 C++ 才是我真正的心头好

实际竞赛或是 PAT 考试时经常会同时用到 C 的简单高效和 C++ 的丰富类库，在总结是也着重记录了 C => C++ 的语法变化和不同应用场景下的选择

语法变化

输出方法

C++ 中提供 cin(>>) 和 cout(<<) 进行弱类型的输入和输出，cin 和 cout 虽然使用起来方便，但是输入输出的效率不如 scanf 和 printf

头文件

C++ 的头文件一般是没有像 C 语言的 .h 后缀，但 C++ 向下包含 C，一般 C 语言中的头文件去掉 .h 在前面加上 c 就可以继续使用

#include <cmath>// 相当于 #include <math.h>
#include <cstdio>// 相当于 #include <stdio.h>
#include <cstring>// 相当于 #include <string.h>

bool 类型

C++ 无需添加头文件就自带布尔类型的变量，在 bool 中 0 为 false，非零为 true

1
2
3

bool flag=true;
bool flag=-357;// 为 true
bool flag=0;// 为 false

C++ 无需用 #define 定义常量，统一用 const 数据类型常量名称 的方式进行定义

string 类

C++ 中自带 string 字符串类，部分情况仍需使用 char[] 数组方法，包含定义、输出、拼接和一定的处理
尽量使用头文件，≠


string str1 = "Hello World";// 定义字符串
string str2;
cin >> str2;// 输入字符串
string str3 = str2 + str1;// 字符串拼接
cout << str3 << endl;// 输出
for (int i = 0; i < str1.length(); i++)
{ // 使用字符数组的方式进行输出
    cout << str1[i];
}
cout << endl;

string 输入输出

由于 string 是 C++ 中产生的，所以 C 语言中的 scanf 和 printf 函数无法对其进行输入输出的处理
可以使用 printf("%s",str.c_str());的方式进行输出，c_str()函数返回的是一个 C 语言中的 char 指针，表示将字符串转换为一个只读的字符数组
cin 的输入处理是以空格结束一个字符串的，如果要进行整行字符串的输入（回车结束）需要使用 getline 方法

对于字符串长度的获取，也可以直接采用 str.length();或者 str.size()的方式
由于有些函数只支持迭代器为参数，所以 string 也可以以迭代器的方式进行访问（可加减）

string str4;
getline(cin, str4);//getline 的参数中需要加上 cin 表示输入
cout << str4 << endl;
cout << str4.length() << endl; 
cout << str4.size() << endl;

string 函数

string 可以直接进行赋值或加减拼接

可以直接用比较运算符判断相等或大于小于（以字典序为规则）


string str1 = "Hello World"; // 定义字符串
string str2 = "12345"; 
str1 += str2; // 相加进行拼接
cout << str1 << endl; 
cout << (str1 > str2) << endl; // 输出 str1 是否小于 str2

输出长度常用 length()而不是 size()
insert()插入函数常用两种方式
- 直接位置插入： insert(位置下标，要插入的字符串)
- 迭代器参数插入，常用于将一个字符串的一部分插入到另一字符串： insert(插入位置，被插入字符串的起点，终点)

substr() 字符串截取函数

1
2
3

string str1 = "Hello World";       // 定义字符串
cout << str1.substr(4) << endl;    // 从下标 4 开始到结束
cout << str1.substr(4, 6) << endl; // 从下标 4 开始，截取 6 个字符

删除字符的函数 erase()
erase()接收的也是迭代器作为参数，单个元素或者一个区间


string str;
cin >> str;
while (str.find('a') != string::npos) //find()返回的是字符的下标
{
    str.erase(str.find('a'), 1); // 第二个参数的 1 代表删除元素的个数
}
cout << str << endl;
str.erase(str.begin()); // 删除第一个字符
cout << str << endl;
str.erase(str.begin(), str.begin() + 2); // 删除一个范围，左闭右开
cout << str << endl;
str.clear(); // 清空字符串

find()查找字符或字串，查找失败返回 string::npos

string str = "qwertasd";
string str2 = "asd";
cout << str.find('a') << endl;
// 查找单个字符返回的这个字符的下标，可用其返回值!=string::npos 的方式表示查找成功
cout << str.find(str2) << endl;    // 返回匹配成功的起始下标
cout << str.find(str2, 4) << endl; // 表示从下标 4 开始向后查找，返回值与上一样

replace()函数替换字串： replace(替换起始位置，替换长度，替换的字串)
也支持迭代器参数替换： replace(迭代器位置起，始，字串)


string str = "qwertasd";
string str2 = "asd";
cout << str.replace(3, 3, str2) << endl; // 从下标 3 开始往后的三个字符被 str2 替代
cout << str.replace(str.begin(), str.begin() + 4, str2) << endl;

struct 的使用

在 C++ 中，结构体生成对象时无需进行结构体的声明，也就是不用在前面加是 struct
结构体的定义尽量在 main() 方法之外

struct stu
{
    int grade;
    float score;
};
struct stu arr1[10]; // C 语言里面需要写 struct
stu arr2[10];        // C++ 里面不用写

& 在 C++ 中的引用

C++ 中的 & 符号在函数的参数列表中作引用，要与 C 语言的取地址输入分开，这两者并不相同
做引用时的意思是将传送进来的变量参数直接进行操作（可以理解成拷贝副本），只是将名字换成了定义方法中的局部变量名

void function(int &a); 
int main()
{

    int n = 0;
    function(n); // n 由 0 变成了 99
    cout << n << endl;
    system("pause");
    return 0;

}
void function(int &a)// 传⼊的是 n 的引⽤，相当于直接对 n 进⾏了操作，只不过在 function 函数中换了个名字叫 a
{ 

    a = 99;

}

void function(int a);
int main()
{
    int n = 0;
    function(n); // 并没有对 n 这个值进行改变，还是 0
    cout << n << endl;
    system("pause");
    return 0;
}
void function(int a) // 传⼊的是 0 这个值，并不会改变 main 函数中 n 的值
{
    a = 99;
}

STL 的应用

STL 称为标准模板库（Standard Template Library），STL 已完全被内置到支持 C++ 的编译器中，无需额外安装

vector 动态数组

动态数组 vector，能够在运行阶段设置数组的长度、在末尾增加新的数据、在中间插入新的值、长度任意被改变

定义 vector，vector 是包含在头文件 [vector] 中的，预定义头文件之后的生成格式为： vector< 数据类型 > 数组名;
vector 的大小如果在初始不进行定义的话默认为 0，可以采用vector< 数据类型 > 数组名(``size``); 的方式来进行初始大小的定义，也可以采用 resize 方法进行大小的重定义
对定义了长度的数组，那么它的初始值将全部定义为 0
也可以采用 vector< 数据类型 > 数组名(size, 初始值); 在初始化的是否就赋予初始值
对 vector 动态数组的访问和普通数组的访问方式一样，也是通过下标的方式，但可以通过迭代器进行遍历


vector<int> num;
cout << num.size() << endl; // 刚创建的数组为空，size==0
vector<int> number(10);     // 将 number 数组的大小定义为 10
cout << number.size() << endl;
num.resize(5); // 将 num 的长度重定义为 5
cout << num.size() << endl;
for (int i = 0; i < num.size(); i++)
{
    cout << num[i] << " "; // 此时初始值为 0
}
cout << endl;
vector<int> numbers(10, 5);// 初始化数组长度为 10，所有元素的初始值为 5
for (int i = 0; i < numbers.size(); i++)
{
    cout << numbers[i] << " "; // 此时初始值为 5
}
num.clear();// 清空数组元素，复杂度为 O(N)（N 为元素的个数） 
for (int i : numbers)// 读取型遍历
{
  cout << i << endl;
}

push_back() 和 pop_back() 函数实现在数组尾插入或删除元素

1
2
3

vector<int> num = {10, 20, 30};
num.push_back(40); // 在数组末尾插入 40
num.pop_back();    // 移除最后一个元素

迭代器访问，完整的指针类型定义应该是 vector<int>::iterator ，但在 C++１１中出现了 auto 型，会自动进行检测变量的类型
美国人的思想为 左闭右开 ，也就是 end() 函数不进行存储任何东西，表示一个数组到这就为空了（尾元素的下一个元素的地址）


vector<int> num = {10, 20, 30, 40, 50};
for (auto it = num.begin(); it != num.end(); it++)//num.begin()是一个指针，代表指向第一个元素
{                       //auto 相当于生成一个 vector 类型的迭代器，it 是 iterator 的缩写
    cout << *it << " "; //it 是一个指针，加 * 进行取值
}

只有 vector 和 string 中才允许有 ve.begin()+3这种迭代器加整数的操作

在指定位置插入新的元素，可以使用自带的 insert()和 emplace()函数

insert() 函数的功能是在 vector 容器的指定位置插入一个或多个元素。该函数的语法格式有多种

语法格式	用法说明
insert(pos,elem)	在迭代器 pos 指定的位置之前插入一个新元素 elem，并返回表示新插入元素位置的迭代器
insert(pos,n,elem)	在迭代器 pos 指定的位置之前插入 n 个元素 elem，并返回表示第一个新插入元素位置的迭代器
insert(pos,first,last)	在迭代器 pos 指定的位置之前，插入其他容器（不仅限于 vector）中位于 [first,last) 区域的所有元素，并返回表示第一个新插入元素位置的迭代器
insert(pos,initlist)	在迭代器 pos 指定的位置之前，插入初始化列表（用大括号 {} 括起来的多个元素，中间有逗号隔开）中所有的元素，并返回表示第一个新插入元素位置的迭代器

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

int main()
{
    vector<int> demo{1, 2};
    // 第一种格式用法
    demo.insert(demo.begin() + 1, 3); //{1,3,2}
    // 第二种格式用法
    demo.insert(demo.end(), 2, 5); //{1,3,2,5,5}
    // 第三种格式用法
    array<int, 3> test{7, 8, 9};
    demo.insert(demo.end(), test.begin(), test.end()); //{1,3,2,5,5,7,8,9}
    // 第四种格式用法
    demo.insert(demo.end(), {10, 11}); //{1,3,2,5,5,7,8,9,10,11}
    for (int i = 0; i < demo.size(); i++)
    {
        cout << demo[i] << " ";
    }
    system("pause");
    return 0;
}

emplace()用于在 vector 容器指定位置之前插入一个新的元素，其格式为 iterator emplace (const_iterator pos, args...); emplace()函数的效率更高一些

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

int main()
{

    vector<int> demo1{1, 2};
    //emplace() 每次只能插入一个 int 类型元素
    demo1.emplace(demo1.begin(), 3);
    for (int i = 0; i < demo1.size(); i++)
    {
        cout << demo1[i] << " ";
    }
    system("pause");
    return 0;

}

erase()删除函数用来删除数组中的特定元素，但其接收的参数为一个迭代器，可以先用下的 find()函数查找出位置

vector<int> num = {3, 4, 5, 6, 7};
auto it = find(num.begin(), num.end(), 6); // 查找相应元素的迭代器
num.erase(it);                             // 删除这个元素
num.erase(num.begin());
for (auto it = num.begin(); it != num.end(); it++)
{
    cout << *it << " ";
}

set 集合

集合中的元素各不相同，而且元素之间会进行从小到大的排序

set 是包含在头文件中的，预定义头文件之后的生成格式为： set< 数据类型 > 集合名;
set 集合中的元素是有序的，所以不用管插入的位置，插入方式为： set.insert(元素);
集合的输出：使用迭代器的方式进行集合的遍历输出，但集合是默认从小到大排序的，所以可以使用 set.rbegin()/set.rend()反向迭代器实现反向遍历
可以通过 *(num.begin()) 这种指针取值的方式来对第一个元素（最小元素）进行输出；同理 *(num.rbegin()) 对最后一个元素（最大元素）进行输出
对集合中元素的查找可以使用 set.find(目标元素)，但此方法是一个迭代器，我们可以用 set.find(目标元素) != set.end()的方式，通过返回值 1 或 0 判断集合中有无这个元素


set<int> num;               // 定义 set 集合
num.insert(1);              // 向集合中插入元素 1
cout << num.size() << endl; // 输出集合的大小
for (int i = 3; i < 10; i++)
{
    num.insert(i);
}
num.erase(5);// 擦除元素 5
cout << "min:" << *(num.begin()) << endl; // 输出集合中第一个元素的元素
cout << "max:" << *(num.rbegin()) << endl; // 输出集合中最后一个元素的元素
for (auto it = num.begin(); it != num.end(); it++)
{ // 遍历集合
    cout << *it << " ";
}
cout << endl;
for (auto it = num.rbegin(); it != num.rend(); it++)
{ // 反向遍历集合
    cout << *it << " ";
}
cout << endl
     << (num.find(7) != num.end()) << endl; // 查找元素 7
cout << *(num.find(7)) << endl; 
num.clear(); // 清空集合

set 集合的 erase()函数不同于 vector 只能以迭代器作为参数，可以用迭代器，元素值和迭代器范围进行删除
但是 set 集合又不允许迭代器相加的操作

set<int> num; // 定义 set 集合
for (int i = 0; i < 10; i++)
{
    num.insert(i);
}
num.erase(5);                              // 擦除元素 5
num.erase(num.begin());                    // 擦除起始元素
num.erase(num.begin(), num.find(4));       // 擦除开始到元素 4 的位置（不包含 num.find(4)）

map 键值对

map 集合又称为映射，采用一键对一值的方式进行存储，存放的元素会通过键进行从小到大的排列
map 是包含在头文件中的，预定义头文件之后的生成格式为： map< 键数据类型, 值数据类型 > 集合名;

通过键作为下标存储值达到同时存储一对数据的目的，擦除也是一样
也有迭代器遍历和反迭代器的内部函数，但是无需对指针进行取值，只要用指针指向 frist 或 second 便可直接显示键或值的内容，如 data.begin()->frist 表示第一对元素的键的内容


map<string, int> data;
data["hello"] = 2;
data["world"] = 7;
data[";"] = 2;                 // 在 map 中插入元素
cout << data["hello"] << endl; // 通过键输出值, 不存在返回 0
cout << data.size() << endl;   //map 的大小，一对键值看作一个元素
data.erase("hello");           // 通过键擦除一对元素
for (auto it = data.begin(); it != data.end(); it++)
{ // 迭代器遍历，直接用指针取值，指向 frist 表示键，指向 seco 表示值
    cout << it->first << "  " << it->second << endl;
}

find()函数，参数为 key，查找成功返回一个迭代器
count()函数，返回被查找元素的个数（map 中的元素不重复，值只可能是 1 或 0），参数也是 key
erase()函数，删除单个元素时的参数可以是迭代器也可以是 key，删除区间元素只能是迭代器的起始位置

map<char, int> data;
data['a'] = 2;
data['b'] = 3;
data['c'] = 4;
data['d'] = 5;
auto it = data.find('a'); // 查找成功返回位置 5
cout << it->first << " " << it->second << endl;
data.erase('a');                      // 通过 key 删除元素
data.erase(data.find('b'));           // 通过迭代器删除元素
data.erase(data.begin(), data.end()); // 通过迭代器起始删除区间元素
data.clear();                         // 清空元素

unordered 集合

因为在 map 和 set 集合中的元素都是有序的，但 unordered 的意思是未经排序，也就是里面的元素是无序的，时间复杂度更小一下，用法相同

queue 队列

有头尾指针 front 和 back，先进先出，队尾入，队首移除
主要使用是在广度优先搜索时无需手动编写队列

头文件，定义格式： queue< 数据类型 > 队名;
push()和 pop()进行入队和出队操作（队尾入，队首出），无法遍历，可读取队首队尾，可访问大小


queue<int> que;
for (int i = 0; i < 10; i++)
{
    que.push(i); // 从队尾入队
}
que.pop();                                        // 移除队首元素
cout << que.front() << " " << que.back() << endl; // 输出首尾元素
cout << que.size() << endl;                       // 输出大小
cout << que.empty() << endl;                      // 判断是否为空

empty()函数判断是否为空返回 bool 型，在使用 front 和 back 进行输出时，先判断是否为空，否则容易出错

priority_queue 队列

称为优先队列，底层是用堆来实现的，具体表现为队首元素永远时优先级最高的那个（优先级可以自己规定）

优先队列没有 front 和 back 指针，统一用 top 来对队首进行操作（又称为堆顶），其他使用与 queue 无异

priority_queue<int> num;
num.push(2);
num.push(4);
num.push(3);
cout << num.top() << endl; // 输出堆顶
num.pop();
cout << num.top() << endl;

优先级的定义，可以使用自带的大小定义，其格式为： priority_queue< 类型，vector< 类型 >，less< 类型 >> num; 这是指小的放后边，也就是默认的规则，若改为大的放后边只要将 less 改为 greater 即可
其他方法看算法笔记 P235

stack 栈

先进后出，只能对栈顶进行操作，所以只有一个指针 top

头文件，定义格式： stack< 数据类型 > 栈名;
push()和 pop()进行入栈和出栈操作，无法遍历，只能读取栈顶 top，可访问大小


stack<int> s; // 定义⼀个空栈 s
for (int i = 0; i < 6; i++)
{
    s.push(i); // 将元素 i 压⼊栈 s 中
}
s.pop();                  // 移除栈顶元素
cout << s.top() << endl;  // 访问 s 的栈顶元素
cout << s.size() << endl; // 输出 s 的元素个数

pair 元素对

在头文件中，主要是将两个元素（无论类型是否相同）合成一个元素，就像定义在结构体中定义两个不同变量，但是用起来更简单，可以直接比较大小（先比较 first，如果相同再比较 second）
访问就像 map 中的 first 元素和 second 函数（但不是指向，而是类似结构体的形式）

初始化可以直接在后边加圆括号直接输入，还有三种赋值方式

pair<string, int> psi;
//pair<string, int> psi("hh", 5);// 初始化 
psi = make_pair("ha", 6); // 使用 make_pair() 函数定义
cout << psi.first << " " << psi.second << endl;
psi = pair<string, int>("hh", 5); // 指定类型定义
cout << psi.first << " " << psi.second << endl;
psi.first = "xx"; // 指定变量定义
psi.second = 7;
cout << psi.first << " " << psi.second << endl;

具体使用就是代替二元结构体和作为键值对插入 map 中


map<string, int> msi;
msi["hh"] = 6;                    // 传统定义
msi.insert(make_pair("xixi", 8)); //pair 插入
auto it = msi.find("hh");
cout << it->first << " " << it->second << endl;
it = msi.find("xixi");
cout << it->first << " " << it->second << endl;