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