Uploaded image for project: 'Swift'
  1. Swift
  2. SR-890

Sequence.minmax() and Collection.minmaxIndices()

    XMLWordPrintable

    Details

      Description

      It is sometimes useful to find both minimum and maximum elements at the same time. Currently, the library provides separate `min()` and `max()` methods for this. Running both methods requires 2n comparisons.

      It is possible to implement a combined operation, `minmax()`, that would only require 1.5n comparisons.

      Just like with min() and max(), we need both operations that return elements, and operations that return indices.

      The idea behind the algorithm is to compare pairs of elements at positions 2i and 2i+1. This produces two sequences of elements:

      (a) elements that are equal or greater than some element in the sequence,

      (b) elements that compare less than some element in the sequence.

      The minimum element is among elements in (b), the maximum element is among elements in (a).

      minmax_element() in libc++ is a good example.

        Attachments

          Issue Links

            Activity

              People

              Assignee:
              valeriyvan Valeriy Van
              Reporter:
              gribozavr Dmitri Gribenko
              Votes:
              0 Vote for this issue
              Watchers:
              6 Start watching this issue

                Dates

                Created:
                Updated: