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