【学习笔记】C++STL标准模板库核心技术详解

📝 说明：本文为C++学习笔记，AI辅助系统整理
📅 整理时间：2025年9-10月
🎯 课时：课时03 - STL标准模板库
💡 目的：掌握STL容器和算法的核心原理与应用
难度：⭐⭐⭐⭐☆ | 时长：2小时 | 类型：实战必修

---

📚 本文内容

1. STL核心架构
2. 容器详解
3. 迭代器使用
4. 算法库应用
5. 容器选择策略

---

🎯 学习目标

通过本课时的学习，你将掌握：

• STL三大组件：容器、迭代器、算法的核心原理
• 常用容器的特性、时间复杂度和使用场景
• 迭代器的分类和使用技巧
• 常用算法的实际应用和性能考量
• 面试中STL的高频考点和最佳实践

---

📚 STL核心架构

🎯 STL三大组件关系图

---

🔍 1. 容器详解

📦 序列容器（Sequence Containers）

vector - 动态数组

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

void demonstrateVector() {
    // 1. 初始化方式
    vector<int> v1;                    // 空vector
    vector<int> v2(5);                 // 5个元素，默认值0
    vector<int> v3(5, 10);             // 5个元素，值为10
    vector<int> v4{1, 2, 3, 4, 5};     // 初始化列表
    vector<int> v5(v4.begin(), v4.end()); // 迭代器范围初始化
    
    // 2. 容量管理
    cout << "大小：" << v4.size() << endl;        // 当前元素数量
    cout << "容量：" << v4.capacity() << endl;    // 已分配空间
    cout << "最大容量：" << v4.max_size() << endl; // 理论最大容量
    
    v4.reserve(100);  // 预分配空间，避免频繁重新分配
    v4.shrink_to_fit(); // 释放多余空间
    
    // 3. 元素访问
    cout << "第一个元素：" << v4[0] << endl;      // 操作符[]
    cout << "第一个元素：" << v4.at(0) << endl;   // at()有边界检查
    cout << "第一个元素：" << v4.front() << endl; // 第一个元素
    cout << "最后元素：" << v4.back() << endl;    // 最后一个元素
    
    // 4. 修改操作
    v4.push_back(6);      // 尾部添加 O(1)摊销
    v4.pop_back();        // 尾部删除 O(1)
    v4.insert(v4.begin() + 2, 99);  // 指定位置插入 O(n)
    v4.erase(v4.begin() + 2);       // 删除指定位置 O(n)
    
    // 5. 遍历方式
    // 传统for循环
    for (size_t i = 0; i < v4.size(); ++i) {
        cout << v4[i] << " ";
    }
    
    // 迭代器
    for (auto it = v4.begin(); it != v4.end(); ++it) {
        cout << *it << " ";
    }
    
    // 范围for（推荐）
    for (const auto& element : v4) {
        cout << element << " ";
    }
}

deque - 双端队列

#include <deque>

void demonstrateDeque() {
    deque<int> dq{1, 2, 3, 4, 5};
    
    // 双端操作 - deque的优势
    dq.push_front(0);    // 头部插入 O(1)
    dq.push_back(6);     // 尾部插入 O(1)
    dq.pop_front();      // 头部删除 O(1)
    dq.pop_back();       // 尾部删除 O(1)
    
    // 随机访问（类似vector）
    cout << "中间元素：" << dq[dq.size()/2] << endl;
    
    // 使用场景：需要频繁头尾操作的场景
    // 例如：滑动窗口、广度优先搜索等
}

list - 双向链表

#include <list>

void demonstrateList() {
    list<int> lst{3, 1, 4, 1, 5};
    
    // 任意位置高效插入删除
    auto it = find(lst.begin(), lst.end(), 4);
    lst.insert(it, 99);  // 在4之前插入99 O(1)
    lst.erase(it);       // 删除4 O(1)
    
    // 链表特有操作
    lst.sort();          // 原地排序
    lst.unique();        // 去除连续重复元素
    lst.reverse();       // 反转
    
    // 合并两个有序链表
    list<int> lst2{2, 6, 8};
    lst2.sort();
    lst.merge(lst2);     // 合并后lst2为空
    
    // 注意：list不支持随机访问，没有[]和at()
    // cout << lst[0];   // 错误！
}

---

🗺️ 关联容器（Associative Containers）

map - 有序键值对

#include <map>

void demonstrateMap() {
    // 1. 初始化
    map<string, int> scores;
    map<string, int> scores2{{"Alice", 95}, {"Bob", 87}, {"Charlie", 92}};
    
    // 2. 插入操作
    scores["Alice"] = 95;                    // 操作符[]
    scores.insert({"Bob", 87});              // insert方法
    scores.insert(make_pair("Charlie", 92)); // make_pair
    scores.emplace("David", 89);             // 原地构造（效率更高）
    
    // 3. 查找操作
    auto it = scores.find("Alice");
    if (it != scores.end()) {
        cout << "Alice的分数：" << it->second << endl;
    }
    
    // 检查键是否存在
    if (scores.count("Eve") > 0) {
        cout << "Eve存在" << endl;
    }
    
    // C++20: contains方法
    // if (scores.contains("Eve")) { ... }
    
    // 4. 有序遍历（map自动按键排序）
    for (const auto& [name, score] : scores) {  // 结构化绑定（C++17）
        cout << name << ": " << score << endl;
    }
    
    // 5. 范围操作
    auto lower = scores.lower_bound("Bob");   // 第一个 >= "Bob" 的元素
    auto upper = scores.upper_bound("Charlie"); // 第一个 > "Charlie" 的元素
    
    for (auto it = lower; it != upper; ++it) {
        cout << it->first << ": " << it->second << endl;
    }
}

set - 有序集合

#include <set>

void demonstrateSet() {
    set<int> numbers{3, 1, 4, 1, 5, 9, 2, 6};  // 自动去重和排序
    
    // 插入和删除
    numbers.insert(7);
    numbers.erase(1);
    
    // 查找
    if (numbers.find(5) != numbers.end()) {
        cout << "找到5" << endl;
    }
    
    // 集合操作
    set<int> set1{1, 2, 3, 4};
    set<int> set2{3, 4, 5, 6};
    set<int> result;
    
    // 交集
    set_intersection(set1.begin(), set1.end(),
                    set2.begin(), set2.end(),
                    inserter(result, result.begin()));
    
    // 并集  
    set_union(set1.begin(), set1.end(),
              set2.begin(), set2.end(),
              inserter(result, result.begin()));
}

---

🔀 无序容器（Unordered Containers）

unordered_map - 哈希表

#include <unordered_map>

void demonstrateUnorderedMap() {
    unordered_map<string, int> wordCount;
    
    // 统计单词频率的经典应用
    vector<string> words{"apple", "banana", "apple", "cherry", "banana", "apple"};
    
    for (const string& word : words) {
        wordCount[word]++;  // 自动初始化为0再递增
    }
    
    // 查看哈希表信息
    cout << "桶数量：" << wordCount.bucket_count() << endl;
    cout << "负载因子：" << wordCount.load_factor() << endl;
    cout << "最大负载因子：" << wordCount.max_load_factor() << endl;
    
    // 自定义哈希函数（用于自定义类型）
    struct Person {
        string name;
        int age;
        
        bool operator==(const Person& other) const {
            return name == other.name && age == other.age;
        }
    };
    
    struct PersonHash {
        size_t operator()(const Person& p) const {
            return hash<string>()(p.name) ^ (hash<int>()(p.age) << 1);
        }
    };
    
    unordered_map<Person, string, PersonHash> personMap;
    personMap[{"Alice", 25}] = "Engineer";
}

---

🔄 2. 迭代器详解

🎯 迭代器类型和特性

#include <iterator>

void demonstrateIterators() {
    vector<int> vec{1, 2, 3, 4, 5};
    list<int> lst{1, 2, 3, 4, 5};
    
    // 1. 随机访问迭代器（vector, deque）
    auto vec_it = vec.begin();
    vec_it += 3;           // 支持算术运算
    vec_it = vec_it - 1;   // 支持减法
    int diff = vec.end() - vec.begin();  // 支持距离计算
    
    // 2. 双向迭代器（list, map, set）
    auto lst_it = lst.begin();
    ++lst_it;              // 支持前进
    --lst_it;              // 支持后退
    // lst_it += 2;        // 不支持算术运算
    
    // 3. 迭代器适配器
    // 反向迭代器
    for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        cout << *rit << " ";  // 逆序输出
    }
    
    // 插入迭代器
    vector<int> dest;
    copy(vec.begin(), vec.end(), back_inserter(dest));  // 尾部插入
    
    list<int> dest2;
    copy(vec.begin(), vec.end(), front_inserter(dest2)); // 头部插入
    
    // 4. 迭代器失效问题
    vector<int> v{1, 2, 3, 4, 5};
    auto it = v.begin() + 2;  // 指向元素3
    
    v.push_back(6);           // 可能导致重新分配，it失效
    // cout << *it;           // 危险！可能崩溃
    
    // 安全做法：记录索引而非迭代器
    size_t index = 2;
    v.push_back(6);
    cout << v[index] << endl;  // 安全
}

---

⚙️ 3. 算法详解

🔍 查找算法

#include <algorithm>

void demonstrateSearchAlgorithms() {
    vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    
    // 1. 线性查找
    auto it = find(vec.begin(), vec.end(), 5);
    if (it != vec.end()) {
        cout << "找到5，位置：" << distance(vec.begin(), it) << endl;
    }
    
    // 查找满足条件的元素
    auto it2 = find_if(vec.begin(), vec.end(), [](int x) { return x > 5; });
    if (it2 != vec.end()) {
        cout << "第一个大于5的元素：" << *it2 << endl;
    }
    
    // 2. 二分查找（需要先排序）
    vector<int> sorted_vec = vec;
    sort(sorted_vec.begin(), sorted_vec.end());
    
    bool found = binary_search(sorted_vec.begin(), sorted_vec.end(), 5);
    cout << "二分查找5：" << (found ? "找到" : "未找到") << endl;
    
    // 查找插入位置
    auto pos = lower_bound(sorted_vec.begin(), sorted_vec.end(), 5);
    cout << "5应该插入的位置：" << distance(sorted_vec.begin(), pos) << endl;
    
    // 3. 计数
    int count = count(vec.begin(), vec.end(), 1);
    cout << "1出现的次数：" << count << endl;
    
    int count_if = count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
    cout << "偶数的个数：" << count_if << endl;
}

🔄 修改算法

void demonstrateModifyingAlgorithms() {
    vector<int> vec{1, 2, 3, 4, 5};
    vector<int> dest(vec.size());
    
    // 1. 复制
    copy(vec.begin(), vec.end(), dest.begin());
    
    // 条件复制
    vector<int> even_nums;
    copy_if(vec.begin(), vec.end(), back_inserter(even_nums), 
            [](int x) { return x % 2 == 0; });
    
    // 2. 变换
    vector<int> squares(vec.size());
    transform(vec.begin(), vec.end(), squares.begin(), 
              [](int x) { return x * x; });
    
    // 两个序列的变换
    vector<int> vec2{6, 7, 8, 9, 10};
    vector<int> sums(vec.size());
    transform(vec.begin(), vec.end(), vec2.begin(), sums.begin(),
              [](int a, int b) { return a + b; });
    
    // 3. 填充
    vector<int> filled(10);
    fill(filled.begin(), filled.end(), 42);
    
    // 生成
    vector<int> generated(10);
    int counter = 0;
    generate(generated.begin(), generated.end(), [&counter]() { return ++counter; });
    
    // 4. 替换
    vector<int> replaced = vec;
    replace(replaced.begin(), replaced.end(), 3, 99);  // 把3替换为99
    
    replace_if(replaced.begin(), replaced.end(), 
               [](int x) { return x % 2 == 0; }, 0);   // 偶数替换为0
    
    // 5. 删除
    vector<int> removed{1, 2, 3, 2, 4, 2, 5};
    auto new_end = remove(removed.begin(), removed.end(), 2);  // 移除所有2
    removed.erase(new_end, removed.end());  // 真正删除
    
    // 或者使用erase-remove idiom
    removed.erase(remove(removed.begin(), removed.end(), 4), removed.end());
}

📊 排序和相关算法

void demonstrateSortingAlgorithms() {
    vector<int> vec{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    
    // 1. 完全排序
    sort(vec.begin(), vec.end());  // 升序
    sort(vec.begin(), vec.end(), greater<int>());  // 降序
    
    // 自定义比较函数
    vector<string> names{"Alice", "Bob", "Charlie", "David"};
    sort(names.begin(), names.end(), [](const string& a, const string& b) {
        return a.length() < b.length();  // 按长度排序
    });
    
    // 2. 部分排序
    vector<int> partial{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    partial_sort(partial.begin(), partial.begin() + 3, partial.end());  // 只排序前3个最小的
    
    // 3. nth_element（快速选择）
    vector<int> nth_vec{3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    nth_element(nth_vec.begin(), nth_vec.begin() + 5, nth_vec.end());
    cout << "第5小的元素：" << nth_vec[5] << endl;
    
    // 4. 堆操作
    vector<int> heap{3, 1, 4, 1, 5, 9, 2, 6};
    make_heap(heap.begin(), heap.end());  // 建立最大堆
    
    heap.push_back(10);
    push_heap(heap.begin(), heap.end());  // 添加元素到堆
    
    pop_heap(heap.begin(), heap.end());   // 移除堆顶
    heap.pop_back();
    
    sort_heap(heap.begin(), heap.end());  // 堆排序
    
    // 5. 集合操作（需要有序序列）
    vector<int> set1{1, 2, 3, 4, 5};
    vector<int> set2{3, 4, 5, 6, 7};
    vector<int> result;
    
    // 并集
    set_union(set1.begin(), set1.end(), set2.begin(), set2.end(),
              back_inserter(result));
    
    result.clear();
    // 交集
    set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(),
                    back_inserter(result));
    
    result.clear();
    // 差集
    set_difference(set1.begin(), set1.end(), set2.begin(), set2.end(),
                  back_inserter(result));
}

---

🎯 容器选择指南

📊 性能对比表

操作	vector	deque	list	map	unordered_map
随机访问	O(1)	O(1)	O(n)	O(log n)	O(1)平均
头部插入	O(n)	O(1)	O(1)	O(log n)	O(1)平均
尾部插入	O(1)摊销	O(1)	O(1)	O(log n)	O(1)平均
中间插入	O(n)	O(n)	O(1)	O(log n)	N/A
查找	O(n)	O(n)	O(n)	O(log n)	O(1)平均
内存局部性	最好	好	差	中等	中等

🎯 选择建议

// 1. 需要频繁随机访问 → vector
vector<int> data;
cout << data[100] << endl;  // O(1)访问

// 2. 需要频繁头尾操作 → deque
deque<int> queue;
queue.push_front(1);
queue.push_back(2);

// 3. 需要频繁中间插入删除 → list
list<int> timeline;
auto it = timeline.begin();
advance(it, 10);
timeline.insert(it, new_event);  // O(1)插入

// 4. 需要有序存储和查找 → map/set
map<string, int> scores;
auto range = scores.equal_range("Alice");  // 范围查询

// 5. 需要快速查找，不关心顺序 → unordered_map/unordered_set
unordered_map<string, int> cache;
if (cache.find("key") != cache.end()) {  // O(1)查找
    // 处理缓存命中
}

---

🎯 面试高频考点

🔥 经典面试题

1. vector的扩容机制？

void demonstrateVectorGrowth() {
    vector<int> v;
    cout << "初始容量：" << v.capacity() << endl;
    
    for (int i = 0; i < 10; ++i) {
        v.push_back(i);
        cout << "大小：" << v.size() << ", 容量：" << v.capacity() << endl;
    }
    
    // 通常按1.5或2的倍数增长
    // 扩容时：分配新空间 → 复制元素 → 释放旧空间
}

2. map和unordered_map的区别？

"map基于红黑树实现，有序，O(log n)操作；
unordered_map基于哈希表，无序，O(1)平均操作。
选择依据：需要有序或范围查询用map，
只需要快速查找用unordered_map。"

3. 迭代器失效的情况？

void demonstrateIteratorInvalidation() {
    vector<int> v{1, 2, 3, 4, 5};
    
    // 1. vector扩容导致失效
    auto it1 = v.begin();
    v.push_back(6);  // 可能扩容，it1失效
    
    // 2. 删除元素导致失效
    auto it2 = v.begin() + 2;
    v.erase(it2);  // it2及其后面的迭代器失效
    
    // 3. list删除不影响其他迭代器
    list<int> lst{1, 2, 3, 4, 5};
    auto lst_it1 = lst.begin();
    auto lst_it2 = next(lst_it1);
    lst.erase(lst_it1);  // 只有lst_it1失效，lst_it2仍有效
}

4. STL算法的时间复杂度？

"sort: O(n log n)
find: O(n)
binary_search: O(log n) (需要有序)
lower_bound/upper_bound: O(log n)
make_heap: O(n)
push_heap/pop_heap: O(log n)"

---

🚀 实际应用案例

📝 LRU缓存实现

#include <unordered_map>
#include <list>

class LRUCache {
private:
    int capacity;
    list<pair<int, int>> cache;  // 双向链表存储键值对
    unordered_map<int, list<pair<int, int>>::iterator> map;  // 哈希表存储迭代器
    
public:
    LRUCache(int cap) : capacity(cap) {}
    
    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) {
            return -1;  // 未找到
        }
        
        // 移动到头部
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 更新值并移动到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
            return;
        }
        
        if (cache.size() >= capacity) {
            // 删除尾部元素
            int last_key = cache.back().first;
            cache.pop_back();
            map.erase(last_key);
        }
        
        // 在头部插入新元素
        cache.emplace_front(key, value);
        map[key] = cache.begin();
    }
};

🎯 单词频率统计

#include <sstream>
#include <algorithm>

class WordCounter {
public:
    map<string, int> countWords(const string& text) {
        map<string, int> wordCount;
        istringstream iss(text);
        string word;
        
        while (iss >> word) {
            // 转换为小写
            transform(word.begin(), word.end(), word.begin(), ::tolower);
            
            // 移除标点符号
            word.erase(remove_if(word.begin(), word.end(), ::ispunct), word.end());
            
            if (!word.empty()) {
                wordCount[word]++;
            }
        }
        
        return wordCount;
    }
    
    vector<pair<string, int>> getTopWords(const map<string, int>& wordCount, int n) {
        vector<pair<string, int>> words(wordCount.begin(), wordCount.end());
        
        // 按频率降序排序
        sort(words.begin(), words.end(), [](const auto& a, const auto& b) {
            return a.second > b.second;
        });
        
        if (words.size() > n) {
            words.resize(n);
        }
        
        return words;
    }
};

---

🎉 课时总结

通过本课时的学习，我们全面掌握了STL的核心内容：

• ✅ 容器掌握：理解了各种容器的特性和适用场景
• ✅ 迭代器应用：学会了迭代器的使用技巧和注意事项
• ✅ 算法运用：掌握了常用算法的应用和性能特点
• ✅ 性能分析：了解了时间复杂度和内存使用特点
• ✅ 实战应用：通过案例学会了STL在实际项目中的应用

STL是C++编程的利器，熟练掌握STL不仅能提高编程效率，还能写出更加安全、高效的代码。在面试和实际开发中，STL的重要性不言而喻。

下一课时，我们将学习C++的内存管理和智能指针，了解如何写出更加安全的C++代码。

💡 最佳实践：

• 优先使用STL算法而非手写循环
• 选择合适的容器，避免性能瓶颈
• 注意迭代器失效问题
• 善用lambda表达式简化代码
• 利用auto关键字提高代码可读性