Heterogeneous comparisons in binary search [was: A small holiday gift, I hope]

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-12-24 13:01:58

In an article posted yesterday, I began a discussion of how to write
the standard requirements for lower_bound, upper_bound, equal_range,
and binary_search so that heterogeneous comparisons are
possible. Today I'm going to try to supply proposed replacement
standard text.

First, though, I made (at least) one small mistake yesterday: when
outlining the requirements for a unary comparison function, I wrote
that it must "induce a partition" on the elements of the sequence. I
think that was technically wrong. After all, nearly any unary function
returning bool induces a partition over its arguments. I should have
said this instead:

   The sequence must be partitioned with respect to the unary comparison
   function.

This is consistent with the standard's notion of a sequence being sorted
with respect to a strict weak ordering.

Also, I notice that the standard contains a requirement on the element
type which was surely unintended: even when using an explicit
comparison function, the standard requires that the elements be
LessThanComparable. This means, for example, that the element types
can't be pointers, even if you use std::less<T> as the comparison
object.

Now for the proposed changes to standard text:

---
Change 25.3 [lib.alg.sorting] paragraph 3 from:
  3 For all algorithms that take Compare, there is a version that uses
  operator< instead. That is, comp(*i, *j) != false defaults to *i <
  *j != false. For the algorithms to work correctly, comp has to
  induce a strict weak ordering on the values.
to:
  3 For all algorithms that take Compare, there is a version that uses
  operator< instead. That is, comp(*i, *j) != false defaults to *i <
  *j != false. For algorithms not described in lib.alg.binary.search
  (25.3.3) to work correctly, comp has to induce a strict weak
  ordering on the values.
---
Add the following paragraph after 25.3 [lib.alg.sorting] paragraph 5:
  6 A sequence [begin, end) is partitioned with respect to an expression
f(e) if
  there exists a non-negative integer n such that for all
  0 <= i < distance(begin, end), f(j) is true if and only if j < n.
---
Change 25.3.3 [lib.alg.binary.search] paragraph 1 from:
  -1- All of the algorithms in this section are versions of binary
   search and assume that the sequence being searched is in order
   according to the implied or explicit comparison function. They work
   on non-random access iterators minimizing the number of
   comparisons, which will be logarithmic for all types of
   iterators. They are especially appropriate for random access
   iterators, because these algorithms do a logarithmic number of
   steps through the data structure. For non-random access iterators
   they execute a linear number of steps.
to:
   -1- All of the algorithms in this section are versions of binary
    search and assume that the sequence being searched is partitioned
    with respect to an expression formed by binding the search key to
    an argument of the implied or explicit comparison function. They
    work on non-random access iterators minimizing the number of
    comparisons, which will be logarithmic for all types of
    iterators. They are especially appropriate for random access
    iterators, because these algorithms do a logarithmic number of
    steps through the data structure. For non-random access iterators
    they execute a linear number of steps.
---
Change 25.3.3.1 [lib.lower.bound] paragraph 1 from:
   -1- Requires: Type T is LessThanComparable
    (lib.lessthancomparable).
to:
   -1- Requires: The elements e of [first, last) are partitioned with
   respect to the expression e < value or comp(e, value)
---
Remove 25.3.3.1 [lib.lower.bound] paragraph 2:
   -2- Effects: Finds the first position into which value can be
    inserted without violating the ordering.
---
Change 25.3.3.2 [lib.upper.bound] paragraph 1 from:
  -1- Requires: Type T is LessThanComparable (lib.lessthancomparable).
to:
   -1- Requires: The elements e of [first, last) are partitioned with
   respect to the expression !(value < e) or !comp(value, e)
---
Remove 25.3.3.2 [lib.upper.bound] paragraph 2:
   -2- Effects: Finds the furthermost position into which value can be
    inserted without violating the ordering.
---
Change 25.3.3.3 [lib.equal.range] paragraph 1 from:
   -1- Requires: Type T is LessThanComparable
    (lib.lessthancomparable).
to:
   -1- Requires: The elements e of [first, last) are partitioned with
   respect to the expressions e < value and !(value < e) or
   comp(e, value) and !comp(value, e).
Optionally add the following to the end of the proposed text above,
which allows library implementors to make a small optimization at the
cost of slightly complexifying the standard text. The idea is that we
want to ensure that the partition point which defines the upper_bound
is no earlier in the sequence than the partion point which defines the
lower_bound, so that the implementor do one of the searches over a
subrange:
   Also, for all elements e of [first, last), e < value implies
   !(value < e) or comp(e, value) implies !comp(value, e)
Note also that if we don't add the above, the result of equal_range()
might be an invalid range.
---
Change 25.3.3.3 [lib.equal.range] paragraph 2 from:
   -2- Effects: Finds the largest subrange [i, j) such that the value
    can be inserted at any iterator k in it without violating the
    ordering. k satisfies the corresponding conditions: !(*k < value)
    && !(value < *k) or comp(*k, value) == false && comp(value, *k) ==
    false.
to:
   -2- Returns:
         make_pair(lower_bound(first, last, value),
                   upper_bound(first, last, value))
       or
         make_pair(lower_bound(first, last, value, comp),
                   upper_bound(first, last, value, comp))
Note that the original text did not say whether the first element of
the return value was the beginning or end of the range, or something
else altogether. The proposed text is both more precise and general
enough to accomodate heterogeneous comparisons.
---
Change 25.3.3.3 [lib.binary.search] paragraph 1 from:
   -1- Requires: Type T is LessThanComparable
    (lib.lessthancomparable).
to:
   -1- Requires: The elements e of [first, last) are partitioned with
   respect to the expressions e < value and !(value < e) or comp(e,
   value) and !comp(value, e). Also, for all elements e of [first,
   last), e < value implies !(value < e) or comp(e, value) implies
   !comp(value, e)
---
Well, that's it for changes to the standard text. Still to come: the
proposed boost binary search library.
Happy Holidays,
Dave