[libstdc++] Follow-on changes for libstdc++/2054

[Phil Edwards]

The fix for that PR involved changing the concept checks for
std::lower_bound.  Mr. Schmid pointed out that the same potential problems
occur in the three other binary-searching functions.

Tested on i686-linux.



2002-01-02  Phil Edwards  <pme@gcc.gnu.org>

	* include/bits/stl_algo.h (upper_bound, equal_range, binary_search):
	Change concept checks, as with lower_bound and PR 2054.
	* testsuite/ext/concept_checks.cc:  Expand test to include those.


Index: include/bits/stl_algo.h
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/include/bits/stl_algo.h,v
retrieving revision 1.17
diff -u -3 -p -r1.17 stl_algo.h
--- stl_algo.h	2001/12/28 21:57:46	1.17
+++ stl_algo.h	2002/01/03 04:42:35
@@ -1,6 +1,6 @@
 // Algorithm implimentation -*- C++ -*-
 
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -1949,6 +1949,10 @@ __result, __binary_pred, _IterType());
       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
     
       // concept requirements
+      // Note that these are slightly stricter than those of the 4-argument
+      // version, defined next.  The difference is in the strictness of the
+      // comparison operations... so for looser checking, define your own
+      // comparison function, as was intended.
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
@@ -2011,6 +2015,7 @@ __result, __binary_pred, _IterType());
       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
       
       // concept requirements
+      // See comments on lower_bound.
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
@@ -2044,8 +2049,7 @@ __result, __binary_pred, _IterType());
       
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
-      __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
-      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
     
       _DistanceType __len = distance(__first, __last);
       _DistanceType __half;
@@ -2074,6 +2078,7 @@ __result, __binary_pred, _IterType());
       typedef typename iterator_traits<_ForwardIter>::difference_type _DistanceType;
       
       // concept requirements
+      // See comments on lower_bound.
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
       __glibcpp_function_requires(_LessThanComparableConcept<_Tp>)
@@ -2113,8 +2118,8 @@ __result, __binary_pred, _IterType());
       
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
-      __glibcpp_function_requires(_SameTypeConcept<_Tp, _ValueType>)
-      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _ValueType, _Tp>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _ValueType>)
     
       _DistanceType __len = distance(__first, __last);
       _DistanceType __half;
@@ -2147,6 +2152,7 @@ __result, __binary_pred, _IterType());
                   const _Tp& __val)
     {
       // concept requirements
+      // See comments on lower_bound.
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
       __glibcpp_function_requires(_SameTypeConcept<_Tp,
 		typename iterator_traits<_ForwardIter>::value_type>)
@@ -2163,9 +2169,10 @@ __result, __binary_pred, _IterType());
     {
       // concept requirements
       __glibcpp_function_requires(_ForwardIteratorConcept<_ForwardIter>)
-      __glibcpp_function_requires(_SameTypeConcept<_Tp,
+      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare,
+		typename iterator_traits<_ForwardIter>::value_type, _Tp>)
+      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp,
 		typename iterator_traits<_ForwardIter>::value_type>)
-      __glibcpp_function_requires(_BinaryPredicateConcept<_Compare, _Tp, _Tp>)
 
       _ForwardIter __i = lower_bound(__first, __last, __val, __comp);
       return __i != __last && !__comp(__val, *__i);
Index: testsuite/ext/concept_checks.cc
===================================================================
RCS file: /cvs/gcc/gcc/libstdc++-v3/testsuite/ext/concept_checks.cc,v
retrieving revision 1.1
diff -u -3 -p -r1.1 concept_checks.cc
--- concept_checks.cc	2001/12/28 21:57:47	1.1
+++ concept_checks.cc	2002/01/03 04:42:35
@@ -1,6 +1,6 @@
 // 2001-12-28  Phil Edwards  <pme@gcc.gnu.org>
 //
-// Copyright (C) 2001 Free Software Foundation, Inc.
+// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
 // software; you can redistribute it and/or modify it under the
@@ -30,7 +30,7 @@
 using namespace std;
 
 
-// PR libstdc++/2054
+// PR libstdc++/2054 and follow-up discussion
 struct indirectCompare
 {
   indirectCompare(const vector<string>& v) : V(v) {}
@@ -45,6 +45,11 @@ struct indirectCompare
        return V[x] < a;
   }
 
+  bool operator()( const string& a, int x) const
+  {
+       return V[x] < a;
+  }
+
   const vector<string>& V;
 };
 
@@ -66,6 +71,9 @@ test2054( )
   string SearchTerm;
 
   lower_bound(Index.begin(), Index.end(), SearchTerm, aComparison);
+  upper_bound(Index.begin(), Index.end(), SearchTerm, aComparison);
+  equal_range(Index.begin(), Index.end(), SearchTerm, aComparison);
+  binary_search(Index.begin(), Index.end(), SearchTerm, aComparison);
 }
 
 int main()