[Development] Is QMap Broken

[Robert Knight]

Hi Robert,

QMap is doing exactly what it is supposed to do. If you want to preserve
insertion order, you need a different data structure - like the one
Mandeep linked to. If the list is not going to grow large, a simple vector
will suffice.

If you want a custom sort order, use STL's equivalent of the map class,
std::map.

Regards,
Rob.



On 10 November 2014 01:20, Robert Steckroth <robertsteckroth at gmail.com>
wrote:

> [SOLVED]: After perusing the qmap.h libraiy I found the reason why QMap was
> keeping a sorted node list.
> There is a few of these calls to qMapLessThanKey which is doing
> variant comparison.
>
> template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2) {
>
>     return key1 < key2;
>
> }
>
>
> Any ways, this kind of simple sorting should be enabled with a flag, E.g.
> QMap<Key, T>::useAlphanumericalSorting(bool)
> Old:
>
>             if (!qMapLessThanKey(n->key, akey))
>
>                 return this->insertMulti(akey, avalue); // ignore hint
>
> New:
>
>             if ( use_alphanumerical_sorting && !qMapLessThanKey(n->key, akey))
>
>                 return this->insertMulti(akey, avalue); // ignore hint
>
>
> Anyways, I simple commented these checks out and all works as expected:
>
>
>         QMap<QString, QString>:: iterator it;
>
>     QMap<QString, QString> m;
>
>     it = m.insertMulti(m.constEnd(), "F", "Me F");
>
>     it = m.insertMulti(it, "B", "Me B");
>
>     it = m.insertMulti(it, "C", "Me C");
>
>     for ( it = m.begin(); it != m.end(); it++) {
>
>         qDebug() << *it;
>
>     }
>
>     qDebug() << "Keys:" << m.keys();
>
>
> Output:
>
>     "Me C"
>
>     "Me B"
>
>     "Me F"
>
>     Keys: ("C", "B", "F")
>
>
> Bug report here -> https://bugreports.qt-project.org/browse/QTBUG-42507
>
>
>
> On Thu, Nov 6, 2014 at 11:51 AM, Mandeep Sandhu <
> mandeepsandhu.chd at gmail.com> wrote:
>
>> On Thu, Nov 6, 2014 at 6:24 AM, Robert Knight <robertknight at gmail.com>
>> wrote:
>>
>>> > Consider the following program, shouldn't the end() iterator place
>>> each key at the end of the newly created QMap. Instead, the keys and
>>> subsequent iterations are sorted (somehow).
>>>
>>> Yes, that's the whole point of a QMap. If you don't care about the order
>>> of elements in a map, you should almost always use a hash
>>> (std::unordered_map or QHash), it is much faster - O(1) vs O(log(n)) for
>>> insertion and lookup.
>>>
>>> If you want a data structure that combines fast lookup and remembers the
>>> order of insertion, that is sometimes referred to as an 'ordered map' and
>>> there are implementations around - typically they glue together a linked
>>> list and a hash map.
>>>
>>
>> Here's an implementation of an 'ordered map' I wrote sometime back. As
>> Robert mentioned, it's implemented using a linked list and a hash (Qt
>> classes).
>>
>> https://github.com/mandeepsandhu/qt-ordered-map
>>
>> HTH,
>> -mandeep
>>
>>
>
>
> --
> <surgemcgee>
>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/development/attachments/20141110/bc919a56/attachment.html>