[patch] C++14: N3671 Making non-modifying sequence operations more robust
Jonathan Wakely
jwakely.gcc@gmail.com
Sat Jun 8 16:13:00 GMT 2013
Another C++14 feature.
* include/bits/stl_algo.h (is_permutation): Add overloads from N3671.
* include/bits/stl_algobase.h (equal, mismatch): Likewise.
* testsuite/25_algorithms/equal/1.cc: Remove duplicate test case.
* testsuite/25_algorithms/equal/2.cc: New.
* testsuite/25_algorithms/equal/check_type2.cc: New.
* testsuite/25_algorithms/is_permutationqual/2.cc: New.
* testsuite/25_algorithms/is_permutationqual/check_type2.cc: New.
* testsuite/25_algorithms/mismatch/2.cc: New.
* testsuite/25_algorithms/mismatch/check_type2.cc: New.
* testsuite/util/testsuite_iterators.h: Fix spelling.
Tested x86_64-linux, committed to trunk.
-------------- next part --------------
commit d38ec2374fd13499d9aa3d6e504193edb2cbf703
Author: Jonathan Wakely <jwakely.gcc@gmail.com>
Date: Sat Jun 8 16:46:23 2013 +0100
* include/bits/stl_algo.h (is_permutation): Add overloads from N3671.
* include/bits/stl_algobase.h (equal, mismatch): Likewise.
* testsuite/25_algorithms/equal/1.cc: Remove duplicate test case.
* testsuite/25_algorithms/equal/2.cc: New.
* testsuite/25_algorithms/equal/check_type2.cc: New.
* testsuite/25_algorithms/is_permutationqual/2.cc: New.
* testsuite/25_algorithms/is_permutationqual/check_type2.cc: New.
* testsuite/25_algorithms/mismatch/2.cc: New.
* testsuite/25_algorithms/mismatch/check_type2.cc: New.
* testsuite/util/testsuite_iterators.h: Fix spelling.
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 873005b..e61f22b 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -4371,6 +4371,140 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return true;
}
+#if __cplusplus > 201103L
+ /**
+ * @brief Checks whether a permutaion of the second sequence is equal
+ * to the first sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 Start of first range.
+ * @param __last1 End of first range.
+ * @param __first2 Start of second range.
+ * @param __last2 End of first range.
+ * @return true if there exists a permutation of the elements in the range
+ * [__first2, __last2), beginning with ForwardIterator2 begin,
+ * such that equal(__first1, __last1, begin) returns true;
+ * otherwise, returns false.
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2>
+ bool
+ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2)
+ {
+ using _Cat1
+ = typename iterator_traits<_ForwardIterator1>::iterator_category;
+ using _Cat2
+ = typename iterator_traits<_ForwardIterator2>::iterator_category;
+ using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
+ using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
+ if (_It1_is_RA() && _It1_is_RA())
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+ }
+
+ // Efficiently compare identical prefixes: O(N) if sequences
+ // have the same elements in the same order.
+ for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
+ if (!(*__first1 == *__first2))
+ break;
+
+ if (__first1 == __last1 && __first2 == __last2)
+ return true;
+
+ if (std::distance(__first1, __last1) != std::distance(__first2, __last2))
+ return false;
+
+ for (auto __scan = __first1; __scan != __last1; ++__scan)
+ {
+ if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
+ continue; // We've seen this one before.
+
+ auto __matches = std::count(__first2, __last2, *__scan);
+ if (0 == __matches
+ || std::count(__scan, __last1, *__scan) != __matches)
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * @brief Checks whether a permutation of the second sequence is equal
+ * to the first sequence.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 Start of first range.
+ * @param __last1 End of first range.
+ * @param __first2 Start of second range.
+ * @param __last2 End of first range.
+ * @param __pred A binary predicate.
+ * @return true if there exists a permutation of the elements in the range
+ * [__first2, __last2), beginning with ForwardIterator2 begin,
+ * such that equal(__first1, __last1, __begin, __pred) returns true;
+ * otherwise, returns false.
+ */
+ template<typename _ForwardIterator1, typename _ForwardIterator2,
+ typename _BinaryPredicate>
+ bool
+ is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
+ _ForwardIterator2 __first2, _ForwardIterator2 __last2,
+ _BinaryPredicate __pred)
+ {
+ using _Cat1
+ = typename iterator_traits<_ForwardIterator1>::iterator_category;
+ using _Cat2
+ = typename iterator_traits<_ForwardIterator2>::iterator_category;
+ using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
+ using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
+ constexpr bool __ra_iters = _It1_is_RA() && _It1_is_RA();
+ if (__ra_iters)
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+ }
+
+ // Efficiently compare identical prefixes: O(N) if sequences
+ // have the same elements in the same order.
+ for (; __first1 != __last1; ++__first1, ++__first2)
+ if (!bool(__pred(*__first1, *__first2)))
+ break;
+
+ if (__ra_iters)
+ {
+ if (__first1 == __last1)
+ return true;
+ }
+ else
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 == 0 && __d2 == 0)
+ return true;
+ if (__d1 != __d2)
+ return false;
+ }
+
+ for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
+ {
+ using std::placeholders::_1;
+
+ if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
+ std::bind(__pred, _1, *__scan)))
+ continue; // We've seen this one before.
+
+ auto __matches = std::count_if(__first2, __last2,
+ std::bind(__pred, _1, *__scan));
+ if (0 == __matches
+ || std::count_if(__scan, __last1,
+ std::bind(__pred, _1, *__scan)) != __matches)
+ return false;
+ }
+ return true;
+ }
+#endif
+
#ifdef _GLIBCXX_USE_C99_STDINT_TR1
/**
* @brief Shuffle the elements of a sequence using a uniform random
diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index a90881f..67f859b 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -798,6 +798,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return false;
return true;
}
+
+#if __cplusplus > 201103L
+ template<typename _II1, typename _II2>
+ static bool
+ equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ for (; __first1 != __last1 && __first2 != __last2;
+ ++__first1, ++__first2)
+ if (!(*__first1 == *__first2))
+ return false;
+ return true;
+ }
+#endif
};
template<>
@@ -810,6 +823,17 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
* (__last1 - __first1));
}
+
+#if __cplusplus > 201103L
+ template<typename _Tp>
+ static bool
+ equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2,
+ const _Tp* __last2)
+ {
+ return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
+ * (__last1 - __first1));
+ }
+#endif
};
template<typename _II1, typename _II2>
@@ -827,6 +851,65 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::__equal<__simple>::equal(__first1, __last1, __first2);
}
+#if __cplusplus > 201103L
+ template<bool _BoolType>
+ struct __equal2
+ {
+ template<typename _It>
+ using _IterCat = typename iterator_traits<_It>::iterator_category;
+ template<typename _It>
+ using _IsRA = is_same<_IterCat<_It>, random_access_iterator_tag>;
+
+ template<typename _II1, typename _II2>
+ static bool
+ equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ constexpr bool __ra_iters = _IsRA<_II1>() && _IsRA<_II2>();
+ if (__ra_iters)
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+ }
+ for (; __first1 != __last1 && __first2 != __last2;
+ ++__first1, ++__first2)
+ if (!(*__first1 == *__first2))
+ return false;
+ return __ra_iters || (__first1 == __last1 && __first2 == __last2);
+ }
+ };
+
+ template<>
+ struct __equal2<true>
+ {
+ template<typename _Tp>
+ static bool
+ equal(const _Tp* __first1, const _Tp* __last1, const _Tp* __first2,
+ const _Tp* __last2)
+ {
+ if ((__last1 - __first1) != (__last2 - __first2))
+ return false;
+ return !__builtin_memcmp(__first1, __first2, sizeof(_Tp)
+ * (__last1 - __first1));
+ }
+ };
+
+ template<typename _II1, typename _II2>
+ inline bool
+ __equal2_aux(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ typedef typename iterator_traits<_II1>::value_type _ValueType1;
+ typedef typename iterator_traits<_II2>::value_type _ValueType2;
+ const bool __simple = ((__is_integer<_ValueType1>::__value
+ || __is_pointer<_ValueType1>::__value)
+ && __is_pointer<_II1>::__value
+ && __is_pointer<_II2>::__value
+ && __are_same<_ValueType1, _ValueType2>::__value);
+
+ return __equal2<__simple>::equal(__first1, __last1, __first2, __last2);
+ }
+#endif
template<typename, typename>
struct __lc_rai
@@ -1064,6 +1147,86 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return true;
}
+#if __cplusplus > 201103L
+ /**
+ * @brief Tests a range for element-wise equality.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 An input iterator.
+ * @param __last1 An input iterator.
+ * @param __first2 An input iterator.
+ * @param __last2 An input iterator.
+ * @return A boolean true or false.
+ *
+ * This compares the elements of two ranges using @c == and returns true or
+ * false depending on whether all of the corresponding elements of the
+ * ranges are equal.
+ */
+ template<typename _II1, typename _II2>
+ inline bool
+ equal(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_II1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_II2>)
+ __glibcxx_function_requires(_EqualOpConcept<
+ typename iterator_traits<_II1>::value_type,
+ typename iterator_traits<_II2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ return std::__equal2_aux(std::__niter_base(__first1),
+ std::__niter_base(__last1),
+ std::__niter_base(__first2),
+ std::__niter_base(__last2));
+ }
+
+ /**
+ * @brief Tests a range for element-wise equality.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 An input iterator.
+ * @param __last1 An input iterator.
+ * @param __first2 An input iterator.
+ * @param __last2 An input iterator.
+ * @param __binary_pred A binary predicate @link functors
+ * functor@endlink.
+ * @return A boolean true or false.
+ *
+ * This compares the elements of two ranges using the binary_pred
+ * parameter, and returns true or
+ * false depending on whether all of the corresponding elements of the
+ * ranges are equal.
+ */
+ template<typename _IIter1, typename _IIter2, typename _BinaryPredicate>
+ inline bool
+ equal(_IIter1 __first1, _IIter1 __last1,
+ _IIter2 __first2, _IIter2 __last2, _BinaryPredicate __binary_pred)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_IIter1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_IIter2>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ using _Cat1 = typename iterator_traits<_IIter1>::iterator_category;
+ using _Cat2 = typename iterator_traits<_IIter2>::iterator_category;
+ using _IIter1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
+ using _IIter2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
+ constexpr bool __ra_iters = _IIter1_is_RA() && _IIter1_is_RA();
+ if (__ra_iters)
+ {
+ auto __d1 = std::distance(__first1, __last1);
+ auto __d2 = std::distance(__first2, __last2);
+ if (__d1 != __d2)
+ return false;
+ }
+
+ for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
+ if (!bool(__binary_pred(*__first1, *__first2)))
+ return false;
+ return __ra_iters || (__first1 == __last1 && __first2 == __last2);
+ }
+#endif
+
/**
* @brief Performs @b dictionary comparison on ranges.
* @ingroup sorting_algorithms
@@ -1211,6 +1374,84 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
+#if __cplusplus > 201103L
+ /**
+ * @brief Finds the places in ranges which don't match.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 An input iterator.
+ * @param __last1 An input iterator.
+ * @param __first2 An input iterator.
+ * @param __last2 An input iterator.
+ * @return A pair of iterators pointing to the first mismatch.
+ *
+ * This compares the elements of two ranges using @c == and returns a pair
+ * of iterators. The first iterator points into the first range, the
+ * second iterator points into the second range, and the elements pointed
+ * to by the iterators are not equal.
+ */
+ template<typename _InputIterator1, typename _InputIterator2>
+ pair<_InputIterator1, _InputIterator2>
+ mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+ __glibcxx_function_requires(_EqualOpConcept<
+ typename iterator_traits<_InputIterator1>::value_type,
+ typename iterator_traits<_InputIterator2>::value_type>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ while (__first1 != __last1 && __first2 != __last2
+ && *__first1 == *__first2)
+ {
+ ++__first1;
+ ++__first2;
+ }
+ return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ }
+
+ /**
+ * @brief Finds the places in ranges which don't match.
+ * @ingroup non_mutating_algorithms
+ * @param __first1 An input iterator.
+ * @param __last1 An input iterator.
+ * @param __first2 An input iterator.
+ * @param __last2 An input iterator.
+ * @param __binary_pred A binary predicate @link functors
+ * functor@endlink.
+ * @return A pair of iterators pointing to the first mismatch.
+ *
+ * This compares the elements of two ranges using the binary_pred
+ * parameter, and returns a pair
+ * of iterators. The first iterator points into the first range, the
+ * second iterator points into the second range, and the elements pointed
+ * to by the iterators are not equal.
+ */
+ template<typename _InputIterator1, typename _InputIterator2,
+ typename _BinaryPredicate>
+ pair<_InputIterator1, _InputIterator2>
+ mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
+ _InputIterator2 __first2, _InputIterator2 __last2,
+ _BinaryPredicate __binary_pred)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
+ __glibcxx_requires_valid_range(__first1, __last1);
+ __glibcxx_requires_valid_range(__first2, __last2);
+
+ while (__first1 != __last1 && __first2 != __last2
+ && bool(__binary_pred(*__first1, *__first2)))
+ {
+ ++__first1;
+ ++__first2;
+ }
+ return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
+ }
+#endif
+
_GLIBCXX_END_NAMESPACE_ALGO
} // namespace std
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/1.cc b/libstdc++-v3/testsuite/25_algorithms/equal/1.cc
index 22af765..f8c1355 100644
--- a/libstdc++-v3/testsuite/25_algorithms/equal/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/1.cc
@@ -27,6 +27,8 @@ int array1[] = {0, 1};
int array2[] = {1, 0};
int array3[] = {1, 0};
+bool __attribute__((unused)) test = false;
+
void test1()
{
Container con1(array1, array1);
@@ -45,17 +47,10 @@ void test3()
{
Container con1(array1, array1 + 2);
Container con2(array2, array2 + 2);
- VERIFY( !std::equal(con2.begin(), con2.end(), con1.begin()) );
-}
-
-void test4()
-{
- Container con1(array1, array1 + 2);
- Container con2(array2, array2 + 2);
VERIFY( !std::equal(con1.begin(), con1.end(), con2.begin()) );
}
-void test5()
+void test4()
{
Container con3(array3, array3 + 2);
Container con2(array2, array2 + 2);
@@ -68,5 +63,4 @@ int main()
test2();
test3();
test4();
- test5();
}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/2.cc b/libstdc++-v3/testsuite/25_algorithms/equal/2.cc
new file mode 100644
index 0000000..012609f
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/2.cc
@@ -0,0 +1,193 @@
+// Copyright (C) 2013 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/>.
+
+// 25.2.11 [alg.equal]
+
+// { dg-options "-std=gnu++1y" }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+using __gnu_test::random_access_iterator_wrapper;
+
+typedef test_container<int, input_iterator_wrapper> Container;
+typedef test_container<int, random_access_iterator_wrapper> RA_Container;
+int array1[] = {0, 1};
+int array2[] = {1, 0};
+int array3[] = {1, 0};
+
+struct equal_to
+{
+ static int count;
+
+ bool operator()(int l, int r)
+ {
+ ++count;
+ return l == r;
+ }
+} eq;
+
+int equal_to::count = 0;
+
+bool __attribute__((unused)) test = false;
+
+void test1()
+{
+ const Container con1(array1, array1);
+ const Container con2(array2, array2);
+
+ auto c1 = con1;
+ auto c2 = con2;
+ VERIFY( std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) );
+ VERIFY( equal_to::count == 0 );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 0 );
+}
+
+void test2()
+{
+ const Container con1(array1, array1 + 0);
+ const Container con2(array2, array2 + 2);
+
+ auto c1 = con1;
+ auto c2 = con2;
+ VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 0 );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end()) );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end(), eq) );
+ VERIFY( equal_to::count == 0 );
+}
+
+void test3()
+{
+ const Container con1(array1, array1 + 2);
+ const Container con2(array2, array2 + 2);
+
+ auto c1 = con1;
+ auto c2 = con2;
+ VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end()) );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c1.begin(), c1.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 1 );
+ equal_to::count = 0;
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end()) );
+
+ c1 = con1;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c1.begin(), c1.end(), eq) );
+ VERIFY( equal_to::count == 1 );
+ equal_to::count = 0;
+}
+
+void test4()
+{
+ const Container con3(array3, array3 + 2);
+ const Container con2(array2, array2 + 2);
+
+ auto c3 = con3;
+ auto c2 = con2;
+ VERIFY( std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) );
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 2 );
+ equal_to::count = 0;
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) );
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) );
+ VERIFY( equal_to::count == 2 );
+ equal_to::count = 0;
+}
+
+void test5()
+{
+ const Container con3(array3, array3 + 1);
+ const Container con2(array2, array2 + 2);
+
+ auto c3 = con3;
+ auto c2 = con2;
+ VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) );
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 1 );
+ equal_to::count = 0;
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) );
+
+ c3 = con3;
+ c2 = con2;
+ VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) );
+ VERIFY( equal_to::count == 1 );
+ equal_to::count = 0;
+}
+
+void test6()
+{
+ RA_Container c3(array3, array3 + 1);
+ RA_Container c2(array2, array2 + 2);
+
+ VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end()) );
+
+ VERIFY( !std::equal(c3.begin(), c3.end(), c2.begin(), c2.end(), eq) );
+ VERIFY( equal_to::count == 0 );
+
+ VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end()) );
+
+ VERIFY( !std::equal(c2.begin(), c2.end(), c3.begin(), c3.end(), eq) );
+ VERIFY( equal_to::count == 0 );
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+ test6();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc
new file mode 100644
index 0000000..c80cced
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/equal/check_type2.cc
@@ -0,0 +1,48 @@
+// Copyright (C) 2013 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/>.
+
+// 25.2.11 [alg.equal]
+
+// { dg-do compile }
+// { dg-options " -std=gnu++1y " }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct Lhs2 { };
+
+struct Rhs2 { };
+
+bool
+predicate(const Lhs2&, const Rhs2&) {return true;}
+
+bool
+test1(input_iterator_wrapper<Lhs1>& lhs1,
+ input_iterator_wrapper<Rhs1>& rhs1)
+{ return std::equal(lhs1, lhs1, rhs1, rhs1); }
+
+bool
+test2(input_iterator_wrapper<Lhs2>& lhs2,
+ input_iterator_wrapper<Rhs2>& rhs2)
+{ return std::equal(lhs2, lhs2, rhs2, rhs2, predicate); }
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc
new file mode 100644
index 0000000..d573fa2
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/2.cc
@@ -0,0 +1,115 @@
+// { dg-options "-std=gnu++1y" }
+
+// Copyright (C) 2013 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/>.
+
+// 25.2.12 [alg.is_permutation] Is permutation
+
+#include <algorithm>
+#include <functional>
+#include <testsuite_hooks.h>
+
+struct my_equal_to
+{
+ bool
+ operator()(int __x, int __y) const
+ { return __x % 10 == __y % 10; }
+};
+
+const int arr0[] = { 11, 22, 33, 44, 55 };
+
+void
+do_test(int arr1[5], bool np = true, unsigned N = 5)
+{
+ bool test __attribute__((unused)) = true;
+
+ do
+ VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, arr0 + N) == np );
+ while (std::next_permutation(arr1, arr1 + 5));
+}
+
+template<typename Predicate>
+ void
+ do_test(int arr1[5], Predicate pred, bool np = true, unsigned N = 5)
+ {
+ bool test __attribute__((unused)) = true;
+
+ do
+ VERIFY( std::is_permutation(arr1, arr1 + 5, arr0, arr0 + N, pred) == np );
+ while (std::next_permutation(arr1, arr1 + 5));
+ }
+
+void test01()
+{
+ int arr1[] = { 11, 22, 33, 44, 55 };
+ do_test(arr1);
+ do_test(arr1, false, 4);
+
+ int arr2[] = { 11, 33, 33, 44, 55 };
+ do_test(arr2, false);
+
+ int arr3[] = { 33, 33, 33, 44, 44 };
+ do_test(arr3, false);
+
+ int arr4[] = { 11, 22, 33, 44, 55 };
+ do_test(arr4, std::equal_to<int>());
+ do_test(arr4, std::equal_to<int>(), false, 4);
+
+ int arr5[] = { 11, 33, 33, 44, 55 };
+ do_test(arr5, std::equal_to<int>(), false);
+
+ int arr6[] = { 33, 33, 33, 44, 44 };
+ do_test(arr6, std::equal_to<int>(), false);
+
+ int arr7[] = { 1, 2, 3, 4, 5 };
+ do_test(arr7, my_equal_to());
+ do_test(arr7, my_equal_to(), false, 4);
+
+ int arr8[] = { 1, 3, 3, 4, 5 };
+ do_test(arr8, my_equal_to(), false);
+
+ int arr9[] = { 3, 3, 3, 4, 4 };
+ do_test(arr9, my_equal_to(), false);
+
+ int arr10[] = { 111, 222, 333, 444, 555 };
+ do_test(arr10, my_equal_to());
+ do_test(arr10, my_equal_to(), false, 4);
+
+ int arr11[] = { 1, 222, 33, 4, 55 };
+ do_test(arr11, my_equal_to());
+
+ int arr12[] = { 111, 333, 333, 444, 555 };
+ do_test(arr12, my_equal_to(), false);
+
+ int arr13[] = { 333, 333, 333, 444, 444 };
+ do_test(arr13, my_equal_to(), false);
+}
+
+bool thrower(int, int) { throw 1; }
+
+void test02()
+{
+ int arr[] = { 11, 22, 33 };
+ using namespace std;
+ is_permutation(begin(arr0), end(arr0), begin(arr), end(arr), thrower);
+}
+
+int main()
+{
+ test01();
+ test02();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc
new file mode 100644
index 0000000..9cdf87d
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/is_permutation/check_type2.cc
@@ -0,0 +1,46 @@
+// Copyright (C) 2013 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/>.
+
+// 25.2.12 [alg.is_permutation] Is permutation
+
+// { dg-do compile }
+// { dg-options " -std=gnu++1y " }
+
+#include <algorithm>
+#include <testsuite_iterators.h>
+
+using __gnu_test::forward_iterator_wrapper;
+
+struct X { };
+bool operator==(const X&, const X) { return true; }
+
+struct Y { };
+bool predicate(const Y&, const Y&) { return true; }
+
+bool
+test1(forward_iterator_wrapper<X>& x1,
+ forward_iterator_wrapper<X>& x2)
+{
+ return std::is_permutation(x1, x1, x2, x2);
+}
+
+bool
+test2(forward_iterator_wrapper<Y>& y1,
+ forward_iterator_wrapper<Y>& y2)
+{
+ return std::is_permutation(y1, y1, y2, y2, predicate);
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc
index bcf2f5e..c70d778 100644
--- a/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc
+++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/1.cc
@@ -29,6 +29,8 @@ int array1[] = {0, 1};
int array2[] = {1, 0};
int array3[] = {1, 0, 1};
+bool __attribute__((unused)) test = false;
+
void test1a()
{
Container con1(array1, array1);
diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc
new file mode 100644
index 0000000..4eac4a9
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/2.cc
@@ -0,0 +1,175 @@
+// Copyright (C) 2013 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/>.
+
+// 25.2.10 [mismatch]
+
+// { dg-options " -std=gnu++1y " }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+using __gnu_test::test_container;
+using __gnu_test::input_iterator_wrapper;
+
+typedef test_container<int, input_iterator_wrapper> Container;
+
+int array1[] = {0, 1};
+int array2[] = {1, 0};
+int array3[] = {1, 0, 1};
+
+struct equal_to
+{
+ static int count;
+
+ bool operator()(int l, int r)
+ {
+ ++count;
+ return l == r;
+ }
+} eq;
+
+int equal_to::count = 0;
+
+bool __attribute__((unused)) test = false;
+
+void test1()
+{
+ // empty ranges
+ Container con1(array1, array1);
+ Container con2(array2, array2);
+ auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+ res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+ VERIFY( equal_to::count == 0 );
+}
+
+void test2()
+{
+ // first range empty, second non-empty
+ Container con1(array1, array1);
+ Container con2(array2, array2 + 2);
+ auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+
+ res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+ VERIFY( equal_to::count == 0 );
+}
+
+void test3()
+{
+ // first range non-empty, second empty
+ Container con1(array1, array1 + 2);
+ Container con2(array2, array2);
+ auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+
+ res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+ VERIFY( equal_to::count == 0 );
+}
+
+void test4()
+{
+ // non-empty, mismatching ranges
+ Container con1(array1, array1 + 2);
+ Container con2(array2, array2 + 2);
+ auto res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+
+ con1.bounds.first = array1;
+ con2.bounds.first = array2;
+ res = std::mismatch(con1.begin(), con1.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array1 );
+ VERIFY( res.second.ptr == array2 );
+ VERIFY( equal_to::count == 1 );
+ equal_to::count = 0;
+}
+
+void test5()
+{
+ // non-empty, matching ranges
+ Container con3(array3, array3 + 2);
+ Container con2(array2, array2 + 2);
+ auto res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array3 + 2 );
+ VERIFY( res.second.ptr == array2 + 2 );
+
+ con3.bounds.first = array3;
+ con2.bounds.first = array2;
+ res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array3 + 2 );
+ VERIFY( res.second.ptr == array2 + 2 );
+ VERIFY( equal_to::count == 2 );
+ equal_to::count = 0;
+}
+
+void test6()
+{
+ // non-empty, matching sub-ranges, first range longer
+ Container con3(array3, array3 + 3);
+ Container con2(array2, array2 + 2);
+ auto res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end());
+ VERIFY( res.first.ptr == array3 + 2 );
+ VERIFY( res.second.ptr == array2 + 2 );
+
+ con3.bounds.first = array3;
+ con2.bounds.first = array2;
+ res = std::mismatch(con3.begin(), con3.end(), con2.begin(), con2.end(), eq);
+ VERIFY( res.first.ptr == array3 + 2 );
+ VERIFY( res.second.ptr == array2 + 2 );
+ VERIFY( equal_to::count == 2 );
+ equal_to::count = 0;
+}
+
+void test7()
+{
+ // non-empty, matching sub-ranges, second range longer
+ Container con3(array3, array3 + 3);
+ Container con2(array2, array2 + 2);
+ auto res = std::mismatch(con2.begin(), con2.end(), con3.begin(), con3.end());
+ VERIFY( res.first.ptr == array2 + 2 );
+ VERIFY( res.second.ptr == array3 + 2 );
+
+ con3.bounds.first = array3;
+ con2.bounds.first = array2;
+ res = std::mismatch(con2.begin(), con2.end(), con3.begin(), con3.end(), eq);
+ VERIFY( res.first.ptr == array2 + 2 );
+ VERIFY( res.second.ptr == array3 + 2 );
+ VERIFY( equal_to::count == 2 );
+ equal_to::count = 0;
+}
+
+int main()
+{
+ test1();
+ test2();
+ test3();
+ test4();
+ test5();
+ test6();
+ test7();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc b/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc
new file mode 100644
index 0000000..3ec1f88
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/mismatch/check_type2.cc
@@ -0,0 +1,51 @@
+// Copyright (C) 2005-2013 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/>.
+
+// 25.2.10 [mismatch]
+
+// { dg-options " -std=gnu++1y " }
+// { dg-do compile }
+
+#include <algorithm>
+#include <utility>
+#include <testsuite_iterators.h>
+
+using __gnu_test::input_iterator_wrapper;
+
+struct Lhs1 { };
+
+struct Rhs1 { };
+
+bool operator==(const Lhs1&, const Rhs1&) {return true;}
+
+struct Lhs2 { };
+
+struct Rhs2 { };
+
+bool predicate(const Lhs2&, const Rhs2&) {return true;}
+
+std::pair<input_iterator_wrapper<Lhs1>, input_iterator_wrapper<Rhs1> >
+test1(input_iterator_wrapper<Lhs1>& lhs1, input_iterator_wrapper<Rhs1>& rhs1)
+{
+ return std::mismatch(lhs1, lhs1, rhs1, rhs1);
+}
+
+std::pair<input_iterator_wrapper<Lhs2>, input_iterator_wrapper<Rhs2> >
+test2(input_iterator_wrapper<Lhs2>& lhs2, input_iterator_wrapper<Rhs2>& rhs2)
+{
+ return std::mismatch(lhs2, lhs2, rhs2, rhs2, predicate);
+}
diff --git a/libstdc++-v3/testsuite/util/testsuite_iterators.h b/libstdc++-v3/testsuite/util/testsuite_iterators.h
index 757282b..9bb5858 100644
--- a/libstdc++-v3/testsuite/util/testsuite_iterators.h
+++ b/libstdc++-v3/testsuite/util/testsuite_iterators.h
@@ -116,7 +116,7 @@ namespace __gnu_test
*
* This class takes a pointer and wraps it to provide exactly
* the requirements of a output_iterator. It should not be
- * instansiated directly, but generated from a test_container
+ * instantiated directly, but generated from a test_container
*/
template<class T>
struct output_iterator_wrapper
@@ -177,7 +177,7 @@ namespace __gnu_test
*
* This class takes a pointer and wraps it to provide exactly
* the requirements of a input_iterator. It should not be
- * instansiated directly, but generated from a test_container
+ * instantiated directly, but generated from a test_container
*/
template<class T>
class input_iterator_wrapper
@@ -259,7 +259,7 @@ namespace __gnu_test
*
* This class takes a pointer and wraps it to provide exactly
* the requirements of a forward_iterator. It should not be
- * instansiated directly, but generated from a test_container
+ * instantiated directly, but generated from a test_container
*/
template<class T>
struct forward_iterator_wrapper : public input_iterator_wrapper<T>
@@ -313,7 +313,7 @@ namespace __gnu_test
*
* This class takes a pointer and wraps it to provide exactly
* the requirements of a forward_iterator. It should not be
- * instansiated directly, but generated from a test_container
+ * instantiated directly, but generated from a test_container
*/
template<class T>
struct bidirectional_iterator_wrapper : public forward_iterator_wrapper<T>
@@ -377,7 +377,7 @@ namespace __gnu_test
*
* This class takes a pointer and wraps it to provide exactly
* the requirements of a forward_iterator. It should not be
- * instansiated directly, but generated from a test_container
+ * instantiated directly, but generated from a test_container
*/
template<class T>
struct random_access_iterator_wrapper
More information about the Gcc-patches
mailing list