[Interest] Set manipulation in Qt 6

[Giuseppe D'Angelo]

Hi,

Il 20/06/20 08:44, Vadim Peretokin ha scritto:
> QMap<QString, QList<QPointF>> customLines;
> QMap<QString, QColor> customLinesColor;
> // ...
> 
> #if (QT_VERSION >= QT_VERSION_CHECK(5, 14, 0))
>      auto customLineKeys = customLines.keys();
>      QSet<QString> missingKeys{customLineKeys.begin(), 
> customLineKeys.end()};
>      if (!customLinesColor.isEmpty()) {
>          auto customLinesColorKeys = customLinesColor.keys();
>          QSet<QString> 
> customLinesColorKeysSet{customLinesColorKeys.begin(), 
> customLinesColorKeys.end()};
>          missingKeys.subtract(customLinesColorKeysSet);
>      }
> #else
>      QSet<QString> 
> missingKeys{customLines.keys().toSet().subtract(customLinesColor.keys().toSet())};
> #endif


With my hat of the guy going around and deprecating toSet() and friends: 
the rationale for these deprecations is the terrible code that those 
methods encourage, and the


Let's just look at this last line. This is, at a minimum:

> customLines.keys()

- 1 temporary allocation + #LINES temporary copies (builds a QList 
copying all the keys from the map)

> .toSet()

- #LINES+1 allocations + #LINES copies (builds a QHash copying all the 
values from the list)

> customLinesColor.keys().toSet()

- 1+1+#COLOR temporary allocations, 2*#COLOR temporary copies (same, but 
this is completely temporary)


Totals:

- 4 + #LINES + #COLOR allocations
- 2 * #LINES + 2 * #COLOR copies
- 3 + #LINES + 2 * #COLOR destructions at a minimum
- 3 + #COLOR deallocations at a minimum

(Luckily the keys are QStrings, and not something where the copy and 
destruction would be even more expensive, or QList would cause further 
allocations).



There are much better alternatives you can aim for with minimal effort.
Assuming that at the end you do want exactly a QSet, you can port it in 
the slightly more verbose but still straightforward:

> QSet<QString> customLinesKeys(customLines.keyBegin(), customLines.keyEnd());
> {
> QSet<QString> customLinesColorKeys(customLinesColor.keyBegin(), customLinesColor.keyEnd());
> customLinesKeys.subtract(customLinesColorKeys);
> }

Which saves buildings the temporary QLists. Totals now:

- 2 + #LINES + #COLOR allocations
- #LINES + #COLOR copies
- 1 + #COLOR destructions at a minimum
- 1 + #COLOR deallocations at a minimum



I think it's possible to do even better -- a QMap, by definition, keeps 
its keys in order. Which means now you can use e.g. std::set_difference.

Unfortunately we can't use a QSet as an output -- let's sketch with a 
std::unordered_set for the moment:

> std::unordered_set<QString> result;
> std::set_difference(customLines.keyBegin(), customLines.keyEnd(),
>                     customLinesColor.keyBegin(), customLinesColor.keyEnd(),
>                     std::inserter(result, result.end()));

Cost of this one:

- 1 + (#LINES / #COLOR) allocations
- (#LINES / #COLOR) copies

AKA optimal.

With a QSet, the cost and the code would be identical. The problem is 
that we can't write _that_ code as QSet is not usable with std::inserter 
(QSet lacks a suitable insert() method). Then again, do you _need_ a 
QSet or would a QList output suffice?

(Which brings me to my second crusade, try stop encouraging the usage of 
Qt containers, as their API is full of holes and doesn't play nice with 
algorithms or ranges. But it's enough for this mail.)

HTH,
-- 
Giuseppe D'Angelo | giuseppe.dangelo at kdab.com | Senior Software Engineer
KDAB (France) S.A.S., a KDAB Group company
Tel. France +33 (0)4 90 84 08 53, http://www.kdab.com
KDAB - The Qt, C++ and OpenGL Experts

-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 4329 bytes
Desc: Firma crittografica S/MIME
URL: <http://lists.qt-project.org/pipermail/interest/attachments/20200620/f1e91780/attachment.bin>