深入浅出Qt容器类：QList、QMap、QHash等常用容器对比分析
上一篇对比了各个使用场景和特点，为了更好地理解不同容器的性能差异，通过一些常见的操作来比较它们的表现。以下是一些基本操作的时间复杂度：
| 操作 | QList<T> | QVector<T> | QLinkedList<T> | QSet<T> | QMap<Key, T> | QMultiMap<Key, T> | QHash<Key, T> | QMultiHash<Key, T> | QStack<T> | QQueue<T> |
|---|---|---|---|---|---|---|---|---|---|---|
| 访问 | O(1) | O(1) | O(n) | N/A | O(log n) | O(log n) | N/A | N/A | O(1) | O(1) |
| 插入（头部） | O(n) | O(n) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(n) | O(n) |
| 插入（尾部） | O(1) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) | O(1) |
| 删除（头部） | O(n) | O(n) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(n) | O(n) |
| 删除（尾部） | O(1) | O(1) | O(1) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(1) | O(1) |
| 查找 | O(n) | O(n) | O(n) | O(1) | O(log n) | O(log n) | O(1) | O(1) | O(n) | O(n) |
性能测试案例
下面是一个简单的性能测试示例，展示了不同容器在插入大量元素时的表现。这个测试程序会测量每个容器在插入20000,000个整数和查询所需的时间。
#include <QList>
#include <QVector>
#include <QLinkedList>
#include <QSet>
#include <QMap>
#include <QMultiMap>
#include <QHash>
#include <QMultiHash>
#include <QStack>
#include <QQueue>
#include <QElapsedTimer>
#include <QDebug>template<typename Container>
void testContainerInsertionAndLookup(const QString& containerName, void (*insertFunction)(Container&, int), bool (*lookupFunction)(const Container&, int)) {Container data;QElapsedTimer timer;// 测试插入操作timer.start();for (int i = 0; i < 20000000; ++i) {insertFunction(data, i);}qint64 insertionTime = timer.elapsed();// 测试查找操作timer.restart();lookupFunction(data, 5000000);qint64 lookupTime = timer.elapsed();qDebug() << containerName << "Insert Time:" << insertionTime << "ms."<< "Lookup Time:" << lookupTime << "ms";
}void insertIntoQList(QList<int>& list, int value) {list.append(value);
}bool lookupInQList(const QList<int>& list, int value) {return list.contains(value);
}void insertIntoQVector(QVector<int>& vector, int value) {vector.append(value);
}bool lookupInQVector(const QVector<int>& vector, int value) {return vector.contains(value);
}void insertIntoQLinkedList(QLinkedList<int>& linkedList, int value) {linkedList.append(value);
}bool lookupInQLinkedList(const QLinkedList<int>& linkedList, int value) {return linkedList.contains(value);
}void insertIntoQSet(QSet<int>& set, int value) {set.insert(value);
}bool lookupInQSet(const QSet<int>& set, int value) {return set.contains(value);
}void insertIntoQMap(QMap<int, int>& map, int value) {map[value] = value;
}bool lookupInQMap(const QMap<int, int>& map, int value) {return map.contains(value);
}void insertIntoQMultiMap(QMultiMap<int, int>& multiMap, int value) {multiMap.insert(value, value);
}bool lookupInQMultiMap(const QMultiMap<int, int>& multiMap, int value) {return multiMap.contains(value);
}void insertIntoQHash(QHash<int, int>& hash, int value) {hash[value] = value;
}bool lookupInQHash(const QHash<int, int>& hash, int value) {return hash.contains(value);
}void insertIntoQMultiHash(QMultiHash<int, int>& multiHash, int value) {multiHash.insert(value, value);
}bool lookupInQMultiHash(const QMultiHash<int, int>& multiHash, int value) {return multiHash.contains(value);
}void insertIntoQStack(QStack<int>& stack, int value) {stack.push(value);
}bool lookupInQStack(const QStack<int>& stack, int value) {return stack.contains(value);
}void insertIntoQQueue(QQueue<int>& queue, int value) {queue.enqueue(value);
}bool lookupInQQueue(const QQueue<int>& queue, int value) {return queue.contains(value);
}int main() {testContainerInsertionAndLookup("QList", insertIntoQList, lookupInQList);testContainerInsertionAndLookup("QVector", insertIntoQVector, lookupInQVector);testContainerInsertionAndLookup("QLinkedList", insertIntoQLinkedList, lookupInQLinkedList);testContainerInsertionAndLookup("QSet", insertIntoQSet, lookupInQSet);testContainerInsertionAndLookup("QMap", insertIntoQMap, lookupInQMap);testContainerInsertionAndLookup("QMultiMap", insertIntoQMultiMap, lookupInQMultiMap);testContainerInsertionAndLookup("QHash", insertIntoQHash, lookupInQHash);testContainerInsertionAndLookup("QMultiHash", insertIntoQMultiHash, lookupInQMultiHash);testContainerInsertionAndLookup("QStack", insertIntoQStack, lookupInQStack);testContainerInsertionAndLookup("QQueue", insertIntoQQueue, lookupInQQueue);return 0;
}测试结果(X86,Qt5.14)
以上是我的测试结果，仅供参考，若有疑问欢迎在评论区讨论。