时间轴

2025-10-03

init

2025-10-12

add next_permutation 生成序列的全排列

语法

& 与 &&，左值与右值

  • 左值 (Lvalue)

    • 有名字，可取地址。

    • 可以出现在赋值符号左边。

    • 例子：

      1
      2
      3
      int x = 5; // x 是左值
      x = 10;    // 可以赋值
      int* p = &x; // 可以取地址

  • 右值 (Rvalue)

    • 临时对象或字面量，没有名字，不能取地址。

    • 通常出现在赋值符号右边。

    • 例子：

      1
      2
      int y = x + 2; // x+2 是右值
      int z = 42;    // 42 是右值

    注意：右值可以绑定到 右值引用 (&&)。

  • 引用类型
引用 含义
T& 左值引用（只能绑定到左值）
T&& 右值引用（只能绑定到右值）

示例：

1
2
3
int a = 5;
int &lref = a;   // 左值引用，a 是左值
int &&rref = 5;  // 右值引用，5 是右值
  • 左值引用可以修改左值：
1
lref = 10; // a = 10
  • 右值引用常用于移动语义：
1
2
vector<int> v1 = {1,2,3};
vector<int> v2 = std::move(v1); // 右值引用允许移动资源

STL

vector

引用头文件

1
2
#include <vector>
using std::vector;

构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 空 vector
vector<int> v1;

// 指定大小，默认初始化为0
vector<int> v2(5);  // 5个元素，每个为0

// 指定大小和初始值
vector<int> v3(5, 42);  // 5个元素，每个为42

// 通过 initializer_list
vector<int> v4 = {1, 2, 3, 4};

// 复制另一个 vector
vector<int> v5(v4);

// 从数组构造
int arr[] = {10, 20, 30};
vector<int> v6(arr, arr + 3);

访问元素

  • 返回的是元素的引用

  • 带边界检查的访问如果越界会抛出 std::out_of_range 异常

1
2
3
4
5
6
7
8
9
// 通过索引访问（不做边界检查）
int a = v[0];

// 通过 at() 访问（带边界检查）
int b = v.at(1); 

// 访问首尾元素
int first = v.front();
int last = v.back();

修改元素

1
2
3
4
5
6
v[2] = 10;     // 修改索引2的值
v.push_back(5); // 在末尾插入元素
v.pop_back();   // 删除末尾元素
v.insert(v.begin() + 1, 20); // 在索引1位置插入20
v.erase(v.begin() + 2);      // 删除索引2的元素
v.clear();                   // 清空所有元素

遍历元素

1
2
3
4
5
6
7
8
9
10
11
// 索引遍历
for (size_t i = 0; i < v.size(); ++i)
    std::cout << v[i] << " ";

// 迭代器遍历
for (auto it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

// 范围 for（C++11+）
for (auto &x : v)
    std::cout << x << " ";

时间复杂度

操作 时间复杂度 说明
v[i] O(1) 随机访问
v.at(i) O(1) 随机访问，带边界检查
push_back(x) O(1) 摊销 平均常数时间，偶尔扩容 O(n)
pop_back() O(1) 删除末尾元素
insert(v.begin() + i, x) O(n) 插入到中间，平均移动 n/2 个元素
erase(v.begin() + i) O(n) 删除中间元素，平均移动 n/2 个元素
front() / back() O(1) 访问首尾元素
size() / empty() O(1) 获取大小/是否为空
clear() O(n) 清空元素（析构调用）
sort(v.begin(), v.end()) O(n log n) 使用 STL 算法排序

queue

引用头文件

1
2
#include <queue>
using std::queue;

构造

1
2
3
4
5
// 空队列
queue<int> q1;

// 拷贝构造
queue<int> q2(q1);

访问队头队尾

1
2
3
// 查看队首/队尾元素
int front_val = q.front();
int back_val  = q.back();

入队出队

1
2
3
4
5
6
// 入队（尾部插入）
q.push(10);
q.push(20);

// 出队（头部删除）
q.pop();

时间复杂度

操作 时间复杂度
push() O(1)
pop() O(1)
front() O(1)
back() O(1)
empty() O(1)
size() O(1)

priority_queue

  • 优先队列，内部默认使用大顶堆

  • 出队时总是弹出队列中 最大的元素（默认大顶堆）。

  • 可以自定义比较器实现 小顶堆。

priority_queue没有迭代器，只能利用pop()和top()实现遍历

引用头文件

1
2
#include <queue>
using std::priority_queue;

构造

priority_queue的泛型参数中第一个是存储元素的类型，第二个是存储元素的容器，默认为vector，第三个是元素的比较器

注意priority_queue除了能弹出堆顶外，不支持直接修改或删除堆中某一个元素

  • 如果想要删除priority_queue中某一个元素，建议考虑能不能配合unordered_map实现懒删除(只有无效元素到堆顶了才删除，否则只做标记)
1
2
3
4
5
6
7
8
9
10
11
// 默认构造
priority_queue<int> pq1;
// 默认构造的全部参数
priority_queue<int,vector<int>,std::less<int>>;
// 拷贝构造
priority_queue<int> pq2(pq1);

// 从容器构造
#include <vector>
std::vector<int> v = {1, 3, 2};
priority_queue<int> pq3(v.begin(), v.end()); // 默认最大堆

访问堆顶

1
2
priority_queue<int> pq;
int top_val = pq.top(); // 20

弹出堆顶元素

1
pq.pop();

自定义比较器

方法1：使用 std::greater\实现小顶堆

1
priority_queue<int, vector<int>, std::greater<int>> min_pq;

方法2：自定义结构体/lambda

1
2
3
4
struct cmp {
    bool operator()(int a, int b) { return a > b; } // 最小值优先
};
priority_queue<int, vector<int>, cmp> pq_custom;

方法3：如果是结构体，直接重载<运算符

1
2
3
4
5
6
7
8
9
10
11
struct Person {
    string name;
    int age;

    // 重载 < 运算符
    bool operator<(const Person& other) const {
        return age < other.age;  // 默认大顶堆，年龄大的优先
    }
};

priority_queue<Person> pq;

时间复杂度

操作 平均复杂度
push O(log n)
pop O(log n)
top O(1)
size O(1)
empty O(1)

stack

栈，先进后出

stack 没有迭代器，不能用 for 循环直接遍历。遍历只能通过 top() + pop()。

引用头文件

1
2
#include <stack>
using std::stack;

构造

1
2
stack<int> s1;          // 空栈
stack<int> s2(s1);      // 拷贝构造

入栈/出栈

1
2
3
4
5
6
stack<int> s;
// 入栈（push 到栈顶）
s.push(20);

// 出栈（pop 栈顶元素）
s.pop();

访问栈顶元素

1
2
// 查看栈顶元素
int top_val = s.top();  // 栈顶元素

时间复杂度

操作 平均复杂度
push O(1)
pop O(1)
top O(1)
size O(1)
empty O(1)

map, unordered_map

  • map

    • map 是 有序关联容器，底层通常用 红黑树 实现。

    • 每个元素是 key-value 对，key 唯一，自动按 key 排序。

    • 适合需要 按键顺序访问 的场景。

  • unordered_map

    • unordered_map 是 哈希表，无序存储 key-value。
    • 查找、插入和删除平均时间复杂度为 O(1)。
    • 适合快速查找，不关心顺序。

    GCC 的 unordered_map 自 C++11 起有一个优化：

    • 当某个桶内链表长度超过一定阈值（通常是 8）时，链表会转为红黑树。
    • 这样可以防止 最坏情况哈希冲突导致的 O(n) 复杂度，把查找复杂度从 O(n) 降到 O(log n)。
    • 也就是：链表 → 红黑树，而不是整个哈希表退化为红黑树。

引用头文件

map

1
2
3
// map
#include <map>
using std::map;

unordered_map

1
2
3
// unordered_map
#include <unordered_map>
using std::unordered_map;

构造

map

1
2
3
4
5
6
7
8
// 空 map
map<int, string> m1;

// 拷贝构造
map<int, string> m2(m1);

// 初始化列表
map<int, string> m3 = {{1, "one"}, {2, "two"}};

unordered_map

1
2
3
4
5
6
7
8
// 空表
unordered_map<int, string> um1;    

// 拷贝构造
unordered_map<int, string> um2(um1);   

// 初始化列表
unordered_map<int, string> um3 = {{1,"one"}, {2,"two"}};

访问元素

map

1
2
3
4
5
map<int, string> m;

// 访问元素
string s = m[1];       // key 必须存在，否则会创建默认值

unordered_map

1
2
3
4
unordered_map<int, string> um;

// 访问元素
string s = m[1];       // key 必须存在，否则会创建默认值

插入，修改和元素

map

1
2
3
4
5
6
map<int, string> m;

// 插入元素
m.insert({3, "three"});
m[1] = "one";     // 插入或修改
m[2] = "two";

unorder_map

1
2
3
4
5
6
unordered_map<int, string> um;

// 插入
um.insert({3, "three"});
um[1] = "one";
um[2] = "two";

查找元素

map

1
2
3
4
5
6
map<int, string> m;

bool hasKey = um.count(2); // 0 或 1

auto it = m.find(2);   // 返回迭代器，找不到返回 m.end()
bool hasKey = um.count(2); // 0 或 1

unordered_map

1
2
3
4
unordered_map<int, string> um;

auto it = um.find(2);  // 返回迭代器，找不到返回 um.end()
bool hasKey = um.count(2); // 0 或 1

删除元素

map

1
2
3
4
5
map<int, string> m;

// 删除元素
m.erase(1);            // 根据 key 删除
m.erase(m.begin());    // 根据迭代器删除

unordered_map

1
2
3
4
5
unordered_map<int, string> um;

// 删除
um.erase(1);
m.erase(um.begin());    // 根据迭代器删除

遍历

map

map是按key有序遍历的

1
2
3
4
5
map<int, string> m;

for (auto &[key, value] : m) {
    cout << key << " -> " << value << endl;
}

unordered_map

注意：unordered_map 是无序的，遍历顺序不固定。

1
2
3
for (auto &[key, value] : um) {
    cout << key << " -> " << value << endl;
}

自定义比较器（仅map支持）

1
map<int, string, std::greater<int>> m; // 按 key 降序

时间复杂度

map

操作 平均复杂度
插入/删除 O(log n)
查找 O(log n)
遍历 O(n)
访问元素 O(log n)

unordered_map

操作 平均复杂度 最坏复杂度
插入 O(1) O(n)
查找 O(1) O(n)
删除 O(1) O(n)
遍历 O(n) O(n)

set, unordered_set

  • set
    • set 是 有序集合，底层通常用 红黑树 实现。
    • 存储 唯一元素，自动按元素大小排序。
    • 适合需要 有序访问和快速查找唯一元素 的场景。
  • unordered_set
    • unordered_set 是 哈希表集合，无序存储唯一元素。
    • 平均查找、插入和删除复杂度为 O(1)。
    • 适合快速查找，不关心顺序。

      GCC 的 unordered_set 同样支持 链表长度超过阈值时桶内树化，避免最坏情况 O(n)。

引用头文件

set

1
2
#include <set>
using std::set;

unordered_set

1
2
#include <unordered_set>
using std::unordered_set;

构造

set

1
2
3
set<int> s1;               // 空集合
set<int> s2(s1);           // 拷贝构造
set<int> s3 = {1, 2, 3};   // 初始化列表

unordered_set

1
2
3
unordered_set<int> us1;              // 空集合
unordered_set<int> us2(us1);         // 拷贝构造
unordered_set<int> us3 = {1, 2, 3};  // 初始化列表

插入和修改

set

1
2
3
4
5
set<int> s;

s.insert(10);  // 插入元素
s.insert(20);
s.insert(10);  // 重复元素不会插入

unordered_set

1
2
3
4
5
unordered_set<int> us;

us.insert(10);
us.insert(20);
us.insert(10);  // 重复元素不会插入

查找元素

set

1
2
3
4
set<int> s = {1,2,3};

auto it = s.find(2);   // 返回迭代器，找不到返回 s.end()
bool exists = s.count(2); // 返回 0 或 1

unordered_set

1
2
3
4
unordered_set<int> us = {1,2,3};

auto it = us.find(2);   // 返回迭代器，找不到返回 us.end()
bool exists = us.count(2); // 返回 0 或 1

删除元素

set

1
2
s.erase(2);        // 根据元素值删除
s.erase(s.begin()); // 根据迭代器删除

unordered_set

1
2
us.erase(2);
us.erase(us.begin());

遍历

set

按元素升序遍历

1
2
3
for (auto &val : s) {
    cout << val << " ";
}

unordered_set

遍历顺序不固定

1
2
3
for (auto &val : us) {
    cout << val << " ";
}

自定义比较器（仅 set 支持）

1
set<int, std::greater<int>> s; // 按降序排列

时间复杂度

set

操作 平均复杂度
插入/删除 O(log n)
查找 O(log n)
遍历 O(n)

unordered_set

操作 平均复杂度 最坏复杂度
插入 O(1) O(n)
查找 O(1) O(n)
删除 O(1) O(n)
遍历 O(n) O(n)

multiset/multimap

multiset\

  • 元素 可重复，自动按 key 排序
  • 底层通常使用 红黑树
  • 不支持通过下标访问，只能用迭代器
  • 适合需要 快速查找和按顺序遍历重复元素

multimap\

  • key 可重复，按 key 排序
  • 底层通常使用 红黑树
  • 可以通过 equal_range 查找某个 key 的所有元素

引用头文件

1
2
3
4
5
6
7
// multiset
#include <set>
using std::multiset;

// multimap
#include <map>
using std::multimap;

构造

multiset

1
2
3
multiset<int> ms;            // 空 multiset
multiset<int> ms2(ms);        // 拷贝构造
multiset<int> ms3 = {1,2,2,3}; // 初始化列表

multimap

1
2
3
multimap<int,string> mm;            // 空 multimap
multimap<int,string> mm2(mm);       // 拷贝构造
multimap<int,string> mm3 = {{1,"a"},{2,"b"},{2,"c"}}; // 初始化列表

插入元素

1
2
3
4
5
6
7
// multiset
ms.insert(2);
ms.insert(2); // 可以重复

// multimap
mm.insert({2,"b"});
mm.insert({2,"c"}); // key 可以重复

查找元素

1
2
3
4
5
6
7
8
9
// multiset
auto it = ms.find(2);       // 返回第一个 2 的迭代器
size_t cnt = ms.count(2);   // 2 出现的次数

// multimap
auto range = mm.equal_range(2); // 返回 key=2 的元素区间 [first, second)
for(auto it = range.first; it != range.second; ++it) {
    cout << it->first << " -> " << it->second << endl;
}

删除元素

1
2
3
4
5
6
7
8
9
// multiset
ms.erase(2);          // 删除所有值为 2 的元素
auto it = ms.find(2);
ms.erase(it);         // 删除单个迭代器指向的元素

// multimap
mm.erase(2);          // 删除所有 key=2 的元素
auto it2 = mm.find(2);
mm.erase(it2);        // 删除单个迭代器指向的元素

遍历

1
2
3
4
5
6
7
8
9
10
// multiset
for(auto &x : ms) {
    cout << x << " ";
}
cout << endl;

// multimap
for(auto &[key,value] : mm) {
    cout << key << " -> " << value << endl;
}

时间复杂度

操作 multiset / multimap
插入 O(log n)
查找 O(log n)
删除 O(log n)
遍历 O(n)

tuple

引用头文件

1
2
#include <tuple>
using std::tuple;

构造

1
2
3
4

tuple<int,int,int> tp ={1,2,3};

auto tp2 = std::make_tuple(1, 2.5, "hi"); // 自动推断类型

访问元素

  • 不能像 pair 一样访问，使用 std::get<0>(tuple)

    注意，这里 get要求 index 是常量，编译期可知的常量，因此不能利用它来遍历

1
2
3
int a = std::get<0>(tp);
int b = std::get<1>(tp);
int c = std::get<2>(tp);
  • c++17 起可以用结构化绑定,这样更优雅些
1
auto [a, b, c] = tuple;
  • 也可以使用 std::tie
1
2
int a, b, c;
std::tie(a, b, std::ignore) = tp;

修改

1
std::get<1>(t) = 6;

获取长度

1
2
// tuple 长度
constexpr size_t n = std::tuple_size<decltype(tp)>::value; // n=3

遍历

不常用，使用结构化绑定 + fold 表达式

1
2
3
4
5
6
7
auto tp = make_tuple(1, 2.5, "hi");

// fold expression 遍历
std::apply([](auto&&... args) {
    ((cout << args << " "), ...);
}, tp);

algorithm

引用头文件

1
#include <algorithm>

sort

基本用法

1
2
3
4
5
6
#include <functional> // std::greater<int>
vector<int> v={3,2,4};
// 按非递减顺序排序（升序）
std::sort(v.begin(), v.end());
// 按非递增顺序排序（降序）
std::sort(v.begin(), v.end(),std::greater<int>)

自定义比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct Person {
    string name;
    int age;
};

vector<Person> people = {{"Alice", 25}, {"Bob", 30}, {"Carol", 20}};

// 按年龄升序
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age < b.age;
});

// 按年龄降序
std::sort(people.begin(), people.end(), [](const Person &a, const Person &b){
    return a.age > b.age;
});

std::sort 的标准要求是 稳定性不保证，如果需要稳定排序请使用 std::stable_sort

  • 稳定排序：如果两个元素相等，排序前它们的相对顺序在排序后保持不变。
  • 不稳定排序：相等元素的相对顺序在排序后可能被打乱。

min, max

基本用法

1
2
3
4
int a = 5, b = 10;

int mi = std::min(a, b); // mi = 5
int ma = std::max(a, b); // ma = 10

自定义比较器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Person {
    std::string name;
    int age;
};

Person p1{"Alice", 25}, p2{"Bob", 30};

// 返回年龄小的
auto youngest = std::min(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

auto oldest = std::max(p1, p2, [](const Person &x, const Person &y){
    return x.age < y.age;
});

可接受 initializer_list (C++11 及以上)

1
2
int x = std::min({3, 1, 4, 2}); // x = 1
int y = std::max({3, 1, 4, 2}); // y = 4

min_element/max_element

min_element和max_element返回的迭代器

1
2
3
4
vector<int> v= {1,2,4,8};
// 查找最小/最大值
int mn = *std::min_element(v.begin(), v.end());
int mx = *std::max_element(v.begin(), v.end());

reverse

反转有序容器

1
2
vector<int> v = {1,2,4,8};
std::reverse(v.begin(), v.end());

find

  • 顺序查找区间内第一个等于给定值的元素，返回迭代器。找不到返回 end。
1
2
3
4
5
vector<int> v = {1, 3, 5, 7};
auto it = std::find(v.begin(), v.end(), 5); // it 指向 5
if(it != v.end()) {
    cout << "Found: " << *it << endl;
}

count

  • 统计区间内某个值出现的次数
1
2
vector<int> v = {1,2,2,3,2};
int cnt = std::count(v.begin(), v.end(), 2); // cnt = 3
  • 对已排序序列执行二分查找，返回 bool，判断是否存在
1
2
3
vector<int> v = {1,3,5,7};
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 5); // true

lower_bound/upper_bound

  • 返回迭代器，要求序列已排序
  • lower_bound(begin,end,val)：返回第一个 >= val 的位置
  • upper_bound(begin,end,val)：返回第一个 > val 的位置
1
2
3
4
5
6
vector<int> v = {1,2,2,3,5};
auto lb = std::lower_bound(v.begin(), v.end(), 2); // 指向第一个 2
auto ub = std::upper_bound(v.begin(), v.end(), 2); // 指向 3

int distance = std::distance(std::lower_bound(vec.begin(), vec.end(), startTime),
                         std::upper_bound(vec.begin(), vec.end(), endTime));

equal_range

  • 返回 [lower_bound, upper_bound) 的迭代器对，区间包含所有等于给定值的元素
1
2
3
4
auto range = std::equal_range(v.begin(), v.end(), 2);
for(auto it = range.first; it != range.second; ++it) {
    cout << *it << " "; // 输出所有 2
}

next_permutation/prev_permutation

生成下一个字典序排列，可以用于生成一个序列的全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // v是字典序列最小
    std::vector<int> v = {1, 2, 3};

    do {
        for (int x : v) std::cout << x << " ";
        std::cout << "\n";
    } while (std::next_permutation(v.begin(), v.end()));
}

输出：

1
2
3
4
5
6
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
  • 也用于生成一个数组的所有长度为m的数字组合
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2;
    int n = vec.size();

    // 初始化标记数组
    std::vector<int> select(n, 0);
    std::fill(select.end() - m, select.end(), 1); // 后 m 个为 1

    do {
        // 根据 select 生成组合
        for (int i = 0; i < n; ++i) {
            if (select[i]) std::cout << vec[i] << " ";
        }
        std::cout << "\n";
    } while (std::next_permutation(select.begin(), select.end()));
}

输出

1
2
3
4
5
6
1 2
1 3
2 3
1 4
2 4
3 4

也可以使用prev_permutation

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
#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    int m = 2; // 组合长度
    int n = vec.size();

    // 1. 创建选择标记数组
    std::vector<int> select(n, 0);
    std::fill(select.begin(), select.begin() + m, 1); // 前 m 个选中

    std::vector<std::vector<int>> result;

    // 2. 用 prev_permutation 生成所有组合
    do {
        std::vector<int> combo;
        for (int i = 0; i < n; ++i) {
            if (select[i]) combo.push_back(vec[i]);
        }
        result.push_back(combo);
    } while (std::prev_permutation(select.begin(), select.end()));

    // 输出
    for (auto& c : result) {
        for (auto x : c) std::cout << x << " ";
        std::cout << "\n";
    }
}

fill

  • fill(begin,end,val)：填充整个区间为指定值
1
2
3
4
5
6
vector<int> v(5);
std::fill(v.begin(), v.end(), 7); // v = {7,7,7,7,7}


std::vector<int> select(n, 0);
std::fill(select.begin(), select.begin() + m, 1);

iota

  • iota(begin,end,start)：生成连续整数序列
1
2
3
#include <numeric>
vector<int> v(5);
std::iota(v.begin(), v.end(), 10); // v = {10,11,12,13,14}

copy / swap / replace / remove / remove_if

  • copy(begin,end,out_it)：拷贝区间到另一容器
1
2
3
vector<int> src = {1,2,3};
vector<int> dst(3);
std::copy(src.begin(), src.end(), dst.begin());
  • swap(a,b) / iter_swap(it1,it2)：交换元素
1
2
std::swap(a,b);
std::iter_swap(v.begin(), v.begin()+1);
  • replace(begin,end,old_val,new_val)：替换区间内元素
1
std::replace(v.begin(), v.end(), 2, 5);
  • remove(begin,end,val) / remove_if(begin,end,pred)：逻辑移除（需要配合 erase）
1
2
v.erase(std::remove(v.begin(), v.end(), 5), v.end());
v.erase(std::remove_if(v.begin(), v.end(), [](int x){ return x%2==0; }), v.end());

set operations（集合操作）

  • 序列必须 已排序
  • merge(a,b,out)：合并两个已排序序列
  • set_union(a,b,out)：并集
  • set_intersection(a,b,out)：交集
  • set_difference(a,b,out)：差集
  • unique(begin,end)：去除相邻重复元素
1
2
3
4
5
6
7
8
vector<int> a = {1,2,2,3};
vector<int> b = {2,3,4};
vector<int> out;

std::set_union(a.begin(),a.end(),b.begin(),b.end(),std::back_inserter(out));
// out = {1,2,2,3,4}

a.erase(std::unique(a.begin(),a.end()), a.end()); // 去重 a = {1,2,3}

accumulate / all_of / any_of / none_of / for_each

  • accumulate(begin,end,init)：区间求和（或自定义操作）
1
2
3
#include <numeric>
vector<int> v = {1,2,3};
int sum = std::accumulate(v.begin(), v.end(), 0); // sum = 6
  • all_of(begin,end,pred) / any_of / none_of：判断区间元素是否满足条件
1
2
bool all_even = std::all_of(v.begin(), v.end(), [](int x){ return x%2==0; });
bool any_even = std::any_of(v.begin(), v.end(), [](int x){ return x%2==0; });
  • for_each(begin,end,f)：区间遍历
1
std::for_each(v.begin(), v.end(), [](int &x){ x++; });

时间复杂度

算法 功能 时间复杂度 示例代码
sort 排序（不稳定） O(n log n) std::sort(v.begin(), v.end());
stable_sort 稳定排序 O(n log² n) 最坏，平均 O(n log n) std::stable_sort(v.begin(), v.end());
min / max 两数取最小/最大 O(1) std::min(a,b); std::max(a,b);
min_element / max_element 区间最小/最大元素迭代器 O(n) *std::min_element(v.begin(), v.end());
reverse 反转区间 O(n) std::reverse(v.begin(), v.end());
find 顺序查找 O(n) auto it = std::find(v.begin(),v.end(),5);
count 统计出现次数 O(n) std::count(v.begin(),v.end(),2);
binary_search 是否存在（二分，需有序） O(log n) std::binary_search(v.begin(),v.end(),5);
lower_bound 第一个 >= val（二分） O(log n) auto it=std::lower_bound(v.begin(),v.end(),2);
upper_bound 第一个 > val（二分） O(log n) auto it=std::upper_bound(v.begin(),v.end(),2);
equal_range 返回等于 val 的区间 O(log n) auto r=std::equal_range(v.begin(),v.end(),2);
fill 区间赋值 O(n) std::fill(v.begin(), v.end(), 7);
iota 连续赋值（需 <numeric>） O(n) std::iota(v.begin(),v.end(),10);
copy 拷贝区间 O(n) std::copy(src.begin(),src.end(),dst.begin());
swap / iter_swap 交换元素 O(1) std::swap(a,b);
replace 替换指定值 O(n) std::replace(v.begin(),v.end(),2,5);
remove / remove_if 逻辑删除（需 erase） O(n) v.erase(std::remove(v.begin(),v.end(),5),v.end());
unique 去除相邻重复（逻辑删除） O(n) v.erase(std::unique(v.begin(),v.end()),v.end());
set_union 并集（需有序） O(n+m) std::set_union(a.begin(),a.end(),b.begin(),b.end(),back_inserter(out));
set_intersection 交集（需有序） O(n+m) std::set_intersection(...);
set_difference 差集（需有序） O(n+m) std::set_difference(...);
merge 合并两个有序序列 O(n+m) std::merge(a.begin(),a.end(),b.begin(),b.end(),out.begin());
accumulate 区间累加（需 <numeric>） O(n) int sum=std::accumulate(v.begin(),v.end(),0);
all_of / any_of / none_of 区间条件判断 O(n) std::all_of(v.begin(),v.end(),[](int x){return x%2==0;});
for_each 遍历执行函数 O(n) std::for_each(v.begin(),v.end(),[](int &x){x++;});

utility

引用头文件

1
#include <utility>

pair

引用头文件

1
2
#include <utility>
using std::pair;

构造

1
2
3
pair<int,int> p = {1,2};

auto p = std::make_pair(1, 2); // 自动推断类型

访问元素

1
2
int a = p.first;
int b = p.second;

std::move

std::move 其实是将参数 t 转换为一个右值引用类型，不会拷贝内存，不会释放资源，不会调用构造函数和析构函数

1
2
3
4
template <typename T>
typename std::remove_reference<T>::type&& move(T&& t) noexcept {
    return static_cast<typename std::remove_reference<T>::type&&>(t);
}

以 std::vector\ 为例：

1
2
std::vector<int> a = {1, 2, 3};
std::vector<int> b = std::move(a);

这里：std::move(a) 把 a 变成右值引用。编译器会选择 vector 的移动构造函数，而不是拷贝构造。
移动构造函数做的事：

  • 把 a 的内部指针直接“偷走”，交给 b。
  • 把 a 的指针设为空，避免析构时释放同一块内存。

所以最后：b 持有 {1,2,3} 的数据。a 变成空的（size()==0，但仍然是合法对象）

总结：
nums1 = std::move(vec);

  • 旧内容自动释放（移动赋值内部完成）
  • 新内容接管
  • vec 变空
    不需要自己手动调用析构函数。