Container Classes

Introduction

Qt提供一组通用的, 基于模板的容器类. 这些类可用于存储指定类型的数据. 例如, 你可以使用 QVector<QString> 存储可变数量的 QString数组.

这些容器类的设计比STL容器更轻量, 安全, 易用. 如果你不熟悉STL或更喜欢 "Qt 风格", 你可以使用这些类替代STL类.

这些容器类是 隐式共享的, 可重入的, 它们还在其他方面进行优化, 如提供运行速度, 降低内存, 使用最小的内联代码, 生成更小的执行文件. 此外, 它们是 线程安全的, 作为只读容器时, 所有的线程都能安全访问它.

若你需要遍历容器中的元素, 你可以使用不同的风格: Java风格的迭代器 和 STL风格的迭代器. Java风格的迭代器更容易使用, 并提供高级功能. STL风格的迭代器效率更改, 且可以使用Qt和STL的 通用算法.

Qt 提供一个关键字 foreach , 可以很容易遍历容器中的所有元素.

从Qt5.14版本开始, 多数容器提供范围构造函数. QMultiMap例外. Qt鼓励使用它们替代from/to方法. 例如:

容器类

Qt 提供的顺序容器: QList, QLinkedList, QVector, QStack, QQueue. 对于大多数应用程序, QList 是最好的类型. 尽管它是以数组链表的形式实现, 但是它提供最高效前置和追加方法. 如果你想需要使用一个链表, 使用 QLinkedList; 如果你希望容器元素占据连续内存, 使用 QVector. QStack 和 QQueue 提供LIFO和FIFO容器.

Qt 也提供关联容器: QMap, QMultiMap, QHash, QMultiHash, QSet. "Multi" 容器支持一对多, 一个key关联多个value. 对比有序容器的二分查找, "Hash" 容器提供更快的查找.

针对特殊情形, 在有限的缓存存储中, QCache 和 QContiguousCache 提供对对象的高效哈希查找.

容器可以嵌套. 例如, 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>>(). 下列代码展示如何为struct 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中, 如果不存在key, 则 QMap::value() 返回默认构造值. 对于多数值类型而言, 这意味使用默认构造函数创建值 (如. QString的空字符串). 但是, 对于基本类型( int, double), 指针类型, C++ 语言没有指定初始值; 在这种情况下, Qt容器会自动将值初始化为 0.

迭代器类

在容器中, 迭代器提供一种访问容器元素的统一方式. Qt的容器提供两种类型容器: Java风格迭代器和STL风格迭代器. 当容器中的数据被非const成员函数修改或从 隐式共享脱离时, 两类迭代器都会失效.

Java风格迭代器

Java风格迭代器是Qt4引入的, 是Qt应用程序使用的标准迭代器. 这种迭代器比STL风格迭代器更简便, 但效率较低. 它们的API是基于Java建模.

每个容器类提供两种类型的Java风格迭代器: 一种提供只读访问, 一种提供读写访问.

这次讨论, 我们集中讨论 QList 和 QMap. QLinkedList, QVector, 和 QSet 的迭代器类型与 QList的完全一致; 类似地, QHash 的迭代器类型与 QMap一致.

与STL风格迭代器不同, Java风格迭代器指向元素之间, 而不是直接指向元素. 它们可能指向容器开始(第一个元素之前), 容器末端(最后一个元素之后), 元素之间. 下图展示4个元素的容器, 有效迭代器位置:

下面代码遍历 QList<QString> 的所有元素, 并以存储顺序打印它们:

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

  QListIterator<QString> i(list);
  while (i.hasNext())
      qDebug() << i.next();

它的工作方式如下: QList 传递给 QListIterator 构造函数. 开始, 迭代器位于QList的第一个元素前方 ( "A" 之前). 我们调用 hasNext() 检查迭代器后面是否有元素. 如果有, 我们调用 next() 返回这个元素, 并跳过它. 对于 QList<QString>, 元素类型是 QString.

下面代码展示如何对 QList 后向遍历:

  QListIterator<QString> i(list);
  i.toBack();
  while (i.hasPrevious())
      qDebug() << i.previous();

代码与前向遍历是对称的, 首先, 我们调用 toBack() 将迭代器移到QList的最后一个元素之后.

下图说明迭代器 next() 和 previous() 的效果:

下表总结 QListIterator 的API:

QListIterator 没有提供函数插入或移除QList的元素. 为了实现这类需求, 你必须使用 QMutableListIterator. 下列代码展示如何使用QMutableListIterator从 QList<int> 中移除偶数 :

  QMutableListIterator<int> i(list);
  while (i.hasNext()) {
      if (i.next() % 2 != 0)
          i.remove();
  }

每次循环都会调用 next(). 它跳过QList中的下一个元素. remove() 函数移除跳过的最后一个元素. 调用 remove() 函数不会使迭代器无效, 因此继续使用迭代器是安全的. 对于前向遍历也同样有效:

  QMutableListIterator<int> i(list);
  i.toBack();
  while (i.hasPrevious()) {
      if (i.previous() % 2 != 0)
          i.remove();
  }

如果我们想修改已存在的值, 我们可以调用 setValue(). 下述代码, 我们将所有大于128的值替换成128:

  QMutableListIterator<int> i(list);
  while (i.hasNext()) {
      if (i.next() > 128)
          i.setValue(128);
  }

跟 remove() 一样, setValue() 操作的也是我们跳过的最后一个元素, 如果我们前向遍历, 这个元素在迭代器之前; 如果我们后向遍历, 这个元素在迭代器之后.

next() 返回QList中元素的非const引用. 对于简单的操作, 我们不需要 setValue():

  QMutableListIterator<int> i(list);
  while (i.hasNext())
      i.next() *= 2;

如上所属, QLinkedList, QVector, and QSet的迭代器与 QList的完全相同. 我们现在转向 QMapIterator, 它与QList不一样, 它是在键值对上迭代.

像 QListIterator, QMapIterator 提供 toFront(), toBack(), hasNext(), next(), peekNext(), hasPrevious(), previous(), peekPrevious(). next(), peekNext(), previous(), 或 peekPrevious() 返回的对象通过 key() 和 value() 获取key和value .

下列示例展示移除所有首都名称以 "City" 结尾的键值对:

  QMap<QString, QString> map;
  map.insert("Paris", "France");
  map.insert("Guatemala City", "Guatemala");
  map.insert("Mexico City", "Mexico");
  map.insert("Moscow", "Russia");
  ...

  QMutableMapIterator<QString, QString> i(map);
  while (i.hasNext()) {
      if (i.next().key().endsWith("City"))
          i.remove();
  }

QMapIterator 也提供 key() 和 value() 函数直接在迭代器上操作. 这个迭代器返回最后跳过的元素. 例如, 下述代码将 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());
  }

如果我们想遍历所有相同值的元素, 我们可以使用 findNext() 或 findPrevious(). 下面示例展示移除与给定值相同的所有元素:

  QMutableMapIterator<int, QWidget *> i(map);
  while (i.findNext(widget))
      i.remove();

STL风格迭代器

STL风格迭代器从 Qt 2.0. 版本开始使用. 它们与Qt和STL的 通用算法 兼容, 并且优化速度.

每个容器类都有两种STL风格迭代器: 一种提供只读访问, 一种提供读写访问. 只读迭代器应该尽可能多的使用, 因为它们比读写迭代器更高效.

STL迭代器的API是以数组中的指针建模. 例如, ++ 运算符将迭代器指向下一个元素, * 运算符返回迭代器指向的元素. 事实上, 对于 QVector 和 QStack这种存储在相邻存储空间的容器, iterator 迭代器类型相当于 T *, const_iterator 类型相当于 const T *.

这次讨论, 我们集中讨论 QList 和 QMap. QLinkedList, QVector, QSet 的迭代器类型与 QList的完全一致; 类似地, QHash 的迭代器类型与 QMap一致.

下面是一个经典循环, 顺序遍历 QList<QString> 中的所有元素, 并将其转换为小写:

  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(), 因此不会执行循环.

下图展示4个元素的容器的迭代器指向的位置:

使用STL风格迭代器的后向迭代器reverse_iterator:

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

  QList<QString>::reverse_iterator i;
  for (i = list.rbegin(); i != list.rend(); ++i)
      *i = i->toLower();
  }

在上述代码片段中, 我们使用一元运算符 * 获取存储在特定迭代器位置的元素, 然后调用 QString::toLower(). 大多数编译器也允许我们将其写成 i->toLower(), 但是某些编译器不允许.

对于只读访问而言, 你可以使用const_iterator, constBegin(), constEnd(). 例如:

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

下表总结STL风格迭代器的API:

++ 和 -- 运算符既有前置运算符 (++i, --i) , 又有后置运算符(i++, i--). 前置运算符修改迭代器, 并返回修改后迭代器指向元素; 后置运算符修改迭代器之前保存迭代器副本, 并返回. 若忽略返回值, 我们推荐你使用前置运算符 (++i, --i), 它的运算速度稍高.

对于非const迭代器类型, 一元运算符 * 的返回值可以作为左值使用.

对于 QMap 和 QHash, 运算符 * 返回元素的键值对. 如果你想获取key, 可以通过迭代器调用 key(). 相应地, 迭代器类型也提供 value() 函数返回值. 例如, 下面代码展示如何在控制台打印 a 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迭代器对容器迭代, 你应该基于容器的副本迭代. 例如:

  // 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)
      ...

返回容器的常量或非常量引用函数不会出现此问题.

迭代器隐式共享问题

隐式共享 对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;
  /*
      Now we should be careful with iterator i since it will point to shared data
      If we do *i = 4 then we would change the shared instance (both vectors)
      The behavior differs from STL containers. Avoid doing such things in Qt.
  */

  a[0] = 5;
  /*
      Container a is now detached from the shared data,
      and even though i was an iterator from the container a, it now works as an iterator in b.
      Here the situation is that (*i) == 0.
  */

  b.clear(); // Now the iterator i is completely invalid.

  int j = *i; // Undefined behavior!
  /*
      The data from b (which i pointed to) is gone.
      This would be well-defined with STL containers (and (*i) == 5),
      but with QVector this is likely to crash.
  */

上述示例展示的是 QVector的问题, 但是这个问题在Qt的所有隐式容器存在.

foreach关键字

如果你只想顺序遍历容器中的所有元素, 你可以使用关键字 foreach. 这个关键字是Qt特意为C++语言扩充, 采用预处理器实现.

foreach 关键字的语法是: (variable, container) statement. 下列代码展示如何使用 foreach 遍历 QLinkedList<QString>:

  QLinkedList<QString> list;
  ...
  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 自动访问 (key, value) 键值对, 因此你不应该在容器上调用 values() (参见下列代码, 它将进行不必要的复制). 如果你想遍历键值对, 你可以使用迭代器 (速度更快), 另外, 你可以先获取所有key, 然后使用它们获取value:

  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;
  }

当进入 foreach 循环时, Qt自动获取容器副本. 如果你在迭代时修改容器, 这不会影响循环. (如果不修改容器, 复制仍会发生, 但是由于 隐式共享, 复制容器非常快.)

由于foreach创建容器副本, 使用非常量引用修改变量不会修改原始容器. 它只会修改容器副本, 这可能不是你想要的.

Qt的 foreach 循环是 for 的替代品, 它是C++11及更新版本的一部分. 但是, 基于 for 循环可能迫使Qt容器 分离, foreach 不会. 基于 foreach 总是复制容器, 对于STL容器, 开销较大. 如有疑问, Qt容器更适合 foreach, STL容器更适合 for.

除 foreach 外, Qt 还提供一个 forever 伪关键字:

  forever {
      ...
  }

如果你担心命名空间污染, 你可以在 .pro 文件添加如下内容禁用这些宏:

  CONFIG += no_keywords

其他类似容器的类

Qt包含类似容器的其他模板类. 这些类不提供迭代器, 不能使用关键字 foreach.

• QVarLengthArray<T, Prealloc> provides a low-level variable-length array. It can be used instead of QVector in places where speed is particularly important.
• QCache<Key, T> 提供缓存, 存储Key类型相关联的T类型对象.
• QContiguousCache<T> 提供一种高效方式, 存储连续数据.
• QPair<T1, T2> 存储元素对.

除此之外, Qt还有一些非模板类型: QBitArray, QByteArray, QString, QStringList.

算法复杂性

算法复杂性关注随容器中元素增长, 每个函数的速度多快. 例如, 无论 QLinkedList 存储多少元素, 往 QLinkedList的中间插入元素都非常高效. 另一方面, 如果 QVector 有许多元素, 那么往 QVector 中间插入一个元素代价很大, 因为一半的元素必须移动内存中的位置.

为了描述算法复杂性, 我们使用基于 "big Oh" 符号术语:

• 常量时间: O(1). 如果无论容器存在多少元素, 函数的运行时间都在恒定时间. 一个例子是 QLinkedList::insert().
• 对数时间: O(log n). 函数的运行时间与容器中元素数量成对数关系. 一个例子是二分搜索算法.
• Linear time: O(n). 函数的运行时间与容器中元素数量成线性关系. 一个例子是 QVector::insert().
• 线性对数时间: O(n log n). A function that runs in linear-logarithmic time is asymptotically slower than a linear-time function, but faster than a quadratic-time function.
• 二次方时间: O(n²). 函数的运行时间与容器中元素数量成二次方关系.

下表总结Qt顺序容器的时间复杂度:

在表格中, "Amort." 代表 "平摊行为". 例如, "Amort. O(1)" 表示, 如果你只调用一次函数, 你的时间复杂度可能是 O(n), 但是如果你多次(例如., n 次)调用, 时间复杂度平均是 O(1).

下表总结Qt关联容器及函数的时间复杂度:

对于 QVector, QHash, QSet, 添加元素的平均时间复杂度是 O(log n). 他能通过调预期元素数量函数 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. QString 的空间用完时, 会进行18次重新分配内存: 4, 8, 12, 16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228, 12276, 14324, 16372. 最终, QString 构造 16372 个 Unicode 字符空间, 其中15000 个被占用.

上面的分析似乎有点奇怪, 但是遵循下列原则:

• 在20之前, QString 每次分配4个字符.
• 从20到4084, 每次增加一倍. 更准确地说, 它以20的下一个整数倍为底数, 之后每次增长2倍.(一些内存分配器分配2的整数倍内存时, 性能较差, 它会在每个内存块分配几个字节记录额外信息).
• 从4084开始, 每次增长2048字节. 现代操作系统在重新分配内存时, 不会复制整个数据; 物理内存页仅会简单排序, 实际上, 仅需要复制第一页和最后一页.

QByteArray 和 QList<T> 使用与 QString类似的算法.

QVector<T> 对某些类型数据(C++基本类型, 指针类型, Qt的共享类)调用 memcpy() 移动内存数据, 对只能调用复制构造函数和析构函数的数据调用不同的算法. 这种情况下, 由于内存的重新分配较高, QVector<T> 在内存空间不足时, 总是增加2倍内存, 减少内存重新分配次数.

QHash<Key, T> 的情况完全不同. QHash的内部哈希表以2倍的速度增长, 每次增长, 所有元素都重新定位到新的bucket, bucket的数量计算方式是 qHash(key) % QHash::capacity(). 这种方式也适用于 QSet<T> 和 QCache<Key, T> as well.

对于大多数应用程序而言, Qt的默认增长算法就满足要求. 如果你需要更多控制, QVector<T>, QHash<Key, T>, QSet<T>, QString, QByteArray 提供下列函数, 允许你检查和指定 元素的存储空间:

• capacity() 如果容器不重新分配存储空间, 可存储元素的数量 (对于 QHash and QSet, hash表的bucket数量).
• reserve(size) 预先设置容器的存储空间.
• squeeze() 释放容器中未使用的空间.

如果你大致知道容器中存储多少元素, 你可以在开始时调用 reserve(), 当你填充完容器, 你可以调用 squeeze() 释放额外分配的存储空间.