1// { dg-do compile }
2// { dg-options "-fgnu-tm -O0"}
3
4namespace 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;
12      pair()
13      : first(), second() { }
14      pair(const _T1& __a, const _T2& __b)
15      : first(__a), second(__b) { }
16    };
17}
18
19
20typedef long int ptrdiff_t;
21typedef __SIZE_TYPE__ size_t;
22namespace std __attribute__ ((__visibility__ ("default"))) {
23  using ::ptrdiff_t;
24  using ::size_t;
25}
26namespace 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}
74namespace 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
163extern "C++" {
164namespace 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}
188namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
189  void __verbose_terminate_handler();
190}
191}
192extern "C++" {
193namespace 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
208void* operator new(std::size_t, const std::nothrow_t&) throw();
209void* operator new[](std::size_t, const std::nothrow_t&) throw();
210void operator delete(void*, const std::nothrow_t&) throw();
211void operator delete[](void*, const std::nothrow_t&) throw();
212inline void* operator new(std::size_t, void* __p) throw() { return __p; }
213inline void* operator new[](std::size_t, void* __p) throw() { return __p; }
214inline void operator delete (void*, void*) throw() { }
215inline void operator delete[](void*, void*) throw() { }
216}
217namespace 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
256namespace 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}
274namespace __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))
309void
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}
330namespace 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}
413namespace 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}
466namespace 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}
838namespace 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))
873void* operator new(size_t);
874__attribute__((transaction_pure))
875void operator delete(void*);
876class Widget
877{
878private:
879};
880class Screen
881{
882protected:
883std::set<Widget *> widgets;
884public:
885void addWidget(Widget* widget);
886};
887void Screen::addWidget(Widget* widget)
888{
889widgets.insert(widget);
890}
891