9.1 顺序容器：QList、QQueue和QLinkedList

本节介绍三种顺序容器：列表 QList、先进先出（First Input First Output，FIFO）队列 QQueue、链表 QLinkedList， QList 和 QLinkList 各配一个示例，示范使用方法。QList 是最为常用的，可以当作数组、队列、栈等使用，队列 QQueue 是 QList 的派生类， 增加了几个队列操作函数，QQueue 自身的函数特别简单，就不单独设置示例了。链表 QLinkedList 是比较特别的顺序容器，是真正的双向链表，数据离散存储， 用双向指针衔接前后节点，需要借助迭代器进行遍历， 而其他顺序容器都可以用数组下标的形式访问元素。

9.1.1 列表 QList

在开始讲解 QList 之前，我们先明确一下 Qt 数据容器能存储什么，不能存储什么。
Qt 提供的数据容器都是模板类，构造时要带数据类型，比如下面这句定义整型数列表：
QList<int> integerList;
Qt 数据容器有支持的数据类型，也有不支持的类型，不仅是 QList ，其他数据容器都有不支持的数据类型。
存储在 Qt 数据容器里面的数据，必须是可赋值类型！
比如 C++ 基本数据类型，int、double、指针等可以存储在 Qt 数据容器里；
Qt 的数据类型，比如 QString、QDate、QTime 等，我们在 Qt Assistant 帮助文档里面查询 QDataStream 支持的可串行化的数值类型，关键字索引为“Serializing Qt Data Types”，这些基本都是可以存到 Qt 数据容器里面的。

还有不能存储在数据容器里的：窗体 QWidget、对话框 QDialog、定时器 QTimer 等等， 凡是 QObject 类和所有 QObject 派生类的对象都不允许直接存储在数据容器里面 。如果代码里新建 QList<QWidget> 列表，那么编译器会报错，QWidget 的复制构造函数和赋值运算符 = 函数都是禁用的。因为窗口不算数据类型，窗口里有线程、指针、句柄、信号和槽函数等等非常复杂的东西，不能当普通数据类型使用。如果确实要存储窗口列表，那么只能存储指 针，比如 QList<QWidget *>。

如果希望自定义数据类型能存储在 Qt 数据容器里面，那么自定义类型必须至少满足三个条件：
①定义默认构造函数，比如 MyData() ;
②定义复制构造函数，比如 MyData(const MyData   &d);
③定义赋值运算符 = 函数，比如 MyData&    operator=(const MyData &d)。
讲完可以存储和不能存储的类型之后，我们开始列表类 QList 的学习。

 QList<T> 就是存储 T 类型数据的列表，类似 T 的数组，可以通过数据下标访问各个元素， QList<T> 针对数据的插入、列表头部添加元素、列表尾部添加元素等等做过优化，访问也非常高效。 QList<T> 应用非常广泛， QList<T> 可以模拟队列操作，比如入队 append() ，出队 takeFirst()；也可以模拟栈工作，比如入栈 append() ，出栈   takeLast()；模拟数组就更简单了，直接用用下标形式，如 aList[0] 。

下面按功能划分，列举该类的函数：
（1）构造函数
QList()    //默认构造函数
QList(const QList<T> & other)   //复制构造函数
QList(QList<T> && other)    //移动构造函数
QList(std::initializer_list<T> args)   //初始列表构造函数
~QList()   //析构函数
第一个是默认构造函数，不带任何参数，可以支持嵌套的列表或与其他数据容器嵌套。
第二个是复制构造函数，将 other 里面的元素均复制到新对象里面。
第三个是 C++11 新特性，配合 std::move 语句使用，将 other 里面的元素全部移动给新建对象，other 本身清空。
第四个也是 C++11 新特性，使得列表对象可以用大括号列举元素初始化，比如 {1, 3, 6, 8} 可以用于初始化整型数列表。
项目里启用 C++11 特性，需要在 *.pro 项目文件里添加一行配置代码：
CONFIG  +=  c++11
第五个是析构函数。
关于移动构造函数请参考： https://www.cnblogs.com/qingergege/p/7607089.html
关于初始化列表构造请参考： https://blog.csdn.net/fengxinlinux/article/details/72614874

（2）添加函数
void    append(const T & value)
void    append(const QList<T> & value)
void    push_back(const T & value)  //同第一个 append()，STL风格添加到队尾
append() 是追加元素到列表的末尾，第一个追加函数添加一个元素到列表末尾，第二个追加函数将一个列表中所有元素追加到列表末尾。
void    insert(int i, const T & value)
插入函数将 value 插入到序号为 i 的位置，如果 i 为 0，元素插到列表列头部，如果 i 为 size() 数值，那么元素添加到列表末尾。
void    prepend(const T & value)
void    push_front(const T & value)  //STL风格，同 prepend()
prepend() 是将参数里的元素 value 添加到列表头部，等同于 insert(0, value) 。

（3）移除和删除函数
移除函数和删除函数调用之前都要判断列表是否非空，用 ! empty() 或  ! isEmpty()  判断，带有序号 i 的必须保证序号不越界。
T    takeAt(int i)  //移除序号为 i 元素并返回该元素
T    takeFirst()     //移除队头元素并返回该元素
T    takeLast()      //移除队尾元素并返回该元素
take**() 移除函数只是将元素从列表中卸载下来，并不会删除元素内存空间，卸下来的元素作为返回值返回。
void    removeAt(int i)  //删除序号为 i 的元素，释放该元素内存
void    removeFirst()     //删除队头元素，释放该元素内存
void    pop_front()       //同 removeFirst() ，STL风格
void    removeLast()      //删除队尾元素，释放该元素内存
void    pop_back()         //同 removeLast()，STL风格
 remove**() 函数没有返回值，直接从列表删除元素，并释放该元素内存空间，删除的元素彻底消失。
int    removeAll(const T & value)       //删除列表中所有等于 value 值的元素，返回删除的数量
bool    removeOne(const T & value) //删除列表中第一个等于 value 值的元素，如果列表有等于 value 值的元素，返回 true，否则返回 false
注意 removeAll( value ) 函数不是清空列表，而是删除列表中所有等于 value 值的元素，并返回删除的计数。
removeOne( value ) 函数第一个等于 value 值的元素，如果删除成功返回 true，即列表中存在等于 value 的元素，
如果删除失败返回 false，即列表中不存在等于 value 的元素。需要特别注意的是：
removeAll( value )、removeOne( value )这两个函数必 须要类型 T 存在 operator==() 等于号函数，T 类型能够进行相等判断！
void    clear()
clear() 函数才是删除列表所有元素，并释放内存空间。

（4）访问和查询函数
int    size() const
int    length() const    //同 size() 
获取列表大小，即存储的元素总数量。列表有 size() 函数，但是没有 resize() 函数，不能直接扩展列表大小。
列表只有为新元素提前保留空间的函数：
void    reserve(int alloc)
reserve() 函数是在程序员能够提前预估元素总量的情况提前为 alloc 数量的元素申请内存空间，保留使用。
如果 alloc 数值不超过 size() 数值，该函数调用被忽略；如果 alloc 数值大于 size() 数值，那么提前分配空间，保证列表能够存储 alloc  数量的元素。注意 reserve() 函数不会改变列表  size() 数值大小，不会添加任何新元素，仅仅是调整内部存储空间，保留使用，实际并没有使用新分配的空间，列表内的元素个数不变。
列表有两个 count() 计数函数，用途不一样：
int    count(const T & value) const
int    count() const
第一个 count( value ) 函数统计列表中等于 value 值的元素个数，这个函数也需要类型 T 带有 operator==() 等于号函数。
第二个 count() 函数不带参数，等同于 size() 函数，是列表元素的总数量。

判断列表是否为空列表，使用如下函数：
bool    empty() const    //空列表返回 true，有元素就返回 false，STL风格
bool    isEmpty() const //空列表返回 true，有元素就返回 false ，Qt 风格
注意 empty() /isEmpty() 、size()/length()/count()  函数要牢记经常使用，因 为列表的函数，凡是涉及到序号 i 的，绝大部分函数都不会判断序号 i 是否越界，需要程序员手动判断序号 i 是否越界，列表的很多函数并不安全！
列表函数为了优化访问效率，基本上没有为访问序号 i 的函数添加越界判断，所以一旦越界，程序很可能崩溃！

访问序号为 i 的元素，可以使用如下函数：
const T &    at(int i) const
at( i ) 函数返回序号为 i 元素的只读引用，但是不 进行数组越界 判断，需要手动判断，该函数的好处是读取效率高。
比较安全的访问函数是下面两个：
T    value(int i) const
T    value(int i, const T & defaultValue) const
第一个 value( i ) 函数返回 序号为 i 的元素（数值复制，不是引用），如果 i 越界，那么返回 T 类型默认构造函数生成的数值，比如 int、double、指针 都返回 0（Qt 容器为基本数据类型做了初始化）。
第二个 value( i, value )  原理是类似的， i 不越界就返回该序号元素值，越界就返回参数里指定的 value 值。
两个 value() 函数因为每次调用都进行数组越界判断，所以访问效率不如 at() 函数高，在知道不越界的情况下使用 at() 更好。

查询数组里是否包含某个数值元素，使用如下函数：
bool    contains(const T & value) const
如果包含等于 value 值的元素返回 true，否则返回 false。要统计等于 value 值的元素个数，使用前面的 count( value )  函数。
如果希望查询等于 value 值的元素的序号，
int    indexOf(const T & value, int from = 0) const          //从前向后 查找等于 value 值的元素序号
int    lastIndexOf(const T & value, int from = -1) const  //从后向前查找等于 value 值的元素序号
indexOf( value, from ) 是从前向后查找元素，第一个参数是要匹配的数值，第二个是查询的起始最小序号，默认从 0  序号开始查找。
lastIndexOf( value, from ) 是从后向前查找元素，第一个参数是要匹配的数值，第二个是查询的起始最大序号，默认从队尾开始查找。
这两个查询函数，如果没找到匹配元素就返回 -1，如果找到了就返回值正确的序号。
注意 contains( value )、count( value ) 、indexOf( value, from )、lastIndexOf( value, from ) 函数都要求 T 类型支持 operator==() 等于号函数。

判断队头、队尾元素是否为 value 的函数如下：
bool    startsWith(const T & value) const    //检查队头是否等于 value
bool    endsWith(const T & value) const     //检查队尾是否等于 value
startsWith( value ) 检查队头元素，如果等于 value 就返回 true，如果列表为空或队头不等于 value 返回 false。
endsWith( value ) 检查队尾元素，如果等于 value 就返回 true，如果列表为空或末尾不等于 value 返回 false。

获取列表头部、尾部元素引用的函数如下：
T &    first()                           //队头读写引用，可以修改队头数值
const T &    first() const       //队头只读引用
T &    front()                         //队头读写引用，可以修改队头数值，STL风格
const T &    front() const     //队头只读引用，STL风格
T &    last()                          //队尾读写引用，可以修改队尾数值
const T &    last() const      //队尾只读引用
T &    back()                        //队尾读写引用，可以修改队尾数值，STL风格
const T &    back() const     //队尾只读引用，STL风格
注意区分只读引用和读写引用，只读引用不会改变元素的数值，而读写引用可以修改队头或队尾的数值。
上面获取队头、队尾引用的 8 个函数本身没有进行列表数组非空判断，在调用它们之前，
必须手动用 ! empty() 或  ! isEmpty() 判断列表非空之后才能调用上面 8 个函数。

获取列表的子列表，使用如下函数：
QList<T>    mid(int pos, int length = -1) const
mid() 函数新建一个子列表，将本列表从序号 pos 开始位置，复制长度为 length 数量的元素到子列表中并返回。
如果 length 为 -1（或大于后面剩余的元素数量），就返回从 pos 开始的所有元素列表。返回的子列表是独立的新列表，与本列表没有内存共享。

（5）替换、移动和交换函数
替换函数就是赋值修改：
void    replace(int i, const T & value)  // 等同于 list[i] = value;
将 序号为 i 的元素数值修改为新的 value。注意序号 i 不能越界，必须满足  0 <= i < size() 。
void    move(int from, int to)
move(from, to) 移动函数是将序号 from 的元素移动到序号为 to 的位置，就是先卸载 from 序号元素，然后插入到 to 序号位置。
两个序号必须都位于 0 到 size() 之间，序号必须合法。
void    swap(QList<T> & other)
这是大 swap() 函数，将本列表所有元素与参数 other 列表内所有元素互换，这个函数不会出错，并且互换的效率非常高。
void    swap(int i, int j)
第二个是小 swap() 函数，将序号 i 的元素和序号 j 的元素数值互换，序号 i、j 不能越界，必须合法。

（6）运算符函数
我们设置三个简单整数列表，在表格中举例说明各个运算符函数用途。三个列表如下：
QList<int> aList = {1, 3, 5};
QList<int> bList = {2, 4, 6};
QList<int> cList;
上面使用 C++11 初始列表构造了列表 aList 和 bList ，cList 是空列表。各个运算符函数举例如下表：

运算符函数 举 例 描述
bool operator!=(const QList<T> & other) const  aList != bList ; aList 和 bList 两个列表有元素不同，结果为 true。
QList<T> operator+(const QList<T> & other) const  cList = aList + bList; aList 和 bList 复制拼接后生成新列表，赋值给 cList。
QList<T> & operator+=(const QList<T> & other)  aList += bList ; 复制 bList 所有元素追加到 aList 末尾。
QList<T> & operator+=(const T & value)  aList += 100 ; 添加一个元素 100 到 aList 末尾。
QList<T> & operator<<(const QList<T> & other)  aList<<bList; 复制 bList 所有元素追加到 aList 末尾。
QList<T> & operator<<(const T & value)  aList<<100; 添加一个元素 100 到 aList 末尾。
QList<T> & operator=(const QList<T> & other)  cList = aList; aList 所有元素都复制一份给 cList，aList本身不变。二者相等。
QList & operator=(QList<T> && other) //移动赋值  cList = std::move(aList) ; aList 所有元素都移动给 cList，aList本身被清空。
bool operator==(const QList<T> & other) const  aList == bList ; aList 和 bList 有元素不同，结果为 false。
只有两个列表所有元素相等并且顺序一样，它们才能算相等。
T & operator[](int i)  aList[0] = 100;
 获取序号为 i 的元素的读写引用，可修改列表元素。
const T & operator[](int i) const  qDebug()<<aList[0] ; 获取序号为 i 的元素的只读引用。

这里说明一下：operator==() 函数需要左右两个列表的长度、每个序号对应元素全部都相同才返回 true，两个列表的元素次序也都要求一样。列表的等于号函数和不等于号函数都要求元素类型 T 必须有 operator==() 判断各个元素是否相等。
移动赋值与移动构造类似，都是 C++11 的新特性，需要使用 std::move  语句实现，移动后右边列表会被清空，元素只存在左边列表里。
中括号函数（数组下标访问函数）要求序号 i 必须合法， 0 <= i < size() ，如果序号越界，程序会崩溃。

（7）迭代器函数
QList 内嵌了 STL 风格的只读迭代器和读写迭代器：
QList::const_iterator      //只读迭代器类，STL风格
QList::iterator               //读写迭代器类，STL风格
QList::​ConstIterator      //只读迭代器，Qt命名风格
QList::​ Iterator               //读写迭代器，Qt命名风格
迭代器就像指向元素的指针，可以枚举列表中所有元素，迭代器本身支持各种操作符函数，
比如 ++ 是找寻下一个元素，-- 是倒退一个元素， (* it) 是获取元素。Qt 帮助文档中示范了迭代器的使用：
QList<QString> list;
list.append("January");
list.append("February");
...
list.append("December");

QList<QString>::const_iterator i;
for (i = list.constBegin(); i != list.constEnd(); ++i)
         cout << *i << endl;
上述代码定义了一个字符串列表，为字符串列表添加多个字符串，然后定义字符串列表的迭代器 i；
i 从列表头部迭代器开始，逐个遍历列表元素，打印每个字符串，直到迭代器末尾结束。
 list.constBegin() 是指向队头元素的指针，但是注意  list.constEnd() 是指向队尾后面假想元素的指 针，
 list.constEnd() 指向的东西根本不存在，仅用于越界判断。

获取指向队头、队尾假想元素的只读迭代器函数如下：
const_iterator    begin() const           //指向队头迭代 器，STL风格
const_iterator    cbegin() const         //指向队头迭代器，STL风格
const_iterator    constBegin() const  //指向队头迭代器，Qt命名风格
const_iterator    end() const             //指向队尾假想元素迭代器，STL风格
const_iterator    cend() const            //指向队尾假想元素迭代器，STL风格
const_iterator    constEnd() const     //指向队尾假想元素迭代器，Qt命名风格
获取指向队头、队尾假想元素的读写迭代器函数如下：
iterator    begin()  //指向队头迭代器，STL风格
iterator    end()     //指向队尾假想元素迭代器，STL风格
利用迭代器也可以添加元素或删除元素，通过迭代器插入元素的函数如下：
iterator    insert(iterator before, const T & value)  //在 before 指向的元素前面插入元素 value
这个 insert() 函数需要注意两点：第一是返回值的迭代器指向新增元素 value ；
第二是执行插入元素操作后，参数里的迭代器 before 失效，不能再使用，只能利用返回值的迭代器进行遍历。
通过迭代器删除一个元素或多个元素的函数如下：
iterator    erase(iterator pos)  //删除 pos 指向的元素，返回指向下一个元素的迭代器或者 list.end()
iterator    erase(iterator begin, iterator end) //删除从 begin 到 end 指向的元素，注意 end 指向的元素不删除
第一个 erase() 函数删除单个元素，它的返回值可能为指向下一个元素或者 list.end() ，要注意判断是否为指向队尾假想元素的迭代器。
第二个 erase() 函数删除多个元素，从 begin 删除到 end，但是 end 指向的元素不删除，这个函数总是返回参数里的 end 迭代器。
由于 QList 自身带有非常多的功能函数，并且支持数组下标形式的访问，实际中几乎不需要使用迭代器操作 QList。因为用迭代器不如用数组下标来操作简单快捷。

（8）容器类型转换函数
列表支持将自身对象转换为其他容器类型，比如集合、标准库列表、向量：
QSet<T>    toSet() const              //转为集合
std::list<T>    toStdList() const     //转为标准库的列表
QVector<T>    toVector() const   //转为向量
QList 能够转出，也能使用列表的静态成员函数，把其他三种容器转换为新的列表对象：
QList<T>    fromSet(const QSet<T> & set)                     //静态函数，将集合转为列表
QList<T>    fromStdList(const std::list<T> & list)            //静态函数，将标准库列表转为 Qt 列表
QList<T>    fromVector(const QVector<T> & vector)     //静态函数，将向量转为列表
静态成员函数的语法类似下面这样：
    QVector<int>  v = {1, 2, 3};
    QList<int> cList = QList<int>::fromVector(v);

（9）其他内容
QList 附带了友元函数 operator<<() 和 operator>>()，用于支持数据流输入和输出：
QDataStream &    operator<<(QDataStream & out, const QList<T> & list)
QDataStream &    operator>>(QDataStream & in, QList<T> & list)
这些流操作符函数正常运行的前提是 类型 T 也能支持流的输入输出，对于 C++ 基本类型 int、double 等都没问题；
Qt 的数据类型如 QColor、QPoint 一般也都附带了友元函数，用于支持流输入输出。
如果使用自定义类型，希望存储在列表中并支持自动的流输入输出，那么要为自定义类型添加友元函数 operator<<() 和 operator>>() 。

使用 QList 时，需要注意 QList 仅支持存储 值类型、指针类型，不能存储变量的引用。
如果定义列表时类型 T 设置为引用，如 QList<int &> ，那么程序无法编译！

Qt 带有全局函数，可以支持容器类对象的排序：
void qSort(Container & container)  //排序
void qStableSort(Container & container)  //稳定排序
排序函数要求容器的元素类型 T 必须支持 operator<() 小于号函数，用于比较元素大小。
Qt 调用的小于号函数原型是两个参数的全局 operator<() 函数，不是成员函数，应该在类外面声明并定义下面的小于号函数：
bool  operator< ( const T &t1, const T &t2 )
一般要将该函数声明为 T 类型的友元函数，方便访问私有变量。

最后我们梳理一下，如果自定义类型希望能够完美地和 QList 配合使用，那么需求如下：
① 必须是可赋值类型，需要默认构造函数、复制构造函数、赋值函数 operator=() ；
② 如果希望支持查询函数，需要双等号函数 operator==()；
③ 如果希望支持排序函数，需要全局小于号函数 operator< (  const T &t1, const T &t2 ) ；
④ 如果希望支持 QDataStream 数据流输入输出，那么添加友元函数  operator<<() 和 operator>>() 。
第一条是必须实现的函数，后面三条是建议实现的函数。

列表的内容介绍到这，本教程在之前的 3.4.2 、7.2.4 、 7.5.4、8.1.4、8.2.6、8.3.5 等章节均有使用列表类的示例代码。
读者可以回顾一下前面的代码，8.3.5 节将列表当作队列使用，其他章节将列表当作数组来使用。
本小节的示例实现自定义类型的联系人 Contact，为联系人 Contact 添加功能函数，使得列表类能够存储该类对象，并添加各种辅助函数实现查询、排序、数据流输入输出等功能。
我们在 D:\QtProjects 里面新建名为 ch09 的文件夹，开始本章示例学习。
打开 QtCreator，新建一个 Qt Widgets Application 项目，在新建项目的向导里填写：
①项目名称 contactlist，创建路径 D:\QtProjects\ch09，点击下一步；
②套件选择里面选择全部套件，点击下一步；
③基类选择 QWidget，点击下一步；
④项目管理不修改，点击完成。
我们打开 widget.ui 界面文件，按照下图拖入控件：
ui
第一行是列表控件，默认对象名 listWidget。
第二行是三个标签和三个单行编辑器，标签文本分别为 “姓名”、“电话”、“地址”，
单行编辑器对象名 lineEditName、lineEditPhone、lineEditAddress，第二行使用水平布局。
第三行和第四行是六个按钮，按钮文本对象名分别为：
“添加”pushButtonAdd、“删除”pushButtonDel、“查询姓名”pushButtonFind、“姓名排 序”pushButtonSort、“保存”pushButtonSave、“打开”pushButtonOpen，第三行和第四行使用一个网格布局。
窗口整体使用垂直布局，窗口尺寸 500*330。
界面布局设置好后，我们依次为六个按钮添加槽函数：
ui
添加槽函数之后，我们进入 QtCreator编辑界面，我们点击 QtCreator 菜单“文件”-->“新建文件或项目...”，
弹出新建对话框，我们在该对话框左边一列选择“文件和类”里面的“C++”，然后中间选择“C++ Class”
ui
然后右下角点击 “Choose... ”按钮，进入定义类的界面：
ui
类名输入 Contact，头文件名和源文件名用自动填充的 contact.h 和 contact.cpp ，然后点击“下一步”按钮，进入项目管理界面：
ui
项目管理界面不用修改，直接点击“完成”按钮，回到 QtCreator 编辑界面可以看到新增的 contact.h 和 contact.cpp 文件。
我们打开 contact.h 头文件并编辑代码如下：
#ifndef CONTACT_H 
#define CONTACT_H

#include <QString> //字符串
#include <QFile>   //文件类
#include <QDataStream> //数据流类

class Contact
{
public:
    Contact();//默认构造函数，必须有
    ~Contact();
    //带参数的构造函数
    Contact(QString strName, QString strPhone, QString strAddress);
    //复制构造函数
    Contact(const Contact &c); //必须有
    //赋值运算符函数
    Contact& operator=( const Contact &c ); //必须有

    //双等号函数，用于支持列表查询函数，双等号和小于号都按姓名字符串比较
    bool operator==( const Contact &c );

    //友元声明，小于号函数必须用两个参数的全局函数
    friend bool operator<( const Contact &c1, const Contact &c2 );

    //友元声明，流插入运算符和流提取运算符函数
    friend QDataStream & operator<<(QDataStream & out, const Contact &c );
    friend QDataStream & operator>>(QDataStream & in, Contact &c);

    //toString 函数方便将三个成员变量作为一行文本显示到列表控件
    QString toString();

    //成员变量
    QString m_strName;   //姓名
    QString m_strPhone;  //电话
    QString m_strAddress;//地址
};
//两个参数的小于号函数声明
bool operator<( const Contact &c1, const Contact &c2 );
//流插入运算符和流提取运算符函数本身的声明
QDataStream & operator<<(QDataStream & out, const Contact &c );
QDataStream & operator>>(QDataStream & in, Contact &c);

#endif // CONTACT_H
我们在该文件添加了字符串、文件类和数据流类的头文件引用。
Contact 类只有默认构造函数和析构函数是创建文件时自动添加的，其他代码都是手动编写的。
我们为该类添加了带三个参数的构造函数，对应三个成员变量，即姓名字符串、电话字符串和地址字符串。
然后添加了复制构造函数、赋值运算符函数的声明，加上原有的默认构造函数，这三个函数是支持 QList 存储的必要条件。
然后添加了双等号比较函数，用于支持 QList 的查询函数。
添加了全局函数 operator<( )  的友元声明，这样保证能访问类的私有变量。
添加了全局函数 operator<<() 和 operator>>() 的友元声明，这样保证数据流输入输出时能够访问类的私有变量。
添加了类的公开成员函数 toString()，方便将成员变量字符串拼接成一行文本，用于后面窗口里的列表控件显示。
类里面最后是三个成员变量，存储姓名、电话和地址。
类外面是三个全局函数声明，小于号函数 operator<( ) 用于支持容器内元素的排序，后面是按照联系人姓名字符串比较的。
operator<<() 和 operator>>() 用于支持数据流输出和输入。

接下来分段添加 contact.cpp 文件的代码，实现头文件里声明的所有函数，首先来看默认的构造函数和析构函数：
#include "contact.h"

//默认构造函数
Contact::Contact()
{
    m_strName = "None";
    m_strPhone = "00000";
    m_strAddress = "None";
}

Contact::~Contact()
{

}
默认构造函数里设置了默认的姓名、电话和地址的字符串，析构函数没改动。
下面来看带三个参数的构造函数和复制构造函数：
//带参数的构造函数
Contact::Contact(QString strName, QString strPhone, QString strAddress)
{
    m_strName = strName;
    m_strPhone = strPhone;
    m_strAddress = strAddress;
}

//复制构造函数
Contact::Contact(const Contact &c)
{
    m_strName = c.m_strName;
    m_strPhone = c.m_strPhone;
    m_strAddress = c.m_strAddress;
}
这两个构造函数代码简单，就是把参数里的变量对应地设置给成员变量。
然后来看赋值运算符函数：
//赋值运算符函数
Contact & Contact::operator= ( const Contact &c )
{
    m_strName = c.m_strName;
    m_strPhone = c.m_strPhone;
    m_strAddress = c.m_strAddress;
    return *this;
}
这个函数也简单，从参数对象里复制对应的字符串给成员变量，然后返回自身对象。返回值是方便连等操作，如 a=b=c 。
下面来看双等号比较函数：
//双等号函数，用于支持列表查询函数
bool Contact::operator== ( const Contact &c )
{
    //比较纯粹看姓名的字符串比较
    return ( c.m_strName == m_strName ) ;
}
该函数将参数里对象 c 的姓名字符串与成员变量姓名字符串进行相等判断，然后返回比较结果。这个函数用于支持 QList 查询操作，QList 的函数比如 contains()、indexOf()、lastIndexOf() 会调用这个函数做比较，查看列表对象里是否有相等的元素。我们的双等号函数只做了姓名字符串比较，电话字符串和地址字符串没有判断，是否相等只看姓名字符串是否一致。
下面来看全局的小于号函数：
//两个参数的小于号函数，全局函数，用于支持排序功能
bool operator<( const Contact &c1, const Contact &c2 )
{
    //纯粹看姓名的字符串比较
    return ( c1.m_strName < c2.m_strName );
}
小于号函数也是只比较两个对象里姓名字符串的字典序，而不用管电话、地址。注意等于号、小于号、大于号这些比较运算符都有两种实现，一种是单参数的类成员函数，如 上 面的双等号成员函数，另一种是带两个参数的全局函数，比如这里的小于号函数，参数 c1 是小于号左边的对象，c2 是小于号右边的对象。具体使用哪种实现要看场景需求，因为 qSort() 排序函数调用的是两个参数的全局小于号函数，所以这里使用全局的小于号函数。
接下来看看 toString() 函数：
//toString 函数方便将三个成员变量作为一行文本显示到列表控件
QString Contact::toString()
{
    //用制表符拼接三个字符串
    QString strRet = m_strName + QString("\t")
                + m_strPhone + QString("\t")
                + m_strAddress;
    return strRet;
}
该函数将三个字符串用两个 Tab 制表符拼接，这个函数与 QList 要求无关，是我们方便添加对象的字符串到列表控件显示用的。
contact.cpp 文件最后是两个全局的流操作符函数：
//数据流操作，流插入运算符
QDataStream & operator<<(QDataStream & out, const Contact &c )
{
    out<<c.m_strName<<c.m_strPhone<<c.m_strAddress;
    return out;
}

//数据流操作，流提取运算符
QDataStream & operator>>(QDataStream & in, Contact &c)
{
    in>>c.m_strName>>c.m_strPhone>>c.m_strAddress;
    return in;
}
第一个流插入操作符函数，依次将姓名、电话、地址字符串输出到流 out 中，并返回 out 流对象。
第二个流提取操作符函数，依次从输入流 in 中提取姓名、电话、地址字符串，并返回 in 流对象。

Contact 类的内容就是上面的代码，接下来我们来编辑窗体类的头文件 widget.h ，窗体头文件内容如下：
#ifndef WIDGET_H 
#define WIDGET_H

#include <QWidget>
#include <QList>   //列表类
#include "contact.h"  //联系人

namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT

public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();

private slots:
    void on_pushButtonAdd_clicked();

    void on_pushButtonDel_clicked();

    void on_pushButtonFind_clicked();

    void on_pushButtonSort_clicked();

    void on_pushButtonSave_clicked();

    void on_pushButtonOpen_clicked();

private:
    Ui::Widget *ui;
    //联系人列表
    QList<Contact> m_listContacts;
};

#endif // WIDGET_H
该文件首先添加 QList 模板类和自定义 Contact 类的头文件引用。
Widget 类里的六个槽函数是之前在设计界面通过按钮的右键菜单添加的。
Widget 类里最后一行定义了联系人列表  m_listContacts，使用 QList 容器存储自定义的 Contact 类对象。

接下来我们分段编辑 widget.cpp 源文件的代码，首先是头文件引用、构造函数、析构函数：
#include "widget.h" 
#include "ui_widget.h"
#include <QDebug>
#include <QMessageBox>
#include <QFile> //文件
#include <QFileDialog> //文件打开或保存对话框
#include <QDataStream> //数据流

Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);
    //定义4个联系人，添加到列表对象和列表控件，列表对象和列表控件一直同步
    //第1个
    Contact daala("Daala", "44444", "North");
    m_listContacts.append(daala);
    ui->listWidget->addItem( daala.toString() );
    //第2个
    Contact bob("Bob", "22222", "South");
    m_listContacts.append(bob);
    ui->listWidget->addItem( bob.toString() );
    //第3个
    Contact carl("Carl", "33333", "West");
    m_listContacts.append(carl);
    ui->listWidget->addItem( carl.toString() );
    //第4个
    Contact alice("Alice", "11111", "East");
    m_listContacts.append(alice);
    ui->listWidget->addItem( alice.toString() );
}

Widget::~Widget()
{
    delete ui;
}
我们添加打印调试信息、消息框、文件、文件对话框、数据流等类的头文件引用。
构造函数代码逻辑很简单，就是定义了四个联系人对象，添加到 m_listContacts 列表对象和窗口里的列表控件。
Contact 类的 toString() 函数这时候就体现出方便了，不需要每次都自己用代码拼接该类的三个成员字符串。

下面来看“添加”按钮的槽函数：
//添加联系人
void Widget::on_pushButtonAdd_clicked()
{
    //获取姓名、电话、地址字符串
    QString strName = ui->lineEditName->text().trimmed();
    QString strPhone = ui->lineEditPhone->text().trimmed();
    QString strAddress = ui->lineEditAddress->text().trimmed();
    //姓名不能为空，电话地址可以空
    if( strName.isEmpty() )
    {
        QMessageBox::warning(this, tr("姓名检查"), tr("姓名为空，请输入姓名。"));
        return;
    }
    //姓名不空
    Contact person(strName, strPhone, strAddress);
    //添加到列表对象和列表控件
    m_listContacts.append( person );
    QListWidgetItem *item = new QListWidgetItem( person.toString() );
    ui->listWidget->addItem( item );
    //选中新条目
    ui->listWidget->setCurrentItem( item );//当前条目是加虚线框的那个
    item->setSelected( true );  //高亮显示
    ui->listWidget->setFocus(); //设置显示焦点
}
该函数首先获取三个单行编辑器的字符串，并判断姓名字符串是否为空，如果姓名为空就不处理。
姓名不空的时候，定义联系人对象 person，然后同步地添加到列表对象  m_listContacts 和列表控件。
这里手动 new 了一个列表控件条目，方便设置新条目为列表控件的当前条目，并高亮选中，
最后把显示焦点设置给列表控件，这样用户就能立即看到高亮的新条目。

接下里看“删除”按钮的槽函数：
//删除联系人
void Widget::on_pushButtonDel_clicked()
{
    //获取当前条目
    QListWidgetItem *curItem = ui->listWidget->currentItem();
    //判断指针是否为空
    if( NULL == curItem )
    {
        return; //没东西可以删除
    }
    //存在当前条目
    //获取当前条目的序号
    int ix = ui->listWidget->currentRow();
    //从列表对象删除联系人
    m_listContacts.removeAt( ix );
    //列表控件同步删除
    delete curItem; curItem = NULL;
}
该函数首先获取列表控件的当前条目，如果为空指针就不处理。
如果当前条目非空，那么获取当前条目的行号，也就是条目序号，我们首先从列表对象 m_listContacts 删除该序号的元素，
然后同步删除列表控件的对应条目。为了让列表对象 m_listContacts 和 列表控件显示一致，我们要在所有元素的增加、删除、排序等过程中注意列表对象和列表控件的同步操作。

下面来看看“查询姓名”按钮的槽函数：
//查找联系人
void Widget::on_pushButtonFind_clicked()
{
    //获取姓名字符串
    QString strName = ui->lineEditName->text().trimmed();
    //判断是否为空
    if( strName.isEmpty() ) //姓名为空，不需要查询
    {
        QMessageBox::warning(this, tr("姓名检查"), tr("姓名为空，无法查询。"));
        return;
    }
    //存在姓名
    //从列表对象查找序号
    int ix = m_listContacts.indexOf( Contact(strName, "", "") );
    //如果找不到返回 -1
    if( ix < 0 )
    {
        QMessageBox::information(this, tr("查找"), tr("没有找到姓名一样的联系人。"));
        return;
    }
    else //找到了
    {
        QMessageBox::information(this, tr("查找"),
                     tr("存在姓名匹配的联系人，序号为 %1 ").arg(ix) );
        //设置列表控件当前选中条目为该序号
        ui->listWidget->setCurrentRow( ix );
        ui->listWidget->currentItem()->setSelected(true); //高亮色
        ui->listWidget->setFocus(); //显示焦点
    }
}
该函数首先获取单行编辑器里的姓名字符串，判断如果为空，那么不处理返回。
如果姓名字符串不为空，那么调用 m_listContacts.indexOf() 函数查询是否有同样姓名字符串的对象，这个函数参数里是一个临时联系人对象，只设置了姓名字符串，电话和地址为空，因为查询时调用的  Contact::operator== () 函数只比较姓名字符串，其他的成员变量不比较。
查询函数的返回值 ix 如果小于 0，说明没找到，提示消息框说没有找到，并返回；
如果返回值是 0 或正数，说明找到了，提示消息框，显示第一个匹配的联系人序号，然后设置列表控件的当前条目为 ix 序号的条目，并设置该条目高亮色显示，将显示焦点设置给列表控件，方便用户直接看到匹配的联系人。

下面来看“姓名排序”按钮的槽函数代码：
//按照姓名排序
void Widget::on_pushButtonSort_clicked()
{
    //获取计数
    int nCount = m_listContacts.count();
    if( nCount <= 1 )
    {
        return; //没有联系人或者只有 1 个，不需要排序
    }
    //存在 2 个以上联系人，直接调用排序函数
    ::qSort( m_listContacts );
    //清空列表控件，然后按照排序后的结果显示
    ui->listWidget->clear();
    //循环添加条目给列表控件
    for(int i=0; i<nCount; i++)
    {
        ui->listWidget->addItem( m_listContacts[i].toString() );
    }
    //列表控件和列表对象的同步完毕
}
该函数首先获取列表对象存储的联系人总数，如果总数小于等于 1，说明没联系人或只有 1 个联系人，不需要排序，直接返回。
如果联系人有 2 个或以上，那么调用 qSort() 函数对列表容器进行排序，排序函数的语法非常简单，把容器对象作为参数调用即可。
qSort() 函数内部会调用我们之前编写的 全局小于号函数 operator<( c1, c2 )。
排序完成后，为了同步显示到列表控件，我们先把列表控件内容全部清空，然后将排序后的 m_listContacts 列表的每个元素，按照顺序添加相应字符串给列表控件， m_listContacts 列表的每个元素对于一个列表控件的条目。
这样保证排序后的列表对象里元素顺序和列表控件条目顺序能一致。

下面来看“保存”按钮的槽函数代码：
//保存到文件 *.ds
void Widget::on_pushButtonSave_clicked()
{
    //获取计数
    int nCount = m_listContacts.count();
    if(nCount < 1) //没有元素
    {
        return;
    }
    //存在元素，先获取要打开的文件名
    QString strFile = QFileDialog::getSaveFileName(this, tr("保存文件"), tr("./test.ds"),
                      tr("QDataStream Files (*.ds)") );
    //判断文件名是否为空
    if( strFile.isEmpty() )
    {
        return; //用户没有设置保存的文件名
    }
    //设置了文件名，定义文件对象并尝试打开
    QFile fileOut(strFile);
    if( ! fileOut.open( QIODevice::WriteOnly ) )
    {
        QMessageBox::warning(this, tr("保存文件"), tr("指定文件名无法打开，请检查文件名和写入权限。"));
        return;
    }
    //正常打开
    QDataStream ds( &fileOut );
    //输出到文件只需一句
    ds<<m_listContacts; //QList 和 Contact 都有配套的流操作符函数，因此可以这样一句搞定
    //保存成功
    QMessageBox::information(this, tr("保存文件"), tr("保存成功！"));
    //关闭文件
    ds.setDevice(NULL);
    fileOut.close();
}
该函数首先获取列表对象里的联系人总数，如果总数小于 1，说明没联系人，直接返回，不需要处理。
如果存在联系人，那么调用 QFileDialog::getSaveFileName() 静态函数获取要保存的文件名， 这个静态对话框函数第一个参数是父窗口指针，第二个参数对话框标题文本，第三个参数是预设的默认文件名， 第四个参数是扩展名筛选字符串。
如果用户在弹出的文件保存对话框设置了文件名，那么该函数返回文件名， 如果用户没有设置文件名就关闭了对话框，那么返回空字符串。所以我们要先判断获取的文件名字符串，如果为空就返回，不处理。
如果文件名字符串有内容，那么根据文件名定义文件对象 fileOut，并尝试用只写模式打开：
如果打开失败，提示消息框通知用户检查文件名和写入权限等问题，然后返回。
如果打开成功，那么以文件对象指针定义数据流对象，然后把 m_listContacts 联系人列表输出到数据流。
将  m_listContacts 输出数据流的代码只有一句，因为 QList 类附带流操作符函数，循环将每个元素写入数据流；
而对于每个元素内，就调用我们之前编写的 operator<<() 函数，将联系人三个字符串写到数据流。
ds<<m_listContacts  这一句调用非常简单，简单的前提是 QList 模板类和我们的 Contact 类做了很多工作，才能够这么方便地输出联系人列表。
输出联系人列表完成后，显示保存成功的消息框，然后将数据流置空，关闭文件。

下面来看最后一个“打开”按钮的槽函数代码： 
//从文件 *.ds 读取联系人并显示
void Widget::on_pushButtonOpen_clicked()
{
    //获取要打开的文件名
    QString strFile = QFileDialog::getOpenFileName(this, tr("打开文件"), tr("./test.ds"),
                      tr("QDataStream Files (*.ds)") );
    //判断是否为空
    if( strFile.isEmpty() )
    {
        return; //用户没设置要打开的文件名
    }
    //设置了文件名，定义文件对象，并尝试打开
    QFile fileIn( strFile );
    if( ! fileIn.open( QIODevice::ReadOnly ) )
    {
        QMessageBox::warning(this, tr("打开文件"), tr("无法打开指定文件，请检查文件名和读取权限。"));
        return;
    }
    //正常打开
    QDataStream ds( &fileIn );
    //先清空旧的列表对象和列表控件内容
    m_listContacts.clear();
    ui->listWidget->clear();
    //加载
    ds>>m_listContacts; //QList 和 Contact 都有配套的流操作符函数，因此可以这样一句搞定
    //读取完毕，需要同步显示到列表控件
    int nCount = m_listContacts.count();
    for(int i=0; i<nCount; i++)
    {
        ui->listWidget->addItem( m_listContacts[i].toString() );
    }
    //同步完成
    QMessageBox::information(this, tr("打开文件"), tr("打开文件成功，并已加载联系人列表。"));
    //关闭文件
    ds.setDevice(NULL);
    fileIn.close();
}
该函数首先调用 QFileDialog::getOpenFileName() 函数获取要打开的文件名，文件对话框类的 getOpenFileName() 和getSaveFileName() 参数是差不多的，只是 getOpenFileName() 针对打开文件时选择已经存在的文件，而 getSaveFileName() 一般用于构造不存在的文件名以供写入，如果 getSaveFileName()  选择了已存在的文件，该对话框会提示是否覆盖现有文件。
QFileDialog::getOpenFileName() 对话框也可能没有选择文件名就关闭了，所以要判断返回的字符串，如果文件名字符串为空就返回，不处理； 如果返回的字符串有内容，那么根据文件名创建文件对象，并尝试以只读模式打开。
如果文件打开失败，弹出消息框通知用户检查文件名和读取权限等问题，然后返回。
如果文件打开成功，根据文件对象指针创建数据流对象。
接着把列表对象和列表控件全部清空，然后用一句  ds>>m_listContacts 从文件中加载联系人列表。
从数据流输入到列表对象的代码也是非常简单的，因为 QList 模板类和我们的 Contact 类做了流操作符重载，所以可以直接输入列表对象。
数据流输入完毕后，我们获取列表对象里的联系人总数，然后将每个联系人对象的字符串添加到列表控件显示。
然后弹出消息框表示打开文件和加载联系人列表都完成了，最后将数据流置空，关闭文件。

注意这个示例为了节省篇幅，没有对输入数据流的异常进行判断，一般正式项目中一定要对输入文件的异常做判断，尽可能防止输入源污染造成程序崩溃。这个示例的代码讲 解到这，我们构建运行示例，可以尝试添加新联系人：
run
点击“姓名排序”，就可以看到排序后的效果：
run
其他按钮的功能读者自行测试一下。我们下面学习 QList 的派生类 QQueue 。

9.1.2 队列 QQueue

QQueue 是 QList 的派生类，继承了列表的全部功能，仅仅是添加了几个队列操作函数，这些队列新函数都可以在基类 QList 找到相应的功能实现，就是名字有点区别。QQueue 也有默认的构造函数和析构函数：
QQueue()
~QQueue()
这两个函数内容都是空的，队列的复制构造函数、赋值运算符函数等全都继承基类 QList 的函数。
新增的入队和出队操作函数如下：
void    enqueue(const T & t)  //元素入队，添加到队尾
T    dequeue()                         //元素出队，将队头元素卸下并返回
入队其实就是调用基类的 append() ，出队就是调用基类的 takeFirst()，仅仅就是套层壳，加个新函数名。
队列类还添加了获取队头元素引用，但是不卸下队头的函数：
T &    head()                          //获取队头的读写引用
const T &    head() const      //获取队头的只读引用
最后队列还添加了与其他队列互换元素的函数：
void    swap(QQueue<T> & other)
这个函数将自身所有元素和 other 队列里面的元素全部互换，交换效率非常高，并且从不失败。
典型的队列操作代码示例如下：
QQueue<int> queue;
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
while (!queue.isEmpty())
    cout << queue.dequeue() << endl;
上述代码依次入队了三个元素，然后用 while 循环依次将元素出队并打印。isEmpty() 函数是从基类继承的，判断队列是否为空。
QQueue 自身的函数非常简单，不单独设置示例了，QQueue 作为本节末尾的练习供读者练手。

9.1.3 链表 QLinkedList

链表 QLinkedList 和列表 QList 没什么关系，只是名字有点像。链表 QLinkedList 是通过双向指针前后衔接的，不能用数组下标的形式访问，所有的遍历操作都是通过迭代器实现。QList 和 QVector 插入元素时像数组，需要进行大批量的元素腾挪，把插入元素后方的元素全部往后面移动，所以随机插入数据的开销比较大。而 QLinkedList 插入新元素时，仅仅是修改前后元素的双向指针，链表插入元素操作的时间复杂度总是 O(1) ，即常量时间。在频繁随机插入和随机删除元素的情景，链表就比较适合使用，因为链表的随机插入和随机删除的效率在所有顺序容器中效率最高。
 
存储在链表里的元素也要求必须是可赋值类型，这点与 QList 一样。下面按功能划分，列举该类的函数：
（1）构造函数
QLinkedList()        //默认构造函数
QLinkedList(const QLinkedList<T> & other)    //复制构造函数
QLinkedList(std::initializer_list<T> list)            //初始化列表构造函数，C++11特性
QLinkedList(QLinkedList<T> && other)        //移动构造函数，C++11特性
~QLinkedList()        //析构函数
第一个是默认构造函数，可以用于支持容器类的嵌套。
第二个是复制构造函数，将参数 other 里的元素都复制一份给新建链表对象。
第三个是初始化列表构造函数，可以根据 {1, 2, 3}  这种列表新建链表对象。
第四个是移动构造函数，将 other 里的元素全部移动给新建的链表对象，就是将元素都搬家的意思，这个函数调用语法示例：
QLinkedList<int>  listA = {1, 2, 3};    //初始化列表构造   
QLinkedList<int>  listB = std::move (listA );         //移动构造函数，listA 会被搬空，元素都存到 listB
第五个是析构函数。
（2）添加函数
链表自带了两个添加元素到末尾的函数和两个添加元素到头部的函数：
void    append(const T & value)         //添加元素到链表末尾
void    push_back(const T & value)    //添加元素到链表末尾，STL风格
void    prepend(const T & value)        //添加元素到链表头部
void    push_front(const T & value)    //添加元素到链表头部，STL风格
链表能添加元素到头部和尾部，但是没有直接将元素插入到中间某个位置的函数，链表必须借助迭代器才能将元素插到链表中间的某个位置。链表除了头部、尾部的元素，其他中间元素都要依赖迭代器插入、删除和访问。

（3）移除和删除函数
注意使用移除和删除函数之前要先用  ! empty() 或  ! isEmpty()   判断列表非空才能移除和删除。
take***() 移除函数只是将元素从链表卸下，并返回该元素值，不会彻底删除该元素：
T    takeFirst()     //卸下头部元素并返回该元素
T    takeLast()     //卸下尾部元素并返回该元素
remove***() 函数会将元素从链表卸下，并且彻底删除该元素的内存空间，删除链表头部、尾部元素的函数如下：
void    removeFirst()    //删除头部元素
void    pop_front()       //删除头部元素，STL风格
void    removeLast()    //删除尾部元素
void    pop_back()       //删除尾部元素，STL风格
如果希望删除一个匹配的元素或删除所有匹配的元素，使用如下函数：
bool    removeOne(const T & value)   //如果找到匹配的元素就删除第一个匹配的元素，删除后返回true，如果没找到相等的元素返回 false
int    removeAll(const T & value)        //删除所有匹配的元素，并返回删除数量
removeOne(  value ) 和 removeAll(  value )  函数要求元素类型 T 支持 operator==() 双等号函数。
removeAll(  value ) 函数不是删除所有元素，是删除所有匹配的元素。
真正删除链表全部内容的函数是下面这个：
void    clear()

（4）访问和查询函数
链表可以查询元素的总数量：
int    size() const        //获取元素总数量
int    count() const    //获取元素总数量
如果希望统计匹配某 value 的元素个数，使用下面的函数：
int    count(const T & value) const     //统计等于 value 值的元素个数
判断链表中是否包含匹配 value 的元素，使用下面函数：
bool    contains(const T & value) const    //判断有没有等于 value 值的元素
判断链表是否为空，可以用下面两个函数：
bool    empty() const    //判断链表是否为空，STL风格
bool    isEmpty() const  //判断链表是否为空
不卸下元素，直接获取链表头部、尾部元素引用的函数如下：
T &    first()    //获取头部元素的读写引用
const T &    first() const    //获取头部元素的只读引用
T &    front()  //获取头部元素的读写引用，STL风格
const T &    front() const  //获取头部元素的只读引用，STL风格
T &    back()    //获取尾部元素的读写引用，STL风格
const T &    back() const  //获取尾部元素的只读引用，STL风格
T &    last()    //获取尾部元素的读写引用
const T &    last() const    //获取尾部元素的只读引用
判断头部、尾部元素是否等于 value 值的函数如下：
bool    startsWith(const T & value) const    //判断头部元素是否等于 value
bool    endsWith(const T & value) const     //判断尾部元素是否等于 value
访问和查询函数、删除函数里面，凡是带 value 参数都要求链表元素类型 T 本身支持 operator==() 函数判断。

（5）交换函数
下面函数将自身元素与 other 链表的元素全部互换，这个操作非常快，并且不会失败。
void    swap(QLinkedList<T> & other)

（6）运算符函数
我们以下面三个链表举例子，示范运算符函数的使用：
QLinkedList<int> listA = {1, 2, 3};
QLinkedList<int> listB = {4, 5, 6};
QLinkedList<int> listC;
链表支持运算符函数如下表所示：

运算符函数 举 例 描述
bool operator!=(const QLinkedList<T> & other) const  listA != listB ; listA 和 listB 两个链表有元素不同，结果为 true。
QLinkedList<T> operator+(const QLinkedList<T> & other) const  listC = listA + listB; 将listA和listB的元素都复制并拼接为新链表，赋值给listC 。
QLinkedList<T> & operator+=(const QLinkedList<T> & other)  listA += listB ; 将 listB 的元素都复制添加到 listA 的末尾。
QLinkedList<T> & operator+=(const T & value)  listA += 100 ; 将 100 添加到listA 末尾。
QLinkedList<T> & operator<<(const QLinkedList<T> & other)  listA<<listB; 将 listB 的元素都复制添加到 listA 的末尾。
QLinkedList<T> & operator<<(const T & value)  listA<<100; 将 100 添加到listA 末尾。
QLinkedList<T> & operator=(const QLinkedList<T> & other)  listC = listA; 将listA的元素都复制并添加给listC，listA 本身不变。二者相等。
QLinkedList<T> & operator=(QLinkedList<T> && other)//移动赋值  listC = std::move(listA); 将listA的元素都移动添加给listC，listA 本身被清空。
bool operator==(const QLinkedList<T> & other) const  listA == listB; listA 和 listB 存在不相等的元素，结果为 false。
只有两个链表所有元素相等并且顺序一样，它们才能算相等。

这里说明一下：operator==() 函数要求两个链表的所有元素都相等，并且顺序都一样，链表长度一样，才会判断二者相等。 双等号函数、不等号函数都要求链表元素类型 T 自身支持 operator==() 函数判断。
移动赋值与移动构造类似，都是 C++11 的新特性，需要使用 std::move  语句实现， 移动后右边链表会被清空，元素只存在左边链表里。
链表不能通过数组下标访问元素，只能依赖迭代器遍历元素，而其他的顺序数据容器是支持数组下标形式访问的。

（7）迭代器函数
链表自带了 STL 风格迭代器：
class    iterator        //STL 命名风格读写迭代器
typedef    Iterator   //Qt 命名风格读写迭代器
class    const_iterator        //STL 命名风格只读迭代器
typedef    ConstIterator    //Qt 命名风格只读迭代器
迭代器就像指向元素的指针，可以枚举链表中所有元素，迭代器本身支持各种操作符函数，
比如 ++ 是找寻下一个元素，-- 是倒退一个元素， (* it) 是获取元素。Qt 帮助文档中示范了迭代器的使用：
QLinkedList<QString> list;
list.append("January");
list.append("February");
...
list.append("December");

QLinkedList<QString>::iterator i;
for (i = list.begin(); i != list.end(); ++i)
    cout << *i << endl;
上述代码定义了一个字符串链表 list，为字符串链表添加多个字符串，然后定义字符串链表的迭代器 i；
i 从链表头部迭代器开始，逐个遍历链表元素，打印每个字符串，直到迭代器末尾结束。
 list.begin() 是指向链表头部元素的指针，但是注意  list.end() 是指向链表尾部后面假想元素的指 针，
 list.end() 指向的东西根本不存在，仅用于越界判断。

获取指向链表头部迭代器、尾部后面假想元素迭代器的函数如下：
iterator    begin()    //指向头部元素的读写迭代器
const_iterator    begin() const    //指向头部元素的只读迭代器，STL风格
const_iterator    cbegin() const  //指向头部元素的只读迭代器，STL风格
const_iterator    constBegin() const //指向头部元素的只读迭代器，Qt风格
iterator    end()    //指向尾部后面假想元素的读写迭代器
const_iterator    end() const      //指向尾部后面假想元素的只读迭代器，STL风格
const_iterator    cend() const    //指向尾部后面假想元素的只读迭代器，STL风格
const_iterator    constEnd() const  //指向尾部后面假想元素的只读迭代器，Qt风格
注意 *begin() 迭代器是指向真实存在的头部元素，而 *end() 迭代器指向尾部后面不存在的假想元素， *end() 迭代器只能用于越界判断，它不指向任何东西！

链表除了头部、尾部元素，其他中间所有元素都需要用迭代器来操作，在链表中间插入元素的迭代器函数如下：
iterator    insert(iterator before, const T & value)
该函数在 before 指向元素的前面插入 value 元素，返回指向新的 value 元素的迭代器。
插入元素后，要使用新返回的迭代器进行后面的元素遍历。
从链表中间部分删除一个元素或连续多个元素的函数如下：
iterator    erase(iterator pos)    //删除 pos 迭代器指向的元素，返回 pos 下一个元素迭代器，注意返回值可能是指向假想元素的 end()
iterator    erase(iterator begin, iterator end)  //删除从 begin 开始到 end 之间所有元素，但是参数 end 指向的元素不删除，该函数总是返回参数 end
第一个 erase() 函数删除 pos 指向的单个元素，它的返回值可能为指向下一个元素或者 指向末尾假想元素的 end() ，要注意判断返回值。
第二个 erase() 函数删除多个元素，从参数 begin 删除到参数 end，但是 end 指向的元素不删除，这个函数总是返回参数里的 end 迭代器。
链表在大部分情况下都需要用迭代器操作，后面的链表示例也都基于迭代器实现。

（8）容器类型转换函数
链表带有一个成员函数，将自身对象转换为标准库的链表 std::list<T> ：
std::list<T>    toStdList() const
而将标准库链表转为 Qt 链表是通过静态函数实现的，该函数的返回值是新的 Qt 链表：
QLinkedList<T>    fromStdList(const std::list<T> & list)
静态函数的语法类似下面这样：
    std::list<int> sl = {1, 2, 3};
    QLinkedList<int> qll = QLinkedList<int>::fromStdList( sl );

（9）其他内容
链表类附带了两个友元 流操作符函数，用于支持数据流输出、输入：
QDataStream &    operator<<(QDataStream & out, const QLinkedList<T> & list)
QDataStream &    operator>>(QDataStream & in, QLinkedList<T> & list)
这些流操作符函数正常运行的前提是元素类型 T 也能支持流的输入输出，对于 C++ 基本类型、Qt 常见数据类型都是支持数据流输入输出的，如果是自定义类型，那么需要手动编写两个友元 流操作符函数。自定义类型和流操作符函数可以参考上面 9.1.1 节示例。
链表不是在内存里连续存储的类型，是不支持排序的，所以不需要考虑排序支持了。

最后我们梳理一下，如果自定义类型希望能够完美地和 QLinkedList 配合使用，那么需求如下：
① 必须是可赋值类型，需要默认构造函数、复制构造函数、赋值函数 operator=() ；
② 如果希望支持查询函数，需要双等号函数 operator==()；
③ 如果希望支持 QDataStream 数据流输入输出，那么添加友元函数  operator<<() 和 operator>>() 。
第一条是必须实现的函数，后面两条是建议实现的函数。

链表结构通常应用在内存分配、磁盘管理以及其他数学问题上， 我们下面通过一个示例模拟简单的内存分配过程，一个链表保存空闲内存块，另一个链表保存已分配的内存块。 为了使例子尽可能简单，我们只用一个字符串代表一个内存块，字符串文本为“空闲内存”时，代表未分配的空闲内存块； 字符串文本为进程名的时候，代表分配给该进程的内存块。下面开始这个链表示例。
打开 QtCreator，新建一个 Qt Widgets Application 项目，在新建项目的向导里填写：
①项目名称 memlinkedlist，创建路径 D:\QtProjects\ch09，点击下一步；
②套件选择里面选择全部套件，点击下一步；
③基类选择 QWidget，点击下一步；
④项目管理不修改，点击完成。
我们打开 widget.ui 界面文件，按照下图拖入控件：
ui
界面第一行是两个标签，文本分别为“空闲内存块链表”、“已使用内存块链表”；
第二行是两个列表控件，对象名分别为 listWidgetFree、listWidgetUsed， 第一行和第二行使用网格布局（即栅格布局）。
第三行控件分别为：标签“进程名”、单行编辑器 lineEditProcessName、标签“内存块数量”、旋钮编辑框 spinBoxMemCount、
按钮“分配”pushButtonAllocate、按钮“查询”pushButtonFind、按钮“释放”pushButtonFree。
第三行控件使用水平布局，窗口整体使用垂直布局，窗口大小 600*330 。
控件和布局设置好后，我们依次右键点击三个按钮，为每个按钮添加槽函数：
slot
三个按钮的槽函数添加后，我们开始编辑代码，首先是头文件 widget.h 代码：
#ifndef WIDGET_H 
#define WIDGET_H

#include <QWidget>
#include <QLinkedList>

namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT

public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();

private slots:
    void on_pushButtonAllocate_clicked();

    void on_pushButtonFind_clicked();

    void on_pushButtonFree_clicked();

private:
    Ui::Widget *ui;
    //空闲内存块链表，以字符串代表内存块
    QLinkedList<QString> m_memFree;
    //已使用的内存块链表
    QLinkedList<QString> m_memUsed;
    //同步更新图形界面的列表控件
    void updateListWidgets();
};

#endif // WIDGET_H
我们在该文件添加链表 QLinkedList 的头文件引用；在窗口类里面，按钮槽函数是通过右键菜单添加的；
窗口类内部最后添加了两个链表保存空闲内存块和已使用的内存块，并添加了同步更新窗口列表控件的函数。
两个链表对象我们分别使用窗口里两个列表控件显示。
下面分段来看源文件 widget.cpp 的代码，首先是头文件包含、构造函数、析构函数代码：


#include "widget.h"
#include "ui_widget.h"
#include <QDebug>
#include <QMessageBox>

//假定管理的内存块数为10
#define MEM_MAX  10

Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);
    //设置SpinBox上下限，至少分配1块，最多10块内存
    ui->spinBoxMemCount->setRange(1, MEM_MAX);
    //初始化空闲内存链表
    for(int i=0; i<MEM_MAX; i++)
    {
        m_memFree.append( tr("空闲内存") );
    }
    //更新列表控件的显示
    updateListWidgets();
}

Widget::~Widget()
{
    delete ui;
}
我们添加了调试类和消息框类的头文件包含，然后定义了一个常量 MEM_MAX，表示管理内存块的总数，为 10 块。
在构造函数里，我们设置旋钮编辑框 spinBoxMemCount 的取值范围从 1 ~ MEM_MAX。
然后通过循环，添加了 MEM_MAX 数量的空闲内存块到 m_memFree 链表。
构造函数末尾调用 updateListWidgets() 函数，根据链表对象更新列表控件的显示。

接下来我们手动添加更新列表控件显示的函数：
//同步更新图形界面的列表控件
void Widget::updateListWidgets()
{
    //清空列表控件
    ui->listWidgetFree->clear();
    ui->listWidgetUsed->clear();
    //根据空闲内存块链表显示
    QLinkedList<QString>::iterator itFree = m_memFree.begin();
    while( itFree != m_memFree.end() )
    {
        ui->listWidgetFree->addItem( *itFree );
        itFree++; //下一个
    }
    //根据已使用内存块链表显示
    QLinkedList<QString>::iterator itUsed = m_memUsed.begin();
    while( itUsed != m_memUsed.end() )
    {
        ui->listWidgetUsed->addItem( *itUsed );
        itUsed++; //下一个
    }
}
该函数首先清空列表控件所有内容；
然后循环遍历 空闲内存块链表 的元素，将每个元素都添加给列表控件 listWidgetFree 显示；
最后循环遍历 已使用内存块链表 的元素，将每个元素都添加给列表控件 listWidgetUsed 显示。
循环遍历的过程对空链表使用是安全的，因为空链表的 begin() 和 end() 是等同的，首尾相等就不会进入循环体内部执行。

下面来看第一个“分配”按钮的槽函数：
//分配内存块
void Widget::on_pushButtonAllocate_clicked()
{
    //获取进程名
    const QString strName = ui->lineEditProcessName->text().trimmed();
    if(strName.isEmpty())
    {
        QMessageBox::warning(this, tr("分配"), tr("进程名为空，无法分配。"));
        return;
    }
    //进程名不能等同 tr("空闲内存")
    if( tr("空闲内存") == strName )
    {
        QMessageBox::warning(this, tr("分配"), tr("进程名不能等同 空闲内存 。"));
        return;
    }
    //判断需要分配的数量
    int nNeededCount = ui->spinBoxMemCount->value();
    //现有的空闲块数量
    int nCurFree = m_memFree.count();
    //判断是否够用
    if( nNeededCount > nCurFree )//超额了
    {
        QMessageBox::warning(this, tr("分配"), tr("请求数量大于现有空闲数量，请减少请求量或释放其他进程内存。"));
        return;
    }
    //数量充足，可以分配
    for(int i=0; i<nNeededCount; i++)
    {
        QString strCurMem = m_memFree.takeFirst(); //从头部取下内存块，逐一分配
        //分配给进程
        strCurMem = strName;
        //添加到已分配链表
        m_memUsed.append( strCurMem );
    }
    //更新列表控件
    updateListWidgets();
}
该函数首先获取进程名，判断进程名是否为空，如果为空就返回不处理；
如果进程名存在，那么判断进程名是否为“空闲内存”，这个名称我们专门用于空闲内存标识，不能用于进程名，
如果进程名为“空闲内存”就返回不处理，如果是比较正常的进程名，那么继续后面代码。
我们获取旋钮编辑框 spinBoxMemCount 的数值，就是需要分配的数量 nNeededCount ，将该数量与现有空闲块数量 nCurFree 比较，如果申请数量大于空闲块数量，那么提示消息框说明空闲数量不够，返回；
如果申请数量没有超过空闲块数量，那么进入循环：
    从memFree头部卸下一块内存 strCurMem ；
    将 strCurMem 设置为进程名，表示该内存块归 strName 进程拥有；
    将 strCurMem 添加到已使用的内存块链表。
分配了 nNeededCount 块数的内存后结束循环，更新列表控件的显示。

我们使用旋钮编辑框来表示内存块数量的好处就是直接调用 spinBoxMemCount->value() 获取数值，不需要进行字符串到 int 的转换，也不要判断数值是否为 0，因为我们在窗口构造函数里指定了旋钮编辑框的数值范围 1 ~ MEM_MAX。

下面我们来看“查询”按钮的槽函数：
//根据进程名查询该进程拥有的内存块数量
void Widget::on_pushButtonFind_clicked()
{
    //获取进程名
    const QString strName = ui->lineEditProcessName->text().trimmed();
    //判断是否为空
    if( strName.isEmpty() )
    {
        QMessageBox::warning(this, tr("查询"), tr("进程名为空，无法查询。"));
        return;
    }
    //判断是否为 空闲内存查询
    if( tr("空闲内存") == strName )
    {
        QMessageBox::information(this, tr("查询"),
                                 tr("空闲内存数量为：%1").arg( m_memFree.count() ) );
        return;
    }
    //查询进程名拥有的内存块数量
    int nMemCount = m_memUsed.count( strName );
    if( nMemCount < 1 )//判断是否存在
    {
        QMessageBox::warning(this, tr("查询"), tr("没有找到该进程名。"));
        return;
    }
    else
    {
        //显示数量
        QMessageBox::information(this, tr("查询"),
                                 tr("该进程拥有的内存块数量为：%1").arg(nMemCount) );
    }
}
该函数首先获取进程名，如果进程名为空，则不查询，直接返回；
如果进程名存在，那么判断进程名是否为 "空闲内存"，如果为该字符串，那么弹出消息框显示空闲内存块的数量，并返回；
如果进程名不是空闲内存块的字符串，那么调用 m_memUsed.count( strName ) 查询该进程占用的内存块数量 nMemCount ；
如果 nMemCount 数量小于 1，说明没分配内存，该进程不存在，弹出消息框显示没找到该进程名并返回；
如果 nMemCount 数量不小于 1，那么显示弹出显示该进程拥有的内存块数量。

链表的 QLinkedList::​count(const T & value) 函数要求元素类型 T 支持 operator==() 函数，因为字符串 QString 本身支持双等号比较，所以不需要额外代码，直接就能调用该计数函数进行查询。链表其他带参数 value 的查询函数也是一样需要元素类型 T 支持 operator==() 函数。

最后我们来看第三个“释放”按钮的槽函数：
//释放指定进程、指定数量的内存块
void Widget::on_pushButtonFree_clicked()
{
    //获取进程名
    const QString strName = ui->lineEditProcessName->text().trimmed();
    //判断是否为空
    if( strName.isEmpty() )
    {
        QMessageBox::warning(this, tr("释放"), tr("进程名为空，无法释放。"));
        return;
    }
    //获取需要释放的数量
    int nNeedFree = ui->spinBoxMemCount->value();
    //获取该进程拥有的数量
    int nCurOwn = m_memUsed.count( strName );
    if( nCurOwn < 1 )//判断是否存在
    {
        QMessageBox::warning(this, tr("释放"),tr("没有找到该进程名。"));
        return;
    }
    //判断释放数量是否超过了拥有数量
    if( nNeedFree > nCurOwn )
    {
        QMessageBox::warning(this, tr("释放"),
                             tr("该进程只拥有 %1 块内存，不能释放 %2 块。").arg(nCurOwn).arg(nNeedFree) );
        return;
    }
    //正常释放内存
    //记录已释放数目
    int nCurFreed = 0;
    //获取迭代器
    QLinkedList<QString>::iterator itUsed = m_memUsed.begin();
    //循环查找该进程内存块并释放
    while( itUsed != m_memUsed.end() )
    {
        //判断当前元素是否为该进程名
        if( strName == (*itUsed) )
        {
            //释放 1 块内存
            QString strMem = (*itUsed); //链表及其迭代器没有 takeAt 函数，只能复制后删除中间元素
            itUsed = m_memUsed.erase( itUsed ); //删除中间元素
            //erase() 返回值就是指向下一个，不需要++，并且不能再用erase()参数里的数值迭代
            //设置空闲内存名字，添加到空闲内存块链表
            strMem = tr("空闲内存");
            m_memFree.append( strMem );
            //释放数量 +1
            nCurFreed += 1;
            //判断数量是否够了
            if( nCurFreed >= nNeedFree ) break; //停止循环
        }
        else
        {
            itUsed++;   //进程名不对，查找下一个
        }
    }
    //释放完毕，更新列表控件
    updateListWidgets();
}
该函数首先获取进程名，如果为空则不处理，返回；
如果存在进程名，那么获取需要释放的内存块数量 nNeedFree ；
调用 m_memUsed.count( strName ) 查询该进程名实际拥有的内存块数量 nCurOwn ；
如果拥有数 nCurOwn 小于 1，说明没找到该进程名，提示消息框返回；
如果该进程拥有 1 块或以上的内存块，那么比较需要释放的数量 nNeedFree  和实际拥有的数量 nCurOwn ；
如果需要释放的数量大于实际拥有的数量，显然不合理，提示消息框说明不能释放比拥有数多的内存，并返回；
如果需要释放的数量没有超过实际拥有数，那么进入正常的内存释放代码：
定义 nCurFreed 变量表示循环过程中新释放的内存数量，初始化为 0；
获取链表初始迭代器，进入循环：
    如果迭代器 itUsed  指向的元素和指定进程名 strName 相等，那么使用 strMem 保存迭代器指向的元素，
        从链表删除迭代器 itUsed 指向的元素，并保存返回值到 itUsed ，返回值自动指向下一个元素；
        将 strMem 设置为空闲内存块的字符串，表示释放了该内存块；
        将 strMem 添加给空闲内存块链表 memFree；
        nCurFreed 释放数量增加 1；
        判断循环释放的内存块数量 nCurFreed 是否大于或等于需要释放的数量 nNeedFree ，如果达到需要的释放数量就跳出循环。
    如果迭代器 itUsed 指向的元素与指定进程名不相等，那么 itUsed++，处理下一个元素。
当释放完 nNeedFree 数量的内存块后循环结束，更新列表控件的显示。

在使用迭代器时候，需要特别注意 iterator QLinkedList::​erase(iterator pos) 函数，这个函数删除指向的元素后，参数里的 pos 迭代器也会被删除，不能再用参数里的 pos 迭代器，必须使用函数返回值里的迭代器，返回值自动指向下一个元素。当然如果删除的是末尾元素，那么返回值就是 end() 迭代器，指向尾部后不存在的元素。因此在使用迭代器的时候，还需要注意判断迭代器是否为 end() 。
示例代码讲解到这，我们构建运行该示例，然后为 processA 分配 2 块内存，为 processB 分配 3 块内存：
run
当尝试为 processB 释放 9 块内存时，会提示没有那么多内存块可以释放：
run
这说明我们的判断代码运行正常，进程不能释放超过自己拥有数量的内存块。其他功能读者自行测试。
本节的内容到这，最后留一个小练习，读者可以自己动手测试 9.1.2 节  QQueue 类的功能函数。


tip 练习
① 使用 QQueue 类及其入队、出队函数实现 “8.3.5 二叉树示例” 里面按层遍历函数：
 void Widget::LevelsTraversal(QTreeWidgetItem *curItem)


prev
contents
next