C++掌握标准模板库(STL)

C++ 标准模板库（STL）概述

C++ 标准模板库（Standard Template Library，简称 STL）是 C++ 标准库的重要组成部分，它提供了一组通用的、高度可复用的数据结构和算法，大大提高了开发效率和代码质量。STL 主要由容器（Containers）、算法（Algorithms）和迭代器（Iterators）三部分组成，这三个组件相互协作，构成了一个强大的编程框架。

容器（Containers）

容器是 STL 中用于存储和管理数据的组件，它可以分为顺序容器（Sequence Containers）、关联容器（Associative Containers）和无序关联容器（Unordered Associative Containers）。

顺序容器

顺序容器按照元素的插入顺序存储和访问元素，主要包括向量（std::vector）、列表（std::list）和双端队列（std::deque）。

1. 向量（std::vector） std::vector 是一个动态数组，它在内存中连续存储元素，因此支持快速的随机访问。向量的大小可以根据需要动态增长，当元素数量超过当前容量时，向量会重新分配内存，将原有元素复制到新的内存位置。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers;
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上述代码中，我们创建了一个 std::vector<int> 对象 numbers，并使用 push_back 方法向向量中添加元素。然后通过索引访问向量中的元素并输出。

2. 列表（std::list） std::list 是一个双向链表，它的元素在内存中不连续存储。列表支持高效的插入和删除操作，尤其是在列表的头部和尾部进行操作时，时间复杂度为 O(1)。但是，列表不支持随机访问，访问元素需要从头开始遍历。

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers;
    numbers.push_back(1);
    numbers.push_back(2);
    numbers.push_back(3);

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

这里我们创建了一个 std::list<int> 对象 numbers，通过 push_back 添加元素，然后使用迭代器遍历列表并输出元素。

3. 双端队列（std::deque） std::deque（double - ended queue）是一个双端队列，它允许在队列的头部和尾部进行高效的插入和删除操作，时间复杂度为 O(1)。与向量类似，双端队列也支持随机访问，但它的内存布局不是连续的，而是由多个连续的内存块组成。

#include <iostream>
#include <deque>

int main() {
    std::deque<int> numbers;
    numbers.push_back(1);
    numbers.push_front(0);
    numbers.push_back(2);

    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这段代码中，我们使用 std::deque<int> 创建了 numbers，通过 push_back 和 push_front 方法在队列两端添加元素，然后通过索引访问并输出元素。

关联容器

关联容器按照特定的键（Key）来存储和访问元素，主要包括集合（std::set）和映射（std::map）。关联容器通常使用红黑树（Red - Black Tree）实现，因此插入、删除和查找操作的平均时间复杂度为 O(log n)。

1. 集合（std::set） std::set 存储的元素是唯一的，并且会按照元素的升序自动排序。

#include <iostream>
#include <set>

int main() {
    std::set<int> numbers;
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(2);

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，我们创建了一个 std::set<int> 对象 numbers，使用 insert 方法插入元素，集合会自动排序并确保元素唯一，最后通过迭代器遍历输出。

2. 映射（std::map） std::map 存储的是键值对（Key - Value Pairs），每个键都是唯一的，并且会按照键的升序自动排序。

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> scores;
    scores["Alice"] = 85;
    scores["Bob"] = 90;
    scores["Charlie"] = 78;

    for (auto it = scores.begin(); it != scores.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

这里我们创建了一个 std::map<std::string, int> 对象 scores，通过键值对的方式插入数据，然后使用迭代器遍历输出每个键值对。

无序关联容器

无序关联容器使用哈希表（Hash Table）实现，按照元素的哈希值存储和访问元素，主要包括无序集合（std::unordered_set）和无序映射（std::unordered_map）。无序关联容器的插入、删除和查找操作的平均时间复杂度为 O(1)，但在最坏情况下可能达到 O(n)。

1. 无序集合（std::unordered_set） std::unordered_set 存储的元素是唯一的，但不保证元素的顺序。

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> numbers;
    numbers.insert(3);
    numbers.insert(1);
    numbers.insert(2);

    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

代码中创建了 std::unordered_set<int> 对象 numbers，插入元素后通过迭代器遍历输出，元素顺序与插入顺序可能不同。

2. 无序映射（std::unordered_map） std::unordered_map 存储键值对，键是唯一的，同样不保证键值对的顺序。

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> scores;
    scores["Alice"] = 85;
    scores["Bob"] = 90;
    scores["Charlie"] = 78;

    for (auto it = scores.begin(); it != scores.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    return 0;
}

此例创建了 std::unordered_map<std::string, int> 对象 scores，插入键值对后通过迭代器遍历输出，顺序可能与插入顺序不同。

算法（Algorithms）

STL 提供了大量的通用算法，这些算法可以分为排序算法、查找算法、数值算法等。算法通过迭代器来操作容器中的元素，使得算法与容器解耦，提高了代码的复用性。

排序算法

排序算法用于对容器中的元素进行排序，常见的排序算法有 std::sort、std::stable_sort 等。

1. std::sort std::sort 是一个快速排序算法，它对给定范围内的元素进行排序，时间复杂度在平均情况下为 O(n log n)，在最坏情况下为 O(n^2)。

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

int main() {
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::sort(numbers.begin(), numbers.end());

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在这段代码中，我们创建了一个 std::vector<int> 并初始化了一些元素，然后使用 std::sort 对向量中的元素进行排序，最后输出排序后的结果。

2. std::stable_sort std::stable_sort 是一个稳定排序算法，它在排序过程中保持相等元素的相对顺序不变，时间复杂度为 O(n log^2 n)。

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

struct Student {
    std::string name;
    int score;
};

bool compareByScore(const Student& a, const Student& b) {
    return a.score < b.score;
}

int main() {
    std::vector<Student> students = {
        {"Alice", 85},
        {"Bob", 90},
        {"Charlie", 85},
        {"David", 78}
    };

    std::stable_sort(students.begin(), students.end(), compareByScore);

    for (const auto& student : students) {
        std::cout << student.name << ": " << student.score << std::endl;
    }

    return 0;
}

这里我们定义了一个 Student 结构体，包含姓名和分数。通过 std::stable_sort 对 students 向量按照分数进行排序，由于是稳定排序，相同分数的学生相对顺序保持不变。

查找算法

查找算法用于在容器中查找特定的元素，常见的查找算法有 std::find、std::find_if 等。

1. std::find std::find 在给定范围内查找指定的值，如果找到则返回指向该元素的迭代器，否则返回范围末尾的迭代器。

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = std::find(numbers.begin(), numbers.end(), 3);

    if (it != numbers.end()) {
        std::cout << "Element found at position " << std::distance(numbers.begin(), it) << std::endl;
    } else {
        std::cout << "Element not found" << std::endl;
    }

    return 0;
}

此代码在 std::vector<int> 中查找值为 3 的元素，通过 std::distance 计算元素位置并输出结果。

2. std::find_if std::find_if 在给定范围内查找满足特定条件的第一个元素，条件由一个谓词（Predicate）函数指定。

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

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

int main() {
    std::vector<int> numbers = {1, 3, 4, 5, 6};
    auto it = std::find_if(numbers.begin(), numbers.end(), isEven);

    if (it != numbers.end()) {
        std::cout << "Even number found: " << *it << std::endl;
    } else {
        std::cout << "No even number found" << std::endl;
    }

    return 0;
}

这里定义了一个 isEven 谓词函数，通过 std::find_if 在向量中查找第一个偶数并输出。

数值算法

数值算法用于对容器中的数值元素进行计算，例如求和、求积等。常见的数值算法有 std::accumulate、std::inner_product 等。

1. std::accumulate std::accumulate 用于计算给定范围内元素的总和，它接受一个初始值，并将范围内的元素依次与初始值相加。

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);

    std::cout << "Sum of numbers: " << sum << std::endl;

    return 0;
}

在这个例子中，我们使用 std::accumulate 计算 std::vector<int> 中元素的总和，并输出结果。

2. std::inner_product std::inner_product 用于计算两个范围的内积，即将两个范围中对应位置的元素相乘，然后将结果累加起来。

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

int main() {
    std::vector<int> a = {1, 2, 3};
    std::vector<int> b = {4, 5, 6};
    int result = std::inner_product(a.begin(), a.end(), b.begin(), 0);

    std::cout << "Inner product: " << result << std::endl;

    return 0;
}

此代码计算了两个 std::vector<int> 的内积并输出。

迭代器（Iterators）

迭代器是 STL 中用于访问容器中元素的对象，它提供了一种统一的方式来遍历不同类型的容器。迭代器可以分为输入迭代器（Input Iterators）、输出迭代器（Output Iterators）、前向迭代器（Forward Iterators）、双向迭代器（Bidirectional Iterators）和随机访问迭代器（Random Access Iterators）。

输入迭代器

输入迭代器用于从容器中读取元素，它只能向前移动，并且只能读取一次。输入迭代器支持 *（解引用）和 ++（递增）操作。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = numbers.begin();

    while (it != numbers.end()) {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << std::endl;

    return 0;
}

在这段代码中，it 是一个随机访问迭代器，它也满足输入迭代器的要求。我们通过 *it 读取元素，通过 ++it 移动到下一个元素。

输出迭代器

输出迭代器用于向容器中写入元素，它只能向前移动，并且只能写入一次。输出迭代器支持 *（解引用）和 ++（递增）操作，但解引用后返回的是一个可写的引用。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers;
    auto it = std::back_inserter(numbers);

    *it = 1;
    ++it;
    *it = 2;
    ++it;
    *it = 3;

    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

这里使用 std::back_inserter 创建了一个输出迭代器 it，通过 *it 向 numbers 向量中写入元素。

前向迭代器

前向迭代器是输入迭代器和输出迭代器的扩展，它可以多次读取和写入元素，并且可以向前移动多次。前向迭代器支持 *（解引用）、++（递增）和复制构造等操作。

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers;
    auto it1 = std::front_inserter(numbers);
    *it1 = 3;
    ++it1;
    *it1 = 2;
    ++it1;
    *it1 = 1;

    auto it2 = numbers.begin();
    while (it2 != numbers.end()) {
        std::cout << *it2 << " ";
        ++it2;
    }
    std::cout << std::endl;

    return 0;
}

在这个例子中，it1 是一个前向输出迭代器（std::front_inserter 返回的迭代器类型），it2 是一个前向输入迭代器（std::list<int>::iterator），它们都满足前向迭代器的要求。

双向迭代器

双向迭代器在前向迭代器的基础上，增加了向后移动的功能，即支持 --（递减）操作。双向迭代器常用于列表（std::list）等容器。

#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {1, 2, 3, 4, 5};
    auto it = numbers.end();
    --it;

    while (it != numbers.begin()) {
        std::cout << *it << " ";
        --it;
    }
    std::cout << *it << std::endl;

    return 0;
}

此代码通过双向迭代器从列表末尾开始向前遍历并输出元素。

随机访问迭代器

随机访问迭代器在双向迭代器的基础上，增加了随机访问的功能，即支持 +（加法）、-（减法）、+=（复合加法）、-=（复合减法）、<（小于）、>（大于）等操作。随机访问迭代器常用于向量（std::vector）和双端队列（std::deque）等容器。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    auto it = numbers.begin() + 2;

    std::cout << "Element at position 2: " << *it << std::endl;

    return 0;
}

这里通过随机访问迭代器直接访问向量中索引为 2 的元素。

STL 的其他组件

除了容器、算法和迭代器外，STL 还包含其他一些组件，如函数对象（Functors）、适配器（Adapters）等。

函数对象（Functors）

函数对象是一种重载了 () 运算符的类对象，它可以像函数一样被调用。函数对象在 STL 中常用于定制算法的行为。

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

struct GreaterThanFive {
    bool operator()(int num) const {
        return num > 5;
    }
};

int main() {
    std::vector<int> numbers = {1, 6, 3, 8, 5};
    auto it = std::find_if(numbers.begin(), numbers.end(), GreaterThanFive());

    if (it != numbers.end()) {
        std::cout << "Number greater than 5 found: " << *it << std::endl;
    } else {
        std::cout << "No number greater than 5 found" << std::endl;
    }

    return 0;
}

在这个例子中，我们定义了一个 GreaterThanFive 函数对象，通过 std::find_if 使用该函数对象查找向量中大于 5 的元素。

适配器（Adapters）

适配器用于将一种类型的对象转换为另一种类型的对象，以满足特定的需求。STL 中的适配器主要包括容器适配器（Container Adapters）、迭代器适配器（Iterator Adapters）和函数适配器（Function Adapters）。

1. 容器适配器 容器适配器基于现有的容器，提供了不同的接口和语义。常见的容器适配器有栈（std::stack）和队列（std::queue）。

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;
    stack.push(1);
    stack.push(2);
    stack.push(3);

    while (!stack.empty()) {
        std::cout << stack.top() << " ";
        stack.pop();
    }
    std::cout << std::endl;

    return 0;
}

这里使用 std::stack 容器适配器，通过 push 方法压入元素，通过 top 方法获取栈顶元素，通过 pop 方法弹出栈顶元素。

2. 迭代器适配器 迭代器适配器用于将一种类型的迭代器转换为另一种类型的迭代器。例如，std::reverse_iterator 可以将一个正向迭代器转换为反向迭代器。

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::reverse_iterator<std::vector<int>::iterator> it(numbers.end());

    while (it != std::reverse_iterator<std::vector<int>::iterator>(numbers.begin())) {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << *it << std::endl;

    return 0;
}

此代码通过 std::reverse_iterator 将 std::vector<int> 的正向迭代器转换为反向迭代器，从而反向遍历向量。

3. 函数适配器 函数适配器用于将一种类型的函数对象转换为另一种类型的函数对象。例如，std::bind 可以将一个函数或函数对象与部分参数绑定，生成一个新的函数对象。

#include <iostream>
#include <functional>

void greet(const std::string& name, const std::string& greeting) {
    std::cout << greeting << ", " << name << "!" << std::endl;
}

int main() {
    auto greetAlice = std::bind(greet, "Alice", std::placeholders::_1);
    greetAlice("Hello");

    return 0;
}

这里使用 std::bind 将 greet 函数与参数 "Alice" 绑定，生成一个新的函数对象 greetAlice，该函数对象只需要传入问候语即可调用。

通过深入理解和掌握 STL 的各个组件，C++ 开发者能够更加高效地编写代码，利用 STL 提供的强大功能来解决各种编程问题。无论是处理大规模数据集合，还是实现复杂的算法逻辑，STL 都能成为有力的工具。