当我们谈论编程中的数据结构时,顺序容器是不可忽视的一个重要概念。顺序容器是一种能够按照元素添加的顺序来存储和检索数据的数据结构。它们提供了简单而直观的方式来组织和管理数据,为程序员提供了灵活性和性能的平衡。
Qt 中提供了丰富的容器类,用于方便地管理和操作数据。这些容器类涵盖了各种不同的用途,从简单的动态数组到复杂的映射和集合。本章我们将主要学习顺序容器,顺序容器是一组强大而灵活的数据结构,用于按照元素添加的顺序存储和管理数据。Qt提供了多种顺序容器,每种都具有独特的特性,这些容器包括向量、列表、队列、栈等,每种都有特定的适用场景。
当然了STL标准模板中也存在这些容器,Qt 的容器类与标准模板库(STL)中的容器类有些相似,但也有一些不同之处。以下是 Qt 容器类相对于STL的一些特点和优势:
- 可自动共享数据:
- Qt 容器类使用了引用计数的技术,能够自动共享数据,减少内存占用。当一个容器对象复制另一个容器对象时,它们可以共享底层数据而不是进行深拷贝。
- 隐式共享:
- Qt 容器类通过隐式共享实现了高效的数据共享。只有在发生写操作时,才会执行深拷贝,从而减少不必要的开销。
- 可跨线程使用:
- Qt 容器类支持在多线程环境中安全使用,通过显式共享(
QExplicitlySharedDataPointer
)和不显式共享两种方式,方便在多线程应用中进行数据处理。
- 提供了一些额外的功能:
- Qt 的容器类在标准容器的基础上提供了一些额外的功能,例如对 Unicode 字符串的特殊支持(
QString
),以及一些便捷的成员函数,使得容器的使用更为方便。
- 内存管理:
- Qt 容器类负责管理其元素的内存,使得内存的分配和释放不需要额外的手动管理,减轻了开发者的负担。
- 直观的 API 设计:
- Qt 的容器类 API 设计考虑了 Qt 的整体框架,采用了一致而直观的命名规范,使得使用者更容易理解和记忆容器类的接口。
- 与其他 Qt 类的集成:
- Qt 容器类能够无缝地与其他 Qt 类和框架集成,例如与信号和槽机制一起使用,使得在 Qt 应用程序中的开发更为方便。
在某些特定的场景和需求下,STL 的容器类可能更适合使用。然而,在使用 Qt 框架的情况下,Qt 容器类通常能够提供更好的集成和一些额外的特性。选择使用哪种容器类取决于具体的项目需求和开发者的偏好。
1.1 QList 动态数组容器
QList
是 Qt 中常用的动态数组类,它提供了动态大小的数组,支持在列表的两端和中间快速插入、删除元素。适用于需要动态管理元素集合的场景,使得对列表的操作更加简便。
以下是 QList
的一些常用函数:
函数 | 功能 |
| 构造函数,创建一个空的 |
| 复制构造函数,创建一个与给定列表相同的 |
| 在列表末尾添加一个元素。 |
| 在列表开头添加一个元素。 |
| 替换列表中索引为 |
| 移除列表中索引为 |
| 移除列表中第一个匹配给定值的元素。 |
| 移除列表中所有匹配给定值的元素。 |
| 移除并返回列表中索引为 |
| 移除并返回列表中的第一个元素。 |
| 移除并返回列表中的最后一个元素。 |
| 在列表中索引为 |
| 判断列表中是否包含给定值。 |
| 统计列表中匹配给定值的元素数量。 |
| 返回给定值在列表中的第一个匹配项的索引,从指定位置 |
| 返回给定值在列表中的最后一个匹配项的索引,从指定位置 |
| 判断列表是否为空。 |
| 返回列表中元素的数量。 |
| 清空列表,移除所有元素。 |
| 重载赋值运算符,将一个列表赋值给另一个列表。 |
| 重载相等运算符,判断两个列表是否相等。 |
| 重载不等运算符,判断两个列表是否不相等。 |
以上是 QList
的一些常用函数及其功能,这些函数允许开发者对列表进行添加、删除、替换、查找等操作,以满足不同场景的需求。
1.1.1 主要特点
- 动态数组:
QList
是动态大小的数组,可以根据需要自动调整大小。 - 泛型:
QList
是泛型容器,可以存储任意类型的数据。 - 可变大小: 列表的大小可以动态改变,元素的插入和删除操作都很高效。
- 双向迭代器:
QList
提供了双向迭代器,可以方便地从前往后或从后往前遍历列表。
1.1.2 如何使用
如下所示的代码中我定义了两个QList
容器,分别是StringPtrA
和StringPtrB
通过使用不同的容器操作函数对其进行简单的增加插入替换删除和移动操作,如下代码所示;
#include <QCoreApplication>
#include <iostream>
#include <QList>
void Display(QList<QString> &ptr)
{
std::cout << "-----------------------------" << std::endl;
for(qint32 x=0;x<ptr.count();x++)
{
// std::cout << ptr[x].toStdString().data() << std::endl;
std::cout << (ptr.at(x)).toStdString().data() << std::endl;
}
std::cout << std::endl;
}
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QList<QString> StringPtrA;
QList<QString> StringPtrB;
// 添加三个成员
StringPtrA.append("admin");
StringPtrA.append("guest");
StringPtrA.append("lyshark");
Display(StringPtrA);
// 在首部插入hanter
StringPtrA.prepend("hanter");
Display(StringPtrA);
// 在第0的位置插入lucy
StringPtrA.insert(0,QString("lucy"));
Display(StringPtrA);
// 替换原来的admin为全拼
StringPtrA.replace(1,"Administrator");
Display(StringPtrA);
// 删除第0个元素
StringPtrA.removeAt(0);
Display(StringPtrA);
// 删除首部和尾部
StringPtrA.removeFirst();
StringPtrA.removeLast();
// 移动两个变量
StringPtrA.move(0,1);
Display(StringPtrA);
// 将两个list容器对调交换
StringPtrB = {"youtube","facebook"};
StringPtrA.swap(StringPtrB);
Display(StringPtrA);
return a.exec();
}
上述代码我们只是对字符串进行了链表管理,其实Qt中支持管理结构体,首先要定义一个特有的结构体MyStruct
当结构体被赋值后就可以像数组一样灵活的操作数据,当然在使用结构体时我们传入的应该是QList<MyStruct>
结构体的名字,在遍历时可以有三种方式,第一种时传统的循环依次输出元素,这里我们说说使用QListIterator
和QMutableListIterator
来输出元素的区别。
#include <QCoreApplication>
#include <iostream>
#include <QList>
#include <QListIterator>
#include <QMutableListIterator>
struct MyStruct
{
qint32 uid;
QString uname;
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QList<MyStruct> ptr;
MyStruct str_ptr;
str_ptr.uid = 1001;
str_ptr.uname = "admin";
ptr.append(str_ptr);
str_ptr.uid = 1002;
str_ptr.uname = "guest";
ptr.append(str_ptr);
// 使用传统方式遍历数据
for(qint32 x=0;x<ptr.count();x++)
{
std::cout << ptr.at(x).uid << std::endl;
std::cout << ptr[x].uname.toStdString().data() << std::endl;
}
// 使用只读迭代器遍历
QListIterator<MyStruct> x(ptr);
while(x.hasNext())
{
// peeknext读取下一个节点,但不影响指针变化
std::cout << x.peekNext().uid << std::endl;
std::cout << (x.peekNext().uname).toStdString().data() << std::endl;
// 最后将x指针指向下一个数据
x.next();
}
// 使用读写迭代器:如果uid=1002则将guest改为lyshark
QMutableListIterator<MyStruct> y(ptr);
while(y.hasNext())
{
// y.peekNext().uid = 9999;
if(y.peekNext().uid == 1002)
{
y.peekNext().uname = "lyshark";
}
y.next();
}
return a.exec();
}
其实QListIterator
和 QMutableListIterator
都是用于遍历 QList
容器的迭代器类。区别是QListIterator
是一个只读迭代器,用于遍历 QList
容器中的元素。它提供了一个方便的方式来访问容器中的元素,支持前向和后向遍历。而QMutableListIterator
是一个可变迭代器,除了支持读取元素外,还允许修改 QList
中的元素。它提供了修改元素的接口,使得在遍历的同时可以对容器进行修改。
QListIterator 主要函数和特点
-
QListIterator(const QList<T> &list)
: 构造函数,用于初始化迭代器并关联到给定的QList
。 -
hasNext() const
: 检查是否有下一个元素。 -
next()
: 返回当前元素并将迭代器移动到下一个元素。 -
peekNext() const
: 返回当前元素但不移动迭代器。 -
toFront()
: 将迭代器移动到列表的第一个元素。 -
toBack()
: 将迭代器移动到列表的最后一个元素。
QMutableListIterator 主要函数和特点
-
QMutableListIterator(QList<T> &list)
: 构造函数,用于初始化可变迭代器并关联到给定的QList
。 -
hasNext() const
: 检查是否有下一个元素。 -
next()
: 返回当前元素并将迭代器移动到下一个元素。 -
peekNext() const
: 返回当前元素但不移动迭代器。 -
toFront()
: 将迭代器移动到列表的第一个元素。 -
toBack()
: 将迭代器移动到列表的最后一个元素。 -
remove()
: 移除迭代器当前位置的元素。 -
setValue(const T &value)
: 将迭代器当前位置的元素设置为给定值。
这两个迭代器类提供了方便而灵活的方式来遍历和操作 QList
中的元素,根据需要选择合适的迭代器。
1.2 QLinkeList 双向链表容器
QLinkedList
是 Qt 中的双向链表实现,与 QList
不同,它不是基于数组的动态容器,而是基于链表的数据结构。QLinkedList
提供了链表特有的灵活性,适用于需要在任意位置高效插入和删除元素的场景。在一些访问元素的场景中,由于链表的非连续存储特性,可能比数组容器的访问效率稍低。选择使用 QLinkedList
还是其他容器,取决于具体的使用需求。
以下是 QLinkedList
的一些常用函数:
函数 | 功能 |
| 构造函数,创建一个空的 |
| 复制构造函数,创建一个与给定链表相同的 |
| 在链表末尾添加一个元素。 |
| 在链表开头添加一个元素。 |
| 替换链表中给定迭代器位置的元素为给定的值。 |
| 移除链表中所有匹配给定值的元素。 |
| 移除链表中第一个匹配给定值的元素。 |
| 移除链表中索引为 |
| 移除并返回链表中索引为 |
| 移除并返回链表中的第一个元素。 |
| 移除并返回链表中的最后一个元素。 |
| 在链表中给定迭代器位置插入一个元素。 |
| 判断链表中是否包含给定值。 |
| 统计链表中匹配给定值的元素数量。 |
| 返回给定值在链表中的第一个匹配项的索引。 |
| 返回给定值在链表中的最后一个匹配项的索引。 |
| 判断链表是否为空。 |
| 返回链表中元素的数量。 |
| 清空链表,移除所有元素。 |
| 返回指向链表第一个元素的迭代器。 |
| 返回指向链表最后一个元素之后的迭代器。 |
QLinkedList
提供了与 QList
类似的操作,但由于其基于双向链表实现,特别适合于需要频繁插入和删除操作的场景。在使用上,QLinkedList
提供了一些额外的函数,如 replace
、insert
等,可以更方便地操作链表中的元素。
1.2.1 主要特点
- 双向链表:
QLinkedList
使用双向链表结构,每个节点存储一个元素以及指向前后节点的指针,支持高效的插入和删除操作。 - 泛型:
QLinkedList
是泛型容器,可以存储任意类型的数据。 - 可变大小: 链表的大小可以动态改变,元素的插入和删除操作在任意位置都很高效。
- 双向迭代器:
QLinkedList
提供了双向迭代器,可以方便地从前往后或从后往前遍历链表。
1.2.2 如何使用
QLinkeList其实就是动态链表结构,数据的存储非连续,访问时无法直接使用下标定位,只能通过迭代器迭代寻找,这是其与QList
的本质区别,其参数定义与QList
基本一致,在使用上并没有本质上的区别。
#include <QCoreApplication>
#include <iostream>
#include <QLinkedList>
#include <QLinkedListIterator>
#include <QMutableLinkedListIterator>
struct MyStruct
{
qint32 uid;
QString uname;
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QLinkedList<MyStruct> ptr;
MyStruct str_ptr;
str_ptr.uid = 1001;
str_ptr.uname = "admin";
ptr.append(str_ptr);
str_ptr.uid = 1002;
str_ptr.uname = "guest";
ptr.append(str_ptr);
// 使用只读迭代器遍历: 从前向后遍历
QLinkedListIterator<MyStruct> x(ptr);
while(x.hasNext())
{
std::cout << x.peekNext().uid << std::endl;
x.next();
}
// 使用只读迭代器遍历: 从后向前遍历
for(x.toBack();x.hasPrevious();x.previous())
{
std::cout << x.peekPrevious().uid << std::endl;
}
// 使用STL风格的迭代器遍历
QLinkedList<MyStruct>::iterator y;
for(y=ptr.begin();y!=ptr.end();++y)
{
std::cout << (*y).uid << std::endl;
}
// STL风格的只读迭代器
QLinkedList<MyStruct>::const_iterator z;
for(z=ptr.constBegin();z!=ptr.constEnd();++z)
{
std::cout <<((*z).uname).toStdString().data()<< std::endl;
}
// 使用读写迭代器: 动态生成列表,每次对二取余
QLinkedList<int> Number = {1,2,3,4,5,6,7,8,9,10};
QMutableLinkedListIterator<int> item(Number);
// --> 从前向后输出一次
for(item.toFront();item.hasNext();item.next())
std::cout << item.peekNext() << std::endl;
// --> 将指针移动到最后然后判断
for(item.toBack();item.hasPrevious();)
{
if(item.previous() % 2==0)
item.remove();
else
item.setValue(item.peekNext() * 10);
}
// --> 最后输出出相加后的结果
for(item.toFront();item.hasNext();)
{
std::cout << item.peekNext() << std::endl;
item.next();
}
return a.exec();
}
1.3 QVector 动态数组容器
QVector
是Qt中的动态数组类,它提供了动态大小的数组,并在内部使用指针数组进行存储。QVector
是一个灵活的动态数组类,适用于需要动态管理元素集合的场景,同时由于其连续存储的特性,在访问元素的效率上相对较高。
以下是 QVector
的一些常用函数:
函数 | 功能 |
| 构造函数,创建一个空的 |
| 构造函数,创建一个包含 |
| 构造函数,创建一个包含 |
| 复制构造函数,创建一个与给定向量相同的 |
| 在向量末尾添加一个元素。 |
| 在向量开头添加一个元素。 |
| 替换向量中索引为 |
| 移除向量中索引为 |
| 移除向量中第一个匹配给定值的元素。 |
| 移除向量中所有匹配给定值的元素。 |
| 移除并返回向量中索引为 |
| 移除并返回向量中的第一个元素。 |
| 移除并返回向量中的最后一个元素。 |
| 在向量中索引为 |
| 使用给定值填充向量,如果指定了 |
| 判断向量中是否包含给定值。 |
| 统计向量中匹配给定值的元素数量。 |
| 返回给定值在向量中的第一个匹配项的索引,从指定位置 |
| 返回给定值在向量中的最后一个匹配项的索引,从指定位置 |
| 判断向量是否为空。 |
| 返回向量中元素的数量。 |
| 清空向量,移除所有元素。 |
| 更改向量的大小,如果新大小大于当前大小,会用默认值填充。 |
| 预留空间以容纳指定数量的元素,可提高插入操作的性能。 |
| 释放向量占用的多余空间。 |
QVector
提供了类似于 QList
的操作,但由于其底层使用连续存储,因此在某些情况下性能更高。开发者可以根据具体的需求选择适合的容器。
1.3.1 主要特点
- 动态数组:
QVector
是动态大小的数组,可以根据需要自动调整大小。 - 连续存储: 与
QLinkedList
不同,QVector
的元素在内存中是连续存储的,这有助于提高访问效率。 - 泛型:
QVector
是泛型容器,可以存储任意类型的数据。 - 可变大小: 数组的大小可以动态改变,元素的插入和删除操作在末尾和中间都很高效。
1.3.2 如何使用
QVector
在内存中存储连续的数据,类似于 C++ 中的 std::vector
。该容器的使用与Qlist
完全一致,但读取性能要比Qlist
更高,但在插入时速度最慢。
#include <QCoreApplication>
#include <iostream>
#include <QVector>
#include <QVectorIterator>
#include <QMutableVectorIterator>
struct MyStruct
{
qint32 uid;
QString uname;
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QVector<MyStruct> ptr;
MyStruct str_ptr;
str_ptr.uid = 1001;
str_ptr.uname = "admin";
ptr.append(str_ptr);
str_ptr.uid = 1002;
str_ptr.uname = "guest";
ptr.append(str_ptr);
// 使用传统方式遍历
for(qint32 x=0;x<ptr.count();x++)
{
std::cout << ptr.at(x).uid << std::endl;
std::cout << ptr[x].uname.toStdString().data() << std::endl;
}
// 使用只读迭代器遍历: C++ STL写法
QVector<MyStruct>::const_iterator item;
for(item = ptr.begin();item != ptr.end(); ++item)
{
std::cout << (*item).uid << std::endl;
std::cout << (*item).uname.toStdString().data() << std::endl;
}
// 使用读写迭代器修改: C++ STL写法
QVector<MyStruct>::iterator write_item;
for(write_item = ptr.begin();write_item !=ptr.end();++write_item)
{
if((*write_item).uid == 1001)
{
(*write_item).uname = "xxxx";
}
std::cout << (*write_item).uid << std::endl;
std::cout << (*write_item).uname.toStdString().data() << std::endl;
}
return a.exec();
}
1.3.3 与QList的比较
- 相似性:
QVector
和QList
在接口上非常相似,可以使用相同的函数进行元素的访问、插入和删除等操作。 - 性能差异: 由于
QVector
的元素在内存中是连续存储的,因此在顺序访问时,QVector
的性能通常比QList
更高。但在中间插入元素时,QVector
的性能可能较差,因为需要移动插入点之后的所有元素。 - 适用场景:
QVector
适用于需要频繁进行顺序访问而较少进行中间插入操作的场景,例如对大量数据进行顺序处理的情况。
1.4 QStack 栈容器
QStack
是 Qt 中的栈容器,它提供了栈(LIFO)的数据结构。该容器用于需要满足后进先出规则的场景,例如在算法实现中,或者在某些数据处理过程中需要临时存储和恢复状态。
以下是 QStack
的一些常用函数:
函数 | 功能 |
| 构造函数,创建一个空的 |
| 复制构造函数,创建一个与给定栈相同的 |
| 在栈顶压入一个元素。 |
| 弹出栈顶的元素。 |
| 返回栈顶的元素,不弹出。 |
| 判断栈是否为空。 |
| 返回栈中元素的数量。 |
| 清空栈,移除所有元素。 |
| 重载赋值运算符,将一个栈赋值给另一个栈。 |
| 重载相等运算符,判断两个栈是否相等。 |
| 重载不等运算符,判断两个栈是否不相等。 |
QStack
是一个后进先出(LIFO)的栈,提供了压栈、弹栈等基本操作。栈是一种常见的数据结构,可以用于需要遵循后进先出原则的场景,例如递归函数调用时的存储函数调用信息等。
1.4.1 主要特点
- 栈数据结构:
QStack
是栈的实现,它遵循后进先出(Last In, First Out,LIFO)的原则。 - 泛型:
QStack
是泛型容器,可以存储任意类型的数据。 - 封闭性:
QStack
提供的接口限制在栈顶进行插入和删除操作,不允许在中间或底部插入或删除元素。
1.4.2 如何使用
#include <QCoreApplication>
#include <iostream>
#include <QString>
#include <QStack>
#include <QQueue>
struct MyStruct
{
qint32 uid;
QString uname;
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
// 定义并弹出QString类型数据
QStack<QString> stack;
stack.push("admin");
stack.push("guest");
std::cout << (stack.top()).toStdString().data()<<std::endl;
while(!stack.isEmpty())
{
std::cout << (stack.pop()).toStdString().data() << std::endl;
}
// 定义并弹出一个结构类型数据
QStack<MyStruct> struct_stack;
MyStruct ptr;
ptr.uid = 1001;
ptr.uname = "admin";
struct_stack.push(ptr);
ptr.uid = 1002;
ptr.uname = "guest";
struct_stack.push(ptr);
// 分别弹出数据并输出
while(!struct_stack.isEmpty())
{
MyStruct ref;
ref = struct_stack.pop();
std::cout << "uid = " << ref.uid << std::endl;
std::cout << "uname = " << ref.uname.toStdString().data() << std::endl;
}
return a.exec();
}
1.5 QQueue 队列容器
QQueue
是 Qt 中的队列容器,它提供了队列(FIFO)的数据结构。QQueue
可以用于需要满足先进先出规则的场景,例如在任务调度、数据缓冲等应用中。
以下是 QQueue
的一些常用函数:
函数 | 功能 |
| 构造函数,创建一个空的 |
| 复制构造函数,创建一个与给定队列相同的 |
| 在队列尾部插入一个元素。 |
| 移除队列头部的元素。 |
| 返回队列头部的元素,不移除。 |
| 判断队列是否为空。 |
| 返回队列中元素的数量。 |
| 清空队列,移除所有元素。 |
| 重载赋值运算符,将一个队列赋值给另一个队列。 |
| 重载相等运算符,判断两个队列是否相等。 |
| 重载不等运算符,判断两个队列是否不相等。 |
QQueue
是一个先进先出(FIFO)的队列,提供了入队、出队等基本操作。队列常用于需要按照先后顺序处理元素的场景,例如任务队列、消息队列等。
1.5.1 主要特点
- 队列数据结构:
QQueue
是队列的实现,它遵循先进先出(First In, First Out,FIFO)的原则。 - 泛型:
QQueue
是泛型容器,可以存储任意类型的数据。 - 封闭性:
QQueue
提供的接口限制在队列的前端进行插入,队列的后端进行删除操作。
1.5.2 如何使用
队列就是先进后出,在使用上与普通容器保持一致,只是队列的可用方法会更少一些。
#include <QCoreApplication>
#include <iostream>
#include <QString>
#include <QQueue>
struct MyStruct
{
qint32 uid;
QString uname;
};
int main(int argc, char *argv[])
{
QCoreApplication a(argc, argv);
QQueue<MyStruct> ptr;
MyStruct queue_ptr;
// 实现对结构体的入队
queue_ptr.uid = 1001;
queue_ptr.uname = "admin";
ptr.enqueue(queue_ptr);
queue_ptr.uid = 1002;
queue_ptr.uname = "guest";
ptr.enqueue(queue_ptr);
// 实现对结构体的出队
while(!ptr.isEmpty())
{
MyStruct ref;
ref = ptr.dequeue();
std::cout << "uid = " << ref.uid << std::endl;
std::cout << "uname = " << ref.uname.toStdString().data() << std::endl;
}
return a.exec();
}