使用C++来刷题需要掌握的知识点

发表于 2020-07-11 更新于 2023-11-05 分类于编程基础知多少阅读次数：本文字数： 6.4k 阅读时长 ≈ 6 分钟

只用C++来刷题，那些你不能不知道的知识。

头文件与命名空间

#include <iostream>：C++ 中用于输入输出的头文件（类似于C语言的<stdio.h>）
C语言的头文件在C++里全部可以使用，但是要把.h后缀去掉，在头文件前面加上c
- #include <stdlib.h> -> #include <cstdlib>
- #include <math.h> -> #include <cmath>
- #include <string.h> -> #include <cstring>
- #include <ctype.h> -> #include <cctype>
C++中，用标准库的东西前面都要加std::，除非加上using namespace std;

#include <bits/stdc++.h>可以一次性包含所有头文件，VS环境除外。

基本数据类型

类型	关键字
布尔型	bool
字符型	char
整型	int
浮点型	float
双浮点型	double
无类型	void
宽字符型	wchar_t

其实 wchar_t 是这样来的：

1	typedef short int wchar_t;

所以 wchar_t实际上的空间是和 short int 一样。

一些基本类型可以使用一个或多个类型修饰符进行修饰：

signed
unsigned
short
long

下表显示了各种变量类型在内存中存储值时需要占用的内存，以及该类型的变量所能存储的最大值和最小值。

**注意：**不同系统会有所差异，一字节为 8 位。

**注意：**long int 与 int 都是 4 个字节，因为早期的 C 编译器定义了 long int 占用 4 个字节，int 占用 2 个字节，新版的C/C++ 标准兼容了早期的这一设定。

类型	位	范围
char	1 个字节	-128 到 127 或者 0 到 255
unsigned char	1 个字节	0 到 255
signed char	1 个字节	-128 到 127
int	4 个字节	-2147483648 到 2147483647
unsigned int	4 个字节	0 到 4294967295
signed int	4 个字节	-2147483648 到 2147483647
short int	2 个字节	-32768 到 32767
unsigned short int	2 个字节	0 到 65,535
signed short int	2 个字节	-32768 到 32767
long int	8 个字节	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
signed long int	8 个字节	-9,223,372,036,854,775,808 到 9,223,372,036,854,775,807
unsigned long int	8 个字节	0 到 18,446,744,073,709,551,615
float	4 个字节	精度型占4个字节（32位）内存空间，+/- 3.4e +/- 38 (~7 个数字)
double	8 个字节	双精度型占8 个字节（64位）内存空间，+/- 1.7e +/- 308 (~15 个数字)
long double	16 个字节	长双精度型 16 个字节（128位）内存空间，可提供18-19位有效数字。
wchar_t	2 或 4 个字节	1 个宽字符

输入与输出

输入
- scanf()：源自C语言#include <stdio.h>，只能对基础数据类型作输入
- cin：C++标准输入流，#include <iostream>
输出
- printf()：源自C语言#include <stdio.h>，只能对基础数据类型作输出
- cout：C++标准输出流，#include <iostream>

整行输入

char str[100];
cin.getline(str, 100);

string str;
getline(cin, str);

cin 的速度比 scanf 慢不少（哪怕是关闭了同步），1e5 以上的数据用 cin 读入就可能会 TLE ，此时建议用 scanf；

输出小数用 printf 更方便一点， C++ 格式输出要用到 <iomanip> 头文件，用 cout.setprecision(int digit) 来修改精度。

C++ 语法特性——动态开辟内存

1
2
3

int* number = new int;
int* arr = new int[10];
int* carr = (int*)malloc(100 * sizeof(int));

与 C 中的 malloc 类似，C++ 中用 new 来动态开辟内存。

new 写起来会更加简明一些。

C++ 不支持变长数组

【TIPS】平时写题的代码可以不适用 delete 释放内存。

C++ 语法特性——struct

struct node{
  int number;
  node* next;
  node (int _number = 0, node* _next = NULL) {
    number = _number;
    next = _next;
  }
};

node a = node(0);
node* b = new node(1, &a);

支持构造函数
支持默认参数

C 标准库常用函数回顾

<cstring>
- strlen() ：字符串长度
- strcmp()：字符串比较
- strcpy()：字符串拷贝
- memset()：暴力清空，memset(str, 0, sizeof(str));
- memcpy()：暴力拷贝
<cmath>
- 三角函数、指数函数、浮点取整函数
<cstdlib>
- qsort()：C语言快排
- rand()：随机数
- malloc()、free()：C语言动态分配内存
<ctime>
- time(0)：从1970年到现在的秒数（配合随机数）
- clock()：程序启动到目前为止的毫秒数
<ctype>
- isdigit()、isalpha()：判断字符是否为数字、大小写字母

C++ 标准库

<vector>、<string>、<algorithm>

C++ STL <vector> 数组：“超级数组”，既可以和C语言数组一样用下标访问，也可以像链表一样动态改变长度。

vector<int> arr(100);
vector<int> list;
list.push_back(1);
list.push_back(2);
list.push_back(3);

迭代器遍历：

vector<int>::iterator p1;
for (p1 = arr1.begin(); p1 != arr1.end(); p1++) {
  cout << *p1 << endl;
}

vector 的常见操作：

list.size();       // 数组元素个数 O(1)
list.clear();      // 一键清空数组 0(n)
list.empty();      // 数组是否为空 O(1)
list.begin();      // 数组首元素迭代器 O(1)
list.end();        // 数组最后一个元素的下一个元素的迭代器 O(1)，实际不存在
list.erase(p1);    // 删除数组某个迭代器所在位置的数字 O(n)
list.push_back(1); // 让数组后面添加元素 O(1)
list.pop_back();   // 删除数组最后一个元素 O(1)

C++ STL <string> 字符串：可以看成一个特殊的 vector

string str1 = "hello";
char str2[] = "world";
string str3;
str3.push_back('!');
cout << str1 << " " << str2 << str3 << endl;

String 和 c 语言字符串的关系就和vector和普通数组的关系一样。

string 常见操作：

string str = "hello";        
str.length(); str.size();   // O(n)
str.insert(1, "aaa");       // 在下标为1处插入一个字符或字符串 O(n)
str.insert(str.begin(),'a');// 在迭代器处插入一个字符或字符串O(n)
str.c_str();                // 返回C风格字符串，用于printf
str.append(str2);           // 把str2拼接到str后面 O(n)
str.compare(str2);          // strcmp(str, str2);
str == str2;                // strcmp(str, str2) == 0;
str += str2;                // str.append(str2);
str += 'a';                 // str.push_back('a');

C++ STL <algorithm> 算法函数

sort快速排序， $O(nlogn)$

int arr[]{2,3,1,5,4};
int n = 5;
// 参数：排序开始指针，排序结束指针（最后一个元素的下一个元素指针）
sort(arr, arr+n);

// 应用于vector
vector<int> list{2,1,3,5,4};
sort(list.begin(), list.end());
vector<int>::iterator p;
for (p = list.begin(); p != list.end(); ++p) {
	cout << *p << endl;
}

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

// 使用自定义比较函数
bool cmp(int a, int b){
	return a > b;
}

int main(){
	// freopen("in.txt", "r", stdin);
	vector<int> list{2,1,3,5,4};
	sort(list.begin(), list.end(), cmp);
	vector<int>::iterator p;
	for (p = list.begin(); p != list.end(); ++p) {
		cout << *p << endl;
	}
	return 1;
}

最大值、最小值： $O(n)$
1
min(1, 2); max(1, 2);

数组中最大最小指针： $O(n)$

1 2	max_element(arr.begin(), arr.end()); min_element(arr.begin(), arr.end());

部分快排：获取数组中第n小的元素

1	nth_element(arr.begin(), arr.begin() + n, arr.end());

交换任意两个同类型变量
1
swap(arr[0],arr[1]);
反转数组
1
reverse(arr.begin(), arr.end());
数组去重
1
int newlength = unique(arr.begin(), arr.end()-arr.begin());
Unique 需要在sort之后使用，unique大多数情况下是用于离散化的，在后续“线段树与树状数组”专题会重新介绍。

查找元素是否存在： $O(logn)$

1	bool isExist = binary_search(arr.begin(), arr.end(), 1);

查找有序数组中的元素插入位置： $O(logn)$
1
2
int firstLoc = lower_bound(arr.begin(), arr.end(), 2) - arr.begin();
int lastLoc = upper_bound(arr.begin(), arr.end(), 2) - arr.begin();
lower_bound一般被用来二分查找，灵活运用这两个函数可以得到有序数组中第一个比查找值大、小的数据。

C++ STL <stack>

stack<int> sta;
sta.push(1);
int topElement = sta.top();
sta.pop();
sta.empty();
sta.size();

C++ STL <queue>

queue<int> que;
que.push(1);
int frontElement = que.front();
que.pop();
que.empty();
que.size();
// 优先队列
priority_queue<int> que2;
que2.push(1);
int minElement = que2.top();
que2.top();
que2.empty();
que2.size();

C++ STL <set>

set<int> st;
st.insert(1);   //O(logn)
st.find(1);     //O(logn)
st.erase(1);    //O(logn)
// 多重集
multiset<int> mst;
mst.insert(1);
mst.insert(1);
mst.count(1); // 2

C++ STL <map>

pair<int, int> origin;
origin = make_pair(0, 0);
origin.first == origin.second;
origin.swap; // 返回swap的新pair

pair<string, int> id;
id = make_pair("somebody", 110);

map<string, int> studentHeight;
studentHeight["小明"] = 170;
studentHeight["小红"] = 150;
studentHeight.insert(id);
studentHeight.erase("小明");

<unordered_set> 和 <unordered_map>是set和map的另一种实现版本，这两种数据结构不孕内需按大小顺序遍历元素，但能 $O(1)$ 地访问和添加一个元素。

<bitset> 位集合：是一个只由0和1组成的数组，其占用空间小，不仅可以和数组一样用下标访问，还可以进行位运算。

bitset<1000> bst;
bst[0] = 1; bst.set(0);
bst[0] = 0; bst.reset(0);
bst << 1; bst >> 1; bst ^= 1; bst &= 1;
bst.count(); // 1的个数
bst.to_string();
bst.to_ullong();

<functional> 只是配合priority_queue一起使用
<complex> ：C++中的复数类