[Bug libstdc++/108556] New: std::sort changes objects' member values

[Bug libstdc++/108556] New: std::sort changes objects' member values

[gnu.iodaj at simplelogin dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108556

            Bug ID: 108556
           Summary: std::sort changes objects' member values
           Product: gcc
           Version: 11.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gnu.iodaj at simplelogin dot com
  Target Milestone: ---

When working on a project, I tried using std::sort to sort a vector of objects,
and it resulted in a crash. After looking closer, valgrind reports lots of
invalid writes and the data is effectively modified during the sort.

This issue doesn't happen with stable_sort nor with small enough vectors.

The g++ versions tested are 11.3.0 and 12.1.0.

The system is a Dell Precision 5570 running Linux Mint 21.

g++ command is g++ -Wall -Wextra sort-bug.cpp (file in attachment)

The compiler output is none (no warnings, no errors, no line displayed)

Please find the attached file that serves as a minimal working example of this
bug.

Thank you.

[Bug libstdc++/108556] std::sort changes objects' member values

[gnu.iodaj at simplelogin dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108556

--- Comment #1 from gnu.iodaj at simplelogin dot com ---
Created attachment 54347
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=54347&action=edit
source file

[Bug libstdc++/108556] std::sort changes objects' member values

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108556

--- Comment #2 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Compiling with -D_GLIBCXX_DEBUG shows the problem:

/home/jwakely/gcc/13/include/c++/13.0.1/bits/stl_algo.h:4892:
In function:
    void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = 
    gnu_debug::_Safe_iterator<gnu_cxx::normal_iterator<Item*, vector<Item, 
    allocator<Item> > >, debug::vector<Item>, random_access_iterator_tag>; 
    _Compare = main()::<lambda(const Item&, const Item&)>]

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Objects involved in the operation:
    instance "functor" @ 0x7ffee875415f {
      type = main::{lambda(Item const&, Item const&)#1};
    }
    iterator::value_type "ordered type"  {
      type = Item;
    }
Aborted (core dumped)


Your comparison function fails to meet the requirements of a strict weak
ordering, so your program has undefined behaviour.

https://www.boost.org/sgi/stl/StrictWeakOrdering.html
https://en.cppreference.com/w/cpp/named_req/Compare

[Bug libstdc++/108556] std::sort changes objects' member values

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108556

Jonathan Wakely <redi at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #3 from Jonathan Wakely <redi at gcc dot gnu.org> ---
  std::sort(items.begin(), items.end(), [](const Item &i, const Item &j) {
    return i.getHeight() >= j.getHeight();
  });

The bug is here. For a strict weak ordering cmp(x, x) must be false, because an
object must no be ordered before/after itself. Your lambda fails that
requirement, because it returns true when called with equivalent values.

[Bug libstdc++/108556] std::sort changes objects' member values

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=108556

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|INVALID                     |DUPLICATE

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
dup

*** This bug has been marked as a duplicate of bug 553 ***