Details
-
Suggestion
-
Resolution: Unresolved
-
P2: Important
-
None
-
None
-
None
-
13
-
Foundation PM Prioritized
Description
Q(Multi)Hash, unlike all other Qt containers, and unlike std::unordered_map, lacks the erase(it, it) function ("range-erase"). Currently, the only option to erase a range of items in QHash is to loop over erase(it), which, however, has algorithmic complexity problems (see QTBUG-103328), so esp. when the range consists of equivalent elements (think QMultiHash), the erase(it) loop is necessarily quadratic.
Workaround: use removeIf() and hope for QTBUG-103328 to be fixed.
Acceptance criteria: The following test passes and has complexity linear in N = std::distance(b, e):
QMultiHash<int, QString> h = { {0, "zero"}, {1, "one"}, {1, "uno"}, {2, "two"}, }; auto b = h.find(1); auto e = std::next(b); auto it = h.erase(b, e); static_assert(std::is_same_v<decltype(it), QMultiHash<int, QString>::iterator>); QVERIFY(it == h.end() || it.key() == 0 || it.key() == 2); QVERIFY(it == h.end() || it.value() == "zero" || it.value() == "two"); QMultiHash<int, QString> res = {{0, "zero"), {2, "two"}}; QCOMPARE_EQ(h, res);
Attachments
Issue Links
- is cloned by
-
QTBUG-106180 QSet is missing range-erase()
-
- Open
-
- relates to
-
QTBUG-106176 Q(Multi)Hash is missing equal_range()
-
- Open
-