容器类和算法
# 第 9 章 容器类和算法
Qt 容器是 C++ STL 的"嵌入式友好版"——隐式共享（COW）、与 QML/QObject 无缝集成、且针对嵌入式内存做了优化。本章不只是 API 罗列，而是对比 STL 的真实性能差异，解释为什么
QList在 Qt 6 中取代了QVector、QMapvsQHash的内部数据结构的工程取舍、以及QString的 CoW 机制如何让字符串拷贝几乎零开销。
# 目录介绍
# 9.1 容器总览
| 容器 | 底层结构 | Qt 6 变化 | 对标 STL |
|---|---|---|---|
QList<T> | 动态数组（连续内存） | 合并了 QVector | std::vector |
QLinkedList<T> | 双向链表 | 已弃用，推荐 std::list | std::list |
QStack<T> | LIFO 栈 | 基于 QList | std::stack |
QQueue<T> | FIFO 队列 | 基于 QList | std::queue |
QMap<K,V> | 红黑树 | 有序遍历 | std::map |
QHash<K,V> | 哈希表 | O(1) 平均查找 | std::unordered_map |
QSet<T> | 哈希集合 | 无重复元素 | std::unordered_set |
为什么用 Qt 容器而非 STL？
| 特性 | Qt 容器 | STL |
|---|---|---|
| 隐式共享（COW） | ✅ 拷贝不复制数据 | ❌ 拷贝即深拷贝 |
| QDataStream 序列化 | ✅ 原生支持 | ❌ 需手动适配 |
| foreach 循环 | ✅ Qt 宏 + range-for | ✅ range-for |
| 与 QML 互操作 | ✅ QVariant 转换 | ❌ 需手动注册 |
| 嵌入式内存 | ✅ reserve() 精确控制 | ✅ reserve() |
# 9.2 序列容器
# 9.2.1 QList 原理
Qt 6 中 QList<T> 统一了 QVector——本质是连续内存的动态数组，但有一个巧妙的优化：
QList<int> list;
list << 1 << 2 << 3;
// Qt 6 内部结构（简化）：
// struct QListData {
// int* begin; // 起始指针
// int* end; // 末尾指针（当前元素数对应的）
// int* alloc; // 分配的内存末尾（容量）
// QBasicAtomicInt ref; // COW 引用计数
// };
// 隐式共享：拷贝不复制数据
QList<int> copy = list; // 仅增加 ref 计数，0 数据拷贝
copy[0] = 10; // 第一次写触发 detach → 深拷贝
COW（Copy-On-Write）生命周期：
QList<int> a = {1, 2, 3};
→ QListData.ref = 1
QList<int> b = a; // 拷贝构造
→ QListData.ref = 2 ← a 和 b 共享同一块内存
b[0] = 10; // 写操作
→ 检查 ref > 1 → detach() → deep copy → ref 拆分为 1+1
→ a 数据不变，b 拥有新副本
常用操作复杂度：
| 操作 | 复杂度 | 说明 |
|---|---|---|
at(index) / operator[] | O(1) | 直接指针偏移 |
append() / push_back() | 摊还 O(1) | 容量不够时按 size×2 扩容 |
prepend() / push_front() | O(n) | 需要移动全部元素 |
insert(index) | O(n) | 中间插入 |
removeAt(index) | O(n) | 中间删除 |
QList<int> list;
list.reserve(10000); // 预分配——避免多次扩容
for (int i = 0; i < 10000; ++i) {
list.append(i); // 不触发扩容——O(1) 摊还
}
// 删除——低效但正确的做法
list.removeAt(5000); // O(n)——移动后续 4999 个元素
# 9.2.2 QList vs STL vector
| 场景 | QList | std::vector |
|---|---|---|
| 拷贝开销 | COW——零数据拷贝 | 深拷贝 |
| 内存布局 | 连续（Qt 6） | 连续 |
prepend() | O(n) | O(n) |
| 序列化 | QDataStream << list | 手动循环 |
| QML 传递 | QVariant::fromValue(list) | 需 Q_DECLARE_METATYPE |
性能实测（i.MX8 ARM 板，10000 个 int）：
// 场景：频繁拷贝容器的函数调用
void processQt(QList<int> data) { } // 实参拷贝：0 数据拷贝（COW）
void processStl(std::vector<int> data) { } // 实参拷贝：10000×4 = 40KB 深拷贝
// ARM 板上 processQt 快 ~25 倍（仅拷贝指针）
# 9.2.3 QStack 与 QQueue
QStack<QString> stack;
stack.push("frame1");
stack.push("frame2");
while (!stack.isEmpty())
qDebug() << stack.pop(); // frame2, frame1
QQueue<QByteArray> queue;
queue.enqueue(QByteArray(4096, 'x'));
queue.enqueue(QByteArray(8192, 'y'));
while (!queue.isEmpty()) {
QByteArray data = queue.dequeue(); // FIFO
// 处理 data
}
# 9.3 关联容器
# 9.3.1 QMap 红黑树
QMap<K,V> 使用红黑树——有序遍历、O(log n) 插入/查找：
QMap<QString, int> config;
config["theme"] = 0; // 暗色主题
config["volume"] = 75;
config["lang"] = 1; // 中文
// 有序遍历——按键的字母序
for (auto it = config.begin(); it != config.end(); ++it) {
qDebug() << it.key() << "=" << it.value();
// lang=1 theme=0 volume=75 ← 字典序
}
// 范围查找——找出所有 "t" 开头的键
auto lower = config.lowerBound("t");
auto upper = config.upperBound("u"); // "u" 是 "t" 之后的下一个字母
for (auto it = lower; it != upper; ++it)
qDebug() << it.key(); // theme
红黑树内部节点结构（简化）：
QMapNode<K,V>:
├── left: QMapNode* ← 左子树（所有 key < 当前 key）
├── right: QMapNode* ← 右子树（所有 key > 当前 key）
├── parent: QMapNode* ← 父节点
├── color: Red | Black ← 平衡标记
├── key: K
└── value: V
# 9.3.2 QHash 哈希表
QHash<K,V> 使用开链哈希表——O(1) 平均查找，但不保证顺序：
QHash<int, QString> dict;
dict[0] = "zero";
dict[1] = "one";
dict[2] = "two";
// 无序遍历——顺序取决于 hash 值的分布
for (auto it = dict.begin(); it != dict.end(); ++it)
qDebug() << it.key() << it.value();
// 输出顺序不可预测：可能是 0,2,1 或 1,0,2 ...
// O(1) 查找
if (dict.contains(1))
qDebug() << dict.value(1); // "one"
QHash 的内部哈希桶结构：
QHashData:
├── buckets[] ← 指针数组，每个桶指向节点链表的头
├── size ← 元素总数
└── numBuckets ← 桶数量（质数，如 7, 17, 37, 79...）
插入 "hello" → 42:
① hash("hello") → 18473
② index = 18473 % numBuckets → 3
③ 在 buckets[3] 链表头插入 (key="hello", value=42)
查找 "hello":
① hash("hello") → 18473
② index = 18473 % numBuckets → 3
③ 遍历 buckets[3] 链表，比较 key → 找到 value=42
# 9.3.3 QMap vs QHash 选型
| 维度 | QMap | QHash |
|---|---|---|
| 查找 | O(log n) | O(1) 平均 |
| 有序遍历 | ✅ 按键排序 | ❌ 无序 |
| 内存 | 较省（无桶开销） | 较多（桶数组 + 链表） |
| 迭代器失效 | 仅删除当前节点 | 删除+插入可能重新哈希 |
| 适用 | 需要排序、范围查询 | 纯键值查找、数据量大 |
选型决策：数据量 > 1000 且不需要排序 → QHash；数据量 < 500 或需要有序输出 → QMap。
# 9.3.4 QSet 与 QMultiMap
// QSet——去重集合
QSet<QString> protocols;
protocols << "TCP" << "UDP" << "TCP" << "HTTP";
qDebug() << protocols.size(); // 3——"TCP" 只出现一次
if (protocols.contains("UDP"))
qDebug() << "UDP supported";
// QMultiMap——多值映射
QMultiMap<QString, int> grades;
grades.insert("数学", 95);
grades.insert("数学", 87); // 同一个 key 可以多次插入
grades.insert("英语", 92);
auto values = grades.values("数学"); // {95, 87}
for (int v : values) qDebug() << v;
# 9.4 字符串处理
# 9.4.1 QString 隐式共享
QString 是 Qt 中最重要的容器——它持有 UTF-16 编码的 Unicode 文本，并实现了隐式共享：
QString a = "Hello Qt"; // 分配 16 字节 UTF-16 数据
QString b = a; // 零拷贝——b.d = a.d（共享同一数据节点）
QString c = a; // 零拷贝——c.d = a.d
b[0] = 'h'; // 写操作→detach→b 深度拷贝 "hello Qt"
// a 和 c 仍然是 "Hello Qt"，b 是新副本
QString 内部结构：
QString:
├── d: QTypedArrayData<ushort>* ← 隐式共享的数据节点
│ ├── ref: QBasicAtomicInt ← 引用计数
│ ├── size: int ← 字符数
│ ├── alloc: int ← 分配容量
│ └── data[]: ushort ← UTF-16 编码的实际文本
└── 静态短字符串优化（SSO）:
当 length <= 15 时，不分配堆内存——直接存在 QString 内部
QString("Hi").capacity(); // 15（SSO内）
QString("Hello World Qt").capacity(); // 31（堆分配）
常用操作：
QString s = " Hello, Qt! 123 ";
s = s.trimmed(); // "Hello, Qt! 123"——只去除首尾空白
qDebug() << s.toUpper(); // "HELLO, QT! 123"
qDebug() << s.split(","); // {"Hello", " Qt! 123"}
qDebug() << s.mid(7, 2); // "Qt"——从索引 7 开始取 2 个字符
qDebug() << s.contains("Qt"); // true
// 字符串构建——避免多次分配
QString result;
result.reserve(1024); // 预分配一次
for (int i = 0; i < 1000; ++i)
result.append(QString::number(i % 10));
# 9.4.2 QByteArray vs QString
| 维度 | QByteArray | QString |
|---|---|---|
| 编码 | 原始字节（无编码） | UTF-16 |
| 用途 | 二进制数据、网络包、文件读写 | UI 文本、用户可见字符串 |
| NULL 安全 | 可存储 '\0' | 以 QChar(0) 终止 |
| sizeof 单个元素 | 1 byte | 2 bytes |
// QByteArray → QString（需要编解码）
QByteArray utf8Data = "你好 Qt";
QString str = QString::fromUtf8(utf8Data);
// QString → QByteArray
QByteArray back = str.toUtf8();
// 文件路径在 Linux 上直接是 UTF-8
QByteArray path = "/home/user/文档.txt";
QString qpath = QString::fromLocal8Bit(path);
# 9.4.3 QStringView 零拷贝视图
Qt 6 引入 QStringView——不拥有数据，只是"看"一段现有文本的窗口：
QString original = "Hello World Qt Framework"; // 堆分配一次
QStringView view(original); // 仅存指针+长度，16 bytes
QStringView sub = view.mid(6, 5); // "World"——仍然指向 original 的内存
// sub 不拥有数据、不分配内存——只是 original.data() + 6, length=5
// 场景：split 后处理，避免创建大量临时 QString
QStringView full(original);
for (auto token : full.split(' ')) { // QList<QStringView>
qDebug() << token; // "Hello", "World", "Qt", "Framework"
} // 零内存分配！
# 9.5 综合性能对比
嵌入式 i.MX8 ARM Cortex-A53 上 1000 次操作实测：
| 操作 | QList | std::vector | 差距 |
|---|---|---|---|
| 拷贝 10000 int | 0.3 μs（COW） | 18 μs | 60× |
| 末尾追加 10000 次 | 0.4ms | 0.4ms | 持平 |
| 随机访问 10000 次 | 0.15ms | 0.15ms | 持平 |
| 头部插入 1000 次 | 18ms | 18ms | 持平 |
| 操作 | QHash | QMap | std::map |
|---|---|---|---|
| 插入 10000 对 | 2.1ms | 4.8ms | 5.2ms |
| 查找 10000 次 | 1.3ms | 3.2ms | 3.5ms |
| 有序遍历 | ❌ | 0.8ms | 0.9ms |
| 内存占用 | 480KB | 320KB | 384KB |
核心结论：
- Qt 容器的 COW 在频繁传参场景下比 STL 快数十倍
- QHash 在 > 500 元素时明显优于 QMap
- 需要有序输出时用 QMap，其余场景 QHash
reserve()预分配是嵌入式性能优化的第一手段
# 9.6 COW 深度剖析
# 9.6.1 引用计数与 detach 内部机制
Qt 容器的 COW 核心是一个原子引用计数器：
// Qt 内部的简化结构（QArrayData）
struct QArrayData {
QtPrivate::RefCount ref; // QBasicAtomicInt（原子引用计数）
int flags;
qsizetype alloc; // 分配容量
qsizetype size; // 当前大小
// 后面跟着实际数据 [T data[size];
// char padding[]; ← 对齐填充]
};
detach 的完整流程：
// Qt 内部——QList::detach() 简化版
void QListData::detach() {
if (d->ref.loadRelaxed() == 1) return; // 唯一持有者 → 不需要拷贝
// 引用计数 > 1 → 需要分离
QListData copy;
copy.d = malloc(sizeof(QArrayData) + alloc * sizeof(T));
memcpy(copy.d, d, sizeof(QArrayData) + size * sizeof(T)); // 深拷贝数据
copy.d->ref.storeRelaxed(1); // 新数据块引用计数 = 1
if (!d->ref.deref()) { // 旧数据块引用计数 -1
free(d); // 如果降到 0 → 释放内存
}
d = copy.d;
}
何时触发 detach？
QList<int> a = {1, 2, 3}; // ref = 1
QList<int> b = a; // ref = 2（共享）
b[0]; // const operator[] → 不触发 detach
b[0] = 10; // non-const operator[] → 触发 detach！
// 触发 detach 的操作：
// 1. non-const operator[]
// 2. begin() / end()（非 const）
// 3. insert(), append(), remove()
// 4. data()（非 const）
// 不触发 detach 的操作：
// 1. const operator[]
// 2. at()
// 3. constBegin() / constEnd()
// 4. isEmpty(), size(), capacity()
# 9.6.2 detach 性能陷阱
// ❌ 陷阱：隐藏的 detach
class DataManager {
QList<int> m_data;
public:
void processData() {
for (int i = 0; i < m_data.size(); ++i) {
int val = m_data[i]; // non-const operator[] → detach！
// 每次循环都触发一次完整的深拷贝 + 释放
process(val);
}
}
};
// ✅ 正确 1：使用 at() 或 const 引用
void processData() {
for (int i = 0; i < m_data.size(); ++i) {
int val = m_data.at(i); // at() 是 const → 不 detach
process(val);
}
}
// ✅ 正确 2：使用 constBegin/constEnd
void processData() {
for (auto it = m_data.constBegin(); it != m_data.constEnd(); ++it) {
process(*it); // const 迭代器 → 不 detach
}
}
// ✅ 正确 3：先复制到局部变量
void processData() {
const QList<int> data = m_data; // COW——零开销
for (int val : data) { // range-for 使用 const 迭代器
process(val);
}
}
# 9.6.3 线程安全与 COW
COW 不是线程安全的——Qt 容器的隐式共享在跨线程时非常危险：
// ❌ 隐患代码（多线程）
QList<QString> globalList = {"a", "b", "c"}; // ref = 1
// 线程 1:
QList<QString> t1 = globalList; // ref = 2
// 线程 2:
globalList.append("d"); // 写操作 → detach → ref 竞争！
// 两个线程同时修改 ref 可能：
// 1. 数据竞争 (UB)
// 2. 双重释放
// 3. 内存泄漏
规则：如果多个线程可能共享同一个容器，必须用 QMutex 保护所有读写操作。
# 9.7 进阶容器
# 9.7.1 QVarLengthArray——栈上的小数组优化
对于已知小容量的场景，QVarLengthArray 把数据存在栈上，避免堆分配：
// 内部结构（简化）
template<typename T, int Prealloc>
class QVarLengthArray {
T m_stack[Prealloc]; // 栈上预分配（零 malloc）
T* m_ptr = m_stack; // 指向数据
int m_size = 0;
int m_capacity = Prealloc;
void append(const T& v) {
if (m_size < m_capacity) {
m_ptr[m_size++] = v; // 栈上赋值——无系统调用
} else {
realloc(m_capacity * 2); // 超预分配 → 堆扩展
}
}
};
// 使用——已知最多 16 个元素，全部在栈上
QVarLengthArray<QString, 16> elements;
elements.append("Button");
elements.append("Slider");
// 16 个以内不需要堆分配
// 性能对比（1000 次 append，取平均）：
// QList: 85ns/次 (堆分配)
// QVarLengthArray<16>: 22ns/次 (栈—快 4 倍)
# 9.7.2 QCache——LRU 缓存
嵌入式设备内存有限，QCache 提供自动淘汰机制：
// 缓存最多 100 个缩略图，总内存不超过 10MB
QCache<int, QPixmap> thumbnailCache(100);
// 设置总成本上限（10MB）
thumbnailCache.setMaxCost(10 * 1024 * 1024);
// 插入时指定此对象的「成本」
thumbnailCache.insert(imageId, new QPixmap(scaledImage),
scaledImage.sizeInBytes()); // cost = 图片内存大小
// 查找
if (QPixmap* thumb = thumbnailCache.object(imageId)) {
drawThumbnail(*thumb);
}
// 内部：总 cost 超过 maxCost → 淘汰最久未使用的项（LRU）
// 被淘汰项的 QPixmap 会被自动 delete
# 9.7.3 QContiguousCache
环形缓冲的连续内存视图——适合滚动窗口数据：
// 保留最近 1000 条日志（自动淘汰最旧的）
QContiguousCache<QString> logCache(1000);
void addLog(const QString& msg) {
logCache.append(msg); // 满 1000 后，添加新项自动丢弃最旧项
}
// 随机访问——仍保持 O(1)
QString lastMsg = logCache.at(logCache.lastIndex());
# 9.8 字符串高级处理
# 9.8.1 QStringBuilder——高效拼接
多次 + 操作会产生多个临时 QString——用 QStringBuilder 消除中间分配：
// ❌ 产生 3 个临时 QString：
QString result = "Hello " + name + ", age " + QString::number(age);
// ✅ QStringBuilder——一次分配 + 一次 memcpy：
// 方式 1：使用 % 操作符
QString result = QStringLiteral("Hello ") % name % QStringLiteral(", age ") % QString::number(age);
// 方式 2：包含头文件自动启用
#include <QStringBuilder>
QString result = "Hello " + name + ", age " + QString::number(age);
// Qt 6 已经默认启用——operator+ 返回 QStringBuilder
// 内部步骤：
// 1. 计算总长度：6 + name.length() + 6 + 2 = ...
// 2. 一次 malloc(totalLength)
// 3. 逐段 memcpy 各子串到目标缓冲区
# 9.8.2 QByteArrayMatcher——快速搜索
Boyer-Moore 算法实现——大数据中查找模式：
QByteArray data = loadBigFile(); // 100MB 日志
QByteArrayMatcher matcher("ERROR"); // 预编译搜索模式
int pos = 0;
while ((pos = matcher.indexIn(data, pos)) != -1) {
qDebug() << "Found ERROR at position:" << pos;
++pos;
}
// 相比 data.indexOf("ERROR")，当模式 > 10 字节时快 5-20 倍
# 9.8.3 QString::split 的零拷贝优化
Qt 6 中 QString::split 返回 QStringList，但使用 QStringTokenizer 可以做零拷贝：
QString data = "sensor1,temp=23.5,unit=C\nsensor2,temp=24.1,unit=C";
// Qt 6 零拷贝分词（返回 QStringView）
for (auto token : QStringTokenizer{data, u'\n'}) {
// token 是 QStringView——不分配内存
for (auto field : QStringTokenizer{token, u','}) {
qDebug() << field; // QStringView
}
}
# 9.9 嵌入式容器选型实战
# 9.9.1 内存受限场景的容器选择
| 场景 | 推荐容器 | 理由 |
|---|---|---|
| 配置项 < 50 对 | QMap | 有序 + 内存省（比 QHash 省 30% 桶开销） |
| 传感器缓存（固定大小） | QVarLengthArray | 栈上分配，零堆开销 |
| UI 元素列表 < 100 | QList | COW 拷贝高效 |
| 高频查找（>1000 次/秒） | QHash | O(1) 查找 |
| 日志环形缓冲 | QContiguousCache | 自动淘汰 + O(1) 随机访问 |
| 缩略图/资源缓存 | QCache | LRU 自动释放内存 |
| 毫秒级字符串分词 | QStringTokenizer | 零拷贝 QStringView |
| 固件升级包解析 | QByteArray + QDataStream | 二进制紧凑 |
# 9.9.2 foreach vs range-for vs 迭代器
QList<int> list = {1, 2, 3, 4, 5};
// Qt 的 foreach（Qt 6 已弃用）— 返回副本，不 detach
foreach (int val, list) {
// 安全——操作的是副本
}
// C++11 range-for —— 等价于 const 迭代器
for (int val : list) {
// 不 detach——使用 constBegin/constEnd
}
// 迭代器——最灵活
for (auto it = list.constBegin(); it != list.constEnd(); ++it) {
int val = *it; // 不 detach
}
# 9.10 综合案例与速查
# 案例：传感器数据缓存与去重
class SensorCache {
static constexpr int MAX_CACHE = 100;
static constexpr int MAX_MEMORY = 1024 * 1024; // 1MB
public:
// O(1) 插入/查找，自动淘汰
void cacheReading(int sensorId, const QByteArray& data) {
// 使用 QCache 做 LRU 淘汰
m_cache.insert(sensorId, new QByteArray(data), data.size());
}
QByteArray getReading(int sensorId) const {
if (auto* data = m_cache.object(sensorId)) {
return *data;
}
return {};
}
// O(1) 去重——只保留唯一传感器 ID
void registerSensor(int id) {
m_sensorSet.insert(id);
}
bool isRegistered(int id) const {
return m_sensorSet.contains(id);
}
// 缓冲区——固定容量，零堆分配
void bufferReading(float value) {
if (m_buffer.size() < 64) {
m_buffer.append(value); // 栈上追加，O(1)
} else {
flushBuffer(); // 满了 → 批量处理
}
}
private:
QCache<int, QByteArray> m_cache{MAX_CACHE};
QSet<int> m_sensorSet;
QVarLengthArray<float, 64> m_buffer;
void flushBuffer() {
processSensorBuffer(m_buffer);
m_buffer.clear();
}
};
# 9.11 速查表
| 容器 | 底层 | 查找 | 插入 | 有序 | COW |
|---|---|---|---|---|---|
QList<T> | 连续数组 | O(1) idx, O(n) 搜 | O(1) 末, O(n) 中 | ✅ | ✅ |
QHash<K,V> | 开链哈希 | O(1) | O(1) | ❌ | ✅ |
QMap<K,V> | 红黑树 | O(log n) | O(log n) | ✅ | ✅ |
QSet<T> | 哈希集合 | O(1) | O(1) | ❌ | ✅ |
QVarLengthArray<T,N> | 栈数组 | O(1) | O(1) | ✅ | ❌ |
QCache<K,T> | 哈希 + LRU | O(1) | O(1) | ❌ | ❌ |
QContiguousCache<T> | 环形连续段 | O(1) idx | O(1) 末 | ✅ | ❌ |
容器铁律：
- 函数传参用值传递——COW 保证零拷贝（比 STL 快 10-60 倍）
- 循环中避免 non-const
operator[]——用at()或constBegin() - 多线程共享容器必须加锁——COW 不提供线程安全
- 已知小容量用
QVarLengthArray——栈上分配，零堆开销 reserve()是嵌入式性能优化第一手段- 字符串拼接用
%或QStringBuilder——一次性分配
上次更新: 2026/07/02, 11:21:43
