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

[Xi Ruoyao]

> 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.

The patch is attached.

libstdc++-v3/ChangeLog:

	* include/Makefile.am: Add
	  include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
	  and
	  include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp,
	  remove
	  include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp.
	* include/Makefile.in: Regenerate.
	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
	  (PB_DS_BIN_TREE_NAME::find_by_order): Declare new member function.
	  (PB_DS_BIN_TREE_NAME::order_of_key): Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
	  (PB_DS_OV_TREE_NAME::find_by_order): Likewise.
	  (PB_DS_OV_TREE_NAME::order_of_key): Likewise.
	* include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp:
	  New file.
	  (PB_DS_CLASS_C_DEC::find_by_order): Implement.
	  (PB_DS_CLASS_C_DEC::order_of_key): Likewise.
	* include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp:
	  New file.
	  (PB_DS_CLASS_C_DEC::find_by_order): Implement.
	  (PB_DS_CLASS_C_DEC::order_of_key): Likewise.
	* include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp:
	  Delete.
	* include/ext/pb_ds/tree_policy.hpp
	  (tree_order_statistics_node_update): Make it noop, and deprecate.
	* testsuite/ext/pb_ds/example/tree_order_statistics.cc:
	  Remove the usage of deprecated tree_order_statistics_node_update.
	* testsuite/ext/pb_ds/example/tree_order_statistics_join.cc:
	  Likewise.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0005-libstdc-implement-order-statistics-function-in-pb_ds.patch
Type: text/x-patch
Size: 19628 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200713/a6a4b9be/attachment-0001.bin>