C++知识

指针

• *号的两种使用

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

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

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

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

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

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

Node* p = new Node(0);
// 或者
Node dummy(0);          // 直接构造
Node* p = &dummy;       // 获取指针
// 或
Node dummy = Node(0);   // 拷贝初始化（C++17 后也是直接构造）

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)排序数组
• vec.erase(it)动态删除向量里的元素

vector<int> vec;
vec.resize(n);
vec[i] = 1;

vec.emplace_back(pair)相当于vec.push_back(pair)，但在面对复杂对象时效率更高

二维向量相关操作

// 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)迭代也是随机的

迭代器

• 实质是一个指针，可用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()

lambda 表达式（匿名函数）

函数名只能用 auto
[capture](parameters) -> return-type { body }

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

捕获器类型

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

<<>>位运算符

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

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

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

// 检查第 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'

栈 stack

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

队列 queue

先进后出，可用于广度优先搜索(BFS)

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

构造函数的初始化列表

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

• LRUCache(int _capacity) 是构造函数的参数列表；
• :capacity(_capacity),size(0) 为初始化列表

class LRUCache {
private:
    int size;
    int capacity;
public:
    // 构造函数,接受一个传入的参数_capacity用他capacity,然后再初始化size为0
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        // 使用初始化的值
    }
}

结构体

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

// 定义一个结构体实现双向链表，包含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) {}
};