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