This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[v3] libstdc++/34730
- From: Paolo Carlini <pcarlini at suse dot de>
- To: Gcc Patch List <gcc-patches at gcc dot gnu dot org>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Sun, 13 Jan 2008 02:36:12 +0100
- Subject: [v3] libstdc++/34730
Hi,
the final version of the work. Tested x86_64-linux, committed to mainline.
Paolo.
/////////////////
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.
Index: include/debug/functions.h
===================================================================
--- include/debug/functions.h (revision 131492)
+++ include/debug/functions.h (working copy)
@@ -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 @@
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 @@
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 @@
{
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 @@
{
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.
Index: include/debug/macros.h
===================================================================
--- include/debug/macros.h (revision 131492)
+++ include/debug/macros.h (working copy)
@@ -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 @@
_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 @@
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) \
Index: include/debug/debug.h
===================================================================
--- include/debug/debug.h (revision 131492)
+++ include/debug/debug.h (working copy)
@@ -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 @@
# 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 @@
__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) \
Index: include/bits/stl_algo.h
===================================================================
--- include/bits/stl_algo.h (revision 131492)
+++ include/bits/stl_algo.h (working copy)
@@ -3034,15 +3034,16 @@
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_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 @@
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 @@
_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_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 @@
_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 @@
_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 @@
_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 @@
_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 @@
_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 @@
_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 @@
_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 @@
_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 @@
_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))
Index: testsuite/25_algorithms/set_intersection/34730.cc
===================================================================
--- testsuite/25_algorithms/set_intersection/34730.cc (revision 0)
+++ testsuite/25_algorithms/set_intersection/34730.cc (revision 0)
@@ -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());
+}