Re: [boost] [btree] Library working with more compilers and standard libraries

Subject: Re: [boost] [btree] Library working with more compilers and standard libraries
From: Stephan T. Lavavej (stl_at_[hidden])
Date: 2010-09-28 21:55:10

[Beman Dawes]
> VC++ 9 is working OK in release mode. There is a bug in some debug
> mode code in the standard library <algorithm> header's lower_bound and
> upper_bound functions.

VC8 and VC9's lower_bound() and upper_bound() dislike heterogeneous comparisons, where *first and value have different types.

Quoting myself from http://lists.cs.uiuc.edu/pipermail/cfe-dev/2010-August/010436.html :

> C++98/03 said:

> 25.3.3: "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."

> 25.3.3.1/1: "Requires: Type T is LessThanComparable (20.1.2)."

> The problem, of course, was that C++98/03 wasn't thinking about this
> clearly, but it's obvious that whatever it was thinking, it was
> thinking about homogeneous comparisons only.

> The FCD, happily, speaks with crystal clarity:

> 25.4.3: "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."

> 25.4.3.1: "Requires: The elements e of [first,last) shall be
> partitioned with respect to the expression e < value or comp(e,
> value)."

> I maintain that VC8/9's debug checks were perfectly acceptable
> according to C++98/03. In any event, VC10 follows C++0x and permits
> heterogeneous comparisons. I've got a todo to investigate re-enabling
> the debug checks in a form friendly to heterogeneous comparisons.

I should clarify my original conclusion ("By the way, providing additional comparators is the correct workaround for VC8/9."). I'll refer to the sequence's element type as E and the provided value's type as V. If you provide E < E, E < V, and V < E (or equivalent comparators), and the sequence is sorted with respect to E < E and partitioned with respect to E < V and V < E, then you should be fine. Providing such comparators should almost always be possible, since lower_bound() and upper_bound() are almost always used with sequences that are actually sorted according to some criterion, rather than merely partitioned.

Stephan T. Lavavej
Visual C++ Libraries Developer