2008-01-12 Paolo Carlini <pcarlini@suse.de>

	PR libstdc++/34730
	* include/debug/functions.h (__check_sorted_set,
	__check_sorted_set_aux): Add.
	(__check_sorted): Check StrictWeakOrdering.
	* include/debug/macros.h (__glibcxx_check_strict_weak_ordering,
	__glibcxx_check_strict_weak_ordering_pred): Remove.
	(__glibcxx_check_sorted, __glibcxx_check_sorted_pred): Adjust.
	(__glibcxx_check_sorted_set, __glibcxx_check_sorted_set_pred): Add.
	* include/debug/debug.h (__glibcxx_requires_sorted_set,
	__glibcxx_requires_sorted_set_pred): Add.
	* include/bits/stl_algo.h (merge, includes, set_union,
	set_intersection, set_difference, set_symmetric_difference):
	Adjust, use __glibcxx_requires_sorted_set* instead. 
	* testsuite/25_algorithms/set_intersection/34730.cc: New.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@131500 138bc75d-0d04-0410-961f-82ee72b054a4

6 files changed, 205 insertions, 50 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index 30d58857f83..a2b07544335 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -1,3 +1,20 @@
+2008-01-12  Paolo Carlini  <pcarlini@suse.de>
+
+	PR libstdc++/34730
+	* include/debug/functions.h (__check_sorted_set,
+	__check_sorted_set_aux): Add.
+	(__check_sorted): Check StrictWeakOrdering.
+	* include/debug/macros.h (__glibcxx_check_strict_weak_ordering,
+	__glibcxx_check_strict_weak_ordering_pred): Remove.
+	(__glibcxx_check_sorted, __glibcxx_check_sorted_pred): Adjust.
+	(__glibcxx_check_sorted_set, __glibcxx_check_sorted_set_pred): Add.
+	* include/debug/debug.h (__glibcxx_requires_sorted_set,
+	__glibcxx_requires_sorted_set_pred): Add.
+	* include/bits/stl_algo.h (merge, includes, set_union,
+	set_intersection, set_difference, set_symmetric_difference):
+	Adjust, use __glibcxx_requires_sorted_set* instead. 
+	* testsuite/25_algorithms/set_intersection/34730.cc: New.
+
 2008-01-09  Paolo Carlini  <pcarlini@suse.de>
 
 	* include/parallel/multiway_merge.h: Reformat to 80 columns;
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index b81a4a354cb..4c65e1154c1 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3034,15 +3034,16 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       while (__last - __first >= __two_step)
 	{
 	  __result = _GLIBCXX_STD_P::merge(__first, __first + __step_size,
-				__first + __step_size, __first + __two_step,
-				__result);
+					   __first + __step_size,
+					   __first + __two_step,
+					   __result);
 	  __first += __two_step;
 	}
 
       __step_size = std::min(_Distance(__last - __first), __step_size);
       _GLIBCXX_STD_P::merge(__first, __first + __step_size, 
 			    __first + __step_size, __last,
-		 __result);
+			    __result);
     }
 
   template<typename _RandomAccessIterator1, typename _RandomAccessIterator2,
@@ -3291,8 +3292,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (*__first2 < *__first1)
@@ -3328,7 +3329,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 	   typename _Compare>
     bool
     includes(_InputIterator1 __first1, _InputIterator1 __last1,
-	     _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp)
+	     _InputIterator2 __first2, _InputIterator2 __last2,
+	     _Compare __comp)
     {
       typedef typename iterator_traits<_InputIterator1>::value_type
 	_ValueType1;
@@ -3342,8 +3344,8 @@ _GLIBCXX_BEGIN_NAMESPACE(std)
 				  _ValueType1, _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (__comp(*__first2, *__first1))
@@ -5029,8 +5031,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
 				  _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
@@ -5092,8 +5094,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
@@ -5237,8 +5239,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
@@ -5305,8 +5307,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1, _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	{
@@ -5367,8 +5369,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (*__first1 < *__first2)
@@ -5425,8 +5427,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1, _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (__comp(*__first1, *__first2))
@@ -5480,8 +5482,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (*__first1 < *__first2)
@@ -5542,8 +5544,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1, _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (__comp(*__first1, *__first2))
@@ -5599,8 +5601,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
       __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)	
-      __glibcxx_requires_sorted(__first1, __last1);
-      __glibcxx_requires_sorted(__first2, __last2);
+      __glibcxx_requires_sorted_set(__first1, __last1, __first2);
+      __glibcxx_requires_sorted_set(__first2, __last2, __first1);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (*__first1 < *__first2)
@@ -5667,8 +5669,8 @@ _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_P)
 				  _ValueType1, _ValueType2>)
       __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
 				  _ValueType2, _ValueType1>)
-      __glibcxx_requires_sorted_pred(__first1, __last1, __comp);
-      __glibcxx_requires_sorted_pred(__first2, __last2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
+      __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
 
       while (__first1 != __last1 && __first2 != __last2)
 	if (__comp(*__first1, *__first2))
diff --git a/libstdc++-v3/include/debug/debug.h b/libstdc++-v3/include/debug/debug.h
index 32f96a37bed..97d6824ef0c 100644
--- a/libstdc++-v3/include/debug/debug.h
+++ b/libstdc++-v3/include/debug/debug.h
@@ -1,6 +1,6 @@
 // Debugging support implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2004, 2005, 2006, 2007
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -63,6 +63,8 @@ namespace __gnu_debug
 # define __glibcxx_requires_valid_range(_First,_Last)
 # define __glibcxx_requires_sorted(_First,_Last)
 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2)
+# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred)
 # define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)
 # define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)
 # define __glibcxx_requires_partitioned_lower_pred(_First,_Last,_Value,_Pred)
@@ -119,6 +121,10 @@ namespace std
      __glibcxx_check_sorted(_First,_Last)
 # define __glibcxx_requires_sorted_pred(_First,_Last,_Pred) \
      __glibcxx_check_sorted_pred(_First,_Last,_Pred)
+# define __glibcxx_requires_sorted_set(_First1,_Last1,_First2) \
+     __glibcxx_check_sorted_set(_First1,_Last1,_First2)
+# define __glibcxx_requires_sorted_set_pred(_First1,_Last1,_First2,_Pred) \
+     __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred)
 # define __glibcxx_requires_partitioned_lower(_First,_Last,_Value)	\
      __glibcxx_check_partitioned_lower(_First,_Last,_Value)
 # define __glibcxx_requires_partitioned_upper(_First,_Last,_Value)	\
diff --git a/libstdc++-v3/include/debug/functions.h b/libstdc++-v3/include/debug/functions.h
index 15c21541b28..7e7562a940d 100644
--- a/libstdc++-v3/include/debug/functions.h
+++ b/libstdc++-v3/include/debug/functions.h
@@ -1,6 +1,6 @@
 // Debugging support implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2005, 2006
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -205,10 +205,9 @@ namespace __gnu_debug
         return true;
 
       _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next) {
+      for (++__next; __next != __last; __first = __next, ++__next)
         if (*__next < *__first)
           return false;
-      }
 
       return true;
     }
@@ -232,10 +231,9 @@ namespace __gnu_debug
         return true;
 
       _ForwardIterator __next = __first;
-      for (++__next; __next != __last; __first = __next, ++__next) {
+      for (++__next; __next != __last; __first = __next, ++__next)
         if (__pred(*__next, *__first))
           return false;
-      }
 
       return true;
     }
@@ -247,6 +245,11 @@ namespace __gnu_debug
     {
       typedef typename std::iterator_traits<_InputIterator>::iterator_category
         _Category;
+
+      // Verify that the < operator for elements in the sequence is a
+      // StrictWeakOrdering by checking that it is irreflexive.
+      _GLIBCXX_DEBUG_ASSERT(__first == __last || !(*__first < *__first));
+
       return __check_sorted_aux(__first, __last, _Category());
     }
 
@@ -257,10 +260,80 @@ namespace __gnu_debug
     {
       typedef typename std::iterator_traits<_InputIterator>::iterator_category
         _Category;
-      return __check_sorted_aux(__first, __last, __pred,
-					     _Category());
+
+      // Verify that the predicate is StrictWeakOrdering by checking that it
+      // is irreflexive.
+      _GLIBCXX_DEBUG_ASSERT(__first == __last || !__pred(*__first, *__first));
+
+      return __check_sorted_aux(__first, __last, __pred, _Category());
+    }
+
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1& __first,
+			   const _InputIterator1& __last,
+			   const _InputIterator2&, std::__true_type)
+    { return __check_sorted(__first, __last); }
+
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1&,
+			   const _InputIterator1&,
+			   const _InputIterator2&, std::__false_type)
+    { return true; }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Predicate>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1& __first,
+			   const _InputIterator1& __last,
+			   const _InputIterator2&, _Predicate __pred,
+			   std::__true_type)
+    { return __check_sorted(__first, __last, __pred); }
+
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Predicate>
+    inline bool
+    __check_sorted_set_aux(const _InputIterator1&,
+			   const _InputIterator1&,
+			   const _InputIterator2&, _Predicate,
+			   std::__false_type)
+    { return true; }
+
+  // ... special variant used in std::merge, std::includes, std::set_*.
+  template<typename _InputIterator1, typename _InputIterator2>
+    inline bool
+    __check_sorted_set(const _InputIterator1& __first,
+		       const _InputIterator1& __last,
+		       const _InputIterator2&)
+    {
+      typedef typename std::iterator_traits<_InputIterator1>::value_type
+	_ValueType1;
+      typedef typename std::iterator_traits<_InputIterator2>::value_type
+	_ValueType2;
+
+      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
+	_SameType;
+      return __check_sorted_set_aux(__first, __last, _SameType());
     }
 
+  template<typename _InputIterator1, typename _InputIterator2,
+	   typename _Predicate>
+    inline bool
+    __check_sorted_set(const _InputIterator1& __first,
+		       const _InputIterator1& __last,
+		       const _InputIterator2&, _Predicate __pred)
+    {
+      typedef typename std::iterator_traits<_InputIterator1>::value_type
+	_ValueType1;
+      typedef typename std::iterator_traits<_InputIterator2>::value_type
+	_ValueType2;
+
+      typedef typename std::__are_same<_ValueType1, _ValueType2>::__type
+	_SameType;
+      return __check_sorted_set_aux(__first, __last, __pred, _SameType());
+   }
+
   // _GLIBCXX_RESOLVE_LIB_DEFECTS
   // 270. Binary search requirements overly strict
   // Determine if a sequence is partitioned w.r.t. this element.
diff --git a/libstdc++-v3/include/debug/macros.h b/libstdc++-v3/include/debug/macros.h
index 4f4a0ccc9bd..6b7b2b277a8 100644
--- a/libstdc++-v3/include/debug/macros.h
+++ b/libstdc++-v3/include/debug/macros.h
@@ -1,6 +1,6 @@
 // Debugging support implementation -*- C++ -*-
 
-// Copyright (C) 2003, 2005, 2006
+// Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
 // Free Software Foundation, Inc.
 //
 // This file is part of the GNU ISO C++ Library.  This library is free
@@ -140,21 +140,9 @@ _GLIBCXX_DEBUG_VERIFY(! this->empty(),					\
 		      _M_message(__gnu_debug::__msg_empty)	        \
                       ._M_sequence(*this, "this"))
 
-// Verify that the < operator for elements in the sequence is a
-// StrictWeakOrdering by checking that it is irreflexive.
-#define __glibcxx_check_strict_weak_ordering(_First,_Last)	\
-_GLIBCXX_DEBUG_ASSERT(_First == _Last || !(*_First < *_First))
-
-// Verify that the predicate is StrictWeakOrdering by checking that it
-// is irreflexive.
-#define __glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred)	\
-_GLIBCXX_DEBUG_ASSERT(_First == _Last || !_Pred(*_First, *_First))
-
-
 // Verify that the iterator range [_First, _Last) is sorted
 #define __glibcxx_check_sorted(_First,_Last)				\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_strict_weak_ordering(_First,_Last);			\
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last),	\
 		      _M_message(__gnu_debug::__msg_unsorted)	        \
                       ._M_iterator(_First, #_First)			\
@@ -164,13 +152,31 @@ _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last),	\
     predicate _Pred. */
 #define __glibcxx_check_sorted_pred(_First,_Last,_Pred)			\
 __glibcxx_check_valid_range(_First,_Last);				\
-__glibcxx_check_strict_weak_ordering_pred(_First,_Last,_Pred);	        \
 _GLIBCXX_DEBUG_VERIFY(__gnu_debug::__check_sorted(_First, _Last, _Pred), \
 		      _M_message(__gnu_debug::__msg_unsorted_pred)      \
                       ._M_iterator(_First, #_First)			\
 		      ._M_iterator(_Last, #_Last)			\
 		      ._M_string(#_Pred))
 
+// Special variant for std::merge, std::includes, std::set_*
+#define __glibcxx_check_sorted_set(_First1,_Last1,_First2)		\
+__glibcxx_check_valid_range(_First1,_Last1);				\
+_GLIBCXX_DEBUG_VERIFY(                                                  \
+  __gnu_debug::__check_sorted_set(_First1, _Last1, _First2),		\
+  _M_message(__gnu_debug::__msg_unsorted)				\
+  ._M_iterator(_First1, #_First1)					\
+  ._M_iterator(_Last1, #_Last1))
+
+// Likewise with a _Pred.
+#define __glibcxx_check_sorted_set_pred(_First1,_Last1,_First2,_Pred)	\
+__glibcxx_check_valid_range(_First1,_Last1);        			\
+_GLIBCXX_DEBUG_VERIFY(							\
+  __gnu_debug::__check_sorted_set(_First1, _Last1, _First2, _Pred),	\
+  _M_message(__gnu_debug::__msg_unsorted_pred)				\
+  ._M_iterator(_First1, #_First1)					\
+  ._M_iterator(_Last1, #_Last1)						\
+  ._M_string(#_Pred))
+
 /** Verify that the iterator range [_First, _Last) is partitioned
     w.r.t. the value _Value. */
 #define __glibcxx_check_partitioned_lower(_First,_Last,_Value)		\
diff --git a/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc b/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc
new file mode 100644
index 00000000000..66aef0f99df
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/set_intersection/34730.cc
@@ -0,0 +1,51 @@
+// Copyright (C) 2008 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
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 2, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING.  If not, write to the Free
+// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
+// USA.
+
+// { dg-options "-D_GLIBCXX_DEBUG" }
+// { dg-do compile }
+
+// libstdc++/34730
+
+#include <string>
+#include <vector>
+#include <algorithm>
+
+using namespace std;
+
+typedef pair<int, string> intstring;
+
+struct intstrcmp
+{
+  bool
+  operator()(const string& x, const intstring& y) const
+  { return x < y.second; }
+
+  bool
+  operator()(const intstring& x, const string& y) const
+  { return x.second < y; }
+};
+
+void test01()
+{
+  vector<string> vec1;
+  vector<intstring> vec2;
+  vector<intstring> vec3;
+  set_intersection(vec2.begin(), vec2.end(),
+		   vec1.begin(), vec1.end(),
+		   back_inserter(vec3), intstrcmp());
+}