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