[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