mbox series

[0/5] libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806)

Message ID 67798e6881dcc5612ef31ac6b98586dfa5d83695.camel@mengyan1223.wang
Headers show
Series libstdc++: keep subtree sizes in pb_ds binary search trees (PR 81806) | expand

Message

Xi Ruoyao July 13, 2020, 8:37 a.m. UTC 
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.

Comments

Xi Ruoyao July 13, 2020, 8:39 a.m. UTC | #1 
> The first patch removes two redundant statements which are confusing.  It
> should
> be applied anyway, disregarding other patches.

The patch is attached, to prevent my mail client from destroying it :(.

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
	  (insert_leaf_new, insert_imp_empty): remove redundant statements.