C++实现有序Map（类似Java的OrderedMap 按照插入顺序），增删改查复杂度为O（lgN）

#ifndef MYORDEREDMAP_H #define MYORDEREDMAP_H #include <QLinkedList> #include <QMap> #include <QVariant> class MyOrderedMap { public: class ValueIterator { public: QVariant v; QLinkedList<QVariant>::iterator it; }; MyOrderedMap() { } void insert(const QVariant k, const QVariant &v) { if (m_map.contains(k)) { m_map[k].v = v; } else { ValueIterator vi; vi.v = v; vi.it = m_keyLL.insert(m_keyLL.end(), k); m_map.insert(k, vi); } } void remove(const QVariant &k) { if (m_map.contains(k)) { ValueIterator &VI = m_map[k]; m_keyLL.erase(VI.it); m_map.remove(k); } } QVariant value(const QVariant &k) const { QVariant v; if (m_map.contains(k)) { v = m_map.value(k).v; } return v; } void clear() { m_keyLL.clear(); m_map.clear(); } int size() const { return m_map.size(); } const QLinkedList<QVariant> &keys() const { return m_keyLL; } private: QMap<QVariant, ValueIterator> m_map; QLinkedList<QVariant> m_keyLL; }; #endif // MYORDEREDMAP_H

说明：

1、为了保证有序，结合双向链表，使得增删改查的复杂度都不超过O（lgN），原来QMap的增删改查的复杂度也是O（lgN）

2、只是实现了思路，key和value都是使用QVariant类，实用性不是很好。更好的应该使用模板来实现template<class K, class V>，只是用模板的时候ValueIterator中的it不知道怎么写（语法问题，编译不过~_~），就先偷懒使用QVariant了。

3、测试代码如下：

#include <QCoreApplication> #include <myorderedmap.h> #include <QDebug> #include <QElapsedTimer> #include <QTime> #include <qmath.h> void test1(int n) { int k = 0, v = 0; qsrand(QTime::currentTime().msec()); MyOrderedMap oMap; QElapsedTimer timer; for (int i = 0; i < n; ++i) { v = qrand(); k = i; //qrand()*qrand(); oMap.insert(k, v); //qDebug() << k; } timer.start(); oMap.value(k); qint64 queryTime = timer.nsecsElapsed(); timer.restart(); for (int i = 0; i < n; ++i) { if (i % 2 == 0) { oMap.remove(i); } } qint64 removeTime = timer.nsecsElapsed() / (n/2); qDebug() << n << oMap.size() << oMap.keys().size() << " " << queryTime << removeTime; //qDebug() << QList<QVariant>::fromStdList(oMap.keys().toStdList()); } int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); // MyOrderedMap oMap; // oMap.insert(123, 456); // oMap.insert(111, 222); // oMap.insert("abc", "def"); // oMap.insert("xxxxxxxx", "yyyyyyyyyy"); // oMap.insert(110, 119); // qDebug() << oMap.value(111); // oMap.remove(QVariant(123)); // qDebug() << oMap.size(); // qDebug() << QList<QVariant>::fromStdList(oMap.keys().toStdList()); // oMap.clear(); for (int i = 1; i <= 20; i++) { test1(100 * qPow(2, i)); } //test1(10000); return a.exec(); }