QSet使用详解

一、QSet 的特性

QSet 是 Qt 提供的一个集合类，其底层数据结构是基于哈希表的。这使得 QSet 在插入、删除和查找操作上都具有平均 O(1) 的时间复杂度。下面我们详细讨论 QSet 的底层实现原理和其使用的相关数据结构。

唯一性：QSet 中的元素是唯一的，插入一个已经存在的元素不会改变集合。
无序性：QSet 不保证元素的顺序，因为哈希表的结构使其存储顺序依赖于哈希函数。
高效性：由于哈希表的使用，QSet 提供了平均 O(1) 的插入、删除和查找操作时间复杂度。

1.1 QSet 的底层结构

QSet 的底层实现依赖于 QHash。实际上，QSet 是使用 QHash 来存储元素，其中键和值都是集合中的元素。QSet 只是对 QHash 的一个封装，使得用户可以方便地使用集合的特性，而无需关心键值对的概念。

1.2 QHash 的数据结构

QHash 采用哈希表作为底层数据结构。哈希表使用一个哈希函数将元素映射到数组中的一个位置（称为桶）。当发生哈希冲突（不同元素映射到相同的桶）时，QHash 使用链地址法（chaining）来解决冲突，这意味着每个桶实际上是一个链表，存储哈希冲突的元素。

二、创建和初始化

2.1 创建空的 QSet

QSet<int> set;

2.2 使用初始值创建 QSet

QSet<int> set = {1, 2, 3, 4, 5};

三、插入和删除元素

3.1 插入元素

set.insert(6);

3.2 删除元素

set.remove(3);

3.3 清空集合

set.clear();

四、检查元素

4.1 检查是否包含特定值

bool contains = set.contains(3);

五、遍历集合

5.1 使用范围循环遍历

for (int value : set) {
    qDebug() << value;
}

5.2 使用迭代器遍历

QSet<int>::iterator it;
for (it = set.begin(); it != set.end(); ++it) {
    qDebug() << *it;
}

六、其他操作

6.1 获取集合的大小

int size = set.size();

6.2 检查集合是否为空

bool isEmpty = set.isEmpty();

6.3 获取集合的并集

QSet<int> set1 = {1, 2, 3};
QSet<int> set2 = {3, 4, 5};
QSet<int> unionSet = set1.unite(set2);

6.4 获取集合的交集

QSet<int> set1 = {1, 2, 3};
QSet<int> set2 = {3, 4, 5};
QSet<int> intersectionSet = set1.intersect(set2);

6. 5 获取集合的差集

QSet<int> set1 = {1, 2, 3};
QSet<int> set2 = {3, 4, 5};
QSet<int> differenceSet = set1.subtract(set2);

七、自定义类型的 QSet

如果要在 QSet 中存储自定义类型，需要提供该类型的 qHash 函数。

7.1 自定义类型示例

class MyClass {
public:
    MyClass(int value) : value(value) {}
    int getValue() const { return value; }

    bool operator==(const MyClass &other) const {
        return value == other.value;
    }

private:
    int value;
};

// 提供 qHash 函数
inline uint qHash(const MyClass &key, uint seed) {
    return qHash(key.getValue(), seed);
}

QSet<MyClass> myClassSet;
myClassSet.insert(MyClass(1));
myClassSet.insert(MyClass(2));

7.2 使用自定义类型

for (const MyClass &item : myClassSet) {
    qDebug() << item.getValue();
}

八、QSet不是线程安全的

QSet 不是线程安全的，如果在多个线程中共享 QSet 对象，需要使用适当的同步机制，如互斥锁 (QMutex)、读写锁 (QReadWriteLock) 等。

• 示例代码

下面是一个完整的示例，演示了 QSet 的基本用法：

#include <QCoreApplication>
#include <QSet>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    // 创建和初始化 QSet
    QSet<int> set = {1, 2, 3, 4, 5};

    // 插入元素
    set.insert(6);

    // 删除元素
    set.remove(3);

    // 检查是否包含特定值
    bool contains = set.contains(3);
    qDebug() << "Set contains 3:" << contains;

    // 遍历集合
    for (int value : set) {
        qDebug() << value;
    }

    // 获取集合的大小
    int size = set.size();
    qDebug() << "Set size:" << size;

    // 获取集合的并集
    QSet<int> set1 = {1, 2, 3};
    QSet<int> set2 = {3, 4, 5};
    QSet<int> unionSet = set1.unite(set2);
    qDebug() << "Union set:";
    for (int value : unionSet) {
        qDebug() << value;
    }

    // 获取集合的交集
    QSet<int> intersectionSet = set1.intersect(set2);
    qDebug() << "Intersection set:";
    for (int value : intersectionSet) {
        qDebug() << value;
    }

    // 获取集合的差集
    QSet<int> differenceSet = set1.subtract(set2);
    qDebug() << "Difference set:";
    for (int value : differenceSet) {
        qDebug() << value;
    }

    return a.exec();
}

九、QSet 对比std::set

QSet 和 std::set 是两种不同的集合类，分别由 Qt 框架和标准模板库（STL）提供。它们在底层实现、性能特性和接口设计上都有一些显著的区别。下面详细介绍它们的区别：

9.1 底层数据结构

• QSet:

  • 使用哈希表（基于 QHash）作为底层数据结构。
  • 哈希表提供平均 O(1) 的时间复杂度进行插入、删除和查找操作。

• std::set:

  • 使用红黑树（self-balancing binary search tree）作为底层数据结构。
  • 红黑树提供 O(log n) 的时间复杂度进行插入、删除和查找操作。

9.2 性能特性

• QSet:

  • 由于哈希表的使用，QSet 在插入、删除和查找操作上通常比 std::set 快，尤其是在元素数量较大的情况下。
  • QSet 的性能依赖于哈希函数的质量和哈希冲突的处理。

• std::set:

  • 由于红黑树的使用，std::set 保证所有操作的最坏情况时间复杂度为 O(log n)。
  • std::set 保持元素有序，因此可以进行有序遍历和范围查询。

9.3 元素有序性

• QSet:

  • QSet 中的元素是无序的，插入顺序不被保留。
  • 不能直接对 QSet 进行排序，需要将元素提取出来并使用其他方法排序。

• std::set:

  • std::set 中的元素是有序的，插入顺序与排序顺序相同。
  • 可以使用有序遍历和范围查询。

9.4 内存使用

• QSet:

  • 由于使用哈希表，QSet 在某些情况下可能会使用比 std::set 更多的内存，特别是当哈希冲突较多时。

• std::set:

  • 由于使用红黑树，std::set 的内存使用比较稳定，但每个节点需要额外的内存来存储指针和颜色信息。

9.5 接口和功能

• QSet:

  • 提供了 Qt 风格的接口，适用于使用 Qt 框架开发的应用程序。
  • 与其他 Qt 容器类（如 QList、QMap）有良好的兼容性。
  • 支持一系列便捷的 Qt 特性，如隐式共享（implicit sharing）。

• std::set:

  • 提供了标准 C++ 风格的接口，适用于不依赖于 Qt 框架的应用程序。
  • 与其他 STL 容器（如 std::vector、std::map）有良好的兼容性。
  • 标准 C++ 库的一部分，因此可以与其他标准库组件无缝集成。

9.6 示例代码

9.6.1 QSet 示例

#include <QCoreApplication>
#include <QSet>
#include <QDebug>

int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);

    QSet<int> set;
    set.insert(1);
    set.insert(2);
    set.insert(3);

    for (int value : set) {
        qDebug() << value;
    }

    return a.exec();
}

9.6.2 std::set 示例

#include <iostream>
#include <set>

int main() {
    std::set<int> set;
    set.insert(1);
    set.insert(2);
    set.insert(3);

    for (int value : set) {
        std::cout << value << std::endl;
    }

    return 0;
}

• 总结

• QSet 更适合用于 Qt 框架的应用程序，提供了高效的哈希表实现和便捷的 Qt 风格接口。
• std::set 是标准模板库的一部分，更适合通用的 C++ 应用程序，提供了有序集合的功能和稳定的 O(log n) 性能。

选择 QSet 还是 std::set 取决于具体的应用需求和项目环境。如果需要与 Qt 框架的其他组件进行紧密集成，并且需要高效的集合操作，可以选择 QSet。如果需要有序集合操作，并且希望与标准 C++ 库兼容，可以选择 std::set。

通过以上内容，你应该能够掌握 QSet 的基本用法，并能在自己的项目中灵活使用它。

其他QT文章
1. QT开发环境安装以配置。
2. QT线段画板实战
3. 半小时玩转QT桌面系统托盘(含托盘消息)
4. QT入门开发一个时钟
5. 半小时教你做大转盘游戏（QT篇）
6. 手把手教你制作【带吸附效果的线段绘制】（QT）
7. 手把手教你开发-滚动效果号码抽奖（QT）
8. 100行代码实现贪吃蛇小游戏
9.C++实现《扫雷》游戏（入门经典）
10. svg转图片工具开发
11. Qt网路与通信(获取本机网络信息）
12. Qt网路与通信(UDP客户与服务）
13. Qt网络与通信（TCP聊天室）
14. Qt多线程以及线程池
15. Qt散点图、折线图、柱状图、盒须图、饼状图、雷达图开发实例
16. 取色器（QT）
17. MQTT客户端入门开发
18.QT文件上传带进度条实例（含源码）
19. Qt音乐播放器开发实例（可毕设含源码）
​