[Interest] How to make the QString "10" behind "9" in QMap's key order

Mon Jan 8 17:17:58 CET 2018

Hi,

That is tricky!

Disclaimer: The example below is just for illustration purposes. It's not
complete and will not work! It only gives you the general idea of a
possible solution.

This basically boils down to maintaining more lists.
for instance:

std::vector<QString> source;
std::vector<QCollatorSortKey> keyCache;

You want to sort "keyCache" and update "source" in the same order.
There are a couple of ways of achieving this.

An approach i did years ago did the exact opposite of what i just
suggested. I added a proxy index on top like:
std::vector<int> proxyToKey;

I sorted the proxyToKey mapping like so:
            std::sort(proxyToKey.begin(), proxyToKey.end(), [&](int a, int
b) {
                return m_collator.compare(keyCache[a], keyCache[b]) < 0;
            });

Now your source[proxyToKey[0]] is the first entry.
This however is quite tricky to get right as you have to keep track of your
bookkeeping (aka, update the collator keyCache, source and proxy for every
change).

Another approach i learned later was by means of a so called "zip
iterator". Boost has one but it's not mutable so you can't sort.
There are other zip iterators out there that do work with std::sort and
those are imho the best solution with the least amount of added bookkeeping.

Another even better approach (but that's not possible at the moment) would
be a QCollatorSortKey to also act as QString itself so that your sort key
is also your string. All string data is known in that key, but the layout
is different. That is something for the future i hope.

On Mon, Jan 8, 2018 at 12:34 PM, Carel Combrink <carel.combrink at gmail.com>
wrote:

> Hi Mark,
>
> How would one use QCollatorSortKey for this type of application?
>
> Unfortunately I have to say that the Qt documentation on this class is not
> as descriptive compared to other classes.
>
> Regards,
> Carel
>
> On Mon, Jan 8, 2018 at 11:50 AM, Mark Gaiser <markg85 at gmail.com> wrote:
>
>> On Mon, Jan 8, 2018 at 4:18 AM, jack ma <assangema at gmail.com> wrote:
>>
>>> Thanks all of you, seems that std::sort + QCollator is a good way
>>>
>>> 2018-01-07 18:47 GMT+08:00 Konstantin Tokarev <annulen at yandex.ru>:
>>>
>>>>
>>>>
>>>> > Hi,
>>>> >
>>>> > you need a "lessThan"-function, tailored for your needs. An
>>>> > example from me is this:
>>>> >
>>>> > bool Person::lessThanFamilyFirst(QSharedPointer<Person>
>>>> > p1, QSharedPointer<Person>
>>>> > p2)
>>>> >
>>>> > {
>>>> >
>>>> > return (QString::localeAwareCompare(p1->familyName(),p2->familyName
>>>> ())<0)
>>>> >
>>>> > || (( p1->familyName() == p2->familyName())
>>>> >
>>>> > && (QString::localeAwareCompare(p1->firstName(),p2->firstName())<0));
>>>> >
>>>> > }
>>>> >
>>>> > Now you can pass this as a functor to a sort method like this:
>>>> >
>>>> > std::stable_sort(pupils.begin(), pupils.end(),
>>>> Person::lessThanFamilyFirst);
>>>>
>>>> FWIW, if this is not a list displayed in UI, or other place where
>>>> preserving order of
>>>> equal elements matters, you should consider std::sort
>>>>
>>>> >
>>>> > Please notice, that there are no () when calling the lessThan functor.
>>>>
>>>> Original question was dealing with QMap. While sorted vector-like
>>>> container can replace
>>>> map (there is even convenience wrapper flat_map in Boost, which allows
>>>> to work with
>>>> sorted array just like it was a "true" map), it doesn't always fit,
>>>> e.g. inserts in such
>>>> "flat map" are very expensive.
>>>>
>>>> So, you can just replace QMap with std::map and pass your comparator,
>>>> e.g.
>>>>
>>>> auto comparator = [](const QString &a, const QString &b) -> bool {
>>>>     // Your comparison function here
>>>> };
>>>> std::map<QString, QGraphicsItem *, decltype(comparator)>
>>>> myMap(comparator);
>>>>
>>>> See [1] for more examples.
>>>>
>>>> Yet another approach is to use your own type as a key of QMap instead
>>>> of QString,
>>>> and create desired operator< for it. This has a downside that your
>>>> access to internal
>>>> QString will be more complicated, and you'll have to invent different
>>>> key type each time
>>>> you want to change comparator.
>>>>
>>>> And, last but not least: you probably want to know *how* to write
>>>> comparator for your
>>>> particular sorting order. You can do this with QCollator, see [2].
>>>>
>>>> [1] http://en.cppreference.com/w/cpp/container/map/map
>>>> [2] https://forum.qt.io/topic/68910/natural-sort-using-qcollator/2
>>>>
>>>> >
>>>> > HTH
>>>> > Sebastian
>>>> >
>>>> > Am 07.01.2018 um 09:01 schrieb jack ma:
>>>> >
>>>> >> Hi,
>>>> >>
>>>> >> there is a QMap<QString,QGraphicsItem *> type, then
>>>> >> insert values with：
>>>> >>
>>>> >> type.insert("U1",nullptr),
>>>> >>
>>>> >> type.insert("U2",nullptr),
>>>> >>
>>>> >> …………
>>>> >>
>>>> >> type.insert("U9",nullptr),
>>>> >>
>>>> >> type.insert("U10",nullptr),
>>>> >>
>>>> >> I want get the values follow the order of U1, U2 ... U10，
>>>> >> but the default order is U1, U10 ,……U9
>>>> >>
>>>> >> I know this is a common string sorting problem, but I do
>>>> >> not know how to solve it well.
>>>> >>
>>>> >> Any suggestions are very grateful !
>>>> >>
>>>> >> Thanks.
>>>> >>
>>>> >> _______________________________________________
>>>> >> Interest mailing list
>>>> >> Interest at qt-project.org
>>>> >> http://lists.qt-project.org/mailman/listinfo/interest
>>>> >
>>>> > --
>>>> > http://www.classintouch.de - Tablet-Software für Lehrer
>>>> --
>>>> Regards,
>>>> Konstantin
>>>> _______________________________________________
>>>> Interest mailing list
>>>> Interest at qt-project.org
>>>> http://lists.qt-project.org/mailman/listinfo/interest
>>>>
>>>
>>>
>>> _______________________________________________
>>> Interest mailing list
>>> Interest at qt-project.org
>>> http://lists.qt-project.org/mailman/listinfo/interest
>>>
>>>
>> Hi,
>>
>> You might want to look into std::map[1] as well. It allows setting a
>> compare function, QMap doesn't.
>> Going that route is most likely more efficient as your inserts will be
>> sorted, no need to do std::sort afterwards.
>>
>> You still would have to use QCollator. Note that you can just use
>> QCollator in the compare method which will work just fine, but is not the
>> performant way to go.
>> The most performant way (i know of) is by using QCollatorSortKey[2].
>>
>>
>> [1] http://en.cppreference.com/w/cpp/container/map/map
>> [2] http://doc.qt.io/qt-5/qcollatorsortkey.html
>>
>> _______________________________________________
>> Interest mailing list
>> Interest at qt-project.org
>> http://lists.qt-project.org/mailman/listinfo/interest
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20180108/940aa0c6/attachment.html>