gcc/testsuite/g++.dg/tm/pr46646.C

   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;
  12       pair()
  13       : first(), second() { }
  14       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 }