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