Re: [PATCH][C++] Fix PR29433, make C++ use a lot less time/memory

[Paolo Carlini <pcarlini at suse dot de>]

Hi again,

> Richard Guenther wrote:
>
> > In libstdc++ testing there are many more cases.  Paolo, can you
> > investigate with the suggested change to gcc/cp/pt.c and fix up?
>
> Indeed, when I saw the first examples I wondered whether we should 
> really audit the entire library... Sure, I'm going to do that next 
> after completing a performance improvement to valarray (almost done)

I have just finished regtesting the below (check + check-performance), 
and in fact only one additional tweak seems necessary (in traits.hpp). 
However, I'd like to fix rope and stl_tree.h in this different way, more 
consistent with the rest of the library, actually a clean-up. I mean to 
commit tomorrow morning.

Thanks,
Paolo.

/////////////////
2006-12-11  Richard Guenther  <rguenther@suse.de>
	    Paolo Carlini  <pcarlini@suse.de>

	* include/ext/pb_ds/detail/pat_trie_/traits.hpp: Qualify types.
	* include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Likewise.
	* include/ext/rope: Likewise.
	* include/bits/stl_tree.h (struct _Rb_tree): Change the _Link_type
	typedefs to use _Rb_tree_node<_Val> directly.
	(_M_get_node, _M_put_node): Use _Link_type.

Index: include/ext/pb_ds/detail/pat_trie_/traits.hpp
===================================================================
--- include/ext/pb_ds/detail/pat_trie_/traits.hpp	(revision 119706)
+++ include/ext/pb_ds/detail/pat_trie_/traits.hpp	(working copy)
@@ -93,7 +93,7 @@
       typedef E_Access_Traits e_access_traits;
 
       typedef
-      synth_e_access_traits<
+      pb_ds::detail::synth_e_access_traits<
 	type_traits,
 	false,
 	e_access_traits>
@@ -254,7 +254,7 @@
       typedef E_Access_Traits e_access_traits;
 
       typedef
-      synth_e_access_traits<
+      pb_ds::detail::synth_e_access_traits<
 	type_traits,
 	true,
 	e_access_traits>
Index: include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
===================================================================
--- include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp	(revision 119706)
+++ include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp	(working copy)
@@ -81,7 +81,7 @@
     entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type
 
 #define PB_DS_RESIZE_POLICY_DEC	\
-    resize_policy<typename Allocator::size_type>
+    pb_ds::detail::resize_policy<typename Allocator::size_type>
 
     /**
      * class description = "Base class for some types of h3ap$">
Index: include/ext/rope
===================================================================
--- include/ext/rope	(revision 119706)
+++ include/ext/rope	(working copy)
@@ -78,8 +78,6 @@
   using std::size_t;
   using std::ptrdiff_t;
   using std::allocator;
-  using std::iterator;
-  using std::reverse_iterator;
   using std::_Destroy;
 
   // The _S_eos function is used for those functions that
@@ -165,7 +163,7 @@
 
   template<class _Sequence, size_t _Buf_sz = 100>
     class sequence_buffer
-    : public iterator<std::output_iterator_tag, void, void, void, void>
+    : public std::iterator<std::output_iterator_tag, void, void, void, void>
     {
     public:
       typedef typename _Sequence::value_type value_type;
@@ -1023,7 +1021,7 @@
   
   template<class _CharT, class _Alloc>
     class _Rope_iterator_base
-    : public iterator<std::random_access_iterator_tag, _CharT>
+    : public std::iterator<std::random_access_iterator_tag, _CharT>
     {
       friend class rope<_CharT, _Alloc>;
     public:
@@ -2017,7 +2015,7 @@
 	//  but it's harder to make guarantees.
       }
 
-      typedef reverse_iterator<const_iterator> const_reverse_iterator;
+      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 
       const_reverse_iterator
       rbegin() const
@@ -2549,7 +2547,7 @@
       mutable_end()
       { return(iterator(this, size())); }
 
-      typedef reverse_iterator<iterator> reverse_iterator;
+      typedef std::reverse_iterator<iterator> reverse_iterator;
       
       reverse_iterator
       mutable_rbegin()
Index: include/bits/stl_tree.h
===================================================================
--- include/bits/stl_tree.h	(revision 119706)
+++ include/bits/stl_tree.h	(working copy)
@@ -326,7 +326,6 @@
     protected:
       typedef _Rb_tree_node_base* _Base_ptr;
       typedef const _Rb_tree_node_base* _Const_Base_ptr;
-      typedef _Rb_tree_node<_Val> _Rb_tree_node;
 
     public:
       typedef _Key key_type;
@@ -335,8 +334,8 @@
       typedef const value_type* const_pointer;
       typedef value_type& reference;
       typedef const value_type& const_reference;
-      typedef _Rb_tree_node* _Link_type;
-      typedef const _Rb_tree_node* _Const_Link_type;
+      typedef _Rb_tree_node<_Val>* _Link_type;
+      typedef const _Rb_tree_node<_Val>* _Const_Link_type;
       typedef size_t size_type;
       typedef ptrdiff_t difference_type;
       typedef _Alloc allocator_type;
@@ -354,12 +353,12 @@
       { return allocator_type(_M_get_Node_allocator()); }
 
     protected:
-      _Rb_tree_node*
+      _Link_type
       _M_get_node()
       { return _M_impl._Node_allocator::allocate(1); }
 
       void
-      _M_put_node(_Rb_tree_node* __p)
+      _M_put_node(_Link_type __p)
       { _M_impl._Node_allocator::deallocate(__p, 1); }
 
       _Link_type