1namespace std 2{ 3 typedef unsigned int size_t; 4 typedef int ptrdiff_t; 5 6} 7 8namespace 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 29namespace std __attribute__ ((__visibility__ ("default"))) { 30 void 31 __throw_bad_alloc(void) __attribute__((__noreturn__)); 32} 33 34namespace __gnu_cxx __attribute__ ((__visibility__ ("default"))) { 35 template<typename _Iterator, typename _Container> 36 class __normal_iterator; 37} 38 39namespace 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 50namespace 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 68namespace 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 100namespace 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 115struct _IO_FILE; 116 117typedef struct _IO_FILE FILE; 118 119typedef struct _IO_FILE __FILE; 120 121typedef __builtin_va_list __gnuc_va_list; 122 123typedef unsigned int size_t; 124typedef unsigned int wint_t; 125 126typedef struct 127{ 128 int __count; 129 union 130 { 131 unsigned int __wch; 132 char __wchb[4]; 133 } __value; 134} __mbstate_t; 135 136 137typedef __mbstate_t mbstate_t; 138 139namespace std __attribute__ ((__visibility__ ("default"))) { 140 using ::mbstate_t; 141} 142 143namespace 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 170namespace __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 193namespace 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 213namespace __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 255namespace 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 287namespace 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 325extern "C" { 326 327typedef int __sig_atomic_t; 328 329typedef struct 330 { 331 unsigned long int __val[(1024 / (8 * sizeof (unsigned long int)))]; 332 } __sigset_t; 333typedef __sigset_t sigset_t; 334} 335typedef unsigned long int pthread_t; 336 337typedef struct __pthread_internal_slist 338{ 339 struct __pthread_internal_slist *__next; 340} __pthread_slist_t; 341 342typedef 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 363typedef unsigned int pthread_key_t; 364 365typedef int pthread_once_t; 366 367extern int pthread_once (pthread_once_t *__once_control, 368 void (*__init_routine) (void)) __attribute__ ((__nonnull__ (1, 2))); 369 370extern int pthread_mutex_lock (pthread_mutex_t *__mutex) 371 throw () __attribute__ ((__nonnull__ (1))); 372 373extern int pthread_mutex_unlock (pthread_mutex_t *__mutex) 374 throw () __attribute__ ((__nonnull__ (1))); 375 376typedef pthread_t __gthread_t; 377typedef pthread_key_t __gthread_key_t; 378typedef pthread_once_t __gthread_once_t; 379typedef pthread_mutex_t __gthread_mutex_t; 380 381static __typeof(pthread_once) __gthrw_pthread_once __attribute__ ((__weakref__("pthread_once"))); 382 383static __typeof(pthread_mutex_lock) __gthrw_pthread_mutex_lock __attribute__ ((__weakref__("pthread_mutex_lock"))); 384 385static __typeof(pthread_mutex_unlock) __gthrw_pthread_mutex_unlock __attribute__ ((__weakref__("pthread_mutex_unlock"))); 386 387static volatile int __gthread_active = -1; 388 389static void 390__gthread_trigger (void) 391{ 392 __gthread_active = 1; 393} 394 395static 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 420typedef int _Atomic_word; 421 422namespace __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 464namespace 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 577namespace 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 889namespace 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 933int 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 945