Skip to content

mandeepsandhu/qt-ordered-map

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

32 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Qt Ordered Map

Github Issues Build Status Average time to resolve an issue

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)

About

A Qt based implementation of an ordered map

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published