Qt4 Sequential Container

Posted on Edited on

這篇是看 Qt4 Container 相關網頁的筆記，包含三種 Sequential Container：QVector、QList、QLinkedList。PS：Qt 已經出到 5。（2014/4/21）

QVector

QVector 使用一塊連續的 memory。

QVector

QVector

QVector 是 implicitly shared，有時稱為 copy on write。copy 一 QVector 時，只會 copy pointer d 以及增加 reference count ref。從以下 copy constructor 及 assignment operator 可以看出來：

copy constructor in Qt 4.8.0 qvector.h
1
inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
assignment operator in Qt 4.8.0 qvector.h
1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
QVector<T> &QVector<T>::operator=(const QVector<T> &v)
{
    QVectorData *o = v.d;
    o->ref.ref();
    if (!d->ref.deref())
        free(p);
    d = o;
    if (!d->sharable)
        detach_helper();
    return *this;
}

QVector 依據 T 的 type 決定如何增加 size。T 是 movable 則用 realloc() 每次增加 4096 bytees。T 是 non-movable，則每次增加 50% 的size。

movable：a data type that can safely be moved around in memory using memcpy() or memmove(), such as the C++ primitive types and Qt’s implicitly shared classes.

QList

QList 以 array list 的方式 implement，不是用 linked list。它的 array 裡是一堆指標，指向 data T，如下圖：

QList

QList 會在它的 array 前面保留一些空間，以 begin 跟 end 記錄保留的空間是哪一段。這麼做方便在 list 的前面增加、移除 data，並且當要在 list 中間 insert data 時，前面保留的空間可作為資料移動的空間，因為它是 array list，不像 linked list 可以直接改 pointer 來 insert data。例如要塞一個 data 到位置 k，可把原本前面 k-1 個 data 往前面移。

如果前面保留的空間用完了？

QLinkedList

提供 doubly linked list。適合龐大資料以及需要 O(1) 的 insertion 跟 removal。如果資料量在 200 element 以下，QList 的 performance 比較好。

選擇 sequential container

QVector、QList、QLinkedList 有不同特性，如何選擇使用哪個？

  • 大多數時候可選擇 QList。它使用 index-based API，比 QLinkedList 的 iterator-based API 方便，速度通常比 QVector 快，而且生出來的可執行 code 也較短。
  • 如果需要一個真正的 linked list，希望 insert data 到 list 中間花的時間是 constant time，且想使用 iterator，則用 QLinkedList。
  • 如果希望 element 佔據的 memory 是連續的，選擇 QVector。

Ref