（38）存儲容器 · Qt 學習之路 2

#（38）：存儲容器存儲容器（containers）有時候也被稱為集合（collections），是能夠在內存中存儲其它特定類型的對象，通常是一些常用的數據結構，一般是通用模板類的形式。C++ 提供了一套完整的解決方案，作為標準模板庫（Standard Template Library）的組成部分，也就是常說的 STL。 Qt 提供了另外一套基于模板的容器類。相比 STL，這些容器類通常更輕量、更安全、更容易使用。如果你對 STL 不大熟悉，或者更喜歡 Qt 風格的 API，那么你就應該選擇使用這些類。當然，你也可以在 Qt 中使用 STL 容器，沒有任何問題。本章的目的，是讓你能夠選擇使用哪個容器，而不是告訴你這個類都哪些函數。這個問題可以在文檔中找到更清晰的回答。 Qt 的容器類都不繼承`QObject`，都提供了隱式數據共享、不可變的特性，并且為速度做了優化，具有較低的內存占用量等。另外一點比較重要的，它們是線程安全的。這些容器類是平臺無關的，即不因編譯器的不同而具有不同的實現；隱式數據共享，有時也被稱作“寫時復制（copy on write）”，這種技術允許在容器類中使用傳值參數，但卻不會出現額外的性能損失。遍歷是容器類的重要操作。Qt 容器類提供了類似 Java 的遍歷器語法，同樣也提供了類似 STL 的遍歷器語法，以方便用戶選擇自己習慣的編碼方式。相比而言，Java 風格的遍歷器更易用，是一種高層次的函數；而 STL 風格的遍歷器更高效，同時能夠支持 Qt 和 STL 的通用算法。最后一點，在一些嵌入式平臺，STL 往往是不可用的，這時你就只能使用 Qt 提供的容器類，除非你想自己創建。順便提一句，除了遍歷器，Qt 還提供了自己的 foreach 語法（C++ 11 也提供了類似的語法，但有所區別，詳見[這里](http://www.devbean.net/2012/06/cpp11-in-qt4/)的 foreach 循環一節）。 Qt 提供了順序存儲容器：`QList`，`QLinkedList`，`QVector`，`QStack`和`QQueue`。對于絕大多數應用程序，`QList`是最好的選擇。雖然它是基于數組實現的列表，但它提供了快速的向前添加和向后追加的操作。如果你需要鏈表，可以使用`QLinkedList`。如果你希望所有元素占用連續地址空間，可以選擇`QVector`。`QStack`和`QQueue`則是 LIFO 和 FIFO 的。 Qt 還提供了關聯容器：`QMap`，`QMultiMap`，`QHash`，`QMultiHash`和`QSet`。帶有“Multi”字樣的容器支持在一個鍵上面關聯多個值。“Hash”容器提供了基于散列函數的更快的查找，而非 Hash 容器則是基于二分搜索的有序集合。另外兩個特例：`QCache`和`QContiguousCache`提供了在有限緩存空間中的高效 hash 查找。我們將 Qt 提供的各個容器類總結如下： * `QList<T>`：這是至今為止提供的最通用的容器類。它將給定的類型 T 的對象以列表的形式進行存儲，與一個整型的索引關聯。`QList`在內部使用數組實現，同時提供基于索引的快速訪問。我們可以使用?`QList::append()`和`QList::prepend()`在列表尾部或頭部添加元素，也可以使用`QList::insert()`在中間插入。相比其它容器類，`QList`專門為這種修改操作作了優化。`QStringList`繼承自`QList<QString>`。 * `QLinkedList<T>`：類似于?`QList`，除了它是使用遍歷器進行遍歷，而不是基于整數索引的隨機訪問。對于在中部插入大量數據，它的性能要優于`QList`。同時具有更好的遍歷器語義（只要數據元素存在，`QLinkedList`的遍歷器就會指向一個合法元素，相比而言，當插入或刪除數據時，`QList`的遍歷器就會指向一個非法值）。 * `QVector<T>`：用于在內存的連續區存儲一系列給定類型的值。在頭部或中間插入數據可能會非常慢，因為這會引起大量數據在內存中的移動。 * `QStack<T>`：這是`QVector`的子類，提供了后進先出（LIFO）語義。相比`QVector`，它提供了額外的函數：`push()`，`pop()`和`top()`。 * `QQueue<T>`：這是`QList`的子類，提供了先進先出（FIFO）語義。相比`QList`，它提供了額外的函數：`enqueue()`，`dequeue()`和`head()`。 * `QSet<T>`：提供單值的數學上面的集合，具有快速的查找性能。 * `QMap<Key, T>`：提供了字典數據結構（關聯數組），將類型 T 的值同類型 Key 的鍵關聯起來。通常，每個鍵與一個值關聯。`QMap`以鍵的順序存儲數據；如果順序無關，`QHash`提供了更好的性能。 * `QMultiMap<Key, T>`：這是`QMap`的子類，提供了多值映射：一個鍵可以與多個值關聯。 * `QHash<Key, T>`：該類同`QMap`的接口幾乎相同，但是提供了更快的查找。`QHash`以字母順序存儲數據。 * `QMultiHash<Key, T>`：這是`QHash`的子類，提供了多值散列。所有的容器都可以嵌套。例如，`QMap<QString, QList<int> >`是一個映射，其鍵是`QString`類型，值是`QList<int>`類型，也就是說，每個值都可以存儲多個 int。這里需要注意的是，C++ 編譯器會將連續的兩個 > 當做輸入重定向運算符，因此，這里的兩個 > 中間必須有一個空格。能夠存儲在容器中的數據必須是**可賦值數據類型**。所謂可賦值數據類型，是指具有默認構造函數、拷貝構造函數和賦值運算符的類型。絕大多數數據類型，包括基本類型，比如 int 和 double，指針，Qt 數據類型，例如`QString`、`QDate`和`QTime`，都是可賦值數據類型。但是，`QObject`及其子類（`QWidget`、`QTimer`等）都不是。也就是說，你不能使用`QList<QWidget>`這種容器，因為`QWidget`的拷貝構造函數和賦值運算符不可用。如果你需要這種類型的容器，只能存儲其指針，也就是`QList<QWidget *>`。如果要使用`QMap`或者`QHash`，作為鍵的類型必須提供額外的輔助函數。`QMap`的鍵必須提供`operator<()`重載，`QHash`的鍵必須提供`operator==()`重載和一個名字是`qHash()`的全局函數。作為例子，我們考慮如下的代碼： ~~~ struct Movie { int id; QString title; QDate releaseDate; }; ~~~ 作為 struct，我們當做純數據類使用。這個類沒有額外的構造函數，因此編譯器會為我們生成一個默認構造函數。同時，編譯器還會生成默認的拷貝構造函數和賦值運算符。這就滿足了將其放入容器類存儲的條件： ~~~ QList<Movie> movs; ~~~ Qt 容器類可以直接使用`QDataStream`進行存取。此時，容器中所存儲的類型必須也能夠使用`QDataStream`進行存儲。這意味著，我們需要重載`operator<<()`和`operator>>()`運算符： ~~~ 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; } ~~~ 根據數據結構的相關內容，我們有必要對這些容器類的算法復雜性進行定量分析。算法復雜度關心的是在數據量增長時，容器的每一個函數究竟有多快（或者多慢）。例如，向`QLinkedList`中部插入數據是一個相當快的操作，并且與`QLinkedList`中已經存儲的數據量無關。另一方面，如果`QVector`中已經保存了大量數據，向`QVector`中部插入數據會非常慢，因為在內存中，有一半的數據必須移動位置。為了描述算法復雜度，我們引入 O 記號（大寫字母 O，讀作“大 O”）： * 常量時間：O(1)。如果一個函數的運行時間與容器中數據量無關，我們說這個函數是常量時間的。`QLinkedList::insert()`就是常量時間的。 * 對數時間：O(log n)。如果一個函數的運行時間是容器數據量的對數關系，我們說這個函數是對數時間的。`qBinaryFind()`就是對數時間的。 * 線性時間：O(n)。如果一個函數的運行時間是容器數據量的線性關系，也就是說直接與數量相關，我們說這個函數是限行時間的。`QVector::insert()`就是線性時間的。 * 線性對數時間：O(n log n)。線性對數時間要比線性時間慢，但是要比平方時間快。 * 平方時間：O(n2)。平方時間與容器數據量的平方關系。基于上面的表示，我們來看看 Qt 順序容器的算法復雜度： | 查找 | 插入 | 前方添加 | 后方追加 || -- | | -- | -- | --| -- | | `QLinkedList<T>` | O(n) | O(1) | O(1) | O(1) | | `QList<T>` | O(1) | O(n) | 統計 O(1) | 統計 O(1) | | `QVector<T>` | O(1) | O(n) | O(n) | 統計 O(1) | 上表中，所謂“統計”，意思是統計意義上的數據。例如“統計 O(1)”是說，如果只調用一次，其運行時間是 O(n)，但是如果調用多次（例如 n 次），則平均時間是 O(1)。下表則是關聯容器的算法復雜度： | 查找鍵 | 插入 || -- | -- || -- | | -- | -- || -- | -- || -- | | 平均 | 最壞 | 平均 | 最壞 |--| | `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>` | 統計 O(1) | O(n) | O(1) | 統計 O(n) | | `QSet<Key, T>` | 統計 O(1) | O(n) | O(1) | 統計 O(n) | `QVector`、`QHash`和`QSet`的頭部添加是統計意義上的 O(log n)。然而，通過給定插入之前的元素個數來調用`QVector::reserve()`、`QHash::reserve()`和`QSet::reserve()`，我們可以把復雜度降到 O(1)。我們會在下面詳細討論這個問題。 `QVector<T>`、`QString`和`QByteArray`在連續內存空間中存儲數據。`QList<T>`維護指向其數據的指針數組，提供基于索引的快速訪問（如果 T 就是指針類型，或者是與指針大小相同的其它類型，那么 QList 的內部數組中存的就是其實際值，而不是其指針）。`QHash<Key, T>`維護一張散列表，其大小與散列中數據量相同。為避免每次插入數據都要重新分配數據空間，這些類都提供了多余實際值的數據位。我們通過下面的代碼來了解這一算法： ~~~ QString onlyLetters(const QString &in) { QString out; for (int j = 0; j < in.size(); ++j) { if (in[j].isLetter()) out += in[j]; } return out; } ~~~ 我們創建了一個字符串，每次動態追加一個字符。假設我們需要追加 15000 個字符。在算法運行過程中，當達到以下空間時，會進行重新分配內存空間，一共會有 18 次：4，8，12，16，20，52，116，244，500，1012，2036，4084，6132，8180，10228，12276，14324，16372。最后，這個 out 對象一共有 16372 個 Unicode 字符，其中 15000 個是有實際數據的。上面的分配數據有些奇怪，其實是有章可循的： * `QString`每次分配 4 個字符，直到達到 20。 * 在 20 到 4084 期間，每次分配大約一倍。準確地說，每次會分配下一個 2 的冪減 12。（某些內存分配器在分配 2 的冪數時會有非常差的性能，因為他們會占用某些字節做預訂） * 自 4084 起，每次多分配 2048 個字符（4096 字節）。這是有特定意義的，因為現代操作系統在重新分配一個緩存時，不會復制整個數據；物理內存頁只是簡單地被重新排序，只有第一頁和最后一頁的數據會被復制。 `QByteArray`和`QList<T>`實際算法與`QString`非常類似。對于那些能夠使用`memcry()`（包括基本的 C++ 類型，指針類型和 Qt 的共享類）函數在內存中移動的數據類型，`QVector<T>`也使用了類似的算法；對于那些只能使用拷貝構造函數和析構函數才能移動的數據類型，使用的是另外一套算法。由于后者的消耗更高，所以`QVector<T>`減少了超出空間時每次所要分配的額外內存數。 `QHash<Key, T>`則是完全不同的形式。`QHash`的內部散列表每次會增加 2 的冪數；每次增加時，所有數據都要重新分配到新的桶中，其計算公式是`qHash(key) % QHash::capacity()`（`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()`函數，釋放所有未使用的預分配空間。