好的，我们来学习C++ STL中最常用的几种容器。STL（Standard Template Library）提供了多种高效的容器类型，用于存储和管理数据。

---

1. vector：动态数组

• 概念：可变大小的数组，支持随机访问（通过下标 $i$）。
• 适用场景：需要频繁访问元素，尾部插入/删除较多时。
• 基本操作：

  #include <vector>
  std::vector<int> vec;          // 创建空vector
  vec.push_back(10);             // 尾部插入元素
  int x = vec[0];                // 访问元素（需确保下标有效）
  vec.pop_back();                // 删除尾部元素
  size_t len = vec.size();       // 获取元素数量
  

---

2. list：双向链表

• 概念：元素通过指针双向链接，插入/删除效率高，但不支持随机访问。
• 适用场景：频繁在任意位置插入/删除。
• 基本操作：

  #include <list>
  std::list<int> lst;
  lst.push_back(20);             // 尾部插入
  lst.push_front(5);             // 头部插入
  lst.pop_front();               // 删除头部元素
  auto it = lst.begin();         // 获取迭代器（指向首元素）
  ++it;                          // 移动迭代器
  

---

3. map：有序键值对

• 概念：基于红黑树实现，按键排序（默认升序），键唯一。
• 适用场景：需通过键快速查找/更新值。
• 基本操作：

  #include <map>
  std::map<std::string, int> scores;
  scores["Alice"] = 90;          // 插入或更新键值对
  auto it = scores.find("Bob");  // 查找键（返回迭代器）
  if (it != scores.end()) {
      int score = it->second;    // 获取值
  }
  scores.erase("Alice");         // 删除键值对
  

---

4. set：有序唯一值集合

• 概念：存储唯一值并自动排序。
• 适用场景：去重或有序集合操作。
• 基本操作：

  #include <set>
  std::set<int> uniqueNums;
  uniqueNums.insert(42);         // 插入元素
  if (uniqueNums.count(42)) {    // 检查元素是否存在
      uniqueNums.erase(42);      // 删除元素
  }
  

---

5. queue：队列（FIFO）

• 概念：先进先出，只允许在队尾插入、队首删除。
• 适用场景：任务调度、广度优先搜索。
• 基本操作：

  #include <queue>
  std::queue<int> q;
  q.push(10);                    // 入队
  int front = q.front();         // 访问队首
  q.pop();                       // 出队
  

---

迭代器遍历（通用）

所有容器均支持迭代器遍历：

std::vector<int> vec = {1, 2, 3};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " "; // 输出：1 2 3
}

---

总结

容器	特点	时间复杂度（平均）
vector	动态数组，随机访问	尾部插入 $O(1)$
list	双向链表	任意插入 $O(1)$
map	键值对，有序	查找 $O(\log n)$
set	唯一值集合，有序	插入 $O(\log n)$
queue	先进先出	入队/出队 $O(1)$

选择合适的容器能大幅提升代码效率和可读性！