libstdc++: Fix debug mode for pb_ds ordered-vector trees
Fixes rare debug mode assertions in pb_ds ordered-vector trees that could be triggered by time-based seeds or incorrect memory allocation.
This commit addresses rare debug mode assertions in libstdc++‘s policy-based data structures (pb_ds) ordered-vector trees. It introduces a way to override the time-based random seed for reliable failure triggering and fixes an exception-safety bug in erase_if where container modifications were not rolled back. Additionally, it corrects an issue in erase(It) that caused a crash when deallocating the last element and makes copy_from_ordered_range safer by preventing allocation of zero-sized memory.
In Details
The pb_ds library's ov_tree implementation has debug assertions that can fail. This commit makes these assertions more reliable by allowing external seeding of the random number generator used for testing. It also fixes exception-safety issues in erase_if and an off-by-one error in erase(It) which could lead to memory corruption or assertion failures.
- pb_ds
- Policy-Based Data Structures, a library within GCC's libstdc++ that allows users to customize data structure behavior through various policies.
- ordered-vector trees
- A specific data structure within pb_ds that offers efficient ordered operations using a tree-based implementation, optimized for certain access patterns.
- exception-safety
- Guarantees provided by a function or operation regarding the state of the program if an exception is thrown. Strong exception safety means the program remains unchanged; basic guarantees mean it remains in a valid, though possibly altered, state.