QHash::removeIf() is needlessly inefficient (in particular, not O(N))

TL;DR: For QHash, erase-loops are not quite O(1), and may be linear, so removeIf() is not quite linear, and maybe quadratic. Users expect this to operate at the theoretical optimum complexity, which is O(N). Programs may run unacceptably slow if they hit this issue (worst-case is quadratic).

Analysis

• QHash::removeIf() calls QtPrivate::associative_erase_if
• associative_erase_if does the usual if (cond) it = c.erase(it); else ++it
• QHash::erase is not O(1), because it needs to rotate elements with equivalent keys[1] into the hole left by the removed elements. The set of elements with equivalent keys may be the whole container. If the keys of all elements are all equivalent, this operation is O(N)
• therefore the erase-loop is not O(N), and could be O(N²).

[1] keys that index into the same initial slot

I believe some OA hash tables use a second marker for such deleted elements to avoid the reshuffling so they can provide an O(1) erase, but QHash doesn't implement that.

BC/SC solution:

• specialize associative_erase_if for QHash to call QHash::removeIf()
• make QHash::removeIf use knowledge of the internal data structure to avoid erase() from shuffling single elements when adjacent elements are removed.

This makes removeIf() O(N) again in all cases. We can then document that erase-loops are inefficient for QHash and suggest to use uniform container erasure (free {[erase_if()}} function) for the task (or removeIf()).

This is for an unshared container. For a shared container, we still have the huge pessimisation of first detach()ing and then removing elements from the copy, instead of making a new QHash with just the elements we want (→ QTBUG-103329)