Is there a map-like tool in QT that can be iterated over inserted index?

Question

From the Qt documentation about QMap::iterator :

Unlike QHash, which stores its items in an arbitrary order, QMap stores its items ordered by key. Items that share the same key (because they were inserted using QMap::insertMulti(), or due to a unite()) will appear consecutively, from the most recently to the least recently inserted value.

What I want is to interate a map by inserted index. For example this map.

const static QMap<QString, int> MEASUREMENT_COLUMNS{{"ID", MY_SQL_BIGINT}, {"logging_id", MY_SQL_INT}, {"calibration_id", MY_SQL_INT}, {"logging_comment", MY_SQL_VARCHAR255}, {"measurement_date_time", MY_SQL_DATETIME}, {"ADC0", MY_SQL_FLOAT},
                                                    {"ADC0", MY_SQL_FLOAT},
                                                    {"ADC1", MY_SQL_FLOAT},
                                                    {"ADC2", MY_SQL_FLOAT},

But the problem is as the documentation says above about QMap and QHashmap. They will not work for be if I want to iterate a map by inserted index.

For example, first ID, then logging_id, then calibration_id etc. So I need to select something else than QMap and QHash.

Question:

Is there a map-like tool in QT that can be iterated over inserted index?

Answer 1

Here's the start of a QHash derivative which provides this functionality. DISCLAIMER: This is not entirely perfected! Not every function / feature of QHash has yet been accounted for. As long as you only use the functions / operator overloads provided here, you'll be fine for sure. If someone wants to keep developing this and repost a truly "finished" class, that would be great!

Note that performance will of course be degraded a bit, and memory consumption will increase, using this vs the natural QHash, but for small data sets that should be negligible.

OrderedHash.h

#ifndef ORDEREDHASH_H
#define ORDEREDHASH_H

#include <QHash>
#include <QVector>
#include <QDataStream>
#include <QDebug>

template<class K, class V>
class OrderedHash : public QHash<K,V>
{
public:
    using QHash<K,V>::QHash;

#ifdef Q_COMPILER_INITIALIZER_LISTS
    OrderedHash( std::initializer_list<std::pair<K, V>> list )
        : QHash<K,V>::QHash()
    { foreach( auto p, list ) insert( std::get<0>(p), std::get<1>(p) ); }
#endif

    // Returns the keys in the order they were inserted.
    // If the ordered keys vector is blatantly out of sync with the hash 
    // (as may occur via the use of QHash functions not accounted for
    // by this override!), this returns UNordered keys, since those are at
    // least accurate.
    QList<K> orderedKeys() const {
        if( QHash<K,V>::size() != orderedKeys_.size() )
        {
            qWarning() << "OrderedHash keys are out of sync!";
            return QHash<K,V>::keys();
        }
        return orderedKeys_.toList();
    }

    // This insert override "appends" to the "end" of the hash. If the key is
    // already present, the entry is "moved" to the new end.
    typename QHash<K,V>::iterator insert( const K &key, const V &value )
    {
        //qDebug() << "OrderedHash insert: " << key << ":" << value;
        orderedKeys_.removeAll( key );
        orderedKeys_.push_back( key );
        return QHash<K,V>::insert( key, value );
    }

    // This additional update function perseveres the "key order" while
    // modifying the value. If the key is not yet present, the entry is
    // appended to the "end" of the hash.
    typename QHash<K,V>::iterator update( const K &key, const V &value )
    {
        if( !QHash<K,V>::contains( key ) ) return insert( key, value );
        return QHash<K,V>::insert( key, value );
    }

    int remove( const K &key )
    {
        orderedKeys_.removeAll( key );
        return QHash<K,V>::remove( key );
    }

    void clear()
    {
        orderedKeys_.clear();
        QHash<K,V>::clear();
    }

private:
    QVector<K> orderedKeys_;
};

// COPIED AND TWEAKED QT SOURCE FOR THESE STREAM OPERATOR OVERLOADS
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QDataStream &operator>>(QDataStream &in, OrderedHash<Key, T> &hash)
{
    QDataStream::Status oldStatus = in.status();
    in.resetStatus();
    hash.clear();

    quint32 n;
    in >> n;

    for (quint32 i = 0; i < n; ++i) {
        if (in.status() != QDataStream::Ok)
            break;

        Key k;
        T t;
        in >> k >> t;
        /* ORGINAL QT SOURCE
        hash.insertMulti(k, t);
        */
        //---------------------------------
        hash.insert(k, t);
        //---------------------------------
    }

    if (in.status() != QDataStream::Ok)
        hash.clear();
    if (oldStatus != QDataStream::Ok)
        in.setStatus(oldStatus);
    return in;
}

template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QDataStream &operator<<(QDataStream &out, const OrderedHash<Key, T>& hash)
{
    out << quint32(hash.size());
    /* ORGINAL QT SOURCE
    typename QHash<Key, T>::ConstIterator it = hash.end();
    typename QHash<Key, T>::ConstIterator begin = hash.begin();
    while (it != begin) {
        --it;
        out << it.key() << it.value();
    }
    */
    //---------------------------------
    const QList<Key> keys( hash.orderedKeys() );
    foreach( auto key, keys ) out << key << hash.value(key);
    //---------------------------------
    return out;
}

#endif // ORDEREDHASH_H

Answer 2

You can use two QVector, or use QVector<QPair<QString, int> > instead.

Answer 3

Not in QT (to my knowledge, at least). Can you use Boost, e.g. boost::multiindex? Another option is to combine map with vector in a class +- like this (this is likely to contain errors; it's supposed to illustrate the general idea, not to be a fully working piece of code):

template<typename K, typename V>
class indexed_map
{
  map<K, V> m_map;
  vector<K> m_insertionOrder;
public:
  void insert(const K& k, const V& v)
  {
    m_map.insert(k,v);
    m_insertionOrder.push_back(k);
  }

  V byKey(const K& k) const {return m_map.at(k)};
  V byOrder(size_t n) const {return m_map.at(m_insertionOrder.at(n));}
};

Of course you'll have to write some boilerplate (ok, lots of it in fact), iterators might be also tricky.