STL模板：容器与算法

1. STL 介绍

1.1 什么是 STL？

• STL (Standard Template Library)：C++ 标准库的一部分，提供高效、可重用的数据结构和算法。
• 主要组成部分：
  • 容器 (Containers)：存储数据的结构。
  • 算法 (Algorithms)：对容器中的数据进行操作的函数。
  • 迭代器 (Iterators)：访问容器元素的对象。
  • 函数对象 (Function Objects)：可作为参数传递的对象。

2. STL 容器

2.1 序列容器 (Sequence Containers)

• vector：动态数组，支持快速随机访问。
• deque：双端队列，支持从两端插入和删除元素。
• list：双向链表，支持高效的插入和删除操作。
• array：固定大小数组，支持快速访问。

示例：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);  // 添加元素
    for (int val : vec) {
        std::cout << val << " ";  // 输出 1 2 3 4 5 6
    }
    return 0;
}

2.2 关联容器 (Associative Containers)

• set：集合，存储唯一元素并自动排序。
• map：映射，存储键值对并自动根据键排序。
• unordered_set：无序集合，基于哈希表实现，查找效率高。
• unordered_map：无序映射，基于哈希表实现，查找效率高。

示例：

#include <iostream>
#include <set>
int main() {
    std::set<int> s = {1, 2, 3, 4};
    s.insert(5);  // 插入元素
    for (int val : s) {
        std::cout << val << " ";  // 输出 1 2 3 4 5
    }
    return 0;
}

2.3 容器适配器 (Container Adapters)

• stack：栈，基于 deque 实现。
• queue：队列，基于 deque 实现。
• priority_queue：优先队列，基于堆实现。

示例：

#include <iostream>
#include <stack>
int main() {
    std::stack<int> s;
    s.push(1);
    s.push(2);
    while (!s.empty()) {
        std::cout << s.top() << " ";  // 输出 2 1
        s.pop();
    }
    return 0;
}

3. STL 迭代器

3.1 迭代器概述

• 迭代器是用于访问容器中元素的对象，类似于指针。
• 常见操作：
  • begin() 和 end()：获取容器的开始和结束位置。
  • ++：迭代器的递增。
  • *：解引用，获取迭代器指向的元素。

示例：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";  // 输出 1 2 3 4 5
    }
    return 0;
}

3.2 范围基 for 循环

• C++11 引入了范围基 for 循环，使得遍历容器更加简洁。

示例：

#include <iostream>
#include <vector>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (int val : vec) {
        std::cout << val << " ";  // 输出 1 2 3 4 5
    }
    return 0;
}

4. STL 算法

4.1 常用算法

• sort()：排序容器中的元素。
• find()：查找容器中的元素。
• reverse()：反转容器中的元素。
• accumulate()：计算容器中所有元素的和。

示例：

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::sort(vec.begin(), vec.end(), std::greater<int>());
    for (int val : vec) {
        std::cout << val << " ";  // 输出 5 4 3 2 1
    }
    int sum = std::accumulate(vec.begin(), vec.end(), 0);
    std::cout << "\nSum: " << sum;  // 输出 Sum: 15
    return 0;
}

4.2 容器与算法结合

• STL 的算法可以与容器配合使用，简化代码，提升开发效率。

示例：

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

5. 总结

• STL 提供了强大的容器、算法和迭代器功能，简化了代码并提高了开发效率。
• 理解 STL 容器和算法的使用方式是成为 C++ 高效开发者的关键。
• 学习模板编程的基础，有助于理解 STL 的泛型编程。

6. 练习与作业

6.1 练习

1. 使用 vector 容器存储 10 个随机整数，排序并输出。
2. 使用 map 容器统计一个字符串中各个字符的频率。
3. 实现一个简单的函数，接受一个 stack 容器并返回其栈顶元素。

6.2 作业

1. 用 set 容器实现一个简易的集合操作，支持添加、删除和查找元素。
2. 编写一个程序，使用 priority_queue 实现一个优先级队列。
3. 使用 accumulate 计算并输出一个 vector 中所有元素的平均值。