09.容器类和算法

• 9.1 容器类介绍
  • 9.1.1 序列容器
  • 9.1.2 关联容器
  • 9.1.3 字符串处理
• 9.2 序列容器
  • 9.2.1 QList
  • 9.2.2 QVector
  • 9.2.3 QLinkedList
  • 9.2.4 QStack
  • 9.2.5 QQueue
• 9.3 关联容器
• 9.4 字符串处理

9.1 容器类介绍

9.1.1 序列容器

• QList：通用动态数组
• QVector：连续内存数组（Qt 6 中与 QList 合并）
• QLinkedList：双向链表
• QStack：栈实现
• QQueue：队列实现

9.1.2 关联容器

• QMap：红黑树实现的键值对
• QHash：哈希表实现的键值对
• QSet：无序集合
• QMultiMap/QMultiHash：支持多值的映射

9.1.3 字符串处理

• QString：Unicode 字符串处理
• QByteArray：原始字节数据处理
• QStringView：字符串视图（只读）
• QChar：Unicode 字符处理

9.2 序列容器

9.2.1 QList

QList 是 Qt 中最常用的动态数组容器，支持快速随机访问和动态扩展。

#include <QList>
#include <QDebug>

int main() {
    QList<int> list;
    // 添加元素
    list << 1 << 2 << 3 << 4 << 5;
    // 访问元素
    qDebug() << "First element:" << list.first();
    qDebug() << "Last element:" << list.last();
    qDebug() << "Element at index 2:" << list.at(2);
    // 遍历元素
    for (int i = 0; i < list.size(); ++i) {
        qDebug() << "Element" << i << ":" << list[i];
    }
    // 删除元素
    list.removeAt(2);
    qDebug() << "After removal:" << list;

    return 0;
}

性能特点

• 支持快速随机访问（O(1)）。
• 插入和删除操作在中间较慢（O(n)），在末尾较快（O(1)）。

9.2.2 QVector

在 Qt 6 中，QVector 和 QList 的实现已经合并，QVector 是 QList 的别名。

（1）基本用法

#include <QVector>
#include <QDebug>

int main() {
    QVector<int> vector;

    // 添加元素
    vector << 10 << 20 << 30 << 40 << 50;

    // 访问元素
    qDebug() << "First element:" << vector.first();
    qDebug() << "Last element:" << vector.last();
    qDebug() << "Element at index 2:" << vector.at(2);

    // 遍历元素
    for (int i = 0; i < vector.size(); ++i) {
        qDebug() << "Element" << i << ":" << vector[i];
    }

    // 删除元素
    vector.remove(2);
    qDebug() << "After removal:" << vector;

    return 0;
}

（2）性能特点

• 与 QList 相同，支持快速随机访问和动态扩展。

9.2.3 QLinkedList

QLinkedList 是一个双向链表容器，适合频繁插入和删除操作的场景。

（1）基本用法

#include <QLinkedList>
#include <QDebug>

int main() {
    QLinkedList<int> linkedList;
    // 添加元素
    linkedList << 100 << 200 << 300 << 400 << 500;
    // 访问元素
    qDebug() << "First element:" << linkedList.first();
    qDebug() << "Last element:" << linkedList.last();
    // 遍历元素
    for (auto it = linkedList.begin(); it != linkedList.end(); ++it) {
        qDebug() << "Element:" << *it;
    }
    // 删除元素
    linkedList.removeOne(300);
    qDebug() << "After removal:"; 
    for (int value : linkedList) {
        qDebug() << value;
    }
    return 0;
}

（2）性能特点

• 插入和删除操作非常高效（O(1)）。
• 随机访问较慢（O(n)）。

9.2.4 QStack

QStack 是一个后进先出（LIFO）的栈容器，基于 QList 实现。

（1）基本用法

#include <QStack>
#include <QDebug>

int main() {
    QStack<int> stack;
    // 压栈
    stack.push(1);
    stack.push(2);
    stack.push(3);
    // 访问栈顶元素
    qDebug() << "Top element:" << stack.top();
    // 弹栈
    while (!stack.isEmpty()) {
        qDebug() << "Popped:" << stack.pop();
    }
    return 0;
}

（2）性能特点

• 基于 QList，支持快速压栈和弹栈操作（O(1)）。

9.2.5 QQueue

QQueue 是一个先进先出（FIFO）的队列容器，基于 QList 实现。

（1）基本用法

#include <QQueue>
#include <QDebug>

int main() {
    QQueue<int> queue;
    // 入队
    queue.enqueue(10);
    queue.enqueue(20);
    queue.enqueue(30);
    // 访问队首元素
    qDebug() << "Front element:" << queue.head();
    // 出队
    while (!queue.isEmpty()) {
        qDebug() << "Dequeued:" << queue.dequeue();
    }
    return 0;
}

（2）性能特点

• 基于 QList，支持快速入队和出队操作（O(1)）。