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

[Xi Ruoyao]

> The second and third patch together resolve PR 81806.

The attached patch keeps the subtree size in binary search tree nodes.

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/rb_tree_map_/node.hpp
	  (rb_tree_node_::size_type): New typedef.
	  (rb_tree_node_::m_subtree_size): New field.
	* include/ext/pb_ds/detail/splay_tree_map_/node.hpp
	  (splay_tree_node_::size_type): New typedef.
	  (splay_tree_node_::m_subtree_size): New field.
	* include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
	  (PB_DS_BIN_TREE_NAME::update_subtree_size): Declare new member
	  function.
	* include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
	  (update_subtree_size): Define.
	  (apply_update, update_to_top): Call update_subtree_size.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0002-libstdc-maintain-subtree-size-in-pb_ds-binary-search.patch
Type: text/x-patch
Size: 6211 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200713/9a544e8a/attachment.bin>