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

[Xi Ruoyao]

> 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 patch is attached.

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
	  (bin_search_tree_const_it_::size_type): New typedef.
	  (bin_search_tree_it_::difference_type): Likewise.
	  (bin_search_tree_const_it_::inc): New overloads.
	  (bin_search_tree_const_it_::dec): Likewise.
	  (bin_search_tree_const_it_::order): New member function.
	  (bin_search_tree_const_it_::operator+=): New operator.
	  (bin_search_tree_const_it_::operator-=): Likewise.
	  (bin_search_tree_const_it_::operator+): Likewise.
	  (bin_search_tree_const_it_::operator-): Likewise.
	  (bin_search_tree_const_it_::operator<): Likewise.
	  (bin_search_tree_const_it_::operator<=): Likewise.
	  (bin_search_tree_const_it_::operator>): Likewise.
	  (bin_search_tree_const_it_::operator>=): Likewise.
	  (bin_search_tree_const_it_::operator[]): Likewise.
	  (bin_search_tree_it_::operator+=): Likewise.
	  (bin_search_tree_it_::operator-=): Likewise.
	  (bin_search_tree_it_::operator+): Likewise.
	  (bin_search_tree_it_::operator-): Likewise.
	  (bin_search_tree_it_::operator[]): Likewise.
	  (bin_search_tree_const_it_::iterator_category):
	  Change to std::random_access_iterator_tag.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0004-libstdc-make-pb_ds-binary-search-tree-point-iterator.patch
Type: text/x-patch
Size: 10475 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200713/c4607d58/attachment.bin>