#（39）：遍歷容器 上一節我們大致了解了有關存儲容器的相關內容。對于所有的容器，最常用的操作就是遍歷。本章我們將詳細了解有關遍歷器的內容。 盡管這個問題不是本章需要考慮的，但是我們還是需要來解釋下，為什么要有遍歷器。沒有遍歷器時，如果我們需要向外界提供一個列表，我們通常會將其返回： ~~~ QList<int> intlist() const { return list; } ~~~ 這么做的問題是：向用戶暴露了集合的內部實現。用戶知道，原來你用的就是一個`QList`啊~那我就可以向里面增加東西了，或者修改其中的內容。有時這不是我們所期望的。很多時候，我們只是想提供用戶一個集合，只允許用戶知道這個集合中有什么，而不是對它進行修改。為此，我們希望有這么一種對象：通過它就能夠提供一種通用的訪問集合元素的方法，不管底層的集合是鏈表還是散列，都可以通過這種對象實現。這就是遍歷器。 Qt 的容器類提供了兩種風格的遍歷器：Java 風格和 STL 風格。這兩種風格的遍歷器在通過非 const 函數對集合進行修改時都是不可用的。 ## 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<T>` | `QMutableMapIterator<T>` | | `QHash<Key, T>`,`QMultiHash<Key, T>` | `QHashIterator<T>` | `QMutableHashIterator<T>` | 這里我們只討論`QList`和`QMap`的遍歷器。`QLinkedList`、`QVector`和`QSet`的遍歷器接口與`QList`的是一樣的；`QHash`遍歷器的接口則同`QMap`是一樣的。 不同于下面我們將要介紹的 STL 風格的遍歷器，Java 風格的遍歷器指向的是兩個元素之間的位置，而不是指向元素本身。因此，它們可能會指向集合第一個元素之前的位置，也可能指向集合的最后一個元素之后的位置，如下圖所示： [](http://files.devbean.net/images/2013/01/java-style-iterator.png) 我們通過下面的代碼看看如何使用這種遍歷器： ~~~ QList<QString> list; list << "A" << "B" << "C" << "D"; QListIterator<QString> i(list); while (i.hasNext()) { qDebug() << i.next(); } ~~~ 首先，我們使用 list 對象創建一個遍歷器。剛剛創建完成時，該遍歷器位于第一個元素之前（也就是 A 之前）。我們通過調用`hasNext()`函數判斷遍歷器之后的位置上有無元素。如果有，調用`next()`函數將遍歷器跳過其后的元素。`next()`函數返回剛剛跳過的元素。當然，我們也可以使用`hasPrevious()`和`previous()`函數來從尾部開始遍歷，詳細內容可以參考 API 文檔。 `QListIterator`是只讀遍歷器，不能插入或者刪除數據。如果需要這些操作，我們可以使用`QMutableListIterator`。來看下面的代碼： ~~~ QMutableListIterator<int> i(list); while (i.hasNext()) { if (i.next() % 2 != 0) { i.remove(); } } ~~~ 這段代碼使用`QMutableListIterator`遍歷集合，如果其值是奇數則將其刪除。在每次循環中都要調用`next()`函數。正如前面所說，它會跳過其后的一個元素。`remove()`函數會刪除我們剛剛跳過的元素。調用`remove()`函數并不會將遍歷器置位不可用，因此我們可以連續調用這個函數。向前遍歷也是類似的，這里不再贅述。 如果我們需要修改已經存在的元素，使用`setValue()`函數。例如： ~~~ QMutableListIterator<int> i(list); while (i.hasNext()) { if (i.next() > 128) { i.setValue(128); } } ~~~ 如同`remove()`函數，`setValue()`也是對剛剛跳過的元素進行操作。實際上，`next()`函數返回的是集合元素的非 const 引用，因此我們根本不需要調用`setValue()`函數： ~~~ QMutableListIterator<int> i(list); while (i.hasNext()) { i.next() *= 2; } ~~~ `QMapItrator`也是類似的。例如，使用`QMapItrator`我們可以將數據從`QMap`復制到`QHash`： ~~~ QMap<int, QWidget *> map; QHash<int, QWidget *> hash; QMapIterator<int, QWidget *> i(map); while (i.hasNext()) { i.next(); hash.insert(i.key(), i.value()); } ~~~ ## STL 風格的遍歷器 STL 風格的遍歷器從 Qt 2.0 就開始提供。這種遍歷器能夠兼容 Qt 和 STL 的通用算法，并且為速度進行了優化。同 Java 風格遍歷器類似，Qt 也提供了兩種 STL 風格的遍歷器：一種是只讀訪問，一種是讀寫訪問。我們推薦盡可能使用只讀訪問，因為它們要比讀寫訪問的遍歷器快一些。 | 容器 | 只讀遍歷器 | 讀寫遍歷器 | | -- | -- | -- | | `QList<T>`,`QQueue<T>` | `QList<T>::const_iterator` | `QList<T>::iterator` | | `QLinkedList<T>` | `QLinkedList<T>::const_iterator` | `QLinkedList<T>::iterator` | | `QVector<T>`,`QStack<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 風格的遍歷器具有類似數組指針的行為。例如，我們可以使用 ++ 運算符讓遍歷器移動到下一個元素，使用 * 運算符獲取遍歷器所指的元素。對于`QVector`和`QStack`，雖然它們是在連續內存區存儲元素，遍歷器類型是`typedef T *`，`const_iterator`類型則是`typedef const T *`。 我們還是以`QList`和`QMap`為例，理由如上。下面是有關`QList`的相關代碼： ~~~ QList<QString> list; list << "A" << "B" << "C" << "D"; QList<QString>::iterator i; for (i = list.begin(); i != list.end(); ++i) { *i = (*i).toLower(); } ~~~ 不同于 Java 風格遍歷器，STL 風格遍歷器直接指向元素本身。容器的`begin()`函數返回指向該容器第一個元素的遍歷器；`end()`函數返回指向該容器**最后一個元素之后的元素**的遍歷器。`end()`實際是一個非法位置，永遠不可達。這是為跳出循環做的一個虛元素。如果集合是空的，`begin()`等于`end()`，我們就不能執行循環。 下圖是 STL 風格遍歷器的示意圖： [](http://files.devbean.net/images/2013/01/stl-style-iterator.png) 我們使用`const_iterator`進行只讀訪問，例如： ~~~ QList<QString>::const_iterator i; for (i = list.constBegin(); i != list.constEnd(); ++i) { qDebug() << *i; } ~~~ `QMap`和`QHash`的遍歷器，* 運算符返回集合鍵值對。下面的代碼，我們打印出`QMap`的所有元素： ~~~ QMap<int, int> map; QMap<int, int>::const_iterator i; for (i = map.constBegin(); i != map.constEnd(); ++i) { qDebug() << i.key() << ":" << i.value(); } ~~~ 由于有隱式數據共享（我們會在后面的章節介紹該部分內容），即使一個函數返回集合中元素的值也不會有很大的代價。Qt API 包含了很多以值的形式返回`QList`或`QStringList`的函數（例如`QSplitter::sizes()`）。如果你希望使用 STL 風格的遍歷器遍歷這樣的元素，應該使用容器的拷貝，例如： ~~~ // 正確的方式 const QList<QString> sizes = splitter->sizes(); QList<QString>::const_iterator i; for (i = sizes.begin(); i != sizes.end(); ++i) ... // 錯誤的方式 QList<QString>::const_iterator i; for (i = splitter->sizes().begin(); i != splitter->sizes().end(); ++i) ... ~~~ 這個問題不存在于那些返回集合的 const 或非 const 引用的函數。隱式數據共享對 STL 風格遍歷器造成的另外影響是，在容器上運行著非 const 遍歷器的時候，不能對容器進行拷貝。Java 風格的遍歷器沒有這個問題。 ### `foreach`關鍵字 如果我們僅僅想要遍歷集合所有元素，我們可以使用 Qt 的`foreach`關鍵字。這個關鍵字是 Qt 特有的，通過預處理器進行處理。C++ 11 也提供了自己的`foreach`關鍵字，不過與此還是有[區別](http://www.devbean.net/2012/06/cpp11-in-qt4/)的。 `foreach`的語法是`foreach (variable, container)`。例如，我們使用`foreach`對`QLinkedList`進行遍歷： ~~~ QLinkedList<QString> list; ... QString str; foreach (str, list) { qDebug() << str; } ~~~ 這段代碼與下面是等價的： ~~~ QLinkedList<QString> list; ... QLinkedListIterator<QString> i(list); while (i.hasNext()) { qDebug() << i.next(); } ~~~ 如果類型名中帶有逗號，比如`QPair<int, int>`，我們只能像上面一樣，先創建一個對象，然后使用`foreach`關鍵字。如果沒有逗號，則可以直接在`foreach`關鍵字中使用新的對象，例如： ~~~ QLinkedList<QString> list; ... foreach (const QString &str, list) { qDebug() << str; } ~~~ Qt 會在`foreach`循環時自動拷貝容器。這意味著，如果在遍歷時修改集合，對于正在進行的遍歷是沒有影響的。即使不修改容器，拷貝也是會發生的。但是由于存在隱式數據共享，這種拷貝還是非常迅速的。 因為`foreach`創建了集合的拷貝，使用集合的非 const 引用也不能實際修改原始集合，所修改的只是這個拷貝。