From 24edf8ef4b5cbb8afabc081b9b196f05868a5364 Mon Sep 17 00:00:00 2001 From: Marshall Clow Date: Mon, 1 Jul 2019 19:22:00 +0000 Subject: [PATCH] Implement P0646R1: Erase-Like Algorithms Should Return size_type. Reviewed as https://reviews.llvm.org/D58332, and then updated because I rewrote a couple of those routines to eliminate some UB. Thanks to Zoe for tghe patch. llvm-svn: 364840 --- libcxx/include/forward_list | 43 ++++++++++++++-------- libcxx/include/list | 34 ++++++++--------- .../forwardlist/forwardlist.ops/remove.pass.cpp | 24 ++++++------ .../forwardlist/forwardlist.ops/remove_if.pass.cpp | 20 +++++----- .../forwardlist/forwardlist.ops/unique.pass.cpp | 20 +++++----- .../sequences/list/list.ops/remove.pass.cpp | 8 ++-- .../sequences/list/list.ops/remove_if.pass.cpp | 6 +-- .../sequences/list/list.ops/unique.pass.cpp | 4 +- 8 files changed, 84 insertions(+), 75 deletions(-) diff --git a/libcxx/include/forward_list b/libcxx/include/forward_list index 6316de9..055da1b 100644 --- a/libcxx/include/forward_list +++ b/libcxx/include/forward_list @@ -120,10 +120,10 @@ public: const_iterator first, const_iterator last); void splice_after(const_iterator p, forward_list&& x, const_iterator first, const_iterator last); - void remove(const value_type& v); - template void remove_if(Predicate pred); - void unique(); - template void unique(BinaryPredicate binary_pred); + size_type remove(const value_type& v); + template size_type remove_if(Predicate pred); + size_type unique(); + template size_type unique(BinaryPredicate binary_pred); void merge(forward_list& x); void merge(forward_list&& x); template void merge(forward_list& x, Compare comp); @@ -819,11 +819,11 @@ public: void splice_after(const_iterator __p, forward_list& __x, const_iterator __i); void splice_after(const_iterator __p, forward_list& __x, const_iterator __f, const_iterator __l); - void remove(const value_type& __v); - template void remove_if(_Predicate __pred); + size_type remove(const value_type& __v); + template size_type remove_if(_Predicate __pred); _LIBCPP_INLINE_VISIBILITY - void unique() {unique(__equal_to());} - template void unique(_BinaryPredicate __binary_pred); + size_type unique() {return unique(__equal_to());} + template size_type unique(_BinaryPredicate __binary_pred); #ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY void merge(forward_list&& __x) {merge(__x, __less());} @@ -1496,18 +1496,20 @@ forward_list<_Tp, _Alloc>::splice_after(const_iterator __p, } template -void +typename forward_list<_Tp, _Alloc>::size_type forward_list<_Tp, _Alloc>::remove(const value_type& __v) { forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing - iterator __e = end(); + typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; + const iterator __e = end(); for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) { if (__i.__get_begin()->__next_->__value_ == __v) { + ++__count_removed; iterator __j = _VSTD::next(__i, 2); for (; __j != __e && *__j == __v; ++__j) - ; + ++__count_removed; __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); if (__j == __e) break; @@ -1516,22 +1518,26 @@ forward_list<_Tp, _Alloc>::remove(const value_type& __v) else ++__i; } + + return __count_removed; } template template -void +typename forward_list<_Tp, _Alloc>::size_type forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) { forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing - iterator __e = end(); + typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; + const iterator __e = end(); for (iterator __i = before_begin(); __i.__get_begin()->__next_ != nullptr;) { if (__pred(__i.__get_begin()->__next_->__value_)) { + ++__count_removed; iterator __j = _VSTD::next(__i, 2); for (; __j != __e && __pred(*__j); ++__j) - ; + ++__count_removed; __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); if (__j == __e) break; @@ -1540,23 +1546,28 @@ forward_list<_Tp, _Alloc>::remove_if(_Predicate __pred) else ++__i; } + + return __count_removed; } template template -void +typename forward_list<_Tp, _Alloc>::size_type forward_list<_Tp, _Alloc>::unique(_BinaryPredicate __binary_pred) { forward_list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing + typename forward_list<_Tp, _Alloc>::size_type __count_removed = 0; for (iterator __i = begin(), __e = end(); __i != __e;) { iterator __j = _VSTD::next(__i); for (; __j != __e && __binary_pred(*__i, *__j); ++__j) - ; + ++__count_removed; if (__i.__get_begin()->__next_ != __j.__get_unsafe_node_pointer()) __deleted_nodes.splice_after(__deleted_nodes.before_begin(), *this, __i, __j); __i = __j; } + + return __count_removed; } template diff --git a/libcxx/include/list b/libcxx/include/list index 9c4851d..cbc165b 100644 --- a/libcxx/include/list +++ b/libcxx/include/list @@ -129,11 +129,11 @@ public: void splice(const_iterator position, list&& x, const_iterator first, const_iterator last); - void remove(const value_type& value); - template void remove_if(Pred pred); - void unique(); + size_type remove(const value_type& value); + template size_type remove_if(Pred pred); + size_type unique(); template - void unique(BinaryPredicate binary_pred); + size_type unique(BinaryPredicate binary_pred); void merge(list& x); void merge(list&& x); template @@ -1070,12 +1070,12 @@ public: void splice(const_iterator __p, list& __c, const_iterator __i); void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l); - void remove(const value_type& __x); - template void remove_if(_Pred __pred); + size_type remove(const value_type& __x); + template size_type remove_if(_Pred __pred); _LIBCPP_INLINE_VISIBILITY - void unique(); + size_type unique() { return unique(__equal_to()); } template - void unique(_BinaryPred __binary_pred); + size_type unique(_BinaryPred __binary_pred); _LIBCPP_INLINE_VISIBILITY void merge(list& __c); #ifndef _LIBCPP_CXX03_LANG @@ -2141,7 +2141,7 @@ list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, con } template -void +typename list<_Tp, _Alloc>::size_type list<_Tp, _Alloc>::remove(const value_type& __x) { list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing @@ -2160,11 +2160,13 @@ list<_Tp, _Alloc>::remove(const value_type& __x) else ++__i; } + + return __deleted_nodes.size(); } template template -void +typename list<_Tp, _Alloc>::size_type list<_Tp, _Alloc>::remove_if(_Pred __pred) { list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing @@ -2183,19 +2185,13 @@ list<_Tp, _Alloc>::remove_if(_Pred __pred) else ++__i; } -} -template -inline -void -list<_Tp, _Alloc>::unique() -{ - unique(__equal_to()); + return __deleted_nodes.size(); } template template -void +typename list<_Tp, _Alloc>::size_type list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) { list<_Tp, _Alloc> __deleted_nodes(get_allocator()); // collect the nodes we're removing @@ -2209,6 +2205,8 @@ list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred) __i = __j; } } + + return __deleted_nodes.size(); } template diff --git a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove.pass.cpp index 3b5e4a2..87f3050 100644 --- a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove.pass.cpp +++ b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove.pass.cpp @@ -37,7 +37,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 4); assert(c1 == c2); } { @@ -46,7 +46,7 @@ int main(int, char**) const T t1[] = {0, 0, 0, 0}; C c1(std::begin(t1), std::end(t1)); C c2; - c1.remove(0); + assert(c1.remove(0) == 4); assert(c1 == c2); } { @@ -56,7 +56,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 0); assert(c1 == c2); } { @@ -64,7 +64,7 @@ int main(int, char**) typedef std::forward_list C; C c1; C c2; - c1.remove(0); + assert(c1.remove(0) == 0); assert(c1 == c2); } { @@ -74,7 +74,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 1); assert(c1 == c2); } { // LWG issue #526 @@ -84,7 +84,7 @@ int main(int, char**) int t2[] = { 2, 3, 5, 8, 11}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(c1.front()); + assert(c1.remove(c1.front()) == 2); assert(c1 == c2); } { @@ -95,7 +95,7 @@ int main(int, char**) C c; for(int *ip = std::end(t1); ip != std::begin(t1);) c.push_front(S(*--ip)); - c.remove(c.front()); + assert(c.remove(c.front()) == 3); C::const_iterator it = c.begin(); for(int *ip = std::begin(t2); ip != std::end(t2); ++ip, ++it) { assert ( it != c.end()); @@ -111,7 +111,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 4); assert(c1 == c2); } { @@ -120,7 +120,7 @@ int main(int, char**) const T t1[] = {0, 0, 0, 0}; C c1(std::begin(t1), std::end(t1)); C c2; - c1.remove(0); + assert(c1.remove(0) == 4); assert(c1 == c2); } { @@ -130,7 +130,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 0); assert(c1 == c2); } { @@ -138,7 +138,7 @@ int main(int, char**) typedef std::forward_list> C; C c1; C c2; - c1.remove(0); + assert(c1.remove(0) == 0); assert(c1 == c2); } { @@ -148,7 +148,7 @@ int main(int, char**) const T t2[] = {5, 5, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.remove(0); + assert(c1.remove(0) == 1); assert(c1 == c2); } #endif diff --git a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove_if.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove_if.pass.cpp index 2a4f079..486d355 100644 --- a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove_if.pass.cpp +++ b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/remove_if.pass.cpp @@ -45,7 +45,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 4); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -57,7 +57,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2; Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 4); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -70,7 +70,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 0); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -81,7 +81,7 @@ int main(int, char**) C c1; C c2; Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 0); assert(c1 == c2); assert(cp.count() == 0); } @@ -94,7 +94,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 1); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -123,7 +123,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 4); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -135,7 +135,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2; Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 4); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -148,7 +148,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 0); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } @@ -159,7 +159,7 @@ int main(int, char**) C c1; C c2; Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 0); assert(c1 == c2); assert(cp.count() == 0); } @@ -172,7 +172,7 @@ int main(int, char**) C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); Predicate cp(g); - c1.remove_if(std::ref(cp)); + assert(c1.remove_if(std::ref(cp)) == 1); assert(c1 == c2); assert(cp.count() == static_cast(std::distance(std::begin(t1), std::end(t1)))); } diff --git a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/unique.pass.cpp b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/unique.pass.cpp index 6ce2da5..32aa8f9 100644 --- a/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/unique.pass.cpp +++ b/libcxx/test/std/containers/sequences/forwardlist/forwardlist.ops/unique.pass.cpp @@ -26,7 +26,7 @@ int main(int, char**) const T t2[] = {0, 5, 0, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 3); assert(c1 == c2); } { @@ -36,7 +36,7 @@ int main(int, char**) const T t2[] = {0}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 3); assert(c1 == c2); } { @@ -46,7 +46,7 @@ int main(int, char**) const T t2[] = {5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 2); assert(c1 == c2); } { @@ -54,7 +54,7 @@ int main(int, char**) typedef std::forward_list C; C c1; C c2; - c1.unique(); + assert(c1.unique() == 0); assert(c1 == c2); } { @@ -64,7 +64,7 @@ int main(int, char**) const T t2[] = {5, 0}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 2); assert(c1 == c2); } #if TEST_STD_VER >= 11 @@ -75,7 +75,7 @@ int main(int, char**) const T t2[] = {0, 5, 0, 5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 3); assert(c1 == c2); } { @@ -85,7 +85,7 @@ int main(int, char**) const T t2[] = {0}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 3); assert(c1 == c2); } { @@ -95,7 +95,7 @@ int main(int, char**) const T t2[] = {5}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 2); assert(c1 == c2); } { @@ -103,7 +103,7 @@ int main(int, char**) typedef std::forward_list> C; C c1; C c2; - c1.unique(); + assert(c1.unique() == 0); assert(c1 == c2); } { @@ -113,7 +113,7 @@ int main(int, char**) const T t2[] = {5, 0}; C c1(std::begin(t1), std::end(t1)); C c2(std::begin(t2), std::end(t2)); - c1.unique(); + assert(c1.unique() == 2); assert(c1 == c2); } #endif diff --git a/libcxx/test/std/containers/sequences/list/list.ops/remove.pass.cpp b/libcxx/test/std/containers/sequences/list/list.ops/remove.pass.cpp index dab23f0..19a8817 100644 --- a/libcxx/test/std/containers/sequences/list/list.ops/remove.pass.cpp +++ b/libcxx/test/std/containers/sequences/list/list.ops/remove.pass.cpp @@ -37,7 +37,7 @@ int main(int, char**) { int a1[] = {1, 2, 3, 4}; int a2[] = {1, 2, 4}; std::list c(a1, a1 + 4); - c.remove(3); + assert(c.remove(3) == 1); assert(c == std::list(a2, a2 + 3)); } { // LWG issue #526 @@ -53,7 +53,7 @@ int main(int, char**) { std::list c; for (int *ip = a1; ip < a1 + 8; ++ip) c.push_back(S(*ip)); - c.remove(c.front()); + assert(c.remove(c.front()) == 3); std::list::const_iterator it = c.begin(); for (int *ip = a2; ip < a2 + 5; ++ip, ++it) { assert(it != c.end()); @@ -67,7 +67,7 @@ int main(int, char**) { int a1[] = {1, 2, 3, 4}; int a2[] = {1, 2, 4}; List c(a1, a1 + 4, Alloc::create()); - c.remove(3); + assert(c.remove(3) == 1); assert(c == List(a2, a2 + 3, Alloc::create())); } #if TEST_STD_VER >= 11 @@ -75,7 +75,7 @@ int main(int, char**) { int a1[] = {1, 2, 3, 4}; int a2[] = {1, 2, 4}; std::list> c(a1, a1 + 4); - c.remove(3); + assert(c.remove(3) == 1); assert((c == std::list>(a2, a2 + 3))); } #endif diff --git a/libcxx/test/std/containers/sequences/list/list.ops/remove_if.pass.cpp b/libcxx/test/std/containers/sequences/list/list.ops/remove_if.pass.cpp index 3724235..d78f7db 100644 --- a/libcxx/test/std/containers/sequences/list/list.ops/remove_if.pass.cpp +++ b/libcxx/test/std/containers/sequences/list/list.ops/remove_if.pass.cpp @@ -46,7 +46,7 @@ int main(int, char**) int a2[] = {3, 4}; std::list c(a1, a1+4); Predicate cp(g); - c.remove_if(std::ref(cp)); + assert(c.remove_if(std::ref(cp)) == 2); assert(c == std::list(a2, a2+2)); assert(cp.count() == 4); } @@ -55,7 +55,7 @@ int main(int, char**) int a2[] = {1, 3}; std::list c(a1, a1+4); Predicate cp(even); - c.remove_if(std::ref(cp)); + assert(c.remove_if(std::ref(cp)) == 2); assert(c == std::list(a2, a2+2)); assert(cp.count() == 4); } @@ -78,7 +78,7 @@ int main(int, char**) int a2[] = {3, 4}; std::list> c(a1, a1+4); Predicate cp(g); - c.remove_if(std::ref(cp)); + assert(c.remove_if(std::ref(cp)) == 2); assert((c == std::list>(a2, a2+2))); assert(cp.count() == 4); } diff --git a/libcxx/test/std/containers/sequences/list/list.ops/unique.pass.cpp b/libcxx/test/std/containers/sequences/list/list.ops/unique.pass.cpp index 90f0fd2..dc80d03 100644 --- a/libcxx/test/std/containers/sequences/list/list.ops/unique.pass.cpp +++ b/libcxx/test/std/containers/sequences/list/list.ops/unique.pass.cpp @@ -22,7 +22,7 @@ int main(int, char**) int a1[] = {2, 1, 1, 4, 4, 4, 4, 3, 3}; int a2[] = {2, 1, 4, 3}; std::list c(a1, a1+sizeof(a1)/sizeof(a1[0])); - c.unique(); + assert(c.unique() == 5); assert(c == std::list(a2, a2+4)); } #if TEST_STD_VER >= 11 @@ -30,7 +30,7 @@ int main(int, char**) int a1[] = {2, 1, 1, 4, 4, 4, 4, 3, 3}; int a2[] = {2, 1, 4, 3}; std::list> c(a1, a1+sizeof(a1)/sizeof(a1[0])); - c.unique(); + assert(c.unique() == 5); assert((c == std::list>(a2, a2+4))); } #endif -- 2.7.4