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
> 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."
> 220.127.116.11/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."
> 18.104.22.168: "Requires: The elements e of [first,last) shall be
> partitioned with respect to the expression e < value or comp(e,
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk