1. 序列容器（Sequence Containers）

存储元素的顺序与插入顺序一致，支持随机访问或顺序访问。

2. 关联容器（Associative Containers）

基于红黑树实现，元素按键值有序存储，查找效率高（O(log n)）。

3. 无序关联容器（Unordered Associative Containers, C++11）

基于哈希表实现，元素无序存储，平均查找效率 O(1)（最坏 O(n)）。

4. 容器适配器（Container Adapters）

基于其他容器封装，提供特定接口。

5. C++11 新增容器

• std::array：固定大小数组，替代C风格数组。
• std::forward_list：单向链表，比 std::list 更节省内存。
• 无序容器（unordered_set, unordered_map 等）：基于哈希表，提供更快的查找（但无序）。

总结

如何选择？

• 需要快速随机访问？ → std::vector 或 std::array
• 频繁头尾插入/删除？ → std::deque
• 需要快速查找？ → std::set（有序）或 std::unordered_set（无序）
• 需要键值对？ → std::map 或 std::unordered_map
• 内存敏感？ → std::forward_list（单向链表）

在C++11中，STL容器提供了一系列成员函数用于操作数据。以下是常见容器的核心函数及其示例，按容器分类说明：

1. 序列容器（Sequence Containers）

(1) std::vector

示例：

#include <vector>
std::vector<int> v = {1, 2, 3};
v.push_back(4);            // v = {1, 2, 3, 4}
v.insert(v.begin() + 1, 9); // v = {1, 9, 2, 3, 4}
v.pop_back();              // v = {1, 9, 2, 3}
int first = v.front();     // first = 1

(2) std::deque

示例：

#include <deque>
std::deque<int> d = {2, 3};
d.push_front(1);  // d = {1, 2, 3}
d.pop_back();     // d = {1, 2}

(3) std::list（双向链表）

示例：

#include <list>
std::list<int> l = {3, 1, 2};
l.sort();          // l = {1, 2, 3}
l.remove(2);       // l = {1, 3}

(4) std::forward_list（单向链表）

（仅支持单向操作，无 size() 和 back()）

示例：

#include <forward_list>
std::forward_list<int> fl = {2, 3};
fl.push_front(1);  // fl = {1, 2, 3}

(5) std::array（固定大小数组）

（不支持插入/删除，但支持迭代器）

示例：

#include <array>
std::array<int, 3> a = {1, 2, 3};
a.fill(5);  // a = {5, 5, 5}

2. 关联容器（Associative Containers）

(1) std::set / std::multiset

示例：

#include <set>
std::set<int> s = {1, 2, 3};
s.insert(4);      // s = {1, 2, 3, 4}
auto it = s.find(2); // it指向2

(2) std::map / std::multimap

示例：

#include <map>
std::map<std::string, int> m = {{"a", 1}};
m["b"] = 2;       // m = {{"a", 1}, {"b", 2}}
int x = m.at("a"); // x = 1

3. 无序容器（Unordered Containers）

(1) std::unordered_set / std::unordered_map

（接口类似关联容器，但无序）

示例：

#include <unordered_set>
std::unordered_set<int> us = {1, 2};
us.insert(3);  // us = {1, 2, 3}（顺序不确定）

4. 容器适配器（Container Adapters）

(1) std::stack

示例：

#include <stack>
std::stack<int> s;
s.push(1); s.push(2); // s = [1, 2]
int top = s.top();    // top = 2

(2) std::queue

示例：

#include <queue>
std::queue<int> q;
q.push(1); q.push(2); // q = [1, 2]
int front = q.front(); // front = 1

总结

• 序列容器：支持 push_back、insert、erase 等。
• 关联容器：提供 find、insert、lower_bound 等。
• 无序容器：类似关联容器，但基于哈希表。
• 适配器：stack 和 queue 限制操作（如栈只能 push/pop）。

在C++11中，STL容器本身并不直接提供 sort() 这样的通用算法，但可以通过 <algorithm> 头文件 提供的算法对容器进行操作。不同容器对算法的支持程度不同，主要取决于容器的存储方式（是否支持随机访问）。以下是常见算法（如 sort()、find()、binary_search() 等）在不同容器上的适用性分析：

1. 标准算法（<algorithm>）对容器的支持

(1) sort() 排序

• 支持容器：
• std::vector、std::deque、std::array（支持随机访问，可以用 std::sort）
• std::list 和 std::forward_list 有专门的成员函数 sort()（因为 std::sort 需要随机访问迭代器）
• 示例：

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5, 9};
std::sort(v.begin(), v.end()); // 升序排序

#include <list>

std::list<int> l = {3, 1, 4, 1, 5, 9};
l.sort(); // list 必须用成员函数 sort()

(2) find() 查找

• 支持容器：
• 所有序列容器（vector、deque、list、forward_list、array）
• 关联容器（set、map 等） 有更高效的 .find() 成员函数（O(log n)）
• 无序容器（unordered_set、unordered_map） 也有 .find()（平均 O(1)）
• 示例：

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};
auto it = std::find(v.begin(), v.end(), 3); // 返回迭代器

#include <set>

std::set<int> s = {1, 2, 3, 4, 5};
auto it = s.find(3); // 比 std::find 更快

(3) binary_search() 二分查找

• 支持容器：
• 已排序的 vector、deque、array（必须先 sort()）
• set、map 等关联容器 本身有序，可以直接用 .count() 或 .find()
• 示例：

#include <algorithm>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};
bool found = std::binary_search(v.begin(), v.end(), 3); // 必须已排序

#include <set>

std::set<int> s = {1, 2, 3, 4, 5};
bool found = s.count(3); // 等效于 binary_search

2. 不同容器的算法支持总结

3. 特殊成员函数

某些容器提供了专属的成员函数，比通用算法更高效：
• list / forward_list：
• sort()、merge()、reverse()、unique()
• 关联容器（set、map）：
• find()、count()、lower_bound()、upper_bound()
• 无序容器（unordered_set、unordered_map）：
• find()、count()、bucket 相关操作

4. 如何选择合适的算法？

1. 需要排序？
   • 如果是 vector/deque/array，用 std::sort。
   • 如果是 list/forward_list，用 list.sort()。
   • 关联容器本身有序，无需排序。
   • 无序容器无法排序。

2. 需要查找？
   • 关联容器用 .find()（O(log n)）。
   • 无序容器用 .find()（平均 O(1)）。
   • 序列容器用 std::find（O(n)），如果已排序可以用 binary_search。

3. 需要去重？
   • 先用 sort()，再用 std::unique（适用于 vector/deque）。
   • list/forward_list 可以直接用 unique() 成员函数。
   • set/unordered_set 本身就去重。

5. 总结

• 通用算法（如 sort、find） 适用于序列容器（vector、deque、array）。
• 关联容器 和 无序容器 有更高效的成员函数（如 .find()）。
• 链表（list、forward_list） 必须用成员函数（如 sort()）。
• <algorithm> 不修改容器结构，只操作迭代器范围。

合理选择算法能大幅提升性能，例如：
• 在 vector 上频繁查找 → 先 sort()，再用 binary_search。
• 在 unordered_map 上查找 → 直接用 .find()（比 std::find 快得多）。