這篇基本是翻譯的Qt官方文件，部落格要求附原貼地址，嫌煩，就厚着臉皮說是原創了，實際非原創！版權歸Qt所有！

另外 QLinkedList is obsolete. 不再推薦使用。

Qt Container

介紹

Qt庫提供了一組基於通用模板的容器類。這些類可用於儲存指定型別的專案。例如，如果需要可調整大小的QString陣列，請使用QVector<QString>。

這些容器類的設計比STL容器更輕，更安全且更易於使用。如果您不熟悉STL，或者更喜歡以「Qt方式」進行操作，則可以使用這些類而不是STL類。

容器類是隱式共用的，它們是可重入的，並且已針對速度，低記憶體消耗和最小的內聯程式碼擴充套件進行了優化，從而生成了較小的可執行檔案。此外，在所有用於存取它們的執行緒都將它們用作只讀容器的情況下，它們是執行緒安全的。

要遍歷儲存在容器中的專案，可以使用兩種型別的迭代器之一：Java樣式的迭代器和STL樣式的迭代器。Java樣式的迭代器更易於使用並提供高階功能，而STL樣式的迭代器效率更高，並且可以與Qt和STL的通用演算法一起使用。

Qt還提供了一個foreach關鍵字，可以很容易地遍歷容器中儲存的所有專案。

注意：從Qt5.14開始，範圍構造器可用於大多數容器類。QMultiMap是一個明顯的例外。鼓勵使用它們代替各種from/to方法。例如：

QVector<int> vector{1, 2, 3, 4, 4, 5};

QSet<int> set(vector.begin(), vector.end());

Will generate a QSet containing 1, 2, 4, 5.

具體容器類

順序容器：QList，QLinkedList，QVector，QStack和QQueue

對於大多數應用程式，QList是最佳使用型別。儘管它是作爲陣列列表實現的，但它提供了非常快的前置和追加操作。

如果您確實需要一個鏈表，請使用QLinkedList。

如果希望專案佔據連續的記憶體位置，請使用QVector。

QStack和QQueue是提供LIFO和FIFO語意的便捷類。

關聯容器：QMap，QMultiMap，QHash，QMultiHash和QSet。

Multi容器方便地支援與單個鍵關聯的多個值。

Hash 容器通過使用雜湊函數而不是對排序集進行二進制搜尋來提供更快的查詢。

快取儲存：QCache和QContiguousCache

這兩個類在有限的快取儲存中提供了物件的有效雜湊查詢。

Class	摘要
QList<T>	最常用的容器類。儲存可以通過索引存取的給定型別（T）的值的列表。在內部，QList是使用陣列實現的，從而確保基於索引的存取非常快。使用QList::append（）和QList::prepend（）將專案新增到列表的任一端使用QList::insert（）將它們插入中間。與其他任何容器類相比，QList經過了高度優化，可以在可執行檔案中擴充套件爲儘可能少的程式碼。
QLinkedList<T>	類似QList，不同之處在於它使用迭代器而不是整數索引來存取專案。當插入大列表中間時，它還提供比QList更好的效能，並且具有更好的迭代器語意。（指向QLinkedList中某個專案的迭代器只要該專案存在就保持有效，而QList的迭代器在任何插入或刪除後都可能變爲無效。）
QVector<T>	將給定型別的值的陣列儲存在記憶體中的相鄰位置。在向量的前面或中間插入可能會非常慢，因爲這可能導致大量專案必須在記憶體中移動一個位置。
QVarLengthArray <T,Prealloc>	這提供了一個低階的可變長度陣列。在速度特別重要的地方，可以使用它代替QVector。
QStack<T>	這是QVector的便利子類，它提供「後進先出」（LIFO）語意。它爲QVector中已經存在的功能新增了以下功能：push（），pop（）和top（）。
QQueue<T>	這是QList的便利子類，它提供「先進先出」（FIFO）語意。它爲QList中已經存在的功能新增以下功能：enqueue（），dequeue（）和head（）。
QSet<T>	這提供了具有快速查詢功能的單值數學集。
QMap<Key,T>	這提供了一個字典（關聯陣列），該字典將Key型別的鍵對映到T型別的值。通常，每個鍵都與一個值相關聯。QMap以金鑰順序儲存其數據；如果順序無關緊要，則QHash是更快的選擇。
QMultiMap<Key,T>	這是QMap的便利子類，它爲多值對映（即一個鍵可以與多個值關聯的對映）提供了一個不錯的介面。
QHash<Key,T>	它具有與QMap幾乎相同的API，但是提供了明顯更快的查詢。QHash以任意順序儲存其數據。
QMultiHash <Key,T>	這是QHash的便利子類，它爲多值雜湊提供了一個不錯的介面。

容器可以巢狀。例如，完全可以使用QMap<QString，QList<int>>，其中鍵型別爲QString，值型別爲QList<int>。
容器在單獨的標頭檔案中定義，並與容器具有相同的名稱（例如，<QLinkedList>）。爲了方便起見，在<QtContainerFwd>中對容器進行了前向宣告。
儲存在各個容器中的值可以是任何可分配的數據型別。要獲得資格，型別必須提供複製建構函式和賦值運算子。對於某些操作，還需要預設建構函式。
涵蓋了要儲存在容器中的大多數數據型別，包括基本型別（例如int和double），指針型別以及Qt數據型別（例如QString，QDate和QTime），
不包括QObject或任何其他物件。QObject子類（QWidget，QDialog，QTimer等）。如果嘗試範例化QList<QWidget>，則編譯器將抱怨QWidget的副本建構函式和賦值運算子已禁用。如果要將此類物件儲存在容器中，請將它們儲存爲指針，例如，儲存爲QList<QWidget*>。

範例：滿足要求的自定義數據型別：

class Employee

{

public:

Employee() {}

Employee(const Employee &other);

Employee &operator=(const Employee &other);

private:

QString myName;

QDate myDateOfBirth;

};

如果我們不提供複製建構函式或賦值運算子，則C++提供一個預設實現，該實現執行逐成員複製。在上面的範例中，這就足夠了。另外，如果您不提供任何建構函式，則C++提供了一個預設建構函式，該建構函式使用預設建構函式初始化其成員。儘管它不提供任何顯式的建構函式或賦值運算子，但可以將以下數據型別儲存在容器中：

struct Movie

{

int id;

QString title;

QDate releaseDate;

};

某些容器對儲存的數據型別有其他要求。例如，QMap<Key，T>的Key型別必須提供operator<( )。這些特殊要求記錄在類的詳細說明中。在某些情況下，特定功能有特殊要求；這些是按功能描述的。如果不滿足要求，編譯器將始終發出錯誤。

Qt的容器提供operator<<( )和operator>>( )，以便可以使用QDataStream輕鬆讀取和寫入它們。這意味着儲存在容器中的數據型別還必須支援operator<<( )和operator>>( )。提供這種支援很簡單；這是我們如何對上面的Movie結構執行此操作：

QDataStream &operator<<(QDataStream &out, const Movie &movie)

{

out << (quint32)movie.id << movie.title << movie.releaseDate;

return out;

}

QDataStream &operator>>(QDataStream &in, Movie &movie)

{

quint32 id;

QDate date;

in >> id >> movie.title >> date;

movie.id = (int)id;

movie.releaseDate = date;

return in;

}

某些容器類函數的文件指的是預設構造的值。例如，QVector使用預設構造的值自動初始化其項，如果指定的鍵不在對映中，則QMap::value( )返回預設構造的值。

對於大多數值型別，這僅表示使用預設建構函式(例如，QString爲空字串)建立值。但是對於int和double之類的原始型別以及指針型別，C++語言未指定任何初始化；在這種情況下，Qt的容器會自動將該值初始化爲0。

迭代器類

迭代器提供了存取容器中專案的統一方法。Qt的容器類提供兩種型別的迭代器：Java樣式的迭代器和STL樣式的迭代器。當容器中的數據由於對非常數成員函數的呼叫而被修改或從隱式共用副本中分離時，兩種型別的迭代器均無效。

Java樣式迭代器

Java樣式的迭代器是Qt4中的新增功能，並且是Qt應用程式中使用的標準迭代器。它們比STL樣式的迭代器更方便使用，但代價是效率略低。他們的API以Java的迭代器類爲模型。

對於每個容器類，有兩種Java樣式的迭代器數據型別：一種提供只讀存取，另一種提供讀寫存取。

容器	只讀迭代器	讀寫迭代器
QList <T>, QQueue <T>	QListIterator <T>	QMutableListIterator <T>
QLinkedList<T>	QLinkedListIterator<T>	QMutableLinkedListIterator<T>
QVector <T>, QStack <T>	QVectorIterator <T>	QMutableVectorIterator <T>
QSet <T>	QSetIterator <T>	QMutableSetIterator <T>
QMap <Key, T>, QMultiMap <Key, T>	QMapIterator <Key, T>	QMutableMapIterator <Key, T>
QHash <Key, T>, QMultiHash <Key, T>	QHashIterator <Key, T>	QMutableHashIterator <Key, T>

在此討論中，我們將專注於QList和QMap。QLinkedList，QVector和QSet的迭代器型別與QList的迭代器具有完全相同的介面。同樣，QHash的迭代器型別與QMap的迭代器具有相同的介面。

與STL樣式的迭代器（如下所述）不同，Java樣式的迭代器在專案之間指向而不是直接指向專案。因此，它們要麼指向容器的最開始（在第一個專案之前），要麼指向容器的最末端（在最後一個專案之後），或者指向兩個專案之間。

下圖包含四個專案的列表中的紅色箭頭爲有效的迭代器位置：

這是一個典型的回圈，用於依次遍歷QList<QString>的所有元素並將其列印到控制檯：

它的工作方式如下：將要迭代的QList傳遞給QListIterator建構函式。此時，迭代器位於列表中第一個專案的前面(專案「A」之前)。然後我們呼叫hasNext( )來檢查迭代器之後是否有一個專案。如果存在，我們呼叫next( )跳過該專案。next( )函數返回它跳過的專案。對於QList<QString>，該專案的型別爲QString。

#include <QtCore>

int main(/*int argc, char *argv[]*/)

{

QList<QString> list;

list << "A" << "B" << "C" << "D";

QListIterator<QString> i(list);

while (i.hasNext())

qDebug() << i.next();

}

這是在QList中向後迭代的方法：

QListIterator<QString> i(list);

i.toBack();

while (i.hasPrevious())

qDebug() << i.previous();

該程式碼是向前迭代對稱的，除了我們從呼叫toBack( )開始，以將迭代器移動到列表中的最後一項之後。

下圖說明了在迭代器上呼叫next( )和previous( )的效果：

下表總結了QListIterator API：

Function	行爲
toFront()	將迭代器移到列表的開頭（在第一項之前）
toBack()	將迭代器移到列表的末尾（最後一項之後）
hasNext()	如果迭代器不在列表的後面，則返回true
next()	返回下一項並將迭代器前進一個位置
peekNext()	返回下一項而不移動迭代器
hasPrevious()	如果迭代器不在列表的最前面，則返回true
previous()	返回上一項，並將迭代器後退一個位置
peekPrevious()	返回上一項而不移動迭代器

QListIterator不提供在迭代時從列表中插入或刪除專案的功能。爲此，必須使用QMutableListIterator。這是一個範例，其中我們使用QMutableListIterator從QList<int>中刪除所有奇數：

#include <QtCore>

int main(/*int argc, char *argv[]*/)

{

QList<int> list;

list << 1 << 2 << 3 << 4 << 5 << 6;

qDebug() << list;

QMutableListIterator<int> i(list);

while (i.hasNext()) {

if (i.next() % 2 != 0)

i.remove();

}

qDebug() << list;

}

每次都會在回圈中進行next( )呼叫。它將跳過列表中的下一項。remove( )函數從列表中刪除我們跳過的最後一項。呼叫remove( )不會使迭代器無效，因此可以安全地繼續使用它。向後迭代時，效果也一樣：

QMutableListIterator<int> i(list);

i.toBack();

while (i.hasPrevious()) {

if (i.previous() % 2 != 0)

i.remove();

}

qDebug() << list;

如果我們只想修改現有專案的值，則可以使用setValue( )。在下面下麪的程式碼中，我們將大於128的任何值替換爲128：

#include <QtCore>

int main(/*int argc, char *argv[]*/)

{

QList<int> list;

list << 10 << 50 << 150 << 200 << 250 << 300;

qDebug() << list;

QMutableListIterator<int> i(list);

while (i.hasNext()) {

if (i.next() > 128)

i.setValue(128);

}

qDebug() << list;

}

就像remove( )一樣，setValue( )對我們跳過的最後一項進行操作。如果我們向前迭代，這就是迭代器之前的專案；如果我們向後迭代，則這是迭代器之後的專案。

next( )函數返回對列表中專案的非常數參照。對於簡單的操作，我們甚至不需要setValue( )：

QMutableListIterator<int> i(list);

while (i.hasNext())

i.next() *= 2;

qDebug() << list;

如上所述，QLinkedList，QVector和QSet的迭代器類具有與QList完全相同的API。現在，我們轉向QMapIterator，它有所不同，因爲它在(鍵，值)對上進行迭代。

與QListIterator一樣，QMapIterator提供toFront( )，toBack( )，hasNext( )，next( )，peekNext( )，hasPrevious( )，previous( )和peekPrevious( )。通過在next( )，peekNext( )，previous( )或peekPrevious( )返回的物件上呼叫key( )和value( )來提取鍵和值分量。

下面下麪的範例刪除所有首都名稱以「City」結尾的（capital,country）對：

#include <QtCore>

int main(/*int argc, char *argv[]*/)

{

QMap<QString, QString> map;

map.insert("Paris", "France");

map.insert("Guatemala City", "Guatemala");

map.insert("Mexico City", "Mexico");

map.insert("Moscow", "Russia");

qDebug() << map;

QMutableMapIterator<QString, QString> i(map);

while (i.hasNext()) {

if (i.next().key().endsWith("City"))

i.remove();

}

qDebug() << map;

}

QMapIterator還提供了直接在迭代器上執行的key( )和value( )函數，並返回迭代器跳轉到其上的最後一項的鍵和值。例如，以下程式碼將QMap的內容複製到QHash中：

int main()

{

QMap<QString, QString> map;

map.insert("Paris", "France");

map.insert("Guatemala City", "Guatemala");

map.insert("Mexico City", "Mexico");

map.insert("Moscow", "Russia");

qDebug() << map;

QHash<QString, QString> hash;

QMapIterator<QString, QString> i(map);

while (i.hasNext()) {

i.next();

hash.insert(i.key(), i.value());

}

qDebug() << hash;

}

如果要遍歷具有相同值的所有專案，則可以使用findNext( )或findPrevious( )。這是一個範例，其中我們刪除了具有特定值的所有專案：

int main()

{

QMap<QString, QString> map;

map.insert("Paris", "France");

map.insert("Guatemala City", "Guatemala");

map.insert("Mexico City", "Mexico");

map.insert("Moscow", "Russia");

map.insert("MO?", "Russia");

qDebug() << map;

QMutableMapIterator<QString,QString> i(map);

while (i.findNext("Russia"))

i.remove();

qDebug() << map;

}

STL 樣式迭代器

自Qt2.0發行以來，已經可以使用STL樣式的迭代器。它們與Qt和STL的通用演算法相容，並針對速度進行了優化。

對於每個容器類，有兩種STL樣式的迭代器型別：一種提供只讀存取，另一種提供讀寫存取。應儘可能使用只讀迭代器，因爲它們比讀寫迭代器快。

容器	只讀迭代器	讀寫迭代器
QList<T>, QQueue<T>	QList<T>::const_iterator	QList<T>::iterator
QLinkedList<T>	QLinkedList<T>::const_iterator	QLinkedList<T>::iterator
QVector<T>, Stack<T>	QVector<T>::const_iterator	QVector<T>::iterator
QSet<T>	QSet<T>::const_iterator	QSet<T>::iterator
QMap<Key, T>, QMultiMap<Key, T>	QMap<Key, T>::const_iterator	QMap<Key, T>::iterator
QHash<Key, T>, QMultiHash<Key, T>	QHash<Key, T>::const_iterator	QHash<Key, T>::iterator

STL迭代器的API以陣列中的指針爲模型。例如，++運算子將迭代器前進到下一個專案，而*運算子將返回迭代器指向的專案。實際上，對於將其項儲存在相鄰記憶體位置的QVector和QStack而言，迭代器型別僅爲T*的typedef，而const_iterator型別僅爲constT*的typedef。

這是一個典型的回圈，用於依次遍歷QList<QString>的所有元素並將其轉換爲小寫：

int main()

{

QList<QString> list;

list << "A" << "B" << "C" << "D";

qDebug() << list;

QList<QString>::iterator i;

for (i = list.begin(); i != list.end(); ++i)

*i = (*i).toLower();

qDebug() << list;

}

與Java樣式的迭代器不同，STL樣式的迭代器直接指向專案。容器的begin( )函數返回一個迭代器，該迭代器指向容器中的第一項。容器的end( )函數將迭代器返回到虛數項，該虛項在容器中最後一項之後。end( )標記無效位置；絕對不能取消參照。它通常用於回圈的中斷條件中。如果列表爲空，則begin( )等於end( )，因此我們從不執行回圈。

下圖將有效迭代器位置顯示爲包含四個專案的向量的紅色箭頭：

使用STL樣式的迭代器反向迭代是通過反向迭代器完成的：

int main()

{

QList<QString> list;

list << "A" << "B" << "C" << "D";

QList<QString>::reverse_iterator i;

for (i = list.rbegin(); i != list.rend(); ++i) {

*i = i->toLower();

qDebug() << *i;

}

到目前爲止，在程式碼片段中，我們使用一元*運算子檢索儲存在某個迭代器位置的QString型別的專案，然後在其上呼叫QString::toLower( )。大多數C++編譯器還允許我們編寫i->toLower( )，但有些則不允許。

對於只讀存取，可以使用const_iterator，constBegin( )和constEnd( )。例如：

int main()

{

QList<QString> list;

list << "A" << "B" << "C" << "D";

QList<QString>::const_iterator i;

for (i = list.constBegin(); i != list.constEnd(); ++i)

qDebug() << *i;

}

下表總結了STL樣式的迭代器的API：

Expression	行爲
*i	返回當前專案
++i	將迭代器前進到下一個專案
i += n	使迭代器前進n個專案
--i	將迭代器後退一個專案
i -= n	將迭代器後退n個專案
i - j	返回迭代器i和j之間的專案數

++和-運算子可用作字首(++i，--i)和後綴(i++，i--)運算子。字首版本會修改迭代器，並返回對修改後的迭代器的參照；後綴版本在修改迭代器之前先獲取它的副本，然後返回該副本。在忽略返回值的表達式中，我們建議您使用字首運算子(++i，--i)，因爲它們稍快一些。

對於非常數迭代器型別，可以在賦值運算子的左側使用一元*運算子的返回值。

對於QMap和QHash，*運算子返回專案的值元件。如果要檢索金鑰，請在迭代器上呼叫key( )。爲了對稱起見，迭代器型別還提供了value( )函數來檢索該值。例如，這是我們將QMap中的所有專案列印到控制檯的方法：

int main()

{

QMap<QString, QString> map;

map.insert("Paris", "France");

map.insert("Guatemala City", "Guatemala");

map.insert("Mexico City", "Mexico");

map.insert("Moscow", "Russia");

QMap<QString, QString>::const_iterator i;

for (i = map.constBegin(); i != map.constEnd(); ++i)

qDebug() << i.key() << ':' << i.value();

}

由於隱式共用，函數爲每個值返回一個容器非常便宜。Qt API包含許多函數，這些函數返回一個QList或QStringList(例如，QSplitter::sizes( ))。如果要使用STL迭代器對其進行迭代，則應始終獲取容器的副本並對該副本進行迭代。例如：

// RIGHT

const QList<int> sizes = splitter->sizes();

QList<int>::const_iterator i;

for (i = sizes.begin(); i != sizes.end(); ++i)

...

// WRONG

QList<int>::const_iterator i;

for (i = splitter->sizes().begin();

i != splitter->sizes().end(); ++i)

...

對於將const或非const參照返回到容器的函數，不會發生此問題。

隱式共用迭代器的問題

隱式共用在STL樣式的迭代器上還有另一個後果：當迭代器在該容器上處於活動狀態時，應避免複製該容器。迭代器指向內部結構，如果您複製容器，則應非常小心使用迭代器。例如：

QVector<int> a, b;

a.resize(100000); // make a big vector filled with 0.

QVector<int>::iterator i = a.begin();

// WRONG way of using the iterator i:

b = a;

現在我們應該對迭代器i保持謹慎，因爲它將指向共用數據

如果我們做 *i = 4，那麼我們將更改共用範例（兩個向量）

該行爲與STL容器不同。避免在Qt中執行此類操作。

a[0] = 5;

現在，容器a已從共用數據中分離出來，

即使 i 是容器a中的迭代器，它現在也可以作爲b中的迭代器。

這裏的情況是（* i）== 0。

b.clear(); // 現在，迭代器i完全無效。

int j = *i; //未定義的行爲！

來自b的數據（ i 指出）消失了。

使用STL容器（和（* i）== 5）可以很好地定義這一點，

但是使用QVector可能會崩潰。

上面的範例僅顯示了QVector的問題，但是所有隱式共用的Qt容器都存在該問題。

foreach關鍵字

如果只想按順序遍歷容器中的所有專案，則可以使用Qt的foreach關鍵字。關鍵字是Qt特定於C++語言的新增，並使用前處理器實現。

它的語法是：foreach(變數，容器)語句。例如，以下是使用foreach遍歷QLinkedList<QString>的方法：

int main()

{

QLinkedList<QString> list;

list.append("one");

list.append("two");

list.append("three");

QString str;

foreach (str, list)

qDebug() << str;

}

foreach程式碼明顯短於使用迭代器的等效程式碼：

QLinkedList<QString> list;

...

QLinkedListIterator<QString> i(list);

while (i.hasNext())

qDebug() << i.next();

除非數據型別包含逗號(例如QPair<int，int>)，否則可以在foreach語句中定義用於迭代的變數：

QLinkedList<QString> list;

...

foreach (const QString &str, list)

qDebug() << str;

與其他任何C++回圈構造一樣，您可以在foreach回圈的主體周圍使用花括號，並且可以使用break離開回圈：

QLinkedList<QString> list;

...

foreach (const QString &str, list) {

if (str.isEmpty())

break;

qDebug() << str;

}

使用QMap和QHash，foreach會自動存取(鍵，值)對的值元件，因此您不應在容器上呼叫values( )(它會生成不必要的副本，請參見下文)。如果要遍歷鍵和值，則可以使用迭代器(速度更快)，也可以獲取鍵，並使用它們來獲取值：

QMap<QString, int> map;

...

foreach (const QString &str, map.keys())

qDebug() << str << ':' << map.value(str);

對於多值對映：

QMultiMap<QString, int> map;

...

foreach (const QString &str, map.uniqueKeys()) {

foreach (int i, map.values(str))

qDebug() << str << ':' << i;

}

當Qt進入foreach回圈時，它會自動獲取該容器的副本。如果在迭代時修改容器，則不會影響回圈。(如果不修改容器，則仍會進行復制，但是由於隱式共用，複製容器非常快。)

由於foreach會建立容器的副本，因此對變數使用非常數參照將不允許您修改原始容器。它只會影響副本，可能不是您想要的。

Qt的foreach回圈的替代方法是基於範圍的，它是C++11和更高版本的一部分。但是，請記住，基於範圍的for可能會強制Qt容器分離，而foreach則不會。但是使用foreach總是會複製容器，這對於STL容器通常並不便宜。如有疑問，對於Qt容器，首選foreach，對於STL容器，首選基於範圍。

除了foreach之外，Qt還爲無限回圈提供了永遠的僞關鍵字：

forever {

...

}

如果您擔心名稱空間污染，可以通過在.pro檔案中新增以下行來禁用這些宏：

CONFIG += no_keywords

其他類似容器的類

Qt包括在某些方面類似於容器的其他模板類。這些類不提供迭代器，因此不能與foreach關鍵字一起使用。

QCache<Key，T>提供了一個快取，用於儲存與Key型別的鍵相關聯的T型別的物件。
QContiguousCache<T>提供了一種快取數據的有效方法，該數據通常以連續的方式存取。
QPair<T1，T2>儲存一對元素。

與Qt的模板容器競爭的其他非模板型別是QBitArray，QByteArray，QString和QStringList。

演算法的複雜性

演算法複雜度關係到每個功能隨着容器中專案數量的增長有多快(或慢)。例如，無論QLinkedList中儲存的專案數如何，在QLinkedList的中間插入專案都是非常快速的操作。另一方面，如果QVector包含許多專案，則在QVector的中間插入專案可能非常昂貴，因爲一半專案必須在記憶體中移動一個位置。

爲了描述演算法的複雜性，我們基於「bigOh」表示法使用以下術語：

恆定時間：O(1)。如果某個功能需要相同的時間量，則無論容器中有多少個物品，該功能都將在恆定時間內執行。一個範例是QLinkedList::insert( )。
對數時間：O(logn)。以對數時間執行的函數是其執行時間與容器中專案數的對數成正比的函數。一個例子是二進制搜尋演算法。
線性時間：O(n)。以線性時間執行的函數將在與容器中儲存的專案數量成正比的時間內執行。一個範例是QVector::insert( )。
線性對數時間：O(nlogn)。線上性對數時間中執行的函數在漸近上比線性時間函數慢，但比二次時間函數快。
二次時間：O(n²)。二次時間函數的執行時間與容器中儲存的專案數的平方成正比。

下表總結了Qt的順序容器類的演算法複雜性：

	Index lookup	Insertion	Prepending	Appending
QLinkedList<T>	O(n)	O(1)	O(1)	O(1)
QList<T>	O(1)	O(n)	Amort. O(1)	Amort. O(1)
QVector<T>	O(1)	O(n)	O(n)	Amort. O(1)

在表中，「Amort」。代表「攤銷行爲」。例如，「Amort.O(1)」表示如果僅呼叫一次函數，則可能會得到O(n)行爲，但是如果多次呼叫(例如，n次)，則平均行爲將爲O(1)。

下表總結了Qt關聯容器和集合的演算法複雜性：

	Key lookup		Insertion
	Average	Worst case	Average	Worst case
QMap<Key, T>	O(log n)	O(log n)	O(log n)	O(log n)
QMultiMap<Key, T>	O(log n)	O(log n)	O(log n)	O(log n)
QHash<Key, T>	Amort. O(1)	O(n)	Amort. O(1)	O(n)
QSet<Key>	Amort. O(1)	O(n)	Amort. O(1)	O(n)

使用QVector，QHash和QSet，附加項的效能攤銷爲O(logn)。在插入專案之前，可以通過呼叫QVector::reserve( )，QHash::reserve( )或QSet::reserve( )並使用預期的專案數將其降至O(1)。下一節將更深入地討論該主題。

成長策略

QVector<T>，QString和QByteArray將它們的專案連續儲存在記憶體中；QList<T>維護指向其儲存的專案的指針陣列，以提供基於索引的快速存取(除非T是指針型別或指針大小的基本型別，在這種情況下，值本身儲存在陣列中);QHash<Key，T>保留一個雜湊表，其大小與雜湊中的項數成正比。爲了避免每次在容器末尾新增專案時重新分配數據，這些類通常分配的記憶體超出了必要。

考慮以下程式碼，該程式碼從另一個QString構建一個QString：

QString onlyLetters(const QString &in)

{

QString out;

for (int j = 0; j < in.size(); ++j) {

if (in[j].isLetter())

out += in[j];

}

return out;

}

我們通過一次附加一個字元來動態構建字串。假設我們在QString字串後附加15000個字元。然後，當QString空間不足時，會發生以下18個重新分配(可能的15000個)：4，8，12，16，16，20，52，116，244，500，1012，2036，4084，6132，8180，10228，12276、14324、16372。最後，QString分配了16372個Unicode字元，其中15000個被佔用。

上面的值可能看起來有些奇怪，但是這裏是指導原則：

QString一次分配4個字元，直到達到大小20。
從20到4084，每次將大小增加一倍就可以提高。更準確地說，它前進到下一個2的冪，再減去12。(某些記憶體分配器在要求精確的2的冪時效能最差，因爲它們在每個塊中使用幾個位元組進行記賬。)
從4084開始，它前進2048個字元(4096位元組)的塊。這是有道理的，因爲現代操作系統在重新分配緩衝區時不會複製整個數據。只需簡單地對實體記憶體頁面進行重新排序，實際上只需要複製首頁和最後一頁上的數據。

QByteArray和QList<T>使用與QString大致相同的演算法。

QVector<T>還使用該演算法處理可以使用memcpy( )在記憶體中移動的數據型別(包括基本的C++類別型，指針型別和Qt的共用類)，但對只能使用通過呼叫複製建構函式和解構函式進行移動。由於在這種情況下重新分配的成本較高，因此QVector<T>通過在空間不足時始終將記憶體翻倍來減少重新分配的次數。

QHash<Key，T>是完全不同的情況。QHash的內部雜湊表以2的冪次方增長，並且每次增長時，這些項都將重新放置在新的儲存桶中，計算方式爲qHash(key) ％ QHash::capacity( )(儲存桶數)。此註釋也適用於QSet<T>和QCache<Key，T>。

對於大多數應用程式，Qt提供的預設增長演算法可以解決問題。如果需要更多控制，QVector<T>，QHash<Key，T>，QSet<T>，QString和QByteArray提供了三個函數，可讓您檢查並指定用於儲存專案的記憶體量：

Capacity（）返回爲其分配記憶體的專案數（對於QHash和QSet，爲雜湊表中的儲存桶數）。
reserve（size）顯式預分配大小專案的記憶體。
squeeze（）釋放不需要儲存專案的任何記憶體。

如果您知道將在一個容器中儲存大約多少個專案，則可以通過呼叫reserve（）開始，然後在完成容器的填充後，可以呼叫squeeze（）釋放額外的預分配記憶體。

Qt--數據容器--總綱

Qt Container

介紹

具體容器類

順序容器：QList，QLinkedList，QVector，QStack和QQueue

關聯容器：QMap，QMultiMap，QHash，QMultiHash和QSet。

快取儲存：QCache和QContiguousCache

​​​​​​​迭代器類

Java樣式迭代器

​​​​​​​STL 樣式迭代器

隱式共用迭代器的問題

foreach關鍵字

​​​​​​​其他類似容器的類

​​​​​​​演算法的複雜性

成長策略

迭代器類

STL 樣式迭代器

其他類似容器的類

演算法的複雜性