c++

Ikko Lv4
  2025-12-18 00:29:04 2025-12-18 00:29:04 Created   2026-01-17 13:46:15 2026-01-17 13:46:15 Updated  2.5k Words  11 Mins  

常见排序算法概述表

排序算法 时间复杂度（平均） 时间复杂度（最坏） 空间复杂度 是否稳定 适用场景/特点
冒泡排序 是 简单，适合小数据量
选择排序 否 简单，交换次数少
插入排序 是 适合部分有序、小数据量
希尔排序 否 改进插入排序，较快
快速排序 否 实际应用最广泛
归并排序 是 稳定，适合大数据
堆排序 否 不稳定，适合大数据
计数排序 是 适合整数、范围小
桶排序 是 适合均匀分布数据
基数排序 是 适合数字、字符串排序

C++

最大堆

1
2
3
4
5
priority_queue<
    T,                // 存储的数据类型
    vector<T>,        // 底层容器类型（一般用 vector）
    Compare           // 比较函数（默认是 less<T>，即大顶堆）
> pq;
1
2
3
4
5
priority_queue<
    T,                // 存储的数据类型
    vector<T>,        // 底层容器类型（一般用 vector）
    Compare           // 比较函数（默认是 less<T>，即大顶堆）
> pq;
1
2
3
4
5
priority_queue<pair<int, int>> pq;  // 默认比较 first，再比较 second
pq.push({3, 100});
pq.push({1, 200});
pq.push({2, 50});
cout << pq.top().first;  // 输出 3

最小堆

1
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 最小堆

pair

访问方式：i.second, i.first，如果用不是 get<0>则会耗时

滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

最大堆

维护一个最大堆，（值，下标）。遍历数组进堆，然后弹出不符合滑动窗口的元素，堆顶即为当前窗口最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>> pg;
        vector<int> result;
        for(int i=0;i<nums.size();i++){
            pg.emplace(nums[i],i);
            if(i>=k-1){
                while(pg.top().second<=i-k){
                    pg.pop();
                }
                result.push_back(pg.top().first);
            }
        }
        return result;
    }
};

单调队列

维护一个单调递减队列，遍历数组进队列，然后弹出不符合滑动窗口的元素，队首即为当前窗口最大值。若队列中当前最小值小于新加入值，则将其弹出，直到队列为空或队尾值大于新加入值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dp;
        vector<int> result;
        for(int i=0;i<nums.size();i++){
            while(!dp.empty()&&nums[dp.back()]<=nums[i]){
                dp.pop_back();
            }
            dp.push_back(i);
            if(dp.front()<=i-k){
                dp.pop_front();
            }
            if(i>=k-1) result.push_back(nums[dp.front()]);
        }
        return result;
    }
};

注意stack 或 queue只有push
deque有push_front push_back pop_front pop_back

指针和引用

Node* a
“a 是一个指向 Node 的指针”
a 存放的是 Node 的地址
Node& a
“a 是一个 Node 的引用”
a 是某个 Node 的别名

哈希表

构造

#include
注意value不一定是int
std::unordered_map<key_type, value_type> map_name;

哈希表遍历

c++17

1
2
3
for (auto& [key, vec] : map) {
    result.push_back(vec);
}

常见用法补充

插入/修改

1
2
map[key] = value; // 插入或修改 key 对应的 value
map.insert({key, value}); // 只插入（若 key 已存在则不变） ‼️‼️‼️‼️

查找

1
2
3
4
5
6
if (map.count(key)) { /* 存在 */ }
if (map.find(key) != map.end()) { /* 存在 */ }
auto it = map.find(key);
if (it != map.end()) {
    // it->first 是 key，it->second 是 value
}

删除

1
map.erase(key); // 删除 key

计数器用法

1
2
unordered_map<int, int> cnt;
cnt[x]++; // 统计 x 出现次数

判断键是否存在

1
if (map.count(key)) { /* 存在 */ }

遍历所有键值对

1
2
3
for (const auto& [k, v] : map) {
    std::cout << k << ": " << v << std::endl;
}

其他常用操作

1
2
map.clear(); // 清空哈希表
map.size();  // 当前元素个数
1
2
3
for (auto& p : map) {
    result.push_back(p.second);
}

常见用法补充

插入/修改

1
2
3
map[key] = value; // 插入或修改 key 对应的 value
map.insert({key, value}); // 只插入（若 key 已存在则不变）
map.try_emplace(key, value); // 只插入（若 key 已存在则不变），且避免不必要的拷贝

查找

1
2
3
4
5
6
if (map.count(key)) { /* 存在 */ }
if (map.find(key) != map.end()) { /* 存在 */ }
auto it = map.find(key);
if (it != map.end()) {
    // it->first 是 key，it->second 是 value
}

删除

1
map.erase(key); // 删除 key

计数器用法

1
2
unordered_map<int, int> cnt;
cnt[x]++; // 统计 x 出现次数

判断键是否存在

1
if (map.count(key)) { /* 存在 */ }

遍历所有键值对

1
2
3
for (const auto& [k, v] : map) {
    std::cout << k << ": " << v << std::endl;
}

其他常用操作

1
2
map.clear(); // 清空哈希表
map.size();  // 当前元素个数

stl

end()

C++ STL 里，end() 的定义是：

“指向容器最后一个元素之后的那个位置”，
它不是有效元素，不能解引用。

lambda

1
2
3
[](const string& a, const string& b) {
            return a + b > b + a; // 关键比较逻辑
        }

nth_element快速求第k大值

左小右大

1
2
3
4
5
6
7
8

nth_element(v.begin(), v.begin() + v.size()/2, v.end());
int median = v[v.size()/2];


auto midptr = nums.begin() + n / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr;

lambda

注意lambda“}”后还有；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int x = 10;

// 1. 完全没 return → 返回 void
auto f1 = [] { std::cout << "我啥也不返回\n"; };
f1();                    // 可以调用
// int a = f1();         // 错误！不能赋值给 int，因为返回 void

// 2. 只有 return 一句话 → 自动推导返回 int
auto f2 = [] { return 42; };
int n = f2();            // 完美！n = 42

// 3. 有 return，但前面还有其他语句 → 必须手动写返回类型！！
auto f3 = [] {           // 错误！编译不过！！
    std::cout << "干活\n";
    return 100;
};

auto f3 = []() -> int {  // 正确！必须加 -> int
    std::cout << "干活\n";
    return 100;
};
int result = f3();       // OK

二进制相关

除2

1
2
int mid = (l + r) >> 1;
int half = n >> 1; // n 除以 2

move

右值引用（&&），专门用于“移动语义”，即资源转移

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include "../exercise.h"

// READ: 左值右值（概念）<https://learn.microsoft.com/zh-cn/cpp/c-language/l-value-and-r-value-expressions?view=msvc-170>
// READ: 左值右值（细节）<https://zh.cppreference.com/w/cpp/language/value_category>
// READ: 关于移动语义 <https://learn.microsoft.com/zh-cn/cpp/cpp/rvalue-reference-declarator-amp-amp?view=msvc-170#move-semantics>
// READ: 如果实现移动构造 <https://learn.microsoft.com/zh-cn/cpp/cpp/move-constructors-and-move-assignment-operators-cpp?view=msvc-170>

// READ: 移动构造函数 <https://zh.cppreference.com/w/cpp/language/move_constructor>
// READ: 移动赋值 <https://zh.cppreference.com/w/cpp/language/move_assignment>
// READ: 运算符重载 <https://zh.cppreference.com/w/cpp/language/operators>

class DynFibonacci {
    size_t *cache;
    int cached;

public:
    // TODO: 实现动态设置容量的构造器
    DynFibonacci(int capacity): cache(new size_t[capacity]), cached(2) {
        cache[0] = 0;
        cache[1] = 1;
    }

    // TODO: 实现移动构造器
    // 移动构造函数
    DynFibonacci(DynFibonacci &&other) noexcept
    : cache(other.cache), cached(other.cached) {
    other.cache = nullptr;
    other.cached = 0;
}

// 移动赋值运算符
    DynFibonacci &operator=(DynFibonacci &&other) noexcept {
    if (this != &other) {
        delete[] cache; // 释放自身资源
        cache = other.cache;
        cached = other.cached;
        other.cache = nullptr;
        other.cached = 0;
    }
    return *this;
}

    // TODO: 实现析构器，释放缓存空间
    ~DynFibonacci(){
        delete[] cache;
    }

    // TODO: 实现正确的缓存优化斐波那契计算
    size_t operator[](int i) {
        for (; cached <= i; ++cached) {
            cache[cached] = cache[cached - 1] + cache[cached - 2];
        }
        return cache[i];
    }

    // NOTICE: 不要修改这个方法
    size_t operator[](int i) const {
        ASSERT(i <= cached, "i out of range");
        return cache[i];
    }

    // NOTICE: 不要修改这个方法
    bool is_alive() const {
        return cache;
    }
};

int main(int argc, char **argv) {
    DynFibonacci fib(12);
    ASSERT(fib[10] == 55, "fibonacci(10) should be 55");

    DynFibonacci const fib_ = std::move(fib);
    ASSERT(!fib.is_alive(), "Object moved");
    ASSERT(fib_[10] == 55, "fibonacci(10) should be 55");

    DynFibonacci fib0(6);
    DynFibonacci fib1(12);

    fib0 = std::move(fib1);
    fib0 = std::move(fib0);
    ASSERT(fib0[10] == 55, "fibonacci(10) should be 55");

    return 0;
}

复制构造器

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "../exercise.h"

// READ: 复制构造函数 <https://zh.cppreference.com/w/cpp/language/copy_constructor>
// READ: 函数定义（显式弃置）<https://zh.cppreference.com/w/cpp/language/function>


class DynFibonacci {
    size_t *cache;
    int cached;

public:
    // TODO: 实现动态设置容量的构造器
    DynFibonacci(int capacity): cache(new size_t[capacity]), cached(2) {
        cache[0] = 0;
        cache[1] = 1;
    }
    // TODO: 实现复制构造器
    DynFibonacci(const DynFibonacci& other): cache(new size_t[other.cached + 1]), cached(other.cached) {
        for (int i = 0; i <= cached; ++i) {
            cache[i] = other.cache[i];
        }
    }

    // TODO: 实现析构器，释放缓存空间
    ~DynFibonacci(){
        delete[] cache;
    }

    // TODO: 实现正确的缓存优化斐波那契计算
    size_t get(int i) {
        for (; cached <= i; ++cached) {
            cache[cached] = cache[cached - 1] + cache[cached - 2];
        }
        return cache[i];
    }

    // NOTICE: 不要修改这个方法
    // NOTICE: 名字相同参数也相同，但 const 修饰不同的方法是一对重载方法，可以同时存在
    //         本质上，方法是隐藏了 this 参数的函数
    //         const 修饰作用在 this 上，因此它们实际上参数不同
    size_t get(int i) const {
        if (i <= cached) {
            return cache[i];
        }
        ASSERT(false, "i out of range");
    }
};

int main(int argc, char **argv) {
    DynFibonacci fib(12);
    ASSERT(fib.get(10) == 55, "fibonacci(10) should be 55");
    DynFibonacci const fib_ = fib;
    ASSERT(fib_.get(10) == fib.get(10), "Object cloned");
    return 0;
}

函数模版化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "../exercise.h"

// READ: 函数模板 <https://zh.cppreference.com/w/cpp/language/function_template>
// TODO: 将这个函数模板化
template<typename T>
T plus(T a, T b) {
    return a + b;
}

int main(int argc, char **argv) {
    ASSERT(plus(1, 2) == 3, "Plus two int");
    ASSERT(plus(1u, 2u) == 3u, "Plus two unsigned int");

    // THINK: 浮点数何时可以判断 ==？何时必须判断差值？
    ASSERT(plus(1.25f, 2.5f) == 3.75f, "Plus two float");
    ASSERT(plus(1.25, 2.5) == 3.75, "Plus two double");
    // TODO: 修改判断条件使测试通过
    auto result = plus(0.1, 0.2);
    ASSERT(result > 0.29 && result < 0.31, "How to make this pass?");

    return 0;
}

vector “管理器

在 64 位平台上（macOS arm64），一个 std::vector 通常内部就存 3 个指针/指针样的东西：

begin：指向数据起始
end：指向已用末尾（size 的边界）
cap：指向容量末尾（capacity 的边界）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
std::vector<char> vec(48, 'z'); // TODO: 调用正确的构造函数
        ASSERT(vec[0] == 'z', "Make this assertion pass.");
        ASSERT(vec[47] == 'z', "Make this assertion pass.");
        ASSERT(vec.size() == 48, "Make this assertion pass.");
        ASSERT(sizeof(vec) == 24, "Fill in the correct value.");
        {
            auto capacity = vec.capacity();
            vec.resize(16);
            ASSERT(vec.size() == 16, "Fill in the correct value.");
            ASSERT(vec.capacity() == capacity, "Fill in a correct identifier.");
        }
        {
            vec.reserve(256);
            ASSERT(vec.size() == 16, "Fill in the correct value.");
            ASSERT(vec.capacity() == 256, "Fill in the correct value.");
        }

string

string substr(size_t pos, size_t len) const;

从下标 pos 开始，取 len 个字符

1
2
3
string s = "abcdef";
string t = s.substr(3); // "def"
s.substr(start, end - start + 1)
  • Title: c++
  • Author: Ikko
  • Created at : 2025-12-18 00:29:04
  • Updated at : 2026-01-17 13:46:15
  • Link: http://ikko-debug.github.io/2025/12/18/c/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
c++
  1. 常见排序算法概述表
  • C++
    1. 最大堆
    2. 最小堆
    3. pair
      1. 滑动窗口最大值
      2. 指针和引用
    4. 哈希表
      1. 构造
      2. 哈希表遍历
      3. 常见用法补充
      4. 常见用法补充
    5. stl
      1. end()
    6. lambda
    7. nth_element快速求第k大值
    8. lambda
    9. 二进制相关
      1. 除2
    10. move
    11. 复制构造器
    12. 函数模版化
    13. vector “管理器
    14. string
      1. string substr(size_t pos, size_t len) const;