Qt Ordered Map

A Qt based implementation of an ordered map.

An ordered map stores key-value pairs according to the insertion order of the keys. It supports a sub-set of the QMap API, as certain APIs like QMap::insertMulti() etc do not make sense for an ordered map.

OrderedMap stores keys according to their insertion order, so if you add a key that already exists, it's order is changed to being the last key in the map. Eg:

#include "orderedmap.h"
...
OrderedMap<int, int> om;
om.insert(1,1);
om.insert(2,2);
// Order of keys is [1, 2]

om.insert(1,1);
// Order of keys is [2, 1]

Here, another example that shows a map of QString > int:

OrderedMap<QString, int> map;

// put some values
map["z-key"] = 10;
map["a-key"] = 20;
map["c-key"] = 15;

// edit some values
map["a-key"] = 21;

foreach (int value, map.values()) {
    qDebug() << value;
}

// [Output will be]:
// > 10
// > 21
// > 15

foreach (QString key, map.keys()) {
    qDebug() << key << ">" << map[key];
}

// [Output will be]:
// > "z-key" > 10
// > "a-key" > 21
// > "c-key" > 15

Requirements

• The key type for the OrderedMap must provide operator==() and a global hash function called qHash().

Limitations

• OrderedMap currently does NOT support implicit sharing like other Qt containers. A deep-copy will be made whenever copying the container with either copy constructor or assignment operator.

Performance

OrderedMap uses a hashtable (QHash) for storing the data and a map (QLinkedList) for storing the order of the keys.

	Key Lookup		Insertion		Removal
	Average	Worst Case	Average	Worst Case	Average	Worst Case
OrderedMap	Amortized O(1)	O(n)	Amortized O(1)	O(n)	Amortized O(1)	O(n)