X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fext%2Fpb_ds%2Fdetail%2Fov_tree_map_%2Fov_tree_map_.hpp;h=77522055a61929a30228cd655fe0f2c5ae592f83;hb=HEAD;hp=20a435047dd65232232af089b0e0d3766b8e48c3;hpb=a345e45d144c0e83aed85b6d29f64af3d21b4453;p=gcc.git

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 20a435047dd..77522055a61 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
@@ -1,6 +1,6 @@
 // -*- C++ -*-
 
-// Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
+// Copyright (C) 2005-2021 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
@@ -35,7 +35,7 @@
 
 /**
  * @file ov_tree_map_/ov_tree_map_.hpp
- * Contains an implementation class for ov_tree_.
+ * Contains an implementation class for ov_tree.
  */
 
 #include <map>
@@ -83,7 +83,7 @@ namespace __gnu_pbds
 #ifdef _GLIBCXX_DEBUG
 #define PB_DS_DEBUG_MAP_BASE_C_DEC \
     debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
-       	typename _Alloc::template rebind<Key>::other::const_reference>
+		   typename rebind_traits<_Alloc, Key>::const_reference>
 #endif
 
 #ifdef PB_DS_TREE_TRACE
@@ -97,7 +97,10 @@ namespace __gnu_pbds
 #  error Missing definition
 #endif
 
-    /// Ordered-vector tree associative-container.
+    /**
+     *  @brief Ordered-vector tree associative-container.
+     *  @ingroup branch-detail
+     */
     template<typename Key, typename Mapped, typename Cmp_Fn,
 	     typename Node_And_It_Traits, typename _Alloc>
     class PB_DS_OV_TREE_NAME :
@@ -117,8 +120,9 @@ namespace __gnu_pbds
 
       typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
 
-      typedef typename _Alloc::template rebind<non_const_value_type>::other value_allocator;
-      typedef typename value_allocator::pointer 	value_vector;
+      typedef rebind_traits<_Alloc, non_const_value_type> value_alloc_traits;
+      typedef typename value_alloc_traits::allocator_type value_allocator;
+      typedef typename value_alloc_traits::pointer	  value_vector;
 
 #ifdef _GLIBCXX_DEBUG
       typedef PB_DS_DEBUG_MAP_BASE_C_DEC 		debug_base;
@@ -133,16 +137,17 @@ namespace __gnu_pbds
 
       typedef typename traits_type::metadata_type 	metadata_type;
 
-      typedef typename _Alloc::template rebind<metadata_type>::other metadata_allocator;
-      typedef typename metadata_allocator::pointer 	metadata_pointer;
-      typedef typename metadata_allocator::const_reference metadata_const_reference;
-      typedef typename metadata_allocator::reference 	metadata_reference;
+      typedef rebind_traits<_Alloc, metadata_type>	metadata_alloc_traits;
+      typedef typename metadata_alloc_traits::allocator_type metadata_allocator;
+      typedef typename metadata_alloc_traits::pointer	metadata_pointer;
+      typedef typename metadata_alloc_traits::const_reference metadata_const_reference;
+      typedef typename metadata_alloc_traits::reference	metadata_reference;
 
       typedef typename traits_type::null_node_update_pointer
       null_node_update_pointer;
 
     public:
-      typedef ov_tree_tag 				 container_category;
+      typedef ov_tree_tag 				container_category;
       typedef _Alloc 					allocator_type;
       typedef typename _Alloc::size_type 		size_type;
       typedef typename _Alloc::difference_type 		difference_type;
@@ -236,7 +241,7 @@ namespace __gnu_pbds
       inline size_type
       max_size() const;
 
-      inline bool
+      _GLIBCXX_NODISCARD inline bool
       empty() const;
 
       inline size_type
@@ -377,15 +382,23 @@ namespace __gnu_pbds
       end() const
       { return m_end_it; }
 
+      /// Returns a const node_iterator corresponding to the node at the
+      /// root of the tree.
       inline node_const_iterator
       node_begin() const;
 
-      inline node_const_iterator
-      node_end() const;
-
+      /// Returns a node_iterator corresponding to the node at the
+      /// root of the tree.
       inline node_iterator
       node_begin();
 
+      /// Returns a const node_iterator corresponding to a node just
+      /// after a leaf of the tree.
+      inline node_const_iterator
+      node_end() const;
+
+      /// Returns a node_iterator corresponding to a node just
+      /// after a leaf of the tree.
       inline node_iterator
       node_end();