From 8c7100650ef446af8a46ac14042d6ae4a8abd5a6 Mon Sep 17 00:00:00 2001 From: Jonathan Wakely Date: Wed, 17 Apr 2019 22:47:20 +0100 Subject: [PATCH] PR libstdc++/90105 make forward_list::sort stable While testing the fix I also discovered that operator== assumes the elements are comparable with operator!= which is not required. PR libstdc++/90105 * include/bits/forward_list.h (operator==): Do not use operator!= to compare elements. (forward_list::sort(Comp)): When elements are equal take the one earlier in the list, so that sort is stable. * testsuite/23_containers/forward_list/operations/90105.cc: New test. * testsuite/23_containers/forward_list/comparable.cc: Test with types that meet the minimum EqualityComparable and LessThanComparable requirements. Remove irrelevant comment. From-SVN: r270427 --- libstdc++-v3/ChangeLog | 10 ++++ libstdc++-v3/include/bits/forward_list.tcc | 6 +- .../23_containers/forward_list/comparable.cc | 44 +++++++++++--- .../forward_list/operations/90105.cc | 60 +++++++++++++++++++ 4 files changed, 110 insertions(+), 10 deletions(-) create mode 100644 libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index 0d5e490befe..fb35a14e1a9 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,5 +1,15 @@ 2019-04-17 Jonathan Wakely + PR libstdc++/90105 + * include/bits/forward_list.h (operator==): Do not use operator!= to + compare elements. + (forward_list::sort(Comp)): When elements are equal take the one + earlier in the list, so that sort is stable. + * testsuite/23_containers/forward_list/operations/90105.cc: New test. + * testsuite/23_containers/forward_list/comparable.cc: Test with + types that meet the minimum EqualityComparable and LessThanComparable + requirements. Remove irrelevant comment. + * include/std/variant (__detail::__variant::_Traits::_S_copy_assign): Do not depend on whether all alternative types are move constructible. (__detail::__variant::_Copy_assign_base::operator=): Remove cv-quals diff --git a/libstdc++-v3/include/bits/forward_list.tcc b/libstdc++-v3/include/bits/forward_list.tcc index 4fac52a8438..088111e3330 100644 --- a/libstdc++-v3/include/bits/forward_list.tcc +++ b/libstdc++-v3/include/bits/forward_list.tcc @@ -399,7 +399,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER auto __iy = __ly.cbegin(); while (__ix != __lx.cend() && __iy != __ly.cend()) { - if (*__ix != *__iy) + if (!(*__ix == *__iy)) return false; ++__ix; ++__iy; @@ -469,9 +469,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER __p = static_cast<_Node*>(__p->_M_next); --__psize; } - else if (__comp(*__p->_M_valptr(), *__q->_M_valptr())) + else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr())) { - // First node of p is lower; e must come from p. + // First node of q is not lower; e must come from p. __e = __p; __p = static_cast<_Node*>(__p->_M_next); --__psize; diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc index cd921b7bc6b..252d9b5a423 100644 --- a/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc +++ b/libstdc++-v3/testsuite/23_containers/forward_list/comparable.cc @@ -17,15 +17,11 @@ // with this library; see the file COPYING3. If not see // . - -// NOTE: This makes use of the fact that we know how moveable -// is implemented on list (via swap). If the implementation changed -// this test may begin to fail. - #include #include -int main() +void +test01() { std::forward_list a = {0.0, 1.0, 2.0, 3.0, 4.0}; std::forward_list b = {0.0, 1.0, 2.0, 3.0, 4.0, 5.0}; @@ -43,6 +39,40 @@ int main() VERIFY((b > a) == true); VERIFY((b >= a) == true); VERIFY((b <= a) == false); +} + +void +test02() +{ + // The EqualityComparable requirements only require == + struct X { + bool operator==(const X&) const { return true; } + }; + + std::forward_list a(2); + const auto b = a; + VERIFY( a == b ); +} + +void +test03() +{ + // The LessThanComparable requirements only require < + struct X { + bool operator<(const X&) const { return false; } + }; - return 0; + std::forward_list a(2); + const auto b = a; + VERIFY( !(a < b) ); + VERIFY( !(a > b) ); + VERIFY( a <= b ); + VERIFY( a >= b ); +} + +int main() +{ + test01(); + test02(); + test03(); } diff --git a/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc new file mode 100644 index 00000000000..3c1478e2e34 --- /dev/null +++ b/libstdc++-v3/testsuite/23_containers/forward_list/operations/90105.cc @@ -0,0 +1,60 @@ +// Copyright (C) 2019 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 +// . + +// { dg-do run { target c++11 } } + +#include +#include + +// PR libstdc++/90105 - std::forward_list::sort() is not "stable" + +struct X +{ + int key; + int val; +}; + +bool operator<(const X& l, const X& r) +{ return l.key < r.key; } + +bool operator==(const X& l, const X& r) +{ return l.key == r.key && l.val == r.val; } + +void +test01() +{ + std::forward_list l{ {1, 1}, {2, 2}, {1, 3}, {0, 4}, {2, 5}, {0, 6} }; + l.sort(); + std::forward_list exp{ {0, 4}, {0, 6}, {1, 1}, {1, 3}, {2, 2}, {2, 5} }; + VERIFY( l == exp ); +} + +void +test02() +{ + std::forward_list l{ {1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6} }; + const std::forward_list exp = l; + l.sort(); + VERIFY( l == exp ); +} + +int +main() +{ + test01(); + test02(); +} -- 2.30.2