Suggested patch to QMap

[ComServant]

Hey, I added what I believe to be a useful function to to the QMap template class (code and rationale below).
I have difficulty with SVN/git/etc (never learned them! It's on my todo list, but so are alot of other things), so I can't submit the patch myself.

I wrote the patch because I needed it in my own code, but since I already wrote it, I figure it'd be good to make it available to others - but since it's not a major patch, it's not worth derailing my projects for three days struggling to learn the Ins and Outs of source control systems, and another day or two struggling to learn the culture and structure and rules of qtproject.org's submission guidelines.

Since I assume alot of users here are probably active submitters to the Qt source, I'll present the small code change below, and let you guys figure out whether it's worth including or not.

I've tested it, and it works - but I might've made a mistake somewhere.

================================================== ========

Problem: When inserting elements into QMap that have identical keys, insertMulti() inserts the most recently added element before the earlier added elements. This is not always desired and in-fact is counter-intuitive way of doing things, though it's mentioned in the documentation.

Documentation:
However, you can store multiple values per key by using insertMulti() instead of insert() (or using the convenience subclass QMultiMap).
...
The items that share the same key are available from most recently to least recently inserted.

Example:

QMap<int, QString> map;
const int THE_SAME_KEY = 15;
 
map.insertMulti(THE_SAME_KEY, "Inserted first");
map.insertMulti(THE_SAME_KEY, "Inserted second");
map.insertMulti(THE_SAME_KEY, "Inserted third");
 
qDebug() << map;

QMap<int, QString> map;
const int THE_SAME_KEY = 15;

map.insertMulti(THE_SAME_KEY, "Inserted first");
map.insertMulti(THE_SAME_KEY, "Inserted second");
map.insertMulti(THE_SAME_KEY, "Inserted third");

qDebug() << map;

To copy to clipboard, switch view to plain text mode 

Output:
QMap((15, "Inserted third")(15, "Inserted second")(15, "Inserted first"))

The order of the elements, when sharing the same key, is the reverse of the order of insertion.
There are occasions, though admittingly rare, where you wish to preserve the order of insertion of elements that share the same key. Actually, this really should be the default of how QMap works, because it's the most intuitive solution (in my opinion). However, for the sake of not breaking anything that current relies on this side-effect of QMap, I suggest the following solution: adding a insertMultiAfter() function that does preserve the order of insertion when elements share the same key. It's very easy to add to QMap itself, but unfortunately cannot be added from outside of QMap (otherwise I'd just do it in my code instead of patching QMap).

================================================== ========

Code:

I added this function. It should work identical to insertMulti, with the exception
//that if two or more elements share the same key, the earlier they were added, the earlier they appear in the map.
//(With the normal insertMulti() function, the most recently added element gets inserted before earlier elements that
//share the same value).
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMultiAfter(const Key &akey,
                                                                            const T &avalue)
{
    detach();
 
    QMapData::Node *update[QMapData::LastLevel + 1];
    mutableFindLastNode(update, akey);                              //<--- The only line that changed.
    return iterator(node_create(d, update, akey, avalue));
}
 
I added this function, to return the *last* node with the matching key,
//instead of the *first* node with the matching key.
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindLastNode(QMapData::Node *aupdate[],
                                                                   const Key &akey) const
{
    QMapData::Node *cur = e;
    QMapData::Node *next = e;
 
    for (int i = d->topLevel; i >= 0; i--) {
        while ((next = cur->forward[i]) != e && qMapLessThanOrEqualKey<Key>(concrete(next)->key, akey))      //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
            cur = next;
        aupdate[i] = cur;
    }
    if (next != e && !qMapLessThanOrEqualKey<Key>(akey, concrete(next)->key)) {      //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
        return next;
    } else {
        return e;
    }
}
 
//This function is added as an alternative to 'qMapLessThanKey' (Likewise, the overloaded pointer versions of these functions have a 'LessThanOrEqual' alternative).
template <class Key> inline bool qMapLessThanOrEqualKey(const Key &key1, const Key &key2)
{
    return key1 <= key2;        //<------------- The only line that changed.
}

I added this function. It should work identical to insertMulti, with the exception
//that if two or more elements share the same key, the earlier they were added, the earlier they appear in the map.
//(With the normal insertMulti() function, the most recently added element gets inserted before earlier elements that
//share the same value).
template <class Key, class T>
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMultiAfter(const Key &akey,
                                                                            const T &avalue)
{
    detach();

    QMapData::Node *update[QMapData::LastLevel + 1];
    mutableFindLastNode(update, akey);                              //<--- The only line that changed.
    return iterator(node_create(d, update, akey, avalue));
}

I added this function, to return the *last* node with the matching key,
//instead of the *first* node with the matching key.
template <class Key, class T>
Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindLastNode(QMapData::Node *aupdate[],
                                                                   const Key &akey) const
{
    QMapData::Node *cur = e;
    QMapData::Node *next = e;

    for (int i = d->topLevel; i >= 0; i--) {
        while ((next = cur->forward[i]) != e && qMapLessThanOrEqualKey<Key>(concrete(next)->key, akey))      //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
            cur = next;
        aupdate[i] = cur;
    }
    if (next != e && !qMapLessThanOrEqualKey<Key>(akey, concrete(next)->key)) {      //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
        return next;
    } else {
        return e;
    }
}

//This function is added as an alternative to 'qMapLessThanKey' (Likewise, the overloaded pointer versions of these functions have a 'LessThanOrEqual' alternative).
template <class Key> inline bool qMapLessThanOrEqualKey(const Key &key1, const Key &key2)
{
    return key1 <= key2;        //<------------- The only line that changed.
}

To copy to clipboard, switch view to plain text mode 

*knocks the dust off my hands*

There. I've done my part - I got it working, tested it, and presented it to the public. I don't care if it gets added or not, that's up to you guys, but since I found a need for it, I figure I'd present it as a suggestion.

[ChrisW67]

It is not going to do much here. If nobody shoots down the suggestion here than you should lodge a "Suggestion" issue in the Qt Bug Tracker and hope a sympathetic reader takes up the cause.