STL 容器
熟悉常用容器接口并掌握选型依据
#一张对照表看懂容器
如果你来自 Python 或 Java,STL 容器基本都能找到老朋友——只是名字换了、行为细节更明确了。先建立映射关系,学起来会快很多:
| C++ 容器 | Python | Java | 底层结构 | 特点 |
|---|---|---|---|---|
std::vector<T> | list | ArrayList | 连续动态数组 | 随机访问 O(1),尾部增删 O(1),中间插入 O(n) |
std::deque<T> | collections.deque | ArrayDeque | 分段连续块 | 头尾增删均 O(1),随机访问 O(1) |
std::list<T> | 无直接对应 | LinkedList | 双向链表 | 任意位置插入 O(1),无随机访问 |
std::set<T> | set | TreeSet | 红黑树 | 有序、去重,增删查 O(log n) |
std::map<K,V> | 无(Python 3.7+ dict 保序但非排序) | TreeMap | 红黑树 | 按键排序,增删查 O(log n) |
std::unordered_map<K,V> | dict | HashMap | 哈希表 | 无序,平均 O(1),最坏 O(n) |
std::unordered_set<T> | set(实际就是它) | HashSet | 哈希表 | 去重,平均 O(1) |
std::string | str | String | 连续数组 | 可变,支持 SSO 小字符串优化 |
一个重要的心智差异:C++ 容器是"值容器"。std::vector<Person> v; Person p = v[0]; 会真的复制一份 Person;Python 和 Java 里 p = v[0] 拿到的只是引用。这既带来拷贝成本(用 const auto& 遍历可避免),也带来安全性(不会出现"改了容器里的对象却意外影响别处"的别名问题)。
#std::string:不只是字符串
C++ 的 std::string 是可变的,这一点和 Java 的 String(不可变)、Python 的 str(不可变)完全不同,倒更像 Java 的 StringBuilder。它底层是连续内存,支持 += 追加、[] 随机访问、resize 等,用起来很像 Python 的 list 和 str 的混合体。
另外 C++ 的字符串字面量 "hello" 类型是 const char[N](会退化成 const char*),不是 std::string。混用时编译器会自动转换,但要注意由此产生的临时对象开销。C++17 引入的 std::string_view 是只读场景的更好选择(第 3 章已提过),Qt 中对应的是 QString 和 QStringView。
#include <iostream>
#include <string>
#include <string_view>
int main() {
std::string s = "Hello"; // 从字面量构造
s += ", C++"; // 追加,可变(Java String 做不到)
s.append(3, '!'); // 追加 3 个 '!'
std::cout << s << "\n"; // Hello, C++!!!
std::cout << "长度 " << s.size() // 字节数,不含 '\0'
<< ",首字符 " << s.front()
<< ",末字符 " << s.back() << "\n";
// 查找与截取:find 找不到时返回 npos(一个巨大的 size_t)
auto pos = s.find("C++");
if (pos != std::string::npos) {
std::cout << "在位置 " << pos << " 找到\n";
std::cout << "子串: " << s.substr(pos, 3) << "\n";
}
// 插入与删除
s.insert(5, " World");
s.erase(5, 6);
std::cout << "编辑后: " << s << "\n";
// 数值转换:C++11 起有 stoi / stod / to_string
int n = std::stoi("1024");
double d = std::stod("3.14159");
std::cout << n << " " << d << " " << std::to_string(n) << "\n";
// string_view(C++17):只读视图,零拷贝,不拥有数据
std::string_view sv = s; // 隐式转换,不会复制字符
std::cout << "视图长度 " << sv.size() << ",前 5 字符 " << sv.substr(0, 5) << "\n";
// 注意:string_view 不管理生命周期,切勿指向已销毁的临时 string
// std::string_view bad = std::string("临时"); // 危险:悬垂视图
// 遍历:C++ 的 string 存的是字节,UTF-8 中文占 3 字节
std::string utf8 = "你好Qt";
std::cout << "中文字节数 " << utf8.size() << "\n"; // 不是 4
return 0;
}#std::vector:默认容器
不知道该用什么容器时,就用 vector。 这是 C++ 社区公认的默认选择,理由和 Python 里 list 一家独大类似:连续内存带来的缓存友好性,往往比渐进复杂度的优劣更重要。哪怕你需要在中间插入,除非数据量很大,vector 也常常比 list 快。
需要掌握的三个要点:reserve() 预分配避免反复扩容;emplace_back 原地构造避免临时对象;迭代器失效规则(扩容后所有迭代器/引用/指针全部失效,erase 后从删除点开始的都失效)。
#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility> // std::move
#include <vector>
struct Person {
std::string name;
int age{0};
// 聚合类型(无自定义构造函数)不能用 emplace_back("Bob", 25) 这种括号写法,
// 所以显式给出构造函数;或者改用 push_back(Person{"Bob", 25})
Person(std::string n, int a) : name(std::move(n)), age(a) {}
};
int main() {
std::vector<int> v{1, 2, 3};
v.push_back(4);
v.emplace_back(5); // 原地构造,比 push_back 少一次临时对象
std::cout << "大小 " << v.size() << ",容量 " << v.capacity() << "\n";
// reserve 预分配:避免多次扩容(每次扩容要复制全部元素)
std::vector<int> big;
big.reserve(1000);
for (int i = 0; i < 1000; ++i) {
big.push_back(i);
}
std::cout << "预分配后容量 " << big.capacity() << "(不会反复增长)\n";
// 三种访问方式:[] 不检查越界,at() 越界抛异常,front/back 访问首尾
std::cout << v[0] << " " << v.at(1) << " " << v.front() << " " << v.back() << "\n";
try {
std::cout << v.at(99) << "\n";
} catch (const std::out_of_range& e) {
std::cout << "越界捕获: " << e.what() << "\n";
}
// 插入与删除:中间操作是 O(n)
v.insert(v.begin() + 1, 99); // 在下标 1 处插入
v.erase(v.begin() + 1); // 删除刚插入的元素
v.pop_back(); // 删除尾部,O(1)
// 存自定义类型:emplace_back 直接传构造参数
std::vector<Person> people;
people.push_back(Person{"Alice", 30}); // 构造临时对象再移动
people.emplace_back("Bob", 25); // 直接原地构造,更优
people.reserve(100);
// 遍历:const auto& 避免复制整个 Person
for (const auto& p : people) {
std::cout << p.name << "(" << p.age << ") ";
}
std::cout << "\n";
// 用 vector 模拟栈:back/push_back/pop_back 足够
std::vector<int> stack;
stack.push_back(1);
stack.push_back(2);
while (!stack.empty()) {
std::cout << stack.back() << " ";
stack.pop_back();
}
std::cout << "\n";
return 0;
}上面的 at() 在越界时抛 std::out_of_range(第 10 章会系统讲异常),这也是它比 [] 安全的地方——后者越界属于未定义行为,可能静默读到垃圾数据。
#map / set / unordered_map:三种关联容器
std::map 和 std::unordered_map 的取舍,等价于 Java 里 TreeMap 与 HashMap、Python 里"没有内置有序 dict"的取舍:需要按 key 排序遍历、或需要 lower_bound 这类区间查询,用 map;只做精确查找,用 unordered_map(它平均 O(1),通常快 2-5 倍)。
Python 的 dict 从 3.7 起保证插入顺序,这和两者都不同;如果你要的是插入顺序,C++ 标准库没有直接对应物,通常用 vector 辅助维护顺序。
std::set 与 std::unordered_set 同理,对应 Python 的 set(Python 的 set 实际就是哈希表实现,等价 unordered_set)。
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
int main() {
// 1) map:按键排序的红黑树
std::map<std::string, int> scores{
{"Alice", 90}, {"Bob", 85}, {"Carol", 92}
};
scores["Dave"] = 78; // operator[] 不存在时会自动插入默认值
scores.insert_or_assign("Bob", 88); // C++17:存在则改,不存在则插
for (const auto& [name, score] : scores) { // 结构化绑定(C++17)
std::cout << name << ":" << score << " ";
}
std::cout << "\n"; // 按字母序输出,map 自动排序
// 查找:find 返回迭代器,找不到是 end()。不要用 operator[] 来"查",它会插入
auto it = scores.find("Alice");
if (it != scores.end()) {
std::cout << "Alice = " << it->second << "\n";
}
std::cout << "count(Bob) = " << scores.count("Bob") << "\n"; // 0 或 1
std::cout << "contains(Carol) = " << std::boolalpha
<< (scores.count("Carol") > 0) << "\n"; // C++20 有 contains()
// 区间查询是 map 的独有能力
auto lower = scores.lower_bound("B");
if (lower != scores.end()) {
std::cout << "第一个 >= B 的键: " << lower->first << "\n";
}
// 2) unordered_map:哈希表,无序但更快
std::unordered_map<std::string, int> fast{
{"apple", 5}, {"banana", 3}, {"cherry", 8}
};
for (const auto& [k, v] : fast) {
std::cout << k << " ";
}
std::cout << "\n(顺序不确定)\n";
// 自定义类型做 key 需要提供 hash 和 ==,内置类型已内置
fast.reserve(1000); // 预分配桶,减少 rehash
// 3) set:有序去重;unordered_set:哈希去重
std::set<int> unique_sorted{3, 1, 4, 1, 5, 9, 2, 6};
std::cout << "set: ";
for (int x : unique_sorted) {
std::cout << x << " "; // 1 2 3 4 5 6 9,有序且去重
}
std::cout << "\n";
std::unordered_set<std::string> tags{"cpp", "qt", "cpp", "stl"};
std::cout << "tags 去重后数量 = " << tags.size() << "\n"; // 3
// 4) 统计词频:map 的经典用法(Python 的 collections.Counter)
std::string text = "the quick brown fox jumps over the lazy dog the end";
std::unordered_map<std::string, int> freq;
{
std::string word;
for (char ch : text) {
if (ch == ' ') {
if (!word.empty()) { ++freq[word]; word.clear(); }
} else {
word += ch;
}
}
if (!word.empty()) { ++freq[word]; }
}
std::cout << "the 出现 " << freq["the"] << " 次\n";
return 0;
}注意 operator[] 的副作用:用 m[key] 查找不存在的键会插入一个默认值,可能悄悄改变容器。只读查找一律用 find() 或 C++20 的 contains()。
#deque、list 与容器适配器
std::deque(double-ended queue)支持头尾 O(1) 增删,同时保留 O(1) 随机访问,是 std::stack 和 std::queue 的默认底层容器。std::list 是双向链表,任意位置插入 O(1) 且迭代器不会因插入而失效,但内存不连续、缓存命中率低——实际工程中它用得比想象中少,多数场景 vector 更快。Java 的 LinkedList 同理,社区也普遍建议优先 ArrayList。
容器适配器不是真正的容器,而是在已有容器上套一层受限接口:
std::stack<T>:后进先出,只暴露push/pop/top。std::queue<T>:先进先出,只暴露push/pop/front/back。std::priority_queue<T>:最大堆,top()取最大元素。
它们对应 Python 的 collections.deque(当栈/队列用)和 heapq。
#include <algorithm>
#include <deque>
#include <functional> // std::greater
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
int main() {
// 1) deque:头尾都能高效增删
std::deque<int> dq{2, 3, 4};
dq.push_front(1); // 头部 O(1)
dq.push_back(5); // 尾部 O(1)
std::cout << "deque: ";
for (int x : dq) { std::cout << x << " "; }
std::cout << ",随机访问 dq[2] = " << dq[2] << "\n";
// 2) list:链表,插入不失效已有迭代器
std::list<std::string> tasks{"编译", "测试"};
auto pos = tasks.begin();
++pos;
tasks.insert(pos, "打包"); // O(1),且已有迭代器仍有效
tasks.remove("测试"); // 按值删除,list 特有
for (const auto& t : tasks) { std::cout << t << " "; }
std::cout << "\n";
// 3) stack:默认基于 deque
std::stack<int> st;
st.push(1); st.push(2); st.push(3);
std::cout << "stack 出栈顺序: ";
while (!st.empty()) {
std::cout << st.top() << " ";
st.pop();
}
std::cout << "\n";
// 4) queue:先进先出
std::queue<std::string> q;
q.push("任务A"); q.push("任务B"); q.push("任务C");
while (!q.empty()) {
std::cout << q.front() << " ";
q.pop();
}
std::cout << "\n";
// 5) priority_queue:默认大顶堆
std::priority_queue<int> pq;
for (int x : {5, 1, 9, 3, 7}) { pq.push(x); }
std::cout << "priority_queue: ";
while (!pq.empty()) {
std::cout << pq.top() << " "; // 9 7 5 3 1
pq.pop();
}
std::cout << "\n";
// 小顶堆:换比较器(greater 需要 <functional>)
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
for (int x : {5, 1, 9, 3, 7}) { min_heap.push(x); }
std::cout << "最小值 = " << min_heap.top() << "\n";
return 0;
}#迭代器:容器与算法之间的胶水
迭代器是所有容器统一的访问接口,可以类比 Python 的迭代器协议(__iter__ / __next__)或 Java 的 Iterator。但 C++ 的迭代器更接近广义化的指针:支持 * 解引用、++ 前进,vector 的迭代器还支持 + n 随机跳跃。
所有容器都有 begin() / end(),注意 end() 指向最后一个元素之后的位置(尾后迭代器),不能解引用——这个半开区间 [begin, end) 设计和 Python 的切片 a[0:len(a)] 思路一致。
C++ 迭代器按能力分五类,从弱到强:输入 → 输出 → 前向 → 双向 → 随机访问。容器的迭代器类型决定了能用哪些算法(第 8 章详述)。简单记忆:vector/deque/array/string 是随机访问,list/set/map 是双向,forward_list 是前向,istream_iterator 是输入。
#include <algorithm> // std::copy
#include <iostream>
#include <iterator> // std::distance, std::back_inserter
#include <list>
#include <map>
#include <string>
#include <vector>
int main() {
std::vector<int> v{10, 20, 30, 40, 50};
// 1) 显式迭代器遍历:begin() 指向首元素,end() 是尾后哨兵
for (auto it = v.begin(); it != v.end(); ++it) {
std::cout << *it << " "; // *it 解引用拿到元素
}
std::cout << "\n";
// 2) 需要修改元素时用非 const 迭代器
for (auto it = v.begin(); it != v.end(); ++it) {
*it *= 2;
}
// 3) 只读遍历用 cbegin()/cend(),返回 const_iterator
for (auto it = v.cbegin(); it != v.cend(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
// 4) 随机访问迭代器支持算术运算(vector/string/deque 专属)
auto mid = v.begin() + 2;
std::cout << "中间元素 = " << *mid
<< ",两个迭代器距离 = " << std::distance(v.begin(), v.end()) << "\n";
// 5) 反向迭代器:rbegin()/rend() 倒着走
std::cout << "倒序: ";
for (auto it = v.rbegin(); it != v.rend(); ++it) {
std::cout << *it << " ";
}
std::cout << "\n";
// 6) list 的迭代器是双向的,不支持 + n,只能用 ++
std::list<std::string> names{"a", "b", "c"};
auto lit = names.begin();
++lit; // OK
// auto bad = lit + 1; // 编译错误:双向迭代器没有 operator+
std::cout << "list 第二个元素 = " << *lit << "\n";
// 7) map 的迭代器指向 pair<const K, V>
std::map<std::string, int> m{{"x", 1}, {"y", 2}};
for (auto it = m.begin(); it != m.end(); ++it) {
std::cout << it->first << "=" << it->second << " ";
}
std::cout << "\n";
// 8) 插入迭代器:back_inserter 让算法可以往容器里追加(第 8 章会用到)
std::vector<int> dst;
std::copy(v.begin(), v.end(), std::back_inserter(dst));
std::cout << "复制后目标大小 = " << dst.size() << "\n";
return 0;
}std::back_inserter 是插入迭代器,它让"只负责读取和写入元素的算法"能够自动扩容目标容器,是连接容器与算法的常用桥梁。
#选型决策
最后给一套实用的决策顺序:
- 默认
vector。它有最好的缓存局部性,sort/find等算法配合起来也最简单。 - 需要频繁在头部增删且要随机访问 →
deque。 - 需要频繁在中间插入且元素很大、已有迭代器必须保持有效 →
list(先测性能,很多时候 vector 仍更快)。 - 需要 key-value 精确查找 →
unordered_map;需要有序遍历或区间查询 →map。 - 需要去重 →
unordered_set(快)或set(有序)。 - 需要栈/队列语义 → 容器适配器,别自己用 vector 拼。
Qt 里对应的是 QVector(Qt 6 中已基本等于 std::vector 的别名)、QList、QMap、QHash、QStringList。Qt 6 的方向是尽量与 STL 统一,所以学好 STL 容器,迁移到 Qt 容器几乎没有成本。
#小结
- 容器映射:
vector≈Python list/Java ArrayList,unordered_map≈Python dict/Java HashMap,map≈TreeMap,unordered_set≈Python set。 - C++ 容器存的是值:
v[0]取出来是副本概念,遍历用const auto&避免不必要的拷贝。 std::string可变(更像StringBuilder),size()返回字节数;只读参数用 C++17 的string_view。vector是默认容器:reserve()预分配、emplace_back原地构造,注意扩容会让所有迭代器失效。- 关联容器查询用
find()/C++20contains(),operator[]会自动插入默认值,只读场景是坑。 - 迭代器是广义指针,
end()是尾后哨兵;vector/string支持随机访问,list/set/map只有双向。
#练习
- 用
std::vector<int>读入 20 个整数,去掉重复值后排序输出。要求用reserve预处理,并在代码里说明为什么先去重再排序。 - 统计一段英文文本的词频,分别用
std::map和std::unordered_map实现,输出前 5 个高频词。观察两种实现输出顺序的差异。 - 用
std::stack<char>判断括号串"{[()()]}"是否匹配,支持()、[]、{}三种括号。 - 写一个
std::vector<std::string>,故意在遍历过程中push_back触发扩容,观察之前保存的迭代器是否失效(打印前后地址对比)。再用reserve预留足够空间重试一次,并把练习 2 的词频统计改成返回std::vector<std::pair<std::string,int>>、用std::sort按频次降序排列——这会把你引向第 8 章的算法。