[Development] Is QMap Broken

[Robert Steckroth]

[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/20141109/9cf64f4b/attachment.html>