Fixed two problems found by Chris Jefferson: Made operator>> for char consistent...
[lldb.git] / libcxx / include / map
1 // -*- C++ -*-
2 //===----------------------------- map ------------------------------------===//
3 //
4 //                     The LLVM Compiler Infrastructure
5 //
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
8 //
9 //===----------------------------------------------------------------------===//
10
11 #ifndef _LIBCPP_MAP
12 #define _LIBCPP_MAP
13
14 /*
15
16     map synopsis
17
18 namespace std
19 {
20
21 template <class Key, class T, class Compare = less<Key>,
22           class Allocator = allocator<pair<const Key, T>>>
23 class map
24 {
25 public:
26     // types:
27     typedef Key                                      key_type;
28     typedef T                                        mapped_type;
29     typedef pair<const key_type, mapped_type>        value_type;
30     typedef Compare                                  key_compare;
31     typedef Allocator                                allocator_type;
32     typedef typename allocator_type::reference       reference;
33     typedef typename allocator_type::const_reference const_reference;
34     typedef typename allocator_type::pointer         pointer;
35     typedef typename allocator_type::const_pointer   const_pointer;
36     typedef typename allocator_type::size_type       size_type;
37     typedef typename allocator_type::difference_type difference_type;
38
39     typedef implementation-defined                   iterator;
40     typedef implementation-defined                   const_iterator;
41     typedef std::reverse_iterator<iterator>          reverse_iterator;
42     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
43
44     class value_compare
45         : public binary_function<value_type, value_type, bool>
46     {
47         friend class map;
48     protected:
49         key_compare comp;
50
51         value_compare(key_compare c);
52     public:
53         bool operator()(const value_type& x, const value_type& y) const;
54     };
55
56     // construct/copy/destroy:
57     map();
58     explicit map(const key_compare& comp);
59     map(const key_compare& comp, const allocator_type& a);
60     template <class InputIterator>
61         map(InputIterator first, InputIterator last,
62             const key_compare& comp = key_compare());
63     template <class InputIterator>
64         map(InputIterator first, InputIterator last,
65             const key_compare& comp, const allocator_type& a);
66     map(const map& m);
67     map(map&& m);
68     explicit map(const allocator_type& a);
69     map(const map& m, const allocator_type& a);
70     map(map&& m, const allocator_type& a);
71     map(initializer_list<value_type> il, const key_compare& comp = key_compare());
72     map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
73     ~map();
74
75     map& operator=(const map& m);
76     map& operator=(map&& m);
77     map& operator=(initializer_list<value_type> il);
78
79     // iterators:
80           iterator begin();
81     const_iterator begin() const;
82           iterator end();
83     const_iterator end()   const;
84
85           reverse_iterator rbegin();
86     const_reverse_iterator rbegin() const;
87           reverse_iterator rend();
88     const_reverse_iterator rend()   const;
89
90     const_iterator         cbegin()  const;
91     const_iterator         cend()    const;
92     const_reverse_iterator crbegin() const;
93     const_reverse_iterator crend()   const;
94
95     // capacity:
96     bool      empty()    const;
97     size_type size()     const;
98     size_type max_size() const;
99
100     // element access:
101     mapped_type& operator[](const key_type& k);
102     mapped_type& operator[](key_type&& k);
103
104           mapped_type& at(const key_type& k);
105     const mapped_type& at(const key_type& k) const;
106
107     // modifiers:
108     template <class... Args>
109         pair<iterator, bool> emplace(Args&&... args);
110     template <class... Args>
111         iterator emplace_hint(const_iterator position, Args&&... args);
112     pair<iterator, bool> insert(const value_type& v);
113     template <class P>
114         pair<iterator, bool> insert(P&& p);
115     iterator insert(const_iterator position, const value_type& v);
116     template <class P>
117         iterator insert(const_iterator position, P&& p);
118     template <class InputIterator>
119         void insert(InputIterator first, InputIterator last);
120     void insert(initializer_list<value_type> il);
121
122     iterator  erase(const_iterator position);
123     size_type erase(const key_type& k);
124     iterator  erase(const_iterator first, const_iterator last);
125     void clear();
126
127     void swap(map& m);
128
129     // observers:
130     allocator_type get_allocator() const;
131     key_compare    key_comp()      const;
132     value_compare  value_comp()    const;
133
134     // map operations:
135           iterator find(const key_type& k);
136     const_iterator find(const key_type& k) const;
137     size_type      count(const key_type& k) const;
138           iterator lower_bound(const key_type& k);
139     const_iterator lower_bound(const key_type& k) const;
140           iterator upper_bound(const key_type& k);
141     const_iterator upper_bound(const key_type& k) const;
142     pair<iterator,iterator>             equal_range(const key_type& k);
143     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
144 };
145
146 template <class Key, class T, class Compare, class Allocator>
147 bool
148 operator==(const map<Key, T, Compare, Allocator>& x,
149            const map<Key, T, Compare, Allocator>& y);
150
151 template <class Key, class T, class Compare, class Allocator>
152 bool
153 operator< (const map<Key, T, Compare, Allocator>& x,
154            const map<Key, T, Compare, Allocator>& y);
155
156 template <class Key, class T, class Compare, class Allocator>
157 bool
158 operator!=(const map<Key, T, Compare, Allocator>& x,
159            const map<Key, T, Compare, Allocator>& y);
160
161 template <class Key, class T, class Compare, class Allocator>
162 bool
163 operator> (const map<Key, T, Compare, Allocator>& x,
164            const map<Key, T, Compare, Allocator>& y);
165
166 template <class Key, class T, class Compare, class Allocator>
167 bool
168 operator>=(const map<Key, T, Compare, Allocator>& x,
169            const map<Key, T, Compare, Allocator>& y);
170
171 template <class Key, class T, class Compare, class Allocator>
172 bool
173 operator<=(const map<Key, T, Compare, Allocator>& x,
174            const map<Key, T, Compare, Allocator>& y);
175
176 // specialized algorithms:
177 template <class Key, class T, class Compare, class Allocator>
178 void
179 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y);
180
181 template <class Key, class T, class Compare = less<Key>,
182           class Allocator = allocator<pair<const Key, T>>>
183 class multimap
184 {
185 public:
186     // types:
187     typedef Key                                      key_type;
188     typedef T                                        mapped_type;
189     typedef pair<const key_type,mapped_type>         value_type;
190     typedef Compare                                  key_compare;
191     typedef Allocator                                allocator_type;
192     typedef typename allocator_type::reference       reference;
193     typedef typename allocator_type::const_reference const_reference;
194     typedef typename allocator_type::size_type       size_type;
195     typedef typename allocator_type::difference_type difference_type;
196     typedef typename allocator_type::pointer         pointer;
197     typedef typename allocator_type::const_pointer   const_pointer;
198
199     typedef implementation-defined                   iterator;
200     typedef implementation-defined                   const_iterator;
201     typedef std::reverse_iterator<iterator>          reverse_iterator;
202     typedef std::reverse_iterator<const_iterator>    const_reverse_iterator;
203
204     class value_compare
205         : public binary_function<value_type,value_type,bool>
206     {
207         friend class multimap;
208     protected:
209         key_compare comp;
210         value_compare(key_compare c);
211     public:
212         bool operator()(const value_type& x, const value_type& y) const;
213     };
214
215     // construct/copy/destroy:
216     explicit multimap(const key_compare& comp = key_compare());
217     multimap(const key_compare& comp, const allocator_type& a);
218     template <class InputIterator>
219         multimap(InputIterator first, InputIterator last, const key_compare& comp);
220     template <class InputIterator>
221         multimap(InputIterator first, InputIterator last, const key_compare& comp,
222                  const allocator_type& a);
223     multimap(const multimap& m);
224     multimap(multimap&& m);
225     explicit multimap(const allocator_type& a);
226     multimap(const multimap& m, const allocator_type& a);
227     multimap(multimap&& m, const allocator_type& a);
228     multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
229     multimap(initializer_list<value_type> il, const key_compare& comp,
230              const allocator_type& a);
231     ~multimap();
232
233     multimap& operator=(const multimap& m);
234     multimap& operator=(multimap&& m);
235     multimap& operator=(initializer_list<value_type> il);
236
237     // iterators:
238           iterator begin();
239     const_iterator begin() const;
240           iterator end();
241     const_iterator end()   const;
242
243           reverse_iterator rbegin();
244     const_reverse_iterator rbegin() const;
245           reverse_iterator rend();
246     const_reverse_iterator rend()   const;
247
248     const_iterator         cbegin()  const;
249     const_iterator         cend()    const;
250     const_reverse_iterator crbegin() const;
251     const_reverse_iterator crend()   const;
252
253     // capacity:
254     bool      empty()    const;
255     size_type size()     const;
256     size_type max_size() const;
257
258     // modifiers:
259     template <class... Args>
260         iterator emplace(Args&&... args);
261     template <class... Args>
262         iterator emplace_hint(const_iterator position, Args&&... args);
263     iterator insert(const value_type& v);
264     template <class P>
265         iterator insert(P&& p);
266     iterator insert(const_iterator position, const value_type& v);
267     template <class P>
268         iterator insert(const_iterator position, P&& p);
269     template <class InputIterator>
270         void insert(InputIterator first, InputIterator last);
271     void insert(initializer_list<value_type> il);
272
273     iterator  erase(const_iterator position);
274     size_type erase(const key_type& k);
275     iterator  erase(const_iterator first, const_iterator last);
276     void clear();
277
278     void swap(multimap& m);
279
280     // observers:
281     allocator_type get_allocator() const;
282     key_compare    key_comp()      const;
283     value_compare  value_comp()    const;
284
285     // map operations:
286           iterator find(const key_type& k);
287     const_iterator find(const key_type& k) const;
288     size_type      count(const key_type& k) const;
289           iterator lower_bound(const key_type& k);
290     const_iterator lower_bound(const key_type& k) const;
291           iterator upper_bound(const key_type& k);
292     const_iterator upper_bound(const key_type& k) const;
293     pair<iterator,iterator>             equal_range(const key_type& k);
294     pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
295 };
296
297 template <class Key, class T, class Compare, class Allocator>
298 bool
299 operator==(const multimap<Key, T, Compare, Allocator>& x,
300            const multimap<Key, T, Compare, Allocator>& y);
301
302 template <class Key, class T, class Compare, class Allocator>
303 bool
304 operator< (const multimap<Key, T, Compare, Allocator>& x,
305            const multimap<Key, T, Compare, Allocator>& y);
306
307 template <class Key, class T, class Compare, class Allocator>
308 bool
309 operator!=(const multimap<Key, T, Compare, Allocator>& x,
310            const multimap<Key, T, Compare, Allocator>& y);
311
312 template <class Key, class T, class Compare, class Allocator>
313 bool
314 operator> (const multimap<Key, T, Compare, Allocator>& x,
315            const multimap<Key, T, Compare, Allocator>& y);
316
317 template <class Key, class T, class Compare, class Allocator>
318 bool
319 operator>=(const multimap<Key, T, Compare, Allocator>& x,
320            const multimap<Key, T, Compare, Allocator>& y);
321
322 template <class Key, class T, class Compare, class Allocator>
323 bool
324 operator<=(const multimap<Key, T, Compare, Allocator>& x,
325            const multimap<Key, T, Compare, Allocator>& y);
326
327 // specialized algorithms:
328 template <class Key, class T, class Compare, class Allocator>
329 void
330 swap(multimap<Key, T, Compare, Allocator>& x,
331      multimap<Key, T, Compare, Allocator>& y);
332
333 }  // std
334
335 */
336
337 #include <__config>
338 #include <__tree>
339 #include <iterator>
340 #include <memory>
341 #include <utility>
342 #include <functional>
343 #include <initializer_list>
344
345 #pragma GCC system_header
346
347 _LIBCPP_BEGIN_NAMESPACE_STD
348
349 template <class _Key, class _Tp, class _Compare, bool = is_empty<_Compare>::value>
350 class __map_value_compare
351     : private _Compare
352 {
353     typedef pair<typename std::remove_const<_Key>::type, _Tp> _P;
354     typedef pair<const _Key, _Tp> _CP;
355 public:
356     _LIBCPP_INLINE_VISIBILITY
357     __map_value_compare() : _Compare() {}
358     _LIBCPP_INLINE_VISIBILITY
359     __map_value_compare(_Compare c) : _Compare(c) {}
360     _LIBCPP_INLINE_VISIBILITY
361     const _Compare& key_comp() const {return *this;}
362     _LIBCPP_INLINE_VISIBILITY
363     bool operator()(const _CP& __x, const _CP& __y) const
364         {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
365     _LIBCPP_INLINE_VISIBILITY
366     bool operator()(const _CP& __x, const _P& __y) const
367         {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
368     _LIBCPP_INLINE_VISIBILITY
369     bool operator()(const _CP& __x, const _Key& __y) const
370         {return static_cast<const _Compare&>(*this)(__x.first, __y);}
371     _LIBCPP_INLINE_VISIBILITY
372     bool operator()(const _P& __x, const _CP& __y) const
373         {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
374     _LIBCPP_INLINE_VISIBILITY
375     bool operator()(const _P& __x, const _P& __y) const
376         {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
377     _LIBCPP_INLINE_VISIBILITY
378     bool operator()(const _P& __x, const _Key& __y) const
379         {return static_cast<const _Compare&>(*this)(__x.first, __y);}
380     _LIBCPP_INLINE_VISIBILITY
381     bool operator()(const _Key& __x, const _CP& __y) const
382         {return static_cast<const _Compare&>(*this)(__x, __y.first);}
383     _LIBCPP_INLINE_VISIBILITY
384     bool operator()(const _Key& __x, const _P& __y) const
385         {return static_cast<const _Compare&>(*this)(__x, __y.first);}
386     _LIBCPP_INLINE_VISIBILITY
387     bool operator()(const _Key& __x, const _Key& __y) const
388         {return static_cast<const _Compare&>(*this)(__x, __y);}
389 };
390
391 template <class _Key, class _Tp, class _Compare>
392 class __map_value_compare<_Key, _Tp, _Compare, false>
393 {
394     _Compare comp;
395
396     typedef pair<typename std::remove_const<_Key>::type, _Tp> _P;
397     typedef pair<const _Key, _Tp> _CP;
398
399 public:
400     _LIBCPP_INLINE_VISIBILITY
401     __map_value_compare() : comp() {}
402     _LIBCPP_INLINE_VISIBILITY
403     __map_value_compare(_Compare c) : comp(c) {}
404     _LIBCPP_INLINE_VISIBILITY
405     const _Compare& key_comp() const {return comp;}
406
407     _LIBCPP_INLINE_VISIBILITY
408     bool operator()(const _CP& __x, const _CP& __y) const
409         {return comp(__x.first, __y.first);}
410     _LIBCPP_INLINE_VISIBILITY
411     bool operator()(const _CP& __x, const _P& __y) const
412         {return comp(__x.first, __y.first);}
413     _LIBCPP_INLINE_VISIBILITY
414     bool operator()(const _CP& __x, const _Key& __y) const
415         {return comp(__x.first, __y);}
416     _LIBCPP_INLINE_VISIBILITY
417     bool operator()(const _P& __x, const _CP& __y) const
418         {return comp(__x.first, __y.first);}
419     _LIBCPP_INLINE_VISIBILITY
420     bool operator()(const _P& __x, const _P& __y) const
421         {return comp(__x.first, __y.first);}
422     _LIBCPP_INLINE_VISIBILITY
423     bool operator()(const _P& __x, const _Key& __y) const
424         {return comp(__x.first, __y);}
425     _LIBCPP_INLINE_VISIBILITY
426     bool operator()(const _Key& __x, const _CP& __y) const
427         {return comp(__x, __y.first);}
428     _LIBCPP_INLINE_VISIBILITY
429     bool operator()(const _Key& __x, const _P& __y) const
430         {return comp(__x, __y.first);}
431     _LIBCPP_INLINE_VISIBILITY
432     bool operator()(const _Key& __x, const _Key& __y) const
433         {return comp(__x, __y);}
434 };
435
436 template <class _Allocator>
437 class __map_node_destructor
438 {
439     typedef _Allocator                          allocator_type;
440     typedef allocator_traits<allocator_type>    __alloc_traits;
441     typedef typename __alloc_traits::value_type::value_type value_type;
442 public:
443     typedef typename __alloc_traits::pointer    pointer;
444 private:
445     typedef typename value_type::first_type     first_type;
446     typedef typename value_type::second_type    second_type;
447
448     allocator_type& __na_;
449
450     __map_node_destructor& operator=(const __map_node_destructor&);
451
452 public:
453     bool __first_constructed;
454     bool __second_constructed;
455
456     _LIBCPP_INLINE_VISIBILITY
457     explicit __map_node_destructor(allocator_type& __na)
458         : __na_(__na),
459           __first_constructed(false),
460           __second_constructed(false)
461         {}
462
463 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
464     _LIBCPP_INLINE_VISIBILITY
465     __map_node_destructor(__tree_node_destructor<allocator_type>&& __x)
466         : __na_(__x.__na_),
467           __first_constructed(__x.__value_constructed),
468           __second_constructed(__x.__value_constructed)
469         {
470             __x.__value_constructed = false;
471         }
472 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
473
474     _LIBCPP_INLINE_VISIBILITY
475     void operator()(pointer __p)
476     {
477         if (__second_constructed)
478             __alloc_traits::destroy(__na_, _STD::addressof(__p->__value_.second));
479         if (__first_constructed)
480             __alloc_traits::destroy(__na_, _STD::addressof(__p->__value_.first));
481         if (__p)
482             __alloc_traits::deallocate(__na_, __p, 1);
483     }
484 };
485
486 template <class, class, class, class> class map;
487 template <class, class, class, class> class multimap;
488 template <class> class __map_const_iterator;
489
490 template <class _TreeIterator>
491 class _LIBCPP_VISIBLE __map_iterator
492 {
493     _TreeIterator __i_;
494
495     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
496     typedef const typename _TreeIterator::value_type::first_type __key_type;
497     typedef typename _TreeIterator::value_type::second_type      __mapped_type;
498 public:
499     typedef bidirectional_iterator_tag                           iterator_category;
500     typedef pair<__key_type, __mapped_type>                      value_type;
501     typedef typename _TreeIterator::difference_type              difference_type;
502     typedef value_type&                                          reference;
503     typedef typename __pointer_traits::template
504 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
505             rebind<value_type>
506 #else
507             rebind<value_type>::other
508 #endif
509                                                                  pointer;
510
511     _LIBCPP_INLINE_VISIBILITY
512     __map_iterator() {}
513
514     _LIBCPP_INLINE_VISIBILITY
515     __map_iterator(_TreeIterator __i) : __i_(__i) {}
516
517     _LIBCPP_INLINE_VISIBILITY
518     reference operator*() const {return *operator->();}
519     _LIBCPP_INLINE_VISIBILITY
520     pointer operator->() const {return (pointer)__i_.operator->();}
521
522     _LIBCPP_INLINE_VISIBILITY
523     __map_iterator& operator++() {++__i_; return *this;}
524     _LIBCPP_INLINE_VISIBILITY
525     __map_iterator operator++(int)
526     {
527         __map_iterator __t(*this);
528         ++(*this);
529         return __t;
530     }
531
532     _LIBCPP_INLINE_VISIBILITY
533     __map_iterator& operator--() {--__i_; return *this;}
534     _LIBCPP_INLINE_VISIBILITY
535     __map_iterator operator--(int)
536     {
537         __map_iterator __t(*this);
538         --(*this);
539         return __t;
540     }
541
542     friend _LIBCPP_INLINE_VISIBILITY
543     bool operator==(const __map_iterator& __x, const __map_iterator& __y)
544         {return __x.__i_ == __y.__i_;}
545     friend 
546     _LIBCPP_INLINE_VISIBILITY
547     bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
548         {return __x.__i_ != __y.__i_;}
549
550     template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
551     template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
552     template <class> friend class _LIBCPP_VISIBLE __map_const_iterator;
553 };
554
555 template <class _TreeIterator>
556 class _LIBCPP_VISIBLE __map_const_iterator
557 {
558     _TreeIterator __i_;
559
560     typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
561     typedef const typename _TreeIterator::value_type::first_type __key_type;
562     typedef typename _TreeIterator::value_type::second_type      __mapped_type;
563 public:
564     typedef bidirectional_iterator_tag                           iterator_category;
565     typedef pair<__key_type, __mapped_type>                      value_type;
566     typedef typename _TreeIterator::difference_type              difference_type;
567     typedef const value_type&                                    reference;
568     typedef typename __pointer_traits::template
569 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
570             rebind<value_type>
571 #else
572             rebind<value_type>::other
573 #endif
574                                                                  pointer;
575
576     _LIBCPP_INLINE_VISIBILITY
577     __map_const_iterator() {}
578
579     _LIBCPP_INLINE_VISIBILITY
580     __map_const_iterator(_TreeIterator __i) : __i_(__i) {}
581     _LIBCPP_INLINE_VISIBILITY
582     __map_const_iterator(
583             __map_iterator<typename _TreeIterator::__non_const_iterator> __i)
584                 : __i_(__i.__i_) {}
585
586     _LIBCPP_INLINE_VISIBILITY
587     reference operator*() const {return *operator->();}
588     _LIBCPP_INLINE_VISIBILITY
589     pointer operator->() const {return (pointer)__i_.operator->();}
590
591     _LIBCPP_INLINE_VISIBILITY
592     __map_const_iterator& operator++() {++__i_; return *this;}
593     _LIBCPP_INLINE_VISIBILITY
594     __map_const_iterator operator++(int)
595     {
596         __map_const_iterator __t(*this);
597         ++(*this);
598         return __t;
599     }
600
601     _LIBCPP_INLINE_VISIBILITY
602     __map_const_iterator& operator--() {--__i_; return *this;}
603     _LIBCPP_INLINE_VISIBILITY
604     __map_const_iterator operator--(int)
605     {
606         __map_const_iterator __t(*this);
607         --(*this);
608         return __t;
609     }
610
611     friend _LIBCPP_INLINE_VISIBILITY
612     bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
613         {return __x.__i_ == __y.__i_;}
614     friend _LIBCPP_INLINE_VISIBILITY
615     bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
616         {return __x.__i_ != __y.__i_;}
617
618     template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
619     template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
620     template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator;
621 };
622
623 template <class _Key, class _Tp, class _Compare = less<_Key>,
624           class _Allocator = allocator<pair<const _Key, _Tp> > >
625 class _LIBCPP_VISIBLE map
626 {
627 public:
628     // types:
629     typedef _Key                                     key_type;
630     typedef _Tp                                      mapped_type;
631     typedef pair<const key_type, mapped_type>        value_type;
632     typedef _Compare                                 key_compare;
633     typedef _Allocator                               allocator_type;
634     typedef value_type&                              reference;
635     typedef const value_type&                        const_reference;
636
637     class _LIBCPP_VISIBLE value_compare
638         : public binary_function<value_type, value_type, bool>
639     {
640         friend class map;
641     protected:
642         key_compare comp;
643
644         _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
645     public:
646         _LIBCPP_INLINE_VISIBILITY
647         bool operator()(const value_type& __x, const value_type& __y) const
648             {return comp(__x.first, __y.first);}
649     };
650
651 private:
652     typedef pair<key_type, mapped_type>                             __value_type;
653     typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
654     typedef typename allocator_traits<allocator_type>::template
655 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
656             rebind_alloc<__value_type>
657 #else
658             rebind_alloc<__value_type>::other
659 #endif
660                                                            __allocator_type;
661     typedef __tree<__value_type, __vc, __allocator_type>   __base;
662     typedef typename __base::__node_traits                 __node_traits;
663     typedef allocator_traits<allocator_type>               __alloc_traits;
664
665     __base __tree_;
666
667 public:
668     typedef typename __alloc_traits::pointer               pointer;
669     typedef typename __alloc_traits::const_pointer         const_pointer;
670     typedef typename __alloc_traits::size_type             size_type;
671     typedef typename __alloc_traits::difference_type       difference_type;
672     typedef __map_iterator<typename __base::iterator>      iterator;
673     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
674     typedef _STD::reverse_iterator<iterator>               reverse_iterator;
675     typedef _STD::reverse_iterator<const_iterator>         const_reverse_iterator;
676
677     _LIBCPP_INLINE_VISIBILITY
678     explicit map(const key_compare& __comp = key_compare())
679         : __tree_(__vc(__comp)) {}
680
681     _LIBCPP_INLINE_VISIBILITY
682     explicit map(const key_compare& __comp, const allocator_type& __a)
683         : __tree_(__vc(__comp), __a) {}
684
685     template <class _InputIterator>
686     _LIBCPP_INLINE_VISIBILITY
687         map(_InputIterator __f, _InputIterator __l,
688             const key_compare& __comp = key_compare())
689         : __tree_(__vc(__comp))
690         {
691             insert(__f, __l);
692         }
693
694     template <class _InputIterator>
695     _LIBCPP_INLINE_VISIBILITY
696         map(_InputIterator __f, _InputIterator __l,
697             const key_compare& __comp, const allocator_type& __a)
698         : __tree_(__vc(__comp), __a)
699         {
700             insert(__f, __l);
701         }
702
703     _LIBCPP_INLINE_VISIBILITY
704     map(const map& __m)
705         : __tree_(__m.__tree_)
706         {
707             insert(__m.begin(), __m.end());
708         }
709
710 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
711
712     _LIBCPP_INLINE_VISIBILITY
713     map(map&& __m)
714         : __tree_(_STD::move(__m.__tree_))
715         {
716         }
717
718     map(map&& __m, const allocator_type& __a);
719
720     _LIBCPP_INLINE_VISIBILITY
721     map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
722         : __tree_(__vc(__comp))
723         {
724             insert(__il.begin(), __il.end());
725         }
726
727     _LIBCPP_INLINE_VISIBILITY
728     map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
729         : __tree_(__vc(__comp), __a)
730         {
731             insert(__il.begin(), __il.end());
732         }
733
734     _LIBCPP_INLINE_VISIBILITY
735     map& operator=(map&& __m)
736         {
737             __tree_ = _STD::move(__m.__tree_);
738             return *this;
739         }
740
741     _LIBCPP_INLINE_VISIBILITY
742     map& operator=(initializer_list<value_type> __il)
743         {
744             __tree_.__assign_unique(__il.begin(), __il.end());
745             return *this;
746         }
747
748 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
749
750     _LIBCPP_INLINE_VISIBILITY
751     explicit map(const allocator_type& __a)
752         : __tree_(__a)
753         {
754         }
755
756     _LIBCPP_INLINE_VISIBILITY
757     map(const map& __m, const allocator_type& __a)
758         : __tree_(__m.__tree_.value_comp(), __a)
759         {
760             insert(__m.begin(), __m.end());
761         }
762
763     _LIBCPP_INLINE_VISIBILITY
764           iterator begin()       {return __tree_.begin();}
765     _LIBCPP_INLINE_VISIBILITY
766     const_iterator begin() const {return __tree_.begin();}
767     _LIBCPP_INLINE_VISIBILITY
768           iterator end()         {return __tree_.end();}
769     _LIBCPP_INLINE_VISIBILITY
770     const_iterator end()   const {return __tree_.end();}
771
772     _LIBCPP_INLINE_VISIBILITY
773           reverse_iterator rbegin()       {return       reverse_iterator(end());}
774     _LIBCPP_INLINE_VISIBILITY
775     const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
776     _LIBCPP_INLINE_VISIBILITY
777           reverse_iterator rend()         {return       reverse_iterator(begin());}
778     _LIBCPP_INLINE_VISIBILITY
779     const_reverse_iterator rend()   const {return const_reverse_iterator(begin());}
780
781     _LIBCPP_INLINE_VISIBILITY
782     const_iterator         cbegin()  const {return begin();}
783     _LIBCPP_INLINE_VISIBILITY
784     const_iterator         cend()    const {return end();}
785     _LIBCPP_INLINE_VISIBILITY
786     const_reverse_iterator crbegin() const {return rbegin();}
787     _LIBCPP_INLINE_VISIBILITY
788     const_reverse_iterator crend()   const {return rend();}
789
790     _LIBCPP_INLINE_VISIBILITY
791     bool      empty()    const {return __tree_.size() == 0;}
792     _LIBCPP_INLINE_VISIBILITY
793     size_type size()     const {return __tree_.size();}
794     _LIBCPP_INLINE_VISIBILITY
795     size_type max_size() const {return __tree_.max_size();}
796
797     mapped_type& operator[](const key_type& __k);
798 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
799     mapped_type& operator[](key_type&& __k);
800 #endif
801
802           mapped_type& at(const key_type& __k);
803     const mapped_type& at(const key_type& __k) const;
804
805     _LIBCPP_INLINE_VISIBILITY
806     allocator_type get_allocator() const {return __tree_.__alloc();}
807     _LIBCPP_INLINE_VISIBILITY
808     key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
809     _LIBCPP_INLINE_VISIBILITY
810     value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
811
812 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
813
814     _LIBCPP_INLINE_VISIBILITY
815     pair<iterator, bool>
816         emplace() {return __tree_.__emplace_unique();}
817
818     template <class _A0,
819               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
820         _LIBCPP_INLINE_VISIBILITY
821         pair<iterator, bool>
822         emplace(_A0&& __a0)
823             {return __tree_.__emplace_unique(_STD::forward<_A0>(__a0));}
824
825 #ifndef _LIBCPP_HAS_NO_VARIADICS
826
827     template <class _A0, class ..._Args,
828               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
829         pair<iterator, bool>
830         emplace(_A0&& __a0, _Args&& ...__args);
831
832 #endif  // _LIBCPP_HAS_NO_VARIADICS
833
834     _LIBCPP_INLINE_VISIBILITY
835     iterator
836     emplace_hint(const_iterator __p)
837         {return __tree_.__emplace_hint_unique(__p.__i_);}
838
839     template <class _A0,
840               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
841         _LIBCPP_INLINE_VISIBILITY
842         iterator
843         emplace_hint(const_iterator __p, _A0&& __a0)
844             {return __tree_.__emplace_hint_unique(__p.__i_, _STD::forward<_A0>(__a0));}
845
846 #ifndef _LIBCPP_HAS_NO_VARIADICS
847
848     template <class _A0, class ..._Args,
849               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
850         iterator
851         emplace_hint(const_iterator __p, _A0&& __a0, _Args&& ...__args);
852
853 #endif  // _LIBCPP_HAS_NO_VARIADICS
854
855     template <class _P,
856               class = typename enable_if<is_convertible<_P, value_type>::value>::type>
857         _LIBCPP_INLINE_VISIBILITY
858         pair<iterator, bool> insert(_P&& __p)
859             {return __tree_.__insert_unique(_STD::forward<_P>(__p));}
860
861     template <class _P,
862               class = typename enable_if<is_convertible<_P, value_type>::value>::type>
863         _LIBCPP_INLINE_VISIBILITY
864         iterator insert(const_iterator __pos, _P&& __p)
865             {return __tree_.__insert_unique(__pos.__i_, _STD::forward<_P>(__p));}
866
867 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
868
869     _LIBCPP_INLINE_VISIBILITY
870     pair<iterator, bool>
871         insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
872
873     _LIBCPP_INLINE_VISIBILITY
874     iterator
875         insert(const_iterator __p, const value_type& __v)
876             {return __tree_.__insert_unique(__p.__i_, __v);}
877
878     template <class _InputIterator>
879         _LIBCPP_INLINE_VISIBILITY
880         void insert(_InputIterator __f, _InputIterator __l)
881         {
882             for (const_iterator __e = cend(); __f != __l; ++__f)
883                 insert(__e.__i_, *__f);
884         }
885
886     _LIBCPP_INLINE_VISIBILITY
887     void insert(initializer_list<value_type> __il)
888         {insert(__il.begin(), __il.end());}
889
890     _LIBCPP_INLINE_VISIBILITY
891     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
892     _LIBCPP_INLINE_VISIBILITY
893     size_type erase(const key_type& __k)
894         {return __tree_.__erase_unique(__k);}
895     _LIBCPP_INLINE_VISIBILITY
896     iterator  erase(const_iterator __f, const_iterator __l)
897         {return __tree_.erase(__f.__i_, __l.__i_);}
898     _LIBCPP_INLINE_VISIBILITY
899     void clear() {__tree_.clear();}
900
901     _LIBCPP_INLINE_VISIBILITY
902     void swap(map& __m) {__tree_.swap(__m.__tree_);}
903
904     _LIBCPP_INLINE_VISIBILITY
905     iterator find(const key_type& __k)             {return __tree_.find(__k);}
906     _LIBCPP_INLINE_VISIBILITY
907     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
908     _LIBCPP_INLINE_VISIBILITY
909     size_type      count(const key_type& __k) const
910         {return __tree_.__count_unique(__k);}
911     _LIBCPP_INLINE_VISIBILITY
912     iterator lower_bound(const key_type& __k)
913         {return __tree_.lower_bound(__k);}
914     _LIBCPP_INLINE_VISIBILITY
915     const_iterator lower_bound(const key_type& __k) const
916         {return __tree_.lower_bound(__k);}
917     _LIBCPP_INLINE_VISIBILITY
918     iterator upper_bound(const key_type& __k)
919         {return __tree_.upper_bound(__k);}
920     _LIBCPP_INLINE_VISIBILITY
921     const_iterator upper_bound(const key_type& __k) const
922         {return __tree_.upper_bound(__k);}
923     _LIBCPP_INLINE_VISIBILITY
924     pair<iterator,iterator> equal_range(const key_type& __k)
925         {return __tree_.__equal_range_unique(__k);}
926     _LIBCPP_INLINE_VISIBILITY
927     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
928         {return __tree_.__equal_range_unique(__k);}
929
930 private:
931     typedef typename __base::__node                    __node;
932     typedef typename __base::__node_allocator          __node_allocator;
933     typedef typename __base::__node_pointer            __node_pointer;
934     typedef typename __base::__node_const_pointer      __node_const_pointer;
935     typedef typename __base::__node_base_pointer       __node_base_pointer;
936     typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
937     typedef __map_node_destructor<__node_allocator> _D;
938     typedef unique_ptr<__node, _D> __node_holder;
939
940 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
941     __node_holder __construct_node();
942     template <class _A0,
943               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
944         __node_holder __construct_node(_A0&& __a0);
945 #ifndef _LIBCPP_HAS_NO_VARIADICS
946     template <class _A0, class ..._Args,
947               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
948         __node_holder __construct_node(_A0&& __a0, _Args&& ...__args);
949 #endif  // _LIBCPP_HAS_NO_VARIADICS
950 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
951     __node_holder __construct_node(const key_type& __k);
952 #endif
953
954     __node_base_pointer&
955         __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
956     __node_base_pointer&
957         __find_equal_key(const_iterator __hint,
958                          __node_base_pointer& __parent, const key_type& __k);
959     __node_base_const_pointer
960         __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
961 };
962
963 // Find place to insert if __k doesn't exist
964 // Set __parent to parent of null leaf
965 // Return reference to null leaf
966 // If __k exists, set parent to node of __k and return reference to node of __k
967 template <class _Key, class _Tp, class _Compare, class _Allocator>
968 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
969 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
970                                                        const key_type& __k)
971 {
972     __node_pointer __nd = __tree_.__root();
973     if (__nd != nullptr)
974     {
975         while (true)
976         {
977             if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
978             {
979                 if (__nd->__left_ != nullptr)
980                     __nd = static_cast<__node_pointer>(__nd->__left_);
981                 else
982                 {
983                     __parent = __nd;
984                     return __parent->__left_;
985                 }
986             }
987             else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
988             {
989                 if (__nd->__right_ != nullptr)
990                     __nd = static_cast<__node_pointer>(__nd->__right_);
991                 else
992                 {
993                     __parent = __nd;
994                     return __parent->__right_;
995                 }
996             }
997             else
998             {
999                 __parent = __nd;
1000                 return __parent;
1001             }
1002         }
1003     }
1004     __parent = __tree_.__end_node();
1005     return __parent->__left_;
1006 }
1007
1008 // Find place to insert if __k doesn't exist
1009 // First check prior to __hint.
1010 // Next check after __hint.
1011 // Next do O(log N) search.
1012 // Set __parent to parent of null leaf
1013 // Return reference to null leaf
1014 // If __k exists, set parent to node of __k and return reference to node of __k
1015 template <class _Key, class _Tp, class _Compare, class _Allocator>
1016 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1017 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(const_iterator __hint,
1018                                                        __node_base_pointer& __parent,
1019                                                        const key_type& __k)
1020 {
1021     if (__hint == end() || __tree_.value_comp().key_comp()(__k, __hint->first))  // check before
1022     {
1023         // __k < *__hint
1024         const_iterator __prior = __hint;
1025         if (__prior == begin() || __tree_.value_comp().key_comp()((--__prior)->first, __k))
1026         {
1027             // *prev(__hint) < __k < *__hint
1028             if (__hint.__ptr_->__left_ == nullptr)
1029             {
1030                 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1031                 return __parent->__left_;
1032             }
1033             else
1034             {
1035                 __parent = const_cast<__node_pointer&>(__prior.__ptr_);
1036                 return __parent->__right_;
1037             }
1038         }
1039         // __k <= *prev(__hint)
1040         return __find_equal_key(__parent, __k);
1041     }
1042     else if (__tree_.value_comp().key_comp()(__hint->first, __k))  // check after
1043     {
1044         // *__hint < __k
1045         const_iterator __next = _STD::next(__hint);
1046         if (__next == end() || __tree_.value_comp().key_comp()(__k, __next->first))
1047         {
1048             // *__hint < __k < *next(__hint)
1049             if (__hint.__ptr_->__right_ == nullptr)
1050             {
1051                 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1052                 return __parent->__right_;
1053             }
1054             else
1055             {
1056                 __parent = const_cast<__node_pointer&>(__next.__ptr_);
1057                 return __parent->__left_;
1058             }
1059         }
1060         // *next(__hint) <= __k
1061         return __find_equal_key(__parent, __k);
1062     }
1063     // else __k == *__hint
1064     __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1065     return __parent;
1066 }
1067
1068 // Find __k
1069 // Set __parent to parent of null leaf and
1070 //    return reference to null leaf iv __k does not exist.
1071 // If __k exists, set parent to node of __k and return reference to node of __k
1072 template <class _Key, class _Tp, class _Compare, class _Allocator>
1073 typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1074 map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1075                                                        const key_type& __k) const
1076 {
1077     __node_const_pointer __nd = __tree_.__root();
1078     if (__nd != nullptr)
1079     {
1080         while (true)
1081         {
1082             if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
1083             {
1084                 if (__nd->__left_ != nullptr)
1085                     __nd = static_cast<__node_pointer>(__nd->__left_);
1086                 else
1087                 {
1088                     __parent = __nd;
1089                     return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1090                 }
1091             }
1092             else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
1093             {
1094                 if (__nd->__right_ != nullptr)
1095                     __nd = static_cast<__node_pointer>(__nd->__right_);
1096                 else
1097                 {
1098                     __parent = __nd;
1099                     return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1100                 }
1101             }
1102             else
1103             {
1104                 __parent = __nd;
1105                 return __parent;
1106             }
1107         }
1108     }
1109     __parent = __tree_.__end_node();
1110     return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1111 }
1112
1113 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1114
1115 template <class _Key, class _Tp, class _Compare, class _Allocator>
1116 map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1117     : __tree_(_STD::move(__m.__tree_), __a)
1118 {
1119     if (__a != __m.get_allocator())
1120     {
1121         const_iterator __e = cend();
1122         while (!__m.empty())
1123             __tree_.__insert_unique(__e.__i_,
1124                     _STD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1125     }
1126 }
1127
1128 template <class _Key, class _Tp, class _Compare, class _Allocator>
1129 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1130 map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1131 {
1132     __node_allocator& __na = __tree_.__node_alloc();
1133     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1134     __node_traits::construct(__na, _STD::addressof(__h->__value_.first));
1135     __h.get_deleter().__first_constructed = true;
1136     __node_traits::construct(__na, _STD::addressof(__h->__value_.second));
1137     __h.get_deleter().__second_constructed = true;
1138     return __h;
1139 }
1140
1141 template <class _Key, class _Tp, class _Compare, class _Allocator>
1142 template <class _A0,
1143           class>
1144 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1145 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1146 {
1147     __node_allocator& __na = __tree_.__node_alloc();
1148     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1149     __node_traits::construct(__na, _STD::addressof(__h->__value_), _STD::forward<_A0>(__a0));
1150     __h.get_deleter().__first_constructed = true;
1151     __h.get_deleter().__second_constructed = true;
1152     return __h;
1153 }
1154
1155 #ifndef _LIBCPP_HAS_NO_VARIADICS
1156
1157 template <class _Key, class _Tp, class _Compare, class _Allocator>
1158 template <class _A0, class ..._Args,
1159           class>
1160 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1161 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _Args&& ...__args)
1162 {
1163     __node_allocator& __na = __tree_.__node_alloc();
1164     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1165     __node_traits::construct(__na, _STD::addressof(__h->__value_.first), _STD::forward<_A0>(__a0));
1166     __h.get_deleter().__first_constructed = true;
1167     __node_traits::construct(__na, _STD::addressof(__h->__value_.second), _STD::forward<_Args>(__args)...);
1168     __h.get_deleter().__second_constructed = true;
1169     return __h;
1170 }
1171
1172 #endif  // _LIBCPP_HAS_NO_VARIADICS
1173
1174 #else  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1175
1176 template <class _Key, class _Tp, class _Compare, class _Allocator>
1177 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1178 map<_Key, _Tp, _Compare, _Allocator>::__construct_node(const key_type& __k)
1179 {
1180     __node_allocator& __na = __tree_.__node_alloc();
1181     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1182     __node_traits::construct(__na, _STD::addressof(__h->__value_.first), __k);
1183     __h.get_deleter().__first_constructed = true;
1184     __node_traits::construct(__na, _STD::addressof(__h->__value_.second));
1185     __h.get_deleter().__second_constructed = true;
1186     return _STD::move(__h);
1187 }
1188
1189 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1190
1191 template <class _Key, class _Tp, class _Compare, class _Allocator>
1192 _Tp&
1193 map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1194 {
1195     __node_base_pointer __parent;
1196     __node_base_pointer& __child = __find_equal_key(__parent, __k);
1197     __node_pointer __r = static_cast<__node_pointer>(__child);
1198     if (__child == nullptr)
1199     {
1200         __node_holder __h = __construct_node(__k);
1201         __tree_.__insert_node_at(__parent, __child, __h.get());
1202         __r = __h.release();
1203     }
1204     return __r->__value_.second;
1205 }
1206
1207 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1208
1209 template <class _Key, class _Tp, class _Compare, class _Allocator>
1210 _Tp&
1211 map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1212 {
1213     __node_base_pointer __parent;
1214     __node_base_pointer& __child = __find_equal_key(__parent, __k);
1215     __node_pointer __r = static_cast<__node_pointer>(__child);
1216     if (__child == nullptr)
1217     {
1218         __node_holder __h = __construct_node(_STD::move(__k));
1219         __tree_.__insert_node_at(__parent, __child, __h.get());
1220         __r = __h.release();
1221     }
1222     return __r->__value_.second;
1223 }
1224
1225 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1226
1227 template <class _Key, class _Tp, class _Compare, class _Allocator>
1228 _Tp&
1229 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1230 {
1231     __node_base_pointer __parent;
1232     __node_base_pointer& __child = __find_equal_key(__parent, __k);
1233 #ifndef _LIBCPP_NO_EXCEPTIONS
1234     if (__child == nullptr)
1235         throw out_of_range("map::at:  key not found");
1236 #endif  // _LIBCPP_NO_EXCEPTIONS
1237     return static_cast<__node_pointer>(__child)->__value_.second;
1238 }
1239
1240 template <class _Key, class _Tp, class _Compare, class _Allocator>
1241 const _Tp&
1242 map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1243 {
1244     __node_base_const_pointer __parent;
1245     __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1246 #ifndef _LIBCPP_NO_EXCEPTIONS
1247     if (__child == nullptr)
1248         throw out_of_range("map::at:  key not found");
1249 #endif  // _LIBCPP_NO_EXCEPTIONS
1250     return static_cast<__node_const_pointer>(__child)->__value_.second;
1251 }
1252
1253 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1254
1255 template <class _Key, class _Tp, class _Compare, class _Allocator>
1256 template <class _A0, class ..._Args,
1257           class //= typename enable_if<is_convertible<_A0, _Key>::value>::type
1258          >
1259 pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1260 map<_Key, _Tp, _Compare, _Allocator>::emplace(_A0&& __a0, _Args&& ...__args)
1261 {
1262     __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1263                                          _STD::forward<_Args>(__args)...);
1264     pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1265     if (__r.second)
1266         __h.release();
1267     return __r;
1268 }
1269
1270 template <class _Key, class _Tp, class _Compare, class _Allocator>
1271 template <class _A0, class ..._Args,
1272           class //= typename enable_if<is_convertible<_A0, _Key>::value>::type
1273          >
1274 typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1275 map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1276                                                    _A0&& __a0, _Args&& ...__args)
1277 {
1278     __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1279                                          _STD::forward<_Args>(__args)...);
1280     iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1281     if (__r.__i_.__ptr_ == __h.get())
1282         __h.release();
1283     return __r;
1284 }
1285
1286 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1287
1288 template <class _Key, class _Tp, class _Compare, class _Allocator>
1289 inline _LIBCPP_INLINE_VISIBILITY
1290 bool
1291 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1292            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1293 {
1294     return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
1295 }
1296
1297 template <class _Key, class _Tp, class _Compare, class _Allocator>
1298 inline _LIBCPP_INLINE_VISIBILITY
1299 bool
1300 operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1301            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1302 {
1303     return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1304 }
1305
1306 template <class _Key, class _Tp, class _Compare, class _Allocator>
1307 inline _LIBCPP_INLINE_VISIBILITY
1308 bool
1309 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1310            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1311 {
1312     return !(__x == __y);
1313 }
1314
1315 template <class _Key, class _Tp, class _Compare, class _Allocator>
1316 inline _LIBCPP_INLINE_VISIBILITY
1317 bool
1318 operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1319            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1320 {
1321     return __y < __x;
1322 }
1323
1324 template <class _Key, class _Tp, class _Compare, class _Allocator>
1325 inline _LIBCPP_INLINE_VISIBILITY
1326 bool
1327 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1328            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1329 {
1330     return !(__x < __y);
1331 }
1332
1333 template <class _Key, class _Tp, class _Compare, class _Allocator>
1334 inline _LIBCPP_INLINE_VISIBILITY
1335 bool
1336 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1337            const map<_Key, _Tp, _Compare, _Allocator>& __y)
1338 {
1339     return !(__y < __x);
1340 }
1341
1342 template <class _Key, class _Tp, class _Compare, class _Allocator>
1343 inline _LIBCPP_INLINE_VISIBILITY
1344 void
1345 swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1346      map<_Key, _Tp, _Compare, _Allocator>& __y)
1347 {
1348     __x.swap(__y);
1349 }
1350
1351 template <class _Key, class _Tp, class _Compare = less<_Key>,
1352           class _Allocator = allocator<pair<const _Key, _Tp> > >
1353 class _LIBCPP_VISIBLE multimap
1354 {
1355 public:
1356     // types:
1357     typedef _Key                                     key_type;
1358     typedef _Tp                                      mapped_type;
1359     typedef pair<const key_type, mapped_type>        value_type;
1360     typedef _Compare                                 key_compare;
1361     typedef _Allocator                               allocator_type;
1362     typedef value_type&                              reference;
1363     typedef const value_type&                        const_reference;
1364
1365     class _LIBCPP_VISIBLE value_compare
1366         : public binary_function<value_type, value_type, bool>
1367     {
1368         friend class multimap;
1369     protected:
1370         key_compare comp;
1371
1372         _LIBCPP_INLINE_VISIBILITY
1373         value_compare(key_compare c) : comp(c) {}
1374     public:
1375         _LIBCPP_INLINE_VISIBILITY
1376         bool operator()(const value_type& __x, const value_type& __y) const
1377             {return comp(__x.first, __y.first);}
1378     };
1379
1380 private:
1381     typedef pair<key_type, mapped_type>                             __value_type;
1382     typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
1383     typedef typename allocator_traits<allocator_type>::template
1384 #ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1385             rebind_alloc<__value_type>
1386 #else
1387             rebind_alloc<__value_type>::other
1388 #endif
1389                                                                     __allocator_type;
1390     typedef __tree<__value_type, __vc, __allocator_type>            __base;
1391     typedef typename __base::__node_traits                          __node_traits;
1392     typedef allocator_traits<allocator_type>                        __alloc_traits;
1393
1394     __base __tree_;
1395
1396 public:
1397     typedef typename __alloc_traits::pointer               pointer;
1398     typedef typename __alloc_traits::const_pointer         const_pointer;
1399     typedef typename __alloc_traits::size_type             size_type;
1400     typedef typename __alloc_traits::difference_type       difference_type;
1401     typedef __map_iterator<typename __base::iterator>      iterator;
1402     typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1403     typedef _STD::reverse_iterator<iterator>               reverse_iterator;
1404     typedef _STD::reverse_iterator<const_iterator>         const_reverse_iterator;
1405
1406     _LIBCPP_INLINE_VISIBILITY
1407     explicit multimap(const key_compare& __comp = key_compare())
1408         : __tree_(__vc(__comp)) {}
1409
1410     _LIBCPP_INLINE_VISIBILITY
1411     explicit multimap(const key_compare& __comp, const allocator_type& __a)
1412         : __tree_(__vc(__comp), __a) {}
1413
1414     template <class _InputIterator>
1415         _LIBCPP_INLINE_VISIBILITY
1416         multimap(_InputIterator __f, _InputIterator __l,
1417             const key_compare& __comp = key_compare())
1418         : __tree_(__vc(__comp))
1419         {
1420             insert(__f, __l);
1421         }
1422
1423     template <class _InputIterator>
1424         _LIBCPP_INLINE_VISIBILITY
1425         multimap(_InputIterator __f, _InputIterator __l,
1426             const key_compare& __comp, const allocator_type& __a)
1427         : __tree_(__vc(__comp), __a)
1428         {
1429             insert(__f, __l);
1430         }
1431
1432     _LIBCPP_INLINE_VISIBILITY
1433     multimap(const multimap& __m)
1434         : __tree_(__m.__tree_.value_comp(),
1435           __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1436         {
1437             insert(__m.begin(), __m.end());
1438         }
1439
1440 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1441
1442     _LIBCPP_INLINE_VISIBILITY
1443     multimap(multimap&& __m)
1444         : __tree_(_STD::move(__m.__tree_))
1445         {
1446         }
1447
1448     multimap(multimap&& __m, const allocator_type& __a);
1449
1450     _LIBCPP_INLINE_VISIBILITY
1451     multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1452         : __tree_(__vc(__comp))
1453         {
1454             insert(__il.begin(), __il.end());
1455         }
1456
1457     _LIBCPP_INLINE_VISIBILITY
1458     multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1459         : __tree_(__vc(__comp), __a)
1460         {
1461             insert(__il.begin(), __il.end());
1462         }
1463
1464     _LIBCPP_INLINE_VISIBILITY
1465     multimap& operator=(multimap&& __m)
1466         {
1467             __tree_ = _STD::move(__m.__tree_);
1468             return *this;
1469         }
1470
1471     _LIBCPP_INLINE_VISIBILITY
1472     multimap& operator=(initializer_list<value_type> __il)
1473         {
1474             __tree_.__assign_multi(__il.begin(), __il.end());
1475             return *this;
1476         }
1477 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1478
1479     _LIBCPP_INLINE_VISIBILITY
1480     explicit multimap(const allocator_type& __a)
1481         : __tree_(__a)
1482         {
1483         }
1484
1485     _LIBCPP_INLINE_VISIBILITY
1486     multimap(const multimap& __m, const allocator_type& __a)
1487         : __tree_(__m.__tree_.value_comp(), __a)
1488         {
1489             insert(__m.begin(), __m.end());
1490         }
1491
1492     _LIBCPP_INLINE_VISIBILITY
1493           iterator begin()       {return __tree_.begin();}
1494     _LIBCPP_INLINE_VISIBILITY
1495     const_iterator begin() const {return __tree_.begin();}
1496     _LIBCPP_INLINE_VISIBILITY
1497           iterator end()         {return __tree_.end();}
1498     _LIBCPP_INLINE_VISIBILITY
1499     const_iterator end()   const {return __tree_.end();}
1500
1501     _LIBCPP_INLINE_VISIBILITY
1502           reverse_iterator rbegin()       {return       reverse_iterator(end());}
1503     _LIBCPP_INLINE_VISIBILITY
1504     const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
1505     _LIBCPP_INLINE_VISIBILITY
1506           reverse_iterator rend()         {return       reverse_iterator(begin());}
1507     _LIBCPP_INLINE_VISIBILITY
1508     const_reverse_iterator rend()   const {return const_reverse_iterator(begin());}
1509
1510     _LIBCPP_INLINE_VISIBILITY
1511     const_iterator         cbegin()  const {return begin();}
1512     _LIBCPP_INLINE_VISIBILITY
1513     const_iterator         cend()    const {return end();}
1514     _LIBCPP_INLINE_VISIBILITY
1515     const_reverse_iterator crbegin() const {return rbegin();}
1516     _LIBCPP_INLINE_VISIBILITY
1517     const_reverse_iterator crend()   const {return rend();}
1518
1519     _LIBCPP_INLINE_VISIBILITY
1520     bool      empty()    const {return __tree_.size() == 0;}
1521     _LIBCPP_INLINE_VISIBILITY
1522     size_type size()     const {return __tree_.size();}
1523     _LIBCPP_INLINE_VISIBILITY
1524     size_type max_size() const {return __tree_.max_size();}
1525
1526     _LIBCPP_INLINE_VISIBILITY
1527     allocator_type get_allocator() const {return __tree_.__alloc();}
1528     _LIBCPP_INLINE_VISIBILITY
1529     key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
1530     _LIBCPP_INLINE_VISIBILITY
1531     value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
1532
1533 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1534
1535     _LIBCPP_INLINE_VISIBILITY
1536     iterator emplace() {return __tree_.__emplace_multi();}
1537
1538     template <class _A0,
1539               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
1540         _LIBCPP_INLINE_VISIBILITY
1541         iterator
1542         emplace(_A0&& __a0)
1543             {return __tree_.__emplace_multi(_STD::forward<_A0>(__a0));}
1544
1545 #ifndef _LIBCPP_HAS_NO_VARIADICS
1546
1547     template <class _A0, class ..._Args,
1548               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1549         iterator
1550         emplace(_A0&& __a0, _Args&& ...__args);
1551
1552 #endif  // _LIBCPP_HAS_NO_VARIADICS
1553
1554     _LIBCPP_INLINE_VISIBILITY
1555     iterator emplace_hint(const_iterator __p)
1556         {return __tree_.__emplace_hint_multi(__p.__i_);}
1557
1558     template <class _A0,
1559               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
1560         _LIBCPP_INLINE_VISIBILITY
1561         iterator
1562         emplace_hint(const_iterator __p, _A0&& __a0)
1563             {return __tree_.__emplace_hint_multi(__p.__i_, _STD::forward<_A0>(__a0));}
1564
1565 #ifndef _LIBCPP_HAS_NO_VARIADICS
1566
1567     template <class _A0, class ..._Args,
1568               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1569         iterator
1570         emplace_hint(const_iterator __p, _A0&& __a0, _Args&& ...__args);
1571
1572 #endif  // _LIBCPP_HAS_NO_VARIADICS
1573
1574     template <class _P,
1575               class = typename enable_if<is_convertible<_P, value_type>::value>::type>
1576         _LIBCPP_INLINE_VISIBILITY
1577         iterator insert(_P&& __p)
1578             {return __tree_.__insert_multi(_STD::forward<_P>(__p));}
1579
1580     template <class _P,
1581               class = typename enable_if<is_convertible<_P, value_type>::value>::type>
1582         _LIBCPP_INLINE_VISIBILITY
1583         iterator insert(const_iterator __pos, _P&& __p)
1584             {return __tree_.__insert_multi(__pos.__i_, _STD::forward<_P>(__p));}
1585
1586 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1587
1588     _LIBCPP_INLINE_VISIBILITY
1589     iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1590
1591     _LIBCPP_INLINE_VISIBILITY
1592     iterator insert(const_iterator __p, const value_type& __v)
1593             {return __tree_.__insert_multi(__p.__i_, __v);}
1594
1595     template <class _InputIterator>
1596         _LIBCPP_INLINE_VISIBILITY
1597         void insert(_InputIterator __f, _InputIterator __l)
1598         {
1599             for (const_iterator __e = cend(); __f != __l; ++__f)
1600                 __tree_.__insert_multi(__e.__i_, *__f);
1601         }
1602
1603     _LIBCPP_INLINE_VISIBILITY
1604     void insert(initializer_list<value_type> __il)
1605         {insert(__il.begin(), __il.end());}
1606
1607     _LIBCPP_INLINE_VISIBILITY
1608     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1609     _LIBCPP_INLINE_VISIBILITY
1610     size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1611     _LIBCPP_INLINE_VISIBILITY
1612     iterator  erase(const_iterator __f, const_iterator __l)
1613         {return __tree_.erase(__f.__i_, __l.__i_);}
1614     _LIBCPP_INLINE_VISIBILITY
1615     void clear() {__tree_.clear();}
1616
1617     _LIBCPP_INLINE_VISIBILITY
1618     void swap(multimap& __m) {__tree_.swap(__m.__tree_);}
1619
1620     _LIBCPP_INLINE_VISIBILITY
1621     iterator find(const key_type& __k)             {return __tree_.find(__k);}
1622     _LIBCPP_INLINE_VISIBILITY
1623     const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1624     _LIBCPP_INLINE_VISIBILITY
1625     size_type      count(const key_type& __k) const
1626         {return __tree_.__count_multi(__k);}
1627     _LIBCPP_INLINE_VISIBILITY
1628     iterator lower_bound(const key_type& __k)
1629         {return __tree_.lower_bound(__k);}
1630     _LIBCPP_INLINE_VISIBILITY
1631     const_iterator lower_bound(const key_type& __k) const
1632             {return __tree_.lower_bound(__k);}
1633     _LIBCPP_INLINE_VISIBILITY
1634     iterator upper_bound(const key_type& __k)
1635             {return __tree_.upper_bound(__k);}
1636     _LIBCPP_INLINE_VISIBILITY
1637     const_iterator upper_bound(const key_type& __k) const
1638             {return __tree_.upper_bound(__k);}
1639     _LIBCPP_INLINE_VISIBILITY
1640     pair<iterator,iterator>             equal_range(const key_type& __k)
1641             {return __tree_.__equal_range_multi(__k);}
1642     _LIBCPP_INLINE_VISIBILITY
1643     pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1644             {return __tree_.__equal_range_multi(__k);}
1645
1646 private:
1647     typedef typename __base::__node                    __node;
1648     typedef typename __base::__node_allocator          __node_allocator;
1649     typedef typename __base::__node_pointer            __node_pointer;
1650     typedef typename __base::__node_const_pointer      __node_const_pointer;
1651     typedef __map_node_destructor<__node_allocator> _D;
1652     typedef unique_ptr<__node, _D> __node_holder;
1653
1654 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1655     __node_holder __construct_node();
1656     template <class _A0,
1657               class = typename enable_if<is_convertible<_A0, value_type>::value>::type>
1658         __node_holder __construct_node(_A0&& __a0);
1659 #ifndef _LIBCPP_HAS_NO_VARIADICS
1660     template <class _A0, class ..._Args,
1661               class = typename enable_if<is_convertible<_A0, key_type>::value>::type>
1662         __node_holder __construct_node(_A0&& __a0, _Args&& ...__args);
1663 #endif  // _LIBCPP_HAS_NO_VARIADICS
1664 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1665 };
1666
1667 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1668
1669 template <class _Key, class _Tp, class _Compare, class _Allocator>
1670 multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1671     : __tree_(_STD::move(__m.__tree_), __a)
1672 {
1673     if (__a != __m.get_allocator())
1674     {
1675         const_iterator __e = cend();
1676         while (!__m.empty())
1677             __tree_.__insert_multi(__e.__i_,
1678                     _STD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1679     }
1680 }
1681
1682 template <class _Key, class _Tp, class _Compare, class _Allocator>
1683 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1684 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1685 {
1686     __node_allocator& __na = __tree_.__node_alloc();
1687     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1688     __node_traits::construct(__na, _STD::addressof(__h->__value_.first));
1689     __h.get_deleter().__first_constructed = true;
1690     __node_traits::construct(__na, _STD::addressof(__h->__value_.second));
1691     __h.get_deleter().__second_constructed = true;
1692     return __h;
1693 }
1694
1695 template <class _Key, class _Tp, class _Compare, class _Allocator>
1696 template <class _A0,
1697           class // = typename enable_if<is_convertible<_A0, value_type>::value>::type
1698          >
1699 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1700 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1701 {
1702     __node_allocator& __na = __tree_.__node_alloc();
1703     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1704     __node_traits::construct(__na, _STD::addressof(__h->__value_), _STD::forward<_A0>(__a0));
1705     __h.get_deleter().__first_constructed = true;
1706     __h.get_deleter().__second_constructed = true;
1707     return __h;
1708 }
1709
1710 #ifndef _LIBCPP_HAS_NO_VARIADICS
1711
1712 template <class _Key, class _Tp, class _Compare, class _Allocator>
1713 template <class _A0, class ..._Args,
1714           class // = typename enable_if<is_convertible<_A0, key_type>::value>::type
1715          >
1716 typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1717 multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _Args&& ...__args)
1718 {
1719     __node_allocator& __na = __tree_.__node_alloc();
1720     __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
1721     __node_traits::construct(__na, _STD::addressof(__h->__value_.first), _STD::forward<_A0>(__a0));
1722     __h.get_deleter().__first_constructed = true;
1723     __node_traits::construct(__na, _STD::addressof(__h->__value_.second), _STD::forward<_Args>(__args)...);
1724     __h.get_deleter().__second_constructed = true;
1725     return __h;
1726 }
1727
1728 #endif  // _LIBCPP_HAS_NO_VARIADICS
1729 #endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1730
1731 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1732
1733 template <class _Key, class _Tp, class _Compare, class _Allocator>
1734 template <class _A0, class ..._Args,
1735           class //= typename enable_if<is_convertible<_A0, _Key>::value>::type
1736          >
1737 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1738 multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_A0&& __a0, _Args&& ...__args)
1739 {
1740     __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1741                                          _STD::forward<_Args>(__args)...);
1742     iterator __r = __tree_.__node_insert_multi(__h.get());
1743     __h.release();
1744     return __r;
1745 }
1746
1747 template <class _Key, class _Tp, class _Compare, class _Allocator>
1748 template <class _A0, class ..._Args,
1749           class //= typename enable_if<is_convertible<_A0, _Key>::value>::type
1750          >
1751 typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1752 multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1753                                                         _A0&& __a0,
1754                                                         _Args&& ...__args)
1755 {
1756     __node_holder __h = __construct_node(_STD::forward<_A0>(__a0),
1757                                          _STD::forward<_Args>(__args)...);
1758     iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1759     __h.release();
1760     return __r;
1761 }
1762
1763 #endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1764
1765 template <class _Key, class _Tp, class _Compare, class _Allocator>
1766 inline _LIBCPP_INLINE_VISIBILITY
1767 bool
1768 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1769            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1770 {
1771     return __x.size() == __y.size() && _STD::equal(__x.begin(), __x.end(), __y.begin());
1772 }
1773
1774 template <class _Key, class _Tp, class _Compare, class _Allocator>
1775 inline _LIBCPP_INLINE_VISIBILITY
1776 bool
1777 operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1778            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1779 {
1780     return _STD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1781 }
1782
1783 template <class _Key, class _Tp, class _Compare, class _Allocator>
1784 inline _LIBCPP_INLINE_VISIBILITY
1785 bool
1786 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1787            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1788 {
1789     return !(__x == __y);
1790 }
1791
1792 template <class _Key, class _Tp, class _Compare, class _Allocator>
1793 inline _LIBCPP_INLINE_VISIBILITY
1794 bool
1795 operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1796            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1797 {
1798     return __y < __x;
1799 }
1800
1801 template <class _Key, class _Tp, class _Compare, class _Allocator>
1802 inline _LIBCPP_INLINE_VISIBILITY
1803 bool
1804 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1805            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1806 {
1807     return !(__x < __y);
1808 }
1809
1810 template <class _Key, class _Tp, class _Compare, class _Allocator>
1811 inline _LIBCPP_INLINE_VISIBILITY
1812 bool
1813 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1814            const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1815 {
1816     return !(__y < __x);
1817 }
1818
1819 template <class _Key, class _Tp, class _Compare, class _Allocator>
1820 inline _LIBCPP_INLINE_VISIBILITY
1821 void
1822 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1823      multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1824 {
1825     __x.swap(__y);
1826 }
1827
1828 _LIBCPP_END_NAMESPACE_STD
1829
1830 #endif  // _LIBCPP_MAP