Results 1 to 2 of 2

Thread: Suggested patch to QMap

  1. #1
    Join Date
    Apr 2009
    Thanked 1 Time in 1 Post
    Qt products

    Default Suggested patch to QMap

    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'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.
    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.
    Qt Code:
    1. QMap<int, QString> map;
    2. const int THE_SAME_KEY = 15;
    4. map.insertMulti(THE_SAME_KEY, "Inserted first");
    5. map.insertMulti(THE_SAME_KEY, "Inserted second");
    6. map.insertMulti(THE_SAME_KEY, "Inserted third");
    8. qDebug() << map;
    To copy to clipboard, switch view to plain text mode 

    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).

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

    Qt Code:
    1. I added this function. It should work identical to insertMulti, with the exception
    2. //that if two or more elements share the same key, the earlier they were added, the earlier they appear in the map.
    3. //(With the normal insertMulti() function, the most recently added element gets inserted before earlier elements that
    4. //share the same value).
    5. template <class Key, class T>
    6. Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMultiAfter(const Key &akey,
    7. const T &avalue)
    8. {
    9. detach();
    11. QMapData::Node *update[QMapData::LastLevel + 1];
    12. mutableFindLastNode(update, akey); //<--- The only line that changed.
    13. return iterator(node_create(d, update, akey, avalue));
    14. }
    16. I added this function, to return the *last* node with the matching key,
    17. //instead of the *first* node with the matching key.
    18. template <class Key, class T>
    19. Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindLastNode(QMapData::Node *aupdate[],
    20. const Key &akey) const
    21. {
    22. QMapData::Node *cur = e;
    23. QMapData::Node *next = e;
    25. for (int i = d->topLevel; i >= 0; i--) {
    26. while ((next = cur->forward[i]) != e && qMapLessThanOrEqualKey<Key>(concrete(next)->key, akey)) //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
    27. cur = next;
    28. aupdate[i] = cur;
    29. }
    30. if (next != e && !qMapLessThanOrEqualKey<Key>(akey, concrete(next)->key)) { //<------------- 'qMapLessThanOrEqualKey()' is called instead of qMapLessThanKey()
    31. return next;
    32. } else {
    33. return e;
    34. }
    35. }
    37. //This function is added as an alternative to 'qMapLessThanKey' (Likewise, the overloaded pointer versions of these functions have a 'LessThanOrEqual' alternative).
    38. template <class Key> inline bool qMapLessThanOrEqualKey(const Key &key1, const Key &key2)
    39. {
    40. return key1 <= key2; //<------------- The only line that changed.
    41. }
    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.

  2. #2
    Join Date
    Mar 2009
    Brisbane, Australia
    Thanked 1,587 Times in 1,516 Posts
    Qt products
    Qt4 Qt5
    Unix/X11 Windows
    Wiki edits

    Default Re: Suggested patch to QMap

    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.

Similar Threads

  1. Suggested Error Handling
    By Max Yaffe in forum Qt Programming
    Replies: 6
    Last Post: 15th July 2014, 17:29
  2. Patch Multi Axes Zoom
    By oddytz1989 in forum Qwt
    Replies: 4
    Last Post: 1st February 2012, 11:17
  3. Replies: 2
    Last Post: 18th November 2010, 08:01
  4. Replies: 5
    Last Post: 31st March 2009, 14:55


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
Digia, Qt and their respective logos are trademarks of Digia Plc in Finland and/or other countries worldwide.