• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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;        // C++14
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;        // C++14
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 _Tp>
648struct __extract_key_value_types;
649
650template <class _Key, class _Tp>
651struct __extract_key_value_types<__value_type<_Key, _Tp> >
652{
653  typedef _Key const __key_type;
654  typedef _Tp        __mapped_type;
655};
656
657template <class _TreeIterator>
658class _LIBCPP_TYPE_VIS_ONLY __map_iterator
659{
660    _TreeIterator __i_;
661
662    typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
663    typedef typename _TreeIterator::value_type __value_type;
664    typedef typename __extract_key_value_types<__value_type>::__key_type    __key_type;
665    typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
666public:
667    typedef bidirectional_iterator_tag                           iterator_category;
668    typedef pair<__key_type, __mapped_type>                      value_type;
669    typedef typename _TreeIterator::difference_type              difference_type;
670    typedef value_type&                                          reference;
671    typedef typename __pointer_traits::template
672#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
673            rebind<value_type>
674#else
675            rebind<value_type>::other
676#endif
677                                                                 pointer;
678
679    _LIBCPP_INLINE_VISIBILITY
680    __map_iterator() _NOEXCEPT {}
681
682    _LIBCPP_INLINE_VISIBILITY
683    __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
684
685    _LIBCPP_INLINE_VISIBILITY
686    reference operator*() const {return __i_->__cc;}
687    _LIBCPP_INLINE_VISIBILITY
688    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
689
690    _LIBCPP_INLINE_VISIBILITY
691    __map_iterator& operator++() {++__i_; return *this;}
692    _LIBCPP_INLINE_VISIBILITY
693    __map_iterator operator++(int)
694    {
695        __map_iterator __t(*this);
696        ++(*this);
697        return __t;
698    }
699
700    _LIBCPP_INLINE_VISIBILITY
701    __map_iterator& operator--() {--__i_; return *this;}
702    _LIBCPP_INLINE_VISIBILITY
703    __map_iterator operator--(int)
704    {
705        __map_iterator __t(*this);
706        --(*this);
707        return __t;
708    }
709
710    friend _LIBCPP_INLINE_VISIBILITY
711    bool operator==(const __map_iterator& __x, const __map_iterator& __y)
712        {return __x.__i_ == __y.__i_;}
713    friend
714    _LIBCPP_INLINE_VISIBILITY
715    bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
716        {return __x.__i_ != __y.__i_;}
717
718    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
719    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
720    template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
721};
722
723template <class _TreeIterator>
724class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
725{
726    _TreeIterator __i_;
727
728    typedef typename _TreeIterator::__pointer_traits             __pointer_traits;
729    typedef typename _TreeIterator::value_type __value_type;
730    typedef typename __extract_key_value_types<__value_type>::__key_type    __key_type;
731    typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
732public:
733    typedef bidirectional_iterator_tag                           iterator_category;
734    typedef pair<__key_type, __mapped_type>                      value_type;
735    typedef typename _TreeIterator::difference_type              difference_type;
736    typedef const value_type&                                    reference;
737    typedef typename __pointer_traits::template
738#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
739            rebind<const value_type>
740#else
741            rebind<const value_type>::other
742#endif
743                                                                 pointer;
744
745    _LIBCPP_INLINE_VISIBILITY
746    __map_const_iterator() _NOEXCEPT {}
747
748    _LIBCPP_INLINE_VISIBILITY
749    __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
750    _LIBCPP_INLINE_VISIBILITY
751    __map_const_iterator(__map_iterator<
752        typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
753        : __i_(__i.__i_) {}
754
755    _LIBCPP_INLINE_VISIBILITY
756    reference operator*() const {return __i_->__cc;}
757    _LIBCPP_INLINE_VISIBILITY
758    pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
759
760    _LIBCPP_INLINE_VISIBILITY
761    __map_const_iterator& operator++() {++__i_; return *this;}
762    _LIBCPP_INLINE_VISIBILITY
763    __map_const_iterator operator++(int)
764    {
765        __map_const_iterator __t(*this);
766        ++(*this);
767        return __t;
768    }
769
770    _LIBCPP_INLINE_VISIBILITY
771    __map_const_iterator& operator--() {--__i_; return *this;}
772    _LIBCPP_INLINE_VISIBILITY
773    __map_const_iterator operator--(int)
774    {
775        __map_const_iterator __t(*this);
776        --(*this);
777        return __t;
778    }
779
780    friend _LIBCPP_INLINE_VISIBILITY
781    bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
782        {return __x.__i_ == __y.__i_;}
783    friend _LIBCPP_INLINE_VISIBILITY
784    bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
785        {return __x.__i_ != __y.__i_;}
786
787    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
788    template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
789    template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
790};
791
792template <class _Key, class _Tp, class _Compare = less<_Key>,
793          class _Allocator = allocator<pair<const _Key, _Tp> > >
794class _LIBCPP_TYPE_VIS_ONLY map
795{
796public:
797    // types:
798    typedef _Key                                     key_type;
799    typedef _Tp                                      mapped_type;
800    typedef pair<const key_type, mapped_type>        value_type;
801    typedef pair<key_type, mapped_type>              __nc_value_type;
802    typedef _Compare                                 key_compare;
803    typedef _Allocator                               allocator_type;
804    typedef value_type&                              reference;
805    typedef const value_type&                        const_reference;
806
807    class _LIBCPP_TYPE_VIS_ONLY value_compare
808        : public binary_function<value_type, value_type, bool>
809    {
810        friend class map;
811    protected:
812        key_compare comp;
813
814        _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
815    public:
816        _LIBCPP_INLINE_VISIBILITY
817        bool operator()(const value_type& __x, const value_type& __y) const
818            {return comp(__x.first, __y.first);}
819    };
820
821private:
822
823    typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
824    typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
825    typedef typename allocator_traits<allocator_type>::template
826#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
827            rebind_alloc<__value_type>
828#else
829            rebind_alloc<__value_type>::other
830#endif
831                                                           __allocator_type;
832    typedef __tree<__value_type, __vc, __allocator_type>   __base;
833    typedef typename __base::__node_traits                 __node_traits;
834    typedef allocator_traits<allocator_type>               __alloc_traits;
835
836    __base __tree_;
837
838public:
839    typedef typename __alloc_traits::pointer               pointer;
840    typedef typename __alloc_traits::const_pointer         const_pointer;
841    typedef typename __alloc_traits::size_type             size_type;
842    typedef typename __alloc_traits::difference_type       difference_type;
843    typedef __map_iterator<typename __base::iterator>             iterator;
844    typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
845    typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
846    typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
847
848    _LIBCPP_INLINE_VISIBILITY
849    map()
850        _NOEXCEPT_(
851            is_nothrow_default_constructible<allocator_type>::value &&
852            is_nothrow_default_constructible<key_compare>::value &&
853            is_nothrow_copy_constructible<key_compare>::value)
854        : __tree_(__vc(key_compare())) {}
855
856    _LIBCPP_INLINE_VISIBILITY
857    explicit map(const key_compare& __comp)
858        _NOEXCEPT_(
859            is_nothrow_default_constructible<allocator_type>::value &&
860            is_nothrow_copy_constructible<key_compare>::value)
861        : __tree_(__vc(__comp)) {}
862
863    _LIBCPP_INLINE_VISIBILITY
864    explicit map(const key_compare& __comp, const allocator_type& __a)
865        : __tree_(__vc(__comp), __a) {}
866
867    template <class _InputIterator>
868    _LIBCPP_INLINE_VISIBILITY
869        map(_InputIterator __f, _InputIterator __l,
870            const key_compare& __comp = key_compare())
871        : __tree_(__vc(__comp))
872        {
873            insert(__f, __l);
874        }
875
876    template <class _InputIterator>
877    _LIBCPP_INLINE_VISIBILITY
878        map(_InputIterator __f, _InputIterator __l,
879            const key_compare& __comp, const allocator_type& __a)
880        : __tree_(__vc(__comp), __a)
881        {
882            insert(__f, __l);
883        }
884
885#if _LIBCPP_STD_VER > 11
886    template <class _InputIterator>
887    _LIBCPP_INLINE_VISIBILITY
888    map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
889        : map(__f, __l, key_compare(), __a) {}
890#endif
891
892    _LIBCPP_INLINE_VISIBILITY
893    map(const map& __m)
894        : __tree_(__m.__tree_)
895        {
896            insert(__m.begin(), __m.end());
897        }
898
899    _LIBCPP_INLINE_VISIBILITY
900    map& operator=(const map& __m)
901        {
902#if __cplusplus >= 201103L
903            __tree_ = __m.__tree_;
904#else
905            if (this != &__m) {
906                __tree_.clear();
907                __tree_.value_comp() = __m.__tree_.value_comp();
908                __tree_.__copy_assign_alloc(__m.__tree_);
909                insert(__m.begin(), __m.end());
910            }
911#endif
912            return *this;
913        }
914
915#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
916
917    _LIBCPP_INLINE_VISIBILITY
918    map(map&& __m)
919        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
920        : __tree_(_VSTD::move(__m.__tree_))
921        {
922        }
923
924    map(map&& __m, const allocator_type& __a);
925
926    _LIBCPP_INLINE_VISIBILITY
927    map& operator=(map&& __m)
928        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
929        {
930            __tree_ = _VSTD::move(__m.__tree_);
931            return *this;
932        }
933
934#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
935
936#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
937
938    _LIBCPP_INLINE_VISIBILITY
939    map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
940        : __tree_(__vc(__comp))
941        {
942            insert(__il.begin(), __il.end());
943        }
944
945    _LIBCPP_INLINE_VISIBILITY
946    map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
947        : __tree_(__vc(__comp), __a)
948        {
949            insert(__il.begin(), __il.end());
950        }
951
952#if _LIBCPP_STD_VER > 11
953    _LIBCPP_INLINE_VISIBILITY
954    map(initializer_list<value_type> __il, const allocator_type& __a)
955        : map(__il, key_compare(), __a) {}
956#endif
957
958    _LIBCPP_INLINE_VISIBILITY
959    map& operator=(initializer_list<value_type> __il)
960        {
961            __tree_.__assign_unique(__il.begin(), __il.end());
962            return *this;
963        }
964
965#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
966
967    _LIBCPP_INLINE_VISIBILITY
968    explicit map(const allocator_type& __a)
969        : __tree_(__a)
970        {
971        }
972
973    _LIBCPP_INLINE_VISIBILITY
974    map(const map& __m, const allocator_type& __a)
975        : __tree_(__m.__tree_.value_comp(), __a)
976        {
977            insert(__m.begin(), __m.end());
978        }
979
980    _LIBCPP_INLINE_VISIBILITY
981          iterator begin() _NOEXCEPT {return __tree_.begin();}
982    _LIBCPP_INLINE_VISIBILITY
983    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
984    _LIBCPP_INLINE_VISIBILITY
985          iterator end() _NOEXCEPT {return __tree_.end();}
986    _LIBCPP_INLINE_VISIBILITY
987    const_iterator end() const _NOEXCEPT {return __tree_.end();}
988
989    _LIBCPP_INLINE_VISIBILITY
990          reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
991    _LIBCPP_INLINE_VISIBILITY
992    const_reverse_iterator rbegin() const _NOEXCEPT
993        {return const_reverse_iterator(end());}
994    _LIBCPP_INLINE_VISIBILITY
995          reverse_iterator rend() _NOEXCEPT
996            {return       reverse_iterator(begin());}
997    _LIBCPP_INLINE_VISIBILITY
998    const_reverse_iterator rend() const _NOEXCEPT
999        {return const_reverse_iterator(begin());}
1000
1001    _LIBCPP_INLINE_VISIBILITY
1002    const_iterator cbegin() const _NOEXCEPT {return begin();}
1003    _LIBCPP_INLINE_VISIBILITY
1004    const_iterator cend() const _NOEXCEPT {return end();}
1005    _LIBCPP_INLINE_VISIBILITY
1006    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1007    _LIBCPP_INLINE_VISIBILITY
1008    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1009
1010    _LIBCPP_INLINE_VISIBILITY
1011    bool      empty() const _NOEXCEPT {return __tree_.size() == 0;}
1012    _LIBCPP_INLINE_VISIBILITY
1013    size_type size() const _NOEXCEPT {return __tree_.size();}
1014    _LIBCPP_INLINE_VISIBILITY
1015    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1016
1017    mapped_type& operator[](const key_type& __k);
1018#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1019    mapped_type& operator[](key_type&& __k);
1020#endif
1021
1022          mapped_type& at(const key_type& __k);
1023    const mapped_type& at(const key_type& __k) const;
1024
1025    _LIBCPP_INLINE_VISIBILITY
1026    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1027    _LIBCPP_INLINE_VISIBILITY
1028    key_compare    key_comp()      const {return __tree_.value_comp().key_comp();}
1029    _LIBCPP_INLINE_VISIBILITY
1030    value_compare  value_comp()    const {return value_compare(__tree_.value_comp().key_comp());}
1031
1032#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1033#ifndef _LIBCPP_HAS_NO_VARIADICS
1034
1035    template <class ..._Args>
1036        pair<iterator, bool>
1037        emplace(_Args&& ...__args);
1038
1039    template <class ..._Args>
1040        iterator
1041        emplace_hint(const_iterator __p, _Args&& ...__args);
1042
1043#endif  // _LIBCPP_HAS_NO_VARIADICS
1044
1045    template <class _Pp,
1046              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1047        _LIBCPP_INLINE_VISIBILITY
1048        pair<iterator, bool> insert(_Pp&& __p)
1049            {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
1050
1051    template <class _Pp,
1052              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1053        _LIBCPP_INLINE_VISIBILITY
1054        iterator insert(const_iterator __pos, _Pp&& __p)
1055            {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1056
1057#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1058
1059    _LIBCPP_INLINE_VISIBILITY
1060    pair<iterator, bool>
1061        insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1062
1063    _LIBCPP_INLINE_VISIBILITY
1064    iterator
1065        insert(const_iterator __p, const value_type& __v)
1066            {return __tree_.__insert_unique(__p.__i_, __v);}
1067
1068    template <class _InputIterator>
1069        _LIBCPP_INLINE_VISIBILITY
1070        void insert(_InputIterator __f, _InputIterator __l)
1071        {
1072            for (const_iterator __e = cend(); __f != __l; ++__f)
1073                insert(__e.__i_, *__f);
1074        }
1075
1076#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1077
1078    _LIBCPP_INLINE_VISIBILITY
1079    void insert(initializer_list<value_type> __il)
1080        {insert(__il.begin(), __il.end());}
1081
1082#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1083
1084    _LIBCPP_INLINE_VISIBILITY
1085    iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1086    _LIBCPP_INLINE_VISIBILITY
1087    size_type erase(const key_type& __k)
1088        {return __tree_.__erase_unique(__k);}
1089    _LIBCPP_INLINE_VISIBILITY
1090    iterator  erase(const_iterator __f, const_iterator __l)
1091        {return __tree_.erase(__f.__i_, __l.__i_);}
1092    _LIBCPP_INLINE_VISIBILITY
1093    void clear() _NOEXCEPT {__tree_.clear();}
1094
1095    _LIBCPP_INLINE_VISIBILITY
1096    void swap(map& __m)
1097        _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1098        {__tree_.swap(__m.__tree_);}
1099
1100    _LIBCPP_INLINE_VISIBILITY
1101    iterator find(const key_type& __k)             {return __tree_.find(__k);}
1102    _LIBCPP_INLINE_VISIBILITY
1103    const_iterator find(const key_type& __k) const {return __tree_.find(__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    find(const _K2& __k)                           {return __tree_.find(__k);}
1109    template <typename _K2>
1110    _LIBCPP_INLINE_VISIBILITY
1111    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1112    find(const _K2& __k) const                     {return __tree_.find(__k);}
1113#endif
1114
1115    _LIBCPP_INLINE_VISIBILITY
1116    size_type      count(const key_type& __k) const
1117        {return __tree_.__count_unique(__k);}
1118#if _LIBCPP_STD_VER > 11
1119    template <typename _K2>
1120    _LIBCPP_INLINE_VISIBILITY
1121    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1122    count(const _K2& __k)                  {return __tree_.__count_unique(__k);}
1123#endif
1124    _LIBCPP_INLINE_VISIBILITY
1125    iterator lower_bound(const key_type& __k)
1126        {return __tree_.lower_bound(__k);}
1127    _LIBCPP_INLINE_VISIBILITY
1128    const_iterator lower_bound(const key_type& __k) const
1129        {return __tree_.lower_bound(__k);}
1130#if _LIBCPP_STD_VER > 11
1131    template <typename _K2>
1132    _LIBCPP_INLINE_VISIBILITY
1133    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1134    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1135
1136    template <typename _K2>
1137    _LIBCPP_INLINE_VISIBILITY
1138    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1139    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1140#endif
1141
1142    _LIBCPP_INLINE_VISIBILITY
1143    iterator upper_bound(const key_type& __k)
1144        {return __tree_.upper_bound(__k);}
1145    _LIBCPP_INLINE_VISIBILITY
1146    const_iterator upper_bound(const key_type& __k) const
1147        {return __tree_.upper_bound(__k);}
1148#if _LIBCPP_STD_VER > 11
1149    template <typename _K2>
1150    _LIBCPP_INLINE_VISIBILITY
1151    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1152    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1153    template <typename _K2>
1154    _LIBCPP_INLINE_VISIBILITY
1155    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1156    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1157#endif
1158
1159    _LIBCPP_INLINE_VISIBILITY
1160    pair<iterator,iterator> equal_range(const key_type& __k)
1161        {return __tree_.__equal_range_unique(__k);}
1162    _LIBCPP_INLINE_VISIBILITY
1163    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1164        {return __tree_.__equal_range_unique(__k);}
1165#if _LIBCPP_STD_VER > 11
1166    template <typename _K2>
1167    _LIBCPP_INLINE_VISIBILITY
1168    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1169    equal_range(const _K2& __k)       {return __tree_.__equal_range_unique(__k);}
1170    template <typename _K2>
1171    _LIBCPP_INLINE_VISIBILITY
1172    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1173    equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1174#endif
1175
1176private:
1177    typedef typename __base::__node                    __node;
1178    typedef typename __base::__node_allocator          __node_allocator;
1179    typedef typename __base::__node_pointer            __node_pointer;
1180    typedef typename __base::__node_const_pointer      __node_const_pointer;
1181    typedef typename __base::__node_base_pointer       __node_base_pointer;
1182    typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1183    typedef __map_node_destructor<__node_allocator> _Dp;
1184    typedef unique_ptr<__node, _Dp> __node_holder;
1185
1186#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1187    __node_holder __construct_node();
1188    template <class _A0>
1189        __node_holder __construct_node(_A0&& __a0);
1190    __node_holder __construct_node_with_key(key_type&& __k);
1191#ifndef _LIBCPP_HAS_NO_VARIADICS
1192    template <class _A0, class _A1, class ..._Args>
1193        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1194#endif  // _LIBCPP_HAS_NO_VARIADICS
1195#endif
1196    __node_holder __construct_node_with_key(const key_type& __k);
1197
1198    __node_base_pointer&
1199        __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1200    __node_base_const_pointer
1201        __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1202};
1203
1204// Find place to insert if __k doesn't exist
1205// Set __parent to parent of null leaf
1206// Return reference to null leaf
1207// If __k exists, set parent to node of __k and return reference to node of __k
1208template <class _Key, class _Tp, class _Compare, class _Allocator>
1209typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1210map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1211                                                       const key_type& __k)
1212{
1213    __node_pointer __nd = __tree_.__root();
1214    if (__nd != nullptr)
1215    {
1216        while (true)
1217        {
1218            if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1219            {
1220                if (__nd->__left_ != nullptr)
1221                    __nd = static_cast<__node_pointer>(__nd->__left_);
1222                else
1223                {
1224                    __parent = static_cast<__node_base_pointer>(__nd);
1225                    return __parent->__left_;
1226                }
1227            }
1228            else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1229            {
1230                if (__nd->__right_ != nullptr)
1231                    __nd = static_cast<__node_pointer>(__nd->__right_);
1232                else
1233                {
1234                    __parent = static_cast<__node_base_pointer>(__nd);
1235                    return __parent->__right_;
1236                }
1237            }
1238            else
1239            {
1240                __parent = static_cast<__node_base_pointer>(__nd);
1241                return __parent;
1242            }
1243        }
1244    }
1245    __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1246    return __parent->__left_;
1247}
1248
1249// Find __k
1250// Set __parent to parent of null leaf and
1251//    return reference to null leaf iv __k does not exist.
1252// If __k exists, set parent to node of __k and return reference to node of __k
1253template <class _Key, class _Tp, class _Compare, class _Allocator>
1254typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1255map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1256                                                       const key_type& __k) const
1257{
1258    __node_const_pointer __nd = __tree_.__root();
1259    if (__nd != nullptr)
1260    {
1261        while (true)
1262        {
1263            if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
1264            {
1265                if (__nd->__left_ != nullptr)
1266                    __nd = static_cast<__node_pointer>(__nd->__left_);
1267                else
1268                {
1269                    __parent = static_cast<__node_base_pointer>(__nd);
1270                    return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1271                }
1272            }
1273            else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
1274            {
1275                if (__nd->__right_ != nullptr)
1276                    __nd = static_cast<__node_pointer>(__nd->__right_);
1277                else
1278                {
1279                    __parent = static_cast<__node_base_pointer>(__nd);
1280                    return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1281                }
1282            }
1283            else
1284            {
1285                __parent = static_cast<__node_base_pointer>(__nd);
1286                return __parent;
1287            }
1288        }
1289    }
1290    __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
1291    return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1292}
1293
1294#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1295
1296template <class _Key, class _Tp, class _Compare, class _Allocator>
1297map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
1298    : __tree_(_VSTD::move(__m.__tree_), __a)
1299{
1300    if (__a != __m.get_allocator())
1301    {
1302        const_iterator __e = cend();
1303        while (!__m.empty())
1304            __tree_.__insert_unique(__e.__i_,
1305                    _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1306    }
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()
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));
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
1322template <class _Key, class _Tp, class _Compare, class _Allocator>
1323template <class _A0>
1324typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1325map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1326{
1327    __node_allocator& __na = __tree_.__node_alloc();
1328    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1329    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1330    __h.get_deleter().__first_constructed = true;
1331    __h.get_deleter().__second_constructed = true;
1332    return __h;
1333}
1334
1335template <class _Key, class _Tp, class _Compare, class _Allocator>
1336typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1337map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
1338{
1339    __node_allocator& __na = __tree_.__node_alloc();
1340    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1341    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
1342    __h.get_deleter().__first_constructed = true;
1343    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1344    __h.get_deleter().__second_constructed = true;
1345    return __h;
1346}
1347
1348#ifndef _LIBCPP_HAS_NO_VARIADICS
1349
1350template <class _Key, class _Tp, class _Compare, class _Allocator>
1351template <class _A0, class _A1, class ..._Args>
1352typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1353map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1354{
1355    __node_allocator& __na = __tree_.__node_alloc();
1356    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1357    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1358                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1359                             _VSTD::forward<_Args>(__args)...);
1360    __h.get_deleter().__first_constructed = true;
1361    __h.get_deleter().__second_constructed = true;
1362    return __h;
1363}
1364
1365#endif  // _LIBCPP_HAS_NO_VARIADICS
1366
1367#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1368
1369template <class _Key, class _Tp, class _Compare, class _Allocator>
1370typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1371map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
1372{
1373    __node_allocator& __na = __tree_.__node_alloc();
1374    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1375    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
1376    __h.get_deleter().__first_constructed = true;
1377    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1378    __h.get_deleter().__second_constructed = true;
1379    return _VSTD::move(__h);  // explicitly moved for C++03
1380}
1381
1382template <class _Key, class _Tp, class _Compare, class _Allocator>
1383_Tp&
1384map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1385{
1386    __node_base_pointer __parent;
1387    __node_base_pointer& __child = __find_equal_key(__parent, __k);
1388    __node_pointer __r = static_cast<__node_pointer>(__child);
1389    if (__child == nullptr)
1390    {
1391        __node_holder __h = __construct_node_with_key(__k);
1392        __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1393        __r = __h.release();
1394    }
1395    return __r->__value_.__cc.second;
1396}
1397
1398#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1399
1400template <class _Key, class _Tp, class _Compare, class _Allocator>
1401_Tp&
1402map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1403{
1404    __node_base_pointer __parent;
1405    __node_base_pointer& __child = __find_equal_key(__parent, __k);
1406    __node_pointer __r = static_cast<__node_pointer>(__child);
1407    if (__child == nullptr)
1408    {
1409        __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
1410        __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1411        __r = __h.release();
1412    }
1413    return __r->__value_.__cc.second;
1414}
1415
1416#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1417
1418template <class _Key, class _Tp, class _Compare, class _Allocator>
1419_Tp&
1420map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1421{
1422    __node_base_pointer __parent;
1423    __node_base_pointer& __child = __find_equal_key(__parent, __k);
1424#ifndef _LIBCPP_NO_EXCEPTIONS
1425    if (__child == nullptr)
1426        throw out_of_range("map::at:  key not found");
1427#endif  // _LIBCPP_NO_EXCEPTIONS
1428    return static_cast<__node_pointer>(__child)->__value_.__cc.second;
1429}
1430
1431template <class _Key, class _Tp, class _Compare, class _Allocator>
1432const _Tp&
1433map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1434{
1435    __node_base_const_pointer __parent;
1436    __node_base_const_pointer __child = __find_equal_key(__parent, __k);
1437#ifndef _LIBCPP_NO_EXCEPTIONS
1438    if (__child == nullptr)
1439        throw out_of_range("map::at:  key not found");
1440#endif  // _LIBCPP_NO_EXCEPTIONS
1441    return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
1442}
1443
1444#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1445
1446template <class _Key, class _Tp, class _Compare, class _Allocator>
1447template <class ..._Args>
1448pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1449map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1450{
1451    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1452    pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1453    if (__r.second)
1454        __h.release();
1455    return __r;
1456}
1457
1458template <class _Key, class _Tp, class _Compare, class _Allocator>
1459template <class ..._Args>
1460typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1461map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1462                                                   _Args&& ...__args)
1463{
1464    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
1465    iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1466    if (__r.__i_.__ptr_ == __h.get())
1467        __h.release();
1468    return __r;
1469}
1470
1471#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1472
1473template <class _Key, class _Tp, class _Compare, class _Allocator>
1474inline _LIBCPP_INLINE_VISIBILITY
1475bool
1476operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1477           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1478{
1479    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
1480}
1481
1482template <class _Key, class _Tp, class _Compare, class _Allocator>
1483inline _LIBCPP_INLINE_VISIBILITY
1484bool
1485operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1486           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1487{
1488    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1489}
1490
1491template <class _Key, class _Tp, class _Compare, class _Allocator>
1492inline _LIBCPP_INLINE_VISIBILITY
1493bool
1494operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1495           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1496{
1497    return !(__x == __y);
1498}
1499
1500template <class _Key, class _Tp, class _Compare, class _Allocator>
1501inline _LIBCPP_INLINE_VISIBILITY
1502bool
1503operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1504           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1505{
1506    return __y < __x;
1507}
1508
1509template <class _Key, class _Tp, class _Compare, class _Allocator>
1510inline _LIBCPP_INLINE_VISIBILITY
1511bool
1512operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1513           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1514{
1515    return !(__x < __y);
1516}
1517
1518template <class _Key, class _Tp, class _Compare, class _Allocator>
1519inline _LIBCPP_INLINE_VISIBILITY
1520bool
1521operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1522           const map<_Key, _Tp, _Compare, _Allocator>& __y)
1523{
1524    return !(__y < __x);
1525}
1526
1527template <class _Key, class _Tp, class _Compare, class _Allocator>
1528inline _LIBCPP_INLINE_VISIBILITY
1529void
1530swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1531     map<_Key, _Tp, _Compare, _Allocator>& __y)
1532    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
1533{
1534    __x.swap(__y);
1535}
1536
1537template <class _Key, class _Tp, class _Compare = less<_Key>,
1538          class _Allocator = allocator<pair<const _Key, _Tp> > >
1539class _LIBCPP_TYPE_VIS_ONLY multimap
1540{
1541public:
1542    // types:
1543    typedef _Key                                     key_type;
1544    typedef _Tp                                      mapped_type;
1545    typedef pair<const key_type, mapped_type>        value_type;
1546    typedef pair<key_type, mapped_type>              __nc_value_type;
1547    typedef _Compare                                 key_compare;
1548    typedef _Allocator                               allocator_type;
1549    typedef value_type&                              reference;
1550    typedef const value_type&                        const_reference;
1551
1552    class _LIBCPP_TYPE_VIS_ONLY value_compare
1553        : public binary_function<value_type, value_type, bool>
1554    {
1555        friend class multimap;
1556    protected:
1557        key_compare comp;
1558
1559        _LIBCPP_INLINE_VISIBILITY
1560        value_compare(key_compare c) : comp(c) {}
1561    public:
1562        _LIBCPP_INLINE_VISIBILITY
1563        bool operator()(const value_type& __x, const value_type& __y) const
1564            {return comp(__x.first, __y.first);}
1565    };
1566
1567private:
1568
1569    typedef _VSTD::__value_type<key_type, mapped_type>             __value_type;
1570    typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1571    typedef typename allocator_traits<allocator_type>::template
1572#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1573            rebind_alloc<__value_type>
1574#else
1575            rebind_alloc<__value_type>::other
1576#endif
1577                                                                    __allocator_type;
1578    typedef __tree<__value_type, __vc, __allocator_type>            __base;
1579    typedef typename __base::__node_traits                          __node_traits;
1580    typedef allocator_traits<allocator_type>                        __alloc_traits;
1581
1582    __base __tree_;
1583
1584public:
1585    typedef typename __alloc_traits::pointer               pointer;
1586    typedef typename __alloc_traits::const_pointer         const_pointer;
1587    typedef typename __alloc_traits::size_type             size_type;
1588    typedef typename __alloc_traits::difference_type       difference_type;
1589    typedef __map_iterator<typename __base::iterator>      iterator;
1590    typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1591    typedef _VSTD::reverse_iterator<iterator>               reverse_iterator;
1592    typedef _VSTD::reverse_iterator<const_iterator>         const_reverse_iterator;
1593
1594    _LIBCPP_INLINE_VISIBILITY
1595    multimap()
1596        _NOEXCEPT_(
1597            is_nothrow_default_constructible<allocator_type>::value &&
1598            is_nothrow_default_constructible<key_compare>::value &&
1599            is_nothrow_copy_constructible<key_compare>::value)
1600        : __tree_(__vc(key_compare())) {}
1601
1602    _LIBCPP_INLINE_VISIBILITY
1603    explicit multimap(const key_compare& __comp)
1604        _NOEXCEPT_(
1605            is_nothrow_default_constructible<allocator_type>::value &&
1606            is_nothrow_copy_constructible<key_compare>::value)
1607        : __tree_(__vc(__comp)) {}
1608
1609    _LIBCPP_INLINE_VISIBILITY
1610    explicit multimap(const key_compare& __comp, const allocator_type& __a)
1611        : __tree_(__vc(__comp), __a) {}
1612
1613    template <class _InputIterator>
1614        _LIBCPP_INLINE_VISIBILITY
1615        multimap(_InputIterator __f, _InputIterator __l,
1616            const key_compare& __comp = key_compare())
1617        : __tree_(__vc(__comp))
1618        {
1619            insert(__f, __l);
1620        }
1621
1622    template <class _InputIterator>
1623        _LIBCPP_INLINE_VISIBILITY
1624        multimap(_InputIterator __f, _InputIterator __l,
1625            const key_compare& __comp, const allocator_type& __a)
1626        : __tree_(__vc(__comp), __a)
1627        {
1628            insert(__f, __l);
1629        }
1630
1631#if _LIBCPP_STD_VER > 11
1632    template <class _InputIterator>
1633    _LIBCPP_INLINE_VISIBILITY
1634    multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1635        : multimap(__f, __l, key_compare(), __a) {}
1636#endif
1637
1638    _LIBCPP_INLINE_VISIBILITY
1639    multimap(const multimap& __m)
1640        : __tree_(__m.__tree_.value_comp(),
1641          __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1642        {
1643            insert(__m.begin(), __m.end());
1644        }
1645
1646    _LIBCPP_INLINE_VISIBILITY
1647    multimap& operator=(const multimap& __m)
1648        {
1649#if __cplusplus >= 201103L
1650            __tree_ = __m.__tree_;
1651#else
1652            if (this != &__m) {
1653                __tree_.clear();
1654                __tree_.value_comp() = __m.__tree_.value_comp();
1655                __tree_.__copy_assign_alloc(__m.__tree_);
1656                insert(__m.begin(), __m.end());
1657            }
1658#endif
1659            return *this;
1660        }
1661
1662#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1663
1664    _LIBCPP_INLINE_VISIBILITY
1665    multimap(multimap&& __m)
1666        _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
1667        : __tree_(_VSTD::move(__m.__tree_))
1668        {
1669        }
1670
1671    multimap(multimap&& __m, const allocator_type& __a);
1672
1673    _LIBCPP_INLINE_VISIBILITY
1674    multimap& operator=(multimap&& __m)
1675        _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1676        {
1677            __tree_ = _VSTD::move(__m.__tree_);
1678            return *this;
1679        }
1680
1681#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1682
1683#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1684
1685    _LIBCPP_INLINE_VISIBILITY
1686    multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1687        : __tree_(__vc(__comp))
1688        {
1689            insert(__il.begin(), __il.end());
1690        }
1691
1692    _LIBCPP_INLINE_VISIBILITY
1693    multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1694        : __tree_(__vc(__comp), __a)
1695        {
1696            insert(__il.begin(), __il.end());
1697        }
1698
1699#if _LIBCPP_STD_VER > 11
1700    _LIBCPP_INLINE_VISIBILITY
1701    multimap(initializer_list<value_type> __il, const allocator_type& __a)
1702        : multimap(__il, key_compare(), __a) {}
1703#endif
1704
1705    _LIBCPP_INLINE_VISIBILITY
1706    multimap& operator=(initializer_list<value_type> __il)
1707        {
1708            __tree_.__assign_multi(__il.begin(), __il.end());
1709            return *this;
1710        }
1711
1712#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1713
1714    _LIBCPP_INLINE_VISIBILITY
1715    explicit multimap(const allocator_type& __a)
1716        : __tree_(__a)
1717        {
1718        }
1719
1720    _LIBCPP_INLINE_VISIBILITY
1721    multimap(const multimap& __m, const allocator_type& __a)
1722        : __tree_(__m.__tree_.value_comp(), __a)
1723        {
1724            insert(__m.begin(), __m.end());
1725        }
1726
1727    _LIBCPP_INLINE_VISIBILITY
1728          iterator begin() _NOEXCEPT {return __tree_.begin();}
1729    _LIBCPP_INLINE_VISIBILITY
1730    const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
1731    _LIBCPP_INLINE_VISIBILITY
1732          iterator end() _NOEXCEPT {return __tree_.end();}
1733    _LIBCPP_INLINE_VISIBILITY
1734    const_iterator end() const _NOEXCEPT {return __tree_.end();}
1735
1736    _LIBCPP_INLINE_VISIBILITY
1737          reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
1738    _LIBCPP_INLINE_VISIBILITY
1739    const_reverse_iterator rbegin() const _NOEXCEPT
1740        {return const_reverse_iterator(end());}
1741    _LIBCPP_INLINE_VISIBILITY
1742          reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
1743    _LIBCPP_INLINE_VISIBILITY
1744    const_reverse_iterator rend() const _NOEXCEPT
1745        {return const_reverse_iterator(begin());}
1746
1747    _LIBCPP_INLINE_VISIBILITY
1748    const_iterator cbegin()  const _NOEXCEPT {return begin();}
1749    _LIBCPP_INLINE_VISIBILITY
1750    const_iterator cend() const _NOEXCEPT {return end();}
1751    _LIBCPP_INLINE_VISIBILITY
1752    const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
1753    _LIBCPP_INLINE_VISIBILITY
1754    const_reverse_iterator crend() const _NOEXCEPT {return rend();}
1755
1756    _LIBCPP_INLINE_VISIBILITY
1757    bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
1758    _LIBCPP_INLINE_VISIBILITY
1759    size_type size() const _NOEXCEPT {return __tree_.size();}
1760    _LIBCPP_INLINE_VISIBILITY
1761    size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
1762
1763    _LIBCPP_INLINE_VISIBILITY
1764    allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
1765    _LIBCPP_INLINE_VISIBILITY
1766    key_compare    key_comp() const {return __tree_.value_comp().key_comp();}
1767    _LIBCPP_INLINE_VISIBILITY
1768    value_compare  value_comp() const
1769        {return value_compare(__tree_.value_comp().key_comp());}
1770
1771#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1772#ifndef _LIBCPP_HAS_NO_VARIADICS
1773
1774    template <class ..._Args>
1775        iterator
1776        emplace(_Args&& ...__args);
1777
1778    template <class ..._Args>
1779        iterator
1780        emplace_hint(const_iterator __p, _Args&& ...__args);
1781
1782#endif  // _LIBCPP_HAS_NO_VARIADICS
1783
1784    template <class _Pp,
1785              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1786        _LIBCPP_INLINE_VISIBILITY
1787        iterator insert(_Pp&& __p)
1788            {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
1789
1790    template <class _Pp,
1791              class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
1792        _LIBCPP_INLINE_VISIBILITY
1793        iterator insert(const_iterator __pos, _Pp&& __p)
1794            {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
1795
1796#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1797
1798    _LIBCPP_INLINE_VISIBILITY
1799    iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1800
1801    _LIBCPP_INLINE_VISIBILITY
1802    iterator insert(const_iterator __p, const value_type& __v)
1803            {return __tree_.__insert_multi(__p.__i_, __v);}
1804
1805    template <class _InputIterator>
1806        _LIBCPP_INLINE_VISIBILITY
1807        void insert(_InputIterator __f, _InputIterator __l)
1808        {
1809            for (const_iterator __e = cend(); __f != __l; ++__f)
1810                __tree_.__insert_multi(__e.__i_, *__f);
1811        }
1812
1813#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1814
1815    _LIBCPP_INLINE_VISIBILITY
1816    void insert(initializer_list<value_type> __il)
1817        {insert(__il.begin(), __il.end());}
1818
1819#endif  // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1820
1821    _LIBCPP_INLINE_VISIBILITY
1822    iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
1823    _LIBCPP_INLINE_VISIBILITY
1824    size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
1825    _LIBCPP_INLINE_VISIBILITY
1826    iterator  erase(const_iterator __f, const_iterator __l)
1827        {return __tree_.erase(__f.__i_, __l.__i_);}
1828    _LIBCPP_INLINE_VISIBILITY
1829    void clear() {__tree_.clear();}
1830
1831    _LIBCPP_INLINE_VISIBILITY
1832    void swap(multimap& __m)
1833        _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1834        {__tree_.swap(__m.__tree_);}
1835
1836    _LIBCPP_INLINE_VISIBILITY
1837    iterator find(const key_type& __k)             {return __tree_.find(__k);}
1838    _LIBCPP_INLINE_VISIBILITY
1839    const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
1840#if _LIBCPP_STD_VER > 11
1841    template <typename _K2>
1842    _LIBCPP_INLINE_VISIBILITY
1843    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1844    find(const _K2& __k)                           {return __tree_.find(__k);}
1845    template <typename _K2>
1846    _LIBCPP_INLINE_VISIBILITY
1847    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1848    find(const _K2& __k) const                     {return __tree_.find(__k);}
1849#endif
1850
1851    _LIBCPP_INLINE_VISIBILITY
1852    size_type      count(const key_type& __k) const
1853        {return __tree_.__count_multi(__k);}
1854#if _LIBCPP_STD_VER > 11
1855    template <typename _K2>
1856    _LIBCPP_INLINE_VISIBILITY
1857    typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1858    count(const _K2& __k)                   {return __tree_.__count_multi(__k);}
1859#endif
1860    _LIBCPP_INLINE_VISIBILITY
1861    iterator lower_bound(const key_type& __k)
1862        {return __tree_.lower_bound(__k);}
1863    _LIBCPP_INLINE_VISIBILITY
1864    const_iterator lower_bound(const key_type& __k) const
1865            {return __tree_.lower_bound(__k);}
1866#if _LIBCPP_STD_VER > 11
1867    template <typename _K2>
1868    _LIBCPP_INLINE_VISIBILITY
1869    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1870    lower_bound(const _K2& __k)       {return __tree_.lower_bound(__k);}
1871
1872    template <typename _K2>
1873    _LIBCPP_INLINE_VISIBILITY
1874    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1875    lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1876#endif
1877
1878    _LIBCPP_INLINE_VISIBILITY
1879    iterator upper_bound(const key_type& __k)
1880            {return __tree_.upper_bound(__k);}
1881    _LIBCPP_INLINE_VISIBILITY
1882    const_iterator upper_bound(const key_type& __k) const
1883            {return __tree_.upper_bound(__k);}
1884#if _LIBCPP_STD_VER > 11
1885    template <typename _K2>
1886    _LIBCPP_INLINE_VISIBILITY
1887    typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1888    upper_bound(const _K2& __k)       {return __tree_.upper_bound(__k);}
1889    template <typename _K2>
1890    _LIBCPP_INLINE_VISIBILITY
1891    typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1892    upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1893#endif
1894
1895    _LIBCPP_INLINE_VISIBILITY
1896    pair<iterator,iterator>             equal_range(const key_type& __k)
1897            {return __tree_.__equal_range_multi(__k);}
1898    _LIBCPP_INLINE_VISIBILITY
1899    pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1900            {return __tree_.__equal_range_multi(__k);}
1901#if _LIBCPP_STD_VER > 11
1902    template <typename _K2>
1903    _LIBCPP_INLINE_VISIBILITY
1904    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1905    equal_range(const _K2& __k)       {return __tree_.__equal_range_multi(__k);}
1906    template <typename _K2>
1907    _LIBCPP_INLINE_VISIBILITY
1908    typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1909    equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1910#endif
1911
1912private:
1913    typedef typename __base::__node                    __node;
1914    typedef typename __base::__node_allocator          __node_allocator;
1915    typedef typename __base::__node_pointer            __node_pointer;
1916    typedef typename __base::__node_const_pointer      __node_const_pointer;
1917    typedef __map_node_destructor<__node_allocator> _Dp;
1918    typedef unique_ptr<__node, _Dp> __node_holder;
1919
1920#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1921    __node_holder __construct_node();
1922    template <class _A0>
1923        __node_holder
1924         __construct_node(_A0&& __a0);
1925#ifndef _LIBCPP_HAS_NO_VARIADICS
1926    template <class _A0, class _A1, class ..._Args>
1927        __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
1928#endif  // _LIBCPP_HAS_NO_VARIADICS
1929#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1930};
1931
1932#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1933
1934template <class _Key, class _Tp, class _Compare, class _Allocator>
1935multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
1936    : __tree_(_VSTD::move(__m.__tree_), __a)
1937{
1938    if (__a != __m.get_allocator())
1939    {
1940        const_iterator __e = cend();
1941        while (!__m.empty())
1942            __tree_.__insert_multi(__e.__i_,
1943                    _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
1944    }
1945}
1946
1947template <class _Key, class _Tp, class _Compare, class _Allocator>
1948typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1949multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1950{
1951    __node_allocator& __na = __tree_.__node_alloc();
1952    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1953    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
1954    __h.get_deleter().__first_constructed = true;
1955    __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
1956    __h.get_deleter().__second_constructed = true;
1957    return __h;
1958}
1959
1960template <class _Key, class _Tp, class _Compare, class _Allocator>
1961template <class _A0>
1962typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1963multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1964{
1965    __node_allocator& __na = __tree_.__node_alloc();
1966    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1967    __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
1968    __h.get_deleter().__first_constructed = true;
1969    __h.get_deleter().__second_constructed = true;
1970    return __h;
1971}
1972
1973#ifndef _LIBCPP_HAS_NO_VARIADICS
1974
1975template <class _Key, class _Tp, class _Compare, class _Allocator>
1976template <class _A0, class _A1, class ..._Args>
1977typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1978multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1979{
1980    __node_allocator& __na = __tree_.__node_alloc();
1981    __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1982    __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1983                             _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1984                             _VSTD::forward<_Args>(__args)...);
1985    __h.get_deleter().__first_constructed = true;
1986    __h.get_deleter().__second_constructed = true;
1987    return __h;
1988}
1989
1990#endif  // _LIBCPP_HAS_NO_VARIADICS
1991#endif  // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1992
1993#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
1994
1995template <class _Key, class _Tp, class _Compare, class _Allocator>
1996template <class ..._Args>
1997typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1998multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
1999{
2000    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2001    iterator __r = __tree_.__node_insert_multi(__h.get());
2002    __h.release();
2003    return __r;
2004}
2005
2006template <class _Key, class _Tp, class _Compare, class _Allocator>
2007template <class ..._Args>
2008typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
2009multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
2010                                                        _Args&& ...__args)
2011{
2012    __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
2013    iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
2014    __h.release();
2015    return __r;
2016}
2017
2018#endif  // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
2019
2020template <class _Key, class _Tp, class _Compare, class _Allocator>
2021inline _LIBCPP_INLINE_VISIBILITY
2022bool
2023operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2024           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2025{
2026    return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
2027}
2028
2029template <class _Key, class _Tp, class _Compare, class _Allocator>
2030inline _LIBCPP_INLINE_VISIBILITY
2031bool
2032operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2033           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2034{
2035    return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
2036}
2037
2038template <class _Key, class _Tp, class _Compare, class _Allocator>
2039inline _LIBCPP_INLINE_VISIBILITY
2040bool
2041operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2042           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2043{
2044    return !(__x == __y);
2045}
2046
2047template <class _Key, class _Tp, class _Compare, class _Allocator>
2048inline _LIBCPP_INLINE_VISIBILITY
2049bool
2050operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2051           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2052{
2053    return __y < __x;
2054}
2055
2056template <class _Key, class _Tp, class _Compare, class _Allocator>
2057inline _LIBCPP_INLINE_VISIBILITY
2058bool
2059operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2060           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2061{
2062    return !(__x < __y);
2063}
2064
2065template <class _Key, class _Tp, class _Compare, class _Allocator>
2066inline _LIBCPP_INLINE_VISIBILITY
2067bool
2068operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2069           const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2070{
2071    return !(__y < __x);
2072}
2073
2074template <class _Key, class _Tp, class _Compare, class _Allocator>
2075inline _LIBCPP_INLINE_VISIBILITY
2076void
2077swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2078     multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2079    _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2080{
2081    __x.swap(__y);
2082}
2083
2084_LIBCPP_END_NAMESPACE_STD
2085
2086#endif  // _LIBCPP_MAP
2087