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