Uploaded image for project: 'Qt'
  1. Qt
  2. QTBUG-103721

Use q20::is_sorted to statically assert that static arrays are sorted

    XMLWordPrintable

Details

    • Task
    • Resolution: Unresolved
    • P3: Somewhat important
    • None
    • None
    • Core: Other, Other
    • 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:
          1. a code comment to that effect
          2. std::lower_bound, std::upper_bound, std::equal_range being called on it
          3. std::binary_search being called on it
          4. 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

      Attachments

        Issue Links

          For Gerrit Dashboard: QTBUG-103721
          # Subject Branch Project Status CR V

          Activity

            People

              cnn Qt Core & Network
              mmutz Marc Mutz
              Vladimir Minenko Vladimir Minenko
              Alex Blasche Alex Blasche
              Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

                Created:
                Updated:

                Gerrit Reviews

                  There are no open Gerrit changes