1 // { dg-do compile }
2 // { dg-options "-fgnu-tm -O0"}
3 
4 namespace std __attribute__ ((__visibility__ ("default"))) {
5   template<class _T1, class _T2>
6     struct pair
7     {
8       typedef _T1 first_type;
9       typedef _T2 second_type;
10       _T1 first;
11       _T2 second;
pairpair12       pair()
13       : first(), second() { }
pairpair14       pair(const _T1& __a, const _T2& __b)
15       : first(__a), second(__b) { }
16     };
17 }
18 
19 
20 typedef long int ptrdiff_t;
21 typedef __SIZE_TYPE__ size_t;
22 namespace std __attribute__ ((__visibility__ ("default"))) {
23   using ::ptrdiff_t;
24   using ::size_t;
25 }
26 namespace std __attribute__ ((__visibility__ ("default"))) {
27   struct input_iterator_tag { };
28   struct output_iterator_tag { };
29   struct forward_iterator_tag : public input_iterator_tag { };
30   struct bidirectional_iterator_tag : public forward_iterator_tag { };
31   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
32   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
33 	   typename _Pointer = _Tp*, typename _Reference = _Tp&>
34     struct iterator
35     {
36       typedef _Category iterator_category;
37       typedef _Tp value_type;
38       typedef _Distance difference_type;
39       typedef _Pointer pointer;
40       typedef _Reference reference;
41     };
42   template<typename _Iterator>
43     struct iterator_traits
44     {
45       typedef typename _Iterator::iterator_category iterator_category;
46       typedef typename _Iterator::value_type value_type;
47       typedef typename _Iterator::difference_type difference_type;
48       typedef typename _Iterator::pointer pointer;
49       typedef typename _Iterator::reference reference;
50     };
51   template<typename _Tp>
52     struct iterator_traits<_Tp*>
53     {
54       typedef random_access_iterator_tag iterator_category;
55       typedef _Tp value_type;
56       typedef ptrdiff_t difference_type;
57       typedef _Tp* pointer;
58       typedef _Tp& reference;
59     };
60   template<typename _Tp>
61     struct iterator_traits<const _Tp*>
62     {
63       typedef random_access_iterator_tag iterator_category;
64       typedef _Tp value_type;
65       typedef ptrdiff_t difference_type;
66       typedef const _Tp* pointer;
67       typedef const _Tp& reference;
68     };
69   template<typename _Iter>
70     inline typename iterator_traits<_Iter>::iterator_category
71     __iterator_category(const _Iter&)
72     { return typename iterator_traits<_Iter>::iterator_category(); }
73 }
74 namespace std __attribute__ ((__visibility__ ("default"))) {
75   template<typename _Iterator>
76     class reverse_iterator
77     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
78 	typename iterator_traits<_Iterator>::value_type,
79 	typename iterator_traits<_Iterator>::difference_type,
80 	typename iterator_traits<_Iterator>::pointer,
81 		      typename iterator_traits<_Iterator>::reference>
82     {
83     protected:
84       _Iterator current;
85       typedef iterator_traits<_Iterator> __traits_type;
86     public:
87       typedef _Iterator iterator_type;
88       typedef typename __traits_type::difference_type difference_type;
89       typedef typename __traits_type::pointer pointer;
90       typedef typename __traits_type::reference reference;
91       reverse_iterator() : current() { }
92       explicit
93       reverse_iterator(iterator_type __x) : current(__x) { }
94       reverse_iterator(const reverse_iterator& __x)
95       : current(__x.current) { }
96       template<typename _Iter>
97 	reverse_iterator(const reverse_iterator<_Iter>& __x)
98  : current(__x.base()) { }
99       iterator_type
100       base() const
101       { return current; }
102       reference
103       operator*() const
104       {
105  _Iterator __tmp = current;
106  return *--__tmp;
107       }
108       pointer
109       operator->() const
110       { return &(operator*()); }
111       reverse_iterator&
112       operator++()
113       {
114  --current;
115  return *this;
116       }
117       reverse_iterator
118       operator++(int)
119       {
120  reverse_iterator __tmp = *this;
121  --current;
122  return __tmp;
123       }
124       reverse_iterator&
125       operator--()
126       {
127  ++current;
128  return *this;
129       }
130       reverse_iterator
131       operator--(int)
132       {
133  reverse_iterator __tmp = *this;
134  ++current;
135  return __tmp;
136       }
137       reverse_iterator
138       operator+(difference_type __n) const
139       { return reverse_iterator(current - __n); }
140       reverse_iterator&
141       operator+=(difference_type __n)
142       {
143  current -= __n;
144  return *this;
145       }
146       reverse_iterator
147       operator-(difference_type __n) const
148       { return reverse_iterator(current + __n); }
149       reverse_iterator&
150       operator-=(difference_type __n)
151       {
152  current += __n;
153  return *this;
154       }
155       reference
156       operator[](difference_type __n) const
157       { return *(*this + __n); }
158     };
159 }
160 
161 
162 
163 extern "C++" {
164 namespace std
165 {
166   class exception
167   {
168   public:
169     exception() throw() { }
170     virtual ~exception() throw();
171     virtual const char* what() const throw();
172   };
173   class bad_exception : public exception
174   {
175   public:
176     bad_exception() throw() { }
177     virtual ~bad_exception() throw();
178     virtual const char* what() const throw();
179   };
180   typedef void (*terminate_handler) ();
181   typedef void (*unexpected_handler) ();
182   terminate_handler set_terminate(terminate_handler) throw();
183   void terminate() throw() __attribute__ ((__noreturn__));
184   unexpected_handler set_unexpected(unexpected_handler) throw();
185   void unexpected() __attribute__ ((__noreturn__));
186   bool uncaught_exception() throw() __attribute__ ((__pure__));
187 }
188 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
189   void __verbose_terminate_handler();
190 }
191 }
192 extern "C++" {
193 namespace std
194 {
195   class bad_alloc : public exception
196   {
197   public:
198     bad_alloc() throw() { }
199     virtual ~bad_alloc() throw();
200     virtual const char* what() const throw();
201   };
202   struct nothrow_t { };
203   extern const nothrow_t nothrow;
204   typedef void (*new_handler)();
205   new_handler set_new_handler(new_handler) throw();
206 }
207 
208 void* operator new(std::size_t, const std::nothrow_t&) throw();
209 void* operator new[](std::size_t, const std::nothrow_t&) throw();
210 void operator delete(void*, const std::nothrow_t&) throw();
211 void operator delete[](void*, const std::nothrow_t&) throw();
212 inline void* operator new(std::size_t, void* __p) throw() { return __p; }
213 inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
214 inline void operator delete (void*, void*) throw() { }
215 inline void operator delete[](void*, void*) throw() { }
216 }
217 namespace std __attribute__ ((__visibility__ ("default"))) {
218   void
219   __throw_bad_exception(void) __attribute__((__noreturn__));
220   __attribute__((transaction_safe))
221   void
222   __throw_bad_alloc(void) __attribute__((__noreturn__));
223   void
224   __throw_bad_cast(void) __attribute__((__noreturn__));
225   void
226   __throw_bad_typeid(void) __attribute__((__noreturn__));
227   void
228   __throw_logic_error(const char*) __attribute__((__noreturn__));
229   void
230   __throw_domain_error(const char*) __attribute__((__noreturn__));
231   void
232   __throw_invalid_argument(const char*) __attribute__((__noreturn__));
233   void
234   __throw_length_error(const char*) __attribute__((__noreturn__));
235   void
236   __throw_out_of_range(const char*) __attribute__((__noreturn__));
237   void
238   __throw_runtime_error(const char*) __attribute__((__noreturn__));
239   void
240   __throw_range_error(const char*) __attribute__((__noreturn__));
241   void
242   __throw_overflow_error(const char*) __attribute__((__noreturn__));
243   void
244   __throw_underflow_error(const char*) __attribute__((__noreturn__));
245   void
246   __throw_ios_failure(const char*) __attribute__((__noreturn__));
247   void
248   __throw_system_error(int) __attribute__((__noreturn__));
249   void
250   __throw_future_error(int) __attribute__((__noreturn__));
251   void
252   __throw_bad_function_call() __attribute__((__noreturn__));
253 }
254 
255 
256 namespace std __attribute__ ((__visibility__ ("default"))) {
257   template<typename _Tp>
258     inline void
259     swap(_Tp& __a, _Tp& __b)
260     {
261 
262       _Tp __tmp = (__a);
263       __a = (__b);
264       __b = (__tmp);
265     }
266   template<typename _Tp, size_t _Nm>
267     inline void
268     swap(_Tp (&__a)[_Nm], _Tp (&__b)[_Nm])
269     {
270       for (size_t __n = 0; __n < _Nm; ++__n)
271  swap(__a[__n], __b[__n]);
272     }
273 }
274 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
275   using std::size_t;
276   using std::ptrdiff_t;
277   template<typename _Tp>
278     class new_allocator
279     {
280     public:
281       typedef size_t size_type;
282       typedef ptrdiff_t difference_type;
283       typedef _Tp* pointer;
284       typedef const _Tp* const_pointer;
285       typedef _Tp& reference;
286       typedef const _Tp& const_reference;
287       typedef _Tp value_type;
288       template<typename _Tp1>
289 	struct rebind
290 	{ typedef new_allocator<_Tp1> other; };
291       new_allocator() throw() { }
292       new_allocator(const new_allocator&) throw() { }
293       template<typename _Tp1>
294 	new_allocator(const new_allocator<_Tp1>&) throw() { }
295       ~new_allocator() throw() { }
296       pointer
297       address(reference __x) const { return &__x; }
298       const_pointer
299       address(const_reference __x) const { return &__x; }
300       __attribute__((transaction_safe))
301       pointer
302       allocate(size_type __n, const void* = 0)
303       {
304  if (__n > this->max_size())
305    std::__throw_bad_alloc();
306  return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
307       }
308 __attribute__((transaction_safe))
309 void
310       deallocate(pointer __p, size_type)
311       { ::operator delete(__p); }
312       size_type
313       max_size() const throw()
314       { return size_t(-1) / sizeof(_Tp); }
315       void
316       construct(pointer __p, const _Tp& __val)
317       { ::new((void *)__p) _Tp(__val); }
318       void
319       destroy(pointer __p) { __p->~_Tp(); }
320     };
321   template<typename _Tp>
322     inline bool
323     operator==(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
324     { return true; }
325   template<typename _Tp>
326     inline bool
327     operator!=(const new_allocator<_Tp>&, const new_allocator<_Tp>&)
328     { return false; }
329 }
330 namespace std __attribute__ ((__visibility__ ("default"))) {
331   template<typename _Tp>
332     class allocator;
333   template<>
334     class allocator<void>
335     {
336     public:
337       typedef size_t size_type;
338       typedef ptrdiff_t difference_type;
339       typedef void* pointer;
340       typedef const void* const_pointer;
341       typedef void value_type;
342       template<typename _Tp1>
343 	struct rebind
344 	{ typedef allocator<_Tp1> other; };
345     };
346   template<typename _Tp>
347     class allocator: public __gnu_cxx::new_allocator<_Tp>
348     {
349    public:
350       typedef size_t size_type;
351       typedef ptrdiff_t difference_type;
352       typedef _Tp* pointer;
353       typedef const _Tp* const_pointer;
354       typedef _Tp& reference;
355       typedef const _Tp& const_reference;
356       typedef _Tp value_type;
357       template<typename _Tp1>
358 	struct rebind
359 	{ typedef allocator<_Tp1> other; };
360       allocator() throw() { }
361       allocator(const allocator& __a) throw()
362       : __gnu_cxx::new_allocator<_Tp>(__a) { }
363       template<typename _Tp1>
364 	allocator(const allocator<_Tp1>&) throw() { }
365       ~allocator() throw() { }
366     };
367   template<typename _T1, typename _T2>
368     inline bool
369     operator==(const allocator<_T1>&, const allocator<_T2>&)
370     { return true; }
371   template<typename _Tp>
372     inline bool
373     operator==(const allocator<_Tp>&, const allocator<_Tp>&)
374     { return true; }
375   template<typename _T1, typename _T2>
376     inline bool
377     operator!=(const allocator<_T1>&, const allocator<_T2>&)
378     { return false; }
379   template<typename _Tp>
380     inline bool
381     operator!=(const allocator<_Tp>&, const allocator<_Tp>&)
382     { return false; }
383   //extern template class allocator<char>;
384   //  extern template class allocator<wchar_t>;
385   template<typename _Alloc, bool = __is_empty(_Alloc)>
386     struct __alloc_swap
387     { static void _S_do_it(_Alloc&, _Alloc&) { } };
388   template<typename _Alloc>
389     struct __alloc_swap<_Alloc, false>
390     {
391       static void
392       _S_do_it(_Alloc& __one, _Alloc& __two)
393       {
394  if (__one != __two)
395    swap(__one, __two);
396       }
397     };
398   template<typename _Alloc, bool = __is_empty(_Alloc)>
399     struct __alloc_neq
400     {
401       static bool
402       _S_do_it(const _Alloc&, const _Alloc&)
403       { return false; }
404     };
405   template<typename _Alloc>
406     struct __alloc_neq<_Alloc, false>
407     {
408       static bool
409       _S_do_it(const _Alloc& __one, const _Alloc& __two)
410       { return __one != __two; }
411     };
412 }
413 namespace std __attribute__ ((__visibility__ ("default"))) {
414   template<typename _Arg, typename _Result>
415     struct unary_function
416     {
417       typedef _Arg argument_type;
418       typedef _Result result_type;
419     };
420   template<typename _Arg1, typename _Arg2, typename _Result>
421     struct binary_function
422     {
423       typedef _Arg1 first_argument_type;
424       typedef _Arg2 second_argument_type;
425       typedef _Result result_type;
426     };
427   template<typename _Tp>
428     struct equal_to : public binary_function<_Tp, _Tp, bool>
429     {
430       bool
431       operator()(const _Tp& __x, const _Tp& __y) const
432       { return __x == __y; }
433     };
434   template<typename _Tp>
435     struct not_equal_to : public binary_function<_Tp, _Tp, bool>
436     {
437       bool
438       operator()(const _Tp& __x, const _Tp& __y) const
439       { return __x != __y; }
440     };
441   template<typename _Tp>
442     struct greater : public binary_function<_Tp, _Tp, bool>
443     {
444       bool
445       operator()(const _Tp& __x, const _Tp& __y) const
446       { return __x > __y; }
447     };
448   template<typename _Tp>
449     struct less : public binary_function<_Tp, _Tp, bool>
450     {
451       bool
452       operator()(const _Tp& __x, const _Tp& __y) const
453       { return __x < __y; }
454     };
455   template<typename _Tp>
456     struct _Identity : public unary_function<_Tp,_Tp>
457     {
458       _Tp&
459       operator()(_Tp& __x) const
460       { return __x; }
461       const _Tp&
462       operator()(const _Tp& __x) const
463       { return __x; }
464     };
465 }
466 namespace std __attribute__ ((__visibility__ ("default"))) {
467   enum _Rb_tree_color { _S_red = false, _S_black = true };
468   struct _Rb_tree_node_base
469   {
470     typedef _Rb_tree_node_base* _Base_ptr;
471     typedef const _Rb_tree_node_base* _Const_Base_ptr;
472     _Rb_tree_color _M_color;
473     _Base_ptr _M_parent;
474     _Base_ptr _M_left;
475     _Base_ptr _M_right;
476     static _Base_ptr
477     _S_minimum(_Base_ptr __x)
478     {
479       while (__x->_M_left != 0) __x = __x->_M_left;
480       return __x;
481     }
482     static _Const_Base_ptr
483     _S_minimum(_Const_Base_ptr __x)
484     {
485       while (__x->_M_left != 0) __x = __x->_M_left;
486       return __x;
487     }
488     static _Base_ptr
489     _S_maximum(_Base_ptr __x)
490     {
491       while (__x->_M_right != 0) __x = __x->_M_right;
492       return __x;
493     }
494     static _Const_Base_ptr
495     _S_maximum(_Const_Base_ptr __x)
496     {
497       while (__x->_M_right != 0) __x = __x->_M_right;
498       return __x;
499     }
500   };
501   template<typename _Val>
502     struct _Rb_tree_node : public _Rb_tree_node_base
503     {
504       typedef _Rb_tree_node<_Val>* _Link_type;
505       _Val _M_value_field;
506     };
507   __attribute__ ((__pure__)) _Rb_tree_node_base*
508   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
509   __attribute__ ((__pure__)) const _Rb_tree_node_base*
510   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
511   __attribute__ ((__pure__)) _Rb_tree_node_base*
512   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
513   __attribute__ ((__pure__)) const _Rb_tree_node_base*
514   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
515   template<typename _Tp>
516     struct _Rb_tree_iterator
517     {
518       typedef _Tp value_type;
519       typedef _Tp& reference;
520       typedef _Tp* pointer;
521       typedef bidirectional_iterator_tag iterator_category;
522       typedef ptrdiff_t difference_type;
523       typedef _Rb_tree_iterator<_Tp> _Self;
524       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
525       typedef _Rb_tree_node<_Tp>* _Link_type;
526       _Rb_tree_iterator()
527       : _M_node() { }
528       explicit
529       _Rb_tree_iterator(_Link_type __x)
530       : _M_node(__x) { }
531       reference
532       operator*() const
533       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
534       pointer
535       operator->() const
536       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
537       _Self&
538       operator++()
539       {
540  _M_node = _Rb_tree_increment(_M_node);
541  return *this;
542       }
543       _Self
544       operator++(int)
545       {
546  _Self __tmp = *this;
547  _M_node = _Rb_tree_increment(_M_node);
548  return __tmp;
549       }
550       _Self&
551       operator--()
552       {
553  _M_node = _Rb_tree_decrement(_M_node);
554  return *this;
555       }
556       _Self
557       operator--(int)
558       {
559  _Self __tmp = *this;
560  _M_node = _Rb_tree_decrement(_M_node);
561  return __tmp;
562       }
563       bool
564       operator==(const _Self& __x) const
565       { return _M_node == __x._M_node; }
566       bool
567       operator!=(const _Self& __x) const
568       { return _M_node != __x._M_node; }
569       _Base_ptr _M_node;
570   };
571   template<typename _Tp>
572     struct _Rb_tree_const_iterator
573     {
574       typedef _Tp value_type;
575       typedef const _Tp& reference;
576       typedef const _Tp* pointer;
577       typedef _Rb_tree_iterator<_Tp> iterator;
578       typedef bidirectional_iterator_tag iterator_category;
579       typedef ptrdiff_t difference_type;
580       typedef _Rb_tree_const_iterator<_Tp> _Self;
581       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
582       typedef const _Rb_tree_node<_Tp>* _Link_type;
583       _Rb_tree_const_iterator()
584       : _M_node() { }
585       explicit
586       _Rb_tree_const_iterator(_Link_type __x)
587       : _M_node(__x) { }
588       _Rb_tree_const_iterator(const iterator& __it)
589       : _M_node(__it._M_node) { }
590       reference
591       operator*() const
592       { return static_cast<_Link_type>(_M_node)->_M_value_field; }
593       pointer
594       operator->() const
595       { return &static_cast<_Link_type>(_M_node)->_M_value_field; }
596       _Self&
597       operator++()
598       {
599  _M_node = _Rb_tree_increment(_M_node);
600  return *this;
601       }
602       _Self
603       operator++(int)
604       {
605  _Self __tmp = *this;
606  _M_node = _Rb_tree_increment(_M_node);
607  return __tmp;
608       }
609       _Self&
610       operator--()
611       {
612  _M_node = _Rb_tree_decrement(_M_node);
613  return *this;
614       }
615       _Self
616       operator--(int)
617       {
618  _Self __tmp = *this;
619  _M_node = _Rb_tree_decrement(_M_node);
620  return __tmp;
621       }
622       bool
623       operator==(const _Self& __x) const
624       { return _M_node == __x._M_node; }
625       bool
626       operator!=(const _Self& __x) const
627       { return _M_node != __x._M_node; }
628       _Base_ptr _M_node;
629     };
630   void
631   _Rb_tree_insert_and_rebalance(const bool __insert_left,
632 				_Rb_tree_node_base* __x,
633 				_Rb_tree_node_base* __p,
634 				_Rb_tree_node_base& __header) throw ();
635   _Rb_tree_node_base*
636   _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
637 	  _Rb_tree_node_base& __header) throw ();
638   template<typename _Key, typename _Val, typename _KeyOfValue,
639 	   typename _Compare, typename _Alloc = allocator<_Val> >
640     class _Rb_tree
641     {
642       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
643 	      _Node_allocator;
644     protected:
645       typedef _Rb_tree_node_base* _Base_ptr;
646       typedef const _Rb_tree_node_base* _Const_Base_ptr;
647     public:
648       typedef _Key key_type;
649       typedef _Val value_type;
650       typedef value_type* pointer;
651       typedef const value_type* const_pointer;
652       typedef value_type& reference;
653       typedef const value_type& const_reference;
654       typedef _Rb_tree_node<_Val>* _Link_type;
655       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
656       typedef size_t size_type;
657       typedef ptrdiff_t difference_type;
658       typedef _Alloc allocator_type;
659       _Node_allocator&
660       _M_get_Node_allocator()
661       { return *static_cast<_Node_allocator*>(&this->_M_impl); }
662       const _Node_allocator&
663       _M_get_Node_allocator() const
664       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
665       allocator_type
666       get_allocator() const
667       { return allocator_type(_M_get_Node_allocator()); }
668     protected:
669       _Link_type
670       _M_get_node()
671       { return _M_impl._Node_allocator::allocate(1); }
672       __attribute__((transaction_safe))
673       void
674       _M_put_node(_Link_type __p)
675       { _M_impl._Node_allocator::deallocate(__p, 1); }
676       __attribute__((transaction_safe))
677       _Link_type
678       _M_create_node(const value_type& __x)
679       {
680  _Link_type __tmp = _M_get_node();
681  try
682    { get_allocator().construct(&__tmp->_M_value_field, __x); }
683  catch(...)
684    {
685      _M_put_node(__tmp);
686      throw;
687    }
688  return __tmp;
689       }
690       void
691       _M_destroy_node(_Link_type __p)
692       {
693  get_allocator().destroy(&__p->_M_value_field);
694  _M_put_node(__p);
695       }
696     protected:
697       template<typename _Key_compare,
698 	bool _Is_pod_comparator = __is_pod(_Key_compare)>
699 	struct _Rb_tree_impl : public _Node_allocator
700 	{
701    _Key_compare _M_key_compare;
702    _Rb_tree_node_base _M_header;
703    size_type _M_node_count;
704    _Rb_tree_impl()
705    : _Node_allocator(), _M_key_compare(), _M_header(),
706      _M_node_count(0)
707    { _M_initialize(); }
708    _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
709    : _Node_allocator(__a), _M_key_compare(__comp), _M_header(),
710      _M_node_count(0)
711    { _M_initialize(); }
712  private:
713    void
714    _M_initialize()
715    {
716      this->_M_header._M_color = _S_red;
717      this->_M_header._M_parent = 0;
718      this->_M_header._M_left = &this->_M_header;
719      this->_M_header._M_right = &this->_M_header;
720    }
721  };
722       _Rb_tree_impl<_Compare> _M_impl;
723     protected:
724       _Base_ptr&
725       _M_root()
726       { return this->_M_impl._M_header._M_parent; }
727       _Const_Base_ptr
728       _M_root() const
729       { return this->_M_impl._M_header._M_parent; }
730       _Base_ptr&
731       _M_leftmost()
732       { return this->_M_impl._M_header._M_left; }
733       _Const_Base_ptr
734       _M_leftmost() const
735       { return this->_M_impl._M_header._M_left; }
736       _Base_ptr&
737       _M_rightmost()
738       { return this->_M_impl._M_header._M_right; }
739       _Const_Base_ptr
740       _M_rightmost() const
741       { return this->_M_impl._M_header._M_right; }
742       _Link_type
743       _M_begin()
744       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
745       _Const_Link_type
746       _M_begin() const
747       {
748  return static_cast<_Const_Link_type>
749    (this->_M_impl._M_header._M_parent);
750       }
751       _Link_type
752       _M_end()
753       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
754       _Const_Link_type
755       _M_end() const
756       { return static_cast<_Const_Link_type>(&this->_M_impl._M_header); }
757       static const_reference
758       _S_value(_Const_Link_type __x)
759       { return __x->_M_value_field; }
760       static const _Key&
761       _S_key(_Const_Link_type __x)
762       { return _KeyOfValue()(_S_value(__x)); }
763       static _Link_type
764       _S_left(_Base_ptr __x)
765       { return static_cast<_Link_type>(__x->_M_left); }
766       static _Const_Link_type
767       _S_left(_Const_Base_ptr __x)
768       { return static_cast<_Const_Link_type>(__x->_M_left); }
769       static _Link_type
770       _S_right(_Base_ptr __x)
771       { return static_cast<_Link_type>(__x->_M_right); }
772       static _Const_Link_type
773       _S_right(_Const_Base_ptr __x)
774       { return static_cast<_Const_Link_type>(__x->_M_right); }
775       static const_reference
776       _S_value(_Const_Base_ptr __x)
777       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
778       static const _Key&
779       _S_key(_Const_Base_ptr __x)
780       { return _KeyOfValue()(_S_value(__x)); }
781     public:
782       typedef _Rb_tree_iterator<value_type> iterator;
783       typedef _Rb_tree_const_iterator<value_type> const_iterator;
784       typedef std::reverse_iterator<iterator> reverse_iterator;
785       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
786     private:
787       iterator
788       _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __y,
789    const value_type& __v);
790     public:
791       _Rb_tree() { }
792       iterator
793       begin()
794       {
795  return iterator(static_cast<_Link_type>
796    (this->_M_impl._M_header._M_left));
797       }
798       const_iterator
799       begin() const
800       {
801  return const_iterator(static_cast<_Const_Link_type>
802 	 (this->_M_impl._M_header._M_left));
803       }
804       iterator
805       end()
806       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
807       const_iterator
808       end() const
809       {
810  return const_iterator(static_cast<_Const_Link_type>
811 	 (&this->_M_impl._M_header));
812       }
813       pair<iterator, bool>
814       _M_insert_unique(const value_type& __x);
815     };
816   template<typename _Key, typename _Val, typename _KeyOfValue,
817 	   typename _Compare, typename _Alloc>
818     typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
819     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
820     _M_insert_(_Const_Base_ptr __x, _Const_Base_ptr __p, const _Val& __v)
821     {
822       _Link_type __z = _M_create_node(__v);
823       return iterator(__z);
824     }
825   template<typename _Key, typename _Val, typename _KeyOfValue,
826 	   typename _Compare, typename _Alloc>
827     pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
828       _Compare, _Alloc>::iterator, bool>
829     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
830     _M_insert_unique(const _Val& __v)
831     {
832       _Link_type __x = _M_begin();
833       _Link_type __y = _M_end();
834       iterator __j = iterator(__y);
835  return pair<iterator, bool>(_M_insert_(__x, __y, __v), true);
836     }
837 }
838 namespace std __attribute__ ((__visibility__ ("default"))) {
839   template<typename _Key, typename _Compare = std::less<_Key>,
840     typename _Alloc = std::allocator<_Key> >
841     class set
842     {
843     public:
844       typedef _Key key_type;
845       typedef _Key value_type;
846       typedef _Compare key_compare;
847       typedef _Compare value_compare;
848       typedef _Alloc allocator_type;
849     private:
850       typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
851       typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
852 	 key_compare, _Key_alloc_type> _Rep_type;
853       _Rep_type _M_t;
854     public:
855       typedef typename _Key_alloc_type::pointer pointer;
856       typedef typename _Key_alloc_type::const_pointer const_pointer;
857       typedef typename _Key_alloc_type::reference reference;
858       typedef typename _Key_alloc_type::const_reference const_reference;
859       typedef typename _Rep_type::const_iterator iterator;
860       typedef typename _Rep_type::const_iterator const_iterator;
861       typedef typename _Rep_type::const_reverse_iterator reverse_iterator;
862       typedef typename _Rep_type::const_reverse_iterator const_reverse_iterator;
863       typedef typename _Rep_type::size_type size_type;
864       typedef typename _Rep_type::difference_type difference_type;
865       std::pair<iterator, bool>
866       insert(const value_type& __x)
867       {
868    _M_t._M_insert_unique(__x);
869       }
870     };
871 }
872 __attribute__((transaction_pure))
873 void* operator new(size_t);
874 __attribute__((transaction_pure))
875 void operator delete(void*);
876 class Widget
877 {
878 private:
879 };
880 class Screen
881 {
882 protected:
883 std::set<Widget *> widgets;
884 public:
885 void addWidget(Widget* widget);
886 };
887 void Screen::addWidget(Widget* widget)
888 {
889 widgets.insert(widget);
890 }
891