test for lib.binary.search

[Anton Pevtsov <an...@moscow.vdiweb.com>]

The attached file contains the test for the lib.binary.search algorithm.

Here I use new compare functor instead of binary_predicate because
the following code fails to compile:

template
bool
std::binary_search (int*, int*,
                    const int&,
                    binary_predicate<int >);

with error:
stdlib\\include\algorithm(1036): error C2248:
'conv_to_bool::operator`!'' : cannot access private member declared in
class 'conv_to_bool'

The binary_search accepts Compare (not BinaryPredicate) functor. The
standard (25.3, p2) says that Compare should return true or false. At
the same time, it says (25, p8) that BinaryPredicate should return value
testable as true. The difference results in the error above.
It looks like we shouldn't use binary_predicate to test this algorithm
(as well as lower.bound, upper.bound, equal.range there the difference
between compare and binary_predicate is not significant). So it would be
useful to add compare functor to the alg_test.h header. Or it is
possible to modify the binary_search algorithm to not use the
"! operator()".
What do you think about it?

And here is another small question:
may be it would be useful to merge tests for lower.bound, upper.bound,
equal.range and binary.search into one .cpp file (tests for these
algorithms are very similar)?


Thanks,
Anton Pevtsov

Re: test for lib.binary.search

[Martin Sebor <se...@roguewave.com>]

Anton Pevtsov wrote:
> The attached file contains the test for the lib.binary.search algorithm.

Thanks! I committed it here:
http://svn.apache.org/viewcvs.cgi?rev=375145&view=rev

> 
> Here I use new compare functor instead of binary_predicate because
> the following code fails to compile:
> 
> template
> bool
> std::binary_search (int*, int*,
>                    const int&,
>                    binary_predicate<int >);
> 
> with error:
> stdlib\\include\algorithm(1036): error C2248:
> 'conv_to_bool::operator`!'' : cannot access private member declared in
> class 'conv_to_bool'
> 
> The binary_search accepts Compare (not BinaryPredicate) functor. The
> standard (25.3, p2) says that Compare should return true or false. At
> the same time, it says (25, p8) that BinaryPredicate should return value
> testable as true. The difference results in the error above.
> It looks like we shouldn't use binary_predicate to test this algorithm
> (as well as lower.bound, upper.bound, equal.range there the difference
> between compare and binary_predicate is not significant). So it would be
> useful to add compare functor to the alg_test.h header. Or it is
> possible to modify the binary_search algorithm to not use the
> "! operator()".
> What do you think about it?

Interesting. I think our general policy should be to be as robust
as possible (i.e., impose as few requirements as reasonably possible
without affecting the performance and maintainability of our code),
even in cases where the standard allows us more latitude.

In this specific case, even though the standard does suggest that
the type of Compare::operator() is required to be bool, I think it
would make sense to relax that requirement following the example set
by the text for Predicates. I informally proposed this change on the
committee's mailing list and if there are no objections from anyone
I will file an issue to have the standard changed.

Either way, let's also open a STDCXX issue and make a note to change
our implementation so as not to assume that the return type is bool
and accommodate user-defined types, including conv_to_bool.

> 
> And here is another small question:
> may be it would be useful to merge tests for lower.bound, upper.bound,
> equal.range and binary.search into one .cpp file (tests for these
> algorithms are very similar)?

I think your suggestion makes perfect sense from the standpoint of
code reuse. I'm just a little concerned what it might do to the
readability of the tests. In addition, having them all in the same
file would allow a compilation error in one algorithm to prevent
the other algorithms from being tested. But if you can resolve both
of these concerns, perhaps by factoring out the common code from
all three tests into the same header file and #include it in each
instead of duplicating all the code, it might be worth considering.

Martin