12、C++标准库（STL）入门：vector、list、map、set、迭代器、算法（sort, find）

说实话，很多初学者学C++学到一半就放弃了，十有八九是卡在了STL这里。我当年刚接触STL时也觉得头大——什么容器、迭代器、算法，一堆新概念砸过来。但后来我发现，STL其实是C++最值得学的东西之一。你想想看，如果没有STL，每次要用个动态数组都得自己new/delete，那得多痛苦？

这一章，我就带你快速过一遍STL的核心内容。咱们不搞理论轰炸，直接上手用。

12.1 容器：你的数据该放哪儿？

容器，说白了就是用来装数据的东西。STL提供了好几种容器，每种都有自己的脾气。我挑最常用的四个讲：vector、list、map、set。

12.1.1 vector——动态数组

vector是我个人用得最多的容器。它就是一个可以自动扩容的数组。你不需要提前知道要存多少元素，往里面push_back就行了。

#include <vector>
#include <iostream>

int main() {
    std::vector<int> scores;
    scores.push_back(85);
    scores.push_back(92);
    scores.push_back(78);

    // 像普通数组一样访问
    for (int i = 0; i < scores.size(); ++i) {
        std::cout << scores[i] << " ";
    }
    return 0;
}

嗯，这里要注意：vector在尾部插入和删除很快，但在中间插入或删除就比较慢了——因为它要移动后面的所有元素。我在项目中遇到过这种情况：一开始用vector存日志数据，后来发现频繁在头部插入导致性能瓶颈，果断换成了deque。

12.1.2 list——双向链表

list和vector正好相反。它适合频繁在中间插入和删除的场景。因为list是链表结构，插入和删除只改几个指针，不涉及元素移动。

#include <list>

std::list<std::string> tasks;
tasks.push_back("写代码");
tasks.push_front("喝咖啡");  // 头部插入，list特有
tasks.insert(++tasks.begin(), "开会");  // 在第二个位置插入

但list有个缺点：不能随机访问。你想取第5个元素？得从头一个个遍历过去。所以，如果你需要经常按索引访问元素，别用list。

12.1.3 map——键值对字典

map存储的是键值对，每个键唯一。你可以把它理解成一个字典——通过键来查找值，非常快。

#include <map>
#include <string>

std::map<std::string, int> ageMap;
ageMap["张三"] = 25;
ageMap["李四"] = 30;
ageMap["王五"] = 28;

// 查找
auto it = ageMap.find("李四");
if (it != ageMap.end()) {
    std::cout << "李四的年龄: " << it->second;
}

map内部是用红黑树实现的，所以查找、插入、删除的时间复杂度都是O(log n)。我曾经在做一个配置管理系统时，用map来存储配置项，查找速度完全够用。

12.1.4 set——集合

set就是数学里的集合——元素唯一，自动排序。它和map很像，只不过只存键，不存值。

#include <set>

std::set<int> uniqueNumbers;
uniqueNumbers.insert(3);
uniqueNumbers.insert(1);
uniqueNumbers.insert(4);
uniqueNumbers.insert(1);  // 重复插入，不会生效

// 遍历时会自动从小到大排序
for (int num : uniqueNumbers) {
    std::cout << num << " ";  // 输出: 1 3 4
}

set适合用来去重。我记得有一次处理用户ID列表，里面有很多重复的，直接扔进set里就搞定了。

12.2 迭代器：容器的通用指针

迭代器，你可以把它想象成一个智能指针，用来遍历容器里的元素。每种容器都提供了自己的迭代器，但用法是统一的。

#include <vector>
#include <iostream>

std::vector<int> vec = {10, 20, 30, 40};

// 用迭代器遍历
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";  // *it 解引用获取元素
}

// 范围for循环（底层也是迭代器）
for (int val : vec) {
    std::cout << val << " ";
}

迭代器分好几种：begin() 指向第一个元素，end() 指向最后一个元素的后面。这个设计初看有点怪，但好处是循环条件可以统一写成 it != end()。

12.3 算法：sort 和 find

STL提供了很多通用算法，放在 <algorithm> 头文件里。它们通过迭代器来操作容器，所以一套算法可以用于所有容器。

12.3.1 sort——排序

sort 默认按升序排序。它用的是快速排序的改进版，性能很好。

#include <algorithm>
#include <vector>

std::vector<int> data = {5, 2, 8, 1, 9};
std::sort(data.begin(), data.end());  // 结果: 1 2 5 8 9

// 降序排序
std::sort(data.begin(), data.end(), std::greater<int>());

sort 要求容器支持随机访问迭代器，所以 vector 和 deque 可以用，但 list 不行。list 自己有个 sort() 成员函数。

12.3.2 find——查找

find 在指定范围内查找第一个匹配的元素，返回指向它的迭代器。如果没找到，返回 end()。

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

std::vector<std::string> names = {"Alice", "Bob", "Charlie", "David"};
auto it = std::find(names.begin(), names.end(), "Charlie");

if (it != names.end()) {
    std::cout << "找到了: " << *it;
} else {
    std::cout << "没找到";
}

find 是线性查找，时间复杂度O(n)。如果你要在大量数据中频繁查找，建议用 map 或 set，它们的查找更快。

12.4 知识体系总览

下面这张图帮你理清STL核心组件之间的关系：

12.5 综合示例：用STL解决实际问题

最后，咱们来个综合例子。假设你要统计一篇文章里每个单词出现的次数，并按频率排序。用STL可以轻松搞定：

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <string>

int main() {
    std::string text = "hello world hello cpp hello stl world cpp";
    std::map<std::string, int> wordCount;
    
    // 1. 用map统计词频
    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        wordCount[word]++;
    }
    
    // 2. 把map转成vector方便排序
    std::vector<std::pair<std::string, int>> vec(wordCount.begin(), wordCount.end());
    
    // 3. 按频率降序排序
    std::sort(vec.begin(), vec.end(), [](const auto& a, const auto& b) {
        return a.second > b.second;
    });
    
    // 4. 输出结果
    for (const auto& [word, count] : vec) {
        std::cout << word << ": " << count << std::endl;
    }
    return 0;
}

你看，map负责统计，vector负责存储，sort负责排序——各司其职，配合得天衣无缝。这就是STL的魅力所在。

STL这东西，光看是学不会的。我建议你打开编译器，把上面的代码都敲一遍，改一改参数，看看输出有什么变化。动手试几次，你就摸清它们的脾气了。

---