Qt ：Ordered Map
#ifndef ORDEREDMAP_H
#define ORDEREDMAP_H
#include <QtGlobal>
#include <QHash>
#include <QLinkedList>
#include <QList>
#include <QPair>
#ifdef Q_COMPILER_INITIALIZER_LISTS
#include <initializer_list>
#endif
template <typename Key> inline bool oMHashEqualToKey(const Key &key1, const Key &key2)
{
// Key type must provide '==' operator
return key1 == key2;
}
template <typename Ptr> inline bool oMHashEqualToKey(Ptr *key1, Ptr *key2)
{
Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
return quintptr(key1) == quintptr(key2);
}
template <typename Ptr> inline bool oMHashEqualToKey(const Ptr *key1, const Ptr *key2)
{
Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
return quintptr(key1) == quintptr(key2);
}
template <typename Key, typename Value>
class OrderedMap
{
class OMHash;
typedef typename QLinkedList<Key>::iterator QllIterator;
typedef typename QLinkedList<Key>::const_iterator QllConstIterator;
typedef QPair<Value, QllIterator> OMHashValue;
typedef typename OMHash::iterator OMHashIterator;
typedef typename OMHash::const_iterator OMHashConstIterator;
public:
class iterator;
class const_iterator;
typedef typename OrderedMap<Key, Value>::iterator Iterator;
typedef typename OrderedMap<Key, Value>::const_iterator ConstIterator;
explicit OrderedMap();
#ifdef Q_COMPILER_INITIALIZER_LISTS
OrderedMap(std::initializer_list<std::pair<Key,Value> > list);
#endif
OrderedMap(const OrderedMap<Key, Value>& other);
#if (QT_VERSION >= 0x050200)
OrderedMap(OrderedMap<Key, Value>&& other);
#endif
void clear();
bool contains(const Key &key) const;
int count() const;
bool empty() const;
iterator insert(const Key &key, const Value &value);
bool isEmpty() const;
QList<Key> keys() const;
int remove(const Key &key);
int size() const;
Value take(const Key &key);
Value value(const Key &key) const;
Value value(const Key &key, const Value &defaultValue) const;
QList<Value> values() const;
OrderedMap<Key, Value> & operator=(const OrderedMap<Key, Value>& other);
#if (QT_VERSION >= 0x050200)
OrderedMap<Key, Value> & operator=(OrderedMap<Key, Value>&& other);
#endif
bool operator==(const OrderedMap<Key, Value> &other) const;
bool operator!=(const OrderedMap<Key, Value> &other) const;
Value& operator[](const Key &key);
const Value operator[](const Key &key) const;
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
iterator erase(iterator pos);
iterator find(const Key& key);
const_iterator find(const Key& key) const;
class const_iterator;
class iterator
{
QllIterator qllIter;
OMHash *data;
friend class const_iterator;
friend class OrderedMap;
public:
iterator() : data(NULL) {}
iterator(const QllIterator &qllIter, OMHash *data) :
qllIter(qllIter), data(data) {}
const Key & key() const
{
return *qllIter;
}
Value & value() const
{
OMHashIterator hit = data->find(*qllIter);
OMHashValue &pair = hit.value();
return pair.first;
}
Value & operator*() const
{
return value();
}
iterator operator+(int i) const
{
QllIterator q = qllIter;
q += i;
return iterator(q, data);
}
iterator operator-(int i) const
{
return operator +(- i);
}
iterator& operator+=(int i)
{
qllIter += i;
return *this;
}
iterator& operator-=(int i)
{
qllIter -= i;
return *this;
}
iterator& operator++()
{
++qllIter;
return *this;
}
iterator operator++(int)
{
iterator it = *this;
qllIter++;
return it;
}
iterator operator--()
{
--qllIter;
return *this;
}
iterator operator--(int)
{
iterator it = *this;
qllIter--;
return it;
}
bool operator ==(const iterator &other) const
{
return (qllIter == other.qllIter);
}
bool operator !=(const iterator &other) const
{
return (qllIter != other.qllIter);
}
};
class const_iterator
{
QllConstIterator qllConstIter;
const OMHash *data;
public:
const_iterator() : data(NULL) {}
const_iterator(const iterator &i) :
qllConstIter(i.qllIter), data(i.data) {}
const_iterator(const QllConstIterator &qllConstIter, const OMHash* data) :
qllConstIter(qllConstIter), data(data) {}
const Key & key() const
{
return *qllConstIter;
}
const Value & value() const
{
OMHashConstIterator hit = data->find(*qllConstIter);
const OMHashValue &pair = hit.value();
return pair.first;
}
const Value & operator*() const
{
return value();
}
const_iterator operator+(int i) const
{
QllConstIterator q = qllConstIter;
q += i;
return const_iterator(q, data);
}
const_iterator operator-(int i) const
{
return operator +(- i);
}
const_iterator& operator+=(int i)
{
qllConstIter += i;
return *this;
}
const_iterator& operator-=(int i)
{
qllConstIter -= i;
return *this;
}
const_iterator& operator++()
{
++qllConstIter;
return *this;
}
const_iterator operator++(int)
{
const_iterator it = *this;
qllConstIter++;
return it;
}
const_iterator operator--()
{
--qllConstIter;
return *this;
}
const_iterator operator--(int)
{
const_iterator it = *this;
qllConstIter--;
return it;
}
bool operator ==(const const_iterator &other) const
{
return (qllConstIter == other.qllConstIter);
}
bool operator !=(const const_iterator &other) const
{
return (qllConstIter != other.qllConstIter);
}
};
private:
class OMHash : public QHash<Key, OMHashValue >
{
public:
bool operator == (const OMHash &other) const
{
if (size() != other.size()) {
return false;
}
if (QHash<Key, OMHashValue >::operator ==(other)) {
return true;
}
typename QHash<Key, OMHashValue >::const_iterator it1 = this->constBegin();
typename QHash<Key, OMHashValue >::const_iterator it2 = other.constBegin();
while(it1 != this->end()) {
OMHashValue v1 = it1.value();
OMHashValue v2 = it2.value();
if ((v1.first != v2.first) || !oMHashEqualToKey<Key>(it1.key(), it2.key())) {
return false;
}
++it1;
++it2;
}
return true;
}
};
private:
void copy(const OrderedMap<Key, Value> &other);
OMHash data;
QLinkedList<Key> insertOrder;
};
template <typename Key, typename Value>
OrderedMap<Key, Value>::OrderedMap() {}
#ifdef Q_COMPILER_INITIALIZER_LISTS
template<typename Key, typename Value>
OrderedMap<Key, Value>::OrderedMap(std::initializer_list<std::pair<Key, Value> > list)
{
typedef typename std::initializer_list<std::pair<Key,Value> >::const_iterator const_initlist_iter;
for (const_initlist_iter it = list.begin(); it != list.end(); ++it)
insert(it->first, it->second);
}
#endif
template <typename Key, typename Value>
OrderedMap<Key, Value>::OrderedMap(const OrderedMap<Key, Value>& other)
{
copy(other);
}
#if (QT_VERSION >= 0x050200)
template <typename Key, typename Value>
OrderedMap<Key, Value>::OrderedMap(OrderedMap<Key, Value>&& other)
{
data = std::move(other.data);
insertOrder = std::move(other.insertOrder);
}
#endif
template <typename Key, typename Value>
void OrderedMap<Key, Value>::clear()
{
data.clear();
insertOrder.clear();
}
template <typename Key, typename Value>
bool OrderedMap<Key, Value>::contains(const Key &key) const
{
return data.contains(key);
}
template <typename Key, typename Value>
int OrderedMap<Key, Value>::count() const
{
return data.count();
}
template <typename Key, typename Value>
bool OrderedMap<Key, Value>::empty() const
{
return data.empty();
}
template <typename Key, typename Value>
typename OrderedMap<Key, Value>::iterator OrderedMap<Key, Value>::insert(const Key &key, const Value &value)
{
OMHashIterator it = data.find(key);
if (it == data.end()) {
// New key
QllIterator ioIter = insertOrder.insert(insertOrder.end(), key);
OMHashValue pair(value, ioIter);
data.insert(key, pair);
return iterator(ioIter