@@ -2026,7 +2026,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_partitioned_lower_pred(__first, __last,
__val, __comp);
- __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__lower_bound(__first, __last, __val,
__gnu_cxx::__ops::__iter_comp_val(__comp));
@@ -2080,7 +2079,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_LessThanOpConcept<
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- __glibcxx_requires_irreflexive2(__first, __last);
return std::__upper_bound(__first, __last, __val,
__gnu_cxx::__ops::__val_less_iter());
@@ -2112,7 +2110,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
- __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__upper_bound(__first, __last, __val,
__gnu_cxx::__ops::__val_comp_iter(__comp));
@@ -2186,7 +2183,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- __glibcxx_requires_irreflexive2(__first, __last);
return std::__equal_range(__first, __last, __val,
__gnu_cxx::__ops::__iter_less_val(),
@@ -2225,7 +2221,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__val, __comp);
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
- __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
return std::__equal_range(__first, __last, __val,
__gnu_cxx::__ops::__iter_comp_val(__comp),
@@ -2255,7 +2250,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_Tp, typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
__glibcxx_requires_partitioned_upper(__first, __last, __val);
- __glibcxx_requires_irreflexive2(__first, __last);
_ForwardIterator __i
= std::__lower_bound(__first, __last, __val,
@@ -2291,7 +2285,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__val, __comp);
__glibcxx_requires_partitioned_upper_pred(__first, __last,
__val, __comp);
- __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
_ForwardIterator __i
= std::__lower_bound(__first, __last, __val,
@@ -989,7 +989,6 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__glibcxx_function_requires(_LessThanOpConcept<
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
- __glibcxx_requires_irreflexive2(__first, __last);
return std::__lower_bound(__first, __last, __val,
__gnu_cxx::__ops::__iter_less_val());
@@ -1214,9 +1213,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
__glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
__glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_irreflexive2(__first1, __last1);
__glibcxx_requires_valid_range(__first2, __last2);
- __glibcxx_requires_irreflexive2(__first2, __last2);
return std::__lexicographical_compare_aux(std::__niter_base(__first1),
std::__niter_base(__last1),
@@ -1246,9 +1243,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
__glibcxx_function_requires(_InputIteratorConcept<_II1>)
__glibcxx_function_requires(_InputIteratorConcept<_II2>)
__glibcxx_requires_valid_range(__first1, __last1);
- __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
__glibcxx_requires_valid_range(__first2, __last2);
- __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
return std::__lexicographical_compare_impl
(__first1, __last1, __first2, __last2,
new file mode 100644
@@ -0,0 +1,67 @@
+// Copyright (C) 2016 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+ int val;
+
+ bool odd() const { return val % 2; }
+
+ // Partitioned so that all odd values come before even values:
+ bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test with range that is partitioned, but not sorted.
+ X seq[] = { 1, 3, 5, 7, 1, 6, 4 };
+ test_container<X, forward_iterator_wrapper> c(seq);
+
+ auto b1 = std::binary_search(c.begin(), c.end(), X{2});
+ VERIFY( b1 );
+ auto b2 = std::binary_search(c.begin(), c.end(), X{2}, std::less<X>{});
+ VERIFY( b2 );
+
+ auto b3 = std::binary_search(c.begin(), c.end(), X{9});
+ VERIFY( b3 );
+ auto b4 = std::binary_search(c.begin(), c.end(), X{9}, std::less<X>{});
+ VERIFY( b4 );
+
+ auto b5 = std::binary_search(seq, seq+5, X{2});
+ VERIFY( !b5 );
+ auto b6 = std::binary_search(seq, seq+5, X{2}, std::less<X>{});
+ VERIFY( !b6 );
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,66 @@
+// Copyright (C) 2016 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+ int val;
+
+ bool odd() const { return val % 2; }
+
+ // Partitioned so that all odd values come before even values:
+ bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test with range that is partitioned, but not sorted.
+ X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+ test_container<X, forward_iterator_wrapper> c(seq);
+
+ auto part1 = std::equal_range(c.begin(), c.end(), X{2});
+ VERIFY( part1.first != c.end() && part1.second == c.end() );
+ VERIFY( part1.first->val == 6 );
+ auto part2 = std::equal_range(c.begin(), c.end(), X{2}, std::less<X>{});
+ VERIFY( part2.first != c.end() && part1.second == c.end() );
+ VERIFY( part2.first->val == 6 );
+
+ auto part3 = std::equal_range(c.begin(), c.end(), X{9});
+ VERIFY( part3.first == c.begin() && part3.second != c.end() );
+ VERIFY( part3.second->val == 6 );
+ auto part4 = std::equal_range(c.begin(), c.end(), X{9}, std::less<X>{});
+ VERIFY( part4.first == c.begin() && part4.second != c.end() );
+ VERIFY( part4.second->val == 6 );
+}
+
+int
+main()
+{
+ test01();
+}
new file mode 100644
@@ -0,0 +1,35 @@
+// Copyright (C) 2016 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" }
+// { dg-do link }
+
+#include <algorithm>
+
+struct X { };
+
+bool operator<(X, int) { return true; }
+bool operator<(int, X) { return false; }
+
+bool operator<(X, X); // undefined (PR libstdc++/71545)
+
+int main()
+{
+ X x[1];
+ int i[1];
+ std::lexicographical_compare(x, x+1, i, i+1);
+}
new file mode 100644
@@ -0,0 +1,100 @@
+// Copyright (C) 2016 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+ int val;
+
+ bool odd() const { return val % 2; }
+
+ // Partitioned so that all odd values come before even values:
+ bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test with range that is partitioned, but not sorted.
+ X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+ test_container<X, forward_iterator_wrapper> c(seq);
+
+ auto part1 = std::lower_bound(c.begin(), c.end(), X{2});
+ VERIFY( part1 != c.end() );
+ VERIFY( part1->val == 6 );
+ auto part2 = std::lower_bound(c.begin(), c.end(), X{2}, std::less<X>{});
+ VERIFY( part2 != c.end() );
+ VERIFY( part2->val == 6 );
+
+ auto part3 = std::lower_bound(c.begin(), c.end(), X{9});
+ VERIFY( part3 != c.end() );
+ VERIFY( part3->val == 1 );
+ auto part4 = std::lower_bound(c.begin(), c.end(), X{9}, std::less<X>{});
+ VERIFY( part4 != c.end() );
+ VERIFY( part4->val == 1 );
+}
+
+struct Y
+{
+ double val;
+
+ // Not irreflexive, so not a strict weak order.
+ bool operator<(const Y& y) const { return val < int(y.val); }
+};
+
+void
+test02()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test that Debug Mode checks don't fire (libstdc++/71545)
+
+ Y seq[] = { -0.1, 1.2, 5.0, 5.2, 5.1, 5.9, 5.5, 6.0 };
+ test_container<Y, forward_iterator_wrapper> c(seq);
+
+ auto part1 = std::lower_bound(c.begin(), c.end(), Y{5.5});
+ VERIFY( part1 != c.end() );
+ VERIFY( part1->val == 5.0 );
+ auto part2 = std::lower_bound(c.begin(), c.end(), Y{5.5}, std::less<Y>{});
+ VERIFY( part2 != c.end() );
+ VERIFY( part2->val == 5.0 );
+
+ auto part3 = std::lower_bound(c.begin(), c.end(), Y{1.0});
+ VERIFY( part3 != c.end() );
+ VERIFY( part3->val == 1.2 );
+ auto part4 = std::lower_bound(c.begin(), c.end(), Y{1.0}, std::less<Y>{});
+ VERIFY( part4 != c.end() );
+ VERIFY( part4->val == 1.2 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
new file mode 100644
@@ -0,0 +1,98 @@
+// Copyright (C) 2016 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 3, 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 COPYING3. If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++11 -D_GLIBCXX_DEBUG" }
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_iterators.h>
+#include <testsuite_hooks.h>
+
+using __gnu_test::test_container;
+using __gnu_test::forward_iterator_wrapper;
+
+struct X
+{
+ int val;
+
+ bool odd() const { return val % 2; }
+
+ // Partitioned so that all odd values come before even values:
+ bool operator<(const X& x) const { return this->odd() && !x.odd(); }
+};
+
+void
+test01()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test with range that is partitioned, but not sorted.
+ X seq[] = { 1, 3, 5, 7, 1, 6, 4, 2 };
+ test_container<X, forward_iterator_wrapper> c(seq);
+
+ auto part1 = std::upper_bound(c.begin(), c.end(), X{2});
+ VERIFY( part1 == c.end() );
+ auto part2 = std::upper_bound(c.begin(), c.end(), X{2}, std::less<X>{});
+ VERIFY( part2 == c.end() );
+
+ auto part3 = std::upper_bound(c.begin(), c.end(), X{9});
+ VERIFY( part3 != c.end() );
+ VERIFY( part3->val == 6 );
+ auto part4 = std::upper_bound(c.begin(), c.end(), X{9}, std::less<X>{});
+ VERIFY( part3 != c.end() );
+ VERIFY( part4->val == 6 );
+}
+
+struct Y
+{
+ double val;
+
+ // Not irreflexive, so not a strict weak order.
+ bool operator<(const Y& y) const { return val < (int)y.val; }
+};
+
+void
+test02()
+{
+ bool test __attribute((unused)) = true;
+
+ // Test that Debug Mode checks don't fire (libstdc++/71545)
+
+ Y seq[] = { -0.1, 1.2, 5.0, 5.2, 5.1, 5.9, 5.5, 6.0 };
+ test_container<Y, forward_iterator_wrapper> c(seq);
+
+ auto part1 = std::upper_bound(c.begin(), c.end(), Y{5.5});
+ VERIFY( part1 != c.end() );
+ VERIFY( part1->val == 6.0 );
+ auto part2 = std::upper_bound(c.begin(), c.end(), Y{5.5}, std::less<Y>{});
+ VERIFY( part2 != c.end() );
+ VERIFY( part2->val == 6.0 );
+
+ auto part3 = std::upper_bound(c.begin(), c.end(), Y{1.0});
+ VERIFY( part3 != c.end() );
+ VERIFY( part3->val == 5.0 );
+ auto part4 = std::upper_bound(c.begin(), c.end(), Y{1.0}, std::less<Y>{});
+ VERIFY( part4 != c.end() );
+ VERIFY( part4->val == 5.0 );
+}
+
+int
+main()
+{
+ test01();
+ test02();
+}
@@ -542,6 +542,13 @@ namespace __gnu_test
test_container(T* _first, T* _last):bounds(_first, _last)
{ }
+#if __cplusplus >= 201103L
+ template<std::size_t N>
+ explicit
+ test_container(T (&arr)[N]) : test_container(arr, arr+N)
+ { }
+#endif
+
ItType<T>
it(int pos)
{
PR libstdc++/71545 * include/bits/stl_algobase.h (lower_bound, lexicographical_compare): Remove irreflexive checks. * include/bits/stl_algo.h (lower_bound, upper_bound, equal_range, binary_search): Likewise. * testsuite/25_algorithms/equal_range/partitioned.cc: New test. * testsuite/25_algorithms/lexicographical_compare/71545.cc: New test. * testsuite/25_algorithms/lower_bound/partitioned.cc: New test. * testsuite/25_algorithms/upper_bound/partitioned.cc: New test. * testsuite/util/testsuite_iterators.h (__gnu_test::test_container): Add constructor from array. The binary search algos and lexicographical_compare do not require the comparison function to be irreflexive, so the recently-added debug mode checks need to be removed. Tested x86_64-linux, committed to trunk. gcc-6-branch commit to follow. commit e775b35ff6cb0b6843ec2f1c8bf3a136deb898dd Author: Jonathan Wakely <jwakely@redhat.com> Date: Fri Jun 17 11:09:18 2016 +0100 libstdc++/71545 fix debug checks in binary search algorithms PR libstdc++/71545 * include/bits/stl_algobase.h (lower_bound, lexicographical_compare): Remove irreflexive checks. * include/bits/stl_algo.h (lower_bound, upper_bound, equal_range, binary_search): Likewise. * testsuite/25_algorithms/equal_range/partitioned.cc: New test. * testsuite/25_algorithms/lexicographical_compare/71545.cc: New test. * testsuite/25_algorithms/lower_bound/partitioned.cc: New test. * testsuite/25_algorithms/upper_bound/partitioned.cc: New test. * testsuite/util/testsuite_iterators.h (__gnu_test::test_container): Add constructor from array.