gcc/testsuite/g++.dg/lto/pr47333.C

   1 namespace std
   2 {
   3   typedef unsigned int size_t;
   4   typedef int ptrdiff_t;
   5
   6 }
   7
   8 namespace std __attribute__ ((__visibility__ ("default"))) {
   9
  10   template<typename _Alloc>
  11     class allocator;
  12
  13   template<class _CharT>
  14     struct char_traits;
  15
  16   template<typename _CharT, typename _Traits = char_traits<_CharT>,
  17            typename _Alloc = allocator<_CharT> >
  18     class basic_string;
  19
  20   template<> struct char_traits<char>;
  21
  22   typedef basic_string<char> string;
  23
  24   template<> struct char_traits<wchar_t>;
  25
  26   typedef basic_string<wchar_t> wstring;
  27 }
  28
  29 namespace std __attribute__ ((__visibility__ ("default"))) {
  30   void
  31   __throw_bad_alloc(void) __attribute__((__noreturn__));
  32 }
  33
  34 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
  35   template<typename _Iterator, typename _Container>
  36     class __normal_iterator;
  37 }
  38
  39 namespace std __attribute__ ((__visibility__ ("default"))) {
  40
  41   template<typename _Tp>
  42     inline _Tp*
  43     __addressof(_Tp& __r)
  44     {
  45       return reinterpret_cast<_Tp*>
  46  (&const_cast<char&>(reinterpret_cast<const volatile char&>(__r)));
  47     }
  48 }
  49
  50 namespace std __attribute__ ((__visibility__ ("default"))) {
  51   template<class _T1, class _T2>
  52     struct pair
  53     {
  54       typedef _T1 first_type;
  55       typedef _T2 second_type;
  56
  57       _T1 first;
  58       _T2 second;
  59
  60       pair()
  61       : first(), second() { }
  62
  63       pair(const _T1& __a, const _T2& __b)
  64       : first(__a), second(__b) { }
  65     };
  66 }
  67
  68 namespace std __attribute__ ((__visibility__ ("default"))) {
  69   struct input_iterator_tag { };
  70
  71   struct output_iterator_tag { };
  72
  73   struct forward_iterator_tag : public input_iterator_tag { };
  74
  75   struct bidirectional_iterator_tag : public forward_iterator_tag { };
  76
  77   struct random_access_iterator_tag : public bidirectional_iterator_tag { };
  78   template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
  79            typename _Pointer = _Tp*, typename _Reference = _Tp&>
  80     struct iterator
  81     {
  82       typedef _Category iterator_category;
  83       typedef _Tp value_type;
  84       typedef _Distance difference_type;
  85       typedef _Pointer pointer;
  86       typedef _Reference reference;
  87     };
  88
  89   template<typename _Iterator>
  90     struct iterator_traits
  91     {
  92       typedef typename _Iterator::iterator_category iterator_category;
  93       typedef typename _Iterator::value_type value_type;
  94       typedef typename _Iterator::difference_type difference_type;
  95       typedef typename _Iterator::pointer pointer;
  96       typedef typename _Iterator::reference reference;
  97     };
  98 }
  99
 100 namespace std __attribute__ ((__visibility__ ("default"))) {
 101   template<typename _Iterator>
 102     class reverse_iterator
 103     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
 104         typename iterator_traits<_Iterator>::value_type,
 105         typename iterator_traits<_Iterator>::difference_type,
 106         typename iterator_traits<_Iterator>::pointer,
 107                       typename iterator_traits<_Iterator>::reference>
 108     {
 109     protected:
 110       _Iterator current;
 111       typedef iterator_traits<_Iterator> __traits_type;
 112     };
 113 }
 114
 115 struct _IO_FILE;
 116
 117 typedef struct _IO_FILE FILE;
 118
 119 typedef struct _IO_FILE __FILE;
 120
 121 typedef __builtin_va_list __gnuc_va_list;
 122
 123 typedef unsigned int size_t;
 124 typedef unsigned int wint_t;
 125
 126 typedef struct
 127 {
 128   int __count;
 129   union
 130   {
 131     unsigned int __wch;
 132     char __wchb[4];
 133   } __value;
 134 } __mbstate_t;
 135
 136
 137 typedef __mbstate_t mbstate_t;
 138
 139 namespace std __attribute__ ((__visibility__ ("default"))) {
 140   using ::mbstate_t;
 141 }
 142
 143 namespace std __attribute__ ((__visibility__ ("default"))) {
 144   typedef long long streamoff;
 145
 146   typedef ptrdiff_t streamsize;
 147   template<typename _StateT>
 148     class fpos
 149     {
 150     private:
 151       streamoff _M_off;
 152       _StateT _M_state;
 153
 154     public:
 155
 156       fpos()
 157       : _M_off(0), _M_state() { }
 158       fpos(streamoff __off)
 159       : _M_off(__off), _M_state() { }
 160
 161       operator streamoff() const { return _M_off; }
 162
 163     };
 164
 165   typedef fpos<mbstate_t> streampos;
 166
 167   typedef fpos<mbstate_t> wstreampos;
 168 }
 169
 170 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 171   template<typename _CharT>
 172     struct _Char_types
 173     {
 174       typedef unsigned long int_type;
 175       typedef std::streampos pos_type;
 176       typedef std::streamoff off_type;
 177       typedef std::mbstate_t state_type;
 178     };
 179   template<typename _CharT>
 180     struct char_traits
 181     {
 182       typedef _CharT char_type;
 183       typedef typename _Char_types<_CharT>::int_type int_type;
 184       typedef typename _Char_types<_CharT>::pos_type pos_type;
 185       typedef typename _Char_types<_CharT>::off_type off_type;
 186       typedef typename _Char_types<_CharT>::state_type state_type;
 187
 188       static const char_type*
 189       find(const char_type* __s, std::size_t __n, const char_type& __a);
 190     };
 191 }
 192
 193 namespace std __attribute__ ((__visibility__ ("default"))) {
 194   template<class _CharT>
 195     struct char_traits : public __gnu_cxx::char_traits<_CharT>
 196     { };
 197
 198   template<>
 199     struct char_traits<char>
 200     {
 201       typedef char char_type;
 202       typedef int int_type;
 203       typedef streampos pos_type;
 204       typedef streamoff off_type;
 205       typedef mbstate_t state_type;
 206
 207       static const char_type*
 208       find(const char_type* __s, size_t __n, const char_type& __a)
 209       { return static_cast<const char_type*>(__builtin_memchr(__s, __a, __n)); }
 210   };
 211 }
 212
 213 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 214
 215   using std::size_t;
 216   using std::ptrdiff_t;
 217   template<typename _Tp>
 218     class new_allocator
 219     {
 220     public:
 221       typedef size_t size_type;
 222       typedef ptrdiff_t difference_type;
 223       typedef _Tp* pointer;
 224       typedef const _Tp* const_pointer;
 225       typedef _Tp& reference;
 226       typedef const _Tp& const_reference;
 227       typedef _Tp value_type;
 228
 229       new_allocator() throw() { }
 230
 231       new_allocator(const new_allocator&) throw() { }
 232
 233       template<typename _Tp1>
 234         new_allocator(const new_allocator<_Tp1>&) throw() { }
 235
 236       ~new_allocator() throw() { }
 237
 238       pointer
 239       allocate(size_type __n, const void* = 0)
 240       {
 241  if (__n > this->max_size())
 242    std::__throw_bad_alloc();
 243
 244  return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));
 245       }
 246       void
 247       deallocate(pointer __p, size_type)
 248       { ::operator delete(__p); }
 249
 250       void
 251       destroy(pointer __p) { __p->~_Tp(); }
 252     };
 253 }
 254
 255 namespace std __attribute__ ((__visibility__ ("default"))) {
 256   template<typename _Tp>
 257     class allocator;
 258
 259   template<typename _Tp>
 260     class allocator: public __gnu_cxx::new_allocator<_Tp>
 261     {
 262    public:
 263       typedef size_t size_type;
 264       typedef ptrdiff_t difference_type;
 265       typedef _Tp* pointer;
 266       typedef const _Tp* const_pointer;
 267       typedef _Tp& reference;
 268       typedef const _Tp& const_reference;
 269       typedef _Tp value_type;
 270
 271       template<typename _Tp1>
 272         struct rebind
 273         { typedef allocator<_Tp1> other; };
 274
 275       allocator() throw() { }
 276
 277       allocator(const allocator& __a) throw()
 278       : __gnu_cxx::new_allocator<_Tp>(__a) { }
 279
 280       template<typename _Tp1>
 281         allocator(const allocator<_Tp1>&) throw() { }
 282
 283       ~allocator() throw() { }
 284     };
 285 }
 286
 287 namespace std __attribute__ ((__visibility__ ("default"))) {
 288   template<typename _Arg, typename _Result>
 289     struct unary_function
 290     {
 291       typedef _Arg argument_type;
 292       typedef _Result result_type;
 293     };
 294
 295   template<typename _Arg1, typename _Arg2, typename _Result>
 296     struct binary_function
 297     {
 298       typedef _Arg1 first_argument_type;
 299       typedef _Arg2 second_argument_type;
 300       typedef _Result result_type;
 301     };
 302
 303   template<typename _Tp>
 304     struct less : public binary_function<_Tp, _Tp, bool>
 305     {
 306       bool
 307       operator()(const _Tp& __x, const _Tp& __y) const
 308       { return __x < __y; }
 309     };
 310
 311   template<typename _Pair>
 312     struct _Select1st : public unary_function<_Pair,
 313            typename _Pair::first_type>
 314     {
 315       typename _Pair::first_type&
 316       operator()(_Pair& __x) const
 317       { return __x.first; }
 318
 319       const typename _Pair::first_type&
 320       operator()(const _Pair& __x) const
 321       { return __x.first; }
 322     };
 323 }
 324
 325 extern "C" {
 326
 327 typedef int __sig_atomic_t;
 328
 329 typedef struct
 330   {
 331     unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))];
 332   } __sigset_t;
 333 typedef __sigset_t sigset_t;
 334 }
 335 typedef unsigned long int pthread_t;
 336
 337 typedef struct __pthread_internal_slist
 338 {
 339   struct __pthread_internal_slist *__next;
 340 } __pthread_slist_t;
 341
 342 typedef union
 343 {
 344   struct __pthread_mutex_s
 345   {
 346     int __lock;
 347     unsigned int __count;
 348     int __owner;
 349     int __kind;
 350
 351     unsigned int __nusers;
 352     __extension__ union
 353     {
 354       int __spins;
 355       __pthread_slist_t __list;
 356     };
 357
 358   } __data;
 359   char __size[24];
 360   long int __align;
 361 } pthread_mutex_t;
 362
 363 typedef unsigned int pthread_key_t;
 364
 365 typedef int pthread_once_t;
 366
 367 extern int pthread_once (pthread_once_t *__once_control,
 368     void (*__init_routine) (void)) __attribute__ ((__nonnull__ (1, 2)));
 369
 370 extern int pthread_mutex_lock (pthread_mutex_t *__mutex)
 371      throw () __attribute__ ((__nonnull__ (1)));
 372
 373 extern int pthread_mutex_unlock (pthread_mutex_t *__mutex)
 374      throw () __attribute__ ((__nonnull__ (1)));
 375
 376 typedef pthread_t __gthread_t;
 377 typedef pthread_key_t __gthread_key_t;
 378 typedef pthread_once_t __gthread_once_t;
 379 typedef pthread_mutex_t __gthread_mutex_t;
 380
 381 static __typeof(pthread_once) __gthrw_pthread_once __attribute__ ((__weakref__("pthread_once")));
 382
 383 static __typeof(pthread_mutex_lock) __gthrw_pthread_mutex_lock __attribute__ ((__weakref__("pthread_mutex_lock")));
 384
 385 static __typeof(pthread_mutex_unlock) __gthrw_pthread_mutex_unlock __attribute__ ((__weakref__("pthread_mutex_unlock")));
 386
 387 static volatile int __gthread_active = -1;
 388
 389 static void
 390 __gthread_trigger (void)
 391 {
 392   __gthread_active = 1;
 393 }
 394
 395 static inline int
 396 __gthread_active_p (void)
 397 {
 398   static pthread_mutex_t __gthread_active_mutex = { { 0, 0, 0, 0, 0, { 0 } } };
 399   static pthread_once_t __gthread_active_once = 0;
 400
 401   int __gthread_active_latest_value = __gthread_active;
 402
 403   if (__builtin_expect (__gthread_active_latest_value < 0, 0))
 404     {
 405       if (__gthrw_pthread_once)
 406  {
 407    __gthrw_pthread_mutex_lock (&__gthread_active_mutex);
 408    __gthrw_pthread_once (&__gthread_active_once, __gthread_trigger);
 409    __gthrw_pthread_mutex_unlock (&__gthread_active_mutex);
 410  }
 411
 412       if (__gthread_active < 0)
 413  __gthread_active = 0;
 414       __gthread_active_latest_value = __gthread_active;
 415     }
 416
 417   return __gthread_active_latest_value != 0;
 418 }
 419
 420 typedef int _Atomic_word;
 421
 422 namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) {
 423
 424   static inline _Atomic_word
 425   __exchange_and_add(volatile _Atomic_word* __mem, int __val)
 426   { return __sync_fetch_and_add(__mem, __val); }
 427
 428   static inline void
 429   __atomic_add(volatile _Atomic_word* __mem, int __val)
 430   { __sync_fetch_and_add(__mem, __val); }
 431   static inline _Atomic_word
 432   __exchange_and_add_single(_Atomic_word* __mem, int __val)
 433   {
 434     _Atomic_word __result = *__mem;
 435     *__mem += __val;
 436     return __result;
 437   }
 438
 439   static inline void
 440   __atomic_add_single(_Atomic_word* __mem, int __val)
 441   { *__mem += __val; }
 442
 443   static inline _Atomic_word
 444   __attribute__ ((__unused__))
 445   __exchange_and_add_dispatch(_Atomic_word* __mem, int __val)
 446   {
 447     if (__gthread_active_p())
 448       return __exchange_and_add(__mem, __val);
 449     else
 450       return __exchange_and_add_single(__mem, __val);
 451   }
 452
 453   static inline void
 454   __attribute__ ((__unused__))
 455   __atomic_add_dispatch(_Atomic_word* __mem, int __val)
 456   {
 457     if (__gthread_active_p())
 458       __atomic_add(__mem, __val);
 459     else
 460       __atomic_add_single(__mem, __val);
 461   }
 462 }
 463
 464 namespace std __attribute__ ((__visibility__ ("default"))) {
 465   template<typename _CharT, typename _Traits, typename _Alloc>
 466     class basic_string
 467     {
 468       typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
 469
 470     public:
 471       typedef _Traits traits_type;
 472       typedef typename _Traits::char_type value_type;
 473       typedef _Alloc allocator_type;
 474       typedef typename _CharT_alloc_type::size_type size_type;
 475       typedef typename _CharT_alloc_type::difference_type difference_type;
 476       typedef typename _CharT_alloc_type::reference reference;
 477       typedef typename _CharT_alloc_type::const_reference const_reference;
 478       typedef typename _CharT_alloc_type::pointer pointer;
 479       typedef typename _CharT_alloc_type::const_pointer const_pointer;
 480       typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
 481       typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
 482                                                             const_iterator;
 483       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 484       typedef std::reverse_iterator<iterator> reverse_iterator;
 485
 486     private:
 487       struct _Rep_base
 488       {
 489  size_type _M_length;
 490  size_type _M_capacity;
 491  _Atomic_word _M_refcount;
 492       };
 493
 494       struct _Rep : _Rep_base
 495       {
 496
 497  typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
 498  static const size_type _S_max_size;
 499  static const _CharT _S_terminal;
 500
 501         static size_type _S_empty_rep_storage[];
 502
 503         static _Rep&
 504         _S_empty_rep()
 505         {
 506    void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
 507    return *reinterpret_cast<_Rep*>(__p);
 508  }
 509
 510  _CharT*
 511  _M_refdata() throw()
 512  { return reinterpret_cast<_CharT*>(this + 1); }
 513
 514  void
 515  _M_dispose(const _Alloc& __a)
 516  {
 517    if (__builtin_expect(this != &_S_empty_rep(), false))
 518      {
 519        ;
 520        if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
 521         -1) <= 0)
 522   {
 523     ;
 524     _M_destroy(__a);
 525   }
 526      }
 527  }
 528
 529  void
 530  _M_destroy(const _Alloc&) throw();
 531
 532  _CharT*
 533  _M_refcopy() throw()
 534  {
 535    if (__builtin_expect(this != &_S_empty_rep(), false))
 536             __gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, 1);
 537    return _M_refdata();
 538  }
 539       };
 540
 541       struct _Alloc_hider : _Alloc
 542       {
 543  _Alloc_hider(_CharT* __dat, const _Alloc& __a)
 544  : _Alloc(__a), _M_p(__dat) { }
 545
 546  _CharT* _M_p;
 547       };
 548
 549     private:
 550
 551       mutable _Alloc_hider _M_dataplus;
 552
 553       _CharT*
 554       _M_data() const
 555       { return _M_dataplus._M_p; }
 556
 557       _Rep*
 558       _M_rep() const
 559       { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }
 560
 561       void
 562       _M_leak_hard();
 563
 564     public:
 565
 566       ~basic_string()
 567       { _M_rep()->_M_dispose(this->get_allocator()); }
 568
 569     public:
 570
 571       allocator_type
 572       get_allocator() const
 573       { return _M_dataplus; }
 574   };
 575 }
 576
 577 namespace std __attribute__ ((__visibility__ ("default"))) {
 578   enum _Rb_tree_color { _S_red = false, _S_black = true };
 579
 580   struct _Rb_tree_node_base
 581   {
 582     typedef _Rb_tree_node_base* _Base_ptr;
 583     typedef const _Rb_tree_node_base* _Const_Base_ptr;
 584
 585     _Rb_tree_color _M_color;
 586     _Base_ptr _M_parent;
 587     _Base_ptr _M_left;
 588     _Base_ptr _M_right;
 589
 590     static _Base_ptr
 591     _S_minimum(_Base_ptr __x)
 592     {
 593       while (__x->_M_left != 0) __x = __x->_M_left;
 594       return __x;
 595     }
 596
 597     static _Const_Base_ptr
 598     _S_minimum(_Const_Base_ptr __x)
 599     {
 600       while (__x->_M_left != 0) __x = __x->_M_left;
 601       return __x;
 602     }
 603
 604     static _Base_ptr
 605     _S_maximum(_Base_ptr __x)
 606     {
 607       while (__x->_M_right != 0) __x = __x->_M_right;
 608       return __x;
 609     }
 610
 611     static _Const_Base_ptr
 612     _S_maximum(_Const_Base_ptr __x)
 613     {
 614       while (__x->_M_right != 0) __x = __x->_M_right;
 615       return __x;
 616     }
 617   };
 618
 619   template<typename _Val>
 620     struct _Rb_tree_node : public _Rb_tree_node_base
 621     {
 622       typedef _Rb_tree_node<_Val>* _Link_type;
 623       _Val _M_value_field;
 624     };
 625
 626   __attribute__ ((__pure__)) _Rb_tree_node_base*
 627   _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
 628
 629   __attribute__ ((__pure__)) const _Rb_tree_node_base*
 630   _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
 631
 632   __attribute__ ((__pure__)) _Rb_tree_node_base*
 633   _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
 634
 635   __attribute__ ((__pure__)) const _Rb_tree_node_base*
 636   _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
 637
 638   template<typename _Tp>
 639     struct _Rb_tree_iterator
 640     {
 641       typedef _Tp value_type;
 642       typedef _Tp& reference;
 643       typedef _Tp* pointer;
 644
 645       typedef bidirectional_iterator_tag iterator_category;
 646       typedef ptrdiff_t difference_type;
 647
 648       typedef _Rb_tree_iterator<_Tp> _Self;
 649       typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
 650       typedef _Rb_tree_node<_Tp>* _Link_type;
 651
 652       _Rb_tree_iterator()
 653       : _M_node() { }
 654
 655       explicit
 656       _Rb_tree_iterator(_Link_type __x)
 657       : _M_node(__x) { }
 658
 659       bool
 660       operator==(const _Self& __x) const
 661       { return _M_node == __x._M_node; }
 662
 663       bool
 664       operator!=(const _Self& __x) const
 665       { return _M_node != __x._M_node; }
 666
 667       _Base_ptr _M_node;
 668   };
 669
 670   template<typename _Tp>
 671     struct _Rb_tree_const_iterator
 672     {
 673       typedef _Tp value_type;
 674       typedef const _Tp& reference;
 675       typedef const _Tp* pointer;
 676
 677       typedef _Rb_tree_iterator<_Tp> iterator;
 678
 679       typedef bidirectional_iterator_tag iterator_category;
 680       typedef ptrdiff_t difference_type;
 681
 682       typedef _Rb_tree_const_iterator<_Tp> _Self;
 683       typedef _Rb_tree_node_base::_Const_Base_ptr _Base_ptr;
 684       typedef const _Rb_tree_node<_Tp>* _Link_type;
 685
 686       _Rb_tree_const_iterator()
 687       : _M_node() { }
 688
 689       explicit
 690       _Rb_tree_const_iterator(_Link_type __x)
 691       : _M_node(__x) { }
 692
 693       _Rb_tree_const_iterator(const iterator& __it)
 694       : _M_node(__it._M_node) { }
 695
 696       pointer
 697       operator->() const
 698       { return std::__addressof(static_cast<_Link_type>
 699     (_M_node)->_M_value_field); }
 700
 701       bool
 702       operator==(const _Self& __x) const
 703       { return _M_node == __x._M_node; }
 704
 705       bool
 706       operator!=(const _Self& __x) const
 707       { return _M_node != __x._M_node; }
 708
 709       _Base_ptr _M_node;
 710     };
 711
 712   template<typename _Key, typename _Val, typename _KeyOfValue,
 713            typename _Compare, typename _Alloc = allocator<_Val> >
 714     class _Rb_tree
 715     {
 716       typedef typename _Alloc::template rebind<_Rb_tree_node<_Val> >::other
 717               _Node_allocator;
 718
 719     protected:
 720       typedef _Rb_tree_node_base* _Base_ptr;
 721       typedef const _Rb_tree_node_base* _Const_Base_ptr;
 722
 723     public:
 724       typedef _Key key_type;
 725       typedef _Val value_type;
 726       typedef value_type* pointer;
 727       typedef const value_type* const_pointer;
 728       typedef value_type& reference;
 729       typedef const value_type& const_reference;
 730       typedef _Rb_tree_node<_Val>* _Link_type;
 731       typedef const _Rb_tree_node<_Val>* _Const_Link_type;
 732       typedef size_t size_type;
 733       typedef ptrdiff_t difference_type;
 734       typedef _Alloc allocator_type;
 735
 736       const _Node_allocator&
 737       _M_get_Node_allocator() const
 738       { return *static_cast<const _Node_allocator*>(&this->_M_impl); }
 739
 740       allocator_type
 741       get_allocator() const
 742       { return allocator_type(_M_get_Node_allocator()); }
 743
 744     protected:
 745       void
 746       _M_put_node(_Link_type __p)
 747       { _M_impl._Node_allocator::deallocate(__p, 1); }
 748
 749       void
 750       _M_destroy_node(_Link_type __p)
 751       {
 752  get_allocator().destroy(std::__addressof(__p->_M_value_field));
 753  _M_put_node(__p);
 754       }
 755
 756     protected:
 757       template<typename _Key_compare,
 758         bool _Is_pod_comparator = __is_pod(_Key_compare)>
 759         struct _Rb_tree_impl : public _Node_allocator
 760         {
 761    _Key_compare _M_key_compare;
 762    _Rb_tree_node_base _M_header;
 763    size_type _M_node_count;
 764
 765  private:
 766    void
 767    _M_initialize()
 768    {
 769      this->_M_header._M_color = _S_red;
 770      this->_M_header._M_parent = 0;
 771      this->_M_header._M_left = &this->_M_header;
 772      this->_M_header._M_right = &this->_M_header;
 773    }
 774  };
 775
 776       _Rb_tree_impl<_Compare> _M_impl;
 777
 778     protected:
 779
 780       _Link_type
 781       _M_begin()
 782       { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
 783
 784       _Link_type
 785       _M_end()
 786       { return static_cast<_Link_type>(&this->_M_impl._M_header); }
 787
 788       static _Link_type
 789       _S_left(_Base_ptr __x)
 790       { return static_cast<_Link_type>(__x->_M_left); }
 791
 792       static _Link_type
 793       _S_right(_Base_ptr __x)
 794       { return static_cast<_Link_type>(__x->_M_right); }
 795
 796       static const_reference
 797       _S_value(_Const_Base_ptr __x)
 798       { return static_cast<_Const_Link_type>(__x)->_M_value_field; }
 799
 800       static const _Key&
 801       _S_key(_Const_Base_ptr __x)
 802       { return _KeyOfValue()(_S_value(__x)); }
 803
 804     public:
 805       typedef _Rb_tree_iterator<value_type> iterator;
 806       typedef _Rb_tree_const_iterator<value_type> const_iterator;
 807
 808     private:
 809
 810       void
 811       _M_erase(_Link_type __x);
 812
 813       iterator
 814       _M_lower_bound(_Link_type __x, _Link_type __y,
 815        const _Key& __k);
 816
 817       const_iterator
 818       _M_lower_bound(_Const_Link_type __x, _Const_Link_type __y,
 819        const _Key& __k) const;
 820
 821     public:
 822
 823       ~_Rb_tree()
 824       { _M_erase(_M_begin()); }
 825
 826       iterator
 827       end()
 828       { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }
 829
 830       const_iterator
 831       end() const
 832       {
 833          return const_iterator(static_cast<_Const_Link_type>
 834          (&this->_M_impl._M_header));
 835       }
 836
 837     public:
 838       iterator
 839       find(const key_type& __k);
 840     };
 841
 842   template<typename _Key, typename _Val, typename _KeyOfValue,
 843            typename _Compare, typename _Alloc>
 844     void
 845     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 846     _M_erase(_Link_type __x)
 847     {
 848
 849       while (__x != 0)
 850  {
 851    _M_erase(_S_right(__x));
 852    _Link_type __y = _S_left(__x);
 853    _M_destroy_node(__x);
 854    __x = __y;
 855  }
 856     }
 857
 858   template<typename _Key, typename _Val, typename _KeyOfValue,
 859            typename _Compare, typename _Alloc>
 860     typename _Rb_tree<_Key, _Val, _KeyOfValue,
 861         _Compare, _Alloc>::iterator
 862     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 863     _M_lower_bound(_Link_type __x, _Link_type __y,
 864      const _Key& __k)
 865     {
 866       while (__x != 0)
 867  if (!_M_impl._M_key_compare(_S_key(__x), __k))
 868    __y = __x, __x = _S_left(__x);
 869  else
 870    __x = _S_right(__x);
 871       return iterator(__y);
 872     }
 873
 874   template<typename _Key, typename _Val, typename _KeyOfValue,
 875            typename _Compare, typename _Alloc>
 876     typename _Rb_tree<_Key, _Val, _KeyOfValue,
 877         _Compare, _Alloc>::iterator
 878     _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
 879     find(const _Key& __k)
 880     {
 881       iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
 882       return (__j == end()
 883        || _M_impl._M_key_compare(__k,
 884      _S_key(__j._M_node))) ? end() : __j;
 885     }
 886
 887 }
 888
 889 namespace std {
 890   template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
 891             typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
 892     class map
 893     {
 894     public:
 895       typedef _Key key_type;
 896       typedef _Tp mapped_type;
 897       typedef std::pair<const _Key, _Tp> value_type;
 898       typedef _Compare key_compare;
 899       typedef _Alloc allocator_type;
 900
 901     private:
 902
 903       typedef typename _Alloc::template rebind<value_type>::other
 904         _Pair_alloc_type;
 905
 906       typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
 907          key_compare, _Pair_alloc_type> _Rep_type;
 908
 909       _Rep_type _M_t;
 910
 911     public:
 912
 913       typedef typename _Rep_type::iterator iterator;
 914       typedef typename _Rep_type::const_iterator const_iterator;
 915
 916       map()
 917       : _M_t() { }
 918
 919       const_iterator
 920       end() const
 921       { return _M_t.end(); }
 922
 923       key_compare
 924       key_comp() const
 925       { return _M_t.key_comp(); }
 926
 927       iterator
 928       find(const key_type& __x)
 929       { return _M_t.find(__x); }
 930     };
 931 }
 932
 933 int main ()
 934 {
 935   typedef std::map<int, std::string> Map;
 936   static Map m;
 937
 938   Map::const_iterator it = m.find(0);
 939   if (it != m.end())
 940     std::string s = it->second;
 941
 942   return 0;
 943 }
 944