首页 Qt 学习之路 2 Qt 学习之路 2(39):遍历容器

Qt 学习之路 2(39):遍历容器

29 6

上一节我们大致了解了有关存储容器的相关内容。对于所有的容器,最常用的操作就是遍历。本章我们将详细了解有关遍历器的内容。

尽管这个问题不是本章需要考虑的,但是我们还是需要来解释下,为什么要有遍历器。没有遍历器时,如果我们需要向外界提供一个列表,我们通常会将其返回:

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>

这里我们只讨论QListQMap的遍历器。QLinkedListQVectorQSet的遍历器接口与QList的是一样的;QHash遍历器的接口则同QMap是一样的。

不同于下面我们将要介绍的 STL 风格的遍历器,Java 风格的遍历器指向的是两个元素之间的位置,而不是指向元素本身。因此,它们可能会指向集合第一个元素之前的位置,也可能指向集合的最后一个元素之后的位置,如下图所示:

Java Style Iterator

我们通过下面的代码看看如何使用这种遍历器:

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_iteratorQList<T>::iterator
QLinkedList<T>QLinkedList<T>::const_iteratorQLinkedList<T>::iterator
QVector<T>,QStack<T>QVector<T>::const_iteratorQVector<T>::iterator
QSet<T>QSet<T>::const_iteratorQSet<T>::iterator
QMap<Key, T>,QMultiMap<Key, T>QMap<Key, T>::const_iteratorQMap<Key, T>::iterator
QHash<Key, T>,QMultiHash<Key, T>QHash<Key, T>::const_iteratorQHash<Key, T>::iterator

STL 风格的遍历器具有类似数组指针的行为。例如,我们可以使用 ++ 运算符让遍历器移动到下一个元素,使用 * 运算符获取遍历器所指的元素。对于QVectorQStack,虽然它们是在连续内存区存储元素,遍历器类型是typedef T *const_iterator类型则是typedef const T *

我们还是以QListQMap为例,理由如上。下面是有关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 风格遍历器的示意图:

STL 风格遍历器

我们使用const_iterator进行只读访问,例如:

QList<QString>::const_iterator i;
for (i = list.constBegin(); i != list.constEnd(); ++i) {
    qDebug() << *i;
}

QMapQHash的遍历器,* 运算符返回集合键值对。下面的代码,我们打印出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 包含了很多以值的形式返回QListQStringList的函数(例如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 风格遍历器造成的另一个影响是,当一个容器正在被一个遍历器遍历的时候,不能对这个容器进行拷贝。如果你必须对其进行拷贝,那么就得万分小心。例如,

QVector<int> a, b;
a.resize(100000); // 使用 0 填充一个非常大的 vector

QVector<int>::iterator i = a.begin();
// 使用遍历器 i 的错误方式(注意,此时,a 上面已经有一个正在遍历的遍历器):
b = a;
/*
    现在,我们的万分小心遍历器 i。因为它指向了共享的数据。
    如果我们执行语句 *i = 4,我们就会改变了共享的数据实例(两个 vector 都会被改变)。
    这里的行为与 STL 容器不同,因此这种问题仅出现在 Qt 中;使用 STL 标准容器不存在这个问题。
*/

a[0] = 5;
/*
    现在,容器 a 被修改了,其实际数据已经与共享数据不同,
    即使 i 就是从容器 a 创建的遍历器,但是它指向的数据与 a 并不一致,其表现就像是 b 的遍历器。
    这里的情形是:(*i) == 0.
*/

b.clear(); // 现在我们清空 b,此时,遍历器 i 已经不可用了。

int j = *i; // 无定义行为!
/*
    来自 b 的数据(也就是 i 指向的那些数据)已经被销毁了。
    这种行为在 STL 容器中是完全可行的(在 STL 容器中,(*i) == 5),
    但是使用 QVector 则很有可能出现崩溃。
*/

虽然这个例子只演示了QVector,但实际上,这个问题适用于所有隐式数据共享的容器类。

foreach关键字

如果我们仅仅想要遍历集合所有元素,我们可以使用 Qt 的foreach关键字。这个关键字是 Qt 特有的,通过预处理器进行处理。C++ 11 也提供了自己的foreach关键字,不过与此还是有区别的。

foreach的语法是foreach (variable, container)。例如,我们使用foreachQLinkedList进行遍历:

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 引用也不能实际修改原始集合,所修改的只是这个拷贝。

29 评论

FEI17 2013年1月16日 - 15:53

博主大神 您好
我想写一个在线电视台给我的妈妈使用(妈妈眼睛不好)

具体的办法是 按钮(很大)按下的时候 调用midori来打开别的网站的链接
现在我想把这个midori窗口嵌入到我软件的窗口上
搜索资料一直找不到办法
大神能否抽空看看?

回复
豆子 2013年1月16日 - 16:02

midori 不大熟悉,不清楚该怎么使用。如果有 C++ 接口的话,应该是可以嵌入到窗口程序中的。如果是微软的话,或者与 MFC 的集成会更方便一些

回复
FEI17 2013年1月16日 - 16:15

是一个轻量级的浏览器

midori
  
Midori是一个轻量级的跨平台网页浏览器。 Midori用C语言编写,并完全整合了GTK+ 2。Midori使用了和Safari一样的WebKit的HTML排版引擎。

也就是说
没有 不论对方是什么样的程序 都统统嵌入进去 的函数么

回复
豆子 2013年1月17日 - 11:44

如果说嵌入的话,应该是没有的。不同界面系统的实现都不一样,比如 MFC 使用消息循环,Qt 使用信号槽,这些都是不能兼容的,也就不大可能嵌入。既然是 GTK+,应该提供了 API,使用 C++ 调用 GTK+ 的 API 应该是可行的

回复
FEI17 2013年1月17日 - 12:07

谢谢
我去查询一下资料 看看能否实现

FEI17 2013年1月16日 - 16:58

一样谢谢啊

回复
panda 2013年1月19日 - 22:30

STL 风格的遍历器其实是一种指针数组?楼主此话怎讲?
STL 风格的遍历器只是拥有类似指针行为的能力吧。

回复
豆子 2013年1月21日 - 10:18

是的,这样的说法更清晰些。已经修改过了,感谢指出!

回复
panda 2013年1月19日 - 22:33

Qt 会在 foreach 循环时自动拷贝容器是不是意为着Qt的foreach是线程安全的?

回复
豆子 2013年1月21日 - 10:30

没有找到权威信息,但是这种行为应该是线程安全的。

回复
panda 2013年1月19日 - 22:41

隐式数据共享对 STL 风格遍历器造成的另外影响是,在容器上运行着非 const 遍历器的时候,不能对容器进行拷贝。
不能对容器进行拷贝是指拷贝出错,还是发生未定义的行为呢?

回复
豆子 2013年1月21日 - 10:34

这种行为的后果文档中并没有指出,只是说不允许这么做

回复
jelly 2013年1月20日 - 01:03

不知博主有没有开源的质量比较高的项目推荐~

回复
豆子 2013年1月21日 - 10:32

可以考虑 Qt Creator 的源代码,大小适中

回复
ediblethecadelle 2013年1月21日 - 18:28

豆子,你好,我最近在看GUI QT4这本书第4章的时候遇到些问题不知道豆子能不能帮我解答一下呢,代码主要是这样的:
//sheet.cpp
sheet::sheet(QWidget *parent) :
QTableWidget(parent){
setRowCount(rowCount);
setColumnCount(columnCount);
this->setSelectionMode(QAbstractItemView::ContiguousSelection);
}

我模仿书里面的那个仿excel实例,敲了一个类似的代码,跟书里一样,
这个子类化QTableWidget的类主要用来处理表格的读写。
//MainWindow.cpp

MainWindow::MainWindow(QWidget *parent)
: QMainWindow(parent){
createTotalAction();
createMenu();
createToolBar();
createStatusBar();
this->setWindowIcon(QIcon(":/icon.png"));
setCentralWidget((oper=new sheet(this)));
oper->item(2,2)->setText("demo");
}
加了oper->item(2,2)->setText("demo");以后,一调适就出现内存错误。
请问豆子哥,该怎么处理?

回复
豆子 2013年1月22日 - 09:39

oper 有没有初始化呢?如果没有的话就是内存错误了

回复
Jack 2013年6月24日 - 16:22


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

QList::iterator i; ❓
for (i = list.begin(); i != list.end(); ++i) {
*i = (*i).toLower();
}

你好,这些测试程序是你经过测试的吗?
QList list,模板类不是这样用吗?

回复
豆子 2013年6月25日 - 09:05

怎么使用的?没有看到你的代码啊。PS: 使用 &lt; 和 &gt; 进行转义

回复
j 2013年7月26日 - 13:35

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

不需要指定QList的类型吗?

回复
豆子 2013年7月27日 - 10:43

需要模板,只是因为 wordpress 屏蔽了,现在改过来了

回复
rrrdr 2014年6月22日 - 05:27

我发现QLinkedList:也可以利用整数索引来进行随机访问。
QLinkedList sizes;
//..................
QLinkedList ::iterator i ;
当需要访问sizes的第五个元素时,
for (int u=1,i = sizes.begin(); i != sizes.end(); ++i,++u)
if(u==5) qDebug() <<"sizes[5]=="<<*i;
后来我发现QLinkedList也可以像索引一样进行随机访问。
i=sizes.begin()+5;
qDebug() <<"sizes[5]=="<<*i;
LZ 你看这样用法正确吗?

回复
豆子 2014年6月24日 - 21:51

个人并不认为这种写法有错误,但毫无疑问应该避免,因为这样的操作很慢。毕竟作为一种数据结构,链表是通过遍历来模拟一种随机访问的操作,性能上不会像 vector 那么高。

回复
rrrdr 2014年6月25日 - 14:29

哦,有道理.
对了,最近很少见你出文章了啊!

回复
豆子 2014年6月26日 - 13:20

最近一直在弄书稿,写的比较慢了 ;-P

回复
阿诺 2015年7月3日 - 13:11

楼主我勇QVector定义了一个对象,但是当我在QTextBrowser中显示时老出现内存问题,强制退出,怎么破

回复
豆子 2015年7月13日 - 11:03

内存问题需要仔细查看代码,这里说不清楚到底怎么回事

回复
stlcours 2015年8月6日 - 01:04

豆子你好,仔细研读了你的文章,感觉你的这段:
// 正确的方式
const QList sizes = splitter->sizes();
QList::const_iterator i;
for (i = sizes.begin(); i != sizes.end(); ++i)
...

// 错误的方式
QList::const_iterator i;
for (i = splitter->sizes().begin();
i != splitter->sizes().end(); ++i)
...
两种方式谈不上正确和错误,只是说因为隐式共享的存在,const QList sizes = splitter->sizes();不付出什么代价而已。两种都是可用的方式,取值的速度和效率应该没有任何区别,只是你推荐的方式代码更整齐一些。请问我这样理解对吗?盼回复!

另外还有不明白的是,QList::const_iterator QList::iterator,为什么只读遍历器更快呢?如果我用读写遍历器,但是不修改其内容,又有什么区别呢?莫非使用只读遍历器可以少拷贝一些东西?但是我觉得iterator本质上是一个指针,不是吗?这样一来,又有什么快和慢的区别呢?

回复
豆子 2015年8月16日 - 18:27

第一个问题,const QList sizes = splitter->sizes(); 语句在一定程度是必要的。查看 QSplitter::sizes() 函数的实现可以看到,这个函数每次返回一个新的 QList 对象,而不是直接返回 QSplitter 实际持有的 QList。因此,如果使用第二种写法,两次 sizes() 函数调用之间,其底层的 list 可能已经发生改变(例如,被另外的线程修改等)。因此,第一种写法更推荐。

第二个问题,从软件工程的角度来说,const_iterator 暗示了你不会对容器数据进行修改,而单纯的 iterator 则没有这一个语义。明确使用 const_iterator 会使代码更具可维护性。从技术的角度而言,const_iterator 的确比 iterator 更快。可参考 QMap::begin() 与 QMap::constBegin() 函数的代码,前者比后者多出一个 detach() 函数的调用。由于隐式数据共享,如果有多个对象使用同一数据,detach() 函数会进行一次实际的数据复制。因此,根据代码的实现,const_iterator 也具有更好的性能。

源码之前,了无秘密 ;-P

回复
smilewind 2015年12月22日 - 17:47

// 正确的方式
const QList sizes = splitter->sizes();
QList::const_iterator i;
for (i = sizes.begin(); i != sizes.end(); ++i)
...

// 错误的方式
QList::const_iterator i;
for (i = splitter->sizes().begin();
i != splitter->sizes().end(); ++i)
...
豆子大神,这个正确的方式,是不是应该去掉第一行的const 呢?
然后使用只读迭代器遍历,是不是应该用 constBegin(),constEnd() ??

回复

发表评论

关于我

devbean

devbean

豆子,生于山东,定居南京。毕业于山东大学软件工程专业。软件工程师,主要关注于 Qt、Angular 等界面技术。

主题 Salodad 由 PenciDesign 提供 | 静态文件存储由又拍云存储提供 | 苏ICP备13027999号-2