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