第15天：STL容器
学习目标
掌握C++标准模板库中各种容器的使用，理解不同容器的特点、性能和使用场景。
核心知识点
1. 序列容器 (Sequence Containers)
vector - 动态数组
- 特点：动态数组，支持随机访问
- 时间复杂度：插入/删除末尾O(1)，中间O(n)，访问O(1)
- 使用场景：需要随机访问，频繁在末尾操作
- 参考资料：
list - 双向链表
- 特点：双向链表，不支持随机访问
- 时间复杂度：插入/删除O(1)，访问O(n)
- 使用场景：频繁在中间插入/删除，不需要随机访问
- 参考资料：
deque - 双端队列
- 特点：双端队列，支持两端操作
- 时间复杂度：两端插入/删除O(1)，中间O(n)，访问O(1)
- 使用场景：需要两端操作，偶尔需要随机访问
- 参考资料：
2. 关联容器 (Associative Containers)
set - 有序集合
- 特点：有序集合，元素唯一
- 时间复杂度：插入/删除/查找O(log n)
- 实现：红黑树
- 参考资料：
map - 键值对映射
- 特点：键值对映射，键唯一且有序
- 时间复杂度：插入/删除/查找O(log n)
- 实现：红黑树
- 参考资料：
3. 容器适配器 (Container Adapters)
stack - 栈
- 特点：后进先出(LIFO)
- 默认容器：deque
- 使用场景：需要栈操作，如表达式求值、括号匹配
- 参考资料：
queue - 队列
- 特点：先进先出(FIFO)
- 默认容器：deque
- 使用场景：需要队列操作，如BFS、任务调度
- 参考资料：
priority_queue - 优先队列
- 特点：优先队列，默认最大堆
- 默认容器：vector
- 使用场景：需要优先处理，如Dijkstra算法、任务调度
- 参考资料：
4. 迭代器 (Iterators)
迭代器类型
- 正向迭代器：begin(), end()
- 反向迭代器：rbegin(), rend()
- 常量迭代器：cbegin(), cend()
- 参考资料：
容器选择原则
1. 访问模式
- 随机访问：vector, deque
- 顺序访问：list, forward_list
- 键值访问：map, unordered_map
2. 插入/删除位置
- 末尾：vector, deque
- 中间：list
- 任意位置：set, map
3. 内存考虑
- 连续存储：vector, array
- 非连续存储：list, set, map
4. 性能要求
- 查找频繁：set, map, unordered_set, unordered_map
- 插入频繁：list, unordered_set, unordered_map
实用教程和文档
官方文档
优质教程
实战案例
今日练习
基础练习
- 实现一个学生成绩管理系统，使用不同的容器存储学生信息
- 编写一个表达式求值器，使用stack容器
- 实现一个任务调度系统，使用priority_queue
算法题推荐
- LeetCode 146. LRU Cache - 使用双向链表和哈希表
- LeetCode 295. Find Median from Data Stream - 使用两个优先队列
- LeetCode 239. Sliding Window Maximum - 使用双端队列
- LeetCode 380. Insert Delete GetRandom O(1) - 使用哈希表和动态数组
学习要点总结
- 容器选择：根据使用场景选择合适的容器
- 性能考虑：了解各容器的时间复杂度
- 内存管理：理解容器的内存分配策略
- 迭代器：掌握各种迭代器的使用
- 实践应用：通过实际项目加深理解
下一天预告
明天我们将学习STL算法，包括查找算法、排序算法、修改算法等，学会如何将算法与容器结合使用。