Featured image of post Qt 不同容器探究

Qt 不同容器探究

Qt 库提供了一组基于模板的通用容器类, 本文探讨不同容器在 Qt 5 和 Qt 6 中的底层实现差异。

前言

Qt 库提供了一组基于模板的通用容器类,与 STL 容器相比,这些容器类更轻便、更安全、更易用。容器类是隐式共享的,它们是可重入的,而且它们经过了优化,速度快、内存消耗低、内联代码扩展最少,因此可执行文件更小。此外,在所有用于访问它们的线程都将它们用作只读容器的情况下,它们是线程安全的。

本文重点探讨不同容器在 Qt 5 和 Qt 6 中的实现差异,揭示底层设计变化对性能和使用的影响。通过源码分析,我们将理解 Qt 容器设计的演进逻辑。

Qt 5 版本

QQueue

基于 QList 的队列,继承了 QList。在 QList 基础上中增加了几个方法:

  • enqueue() → 调用 QList::append()
  • dequeue() → 调用 QList::takeFirst()
  • head() → 调用 QList::first()

qt-everywhere-src-5.15.2\qtbase\src\corelib\tools\qqueue.h 源码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
template <class T>
class QQueue : public QList<T>
{
public:
    // compiler-generated special member functions are fine!
    inline void swap(QQueue<T> &other) noexcept { QList<T>::swap(other); } // prevent QList<->QQueue swaps
#if QT_DEPRECATED_SINCE(5, 14) && !defined(Q_QDOC)
    // NOT using QList<T>::swap; it would make swap(QList&) available.
    QT_DEPRECATED_VERSION_X_5_14("Use swapItemsAt(i, j) instead")
    inline void swap(int i, int j) { QList<T>::swapItemsAt(i, j); }
#endif
    inline void enqueue(const T &t) { QList<T>::append(t); }
    inline T dequeue() { return QList<T>::takeFirst(); }
    inline T &head() { return QList<T>::first(); }
    inline const T &head() const { return QList<T>::first(); }
};

QStack

基于 QVector 的栈,继承了 QVector。在 QVector 基础上增加了几个方法:push ()、pos ()、top ()。

  • pop() 直接操作内存索引(非简单调用 takeLast()
  • top() 调用 detach() 确保写时复制

qt-everywhere-src-5.15.2\qtbase\src\corelib\tools\qstack.h 源码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<class T>
class QStack : public QVector<T>
{
public:
    // compiler-generated special member functions are fine!
    inline void swap(QStack<T> &other) noexcept { QVector<T>::swap(other); } // prevent QVector<->QStack swaps
    inline void push(const T &t) { QVector<T>::append(t); }
    T pop();
    T &top();
    const T &top() const;
};

template<class T>
inline T QStack<T>::pop()
{ Q_ASSERT(!this->isEmpty()); T t = this->data()[this->size() -1];
  this->resize(this->size()-1); return t; }

template<class T>
inline T &QStack<T>::top()
{ Q_ASSERT(!this->isEmpty()); this->detach(); return this->data()[this->size()-1]; }

template<class T>
inline const T &QStack<T>::top() const
{ Q_ASSERT(!this->isEmpty()); return this->data()[this->size()-1]; }

QSet

QSet 是基于 QHash 实现的集合,值部分使用空结构体。

qt-everywhere-src-5.15.2\qtbase\src\corelib\tools\qset.h 源码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
template <class T>
class QSet
{
    typedef QHash<T, QHashDummyValue> Hash;

public:
    inline QSet() noexcept {}
    inline QSet(std::initializer_list<T> list)
        : QSet(list.begin(), list.end()) {}
    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
    inline QSet(InputIterator first, InputIterator last)
    {
        QtPrivate::reserveIfForwardIterator(this, first, last);
        for (; first != last; ++first)
            insert(*first);
    }

private:
    Hash q_hash;
};

Qt 6 版本

在 Qt 6 之后,容器底层发生了变化。

QVector

QVector 在 Qt 6 版本中,是 QList 的别名。

Qt\6.8.2\msvc2022_64\include\QtCore\qcontainerfwd.h 源码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
#ifndef Q_QDOC
template<typename T> using QVector = QList<T>;
using QStringList = QList<QString>;
class QByteArray;
using QByteArrayList = QList<QByteArray>;
#else
template<typename T> class QVector;
class QStringList;
class QByteArrayList;
#endif

QList

在 Qt 6 中,QList 和 QVector 被统一了。这意味着 QList 并非以链表形式实现,现在是一个提供动态数组的模板类,它将项目存储在相邻的内存位置,并提供基于索引的快速访问。因此如果您需要在常量时间内进行插入、删除、追加或前置操作,请考虑使用 std::list

QStack

在 Qt 6 之后,QStack 实质上是继承 QList 了

Qt\6.8.2\msvc2022_64\include\QtCore\qstack.h 源码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
template<class T>
class QStack : public QList<T>
{
public:
    // compiler-generated special member functions are fine!
    void swap(QStack<T> &other) noexcept { QList<T>::swap(other); } // prevent QList<->QStack swaps
    void push(const T &t) { QList<T>::append(t); }
    T pop() { return QList<T>::takeLast(); }
    T &top() { return QList<T>::last(); }
    const T &top() const { return QList<T>::last(); }
};

总结

容器底层的实现替换,通常是无感的,但是理解这些底层变化,将是有帮助的,可以在日常开发中写出更高效的代码。

Container Classes | Qt Core | Qt 6.9.1

Licensed under CC BY-NC-SA 4.0