[btree] Library working with more compilers and standard libraries
* VC++ 10 and MinGW/gcc 4.5 are my primary platforms, and the tests continue to pass on those. Some of the tests have been beefed up, too. * The Btree library now passes tests with Cygwin/gcc 4.3. That was a bug in my POSIX implementation code that is now fixed. * 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. I'm not sure how to deal with that. Maybe supply lower_bound/upper_bound implementations, and switch to them when needed. * I'm about to start a round of tests on Linux. --Beman
On Wed, Sep 29, 2010 at 9:10 AM, Beman Dawes <bdawes@acm.org> wrote:
* I'm about to start a round of tests on Linux.
Great news Beman, I look forward to more information about how it works on Linux. It would be great to know if you encounter any problems so that us Linux natives can help you out. -- Dean Michael Berris deanberris.com
On Tue, Sep 28, 2010 at 9:33 PM, Dean Michael Berris <mikhailberis@gmail.com> wrote:
On Wed, Sep 29, 2010 at 9:10 AM, Beman Dawes <bdawes@acm.org> wrote:
* I'm about to start a round of tests on Linux.
Great news Beman, I look forward to more information about how it works on Linux. It would be great to know if you encounter any problems so that us Linux natives can help you out.
The tests are now passing on my Ubuntu VirtualBox g++ 4.4 setup, and the fixes have been pushed up to GitHub. I haven't done any testing beyond simply getting the tests to compile and run, however. The great bulk of the code is operating system independent. The biggest worry for me is libs/btree/src/detail/binary_file.cpp. It would be a big help if POSIX and/or Linux folks could look that over to see if they can spot any weaknesses. Thanks, --Beman
[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
On Tue, Sep 28, 2010 at 9:55 PM, Stephan T. Lavavej <stl@exchange.microsoft.com> wrote:
[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.
...
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.
Worked like a charm! VC++ 8, 9, and 10 are now passing all the B-tree tests. Thanks! --Beman
participants (3)
-
Beman Dawes -
Dean Michael Berris -
Stephan T. Lavavej