[Interest] QMap operator<() overload.

[K. Frank]

Hello Kai and Torgeir!

Thank you for your insightful comments.

I have some follow-up questions, in line, below.  (And sorry
for moving the discussion away from Qt.)

On Wed, Feb 25, 2015 at 9:45 AM, Torgeir Lilleskog
<torgeir.lilleskog at gmail.com> wrote:
> I like this talk by Chandler Carruth:
> https://www.youtube.com/watch?v=fHNmRkzxHWs
>
> He says something along the lines of "I don't think I've ever seen a problem
> for which std::map is the right data structure"

I have come to prefer std::unordered_map (a hash-map) to
std::map, *except* when I need the entries sorted for some
reason other than look-up (e.g., iterating over them to process
them in sorted order).

I would speculate that std::map (or QMap) would be the right
choice when:

   1)  modifications (insertions / deletions) are mixed with access
   (look-up)

*and*

   2)  there is need to iterate over the collection ins sorted order

Does that sound right?

> QMap is the same type of data structure as std::map.
>
> If your map is small and not expected to scale and you are comfortable with
> the performance of a map for this data it will be OK. Measure if in doubt
> :-)
>
> I think it is really good for programmers to be aware of the cost of using
> data structures like linked lists/maps/hashes.
> The costs/tradeoffs have really changed the last 10+ years or so. What used
> to be a good data structure in the 90s may have absolutely terrible
> performance today. And it is not just some percentage differences, sometimes
> one may see 10x-50x performance difference from a change in data layout
> alone.
>
> Best regards,
> - Torgeir
>
> On Wed, Feb 25, 2015 at 2:19 PM, Koehne Kai <Kai.Koehne at theqtcompany.com>
> wrote:
>>
>> > -----Original Message-----
>> > From: interest-bounces+kai.koehne=theqtcompany.com at qt-project.org
>> > [...]
>> > Could you elaborate a little on your comment, and on for which use cases
>> > QMap might not be the "right" abstraction?
>> >
>> > I've always thought that maps (and hash-maps, e.g. std::unordered_map)
>> > were the right tool when you want to look up a value using a key.  Are
>> > there
>> > pitfalls in this use case?
>>
>> As usual with performance, it highly depends on how you use it ... Anyhow,
>> this was recently discussed on the development at qt-project.org mailing ist:
>>
>> http://permalink.gmane.org/gmane.comp.lib.qt.devel/20044
>>
>> > Or are there other use cases where you often see people using maps when
>> > something else would be more efficient?
>>
>> Citing from the above:
>>
>> " In the vast majority of cases, a sorted vector is much faster, due to
>> locality-of-reference. A RB-tree is optimized for wildly mixing insertions,
>> lookups, and removals. When you can batch updates and separate them from
>> lookups, time-wise, then a sorted vector is usually preferrable."

My take-away from this is that for a static (or semi-static) map,
a binary search into a sorted vector (e.g., of pairs, as you mentioned
in your earlier post) beats a sorted map (e.g., std::map).  But when
modifications (insertions, removals) are mixed with access, the
sorted map is likely to win out.

Would this be your rule of thumb?

I would also assume that a hash-map (e.g., std::unordered_map)
beats a sorted vector, even for access (except when there are a
lot of hash collisions or you need a sorted data structure for other
reasons).

>> If in doubt (and it matters), measure :)
>>
>> Regards
>>
>> Kai


Thanks again.  Food for thought.


K. Frank