第26章 标准模板库

C++20新特性：Ranges库

C++20引入了Ranges库，这是对STL的重大增强，提供了更简洁、更灵活的方式来处理序列：

Ranges的基本概念

  • Range：一个可以迭代的序列，包含开始和结束迭代器
  • View：对Range的非拥有视图，可以进行变换和过滤
  • Adapter：用于修改Range行为的组件
  • Algorithm：操作Range的算法

Ranges库的使用示例

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 使用views进行过滤和变换
    auto result = numbers | std::views::filter([](int n) { return n % 2 == 0; })  // 过滤偶数
                         | std::views::transform([](int n) { return n * n; })    // 平方
                         | std::views::take(3);                                  // 取前3个
    
    // 输出结果
    std::cout << "Filtered and transformed: ";
    for (int n : result) {
        std::cout << n << " ";  // 输出：4 16 36
    }
    std::cout << std::endl;
    
    // 使用ranges算法
    std::vector<int> sorted_numbers = numbers;
    std::ranges::sort(sorted_numbers);
    
    std::cout << "Sorted numbers: ";
    for (int n : sorted_numbers) {
        std::cout << n << " ";  // 输出：1 2 3 4 5 6 7 8 9 10
    }
    std::cout << std::endl;
    
    // 检查是否所有元素都满足条件
    bool all_positive = std::ranges::all_of(numbers, [](int n) { return n > 0; });
    std::cout << "All positive: " << std::boolalpha << all_positive << std::endl;  // true
    
    // 查找第一个满足条件的元素
    auto it = std::ranges::find_if(numbers, [](int n) { return n > 5; });
    if (it != numbers.end()) {
        std::cout << "First element > 5: " << *it << std::endl;  // 6
    }
    
    return 0;
}

Ranges库的优点

  1. 更简洁的语法：使用管道操作符（|）链式组合操作
  2. 惰性求值：views是惰性的，只在需要时计算
  3. 更好的组合性：可以轻松组合多个变换和过滤操作
  4. 类型推导：减少了显式类型声明的需要
  5. 与现有STL兼容：可以与传统的STL容器和算法一起使用

STL概述

标准模板库（Standard Template Library，STL）是C++标准库的重要组成部分，它提供了一系列的模板类和函数，用于实现常用的数据结构和算法。STL的设计理念是泛型编程，通过模板机制实现了与类型无关的代码。

STL的组成

STL主要由以下几个部分组成：

  1. 容器（Containers）：用于存储数据的对象
  2. 迭代器（Iterators）：用于遍历容器中的元素
  3. 算法（Algorithms）：用于操作容器中的元素
  4. 函数对象（Functors）：行为类似函数的对象
  5. 适配器（Adapters）：修改其他STL组件接口的组件
  6. 分配器（Allocators）：用于管理内存分配

STL的优势

  • 代码重用：STL提供了大量现成的组件，避免重复造轮子
  • 性能优化：STL的实现经过了精心优化，性能优异
  • 类型安全：通过模板机制，提供了类型安全的代码
  • 灵活性：STL的组件可以灵活组合，适应不同的需求
  • 标准统一：STL是C++标准的一部分，保证了跨平台兼容性

容器

容器是STL中用于存储数据的对象，根据存储方式和访问特性的不同，容器可以分为以下几类：

序列容器

序列容器按顺序存储元素，包括：

  • vector：动态数组，支持随机访问
  • list：双向链表，支持双向遍历
  • deque：双端队列，支持两端快速插入和删除
  • array：固定大小数组（C++11+）
  • forward_list：单向链表（C++11+）

vector

vector是最常用的序列容器，它提供了动态数组的功能，支持随机访问，尾部插入和删除操作效率高。

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

int main() {
    // 创建vector
    std::vector<int> vec;
    std::vector<int> vec2(5, 10); // 5个元素，每个都是10
    std::vector<int> vec3 = {1, 2, 3, 4, 5};
    
    // 添加元素
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    
    // 访问元素
    std::cout << "First element: " << vec[0] << std::endl;
    std::cout << "Second element: " << vec.at(1) << std::endl;
    std::cout << "Last element: " << vec.back() << std::endl;
    
    // 修改元素
    vec[0] = 10;
    
    // 删除元素
    vec.pop_back();
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (size_t i = 0; i < vec.size(); ++i) {
        std::cout << vec[i] << " ";
    }
    std::cout << std::endl;
    
    // 使用迭代器遍历
    std::cout << "Elements (iterator): " << std::endl;
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 容量相关
    std::cout << "Size: " << vec.size() << std::endl;
    std::cout << "Capacity: " << vec.capacity() << std::endl;
    std::cout << "Empty: " << (vec.empty() ? "Yes" : "No") << std::endl;
    
    // 预留空间
    vec.reserve(10);
    std::cout << "Capacity after reserve: " << vec.capacity() << std::endl;
    
    // 收缩空间
    vec.shrink_to_fit();
    std::cout << "Capacity after shrink_to_fit: " << vec.capacity() << std::endl;
    
    return 0;
}

list

list是双向链表，支持双向遍历，任意位置的插入和删除操作效率高，但不支持随机访问。

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
#include <list>
#include <iostream>

int main() {
    // 创建list
    std::list<int> lst;
    std::list<int> lst2(5, 10); // 5个元素，每个都是10
    std::list<int> lst3 = {1, 2, 3, 4, 5};
    
    // 添加元素
    lst.push_back(1);
    lst.push_back(2);
    lst.push_front(0);
    
    // 访问元素
    std::cout << "Front element: " << lst.front() << std::endl;
    std::cout << "Back element: " << lst.back() << std::endl;
    // 注意：list不支持[]操作符和at()方法
    
    // 修改元素
    lst.front() = 10;
    lst.back() = 20;
    
    // 删除元素
    lst.pop_front();
    lst.pop_back();
    
    // 插入元素
    auto it = lst.begin();
    ++it; // 移动到第二个位置
    lst.insert(it, 15);
    
    // 删除元素
    it = lst.begin();
    lst.erase(it);
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (int num : lst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    std::cout << "Size: " << lst.size() << std::endl;
    std::cout << "Empty: " << (lst.empty() ? "Yes" : "No") << std::endl;
    
    // 排序
    lst.sort();
    
    // 反转
    lst.reverse();
    
    // 合并
    std::list<int> lst4 = {6, 7, 8};
    lst.merge(lst4);
    
    return 0;
}

deque

deque是双端队列，支持两端快速插入和删除操作，也支持随机访问。

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
#include <deque>
#include <iostream>

int main() {
    // 创建deque
    std::deque<int> dq;
    std::deque<int> dq2(5, 10); // 5个元素，每个都是10
    std::deque<int> dq3 = {1, 2, 3, 4, 5};
    
    // 添加元素
    dq.push_back(1);
    dq.push_back(2);
    dq.push_front(0);
    
    // 访问元素
    std::cout << "First element: " << dq[0] << std::endl;
    std::cout << "Second element: " << dq.at(1) << std::endl;
    std::cout << "Front element: " << dq.front() << std::endl;
    std::cout << "Back element: " << dq.back() << std::endl;
    
    // 修改元素
    dq[0] = 10;
    
    // 删除元素
    dq.pop_front();
    dq.pop_back();
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (size_t i = 0; i < dq.size(); ++i) {
        std::cout << dq[i] << " ";
    }
    std::cout << std::endl;
    
    // 使用迭代器遍历
    std::cout << "Elements (iterator): " << std::endl;
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    std::cout << "Size: " << dq.size() << std::endl;
    std::cout << "Empty: " << (dq.empty() ? "Yes" : "No") << std::endl;
    
    return 0;
}

array

array是固定大小的数组（C++11+），支持随机访问，大小在编译时确定。

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
#include <array>
#include <iostream>

int main() {
    // 创建array
    std::array<int, 5> arr;
    std::array<int, 5> arr2 = {1, 2, 3, 4, 5};
    std::array<int, 5> arr3 = {1, 2}; // 剩余元素初始化为0
    
    // 访问元素
    arr[0] = 10;
    arr[1] = 20;
    std::cout << "First element: " << arr[0] << std::endl;
    std::cout << "Second element: " << arr.at(1) << std::endl;
    std::cout << "Front element: " << arr.front() << std::endl;
    std::cout << "Back element: " << arr.back() << std::endl;
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (size_t i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    
    // 使用迭代器遍历
    std::cout << "Elements (iterator): " << std::endl;
    for (auto it = arr.begin(); it != arr.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    std::cout << "Size: " << arr.size() << std::endl;
    std::cout << "Max size: " << arr.max_size() << std::endl;
    std::cout << "Empty: " << (arr.empty() ? "Yes" : "No") << std::endl;
    
    // 填充
    arr.fill(5);
    
    // 交换
    arr.swap(arr2);
    
    return 0;
}

forward_list

forward_list是单向链表（C++11+），支持单向遍历，任意位置的插入和删除操作效率高，但不支持双向遍历和随机访问。

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
#include <forward_list>
#include <iostream>

int main() {
    // 创建forward_list
    std::forward_list<int> flst;
    std::forward_list<int> flst2(5, 10); // 5个元素，每个都是10
    std::forward_list<int> flst3 = {1, 2, 3, 4, 5};
    
    // 添加元素
    flst.push_front(1);
    flst.push_front(0);
    
    // 访问元素
    std::cout << "Front element: " << flst.front() << std::endl;
    // 注意：forward_list不支持back()方法
    
    // 修改元素
    flst.front() = 10;
    
    // 删除元素
    flst.pop_front();
    
    // 插入元素
    auto it = flst.begin();
    flst.insert_after(it, 15);
    
    // 删除元素
    it = flst.begin();
    flst.erase_after(it);
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = flst.begin(); it != flst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (int num : flst) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    // 注意：forward_list没有size()方法
    std::cout << "Empty: " << (flst.empty() ? "Yes" : "No") << std::endl;
    
    // 排序
    flst.sort();
    
    // 反转
    flst.reverse();
    
    // 合并
    std::forward_list<int> flst4 = {6, 7, 8};
    flst.merge(flst4);
    
    return 0;
}

关联容器

关联容器按键存储元素，包括：

  • set：有序集合，键唯一
  • multiset：有序集合，键可重复
  • map：有序映射，键值对，键唯一
  • multimap：有序映射，键值对，键可重复

set

set是有序集合，存储唯一的键，按照升序排列。

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
#include <set>
#include <iostream>

int main() {
    // 创建set
    std::set<int> s;
    std::set<int> s2 = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 添加元素
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(2); // 重复元素，不会插入
    
    // 查找元素
    auto it = s.find(2);
    if (it != s.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // 删除元素
    s.erase(2);
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (int num : s) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    std::cout << "Size: " << s.size() << std::endl;
    std::cout << "Empty: " << (s.empty() ? "Yes" : "No") << std::endl;
    
    // 计数
    std::cout << "Count of 1: " << s.count(1) << std::endl;
    
    return 0;
}

map

map是有序映射，存储键值对，键唯一，按照键的升序排列。

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
#include <map>
#include <iostream>

int main() {
    // 创建map
    std::map<std::string, int> m;
    std::map<std::string, int> m2 = {{"one", 1}, {"two", 2}, {"three", 3}};
    
    // 添加元素
    m["one"] = 1;
    m["two"] = 2;
    m.insert({"three", 3});
    
    // 查找元素
    auto it = m.find("two");
    if (it != m.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // 删除元素
    m.erase("two");
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = m.begin(); it != m.end(); ++it) {
        std::cout << it->first << " -> " << it->second << std::endl;
    }
    
    // 使用范围for循环
    std::cout << "Elements (range-based): " << std::endl;
    for (const auto& pair : m) {
        std::cout << pair.first << " -> " << pair.second << std::endl;
    }
    
    // 大小相关
    std::cout << "Size: " << m.size() << std::endl;
    std::cout << "Empty: " << (m.empty() ? "Yes" : "No") << std::endl;
    
    // 计数
    std::cout << "Count of 'one': " << m.count("one") << std::endl;
    
    return 0;
}

无序容器

无序容器（C++11+）使用哈希表实现，包括：

  • unordered_set：无序集合，键唯一
  • unordered_multiset：无序集合，键可重复
  • unordered_map：无序映射，键值对，键唯一
  • unordered_multimap：无序映射，键值对，键可重复

unordered_set

unordered_set是无序集合，存储唯一的键，使用哈希表实现，查找效率高。

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
#include <unordered_set>
#include <iostream>

int main() {
    // 创建unordered_set
    std::unordered_set<int> us;
    std::unordered_set<int> us2 = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // 添加元素
    us.insert(1);
    us.insert(2);
    us.insert(3);
    us.insert(2); // 重复元素，不会插入
    
    // 查找元素
    auto it = us.find(2);
    if (it != us.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // 删除元素
    us.erase(2);
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = us.begin(); it != us.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 大小相关
    std::cout << "Size: " << us.size() << std::endl;
    std::cout << "Empty: " << (us.empty() ? "Yes" : "No") << std::endl;
    
    // 桶相关
    std::cout << "Bucket count: " << us.bucket_count() << std::endl;
    std::cout << "Load factor: " << us.load_factor() << std::endl;
    
    return 0;
}

unordered_map

unordered_map是无序映射，存储键值对，键唯一，使用哈希表实现，查找效率高。

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
#include <unordered_map>
#include <iostream>

int main() {
    // 创建unordered_map
    std::unordered_map<std::string, int> um;
    std::unordered_map<std::string, int> um2 = {{"one", 1}, {"two", 2}, {"three", 3}};
    
    // 添加元素
    um["one"] = 1;
    um["two"] = 2;
    um.insert({"three", 3});
    
    // 查找元素
    auto it = um.find("two");
    if (it != um.end()) {
        std::cout << "Found: " << it->first << " -> " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
    
    // 删除元素
    um.erase("two");
    
    // 遍历元素
    std::cout << "Elements: " << std::endl;
    for (auto it = um.begin(); it != um.end(); ++it) {
        std::cout << it->first << " -> " << it->second << std::endl;
    }
    
    // 大小相关
    std::cout << "Size: " << um.size() << std::endl;
    std::cout << "Empty: " << (um.empty() ? "Yes" : "No") << std::endl;
    
    // 桶相关
    std::cout << "Bucket count: " << um.bucket_count() << std::endl;
    std::cout << "Load factor: " << um.load_factor() << std::endl;
    
    return 0;
}

容器适配器

容器适配器是修改其他容器接口的组件，包括：

  • stack：栈，后进先出（LIFO）
  • queue：队列，先进先出（FIFO）
  • priority_queue：优先队列，最高优先级元素先出

stack

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
#include <stack>
#include <iostream>

int main() {
    // 创建stack
    std::stack<int> s;
    
    // 添加元素
    s.push(1);
    s.push(2);
    s.push(3);
    
    // 访问元素
    std::cout << "Top element: " << s.top() << std::endl;
    
    // 删除元素
    s.pop();
    std::cout << "Top element after pop: " << s.top() << std::endl;
    
    // 大小相关
    std::cout << "Size: " << s.size() << std::endl;
    std::cout << "Empty: " << (s.empty() ? "Yes" : "No") << std::endl;
    
    return 0;
}

queue

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
#include <queue>
#include <iostream>

int main() {
    // 创建queue
    std::queue<int> q;
    
    // 添加元素
    q.push(1);
    q.push(2);
    q.push(3);
    
    // 访问元素
    std::cout << "Front element: " << q.front() << std::endl;
    std::cout << "Back element: " << q.back() << std::endl;
    
    // 删除元素
    q.pop();
    std::cout << "Front element after pop: " << q.front() << std::endl;
    
    // 大小相关
    std::cout << "Size: " << q.size() << std::endl;
    std::cout << "Empty: " << (q.empty() ? "Yes" : "No") << std::endl;
    
    return 0;
}

priority_queue

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
#include <queue>
#include <iostream>

int main() {
    // 创建priority_queue（默认最大堆）
    std::priority_queue<int> pq;
    
    // 添加元素
    pq.push(3);
    pq.push(1);
    pq.push(5);
    pq.push(2);
    
    // 访问元素
    std::cout << "Top element: " << pq.top() << std::endl; // 最大的元素
    
    // 删除元素
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl;
    
    // 大小相关
    std::cout << "Size: " << pq.size() << std::endl;
    std::cout << "Empty: " << (pq.empty() ? "Yes" : "No") << std::endl;
    
    // 创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
    min_pq.push(3);
    min_pq.push(1);
    min_pq.push(5);
    std::cout << "Top element (min heap): " << min_pq.top() << std::endl; // 最小的元素
    
    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
56
57
58
59
60
61
#include <vector>
#include <list>
#include <iostream>

int main() {
    // vector 支持随机访问迭代器
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::cout << "Vector: " << std::endl;
    
    // 正向迭代器
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 反向迭代器
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 常量迭代器
    std::cout << "Constant iteration: " << std::endl;
    for (auto it = vec.cbegin(); it != vec.cend(); ++it) {
        std::cout << *it << " ";
        // *it = 10; // 错误：常量迭代器不能修改元素
    }
    std::cout << std::endl;
    
    // 随机访问
    std::cout << "Third element: " << *(vec.begin() + 2) << std::endl;
    std::cout << "Using []: " << vec[2] << std::endl;
    
    // list 支持双向迭代器
    std::list<int> lst = {1, 2, 3, 4, 5};
    std::cout << "List: " << std::endl;
    
    // 正向迭代器
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 反向迭代器
    for (auto it = lst.rbegin(); it != lst.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 双向移动
    auto it = lst.begin();
    ++it; // 移动到第二个元素
    std::cout << "Second element: " << *it << std::endl;
    --it; // 移动回第一个元素
    std::cout << "First element: " << *it << std::endl;
    
    // 注意：list的迭代器不支持随机访问
    // std::cout << *(it + 2) << std::endl; // 错误
    
    return 0;
}

迭代器失效

在修改容器时，需要注意迭代器可能会失效，即迭代器不再指向有效的元素。不同容器的迭代器失效情况不同：

  • vector：当添加元素导致重新分配内存时，所有迭代器失效；在中间插入或删除元素时，插入/删除点之后的迭代器失效。
  • list：插入元素时，所有迭代器都有效；删除元素时，只有被删除元素的迭代器失效。
  • deque：在两端插入元素时，迭代器可能失效；在中间插入或删除元素时，所有迭代器失效。
  • 关联容器：插入元素时，所有迭代器都有效；删除元素时，只有被删除元素的迭代器失效。
  • 无序容器：插入元素时，如果发生重新哈希，所有迭代器失效；删除元素时，只有被删除元素的迭代器失效。
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
#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // 错误：迭代器失效
    std::cout << "错误示例：" << std::endl;
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        if (*it == 3) {
            vec.erase(it); // 迭代器it失效
            // 后续的++it操作会导致未定义行为
        }
    }
    
    // 正确：使用erase的返回值
    vec = {1, 2, 3, 4, 5};
    std::cout << "正确示例：" << std::endl;
    for (auto it = vec.begin(); it != vec.end();) {
        if (*it == 3) {
            it = vec.erase(it); // erase返回下一个有效的迭代器
        } else {
            ++it;
        }
    }
    
    // 输出结果
    std::cout << "Result: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

算法

STL提供了大量的算法，用于操作容器中的元素。这些算法定义在<algorithm>头文件中，大部分算法都是通过迭代器来操作容器的，因此可以适用于不同类型的容器。

常用算法

查找算法

  • find：查找第一个等于给定值的元素
  • find_if：查找第一个满足给定条件的元素
  • find_if_not：查找第一个不满足给定条件的元素
  • count：统计等于给定值的元素个数
  • count_if：统计满足给定条件的元素个数
  • search：查找子序列
  • binary_search：二分查找（要求容器已排序）
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
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // find
    auto it = std::find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        std::cout << "Found 5 at position: " << std::distance(vec.begin(), it) << std::endl;
    }
    
    // find_if
    it = std::find_if(vec.begin(), vec.end(), [](int x) { return x > 5; });
    if (it != vec.end()) {
        std::cout << "First element > 5: " << *it << " at position: " << std::distance(vec.begin(), it) << std::endl;
    }
    
    // count
    int cnt = std::count(vec.begin(), vec.end(), 5);
    std::cout << "Count of 5: " << cnt << std::endl;
    
    // count_if
    cnt = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
    std::cout << "Count of even numbers: " << cnt << std::endl;
    
    // binary_search (需要先排序)
    std::sort(vec.begin(), vec.end());
    bool found = std::binary_search(vec.begin(), vec.end(), 5);
    std::cout << "5 found in sorted vector: " << (found ? "Yes" : "No") << std::endl;
    
    return 0;
}

排序算法

  • sort：排序
  • stable_sort：稳定排序
  • partial_sort：部分排序
  • nth_element：找到第n大的元素
  • merge：合并两个已排序的范围
  • reverse：反转
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
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // sort
    std::sort(vec.begin(), vec.end());
    std::cout << "Sorted: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // reverse
    std::reverse(vec.begin(), vec.end());
    std::cout << "Reversed: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // sort with custom comparator
    std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });
    std::cout << "Sorted in descending order: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

修改算法

  • copy：复制元素
  • move：移动元素
  • fill：填充元素
  • replace：替换元素
  • swap：交换元素
  • transform：转换元素
  • remove：移除元素
  • unique：移除重复元素
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
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    std::vector<int> dest(vec.size());
    
    // copy
    std::copy(vec.begin(), vec.end(), dest.begin());
    std::cout << "Copied: " << std::endl;
    for (int num : dest) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // fill
    std::fill(dest.begin(), dest.end(), 0);
    std::cout << "Filled with 0: " << std::endl;
    for (int num : dest) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // replace
    std::replace(vec.begin(), vec.end(), 5, 50);
    std::cout << "After replacing 5 with 50: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // transform
    std::transform(vec.begin(), vec.end(), dest.begin(), [](int x) { return x * 2; });
    std::cout << "After doubling: " << std::endl;
    for (int num : dest) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // remove (需要配合erase使用)
    auto new_end = std::remove(vec.begin(), vec.end(), 50);
    vec.erase(new_end, vec.end());
    std::cout << "After removing 50: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // unique (需要先排序)
    std::sort(vec.begin(), vec.end());
    new_end = std::unique(vec.begin(), vec.end());
    vec.erase(new_end, vec.end());
    std::cout << "After removing duplicates: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

关系算法

  • equal：判断两个范围是否相等
  • lexicographical_compare：字典序比较
  • max：最大值
  • min：最小值
  • max_element：最大元素
  • min_element：最小元素
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 <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {1, 2, 3, 4, 5};
    std::vector<int> vec3 = {1, 2, 3, 4, 6};
    
    // equal
    bool is_equal = std::equal(vec1.begin(), vec1.end(), vec2.begin());
    std::cout << "vec1 == vec2: " << (is_equal ? "Yes" : "No") << std::endl;
    
    is_equal = std::equal(vec1.begin(), vec1.end(), vec3.begin());
    std::cout << "vec1 == vec3: " << (is_equal ? "Yes" : "No") << std::endl;
    
    // lexicographical_compare
    bool is_less = std::lexicographical_compare(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
    std::cout << "vec1 < vec3: " << (is_less ? "Yes" : "No") << std::endl;
    
    // max_element
    auto max_it = std::max_element(vec3.begin(), vec3.end());
    std::cout << "Max element in vec3: " << *max_it << std::endl;
    
    // min_element
    auto min_it = std::min_element(vec3.begin(), vec3.end());
    std::cout << "Min element in vec3: " << *min_it << std::endl;
    
    return 0;
}

数值算法

  • accumulate：累加
  • inner_product：内积
  • adjacent_difference：相邻元素的差
  • partial_sum：部分和
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
#include <vector>
#include <numeric>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    
    // accumulate
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "Sum: " << sum << std::endl;
    
    // accumulate with custom operation
    int product = std::accumulate(vec.begin(), vec.end(), 1, [](int a, int b) { return a * b; });
    std::cout << "Product: " << product << std::endl;
    
    // inner_product
    std::vector<int> vec2 = {6, 7, 8, 9, 10};
    int inner_prod = std::inner_product(vec.begin(), vec.end(), vec2.begin(), 0);
    std::cout << "Inner product: " << inner_prod << std::endl;
    
    // adjacent_difference
    std::vector<int> diff(vec.size());
    std::adjacent_difference(vec.begin(), vec.end(), diff.begin());
    std::cout << "Adjacent differences: " << std::endl;
    for (int num : diff) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // partial_sum
    std::vector<int> partial(vec.size());
    std::partial_sum(vec.begin(), vec.end(), partial.begin());
    std::cout << "Partial sums: " << std::endl;
    for (int num : partial) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

函数对象

函数对象是重载了函数调用运算符()的类的实例，也称为仿函数（functor）。函数对象可以像函数一样被调用，同时还可以存储状态。

函数对象的定义和使用

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

// 函数对象
class GreaterThan {
private:
    int value;

public:
    GreaterThan(int v) : value(v) {}
    
    bool operator()(int num) const {
        return num > value;
    }
};

class Add {
private:
    int value;

public:
    Add(int v) : value(v) {}
    
    int operator()(int num) const {
        return num + value;
    }
};

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 使用函数对象作为谓词
    int threshold = 5;
    GreaterThan gt(threshold);
    int count = std::count_if(vec.begin(), vec.end(), gt);
    std::cout << "Count of elements greater than " << threshold << ": " << count << std::endl;
    
    // 使用函数对象作为转换操作
    Add add5(5);
    std::vector<int> result(vec.size());
    std::transform(vec.begin(), vec.end(), result.begin(), add5);
    std::cout << "After adding 5: " << std::endl;
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用lambda表达式（C++11+）
    count = std::count_if(vec.begin(), vec.end(), [threshold](int num) { return num > threshold; });
    std::cout << "Count using lambda: " << count << std::endl;
    
    std::transform(vec.begin(), vec.end(), result.begin(), [](int num) { return num + 5; });
    std::cout << "After adding 5 using lambda: " << std::endl;
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

标准函数对象

STL提供了一系列标准函数对象，定义在<functional>头文件中：

  • 算术运算：plus, minus, multiplies, divides, modulus, negate
  • 比较运算：equal_to, not_equal_to, greater, greater_equal, less, less_equal
  • 逻辑运算：logical_and, logical_or, logical_not
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
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 使用标准函数对象排序（降序）
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    std::cout << "Sorted in descending order: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用标准函数对象进行转换
    std::vector<int> result(vec.size());
    std::transform(vec.begin(), vec.end(), result.begin(), std::bind(std::multiplies<int>(), std::placeholders::_1, 2));
    std::cout << "After multiplying by 2: " << std::endl;
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

Lambda表达式（C++11+）

Lambda表达式是C++11引入的匿名函数对象，提供了一种简洁的方式来定义函数对象。

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

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 基本lambda表达式
    auto add = [](int a, int b) { return a + b; };
    std::cout << "5 + 3 = " << add(5, 3) << std::endl;
    
    // 带捕获的lambda
    int x = 10;
    auto addX = [x](int a) { return a + x; };
    std::cout << "5 + x = " << addX(5) << std::endl;
    
    // 引用捕获
    auto addXRef = [&x](int a) { return a + x; };
    
    // 捕获所有变量
    auto addAll = [=](int a) { return a + x; };
    
    // 可变lambda
    auto increment = [x]() mutable { return ++x; };
    
    // lambda作为谓词
    std::sort(vec.begin(), vec.end(), [](int a, int b) { return a > b; });
    std::cout << "Sorted in descending order: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // lambda作为转换操作
    std::vector<int> result(vec.size());
    std::transform(vec.begin(), vec.end(), result.begin(), [](int num) { return num * 2; });
    std::cout << "After doubling: " << std::endl;
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

适配器

适配器是修改其他STL组件接口的组件，包括容器适配器、迭代器适配器和函数适配器。

容器适配器

容器适配器修改容器的接口，提供不同的使用方式，包括：

  • stack：栈，后进先出（LIFO）
  • queue：队列，先进先出（FIFO）
  • priority_queue：优先队列，最高优先级元素先出

迭代器适配器

迭代器适配器修改迭代器的行为，包括：

  • reverse_iterator：反向迭代器
  • insert_iterator：插入迭代器
  • ostream_iterator：输出流迭代器
  • istream_iterator：输入流迭代器
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
#include <vector>
#include <iterator>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::vector<int> dest;
    
    // 使用插入迭代器
    std::copy(vec.begin(), vec.end(), std::back_inserter(dest));
    std::cout << "Using back_inserter: " << std::endl;
    for (int num : dest) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用输出流迭代器
    std::cout << "Using ostream_iterator: " << std::endl;
    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    
    // 使用输入流迭代器
    std::cout << "Enter numbers (Ctrl+D to end): " << std::endl;
    std::vector<int> input;
    std::copy(std::istream_iterator<int>(std::cin), std::istream_iterator<int>(), std::back_inserter(input));
    std::cout << "You entered: " << std::endl;
    std::copy(input.begin(), input.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    
    return 0;
}

函数适配器

函数适配器修改函数对象的行为，包括：

  • bind：绑定函数参数（C++11+）
  • not1, not2：取反一元和二元谓词
  • mem_fun, mem_fun_ref：将成员函数转换为函数对象
  • ptr_fun：将普通函数转换为函数对象
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
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>

int add(int a, int b) {
    return a + b;
}

bool isEven(int num) {
    return num % 2 == 0;
}

class MyClass {
private:
    int value;

public:
    MyClass(int v) : value(v) {}
    
    bool isGreaterThan(int v) const {
        return value > v;
    }
    
    int getValue() const {
        return value;
    }
};

int main() {
    std::vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 使用bind
    auto add5 = std::bind(add, std::placeholders::_1, 5);
    std::vector<int> result(vec.size());
    std::transform(vec.begin(), vec.end(), result.begin(), add5);
    std::cout << "After adding 5: " << std::endl;
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用not1
    int count = std::count_if(vec.begin(), vec.end(), std::not1(std::ptr_fun(isEven)));
    std::cout << "Count of odd numbers: " << count << std::endl;
    
    // 使用mem_fun_ref
    std::vector<MyClass> objs = {MyClass(1), MyClass(2), MyClass(3), MyClass(4), MyClass(5)};
    std::vector<int> values(objs.size());
    std::transform(objs.begin(), objs.end(), values.begin(), std::mem_fun_ref(&MyClass::getValue));
    std::cout << "Values: " << std::endl;
    for (int num : values) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用bind与成员函数
    count = std::count_if(objs.begin(), objs.end(), std::bind(&MyClass::isGreaterThan, std::placeholders::_1, 3));
    std::cout << "Count of objects with value > 3: " << count << std::endl;
    
    return 0;
}

分配器

分配器是STL中用于管理内存分配的组件，它负责容器的内存分配和释放。默认情况下，STL容器使用std::allocator作为分配器。

自定义分配器

虽然STL提供了默认的分配器，但在某些情况下，可能需要自定义分配器以满足特定的需求，例如：

  • 内存池分配
  • 共享内存分配
  • 调试内存分配
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
#include <vector>
#include <iostream>

// 简单的自定义分配器模板
 template <typename T>
 class MyAllocator {
 public:
     using value_type = T;
     
     MyAllocator() = default;
     
     template <typename U>
     MyAllocator(const MyAllocator<U>&) noexcept {
     }
     
     T* allocate(std::size_t n) {
         std::cout << "Allocating " << n * sizeof(T) << " bytes" << std::endl;
         return static_cast<T*>(std::malloc(n * sizeof(T)));
     }
     
     void deallocate(T* p, std::size_t n) noexcept {
         std::cout << "Deallocating " << n * sizeof(T) << " bytes" << std::endl;
         std::free(p);
     }
 };
 
 template <typename T, typename U>
 bool operator==(const MyAllocator<T>&, const MyAllocator<U>&) noexcept {
     return true;
 }
 
 template <typename T, typename U>
 bool operator!=(const MyAllocator<T>&, const MyAllocator<U>&) noexcept {
     return false;
 }

int main() {
    // 使用自定义分配器
    std::vector<int, MyAllocator<int>> vec;
    
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    
    std::cout << "Vector elements: " << std::endl;
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

最佳实践

1. 容器选择

场景推荐容器原因
随机访问频繁vector随机访问时间复杂度O(1)
插入删除频繁list插入删除时间复杂度O(1)
两端插入删除deque两端操作时间复杂度O(1)
固定大小数组array编译期大小，更高效
查找频繁（有序）set/map查找时间复杂度O(log n)
查找频繁（无序）unordered_set/unordered_map平均查找时间复杂度O(1)
栈操作stack后进先出
队列操作queue先进先出
优先队列priority_queue最高优先级元素先出

2. 迭代器使用

  • 使用auto：使用auto推导迭代器类型，提高代码可读性
  • 注意迭代器失效：在修改容器时，注意迭代器可能失效
  • 优先使用范围for：对于简单遍历，使用范围for循环
  • 使用const迭代器：对于只读操作，使用const迭代器
  • 选择合适的迭代器类型：根据容器类型选择合适的迭代器

3. 算法使用

  • 了解算法的时间复杂度：选择合适的算法
  • 使用合适的谓词：根据需要使用函数对象或lambda表达式
  • 注意算法的要求：不同算法对迭代器类型有不同要求
  • 优先使用STL算法：避免手写循环，提高代码可读性和效率
  • 使用正确的算法：根据具体需求选择正确的算法

4. 函数对象和Lambda

  • 对于复杂逻辑：使用函数对象，提高代码可读性
  • 对于简单逻辑：使用Lambda表达式，简化代码
  • 注意捕获列表：避免不必要的捕获，防止变量生命周期问题
  • 使用mutable：需要修改捕获变量时，使用mutable关键字
  • 考虑性能：对于频繁调用的场景，函数对象可能比Lambda更高效

5. 内存管理

  • 使用reserve：对于vector等容器，使用reserve预分配空间
  • 避免不必要的拷贝：使用移动语义和引用传递
  • 使用智能指针：管理动态内存，避免内存泄漏
  • 考虑自定义分配器：在特殊场景下，使用自定义分配器提高性能

常见错误和陷阱

1. 容器使用错误

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
// 错误：使用错误的容器
// 需要频繁查找时使用vector
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = std::find(vec.begin(), vec.end(), 5); // 时间复杂度O(n)

// 正确：使用set
std::set<int> s = {1, 2, 3, 4, 5};
auto it = s.find(5); // 时间复杂度O(log n)

// 错误：在遍历过程中修改vector
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it); // 错误：迭代器失效
    }
}

// 正确：使用erase的返回值
for (auto it = vec.begin(); it != vec.end();) {
    if (*it == 3) {
        it = vec.erase(it);
    } else {
        ++it;
    }
}

// 错误：vector的容量管理
std::vector<int> vec;
for (int i = 0; i < 1000000; ++i) {
    vec.push_back(i); // 可能导致多次重新分配
}

// 正确：预分配空间
std::vector<int> vec;
vec.reserve(1000000);
for (int i = 0; i < 1000000; ++i) {
    vec.push_back(i); // 避免重新分配
}

2. 迭代器错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 错误：使用已失效的迭代器
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
vec.push_back(6); // 可能导致迭代器失效
std::cout << *it << std::endl; // 未定义行为

// 正确：重新获取迭代器
std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
vec.push_back(6);
it = vec.begin(); // 重新获取
std::cout << *it << std::endl;

// 错误：使用错误的迭代器类型
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::cout << *(it + 2) << std::endl; // 错误：list的迭代器不支持随机访问

// 正确：使用循环移动迭代器
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // 移动2个位置
std::cout << *it << std::endl;

3. 算法使用错误

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
// 错误：使用不匹配的算法
std::list<int> lst = {5, 2, 8, 1, 9};
std::sort(lst.begin(), lst.end()); // 错误：list的迭代器不支持随机访问

// 正确：使用list的成员函数
lst.sort();

// 错误：未提供足够的空间
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst;
std::copy(src.begin(), src.end(), dst.begin()); // 错误：dst为空

// 正确：使用back_inserter
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// 或预分配空间
dst.resize(src.size());
std::copy(src.begin(), src.end(), dst.begin());

// 错误：使用remove后未使用erase
std::vector<int> vec = {1, 2, 3, 4, 5};
std::remove(vec.begin(), vec.end(), 3); // 只是移动元素，没有删除
std::cout << "Size: " << vec.size() << std::endl; // 大小仍然是5

// 正确：使用erase
auto new_end = std::remove(vec.begin(), vec.end(), 3);
vec.erase(new_end, vec.end());
std::cout << "Size: " << vec.size() << std::endl; // 大小变为4

4. 函数对象和Lambda错误

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
// 错误：Lambda捕获悬空引用
int* ptr = new int(42);
auto lambda = [&]() { std::cout << *ptr << std::endl; };
delete ptr;
lambda(); // 未定义行为：引用已释放的内存

// 正确：捕获指针或值
int* ptr = new int(42);
auto lambda = [ptr]() { std::cout << *ptr << std::endl; };
lambda();
delete ptr;

// 错误：函数对象缺少const
class GreaterThan {
private:
    int value;

public:
    GreaterThan(int v) : value(v) {}
    
    bool operator()(int num) { // 错误：缺少const
        return num > value;
    }
};

// 正确：添加const
class GreaterThan {
private:
    int value;

public:
    GreaterThan(int v) : value(v) {}
    
    bool operator()(int num) const { // 正确：添加const
        return num > value;
    }
};

小结

本章详细介绍了C++标准模板库（STL），包括：

  1. STL概述：STL的组成、优势和设计理念
  2. 容器：序列容器、关联容器、无序容器和容器适配器
  3. 迭代器：迭代器类型、使用方法和迭代器失效问题
  4. 算法：查找算法、排序算法、修改算法、关系算法和数值算法
  5. 函数对象：函数对象的定义、使用和标准函数对象
  6. Lambda表达式：C++11引入的匿名函数对象
  7. 适配器：容器适配器、迭代器适配器和函数适配器
  8. 分配器：内存分配管理和自定义分配器
  9. 最佳实践：容器选择、迭代器使用、算法使用、函数对象和Lambda使用、内存管理
  10. 常见错误和陷阱：容器使用错误、迭代器错误、算法使用错误、函数对象和Lambda错误

STL是C++标准库的重要组成部分，它提供了丰富的组件和工具，大大提高了编程效率和代码质量。掌握STL的使用对于成为一名优秀的C++程序员至关重要。在实际编程中，应根据具体情况选择合适的STL组件，遵循最佳实践，避免常见错误，以充分发挥STL的优势。

通过本章的学习，读者应该对STL有了全面的了解，能够在实际编程中灵活使用STL的各种组件，编写高效、优雅的C++代码。