This is a series of patches essentially adding order statistics directly into pb_ds binary search trees. The main purpose is to resolve PR 81806 (spliting a splay tree needs linear time).
The first patch removes two redundant statements which are confusing. It should be applied anyway, disregarding other patches. The second and third patch together resolve PR 81806. The fourth patch converts the point_iterator of rb_tree and splay_tree based maps to random access iterator. With the subtree size kept we can implement the operators required by random access iterator in logarithm time. The fifth patch moves the functionality of tree_order_statistics_node_update into the implementation of binary search trees (they are now order-statistics trees), makes tree_order_statistics_node_update no-op, and deprecates it. Tested with `make check-target-libstdc++` in a non-bootstrap GCC build. GCC does not use pb_ds so it should be unnecessary to run a bootstrap. -- Xi Ruoyao <xry...@mengyan1223.wang> School of Aerospace Science and Technology, Xidian University
