C++基础知识

标准输出

​x
1
int a = 10;
2

3
// 输出：10
4
cout << a << endl;
5

6
// 可以串联输出
7
// endl为换行
8
// 输出：Hello, World!
9
cout << "Hello" << ", " << "World!" << endl;
10

11
string s = "abc";
12
// 输出：abc 10
13
cout << s << " " << a << endl;

控制语句

条件判断 if else

xxxxxxxxxx
10
1
int a = 10;
2

3
if (a > 5) {
4
    cout << "a > 5" << endl;
5
} else if (a == 5) {
6
    cout << "a == 5" << endl;
7
} else {
8
    cout << "a < 5" << endl;
9
}
10
// 输出：a > 5

循环 for/while

• for 和 while 都可以用来做循环，for 循环一般用于已知循环次数的情况，while 循环一般用于未知循环次数的情况。

xxxxxxxxxx
11
1
// 0 1 2 3 4
2
for (int i = 0; i < 5; i++) {
3
    cout << i << " ";
4
}
5

6
int num = 100;
7
// 100 50 25 12 6 3 1
8
while (num > 0) {
9
    cout << num << " ";
10
    num /= 2;
11
}

基本数据结构

动态数组 vector

• vector 是 C++ 标准库的动态数组。

xxxxxxxxxx
22
1
#include <vector>
2

3
int n = 7, m = 8;
4

5
// 初始化一个 int 型的空数组 nums
6
vector<int> nums;
7

8
// 初始化一个大小为 n 的数组 nums，数组中的值默认都为 0
9
vector<int> nums(n);
10

11
// 初始化一个元素为 1, 3, 5 的数组 nums
12
vector<int> nums{1, 3, 5};
13

14
// 初始化一个大小为 n 的数组 nums，其值全都为 2
15
vector<int> nums(n, 2);
16

17
// 初始化一个二维 int 数组 dp
18
vector<vector<int>> dp;
19

20
// 初始化一个大小为 m * n 的布尔数组 dp，
21
// 其中的值都初始化为 true
22
vector<vector<bool>> dp(m, vector<bool>(n, true));

• vector 的常用操作：

xxxxxxxxxx
48
1
#include <iostream>
2
#include <vector>
3
using namespace std;
4

5
int main() {
6
    int n = 10;
7
    // 数组大小为 10，元素值都为 0
8
    vector<int> nums(n);
9
    // 输出 0 (false)
10
    cout << nums.empty() << endl;
11
    // 输出：10
12
    cout << nums.size() << endl;
13

14
    // 在数组尾部插入一个元素 20
15
    nums.push_back(20);
16
    // 输出：11
17
    cout << nums.size() << endl;
18

19
    // 得到数组最后一个元素的引用
20
    // 输出：20
21
    cout << nums.back() << endl;
22

23
    // 删除数组的最后一个元素（无返回值）
24
    nums.pop_back();
25
    // 输出：10
26
    cout << nums.size() << endl;
27

28
    // 可以通过方括号直接取值或修改
29
    nums[0] = 11;
30
    // 输出：11
31
    cout << nums[0] << endl;
32

33
    // 在索引 3 处插入一个元素 99
34
    nums.insert(nums.begin() + 3, 99);
35

36
    // 删除索引 2 处的元素
37
    nums.erase(nums.begin() + 2);
38

39
    // 交换 nums[0] 和 nums[1]
40
    swap(nums[0], nums[1]);
41

42
    // 遍历数组
43
    // 0 11 99 0 0 0 0 0 0 0
44
    for (int i = 0; i < nums.size(); i++) {
45
        cout << nums[i] << " ";
46
    }
47
    cout << endl;
48
}

• 根据数组的特性，利用索引访问元素很高效，从尾部增删元素也是很高效的；而从中间或头部增删元素要涉及搬移数据，很低效。

双链表 list

list 是 C++ 标准库中的双向链表容器。

xxxxxxxxxx
15
1
#include <list>
2

3
int n = 7;
4

5
// 初始化一个空的双向链表 lst
6
std::list<int> lst;
7

8
// 初始化一个大小为 n 的链表 lst，链表中的值默认都为 0
9
std::list<int> lst(n);
10

11
// 初始化一个包含元素 1, 3, 5 的链表 lst
12
std::list<int> lst{1, 3, 5};
13

14
// 初始化一个大小为 n 的链表 lst，其中值都为 2
15
std::list<int> lst(n, 2);

• 常用方法：

xxxxxxxxxx
50
1
#include <iostream>
2
#include <list>
3
using namespace std;
4

5
int main() {
6
    // 初始化链表
7
    list<int> lst{1, 2, 3, 4, 5};
8

9
    // 检查链表是否为空，输出：false
10
    cout << lst.empty() << endl;
11

12
    // 获取链表的大小，输出：5
13
    cout << lst.size() << endl;
14

15
    // 在链表头部插入元素 0
16
    lst.push_front(0);
17
    // 在链表尾部插入元素 6
18
    lst.push_back(6);
19

20
    // 获取链表头部和尾部元素，输出：0 6
21
    cout << lst.front() << " " << lst.back() << endl;
22

23
    // 删除链表头部元素
24
    lst.pop_front();
25
    // 删除链表尾部元素
26
    lst.pop_back();
27

28
    // 在链表中插入元素
29
    auto it = lst.begin();
30
    // 移动到第三个位置
31
    advance(it, 2);
32
    // 在第三个位置插入 99
33
    lst.insert(it, 99);
34

35
    // 删除链表中某个元素
36
    it = lst.begin();
37
    // 移动到第二个位置
38
    advance(it, 1);
39
    // 删除第二个位置的元素
40
    lst.erase(it);
41

42
    // 遍历链表
43
    // 输出：1 99 3 4 5
44
    for (int val : lst) {
45
        cout << val << " ";
46
    }
47
    cout << endl;
48

49
    return 0;
50
}

• 一般来说，当我们想在头部增删元素时会使用双链表，因为它在头部增删元素的效率比 vector 高。但我们通过索引访问元素，这种场景下我们会使用 vector。

队列 queue

• queue 是 C++ 标准库中的队列容器，基于先进先出（FIFO）的原则。队列适用于只允许从一端（队尾）添加元素、从另一端（队头）移除元素的场景。

xxxxxxxxxx
30
1
#include <iostream>
2
#include <queue>
3
using namespace std;
4

5
int main() {
6
    // 初始化一个空的整型队列 q
7
    queue<int> q;
8

9
    // 在队尾添加元素
10
    q.push(10);
11
    q.push(20);
12
    q.push(30);
13

14
    // 检查队列是否为空，输出：false
15
    cout << q.empty() << endl;
16

17
    // 获取队列的大小，输出：3
18
    cout << q.size() << endl;
19

20
    // 获取队列的队头和队尾元素，输出：10 和 30
21
    cout << q.front() << " " << q.back() << endl;
22

23
    // 删除队头元素
24
    q.pop();
25

26
    // 输出新的队头元素：20
27
    cout << q.front() << endl;
28

29
    return 0;
30
}

栈 stack

• 栈是一种后进先出（LIFO）的数据结构，栈适用于只允许在一端（栈顶）添加或移除元素的场景。

xxxxxxxxxx
31
1
#include <iostream>
2
#include <stack>
3
using namespace std;
4

5
int main() {
6

7
    // 初始化一个空的整型栈 s
8
    stack<int> s;
9

10
    // 向栈顶添加元素
11
    s.push(10);
12
    s.push(20);
13
    s.push(30);
14

15
    // 检查栈是否为空，输出：false
16
    cout << s.empty() << endl;
17

18
    // 获取栈的大小，输出：3
19
    cout << s.size() << endl;
20

21
    // 获取栈顶元素，输出：30
22
    cout << s.top() << endl;
23

24
    // 删除栈顶元素
25
    s.pop();
26

27
    // 输出新的栈顶元素：20
28
    cout << s.top() << endl;
29

30
    return 0;
31
}

哈希表 unordered_map

• unordered_map 是 C++ 标准库中的一种哈希表实现，它提供了基于键值对（key-value）的存储，提供了常数时间复杂度的查找、插入和删除键值对的操作。

xxxxxxxxxx
8
1
#include <unordered_map>
2
using namespace std;
3

4
// 初始化一个空的哈希表 map
5
unordered_map<int, string> hashmap;
6

7
// 初始化一个包含一些键值对的哈希表 map
8
unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};

• 特别注意：访问不存在的键会自动插入键值对

  • 在 C++ 的哈希表中，如果你访问一个不存在的键，它会自动创建这个键，对应的值是默认构造的值。

• 这一点和其他语言不同，需要格外注意。记住访问值之前要先判断键是否存在，否则可能会意外地创建新键，导致算法出错。

xxxxxxxxxx
68
1
#include <iostream>
2
#include <unordered_map>
3
using namespace std;
4

5
int main() {
6
    // 初始化哈希表
7
    unordered_map<int, string> hashmap{{1, "one"}, {2, "two"}, {3, "three"}};
8

9
    // 检查哈希表是否为空，输出：0 (false)
10
    cout << hashmap.empty() << endl;
11

12
    // 获取哈希表的大小，输出：3
13
    cout << hashmap.size() << endl;
14

15
    // 查找指定键是否存在
16
    // 注意 contains 方法是 C++20 新增的
17
    // 输出：Key 2 -> two
18
    if (hashmap.contains(2)) {
19
        cout << "Key 2 -> " << hashmap[2] << endl;
20
    } else {
21
        cout << "Key 2 not found." << endl;
22
    }
23

24
    // 获取指定键对应的值，若不存在会返回默认构造的值
25
    // 输出空字符串
26
    cout << hashmap[4] << endl;
27

28
    // 插入一个新的键值对
29
    hashmap[4] = "four";
30

31
    // 获取新插入的值，输出：four
32
    cout << hashmap[4] << endl;
33

34
    // 删除键值对
35
    hashmap.erase(3);
36

37
    // 检查删除后键 3 是否存在
38
    // 输出：Key 3 not found.
39
    if (hashmap.contains(3)) {
40
        cout << "Key 3 -> " << hashmap[3] << endl;
41
    } else {
42
        cout << "Key 3 not found." << endl;
43
    }
44

45
    // 遍历哈希表
46
    // 输出（顺序可能不同）：
47
    // 4 -> four
48
    // 2 -> two
49
    // 1 -> one
50
    for (const auto &pair: hashmap) {
51
        cout << pair.first << " -> " << pair.second << endl;
52
    }
53

54
    // 特别注意，访问不存在的键会自动创建这个键
55
    unordered_map<int, string> hashmap2;
56

57
    // 键值对的数量是 0
58
    cout << hashmap2.size() << endl; // 0
59

60
    // 访问不存在的键，会自动创建这个键，对应的值是默认构造的值
61
    cout << hashmap2[1] << endl; // empty string
62
    cout << hashmap2[2] << endl; // empty string
63

64
    // 现在键值对的数量是 2
65
    cout << hashmap2.size() << endl; // 2
66

67
    return 0;
68
}

哈希集合 unordered_set

• unordered_set 是 C++ 标准库中的一种哈希集合实现，用于存储不重复的元素，常见使用场景是对元素进行去重。

xxxxxxxxxx
8
1
#include <unordered_set>
2
using namespace std;
3

4
// 初始化一个空的哈希集合 set
5
unordered_set<int> uset;
6

7
// 初始化一个包含一些元素的哈希集合 set
8
unordered_set<int> uset{1, 2, 3, 4};

• 常用方法：

xxxxxxxxxx
46
1
#include <iostream>
2
#include <unordered_set>
3
using namespace std;
4

5
int main() {
6
    // 初始化哈希集合
7
    unordered_set<int> hashset{1, 2, 3, 4};
8

9
    // 检查哈希集合是否为空，输出：0 (false)
10
    cout << hashset.empty() << endl;
11

12
    // 获取哈希集合的大小，输出：4
13
    cout << hashset.size() << endl;
14

15
    // 查找指定元素是否存在
16
    // 输出：Element 3 found.
17
    if (hashset.contains(3)) {
18
        cout << "Element 3 found." << endl;
19
    } else {
20
        cout << "Element 3 not found." << endl;
21
    }
22

23
    // 插入一个新的元素
24
    hashset.insert(5);
25

26
    // 删除一个元素
27
    hashset.erase(2);
28
    // 输出：Element 2 not found.
29
    if (hashset.contains(2)) {
30
        cout << "Element 2 found." << endl;
31
    } else {
32
        cout << "Element 2 not found." << endl;
33
    }
34

35
    // 遍历哈希集合
36
    // 输出（顺序可能不同）：
37
    // 1
38
    // 3
39
    // 4
40
    // 5
41
    for (const auto &element : hashset) {
42
        cout << element << endl;
43
    }
44

45
    return 0;
46
}

传值和传引用

在 C++ 中，函数参数的传递方式主要有两种：传值和传引用。理解它们的区别对于编写高效的算法代码至关重要，特别是在处理大量数据或需要修改原始数据时。

传值（Pass by Value）

• 传值是指将函数参数的一个副本传递给函数，在函数内部对该副本的修改不会影响到原始数据。

xxxxxxxxxx
14
1
#include <iostream>
2
using namespace std;
3

4
void modifyValue(int x) {
5
    x = 10;  // 只修改副本，不会影响原始数据
6
}
7

8
int main() {
9
    int num = 5;
10
    modifyValue(num);
11
    // 输出：5
12
    cout << "After modifyValue, num = " << num << endl;
13
    return 0;
14
}

传引用（Pass by Reference）

• 传引用是指将实参的地址传递给函数，函数可以直接操作原始数据。这意味着对参数的修改会直接影响原始数据。

xxxxxxxxxx
14
1
#include <iostream>
2
using namespace std;
3

4
void modifyReference(int &x) {
5
    x = 10;  // 修改原始数据
6
}
7

8
int main() {
9
    int num = 5;
10
    modifyReference(num);
11
    // 输出：10
12
    cout << "After modifyReference, num = " << num << endl;
13
    return 0;
14
}

做算法题时的选择

• 如果是传递基本类型，比如 int、bool 等，用传值比较多，因为这类数据一般不需要在函数内部修改，而且复制的开销很小。

• 如果是传递容器数据结构，比如 vector、unordered_map 等，用传引用比较多，因为可以避免复制数据副本的开销，而且容器一般需要在函数内部修改。

• 特别注意一个可能出现的问题，就是当递归函数的参数中有容器数据结构时，千万别使用传值的方式，否则每次递归都会创建一个数据副本，消耗大量的内存和时间，非常容易导致超时或者超内存的错误。