C++知识

指针

  • *号的两种使用

  • 定义指针int* p, int *p，星号位置不重要

  • 解指针p = &a ,*(p)

  • 指针可用->访问成员变量，ptr->member等价于(*ptr).member

  • 也可以连续访问root->left->right

1
2
3
it是一个迭代器，
vector<int>& nums = it->second;   // (1) 引用
vector<int> nums = it->second;    // (2) 值拷贝，一般不用

new关键字返回的是指针
所以构造结点的正确做法如下

1
2
3
4
5
6
Node* p = new Node(0);
// 或者
Node dummy(0);          // 直接构造
Node* p = &dummy;       // 获取指针，地址要用指针类型来接收
// 或
Node dummy = Node(0);   // 拷贝初始化（C++17 后也是直接构造）

引用，与目标共享一个内存空间，修改引用，也会修改目标

1
2
int& res = vec[i];  // res 是 vec[i] 的引用（别名）
int* res = &vec[i];  // res 是一个指针，指向 vec[i]，输出 vec[i] 的地址

迭代器

  • 迭代器是一种泛化的指针，用于统一访问各种容器中的元素

  • 所有标准容器都有迭代器

  • 为什么返回迭代器而不是索引？因为不是所有容器都有索引，迭代器是通用位置的抽象

  • 实质是一个指针，可用it -> first, it -> second访问内部成员

  • 也可以完全解指针&a = *it, a -> first

  • 用于迭代for (auto it = c.begin(); it != c.end(); ++it)或者for (const auto& x : vec)

  • 类型复杂所以直接用 auto 声明

  • 很多函数返回的都是迭代器，就比如lower_bound(), map.find(key), nums.begin(), nums.end()

vector 向量（动态数组）

  • vector<int> vec(n, 1);初始化长度为 n,元素全为 1 的向量

  • vector<vector<int>> vec;空的二维向量

  • int m = matrix.size(), n = matrix[0].size();获取向量的长度 m，每一项的长度为 n

  • vec.push_back({b});添加每一项的第一个

  • vec[i].push_back(b);添加每一项的第二个

  • vec.resize(n);初始化,分配空间之后才能赋值，所有初值为 0

  • swap(nums[i], nums[j]);交换两个元素

  • vec[0], vec.back()返回第一个和最后一个元素的引用

  • vec.begin(), vec.end()返回第一个和最后一个元素的迭代器

  • ranges::reverse(nums.begin(), nums.begin() + k);翻转向量，123->321

  • ranges::sort(vec);排序数组

  • ranges::sort(vec.begin(), vec.end());排序指定区间的数组

  • auto it = v.begin() + index; 通过索引返回迭代器

  • vec.erase(it);动态删除向量里的元素

  • vec1 = move(vec2);把 vec2 内部的指针等资源直接转移给 vec1，vec2 空，时间复杂度 O(1)，vec1 会被完全覆盖

  • vec.emplace_back(pair)功能相当于vec.push_back(pair)，但在面对复杂对象时效率更高，他是直接在 vec 里面创建这个对象

  • vector vec(n, string(m, '.'));快捷创建 n 行 m 列二维向量，内部是 string，前面

  • vector memo(n, vector<int>(amount + 1, -1));快捷创建二维数组，前面的 vector 不用写<>也行，C++会自己推导

1
2
3
4
// 初始化向量
vector<int> vec;
vec.resize(n);
vec[i] = 1;

二维向量相关操作

1
2
3
4
5
6
7
8
9
10
// leetCode第56题合并区间
vector<vector<int>> ans;// 新建一个二维向量
ranges::sort(intervals); // 二维向量按照左端点从小到大排序
for (auto& pair : intervals) {
    if (!ans.empty() && ans.back()[1] >= pair[0]) {// .back()访问最后一项，[1]访问第二个元素
        ans.back()[1] = max(ans.back()[1], pair[1]);
        continue;
    }
    ans.emplace_back(pair);// 如果不满足就在ans中构建这个新pair
}

unordered_map 哈希表

  • unordered_map<int, int> map;初始化
  • map[i] == map2[i]用操作符[]访问不存在的 key 时会隐式的插入 0 污染 map，即使作为判断条件也是
  • map.count(key)判断是否存在，返回 0 或 1，在上面的判断条件里加上map2.count(s[i]) &&先执行就能避免污染
  • map 是无序的，用for (auto& x : map)迭代也是随机的

lambda 表达式（匿名函数）

C++在方法内定义方法就要用这种隐函数的语法
函数名只能用 auto
[capture](parameters) -> return-type { body }

1
2
3
auto sum = [&](int b) -> int {
    // ...
};

捕获器类型

  • [] 不捕获任何外部变量
  • [&] 按引用捕获所有用到的外部变量（推荐用于读写或大对象）
  • [=] 按值捕获所有用到的外部变量（只读副本）
  • [&nums, threshold] 显式按引用捕获 nums，按值捕获 threshold

定义递归函数，把函数自身作为参数传进去(this auto&& dfs)

1
2
3
4
5
6
7
8
9
10
11
auto dfs = [&](this auto&& dfs, int i, int j) -> void {
            // 出界，或者不是 '1'，就不再往下递归
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] != '1') {
                return;
            }
            grid[i][j] = '2'; // 插旗！避免来回横跳无限递归
            dfs(i, j - 1); // 往左走
            dfs(i, j + 1); // 往右走
            dfs(i - 1, j); // 往上走
            dfs(i + 1, j); // 往下走
        };

<<>>位运算符

<<运算符用于左移，>>运算符用于右移

1
2
3
4
5
6
7
8
x << 3  // 等价于 x * 8

int a = 5;        // 二进制: 00000101
int b = a << 1;   // 左移1位 → 00001010 = 10
int c = a << 2;   // 左移2位 → 00010100 = 20

cout << b << endl; // 输出: 10
cout << c << endl; // 输出: 20

&运算符用于位与，|运算符用于位或，^运算符用于位异或，~运算符用于位取反

1
2
3
4
5
// 检查第 c 位是否为 1
if (vis >> c & 1) { // c 在集合中
    return false;
}
vis |= 1 << c; // 把 c 加入集合

deque 双端队列

两侧都能添加和删除元素
deque<int> q;初始化
pop_front() 删除队列首元素,动态删除，删完之后队首元素索引还是 0
pop 访问队首元素，但不删除

条件运算顺序

C++ 的&&是从左到右求值，所以会先执行q.back()，再判断!q.empty()，在 q 为空的时候这么做会报错
正确做法:while (!q.empty() && nums[i] > nums[q.back()])

字符串

  • 操作和动态数组很像

  • 可以直接加减字符串string ans = t + 'a'

  • 字符串是可变的，但在作为 key 的时候存储的是字符串的副本，所以修改原来的字符串不影响

    构建子串

  • std::string sub1 = s.substr(0, 5); // 选取从 0 开始的长度为 5 的子串

  • std::string sub2 = s.substr(7); // 选取从 7 开始的子串

stack 栈

  • stack<int> s;初始化
  • s.push(x)入栈
  • s.pop()出栈
  • s.top()访问栈顶元素,要获取栈顶再弹出就要先 top()再 pop()
  • s.empty()判断栈是否为空
  • st = stack<int>();构造空栈，置空栈

单调栈，栈内元素是单调的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 84. 柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int ans = 0;
stack<int> st;
st.push(-1);// 用-1 入栈来做哨兵元素，这样所有左侧第一小保底就是-1，改 while 循环条件
heights.push_back(-1); // 结尾也加哨兵元素，就能用用 -1 把栈清空

        // 有了哨兵元素而且能直接计算，所以最后数组也不需要了
        for (int right = 0; right < heights.size(); right++) {// i改叫right，更直观
            int h = heights[right];
            // 在进入while的时候，当前的right就是栈顶的左侧第一小！！！
            // 数组结尾添加一个哨兵-1，遍历到-1，就能最后把栈排空
            while (st.size() > 1 && h <= heights[st.top()]) {
                int h_ans = heights[st.top()];// 保存当前栈顶的高
                // 弹出一个元素之后，当前栈顶就是被弹出栈顶的左侧第一小！！！
                st.pop();
                int left = st.top();
                ans = max(ans, h_ans * (right - left - 1));
            }
            st.push(right);
        }
        return ans;
    }
};

queue 队列

先进后出，从队尾入队，队首出队(就是排队)
可用于广度优先搜索(BFS)

  • queue<T> q;初始化
  • q.push(x)入队
  • q.pop()出队
  • q.front()访问队首元素,要获取队首再弹出就要先 front()再 pop()
  • q.empty()判断队列是否为空

Deque 双端队列

构造函数的初始化列表

用初始化列表初始化成员变量，比赋值更高效
const 成员和引用成员只能用初始化列表初始化

  • LRUCache(int _capacity) 是构造函数的参数列表；
  • :capacity(_capacity),size(0) 为初始化列表
1
2
3
4
5
6
7
8
9
10
class LRUCache {
private:
    int size;
    int capacity;
public:
    // 构造函数,接受一个传入的参数_capacity用他capacity,然后再初始化size为0
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        // 使用初始化的值
    }
}

结构体

结构体(struct)是一种用户自定义的数据类型，允许将不同类型的数据组合在一起。
结点就是一种定义的结构体，用指针加成员访问符->可以访问成员变量，用结构体名加.也可以访问成员变量

1
2
3
4
5
6
7
8
9
10
11
// 定义一个结构体实现双向链表，包含4个属性，key，value，前后指针
struct DLinkedNode {
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    // 默认构造器
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
    // 带参构造器
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

pair 二元组

pair 是 C++ 标准库中的一个类，用于存储两个元素。
适合遍历图，Map，表示坐标，键值对
有两个成员变量 first 和 second，分别表示键和值。

vector<pair<int, int>> q;坐标向量
for (auto& [x, y] : q)结构化绑定遍历
或者for (auto& p : q)然后用 p.first, p.second 访问

Map 哈希表

map 里面的元素是键值对，pair 来表示，也可称作 entry
first 和 second 是 pair 的成员变量

map 的遍历
for (auto& [key, value] : map)结构化绑定，里面是形参代表的键值
for (auto& p : map)然后用 p.first, p.second 访问`

堆（优先队列）

priority_queue<int> pq;最大堆，top()是最大值
priority_queue<int, vector<int>, greater<int>> minHeap;最小堆，top()是最小值

以下是优先队列(priority_queue)的操作总结表：

操作 时间复杂度 说明
push(x) O(log n) 插入元素
pop() O(log n) 删除堆顶元素（无返回值！）
top() O(1) 返回堆顶元素（不删除）
empty() O(1) 判断是否为空
size() O(1) 返回元素个数

注意事项：

  • ❌ 不能遍历：没有迭代器，不能 for-each。
  • ❌ 不能随机访问：只能通过 top() 访问堆顶。
  • ❌ 不能修改内部元素：一旦插入，只能通过 pop() 删除。
  • ❌ 不能高效查找或删除任意元素：不是设计用来干这个的。

set

  1. unordered_set<int> mySet;// 初始化
    // 用 vector 的 begin() 和 end() 初始化 unordered_set
    unordered_set<int> mySet(vec.begin(), vec.end());

  2. 插入元素

    1
    2
    3
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(10); // 重复插入无效，仍只存一个 10

  3. 查找元素

    1
    2
    3
    4
    5
    6
    7
    if (mySet.find(10) != mySet.end()) {
        cout << "Found 10\n";
    }
    // 或者用 count（返回 0 或 1）
    if (mySet.count(10)) {
        cout << "10 exists\n";
    }

  4. 删除元素

mySet.erase(10); // 删除值为 10 的元素

知识
C++知识
http://www.981928.xyz/2025/11/05/C-知识/
作者
981928
发布于
2025年11月5日
许可协议