libstdc++: Make forward_list::sort exception-safe [PR124051]
Ensures std::forward_list::sort is exception-safe, preventing memory leaks or cycles on comparison exceptions.
The std::forward_list::sort implementation has been made exception-safe. Previously, if the comparison function threw an exception after the list’s internal pointers were rearranged, it could lead to unreachable nodes or cycles. The updated code now ensures the list is properly reconnected and all nodes remain reachable before propagating any exception.
In Details
This commit improves the exception safety of std::forward_list::sort. The algorithm uses a bottom-up merge sort, temporarily maintaining partially merged lists via local pointers while the container's head still points into the original structure. If a comparison operation throws an exception after internal links have been modified but before the container head is updated, it could result in a disconnected list or a cycle, rendering nodes unreachable. The fix ensures that the merged prefix and remaining runs are correctly reconnected, the container head is updated, and then the exception is…
- forward_list
- A C++ standard library container providing a singly linked list. It offers constant time insertion and deletion but lacks efficient random access.
- exception-safe
- A guarantee that a piece of code will maintain its invariants and not leak resources even if an exception is thrown during its execution. Strong exception safety ensures that if an operation fails, the program state is rolled back to what it was before the operation began.
- bottom-up merge sort
- A merge sort variant that starts by merging small sorted sublists and progressively combines them into larger sorted lists until the entire list is sorted.
- iterator
- An object that points to an element in a container and allows traversal through the container's elements.