C++标准模板库(STL)深度解析：容器、算法与迭代器

bicheng/2025/9/28 1:06:36/文章来源:href="https://blog.51cto.com/u_15511034/14130682" target="_blank"

STL：C++编程的瑞士军刀

欢迎来到C++标准模板库(STL)的奇妙世界！STL是C++标准库的核心组成部分，提供了一套丰富的通用数据结构和算法，极大地提升了开发效率和代码质量。想象STL就像一个精心组织的工具箱，里面装满了各种高效可靠的"工具"——从存储数据的容器到处理数据的算法，再到连接两者的迭代器。

STL的设计哲学基于三个核心概念：容器管理数据集合，算法执行操作，迭代器在两者之间建立桥梁。这种分离设计使得算法可以独立于容器工作，大大提高了代码的复用性。无论你是开发游戏、金融系统还是嵌入式应用，STL都能提供强大的支持。

序列容器：线性数据结构的实现

vector：动态数组

vector是最常用的序列容器，提供快速的随机访问和尾部插入/删除操作：

#include <iostream>
#include <vector>int main() {// 创建和初始化vectorstd::vector<int> numbers = {1, 2, 3, 4, 5};// 添加元素numbers.push_back(6);numbers.insert(numbers.begin(), 0);// 访问元素std::cout << "第一个元素: " << numbers.front() << std::endl;std::cout << "最后一个元素: " << numbers.back() << std::endl;std::cout << "第三个元素: " << numbers[2] << std::endl; // 不检查边界std::cout << "第四个元素: " << numbers.at(3) << std::endl; // 检查边界// 遍历vectorstd::cout << "所有元素: ";for (int num : numbers) {std::cout << num << " ";}std::cout << std::endl;// 容量信息std::cout << "大小: " << numbers.size() << std::endl;std::cout << "容量: " << numbers.capacity() << std::endl;// 删除元素numbers.pop_back();numbers.erase(numbers.begin() + 2);// 清空vectornumbers.clear();return 0;
}

deque：双端队列

deque支持高效的头部和尾部插入/删除操作：

#include <iostream>
#include <deque>int main() {std::deque<std::string> lines;// 两端添加元素lines.push_back("World");lines.push_front("Hello");lines.push_back("!");// 遍历dequefor (const auto &line : lines) {std::cout << line << " ";}std::cout << std::endl;// 随机访问std::cout << "第二个元素: " << lines[1] << std::endl;return 0;
}

list与forward_list：链表实现

list是双向链表，forward_list是单向链表：

#include <iostream>
#include <list>
#include <forward_list>int main() {// 双向链表std::list<int> myList = {1, 2, 3};myList.push_front(0);myList.push_back(4);// 在中间插入元素(高效)auto it = myList.begin();std::advance(it, 2);myList.insert(it, 10);std::cout << "双向链表: ";for (int n : myList) {std::cout << n << " ";}std::cout << std::endl;// 单向链表std::forward_list<int> flist = {1, 2, 3};flist.push_front(0); // 只有push_frontstd::cout << "单向链表: ";for (int n : flist) {std::cout << n << " ";}std::cout << std::endl;return 0;
}

关联容器：有序与无序集合

set与multiset：有序集合

set存储唯一元素，multiset允许重复：

#include <iostream>
#include <set>
#include <string>int main() {std::set<std::string> words;words.insert("apple");words.insert("banana");words.insert("orange");words.insert("apple"); // 不会插入重复元素std::cout << "单词集合: ";for (const auto &word : words) {std::cout << word << " ";}std::cout << std::endl;// 查找元素auto search = words.find("banana");if (search != words.end()) {std::cout << "找到了banana" << std::endl;}// multiset示例std::multiset<int> numbers = {1, 2, 2, 3, 4, 4, 4};std::cout << "数字多重集合: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;std::cout << "数字4出现的次数: " << numbers.count(4) << std::endl;return 0;
}

map与multimap：键值对容器

map存储唯一键值对，multimap允许重复键：

#include <iostream>
#include <map>
#include <string>int main() {std::map<std::string, int> ageMap;// 插入元素ageMap["Alice"] = 25;ageMap["Bob"] = 30;ageMap.insert({"Charlie", 28});// 遍历mapstd::cout << "年龄映射表:" << std::endl;for (const auto &pair : ageMap) {std::cout << pair.first << ": " << pair.second << "岁" << std::endl;}// 查找元素if (ageMap.find("Bob") != ageMap.end()) {std::cout << "Bob的年龄: " << ageMap["Bob"] << std::endl;}// multimap示例std::multimap<std::string, std::string> teamMap;teamMap.insert({"开发部", "张三"});teamMap.insert({"开发部", "李四"});teamMap.insert({"市场部", "王五"});std::cout << "\n团队成员:" << std::endl;for (const auto &member : teamMap) {std::cout << member.first << " - " << member.second << std::endl;}return 0;
}

无序容器(C++11)：基于哈希的实现

无序容器提供更快的平均访问速度：

#include <iostream>
#include <unordered_set>
#include <unordered_map>int main() {// 无序集合std::unordered_set<std::string> uset = {"red", "green", "blue"};uset.insert("yellow");std::cout << "颜色集合: ";for (const auto &color : uset) {std::cout << color << " ";}std::cout << std::endl;// 无序映射std::unordered_map<std::string, double> umap = {{"pi", 3.14159},{"e", 2.71828}};umap["sqrt2"] = 1.41421;std::cout << "\n常数表:" << std::endl;for (const auto &pair : umap) {std::cout << pair.first << ": " << pair.second << std::endl;}return 0;
}

容器适配器：特殊用途的接口

stack：后进先出(LIFO)结构

#include <iostream>
#include <stack>int main() {std::stack<int> s;// 压栈s.push(1);s.push(2);s.push(3);// 查看栈顶std::cout << "栈顶元素: " << s.top() << std::endl;// 出栈std::cout << "出栈顺序: ";while (!s.empty()) {std::cout << s.top() << " ";s.pop();}std::cout << std::endl;return 0;
}

queue：先进先出(FIFO)结构

#include <iostream>
#include <queue>int main() {std::queue<std::string> q;// 入队q.push("第一人");q.push("第二人");q.push("第三人");// 查看队首和队尾std::cout << "队首: " << q.front() << std::endl;std::cout << "队尾: " << q.back() << std::endl;// 出队std::cout << "处理顺序: ";while (!q.empty()) {std::cout << q.front() << " ";q.pop();}std::cout << std::endl;return 0;
}

priority_queue：优先级队列

#include <iostream>
#include <queue>
#include <vector>int main() {// 最大堆(默认)std::priority_queue<int> maxHeap;maxHeap.push(3);maxHeap.push(1);maxHeap.push(4);maxHeap.push(2);std::cout << "最大堆出队顺序: ";while (!maxHeap.empty()) {std::cout << maxHeap.top() << " ";maxHeap.pop();}std::cout << std::endl;// 最小堆std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;minHeap.push(3);minHeap.push(1);minHeap.push(4);minHeap.push(2);std::cout << "最小堆出队顺序: ";while (!minHeap.empty()) {std::cout << minHeap.top() << " ";minHeap.pop();}std::cout << std::endl;return 0;
}

STL算法：强大的数据处理能力

STL提供了超过100种算法，用于搜索、排序、计数、修改等操作。

常用算法示例

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>int main() {std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6};// 排序std::sort(numbers.begin(), numbers.end());std::cout << "排序后: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;// 反转std::reverse(numbers.begin(), numbers.end());std::cout << "反转后: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;// 查找auto result = std::find(numbers.begin(), numbers.end(), 5);if (result != numbers.end()) {std::cout << "找到5在位置: " << (result - numbers.begin()) << std::endl;}// 计数int ones = std::count(numbers.begin(), numbers.end(), 1);std::cout << "1出现的次数: " << ones << std::endl;// 累加int sum = std::accumulate(numbers.begin(), numbers.end(), 0);std::cout << "总和: " << sum << std::endl;// lambda表达式与算法std::cout << "偶数: ";std::for_each(numbers.begin(), numbers.end(), [](int n) {if (n % 2 == 0) {std::cout << n << " ";}});std::cout << std::endl;// 移除重复元素std::sort(numbers.begin(), numbers.end());auto last = std::unique(numbers.begin(), numbers.end());numbers.erase(last, numbers.end());std::cout << "去重后: ";for (int n : numbers) {std::cout << n << " ";}std::cout << std::endl;return 0;
}

算法分类概览

非修改序列算法：find, count, search, for_each等
修改序列算法：copy, move, transform, replace等
排序与相关算法：sort, stable_sort, partial_sort, nth_element等
数值算法：accumulate, inner_product, partial_sum, adjacent_difference等

迭代器：容器与算法的桥梁

迭代器提供统一的方式来遍历容器中的元素。

迭代器类别

输入迭代器：只读，单遍扫描
输出迭代器：只写，单遍扫描
前向迭代器：读写，多遍扫描
双向迭代器：可前后移动
随机访问迭代器：支持跳跃访问

迭代器使用示例

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};// 使用迭代器遍历std::cout << "向量元素: ";for (auto it = vec.begin(); it != vec.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 反向迭代器std::cout << "反向遍历: ";for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {std::cout << *rit << " ";}std::cout << std::endl;// 迭代器与算法std::list<int> lst = {5, 3, 1, 4, 2};lst.sort(); // list有自己的sort方法std::cout << "链表排序后: ";for (int n : lst) {std::cout << n << " ";}std::cout << std::endl;// 使用advance和distanceauto it = lst.begin();std::advance(it, 2); // 移动迭代器std::cout << "第三个元素: " << *it << std::endl;auto dist = std::distance(lst.begin(), it);std::cout << "距离开始位置: " << dist << std::endl;// 插入迭代器std::vector<int> source = {1, 2, 3};std::vector<int> target;std::copy(source.begin(), source.end(), std::back_inserter(target));std::cout << "目标向量: ";for (int n : target) {std::cout << n << " ";}std::cout << std::endl;return 0;
}

实践项目：单词频率统计器

让我们综合运用STL组件，构建一个统计文本中单词频率的程序：

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <iomanip>// 转换字符串为小写并移除标点
std::string normalizeWord(const std::string &word) {std::string result;for (char ch : word) {if (isalpha(ch)) {result += tolower(ch);}}return result;
}void countWordFrequencies(const std::string &text) {std::map<std::string, int> wordCounts;// 分割文本为单词std::string currentWord;for (char ch : text) {if (isalpha(ch)) {currentWord += ch;} else if (!currentWord.empty()) {std::string normalized = normalizeWord(currentWord);if (!normalized.empty()) {wordCounts[normalized]++;}currentWord.clear();}}// 处理最后一个单词if (!currentWord.empty()) {std::string normalized = normalizeWord(currentWord);if (!normalized.empty()) {wordCounts[normalized]++;}}// 将结果转移到vector以便排序std::vector<std::pair<std::string, int>> wordVector(wordCounts.begin(), wordCounts.end());// 按频率降序排序std::sort(wordVector.begin(), wordVector.end(),[](const auto &a, const auto &b) {return a.second > b.second;});// 打印结果std::cout << std::left << std::setw(15) << "单词" << "频率" << std::endl;std::cout << std::string(25, '-') << std::endl;for (const auto &pair : wordVector) {std::cout << std::left << std::setw(15) << pair.first << pair.second << std::endl;}
}int main() {std::string text = R"(C++ is a general-purpose programming language created by Bjarne Stroustrup as an extension of the C programming language. The language has expanded significantly over time, and modern C++ now has object-oriented, generic, and functional features in addition to facilities for low-level memory manipulation. C++ is almost always implemented as a compiled language.)";countWordFrequencies(text);return 0;
}

这个程序展示了：