}
}
-#ifdef __GXX_EXPERIMENTAL_CXX0X__
/// This is an overload used by find_if_not() for the Input Iterator case.
template<typename _InputIterator, typename _Predicate>
inline _InputIterator
return __last;
}
}
-#endif
+
+ /// Provided for stable_partition to use.
+ template<typename _InputIterator, typename _Predicate>
+ inline _InputIterator
+ __find_if_not(_InputIterator __first, _InputIterator __last,
+ _Predicate __pred)
+ {
+ return std::__find_if_not(__first, __last, __pred,
+ std::__iterator_category(__first));
+ }
+
+ /// Like find_if_not(), but uses and updates a count of the
+ /// remaining range length instead of comparing against an end
+ /// iterator.
+ template<typename _InputIterator, typename _Predicate, typename _Distance>
+ _InputIterator
+ __find_if_not_n(_InputIterator __first, _Distance& __len, _Predicate __pred)
+ {
+ for (; __len; --__len, ++__first)
+ if (!bool(__pred(*__first)))
+ break;
+ return __first;
+ }
// set_difference
// set_intersection
__glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
typename iterator_traits<_InputIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
- return std::__find_if_not(__first, __last, __pred,
- std::__iterator_category(__first));
+ return std::__find_if_not(__first, __last, __pred);
}
/**
// partition
/// This is a helper function...
+ /// Requires __len != 0 and !__pred(*__first),
+ /// same as __stable_partition_adaptive.
template<typename _ForwardIterator, typename _Predicate, typename _Distance>
_ForwardIterator
__inplace_stable_partition(_ForwardIterator __first,
- _ForwardIterator __last,
_Predicate __pred, _Distance __len)
{
if (__len == 1)
- return __pred(*__first) ? __last : __first;
+ return __first;
_ForwardIterator __middle = __first;
std::advance(__middle, __len / 2);
- _ForwardIterator __begin = std::__inplace_stable_partition(__first,
- __middle,
- __pred,
- __len / 2);
- _ForwardIterator __end = std::__inplace_stable_partition(__middle, __last,
- __pred,
- __len
- - __len / 2);
- std::rotate(__begin, __middle, __end);
- std::advance(__begin, std::distance(__middle, __end));
- return __begin;
+ _ForwardIterator __left_split =
+ std::__inplace_stable_partition(__first, __pred, __len / 2);
+ // Advance past true-predicate values to satisfy this
+ // function's preconditions.
+ _Distance __right_len = __len - __len / 2;
+ _ForwardIterator __right_split =
+ std::__find_if_not_n(__middle, __right_len, __pred);
+ if (__right_len)
+ __right_split = std::__inplace_stable_partition(__middle,
+ __pred,
+ __right_len);
+ std::rotate(__left_split, __middle, __right_split);
+ std::advance(__left_split, std::distance(__middle, __right_split));
+ return __left_split;
}
/// This is a helper function...
+ /// Requires __first != __last and !__pred(*__first)
+ /// and __len == distance(__first, __last).
+ ///
+ /// !__pred(*__first) allows us to guarantee that we don't
+ /// move-assign an element onto itself.
template<typename _ForwardIterator, typename _Pointer, typename _Predicate,
typename _Distance>
_ForwardIterator
{
_ForwardIterator __result1 = __first;
_Pointer __result2 = __buffer;
+ // The precondition guarantees that !__pred(*__first), so
+ // move that element to the buffer before starting the loop.
+ // This ensures that we only call __pred once per element.
+ *__result2 = _GLIBCXX_MOVE(*__first);
+ ++__result2;
+ ++__first;
for (; __first != __last; ++__first)
if (__pred(*__first))
{
{
_ForwardIterator __middle = __first;
std::advance(__middle, __len / 2);
- _ForwardIterator __begin =
+ _ForwardIterator __left_split =
std::__stable_partition_adaptive(__first, __middle, __pred,
__len / 2, __buffer,
__buffer_size);
- _ForwardIterator __end =
- std::__stable_partition_adaptive(__middle, __last, __pred,
- __len - __len / 2,
- __buffer, __buffer_size);
- std::rotate(__begin, __middle, __end);
- std::advance(__begin, std::distance(__middle, __end));
- return __begin;
+ // Advance past true-predicate values to satisfy this
+ // function's preconditions.
+ _Distance __right_len = __len - __len / 2;
+ _ForwardIterator __right_split =
+ std::__find_if_not_n(__middle, __right_len, __pred);
+ if (__right_len)
+ __right_split =
+ std::__stable_partition_adaptive(__right_split, __last, __pred,
+ __right_len,
+ __buffer, __buffer_size);
+ std::rotate(__left_split, __middle, __right_split);
+ std::advance(__left_split, std::distance(__middle, __right_split));
+ return __left_split;
}
}
typename iterator_traits<_ForwardIterator>::value_type>)
__glibcxx_requires_valid_range(__first, __last);
+ __first = std::__find_if_not(__first, __last, __pred);
+
if (__first == __last)
return __first;
else
_DistanceType(__buf.size()));
else
return
- std::__inplace_stable_partition(__first, __last, __pred,
+ std::__inplace_stable_partition(__first, __pred,
_DistanceType(__buf.requested_size()));
}
}
const int B[] = {2, 4, 6, 8, 10, 12, 14, 16, 1, 3, 5, 7, 9, 11, 13, 15, 17};
const int N = sizeof(A) / sizeof(int);
+// Check that starting with a true predicate works too. (PR52822)
+const int A2[] = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17};
+const int B2[] = {2, 4, 6, 8, 10, 12, 14, 16, 3, 5, 7, 9, 11, 13, 15, 17};
+const int N2 = sizeof(A2) / sizeof(int);
+
struct Pred
{
bool
{ return (x.val % 2) == 0; }
};
-// 25.2.12 stable_partition()
+// 25.2.12 stable_partition(), starting with a false predicate.
void
test01()
{
VERIFY( std::equal(s1, s1 + N, B) );
}
+// 25.2.12 stable_partition(), starting with a true predicate.
+void
+test02()
+{
+ bool test __attribute__((unused)) = true;
+
+ rvalstruct s1[N2];
+ std::copy(A2, A2 + N2, s1);
+ Container con(s1, s1 + N2);
+
+ std::stable_partition(con.begin(), con.end(), Pred());
+ VERIFY( std::equal(s1, s1 + N2, B2) );
+}
+
int
main()
{
test01();
+ test02();
return 0;
}
--- /dev/null
+// { dg-options "-std=gnu++0x" }
+
+// Copyright (C) 2012 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 Pred 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 [lib.alg.partitions] Partitions.
+
+#include <algorithm>
+#include <vector>
+#include <testsuite_hooks.h>
+
+bool true_vector_pred(const std::vector<int>&) { return true; }
+
+void
+test01()
+{
+ std::vector<std::vector<int> > v(1);
+ v[0].push_back(7);
+ VERIFY( v[0].size() == 1 );
+ std::stable_partition(v.begin(), v.end(), &true_vector_pred);
+ VERIFY( v[0].size() == 1 );
+}
+
+int
+main()
+{
+ test01();
+ return 0;
+}
OSDN Git Service
