firemail

标题: QT容器学习 [打印本页]
作者: Qter    时间: 2017-1-22 14:54
标题: QT容器学习
存储容器（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 也提供了类似的语法，但有所区别，详见这里的 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 的对象以列表的形式进行存储，与一个整型的索引关联。QList在内部使用数组实现，同时提供基于索引的快速访问。我们可以使用 QList::append()和QList::prepend()在列表尾部或头部添加元素，也可以使用QList::insert()在中间插入。相比其它容器类，QList专门为这种修改操作作了优化。QStringList继承自QList。
　　QLinkedList：类似于 QList，除了它是使用遍历器进行遍历，而不是基于整数索引的随机访问。对于在中部插入大量数据，它的性能要优于QList。同时具有更好的遍历器语义（只要数据元素存在，QLinkedList的遍历器就会指向一个合法元素，相比而言，当插入或删除数据时，QList的遍历器就会指向一个非法值）。
　　QVector：用于在内存的连续区存储一系列给定类型的值。在头部或中间插入数据可能会非常慢，因为这会引起大量数据在内存中的移动。
　　QStack：这是QVector的子类，提供了后进先出（LIFO）语义。相比QVector，它提供了额外的函数：push()，pop()和top()。
　　QQueue：这是QList的子类，提供了先进先出（FIFO）语义。相比QList，它提供了额外的函数：enqueue()，dequeue()和head()。
　　QSet：提供单值的数学上面的集合，具有快速的查找性能。
　　QMap：提供了字典数据结构（关联数组），将类型 T 的值同类型 Key 的键关联起来。通常，每个键与一个值关联。QMap以键的顺序存储数据；如果顺序无关，QHash提供了更好的性能。
　　QMultiMap：这是QMap的子类，提供了多值映射：一个键可以与多个值关联。
　　QHash：该类同QMap的接口几乎相同，但是提供了更快的查找。QHash以字母顺序存储数据。
　　QMultiHash：这是QHash的子类，提供了多值散列。
　　所有的容器都可以嵌套。例如，QMap<qstring, qlist >是一个映射，其键是QString类型，值是QList类型，也就是说，每个值都可以存储多个 int。这里需要注意的是，C++ 编译器会将连续的两个 > 当做输入重定向运算符，因此，这里的两个 > 中间必须有一个空格。
　　能够存储在容器中的数据必须是可赋值数据类型。所谓可赋值数据类型，是指具有默认构造函数、拷贝构造函数和赋值运算符的类型。绝大多数数据类型，包括基本类型，比如 int 和 double，指针，Qt 数据类型，例如QString、QDate和QTime，都是可赋值数据类型。但是，QObject及其子类（QWidget、QTimer等）都不是。也就是说，你不能使用QList这种容器，因为QWidget的拷贝构造函数和赋值运算符不可用。如果你需要这种类型的容器，只能存储其指针，也就是QList。
　　如果要使用QMap或者QHash，作为键的类型必须提供额外的辅助函数。QMap的键必须提供operator<()重载，QHash的键必须提供operator==()重载和一个名字是qHash()的全局函数。
作者: Qter    时间: 2017-1-22 14:56
本帖最后由 Qter 于 2017-1-22 15:03 编辑

遍历容器
Qt 的容器类提供了两种风格的遍历器：Java 风格和 STL 风格。这两种风格的遍历器在通过非 const 函数对集合进行修改时都是不可用的。
　　Java 风格的遍历器
　　Java 风格的遍历器是在 Qt4 首先引入的，是 Qt 应用程序首先推荐使用的形式。这种风格比起 STL 风格的遍历器更方便。方便的代价就是不如后者高效。它们的 API 非常类似于 Java 的遍历器类，故名。
　　每一种容器都有两种 Java 风格的遍历器：一种提供只读访问，一种提供读写访问：



容器只读遍历器读写遍历器
QList,QQueueQListIteratorQMutableListIterator
QLinkedListQLinkedListIteratorQMutableLinkedListIterator
QVector,QStackQVectorIteratorQMutableVectorIterator
QSetQSetIteratorQMutableSetIterator
QMap,QMultiMapQMapIteratorQMutableMapIterator
QHash,QMultiHashQHashIteratorQMutableHashIterator



不同于下面我们将要介绍的 STL 风格的遍历器，Java 风格的遍历器指向的是两个元素之间的位置，而不是指向元素本身。因此，它们可能会指向集合第一个元素之前的位置，也可能指向集合的最后一个元素之后的位置。
　　我们通过调用hasNext()函数判断遍历器之后的位置上有无元素。如果有，调用next()函数将遍历器跳过其后的元素。next()函数返回刚刚跳过的元素。当然，我们也可以使用hasPrevious()和previous()函数来从尾部开始遍历，详细内容可以参考 API 文档。
　　QListIterator是只读遍历器，不能插入或者删除数据。如果需要这些操作，我们可以使用QMutableListIterator。
　　STL 风格的遍历器
　　STL 风格的遍历器从 Qt 2.0 就开始提供。这种遍历器能够兼容 Qt 和 STL 的通用算法，并且为速度进行了优化。同 Java 风格遍历器类似，Qt 也提供了两种 STL 风格的遍历器：一种是只读访问，一种是读写访问。我们推荐尽可能使用只读访问，因为它们要比读写访问的遍历器快一些。


容器只读遍历器读写遍历器
QList,QQueueQList::const_iteratorQList::iterator
QLinkedListQLinkedList::const_iteratorQLinkedList::iterator
QVector,QStackQVector::const_iteratorQVector::iterator
QSetQSet::const_iteratorQSet::iterator
QMap,QMultiMapQMap::const_iteratorQMap::iterator
QHash,QMultiHashQHash::const_iteratorQHash::iterator


STL 风格的遍历器具有类似数组指针的行为。例如，我们可以使用 ++ 运算符让遍历器移动到下一个元素，使用 运算符获取遍历器所指的元素。对于QVector和QStack，虽然它们是在连续内存区存储元素，遍历器类型是`typedef T ，const_iterator类型则是typedef const T *`。
　　不同于 Java 风格遍历器，STL 风格遍历器直接指向元素本身。容器的begin()函数返回指向该容器第一个元素的遍历器；end()函数返回指向该容器最后一个元素之后的元素的遍历器。end()实际是一个非法位置，永远不可达。这是为跳出循环做的一个虚元素。如果集合是空的，begin()等于end()，我们就不能执行循环。
　　由于有隐式数据共享（我们会在后面的章节介绍该部分内容），即使一个函数返回集合中元素的值也不会有很大的代价。Qt API 包含了很多以值的形式返回QList或QStringList的函数（例如QSplitter::sizes()）。如果你希望使用 STL 风格的遍历器遍历这样的元素，应该使用容器的拷贝，例如：



  2. // 正确的方式
  3. const QList<QString> sizes = splitter->sizes();
  4. QList<QString>::const_iterator i;
  5. for (i = sizes.begin(); i != sizes.end(); ++i)
  6.     ...
  7. // 错误的方式
  8. QList<QString>::const_iterator i;
  9. for (i = splitter->sizes().begin();
  10.      i != splitter->sizes().end(); ++i)
  11.     ...
复制代码
这个问题不存在于那些返回集合的 const 或非 const 引用的函数。隐式数据共享对 STL 风格遍历器造成的另外影响是，在容器上运行着非 const 遍历器的时候，不能对容器进行拷贝。Java 风格的遍历器没有这个问题。
　　foreach关键字
　　如果类型名中带有逗号，比如QPair，我们只能像上面一样，先创建一个对象，然后使用foreach关键字。如果没有逗号，则可以直接在foreach关键字中使用新的对象。
　　Qt 会在foreach循环时自动拷贝容器。这意味着，如果在遍历时修改集合，对于正在进行的遍历是没有影响的。即使不修改容器，拷贝也是会发生的。但是由于存在隐式数据共享，这种拷贝还是非常迅速的。
　　因为foreach创建了集合的拷贝，使用集合的非 const 引用也不能实际修改原始集合，所修改的只是这个拷贝。


作者: Qter    时间: 2017-1-22 15:03
隐式数据共享

Qt 中许多 C++ 类使用了隐式数据共享技术，来最大化资源利用率和最小化拷贝时的资源消耗。当作为参数传递时，具有隐式数据共享的类即安全又高效。在数据传递时，实际上只是传递了数据的指针（这一切都是隐含帮你完成的），而只有在函数发生需要写入的情况时，数据才会被拷贝（也就是通常所说的写时复制）。本章我们将介绍有关隐式数据共享的相关内容，以便为恰当地使用前面所介绍的容器夯实基础。
　　具有数据共享能力的类包含了一个指向共享数据块的指针。这个数据块包含了数据本身以及数据的引用计数。当共享对象创建出来时，引用计数被设置为 1。当新的对象引用到共享数据时，引用计数增加；当对象引用不再引用数据时，引用计数减少。当引用计数变为 0 时，共享数据被删除。
　　在我们操作共享数据时，实际有两种拷贝对象的方法：我们通常称其为深拷贝和浅拷贝。深拷贝意味着要重新构造一个全新的对象；浅拷贝则仅仅复制引用，也就是上面所说的那个指向共享数据块的指针。深拷贝对内存和 CPU 资源都是很昂贵的；浅拷贝则非常快速，因为它仅仅是设置一个新的指针，然后将引用计数加 1。具有隐式数据共享的对象，其赋值运算符使用的是浅拷贝来实现的。
　　这种隐式数据共享的好处是，程序不需要拥有不必要的重复数据，减少数据拷贝的需求。重复数据的代价是降低内存使用率（因为内存存储了更多重复的数据）。通过数据共享，对象可以更简单地作为值来传递以及从函数中返回。
　　隐式数据共享是在底层自动完成的，程序人员无需关心。这也是“隐式”一词的含义。从 Qt4 开始，即使在多线程程序中，隐式数据共享也是起作用的。在很多人看来，隐式数据共享和多线程是不兼容的，这是由引用计数的实现方式决定的。但是，Qt 使用了原子性的引用计数来避免多线程环境下可能出现的执行顺序打断的行为。需要注意的是，原子引用计数并不能保证线程安全，还是需要恰当的锁机制。这种观点对所有类似的场合都是适用的。原子引用计数能够保证的是，线程肯定操作自己的数据，线程自己的数据是安全的。总的来说，从 Qt4 开始，你可以放心使用隐式数据共享的类，即使在多线程环境下。
　　我们可以使用QSharedData和QSharedDataPointer类实现自己的隐式数据共享类。
　　当对象即将被修改，并且其引用计数大于 1 时，隐式数据共享自动将数据从共享块中拿出。隐式共享类必须控制其内部数据，在任何修改其数据的函数中，将数据自动取出。
　　————————————————————————————————————-
　　凡是支持隐式数据共享的 Qt 类都支持类似的操作。用户甚至不需要知道对象其实已经共享。因此，你应该把这样的类当作普通类一样，而不应该依赖于其共享的特色作一些“小动作”。事实上，这些类的行为同普通类一样，只不过添加了可能的共享数据的优点。因此，你大可以使用按值传参，而无须担心数据拷贝带来的性能问题。
　　————————————————————————————————————-
　　注意，前面已经提到过，不要在使用了隐式数据共享的容器上，在有非 const STL 风格的遍历器正在遍历时复制容器。另外还有一点，对于QList或者QVector，我们应该使用at()函数而不是 [] 操作符进行只读访问。原因是 [] 操作符既可以是左值又可以是右值，这让 Qt 容器很难判断到底是左值还是右值，这意味着无法进行隐式数据共享；而at()函数不能作左值，因此可以进行隐式数据共享。另外一点是，对于begin()，end()以及其他一些非 const 遍历器，由于数据可能改变，因此 Qt 会进行深复制。为了避免这一点，要尽可能使用const_iterator、constBegin()和constEnd()。




欢迎光临 firemail (http://firemail.wang:8088/) Powered by Discuz! X3