
Boost : 
From: David Abrahams (abrahams_at_[hidden])
Date: 20001224 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 nonnegative 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 nonrandom 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 nonrandom 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 nonrandom 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 nonrandom 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk