STL模版

# 第 16 章 C++ STL 模板

# 目录介绍

16.1 函数模版
16.2 类模版
16.3 STL标准库模版
16.4 STL算法模版
16.5 STL迭代器
16.6 STL适配器
16.7 STL函数对象
16.8 模板与STL底层原理
16.9 模板与STL训练题
16.10 综合思考题

# 16.1 函数模版

在 C++ 中，函数模板是一种通用函数定义，允许你编写可以处理多种数据类型的函数。通过使用模板，你可以避免为每种数据类型编写重复的代码，从而提高代码的复用性和可维护性。

# 16.1.1 函数模版概念

模板就是建立通用的模具，大大提高复用性。

模板的特点：

模板不可以直接使用，它只是一个框架
模板的通用并不是万能的

C++另一种编程思想称为 ==泛型编程== ，主要利用的技术就是模板

C++提供两种模板机制: 函数模板和类模板

# 16.1.2 函数模板语法

函数模板的定义使用 template 关键字，后跟模板参数列表。模板参数可以是类型参数（如 typename T）或非类型参数（如 int N）。

语法

template <typename T>
返回类型 函数名(参数列表) {
    // 函数体
}

1
2
3
4

template --- 声明创建模板
typename --- 表面其后面的符号是一种数据类型，可以用class代替
T --- 通用的数据类型，名称可以替换，通常为大写字母

# 16.1.3 函数模板示例

示例 1：交换两个值

#include <iostream>

// 定义函数模板
template <typename T>
void swap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

int main() {
    int x = 10, y = 20;
    std::cout << "Before swap: x = " << x << ", y = " << y << std::endl;
    swap(x, y); // 调用模板函数
    std::cout << "After swap: x = " << x << ", y = " << y << std::endl;

    double a = 1.5, b = 2.5;
    std::cout << "Before swap: a = " << a << ", b = " << b << std::endl;
    swap(a, b); // 调用模板函数
    std::cout << "After swap: a = " << a << ", b = " << b << 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

示例 2：返回最大值

#include <iostream>

// 定义函数模板
template <typename T>
T max(T a, T b) {
    return (a > b) ? a : b;
}

int main() {
    int x = 10, y = 20;
    std::cout << "Max of " << x << " and " << y << " is " << max(x, y) << std::endl;

    double a = 1.5, b = 2.5;
    std::cout << "Max of " << a << " and " << b << " is " << max(a, b) << std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结：

函数模板利用关键字 template
使用函数模板有两种方式：自动类型推导、显示指定类型
模板的目的是为了提高复用性，将类型参数化

# 16.1.4 多类型参数函数模板

函数模板可以接受多个类型参数。示例

#include <iostream>

// 定义函数模板
template <typename T1, typename T2>
void printPair(T1 a, T2 b) {
    std::cout << "Pair: (" << a << ", " << b << ")" << std::endl;
}

int main() {
    printPair(10, 20.5); // 输出: Pair: (10, 20.5)
    printPair("Hello", 42); // 输出: Pair: (Hello, 42)
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 16.1.5 显式指定模板参数

注意事项：

自动类型推导，必须推导出一致的数据类型T,才可以使用
模板必须要确定出T的数据类型，才可以使用

//利用模板提供通用的交换函数
template<class T>
void mySwap(T &a, T &b) {
    T temp = a;
    a = b;
    b = temp;
}

//1、自动类型推导，必须推导出一致的数据类型T,才可以使用
void test1() {
    int a = 10;
    int b = 20;
    char c = 'c';
    mySwap(a,b);    // 正确，可以推导出一致的T
    //mySwap(a,c);    // 错误，推导不出一致的T类型
    cout << "a = " << a << endl;
    cout << "b = " << b << endl;
    cout << "c = " << c << endl;
}

template<class T>
void func() {
    cout << "func 调用" << endl;
}

void test2() {
    //func(); //错误，模板不能独立使用，必须确定出T的类型
    func<int>(); //利用显示指定类型的方式，给T一个类型，才可以使用该模板
}

int main() {
    test1();
    test2();
    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

总结：使用模板时必须确定出通用数据类型T，并且能够推导出一致的类型

# 16.1.6 函数模板的特化

函数模板的特化是指为特定类型提供特殊的实现。

示例

#include <iostream>

// 通用模板
template <typename T>
void print(T value) {
    std::cout << "Generic: " << value << std::endl;
}

// 特化版本（针对 const char*）
template <>
void print<const char*>(const char* value) {
    std::cout << "Specialized: " << value << std::endl;
}

int main() {
    print(10); // 调用通用模板
    print("Hello"); // 调用特化版本
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 16.1.7 函数模板与重载

函数模板可以与普通函数重载。编译器会优先选择最匹配的函数。

示例

#include <iostream>

// 普通函数
void print(int value) {
    std::cout << "Overloaded: " << value << std::endl;
}

// 函数模板
template <typename T>
void print(T value) {
    std::cout << "Template: " << value << std::endl;
}

int main() {
    print(10); // 调用普通函数
    print(10.5); // 调用函数模板
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 16.1.8 综合案例与思考

下面通过一个"通用工具库"案例，综合演示函数模板的定义、多类型参数、自动推导、显式指定、特化与重载：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

// 1. 基础函数模板：比较两个值
template<typename T>
bool isEqual(const T& a, const T& b) {
    return a == b;
}

// 2. 函数模板特化：C风格字符串需要用 strcmp 比较
template<>
bool isEqual<const char*>(const char* const& a, const char* const& b) {
    return strcmp(a, b) == 0;
}

// 3. 多类型参数模板：转换并格式化
template<typename T1, typename T2>
string formatPair(const T1& key, const T2& value) {
    return to_string(key) + " => " + to_string(value);
}

// 4. 函数模板特化：string 不需要 to_string
template<>
string formatPair<string, string>(const string& key, const string& value) {
    return key + " => " + value;
}

// 5. 普通函数重载：编译器优先匹配普通函数
string formatPair(const string& key, int value) {
    return key + " = " + to_string(value);
}

// 6. 非类型模板参数：固定大小的数组求和
template<typename T, int N>
T arraySum(const T (&arr)[N]) {
    T sum = T();
    for (int i = 0; i < N; ++i) {
        sum += arr[i];
    }
    return sum;
}

int main() {
    // 测试 isEqual：自动类型推导
    cout << "=== isEqual ===" << endl;
    cout << "10 == 10: " << isEqual(10, 10) << endl;
    cout << "3.14 == 3.14: " << isEqual(3.14, 3.14) << endl;
    // 特化版本处理 C 字符串
    cout << "\"hi\" == \"hi\": " << isEqual("hi", "hi") << endl;

    // 测试 formatPair
    cout << "\n=== formatPair ===" << endl;
    // 显式指定模板参数
    cout << formatPair<int, double>(42, 3.14) << endl;
    // 普通函数重载优先匹配
    cout << formatPair(string("age"), 25) << endl;
    // 特化版本
    cout << formatPair(string("name"), string("Alice")) << endl;

    // 测试 arraySum：非类型模板参数
    cout << "\n=== arraySum ===" << endl;
    int nums[] = {1, 2, 3, 4, 5};
    cout << "int数组求和: " << arraySum(nums) << endl;

    double vals[] = {1.1, 2.2, 3.3};
    cout << "double数组求和: " << arraySum(vals) << 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
62
63
64
65
66
67
68
69
70
71

输出结果：

=== isEqual ===
10 == 10: 1
3.14 == 3.14: 1
"hi" == "hi": 1

=== formatPair ===
42 => 3.140000
age = 25
name => Alice

=== arraySum ===
int数组求和: 15
double数组求和: 6.6

1
2
3
4
5
6
7
8
9
10
11
12
13

案例知识融合：本案例将函数模板的核心知识融为一体。isEqual 展示了基础模板定义和模板特化（const char* 需要特殊比较逻辑）。formatPair 展示了多类型参数模板、显式指定模板参数以及普通函数重载与模板的优先级关系（编译器优先选择非模板函数）。arraySum 使用了非类型模板参数 int N，编译器自动推导数组大小，实现编译期确定的安全数组操作。

思考题：

调用 formatPair(string("age"), 25) 时，为什么匹配的是普通函数而非函数模板？如果把普通函数删掉会怎样？
isEqual("hi", "hi") 如果没有特化版本，会发生什么？两个字符串字面量的地址是否相同？
arraySum 中为什么用 T sum = T() 而不是 T sum = 0？对于非数值类型有什么影响？

# 16.2 类模版

# 16.2.1 类模版概念

在 C++ 中，类模板是一种通用类定义，允许你编写可以处理多种数据类型的类。通过使用类模板，你可以避免为每种数据类型编写重复的代码，从而提高代码的复用性和可维护性。

# 16.2.2 类模板语法

类模板的定义使用 template 关键字，后跟模板参数列表。模板参数可以是类型参数（如 typename T）或非类型参数（如 int N）。

语法

template <typename T>
class 类名 {
    // 类成员
};

1
2
3
4

typename T：表示一个类型参数，T 可以是任意类型（如 int、double、std::string 等）。
在类中，T 可以像普通类型一样使用。

# 16.2.3 类模板示例

示例 1：简单的类模板

#include <iostream>

// 定义类模板
template <typename T>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    void print() {
        std::cout << "Value: " << value << std::endl;
    }
};

int main() {
    Box<int> intBox(10); // 实例化一个 Box<int> 对象
    intBox.print(); // 输出: Value: 10

    Box<double> doubleBox(3.14); // 实例化一个 Box<double> 对象
    doubleBox.print(); // 输出: Value: 3.14

    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

示例 2：类模板的成员函数。类模板的成员函数可以在类外定义，但需要显式指定模板参数。

#include <iostream>

template <typename T>
class Box {
private:
    T value;
public:
    Box(T v);
    void print();
};

// 类外定义构造函数
template <typename T>
Box<T>::Box(T v) : value(v) {}

// 类外定义成员函数
template <typename T>
void Box<T>::print() {
    std::cout << "Value: " << value << std::endl;
}

int main() {
    Box<int> intBox(42);
    intBox.print(); // 输出: Value: 42

    Box<std::string> stringBox("Hello");
    stringBox.print(); // 输出: Value: Hello

    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

# 16.2.4 多类型参数类模板

类模板可以接受多个类型参数。示例

#include <iostream>

template <typename T1, typename T2>
class Pair {
private:
    T1 first;
    T2 second;
public:
    Pair(T1 f, T2 s) : first(f), second(s) {}
    void print() {
        std::cout << "Pair: (" << first << ", " << second << ")" << std::endl;
    }
};

int main() {
    Pair<int, double> p1(10, 3.14);
    p1.print(); // 输出: Pair: (10, 3.14)

    Pair<std::string, int> p2("Hello", 42);
    p2.print(); // 输出: Pair: (Hello, 42)

    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

# 16.2.5 类模板的特化

类模板的特化是指为特定类型提供特殊的实现。

示例

#include <iostream>

// 通用模板
template <typename T>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    void print() {
        std::cout << "Generic: " << value << std::endl;
    }
};

// 特化版本（针对 const char*）
template <>
class Box<const char*> {
private:
    const char* value;
public:
    Box(const char* v) : value(v) {}
    void print() {
        std::cout << "Specialized: " << value << std::endl;
    }
};

int main() {
    Box<int> intBox(10);
    intBox.print(); // 输出: Generic: 10

    Box<const char*> stringBox("Hello");
    stringBox.print(); // 输出: Specialized: Hello

    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

# 16.2.6 类模板默认模板参数

可以为类模板的模板参数指定默认值。示例

#include <iostream>

template <typename T = int>
class Box {
private:
    T value;
public:
    Box(T v) : value(v) {}
    void print() {
        std::cout << "Value: " << value << std::endl;
    }
};

int main() {
    Box<> intBox(10); // 使用默认模板参数 int
    intBox.print(); // 输出: Value: 10

    Box<double> doubleBox(3.14); // 显式指定模板参数 double
    doubleBox.print(); // 输出: Value: 3.14

    return 0;
}

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

# 16.2.7 类模板嵌套

类模板可以嵌套在其他类或类模板中。示例

#include <iostream>

template <typename T>
class Outer {
public:
    template <typename U>
    class Inner {
    private:
        U value;
    public:
        Inner(U v) : value(v) {}
        void print() {
            std::cout << "Inner value: " << value << std::endl;
        }
    };
};

int main() {
    Outer<int>::Inner<double> inner(3.14);
    inner.print(); // 输出: Inner value: 3.14

    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

# 16.2.9 类模板注意事项

模板参数推断：类模板的模板参数不能自动推断，必须显式指定。
模板定义与声明：类模板的定义通常放在头文件中，因为编译器需要看到完整的定义才能实例化模板。
模板实例化：模板本身不是类，只有在使用时才会生成具体的类实例。

# 16.3 STL标准库模版

C++ 标准模板库（Standard Template Library，STL）是 C++ 标准库的一部分，提供了一系列通用的模板类和函数，用于实现常见的数据结构和算法。

# 16.3.1 STL核心组件

STL 的核心组件包括容器、迭代器、算法和 函数对象。

# 16.3.2 容器（Containers）

容器是用于存储数据的模板类，分为以下几类：

序列容器：按线性顺序存储数据，如 vector、list、deque。
关联容器：按键值对存储数据，如 set、map、multiset、multimap。
无序关联容器：基于哈希表实现，如 unordered_set、unordered_map。
容器适配器：基于其他容器实现的特殊接口，如 stack、queue、priority_queue。

# 16.3.3 迭代器（Iterators）

迭代器是用于遍历容器中元素的对象，类似于指针。STL 提供了多种迭代器：

输入迭代器：只能读取元素。
输出迭代器：只能写入元素。
前向迭代器：可以读取和写入元素，支持单向遍历。
双向迭代器：支持双向遍历。
随机访问迭代器：支持随机访问。

# 16.3.4 算法（Algorithms）

STL 提供了大量通用算法，用于操作容器中的数据，如排序、查找、遍历等。这些算法通过迭代器与容器交互。

# 16.3.5 函数对象（Function Objects）

函数对象是重载了 operator() 的类对象，可以像函数一样调用。STL 中的许多算法支持函数对象作为参数。

# 16.3.6 综合案例与思考

下面通过一个"学生成绩管理系统"案例，综合演示 STL 的容器、迭代器、算法和函数对象四大组件的协同使用：

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <string>
#include <functional>
using namespace std;

struct Student {
    string name;
    int score;
    bool operator<(const Student& other) const { return score > other.score; } // 降序
};

int main() {
    // 1. 序列容器：vector 存储学生
    vector<Student> students = {
        {"Alice", 92}, {"Bob", 78}, {"Carol", 95},
        {"David", 88}, {"Eve", 85}, {"Frank", 78}
    };

    // 2. 算法 + Lambda（函数对象）：排序
    sort(students.begin(), students.end());  // 使用 operator< 排序（降序）
    cout << "=== 成绩排名 ===" << endl;
    // 3. 迭代器：遍历
    int rank = 1;
    for (auto it = students.begin(); it != students.end(); ++it, ++rank) {
        cout << rank << ". " << it->name << ": " << it->score << endl;
    }

    // 4. 算法：统计
    int total = accumulate(students.begin(), students.end(), 0,
        [](int sum, const Student& s){ return sum + s.score; });
    double avg = static_cast<double>(total) / students.size();
    cout << "\n平均分: " << avg << endl;

    // 5. 算法：查找及格的学生
    auto passCount = count_if(students.begin(), students.end(),
        [](const Student& s){ return s.score >= 60; });
    cout << "及格人数: " << passCount << "/" << students.size() << endl;

    // 6. 算法：查找特定学生
    auto it = find_if(students.begin(), students.end(),
        [](const Student& s){ return s.name == "Bob"; });
    if (it != students.end()) {
        cout << "Bob 的成绩: " << it->score << endl;
    }

    // 7. 关联容器：map 统计分数段分布
    map<string, int> distribution;
    for (const auto& s : students) {
        if (s.score >= 90) distribution["优秀"]++;
        else if (s.score >= 80) distribution["良好"]++;
        else if (s.score >= 60) distribution["及格"]++;
        else distribution["不及格"]++;
    }
    cout << "\n=== 分数段分布 ===" << endl;
    for (const auto& [grade, count] : distribution) {
        cout << grade << ": " << count << "人" << endl;
    }

    // 8. 有序容器：set 去重获取所有不同分数
    set<int, greater<int>> uniqueScores;
    for (const auto& s : students) {
        uniqueScores.insert(s.score);
    }
    cout << "\n不同分数值(降序): ";
    for (int score : uniqueScores) cout << score << " ";
    cout << endl;

    // 9. 算法 + 函数对象：transform 生成评语
    vector<string> comments(students.size());
    transform(students.begin(), students.end(), comments.begin(),
        [](const Student& s) -> string {
            return s.name + (s.score >= 90 ? " 优秀!" : s.score >= 80 ? " 良好" : " 加油");
        });
    cout << "\n=== 评语 ===" << endl;
    for_each(comments.begin(), comments.end(), [](const string& c){ cout << c << 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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

输出结果：

=== 成绩排名 ===
1. Carol: 95
2. Alice: 92
3. David: 88
4. Eve: 85
5. Bob: 78
6. Frank: 78

平均分: 86
及格人数: 6/6
Bob 的成绩: 78

=== 分数段分布 ===
优秀: 2人
及格: 2人
良好: 2人

不同分数值(降序): 95 92 88 85 78
=== 评语 ===
Carol 优秀!
Alice 优秀!
David 良好
Eve 良好
Bob 加油
Frank 加油

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

案例知识融合：本案例将 STL 的四大核心组件有机结合：vector 和 map/set 展示了序列容器与关联容器的不同特性和适用场景；迭代器在排序、遍历、查找中扮演了容器与算法之间的桥梁角色；sort、accumulate、count_if、find_if、transform、for_each 等算法通过迭代器操作不同类型的容器；Lambda 表达式作为函数对象传给算法，实现了灵活的自定义行为。set<int, greater<int>> 使用了标准函数对象 greater 实现降序排列。

思考题：

sort 要求随机访问迭代器，如果把 vector 换成 list，还能直接用 std::sort 吗？应该怎么处理？
map 中的键 "优秀"/"良好"/"及格" 的输出顺序为什么是按字典序而非插入序？如果需要保持插入顺序应该用什么容器？
accumulate 的第三个参数为什么是 0 而不是 0.0？如果改成 0.0 并把 Lambda 的第一个参数改为 double，结果会有什么区别？

# 16.4 STL算法模版

# 16.4.1 非修改序列算法

find 查找容器中指定值的第一个匹配项。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::find(vec.begin(), vec.end(), 3);
    if (it != vec.end()) {
        std::cout << "Found: " << *it << std::endl; // 输出: Found: 3
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

count 统计容器中指定值的出现次数。

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

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 2};
    int cnt = std::count(vec.begin(), vec.end(), 2);
    std::cout << "Count: " << cnt << std::endl; // 输出: Count: 3
    return 0;
}

1
2
3
4
5
6
7
8
9
10

for_each 对容器中的每个元素执行指定操作。

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

void print(int x) {
    std::cout << x << " ";
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::for_each(vec.begin(), vec.end(), print); // 输出: 1 2 3 4 5
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 16.4.2 修改序列算法

这些算法会修改容器中的元素。

# 2.1 `copy`

将一个容器的元素复制到另一个容器。

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

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(5);
    std::copy(src.begin(), src.end(), dst.begin());
    for (int i : dst) {
        std::cout << i << " "; // 输出: 1 2 3 4 5
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 2.2 `fill`

将容器中的元素填充为指定值。

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

int main() {
    std::vector<int> vec(5);
    std::fill(vec.begin(), vec.end(), 10);
    for (int i : vec) {
        std::cout << i << " "; // 输出: 10 10 10 10 10
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 2.3 `transform`

对容器中的每个元素进行转换，并将结果存储到另一个容器。

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

int square(int x) {
    return x * x;
}

int main() {
    std::vector<int> src = {1, 2, 3, 4, 5};
    std::vector<int> dst(src.size());
    std::transform(src.begin(), src.end(), dst.begin(), square);
    for (int i : dst) {
        std::cout << i << " "; // 输出: 1 4 9 16 25
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 16.4.3 排序算法

# 3.1 `sort`

对容器中的元素进行排序。

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

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::sort(vec.begin(), vec.end());
    for (int i : vec) {
        std::cout << i << " "; // 输出: 1 2 3 4 5
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 3.2 `stable_sort`

稳定排序，保持相等元素的相对顺序。

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

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::stable_sort(vec.begin(), vec.end());
    for (int i : vec) {
        std::cout << i << " "; // 输出: 1 2 3 4 5
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 3.3 `partial_sort`

对容器中的部分元素进行排序。

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

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
    for (int i : vec) {
        std::cout << i << " "; // 输出: 1 2 3 5 4
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12

# 16.4.4 查找算法

# 4.1 `binary_search`

在有序容器中查找指定值。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    bool found = std::binary_search(vec.begin(), vec.end(), 3);
    std::cout << (found ? "Found" : "Not found") << std::endl; // 输出: Found
    return 0;
}

1
2
3
4
5
6
7
8
9
10

# 4.2 `lower_bound`

返回第一个不小于指定值的元素位置。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::lower_bound(vec.begin(), vec.end(), 3);
    std::cout << "Lower bound: " << *it << std::endl; // 输出: Lower bound: 3
    return 0;
}

1
2
3
4
5
6
7
8
9
10

# 4.3 `upper_bound`

返回第一个大于指定值的元素位置。

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

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto it = std::upper_bound(vec.begin(), vec.end(), 3);
    std::cout << "Upper bound: " << *it << std::endl; // 输出: Upper bound: 4
    return 0;
}

1
2
3
4
5
6
7
8
9
10

# 16.4.5 数值算法

# 5.1 `accumulate`

计算容器中元素的和。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "Sum: " << sum << std::endl; // 输出: Sum: 15
    return 0;
}

1
2
3
4
5
6
7
8
9
10

# 5.2 `inner_product`

计算两个容器的内积。

#include <iostream>
#include <vector>
#include <numeric>

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2 = {4, 5, 6};
    int result = std::inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
    std::cout << "Inner product: " << result << std::endl; // 输出: Inner product: 32
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11

# 16.4.6 总结一下

STL 算法提供了强大的功能，可以高效地操作容器中的数据。常用的算法包括：

非修改序列算法：如 find、count、for_each。
修改序列算法：如 copy、fill、transform。
排序算法：如 sort、stable_sort、partial_sort。
查找算法：如 binary_search、lower_bound、upper_bound。
数值算法：如 accumulate、inner_product。

# 16.4.7 综合案例与思考

下面通过一个"数据处理流水线"案例，综合演示非修改算法、修改算法、排序算法、查找算法和数值算法的组合使用：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <string>
#include <cmath>
using namespace std;

int main() {
    // 原始数据：一组温度采样值
    vector<double> temps = {36.5, 37.8, 36.2, 39.1, 36.8, 38.5, 36.1, 37.2, 40.2, 36.9};

    // 1. for_each + 输出原始数据
    cout << "原始数据: ";
    for_each(temps.begin(), temps.end(), [](double t){ cout << t << " "; });
    cout << endl;

    // 2. count_if：统计发烧数据（>37.5）
    int feverCount = count_if(temps.begin(), temps.end(),
        [](double t){ return t > 37.5; });
    cout << "发烧次数: " << feverCount << "/" << temps.size() << endl;

    // 3. sort：升序排列
    vector<double> sorted_temps(temps);
    sort(sorted_temps.begin(), sorted_temps.end());
    cout << "排序后: ";
    for_each(sorted_temps.begin(), sorted_temps.end(),
        [](double t){ cout << t << " "; });
    cout << endl;

    // 4. binary_search / lower_bound / upper_bound
    bool has37 = binary_search(sorted_temps.begin(), sorted_temps.end(), 37.2);
    cout << "包含37.2: " << (has37 ? "是" : "否") << endl;

    auto lb = lower_bound(sorted_temps.begin(), sorted_temps.end(), 37.0);
    auto ub = upper_bound(sorted_temps.begin(), sorted_temps.end(), 38.0);
    cout << "37.0~38.0之间: ";
    for_each(lb, ub, [](double t){ cout << t << " "; });
    cout << endl;

    // 5. accumulate：求和与平均值
    double sum = accumulate(temps.begin(), temps.end(), 0.0);
    double avg = sum / temps.size();
    cout << "平均温度: " << avg << endl;

    // 6. transform：计算每个值与平均值的偏差
    vector<double> deviations(temps.size());
    transform(temps.begin(), temps.end(), deviations.begin(),
        [avg](double t){ return t - avg; });
    cout << "偏差值: ";
    for_each(deviations.begin(), deviations.end(),
        [](double d){ cout << (d >= 0 ? "+" : "") << d << " "; });
    cout << endl;

    // 7. inner_product：计算方差
    double variance = inner_product(deviations.begin(), deviations.end(),
        deviations.begin(), 0.0) / temps.size();
    cout << "方差: " << variance << ", 标准差: " << sqrt(variance) << endl;

    // 8. copy_if + back_inserter：筛选异常温度
    vector<double> abnormal;
    copy_if(temps.begin(), temps.end(), back_inserter(abnormal),
        [avg, variance](double t){ return abs(t - avg) > sqrt(variance); });
    cout << "异常温度(超过1个标准差): ";
    for_each(abnormal.begin(), abnormal.end(),
        [](double t){ cout << t << " "; });
    cout << endl;

    // 9. partial_sort：找出前3高温
    vector<double> top3(temps);
    partial_sort(top3.begin(), top3.begin() + 3, top3.end(), greater<double>());
    cout << "最高3个温度: ";
    for_each(top3.begin(), top3.begin() + 3,
        [](double t){ cout << t << " "; });
    cout << endl;

    // 10. fill + generate：生成校准数据
    vector<double> calibrated(temps.size());
    transform(temps.begin(), temps.end(), calibrated.begin(),
        [](double t){ return round(t * 10) / 10; });  // 保留一位小数
    cout << "校准后: ";
    for_each(calibrated.begin(), calibrated.end(),
        [](double t){ cout << t << " "; });
    cout << endl;

    return 0;
}

案例知识融合：本案例将 STL 五大类算法在一个温度数据分析场景中串联使用。非修改算法（for_each、count_if、find）用于数据查看和统计；排序算法（sort、partial_sort）用于排序和 Top-N 筛选；查找算法（binary_search、lower_bound、upper_bound）用于有序数据的高效查找和范围定位；修改算法（transform、copy_if）用于数据变换和筛选；数值算法（accumulate、inner_product）用于统计计算。back_inserter 适配器让 copy_if 可以动态追加元素而无需预分配空间，体现了迭代器适配器的实用价值。

思考题：

sort 默认是升序，partial_sort(begin, begin+3, end, greater<>()) 只排前3大的值，剩余元素的顺序是否确定？partial_sort 相比完整 sort 后取前3个有什么性能优势？
binary_search 要求数据已经排序，如果对未排序的 temps 直接调用会怎样？返回值是否可靠？
计算方差时用 inner_product(d.begin(), d.end(), d.begin(), 0.0) 巧妙地实现了"对自身做内积"，这等价于什么数学运算？如果初始值用 0 而不是 0.0 会有什么问题？

# 16.8 模板与STL底层原理

# 16.8.1 模板的编译期展开

模板不是真正的代码，它是生成代码的蓝图。编译器看到模板的使用（实例化）时，为每种类型生成一份独立的代码：

template<typename T>
T add(T a, T b) { return a + b; }

add(1, 2);       // 编译器生成 int add(int, int)
add(1.5, 2.5);   // 编译器生成 double add(double, double)

1
2
3
4
5

编译后的目标文件中有两个独立的函数。这就是**模板膨胀（Code Bloat）**的原因——同一份模板为100种类型实例化就有100份代码。

模板编译的两阶段：

定义时：检查模板本身的语法（与T无关的部分）
实例化时：替换T为具体类型，检查所有依赖T的表达式是否合法

template<typename T>
void foo(T x) {
    x.bar();      // 定义时不报错（T是什么都不知道）
    int a = "hi"; // 定义时报错（与T无关的语法错误）
}
// 只有 foo(myObj) 时才检查 myObj 是否有 bar() 方法

1
2
3
4
5
6

模板特化的底层：编译器维护一个"特化表"，实例化时先查找是否有匹配的特化版本，有则使用特化，无则使用通用模板。

# 16.8.2 STL容器的内存布局

vector<T>的内存结构：

// vector的简化模型
template<typename T>
class vector {
    T* begin_;      // 指向第一个元素
    T* end_;        // 指向最后一个元素的下一位
    T* capacity_;   // 指向分配空间的末尾
};
// sizeof(vector) = 24字节（3个指针）

1
2
3
4
5
6
7
8

vector<int> v = {1,2,3,4,5}; 容量为8时：

v对象（栈上24字节）:
┌────────┬────────┬────────┐
│ begin_ │ end_   │capacity│
│  ↓     │  ↓     │  ↓     │
└────────┴────────┴────────┘

堆上连续内存：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │ ? │ ? │ ? │
└───┴───┴───┴───┴───┴───┴───┴───┘
 ↑begin              ↑end       ↑capacity

1
2
3
4
5
6
7
8
9
10
11
12
13

list<T>是双向链表——每个元素独立分配，通过指针链接。缓存不友好但支持O(1)插入删除。

unordered_map<K,V>是哈希表——内部是一个bucket数组，每个bucket是一个链表（或在C++23中可能是开放寻址）。

# 16.8.3 迭代器失效问题

迭代器失效是STL中最常见的bug来源：

容器	插入时失效	删除时失效
`vector`	扩容时所有迭代器失效；不扩容时插入点后失效	删除点及之后所有失效
`deque`	头尾插入不失效（中间插入全失效）	删除端点不失效其他；删除中间全失效
`list`	不失效	只有被删元素的迭代器失效
`map/set`	不失效	只有被删元素失效
`unordered_map`	rehash时所有失效	只有被删元素失效

vector扩容导致失效的原因：

vector<int> v = {1,2,3};
auto it = v.begin();  // it指向旧内存
v.push_back(4);       // 触发扩容，分配新内存，拷贝元素，释放旧内存
cout << *it;           // 未定义行为！it仍指向已释放的旧内存

1
2
3
4

# 16.9 模板与STL训练题

训练题1：实现通用的查找和过滤函数

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// 泛型filter函数
template<typename Container, typename Predicate>
auto filter(const Container& c, Predicate pred) {
    Container result;
    copy_if(c.begin(), c.end(), back_inserter(result), pred);
    return result;
}

// 泛型transform函数
template<typename Container, typename Func>
auto transform_all(const Container& c, Func f) {
    using ResultType = decltype(f(*c.begin()));
    vector<ResultType> result;
    result.reserve(c.size());
    transform(c.begin(), c.end(), back_inserter(result), f);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    // 过滤偶数
    auto evens = filter(nums, [](int n) { return n % 2 == 0; });
    cout << "偶数: ";
    for (int n : evens) cout << n << " ";
    cout << endl;

    // 平方变换
    auto squares = transform_all(nums, [](int n) { return n * n; });
    cout << "平方: ";
    for (int n : squares) cout << n << " ";
    cout << endl;

    // 字符串操作
    vector<string> words = {"hello", "world", "c++", "template"};
    auto long_words = filter(words, [](const string& s) { return s.size() > 4; });
    auto upper = transform_all(words, [](const string& s) {
        string u = s;
        transform(u.begin(), u.end(), u.begin(), ::toupper);
        return u;
    });

    cout << "长单词: ";
    for (const auto& w : long_words) cout << w << " ";
    cout << "\n大写: ";
    for (const auto& w : upper) cout << w << " ";
    cout << 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

练习重点：函数模板+Lambda实现泛型算法、decltype自动推导返回类型、STL算法组合使用。

训练题2：实现简易的模板容器

#include <iostream>
#include <stdexcept>
using namespace std;

template<typename T, int N>
class FixedArray {
    T data_[N];
    int size_ = 0;

public:
    void push_back(const T& val) {
        if (size_ >= N) throw overflow_error("数组已满");
        data_[size_++] = val;
    }

    T& operator[](int i) {
        if (i < 0 || i >= size_) throw out_of_range("越界");
        return data_[i];
    }

    int size() const { return size_; }

    // 迭代器支持（让range-for可用）
    T* begin() { return data_; }
    T* end() { return data_ + size_; }
    const T* begin() const { return data_; }
    const T* end() const { return data_ + size_; }
};

int main() {
    FixedArray<int, 5> arr;
    for (int i = 0; i < 5; ++i) arr.push_back(i * 10);

    // range-for遍历
    for (int val : arr) cout << val << " ";
    cout << endl;

    // 不同类型实例化
    FixedArray<string, 3> names;
    names.push_back("Alice");
    names.push_back("Bob");
    for (const auto& name : names) cout << name << " ";
    cout << 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

练习重点：类模板+非类型模板参数（int N）、提供begin/end支持range-for、编译期确定数组大小避免动态分配。

# 16.10 综合思考题

模板元编程（TMP）：C++模板系统是图灵完备的，可以在编译期计算任意结果（如编译期斐波那契数列）。C++17的constexpr if和if constexpr如何简化了TMP？C++20的Concepts如何替代了SFINAE（Substitution Failure Is Not An Error）技巧？
STL容器的选择策略：vector、list、deque、map、unordered_map各有什么适用场景？为什么90%的情况应该优先使用vector（即使理论复杂度不是最优）？缓存友好性（cache-friendly）如何影响实际性能？
move语义对STL的影响：C++11的移动语义让vector<string>的扩容从O(n×字符串长度)降到了O(n)。请解释为什么移动一个string是O(1)而拷贝是O(n)？emplace_back比push_back快在哪里？

上次更新: 2026/06/10, 11:13:41

← 线程和锁预处理器→

STL模版

# 第 16 章 C++ STL 模板

# 目录介绍

# 16.1 函数模版

# 16.1.1 函数模版概念

# 16.1.2 函数模板语法

# 16.1.3 函数模板示例

# 16.1.4 多类型参数函数模板

# 16.1.5 显式指定模板参数

# 16.1.6 函数模板的特化

# 16.1.7 函数模板与重载

# 16.1.8 综合案例与思考

# 16.2 类模版

# 16.2.1 类模版概念

# 16.2.2 类模板语法

# 16.2.3 类模板示例

# 16.2.4 多类型参数类模板

# 16.2.5 类模板的特化

# 16.2.6 类模板默认模板参数

# 16.2.7 类模板嵌套

# 16.2.9 类模板注意事项

# 16.3 STL标准库模版

# 16.3.1 STL核心组件

# 16.3.2 容器（Containers）

# 16.3.3 迭代器（Iterators）

# 16.3.4 算法（Algorithms）

# 16.3.5 函数对象（Function Objects）

# 16.3.6 综合案例与思考

# 16.4 STL算法模版

# 16.4.1 非修改序列算法

# 16.4.2 修改序列算法

# 2.1 copy

# 2.2 fill

# 2.3 transform

# 16.4.3 排序算法

# 3.1 sort

# 3.2 stable_sort

# 3.3 partial_sort

# 16.4.4 查找算法

# 4.1 binary_search

# 4.2 lower_bound

# 4.3 upper_bound

# 16.4.5 数值算法

# 5.1 accumulate

# 5.2 inner_product

# 16.4.6 总结一下

# 16.4.7 综合案例与思考

# 16.8 模板与STL底层原理

# 16.8.1 模板的编译期展开

# 16.8.2 STL容器的内存布局

# 16.8.3 迭代器失效问题

# 16.9 模板与STL训练题

# 16.10 综合思考题

# 2.1 `copy`

# 2.2 `fill`

# 2.3 `transform`

# 3.1 `sort`

# 3.2 `stable_sort`

# 3.3 `partial_sort`

# 4.1 `binary_search`

# 4.2 `lower_bound`

# 4.3 `upper_bound`

# 5.1 `accumulate`

# 5.2 `inner_product`