Movatterモバイル変換

This page is a snapshot from the LWG issues list, see theLibrary Active Issues List for more information and the meaning ofCD1 status.

270. Binary search requirements overly strict

Section: 26.8.4[alg.binary.search]Status:CD1Submitter: Matt AusternOpened: 2000-10-18Last modified: 2016-01-28

Priority:Not Prioritized

View all otherissues in [alg.binary.search].

View all issues withCD1 status.

Duplicate of:472

Discussion:

Each of the four binary search algorithms (lower_bound, upper_bound,equal_range, binary_search) has a form that allows the user to pass acomparison function object. According to 25.3, paragraph 2, thatcomparison function object has to be a strict weak ordering.

This requirement is slightly too strict. Suppose we are searchingthrough a sequence containing objects of type X, where X is somelarge record with an integer key. We might reasonably want to lookup a record by key, in which case we would want to write somethinglike this:

    struct key_comp {      bool operator()(const X& x, int n) const {        return x.key() < n;      }    }    std::lower_bound(first, last, 47, key_comp());

key_comp is not a strict weak ordering, but there is no reason toprohibit its use in lower_bound.

There's no difficulty in implementing lower_bound so that it allowsthe use of something like key_comp. (It will probably work unless animplementor takes special pains to forbid it.) What's difficult isformulating language in the standard to specify what kind ofcomparison function is acceptable. We need a notion that's slightlymore general than that of a strict weak ordering, one that can encompassa comparison function that involves different types. Expressing thatnotion may be complicated.

Additional questions raised at the Toronto meeting:

• Do we really want to specify what ordering the implementor must use when calling the function object? The standard gives specific expressions when describing these algorithms, but it also says that other expressions (with different argument order) are equivalent.
• If we are specifying ordering, note that the standard uses both orderings when describingequal_range.
• Are we talking about requiring these algorithms to work properly when passed a binary function object whose two argument types are not the same, or are we talking about requirements when they are passed a binary function object with several overloaded versions ofoperator()?
• The definition of a strict weak ordering does not appear to give any guidance on issues of overloading; it only discusses expressions, and all of the values in these expressions are of the same type. Some clarification would seem to be in order.

Additional discussion from Copenhagen:

• It was generally agreed that there is a real defect here: ifthe predicate is merely required to be a Strict Weak Ordering, thenit's possible to pass in a function object with an overloadedoperator(), where the version that's actually called does somethingcompletely inappropriate. (Such as returning a random value.)
• An alternative formulation was presented in a paper distributed byDavid Abrahams at the meeting, "Binary Search with HeterogeneousComparison", J16-01/0027 = WG21 N1313: Instead of viewing thepredicate as a Strict Weak Ordering acting on a sorted sequence, viewthe predicate/value pair as something that partitions a sequence.This is almost equivalent to saying that we should view binary searchas if we are given a unary predicate and a sequence, such that f(*p)is true for all p below a specific point and false for all p above it.The proposed resolution is based on that alternative formulation.

Proposed resolution:

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 other than those 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 [start, finish) is partitioned with respect to an expression f(e) if there exists an integer n such that for all 0 <= i < distance(start, finish), f(*(begin+i)) is true if and only if i < 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). Also, for all elements e of [first, last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e)

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))

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)

[Copenhagen: Dave Abrahams provided this wording]

[Redmond: Minor changes in wording. (Removed "non-negative", andchanged the "other than those described in" wording.) Also, the LWGdecided to accept the "optional" part.]

Rationale:

The proposed resolution reinterprets binary search. Instead ofthinking about searching for a value in a sorted range, we view thatas an important special case of a more general algorithm: searchingfor the partition point in a partitioned range.

We also add a guarantee that the old wording did not: we ensurethat the upper bound is no earlier than the lower bound, thatthe pair returned by equal_range is a valid range, and that the firstpart of that pair is the lower bound.