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

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

[Xi Ruoyao]

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 <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 469 bytes --]


> 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.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University

[-- Attachment #2: 0001-libstdc-remove-two-redundant-statements-in-pb_ds-bin.patch --]
[-- Type: text/x-patch, Size: 1498 bytes --]

From 4eea45261ebf974ddf02f6154166c5cb6aa180da Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Fri, 10 Jul 2020 20:10:52 +0800
Subject: [PATCH 1/5] libstdc++: remove two redundant statements in pb_ds
 binary tree

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
	  (insert_leaf_new, insert_imp_empty): remove redundant statements.
---
 .../ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp        | 2 --
 1 file changed, 2 deletions(-)

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
index 3942da05600..bdc10379af6 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
@@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
     }
 
   p_new_nd->m_p_parent = p_nd;
-  p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
   PB_DS_ASSERT_NODE_CONSISTENT(p_nd)
 
   update_to_top(p_new_nd, (node_update* )this);
@@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value)
     m_p_head->m_p_parent = p_new_node;
 
   p_new_node->m_p_parent = m_p_head;
-  p_new_node->m_p_left = p_new_node->m_p_right = 0;
   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
 
   update_to_top(m_p_head->m_p_parent, (node_update*)this);
-- 
2.27.0

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 540 bytes --]

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

Please ignore a previous duplication of this mail with wrong title :(.

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
	  (insert_leaf_new, insert_imp_empty): remove redundant statements.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University

[-- Attachment #2: 0001-libstdc-remove-two-redundant-statements-in-pb_ds-bin.patch --]
[-- Type: text/x-patch, Size: 1498 bytes --]

From 4eea45261ebf974ddf02f6154166c5cb6aa180da Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Fri, 10 Jul 2020 20:10:52 +0800
Subject: [PATCH 1/5] libstdc++: remove two redundant statements in pb_ds
 binary tree

libstdc++-v3/ChangeLog:

	* include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
	  (insert_leaf_new, insert_imp_empty): remove redundant statements.
---
 .../ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp        | 2 --
 1 file changed, 2 deletions(-)

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
index 3942da05600..bdc10379af6 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp
@@ -122,7 +122,6 @@ insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd)
     }
 
   p_new_nd->m_p_parent = p_nd;
-  p_new_nd->m_p_left = p_new_nd->m_p_right = 0;
   PB_DS_ASSERT_NODE_CONSISTENT(p_nd)
 
   update_to_top(p_new_nd, (node_update* )this);
@@ -142,7 +141,6 @@ insert_imp_empty(const_reference r_value)
     m_p_head->m_p_parent = p_new_node;
 
   p_new_node->m_p_parent = m_p_head;
-  p_new_node->m_p_left = p_new_node->m_p_right = 0;
   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value));)
 
   update_to_top(m_p_head->m_p_parent, (node_update*)this);
-- 
2.27.0

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 851 bytes --]


> 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

[-- Attachment #2: 0002-libstdc-maintain-subtree-size-in-pb_ds-binary-search.patch --]
[-- Type: text/x-patch, Size: 6211 bytes --]

From 248ab526b766070d348d676ebf9f9c7b16c3a93e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Fri, 10 Jul 2020 20:58:04 +0800
Subject: [PATCH 2/5] libstdc++: maintain subtree size in pb_ds binary search
 trees

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.
---
 .../bin_search_tree_/bin_search_tree_.hpp     |  3 ++
 .../bin_search_tree_/rotate_fn_imps.hpp       | 31 ++++++++++++++++---
 .../ext/pb_ds/detail/rb_tree_map_/node.hpp    |  8 +++++
 .../ext/pb_ds/detail/splay_tree_/node.hpp     |  8 +++++
 4 files changed, 46 insertions(+), 4 deletions(-)

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
index 32dcb6ee020..38a3bab0444 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
@@ -304,6 +304,9 @@ namespace __gnu_pbds
       inline void
       rotate_parent(node_pointer);
 
+      inline void
+      update_subtree_size(node_pointer);
+
       inline void
       apply_update(node_pointer, null_node_update_pointer);
 
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
index 1f18243a859..72ccfeb16a2 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp
@@ -122,8 +122,23 @@ rotate_parent(node_pointer p_nd)
 PB_DS_CLASS_T_DEC
 inline void
 PB_DS_CLASS_C_DEC::
-apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
-{ }
+update_subtree_size(node_pointer p_nd)
+{
+  size_type size = 1;
+  if (p_nd->m_p_left)
+    size += p_nd->m_p_left->m_subtree_size;
+  if (p_nd->m_p_right)
+    size += p_nd->m_p_right->m_subtree_size;
+  p_nd->m_subtree_size = size;
+}
+
+PB_DS_CLASS_T_DEC
+inline void
+PB_DS_CLASS_C_DEC::
+apply_update(node_pointer p_nd, null_node_update_pointer /*p_update*/)
+{
+  update_subtree_size(p_nd);
+}
 
 PB_DS_CLASS_T_DEC
 template<typename Node_Update_>
@@ -131,6 +146,7 @@ inline void
 PB_DS_CLASS_C_DEC::
 apply_update(node_pointer p_nd, Node_Update_*  /*p_update*/)
 {
+  update_subtree_size(p_nd);
   node_update::operator()(node_iterator(p_nd),
 			  node_const_iterator(static_cast<node_pointer>(0)));
 }
@@ -152,7 +168,14 @@ update_to_top(node_pointer p_nd, Node_Update_* p_update)
 PB_DS_CLASS_T_DEC
 inline void
 PB_DS_CLASS_C_DEC::
-update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/)
-{ }
+update_to_top(node_pointer p_nd, null_node_update_pointer /*p_update */)
+{
+  while (p_nd != m_p_head)
+    {
+      update_subtree_size(p_nd);
+
+      p_nd = p_nd->m_p_parent;
+    }
+}
 
 #endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
index de2d92a59b6..802562ad4f2 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_/node.hpp
@@ -58,6 +58,9 @@ namespace __gnu_pbds
       typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
 	node_pointer;
 
+      typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type
+	size_type;
+
       typedef typename rebind_traits<_Alloc, metadata_type>::reference
 	metadata_reference;
 
@@ -88,6 +91,7 @@ namespace __gnu_pbds
       node_pointer 	m_p_left;
       node_pointer 	m_p_right;
       node_pointer 	m_p_parent;
+      size_type 	m_subtree_size;
       value_type 	m_value;
       bool 		m_red;
       metadata_type 	m_metadata;
@@ -100,6 +104,9 @@ namespace __gnu_pbds
       typedef Value_Type 		value_type;
       typedef null_type 	metadata_type;
 
+      typedef typename rebind_traits<_Alloc, rb_tree_node_>::size_type
+	size_type;
+
       typedef typename rebind_traits<_Alloc, rb_tree_node_>::pointer
 	node_pointer;
 
@@ -116,6 +123,7 @@ namespace __gnu_pbds
       node_pointer 	m_p_left;
       node_pointer 	m_p_right;
       node_pointer 	m_p_parent;
+      size_type 	m_subtree_size;
       value_type 	m_value;
       bool 		m_red;
     };
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
index 5c7b5d43c2b..d83b44deaae 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/splay_tree_/node.hpp
@@ -56,6 +56,9 @@ namespace __gnu_pbds
       typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
 	node_pointer;
 
+      typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type
+	size_type;
+
       typedef typename rebind_traits<_Alloc, metadata_type>::reference
 	metadata_reference;
 
@@ -85,6 +88,7 @@ namespace __gnu_pbds
       node_pointer m_p_left;
       node_pointer m_p_right;
       node_pointer m_p_parent;
+      size_type m_subtree_size;
       metadata_type m_metadata;
     };
 
@@ -98,6 +102,9 @@ namespace __gnu_pbds
       typedef typename rebind_traits<_Alloc, splay_tree_node_>::pointer
 	node_pointer;
 
+      typedef typename rebind_traits<_Alloc, splay_tree_node_>::size_type
+	size_type;
+
       inline bool
       special() const
       { return m_special; }
@@ -111,6 +118,7 @@ namespace __gnu_pbds
       node_pointer m_p_left;
       node_pointer m_p_right;
       node_pointer m_p_parent;
+      size_type m_subtree_size;
       value_type m_value;
       bool m_special;
     };
-- 
2.27.0

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 480 bytes --]


> The second and third patch together resolve PR 81806.

The attached patch modifies split_finish to use the subtree size we maintained
in the previous patch, resolving libstdc++/81806.

libstdc++-v3/ChangeLog:

	PR libstdc++/81806
	* include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
	  (split_finish): Use maintained size, instead of calling
	  std::distance.
-- 
Xi Ruoyao <xry111@mengyan1223.wang>
School of Aerospace Science and Technology, Xidian University

[-- Attachment #2: 0003-libstdc-use-maintained-size-when-split-pb_ds-binary-.patch --]
[-- Type: text/x-patch, Size: 1351 bytes --]

From 4434da1b2b45797204f4fd978dcc4fbba4b17c6e Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Fri, 10 Jul 2020 21:38:09 +0800
Subject: [PATCH 3/5] libstdc++: use maintained size when split pb_ds binary
 search trees

libstdc++-v3/ChangeLog:

	PR libstdc++/81806
	* include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
	  (split_finish): Use maintained size, instead of calling
	  std::distance.
---
 .../ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp  | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
index d08288f186d..fb924b4434b 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp
@@ -133,7 +133,9 @@ PB_DS_CLASS_C_DEC::
 split_finish(PB_DS_CLASS_C_DEC& other)
 {
   other.initialize_min_max();
-  other.m_size = std::distance(other.begin(), other.end());
+  other.m_size = 0;
+  if (other.m_p_head->m_p_parent != 0)
+    other.m_size = other.m_p_head->m_p_parent->m_subtree_size;
   m_size -= other.m_size;
   initialize_min_max();
   PB_DS_ASSERT_VALID((*this))
-- 
2.27.0

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 1537 bytes --]


> 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

[-- Attachment #2: 0004-libstdc-make-pb_ds-binary-search-tree-point-iterator.patch --]
[-- Type: text/x-patch, Size: 10475 bytes --]

From 5149d3156b0b1ae5d8cf82c54d041bd47451c995 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Sat, 11 Jul 2020 23:32:36 +0800
Subject: [PATCH 4/5] libstdc++: make pb_ds binary search tree point iterator
 random accessible

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.
---
 .../bin_search_tree_/point_iterators.hpp      | 277 +++++++++++++++++-
 1 file changed, 276 insertions(+), 1 deletion(-)

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
index eb2f4fdbfd2..f7efe79290a 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
@@ -105,8 +105,9 @@ namespace __gnu_pbds
     class bin_search_tree_const_it_
     {
     public:
-      typedef std::bidirectional_iterator_tag 		iterator_category;
+      typedef std::random_access_iterator_tag 		iterator_category;
       typedef typename _Alloc::difference_type 	difference_type;
+      typedef typename _Alloc::size_type		size_type;
       typedef Value_Type 				value_type;
       typedef Pointer 					pointer;
       typedef Const_Pointer 				const_pointer;
@@ -185,6 +186,28 @@ namespace __gnu_pbds
 	return ret_it;
       }
 
+      inline PB_DS_TREE_CONST_IT_C_DEC&
+      operator+=(difference_type dif)
+      {
+        inc(dif, integral_constant<int,Is_Forward_Iterator>());
+        return *this;
+      }
+
+      inline PB_DS_TREE_CONST_IT_C_DEC
+      operator+(difference_type dif) const
+      {
+        PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+        ret_it += dif;
+        return ret_it;
+      }
+
+      inline PB_DS_TREE_CONST_IT_C_DEC&
+      operator-=(difference_type dif)
+      {
+        dec(dif, integral_constant<int,Is_Forward_Iterator>());
+        return *this;
+      }
+
       inline PB_DS_TREE_CONST_IT_C_DEC& 
       operator--()
       {
@@ -200,6 +223,54 @@ namespace __gnu_pbds
 	return ret_it;
       }
 
+      inline PB_DS_TREE_CONST_IT_C_DEC
+      operator-(difference_type dif) const
+      {
+        PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+        ret_it -= dif;
+        return ret_it;
+      }
+
+      inline const_reference
+      operator[](difference_type dif) const
+      {
+        return *operator+(dif);
+      }
+
+      inline bool
+      operator<(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+      {
+        return order() < rhs.order();
+      }
+
+      inline bool
+      operator<=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+      {
+        return order() <= rhs.order();
+      }
+
+      inline bool
+      operator>(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+      {
+        return order() >= rhs.order();
+      }
+
+      inline bool
+      operator>=(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+      {
+        return order() >= rhs.order();
+      }
+
+      inline difference_type
+      operator-(const PB_DS_TREE_CONST_IT_C_DEC &rhs) const
+      {
+        size_type r = order(), l = rhs.order();
+        if (r >= l)
+          return static_cast<difference_type>(r - l);
+        else
+          return -static_cast<difference_type>(l - r);
+      }
+
     protected:
       inline void
       inc(false_type)
@@ -266,6 +337,171 @@ namespace __gnu_pbds
 	  m_p_nd = p_y;
       }
 
+      Node_Pointer find_by_order_in_subtree(size_type order)
+      {
+        Node_Pointer p_nd = m_p_nd;
+
+        while (p_nd != 0)
+          {
+            Node_Pointer p_left = p_nd->m_p_left;
+            const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+            if (order == o)
+              break;
+            else if (order < o)
+              p_nd = p_left;
+            else
+              {
+                order -= o + 1;
+                p_nd = p_nd->m_p_right;
+              }
+          }
+
+        return p_nd;
+      }
+
+      inline void
+      inc(difference_type dif, false_type)
+      { dec(dif, true_type()); }
+
+      void
+      inc(difference_type dif, true_type)
+      {
+        if (dif < 0)
+          {
+            dec(-dif, true_type());
+            return;
+          }
+
+        size_type d = static_cast<size_type>(dif);
+
+        if (d != 0 &&
+            m_p_nd->special() &&
+            m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+          {
+            --d;
+            m_p_nd = m_p_nd->m_p_left;
+          }
+
+        while (d != 0)
+          {
+            Node_Pointer p_right = m_p_nd->m_p_right;
+            const size_type o = (p_right == 0 ? 0 : p_right->m_subtree_size);
+
+            if (o >= d)
+              {
+                m_p_nd = m_p_nd->m_p_right;
+                m_p_nd = find_by_order_in_subtree(d - 1);
+                break;
+              }
+
+            d -= o + 1;
+
+            while (m_p_nd == m_p_nd->m_p_parent->m_p_right)
+              m_p_nd = m_p_nd->m_p_parent;
+
+            m_p_nd = m_p_nd->m_p_parent;
+          }
+      }
+
+      inline void
+      dec(difference_type dif, false_type)
+      { inc(dif, true_type()); }
+
+      void
+      dec(difference_type dif, true_type)
+      {
+        if (dif < 0)
+          {
+            inc(-dif, true_type());
+            return;
+          }
+
+        size_type d = static_cast<size_type>(dif);
+
+        if (d != 0 &&
+            m_p_nd->special() &&
+            m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+          {
+            --d;
+            m_p_nd = m_p_nd->m_p_right;
+          }
+
+        while (d != 0)
+          {
+            Node_Pointer p_left = m_p_nd->m_p_left;
+            const size_type o = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+            if (o >= d)
+              {
+                m_p_nd = m_p_nd->m_p_left;
+                m_p_nd = find_by_order_in_subtree(o - d);
+                break;
+              }
+
+            d -= o + 1;
+
+            while (m_p_nd == m_p_nd->m_p_parent->m_p_left)
+              m_p_nd = m_p_nd->m_p_parent;
+
+            m_p_nd = m_p_nd->m_p_parent;
+          }
+      }
+
+      inline size_type
+      order() const
+      {
+        return order(integral_constant<int, Is_Forward_Iterator>());
+      }
+
+      size_type
+      order(true_type) const
+      {
+        if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+          return m_p_nd->m_p_parent->m_subtree_size;
+
+        Node_Pointer p_left = m_p_nd->m_p_left;
+        size_type ret = (p_left == 0 ? 0 : p_left->m_subtree_size);
+
+        for (Node_Pointer p_nd = m_p_nd;
+             p_nd->m_p_parent->m_p_parent != p_nd;
+             p_nd = p_nd->m_p_parent)
+        {
+          if (p_nd->m_p_parent->m_p_right == p_nd)
+            {
+              ret += 1;
+              if (p_nd->m_p_parent->m_p_left != 0)
+                ret += p_nd->m_p_parent->m_p_left->m_subtree_size;
+            }
+        }
+
+        return ret;
+      }
+
+      size_type
+      order(false_type) const
+      {
+        if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+          return m_p_nd->m_p_parent->m_subtree_size;
+
+        Node_Pointer p_right = m_p_nd->m_p_right;
+        size_type ret = (p_right == 0 ? 0 : p_right->m_subtree_size);
+
+        for (Node_Pointer p_nd = m_p_nd;
+             p_nd->m_p_parent->m_p_parent != p_nd;
+             p_nd = p_nd->m_p_parent)
+        {
+          if (p_nd->m_p_parent->m_p_left == p_nd)
+            {
+              ret += 1;
+              if (p_nd->m_p_parent->m_p_right != 0)
+                ret += p_nd->m_p_parent->m_p_right->m_subtree_size;
+            }
+        }
+
+        return ret;
+      }
+
     public:
       Node_Pointer m_p_nd;
     };
@@ -282,6 +518,8 @@ namespace __gnu_pbds
     class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
     {
     public:
+      typedef typename _Alloc::difference_type difference_type;
+
       inline
       bin_search_tree_it_(const Node_Pointer p_nd = 0) 
       : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
@@ -337,6 +575,21 @@ namespace __gnu_pbds
 	return ret_it;
       }
 
+      inline PB_DS_TREE_IT_C_DEC&
+      operator+=(difference_type dif)
+      {
+        PB_DS_TREE_CONST_IT_C_DEC:: operator+=(dif);
+        return *this;
+      }
+
+      inline PB_DS_TREE_IT_C_DEC
+      operator+(difference_type dif) const
+      {
+        PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+        ret_it += dif;
+        return ret_it;
+      }
+
       inline PB_DS_TREE_IT_C_DEC& 
       operator--()
       {
@@ -352,8 +605,30 @@ namespace __gnu_pbds
 	return ret_it;
       }
 
+      inline PB_DS_TREE_IT_C_DEC&
+      operator-=(difference_type dif)
+      {
+        PB_DS_TREE_CONST_IT_C_DEC:: operator-=(dif);
+        return *this;
+      }
+
+      inline PB_DS_TREE_IT_C_DEC
+      operator-(difference_type dif) const
+      {
+        PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+        ret_it -= dif;
+        return ret_it;
+      }
+
+      inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
+      operator[](difference_type dif) const
+      {
+        return *operator+(dif);
+      }
+
     protected:
       typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
+
     };
 
 #undef PB_DS_TREE_CONST_IT_C_DEC
-- 
2.27.0

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

[Xi Ruoyao]

[-- Attachment #1: Type: text/plain, Size: 1763 bytes --]


> 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

[-- Attachment #2: 0005-libstdc-implement-order-statistics-function-in-pb_ds.patch --]
[-- Type: text/x-patch, Size: 19628 bytes --]

From c0ee85f492872ba164ad3c1c9636aace1de02e96 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?X=E2=84=B9=20Ruoyao?= <xry111@mengyan1223.wang>
Date: Sun, 12 Jul 2020 16:12:18 +0800
Subject: [PATCH 5/5] libstdc++: implement order statistics function in pb_ds
 tree maps

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.
---
 libstdc++-v3/include/Makefile.am              |  3 +-
 libstdc++-v3/include/Makefile.in              |  3 +-
 .../bin_search_tree_/bin_search_tree_.hpp     | 10 +++
 .../order_statistics_imps.hpp}                | 50 ++++-------
 .../ov_tree_map_/order_statistics_imps.hpp    | 77 ++++++++++++++++
 .../detail/ov_tree_map_/ov_tree_map_.hpp      | 10 +++
 .../include/ext/pb_ds/tree_policy.hpp         | 88 ++-----------------
 .../pb_ds/example/tree_order_statistics.cc    |  9 +-
 .../example/tree_order_statistics_join.cc     |  4 +-
 9 files changed, 125 insertions(+), 129 deletions(-)
 rename libstdc++-v3/include/ext/pb_ds/detail/{tree_policy/order_statistics_imp.hpp => bin_search_tree_/order_statistics_imps.hpp} (71%)
 create mode 100644 libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp

diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am
index e131ce04f8c..604821ecda2 100644
--- a/libstdc++-v3/include/Makefile.am
+++ b/libstdc++-v3/include/Makefile.am
@@ -365,6 +365,7 @@ pb_headers2 = \
 	${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \
+	${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/traits.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \
@@ -467,6 +468,7 @@ pb_headers4 = \
 	${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \
+	${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp
 
@@ -551,7 +553,6 @@ pb_headers7 = \
 	${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
 	${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
 	${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-	${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
 	${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
 	${pb_srcdir}/detail/tree_trace_base.hpp \
 	${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
diff --git a/libstdc++-v3/include/Makefile.in b/libstdc++-v3/include/Makefile.in
index c0b71e13a32..f7b2c136dbf 100644
--- a/libstdc++-v3/include/Makefile.in
+++ b/libstdc++-v3/include/Makefile.in
@@ -711,6 +711,7 @@ pb_headers2 = \
 	${pb_srcdir}/detail/bin_search_tree_/r_erase_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/rotate_fn_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/split_join_fn_imps.hpp \
+	${pb_srcdir}/detail/bin_search_tree_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/bin_search_tree_/traits.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cc_ht_map_.hpp \
 	${pb_srcdir}/detail/cc_hash_table_map_/cmp_fn_imps.hpp \
@@ -813,6 +814,7 @@ pb_headers4 = \
 	${pb_srcdir}/detail/ov_tree_map_/info_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/insert_fn_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/iterators_fn_imps.hpp \
+	${pb_srcdir}/detail/ov_tree_map_/order_statistics_imps.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/node_iterators.hpp \
 	${pb_srcdir}/detail/ov_tree_map_/ov_tree_map_.hpp
 
@@ -897,7 +899,6 @@ pb_headers7 = \
 	${pb_srcdir}/detail/thin_heap_/thin_heap_.hpp \
 	${pb_srcdir}/detail/thin_heap_/trace_fn_imps.hpp \
 	${pb_srcdir}/detail/tree_policy/node_metadata_selector.hpp \
-	${pb_srcdir}/detail/tree_policy/order_statistics_imp.hpp \
 	${pb_srcdir}/detail/tree_policy/sample_tree_node_update.hpp \
 	${pb_srcdir}/detail/tree_trace_base.hpp \
 	${pb_srcdir}/detail/trie_policy/node_metadata_selector.hpp \
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
index 38a3bab0444..d76e822516b 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp
@@ -238,6 +238,15 @@ namespace __gnu_pbds
       inline const_reverse_iterator
       rend() const;
 
+      inline iterator
+      find_by_order(size_type order);
+
+      inline const_iterator
+      find_by_order(size_type order) const;
+
+      inline size_type
+      order_of_key(key_const_reference r_key) const;
+
       /// Returns a const node_iterator corresponding to the node at the
       /// root of the tree.
       inline node_const_iterator
@@ -411,6 +420,7 @@ namespace __gnu_pbds
 #include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp>
+#include <ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp>
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
similarity index 71%
rename from libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp
rename to libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
index a31d5985d18..6358c79c3ba 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/order_statistics_imps.hpp
@@ -34,8 +34,8 @@
 // warranty.
 
 /**
- * @file tree_policy/order_statistics_imp.hpp
- * Contains forward declarations for order_statistics_key
+ * @file bin_search_tree_/order_statistics_imps.hpp
+ * Contains an implementation class for bin_search_tree_.
  */
 
 #ifdef PB_DS_CLASS_C_DEC
@@ -51,20 +51,20 @@ find_by_order(size_type order)
   while (it != end_it)
     {
       node_iterator l_it = it.get_l_child();
-      const size_type o = (l_it == end_it)? 0 : l_it.get_metadata();
+      const size_type o = (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size;
 
       if (order == o)
-	return *it;
+        return *it;
       else if (order < o)
-	it = l_it;
+        it = l_it;
       else
         {
-	  order -= o + 1;
-	  it = it.get_r_child();
+          order -= o + 1;
+          it = it.get_r_child();
         }
     }
 
-  return base_type::end_iterator();
+  return iterator(m_p_head);
 }
 
 PB_DS_CLASS_T_DEC
@@ -87,38 +87,20 @@ order_of_key(key_const_reference r_key) const
     {
       node_const_iterator l_it = it.get_l_child();
 
-      if (r_cmp_fn(r_key, this->extract_key(*(*it))))
-	it = l_it;
-      else if (r_cmp_fn(this->extract_key(*(*it)), r_key))
+      if (r_cmp_fn(r_key, PB_DS_V2F(*(*it))))
+        it = l_it;
+      else if (r_cmp_fn(PB_DS_V2F(*(*it)),
+                        r_key))
         {
-	  ord += (l_it == end_it)? 1 : 1 + l_it.get_metadata();
-	  it = it.get_r_child();
+          ord += (l_it == end_it)? 1 : 1 + l_it.m_p_nd->m_subtree_size;
+          it = it.get_r_child();
         }
       else
         {
-	  ord += (l_it == end_it)? 0 : l_it.get_metadata();
-	  it = end_it;
+          ord += (l_it == end_it)? 0 : l_it.m_p_nd->m_subtree_size;
+          it = end_it;
         }
     }
   return ord;
 }
-
-PB_DS_CLASS_T_DEC
-inline void
-PB_DS_CLASS_C_DEC::
-operator()(node_iterator node_it, node_const_iterator end_nd_it) const
-{
-  node_iterator l_it = node_it.get_l_child();
-  const size_type l_rank = (l_it == end_nd_it) ? 0 : l_it.get_metadata();
-
-  node_iterator r_it = node_it.get_r_child();
-  const size_type r_rank = (r_it == end_nd_it) ? 0 : r_it.get_metadata();
-
-  const_cast<metadata_reference>(node_it.get_metadata())= 1 + l_rank + r_rank;
-}
-
-PB_DS_CLASS_T_DEC
-PB_DS_CLASS_C_DEC::
-~tree_order_statistics_node_update()
-{ }
 #endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp
new file mode 100644
index 00000000000..69c0d543b4c
--- /dev/null
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp
@@ -0,0 +1,77 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005-2020 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file bin_search_tree_/order_statistics_imps.hpp
+ * Contains an implementation class for bin_search_tree_.
+ */
+
+#ifdef PB_DS_CLASS_C_DEC
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::iterator
+PB_DS_CLASS_C_DEC::
+find_by_order(size_type order)
+{
+  if (order < m_size)
+    return iterator(&m_a_values[order]);
+
+  return end();
+}
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::const_iterator
+PB_DS_CLASS_C_DEC::
+find_by_order(size_type order) const
+{ return const_cast<PB_DS_CLASS_C_DEC*>(this)->find_by_order(order); }
+
+PB_DS_CLASS_T_DEC
+inline typename PB_DS_CLASS_C_DEC::size_type
+PB_DS_CLASS_C_DEC::
+order_of_key(key_const_reference r_key) const
+{
+  pointer it = m_a_values;
+  pointer e_it = m_a_values + m_size;
+  while (it != e_it)
+    {
+      pointer mid_it = it + ((e_it - it) >> 1);
+      if (cmp_fn::operator()(PB_DS_V2F(*mid_it), r_key))
+        it = ++mid_it;
+      else
+        e_it = mid_it;
+    }
+  return (size_type)(it - m_a_values);
+}
+#endif
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
index 79ca5b30051..6dfc329eb7e 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp
@@ -382,6 +382,15 @@ namespace __gnu_pbds
       end() const
       { return m_end_it; }
 
+      inline iterator
+      find_by_order(size_type order);
+
+      inline const_iterator
+      find_by_order(size_type order) const;
+
+      inline size_type
+      order_of_key(key_const_reference r_key) const;
+
       /// Returns a const node_iterator corresponding to the node at the
       /// root of the tree.
       inline node_const_iterator
@@ -529,6 +538,7 @@ namespace __gnu_pbds
 #include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
 #include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
 #include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
+#include <ext/pb_ds/detail/ov_tree_map_/order_statistics_imps.hpp>
 #include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 
 #undef PB_DS_CLASS_C_DEC
diff --git a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
index e76b56a9454..1b769578fee 100644
--- a/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/tree_policy.hpp
@@ -55,99 +55,21 @@ namespace __gnu_pbds
 #define PB_DS_CLASS_C_DEC \
   tree_order_statistics_node_update<Node_CItr, Node_Itr, Cmp_Fn, _Alloc>
 
-#define PB_DS_BRANCH_POLICY_BASE \
-  detail::branch_policy<Node_CItr, Node_Itr, _Alloc>
-
-  /// Functor updating ranks of entrees.
   template<typename Node_CItr, typename Node_Itr, 
 	   typename Cmp_Fn, typename _Alloc>
-  class tree_order_statistics_node_update : private PB_DS_BRANCH_POLICY_BASE
+  class __attribute__((__deprecated__)) tree_order_statistics_node_update
   {
-  private:
-    typedef PB_DS_BRANCH_POLICY_BASE 		       	base_type;
-
   public:
-    typedef Cmp_Fn 					cmp_fn;
-    typedef _Alloc 					allocator_type;
-    typedef typename allocator_type::size_type 		size_type;
-    typedef typename base_type::key_type 		key_type;
-    typedef typename base_type::key_const_reference 	key_const_reference;
-
-    typedef size_type 					metadata_type;
-    typedef Node_CItr 	       			node_const_iterator;
-    typedef Node_Itr 					node_iterator;
-    typedef typename node_const_iterator::value_type 	const_iterator;
-    typedef typename node_iterator::value_type 		iterator;
-
-    /// Finds an entry by __order. Returns a const_iterator to the
-    /// entry with the __order order, or a const_iterator to the
-    /// container object's end if order is at least the size of the
-    /// container object.
-    inline const_iterator
-    find_by_order(size_type) const;
-
-    /// Finds an entry by __order. Returns an iterator to the entry
-    /// with the __order order, or an iterator to the container
-    /// object's end if order is at least the size of the container
-    /// object.
-    inline iterator
-    find_by_order(size_type);
-
-    /// Returns the order of a key within a sequence. For exapmle, if
-    /// r_key is the smallest key, this method will return 0; if r_key
-    /// is a key between the smallest and next key, this method will
-    /// return 1; if r_key is a key larger than the largest key, this
-    /// method will return the size of r_c.
-    inline size_type
-    order_of_key(key_const_reference) const;
-
-  private:
-    /// Const reference to the container's value-type.
-    typedef typename base_type::const_reference 	const_reference;
-
-    /// Const pointer to the container's value-type.
-    typedef typename base_type::const_pointer 		const_pointer;
-
-    /// Const metadata reference.
-    typedef typename detail::rebind_traits<_Alloc, metadata_type>::const_reference
-      metadata_const_reference;
-
-    /// Metadata reference.
-    typedef typename detail::rebind_traits<_Alloc, metadata_type>::reference
-      metadata_reference;
-
-    /// Returns the node_const_iterator associated with the tree's root node.
-    virtual node_const_iterator
-    node_begin() const = 0;
-
-    /// Returns the node_iterator associated with the tree's root node.
-    virtual node_iterator
-    node_begin() = 0;
-
-    /// Returns the node_const_iterator associated with a just-after leaf node.
-    virtual node_const_iterator
-    node_end() const = 0;
-
-    /// Returns the node_iterator associated with a just-after leaf node.
-    virtual node_iterator
-    node_end() = 0;
-
-    /// Access to the cmp_fn object.
-    virtual cmp_fn& 
-    get_cmp_fn() = 0;
+    typedef null_type metadata_type;
 
-  protected:
-    /// Updates the rank of a node through a node_iterator node_it;
-    /// end_nd_it is the end node iterator.
     inline void
-    operator()(node_iterator, node_const_iterator) const;
+    operator()(Node_CItr, Node_Itr) {}
 
+  protected:
     virtual
-    ~tree_order_statistics_node_update();
+    ~tree_order_statistics_node_update() {}
   };
 
-#include <ext/pb_ds/detail/tree_policy/order_statistics_imp.hpp>
-
 #undef PB_DS_CLASS_T_DEC
 #undef PB_DS_CLASS_C_DEC
 #undef PB_DS_BRANCH_POLICY_BASE
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
index cf4b357bff6..7a2f6f5a234 100644
--- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics.cc
@@ -45,23 +45,18 @@
 
 #include <cassert>
 #include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
 
 using namespace std;
 using namespace __gnu_pbds;
 
 // A red-black tree table storing ints and their order
-// statistics. Note that since the tree uses
-// tree_order_statistics_node_update as its update policy, then it
-// includes its methods by_order and order_of_key.
+// statistics.
 typedef
 tree<
   int,
   null_type,
   less<int>,
-  rb_tree_tag,
-  // This policy updates nodes' metadata for order statistics.
-  tree_order_statistics_node_update>
+  rb_tree_tag>
 set_t;
 
 int main()
diff --git a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
index 2fc51ccdf6c..f8fc45a4344 100644
--- a/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
+++ b/libstdc++-v3/testsuite/ext/pb_ds/example/tree_order_statistics_join.cc
@@ -42,7 +42,6 @@
 
 #include <cassert>
 #include <ext/pb_ds/assoc_container.hpp>
-#include <ext/pb_ds/tree_policy.hpp>
 
 using namespace std;
 using namespace __gnu_pbds;
@@ -51,8 +50,7 @@ using namespace __gnu_pbds;
 // statistics.
 typedef
 tree<int, char, less<int>,
-     splay_tree_tag,
-     tree_order_statistics_node_update>
+     splay_tree_tag>
 tree_map_t;
 
 int main()
-- 
2.27.0