Details
-
Task
-
Resolution: Unresolved
-
P3: Somewhat important
-
None
-
None
-
None
Description
Several of our static arrays are supposed to be sorted (because, e.g., we're runningĀ lower_bound() orĀ binary_search() on them). At least the entries array has, in the past, violated sorted-ness (due to a null entry at the end).
Traditionally, this sort of thing would have been checked by an assert at runtime, but C++20 gave us constexpr algorithms, so we can now static_assert(is_sorted(~~~)), too, so we should use it to catch such mistakes earl(y|ier).
Acceptance criteria:
- q20::is_sorted, a backport of C++20's is_sorted is merged
- just the classic version, not the std::ranges one
- any assert(is_sorted) on static const arrays have been changed to static_assert(q20::is_sorted))
- all static const arrays which are supposed to be sorted got a static is_sorted check added
- indications that an array is supposed to be sorted include:
- a code comment to that effect
- std::lower_bound, std::upper_bound, std::equal_range being called on it
- std::binary_search being called on it
- a hand-written binary search is used on the data
- try to rewrite these to use lower_bound() instead, implementing binary search correctly is surprisingly hard
- indications that an array is supposed to be sorted include:
Attachments
Issue Links
- relates to
-
QTBUG-109233 qOffsetStringArray(): allow iteration
-
- Open
-
Gerrit Reviews
For Gerrit Dashboard: QTBUG-103721 | ||||||
---|---|---|---|---|---|---|
# | Subject | Branch | Project | Status | CR | V |
412087,3 | Short live q20::is_sorted{,_until}! | dev | qt/qtbase | Status: MERGED | +2 | 0 |
422285,4 | QLocale/Win: statically assert that is_sorted(windows_to_iso_list) | dev | qt/qtbase | Status: MERGED | +2 | 0 |
422286,3 | QLocale/Win: replace hand-written binary search with a call to lower_bound() | dev | qt/qtbase | Status: MERGED | +2 | 0 |