C++ STL 容器入门与速查

C++ 标准库提供了常用容器和算法。选择容器时先想清楚需要什么：按下标访问、先进先出、自动排序、键值查找，还是只需要快速平均查找。

1. 常见容器如何选择

容器 主要特点 常见操作的复杂度
vector 连续动态数组，支持下标访问 尾部插入均摊 O(1)，中间插入/删除 O(n)
stack 后进先出 栈顶操作 O(1)
queue 先进先出 队首、队尾操作 O(1)
set / multiset 有序集合；前者去重，后者允许重复 查找、插入、删除 O(log n)
priority_queue 每次取出优先级最高的元素 查看堆顶 O(1)，插入/弹出 O(log n)
map 按键排序的键值对 查找、插入、删除 O(log n)
unordered_map 哈希表，不保证遍历顺序 平均 O(1)，最坏可能 O(n)

2. vector

适合需要按下标访问的序列。元素连续存放，v[i] 是 O(1)；使用 at(i) 会进行边界检查。

1
2
3
4
5
6
7
8
9
10
11
vector<int> v(10, 0); // 10 个 0
v.push_back(5);
v.pop_back();
bool isEmpty = v.empty();
size_t count = v.size();

auto it = find(v.begin(), v.end(), 3); // 线性查找，O(n)
if (it != v.end()) v.erase(it);       // 删除后续元素左移，O(n)

sort(v.begin(), v.end());
reverse(v.begin(), v.end());

插入或删除可能使指向 vector 元素的迭代器、指针和引用失效。具体失效范围取决于操作位置和是否重新分配内存；修改后不要继续使用可能失效的迭代器。

3. stack 和 queue

1
2
3
4
5
6
7
8
9
stack<int> st;
st.push(10);
int top = st.top();
st.pop();

queue<int> q;
q.push(10);
int first = q.front();
q.pop();

pop() 只移除元素，不返回元素值；读取前应确认容器非空。队列还可用 back() 查看队尾。

4. set 和 multiset

两者默认按升序维护元素。set 不允许重复值，multiset 允许重复值。

1
2
3
4
5
6
7
8
9
10
set<int> s{3, 1, 3};       // 保存 1、3
multiset<int> ms{3, 1, 3}; // 保存 1、3、3

s.insert(5);
auto it = s.find(3);
if (it != s.end()) s.erase(it); // 删除迭代器对应的一个元素

ms.erase(3); // 删除 multiset 中所有值为 3 的元素
auto one = ms.find(3);
if (one != ms.end()) ms.erase(one); // 只删除一个 3

对于有序容器，lower_bound(x) 返回第一个大于等于 x 的位置，upper_bound(x) 返回第一个大于 x 的位置。迭代器可能等于 end()，解引用前必须检查。

5. priority_queue

默认是大根堆，top() 返回最大元素。用 greater<int> 可以创建小根堆：

1
2
3
4
5
6
7
8
9
priority_queue<int> maxHeap;
maxHeap.push(4);
maxHeap.push(9);
int largest = maxHeap.top(); // 9

priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(4);
minHeap.push(9);
int smallest = minHeap.top(); // 4

堆只保证堆顶是当前优先级最高的元素，不支持遍历时按完整顺序访问。

6. map 和 unordered_map

两者都保存键值对。map 按键排序；unordered_map 使用哈希，遍历顺序不确定。

1
2
3
4
5
6
7
8
map<string, int> score;
score["Ming"] = 90;
auto it = score.find("Ming");
if (it != score.end()) cout << it->second;

unordered_map<string, int> frequency;
++frequency["apple"];
if (frequency.count("apple")) cout << frequency["apple"];

使用 m[key] 读取一个不存在的键时，会插入该键并创建默认值。若只想查找、不想插入，使用 find。C++17 可以用结构化绑定遍历：

1
2
3
for (const auto& [key, value] : frequency) {
    cout << key << ": " << value << '\n';
}

7. 标准算法与常见误区

find、sort、reverse 和 lower_bound 等是 <algorithm> 中的算法，不是 vector 的成员函数。lower_bound 要求输入范围已经按相同规则排序。

  • vector::reverse() 不存在，应写 reverse(v.begin(), v.end())。
  • find 对 vector 是线性查找；需要频繁查找时可考虑 set 或哈希表。
  • set 是有序的；unordered_map 才是不保证顺序。
  • priority_queue<int> 默认取最大值；小根堆需要指定比较器。
  • 容器的复杂度通常指常见或平均情况，遇到性能要求时应结合操作和数据规模判断。

可以从牛客 130 系列中挑选题目练习。每次使用容器时，先确认需要的操作，再选合适的数据结构。