C++ STL容器详解（十种常用容器）

C++ 标准模板库（STL）提供了一系列高效的数据结构容器，用于存储和管理数据。这些容器分为顺序容器、关联容器和容器适配器。以下将详细介绍十种常用容器：vector、list、deque、stack、queue、priority_queue、set、multiset、map 和 multimap。每个容器的介绍包括特性、时间复杂度、使用场景和代码示例。

---

1. vector（向量）

vector 是一个动态数组，支持随机访问。它在内存中是连续的，允许在尾部高效插入和删除元素。

• 特性：顺序容器，可动态调整大小。
• 时间复杂度：
  • 随机访问：$O(1)$
  • 尾部插入/删除：$O(1)$（平均情况）
  • 中间插入/删除：$O(n)$
• 使用场景：需要随机访问的场景，如数组替代品。
• 代码示例：

#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec = {1, 2, 3}; // 初始化
    vec.push_back(4); // 尾部插入，O(1)
    std::cout << vec[0] << std::endl; // 随机访问，O(1)
    return 0;
}

---

2. list（双向链表）

list 是一个双向链表，支持在任意位置高效插入和删除元素，但不支持随机访问。

• 特性：顺序容器，元素不连续存储。
• 时间复杂度：
  • 插入/删除任意位置：$O(1)$（如果已知迭代器）
  • 随机访问：$O(n)$
• 使用场景：需要频繁在中间插入或删除元素的场景。
• 代码示例：

#include <list>
#include <iostream>
int main() {
    std::list<int> lst = {1, 2, 3}; // 初始化
    auto it = lst.begin();
    ++it;
    lst.insert(it, 4); // 在位置插入，O(1)
    for (int n : lst) std::cout << n << " "; // 遍历
    return 0;
}

---

3. deque（双端队列）

deque 是一个双端队列，支持在头部和尾部高效插入和删除元素，同时支持随机访问。

• 特性：顺序容器，分段连续存储。
• 时间复杂度：
  • 头部/尾部插入/删除：$O(1)$
  • 随机访问：$O(1)$
• 使用场景：需要频繁在两端操作元素的场景，如队列和栈的组合。
• 代码示例：

#include <deque>
#include <iostream>
int main() {
    std::deque<int> dq = {1, 2, 3}; // 初始化
    dq.push_front(0); // 头部插入，O(1)
    dq.push_back(4); // 尾部插入，O(1)
    std::cout << dq[1] << std::endl; // 随机访问，O(1)
    return 0;
}

---

4. stack（栈）

stack 是一个容器适配器，基于其他容器（如 deque 或 list）实现后进先出（LIFO）操作。

• 特性：容器适配器，只允许在顶部插入和删除。
• 时间复杂度：
  • 插入（push）：$O(1)$
  • 删除（pop）：$O(1)$
• 使用场景：需要 LIFO 行为的场景，如函数调用栈。
• 代码示例：

#include <stack>
#include <iostream>
int main() {
    std::stack<int> st;
    st.push(1); // 压栈，O(1)
    st.push(2);
    std::cout << st.top() << std::endl; // 查看栈顶，O(1)
    st.pop(); // 出栈，O(1)
    return 0;
}

---

5. queue（队列）

queue 是一个容器适配器，基于其他容器（如 deque）实现先进先出（FIFO）操作。

• 特性：容器适配器，只允许在尾部插入和头部删除。
• 时间复杂度：
  • 插入（push）：$O(1)$
  • 删除（pop）：$O(1)$
• 使用场景：需要 FIFO 行为的场景，如任务调度。
• 代码示例：

#include <queue>
#include <iostream>
int main() {
    std::queue<int> q;
    q.push(1); // 入队，O(1)
    q.push(2);
    std::cout << q.front() << std::endl; // 查看队头，O(1)
    q.pop(); // 出队，O(1)
    return 0;
}

---

6. priority_queue（优先队列）

priority_queue 是一个容器适配器，基于堆实现，元素按优先级排序（默认最大堆）。

• 特性：容器适配器，元素有序。
• 时间复杂度：
  • 插入（push）：$O(\log n)$
  • 删除（pop）：$O(\log n)$
  • 访问顶部元素：$O(1)$
• 使用场景：需要快速访问最大或最小元素的场景，如 Dijkstra 算法。
• 代码示例：

#include <queue>
#include <iostream>
int main() {
    std::priority_queue<int> pq; // 默认最大堆
    pq.push(3); // 插入，O(log n)
    pq.push(1);
    pq.push(2);
    std::cout << pq.top() << std::endl; // 顶部元素，O(1)
    pq.pop(); // 删除顶部，O(log n)
    return 0;
}

---

7. set（集合）

set 是一个关联容器，存储唯一元素，基于红黑树实现，元素自动排序。

• 特性：关联容器，元素唯一且有序。
• 时间复杂度：
  • 插入/删除：$O(\log n)$
  • 查找：$O(\log n)$
• 使用场景：需要唯一元素和快速查找的场景。
• 代码示例：

#include <set>
#include <iostream>
int main() {
    std::set<int> s;
    s.insert(3); // 插入，O(log n)
    s.insert(1);
    s.insert(2);
    if (s.find(2) != s.end()) std::cout << "Found" << std::endl; // 查找，O(log n)
    return 0;
}

---

8. multiset（多重集合）

multiset 类似于 set，但允许重复元素。

• 特性：关联容器，元素可重复且有序。
• 时间复杂度：
  • 插入/删除：$O(\log n)$
  • 查找：$O(\log n)$
• 使用场景：需要重复元素和排序的场景。
• 代码示例：

#include <set>
#include <iostream>
int main() {
    std::multiset<int> ms;
    ms.insert(1); // 插入，O(log n)
    ms.insert(1); // 允许重复
    std::cout << ms.count(1) << std::endl; // 计数，O(log n)
    return 0;
}

---

9. map（映射）

map 是一个关联容器，存储键值对，键唯一且有序，基于红黑树实现。

• 特性：关联容器，键唯一，支持通过键访问值。
• 时间复杂度：
  • 插入/删除：$O(\log n)$
  • 查找：$O(\log n)$
• 使用场景：需要键值对映射的场景，如字典。
• 代码示例：

#include <map>
#include <iostream>
int main() {
    std::map<std::string, int> m;
    m["apple"] = 1; // 插入或更新，O(log n)
    m["banana"] = 2;
    std::cout << m["apple"] << std::endl; // 查找，O(log n)
    return 0;
}

---

10. multimap（多重映射）

multimap 类似于 map，但允许重复键。

• 特性：关联容器，键可重复且有序。
• 时间复杂度：
  • 插入/删除：$O(\log n)$
  • 查找：$O(\log n)$
• 使用场景：需要一键多值的场景。
• 代码示例：

#include <map>
#include <iostream>
int main() {
    std::multimap<std::string, int> mm;
    mm.insert({"fruit", 1}); // 插入，O(log n)
    mm.insert({"fruit", 2}); // 键可重复
    auto range = mm.equal_range("fruit"); // 查找所有值
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << " ";
    }
    return 0;
}

---

总结

STL容器提供了高效的数据管理方案：

• 顺序容器：vector、list、deque 支持灵活的元素访问。
• 容器适配器：stack、queue、priority_queue 基于其他容器实现特定行为。
• 关联容器：set、multiset、map、multimap 提供有序存储和快速查找。

选择合适的容器取决于具体需求，如随机访问、插入频率或元素唯一性。使用这些容器时，注意时间复杂度以优化性能。C++ STL 的完整实现可参考标准库文档。