blob: 886aecf2c9f4468df6c93acb443ddadcd74a32a7 [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//
Howard Hinnantee11c312010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantc51e1022010-05-11 19:42:16 +00008//
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:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000057 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);
Howard Hinnantc51e1022010-05-11 19:42:16 +000062 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);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000071 map(map&& m)
72 noexcept(
73 is_nothrow_move_constructible<allocator_type>::value &&
74 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000075 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);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000083 map& operator=(map&& m)
84 noexcept(
85 allocator_type::propagate_on_container_move_assignment::value &&
86 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +000087 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000088 map& operator=(initializer_list<value_type> il);
89
90 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000091 iterator begin() noexcept;
92 const_iterator begin() const noexcept;
93 iterator end() noexcept;
94 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +000095
Howard Hinnantf95f4f52011-06-04 15:22:34 +000096 reverse_iterator rbegin() noexcept;
97 const_reverse_iterator rbegin() const noexcept;
98 reverse_iterator rend() noexcept;
99 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000100
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000101 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;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000105
106 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000107 bool empty() const noexcept;
108 size_type size() const noexcept;
109 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000110
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);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000136 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000137
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000138 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));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000143
144 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000145 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000146 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
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000194swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
195 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000196
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:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000232 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);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000238 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);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000245 multimap(multimap&& m)
246 noexcept(
247 is_nothrow_move_constructible<allocator_type>::value &&
248 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000249 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);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000258 multimap& operator=(multimap&& m)
259 noexcept(
260 allocator_type::propagate_on_container_move_assignment::value &&
261 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000262 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000263 multimap& operator=(initializer_list<value_type> il);
264
265 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000266 iterator begin() noexcept;
267 const_iterator begin() const noexcept;
268 iterator end() noexcept;
269 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000270
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000271 reverse_iterator rbegin() noexcept;
272 const_reverse_iterator rbegin() const noexcept;
273 reverse_iterator rend() noexcept;
274 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000275
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000276 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;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000280
281 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000282 bool empty() const noexcept;
283 size_type size() const noexcept;
284 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000285
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);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000304 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000305
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000306 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));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000311
312 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000313 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000314 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,
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000363 multimap<Key, T, Compare, Allocator>& y)
364 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000365
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#pragma GCC system_header
379
380_LIBCPP_BEGIN_NAMESPACE_STD
381
382template <class _Key, class _Tp, class _Compare, bool = is_empty<_Compare>::value>
383class __map_value_compare
384 : private _Compare
385{
Howard Hinnant6098e092011-01-04 19:21:05 +0000386 typedef pair<typename std::remove_const<_Key>::type, _Tp> _P;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000387 typedef pair<const _Key, _Tp> _CP;
388public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000390 __map_value_compare()
391 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
392 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000393 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000394 __map_value_compare(_Compare c)
395 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
396 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000397 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000398 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000399 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000400 bool operator()(const _CP& __x, const _CP& __y) const
401 {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000402 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000403 bool operator()(const _CP& __x, const _P& __y) const
404 {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000405 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000406 bool operator()(const _CP& __x, const _Key& __y) const
407 {return static_cast<const _Compare&>(*this)(__x.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000408 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000409 bool operator()(const _P& __x, const _CP& __y) const
410 {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000411 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000412 bool operator()(const _P& __x, const _P& __y) const
413 {return static_cast<const _Compare&>(*this)(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000414 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000415 bool operator()(const _P& __x, const _Key& __y) const
416 {return static_cast<const _Compare&>(*this)(__x.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000417 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000418 bool operator()(const _Key& __x, const _CP& __y) const
419 {return static_cast<const _Compare&>(*this)(__x, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000420 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000421 bool operator()(const _Key& __x, const _P& __y) const
422 {return static_cast<const _Compare&>(*this)(__x, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000423 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000424 bool operator()(const _Key& __x, const _Key& __y) const
425 {return static_cast<const _Compare&>(*this)(__x, __y);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000426};
427
428template <class _Key, class _Tp, class _Compare>
429class __map_value_compare<_Key, _Tp, _Compare, false>
430{
431 _Compare comp;
432
Howard Hinnant6098e092011-01-04 19:21:05 +0000433 typedef pair<typename std::remove_const<_Key>::type, _Tp> _P;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000434 typedef pair<const _Key, _Tp> _CP;
435
436public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000437 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000438 __map_value_compare()
439 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
440 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000441 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000442 __map_value_compare(_Compare c)
443 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
444 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000446 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000447
Howard Hinnant756c69b2010-09-22 16:48:34 +0000448 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000449 bool operator()(const _CP& __x, const _CP& __y) const
450 {return comp(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000451 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000452 bool operator()(const _CP& __x, const _P& __y) const
453 {return comp(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000454 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000455 bool operator()(const _CP& __x, const _Key& __y) const
456 {return comp(__x.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000457 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000458 bool operator()(const _P& __x, const _CP& __y) const
459 {return comp(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000460 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000461 bool operator()(const _P& __x, const _P& __y) const
462 {return comp(__x.first, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000464 bool operator()(const _P& __x, const _Key& __y) const
465 {return comp(__x.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000466 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000467 bool operator()(const _Key& __x, const _CP& __y) const
468 {return comp(__x, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000470 bool operator()(const _Key& __x, const _P& __y) const
471 {return comp(__x, __y.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000472 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000473 bool operator()(const _Key& __x, const _Key& __y) const
474 {return comp(__x, __y);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000475};
476
477template <class _Allocator>
478class __map_node_destructor
479{
480 typedef _Allocator allocator_type;
481 typedef allocator_traits<allocator_type> __alloc_traits;
482 typedef typename __alloc_traits::value_type::value_type value_type;
483public:
484 typedef typename __alloc_traits::pointer pointer;
485private:
486 typedef typename value_type::first_type first_type;
487 typedef typename value_type::second_type second_type;
488
489 allocator_type& __na_;
490
491 __map_node_destructor& operator=(const __map_node_destructor&);
492
493public:
494 bool __first_constructed;
495 bool __second_constructed;
496
Howard Hinnant756c69b2010-09-22 16:48:34 +0000497 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000498 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000499 : __na_(__na),
500 __first_constructed(false),
501 __second_constructed(false)
502 {}
503
Howard Hinnant74279a52010-09-04 23:28:19 +0000504#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant756c69b2010-09-22 16:48:34 +0000505 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000506 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000507 : __na_(__x.__na_),
508 __first_constructed(__x.__value_constructed),
509 __second_constructed(__x.__value_constructed)
510 {
511 __x.__value_constructed = false;
512 }
Howard Hinnant5dc89112010-09-04 23:46:48 +0000513#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000514
Howard Hinnant756c69b2010-09-22 16:48:34 +0000515 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000516 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000517 {
518 if (__second_constructed)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000519 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000520 if (__first_constructed)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000521 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000522 if (__p)
523 __alloc_traits::deallocate(__na_, __p, 1);
524 }
525};
526
Howard Hinnant944510a2011-06-14 19:58:17 +0000527template <class _Key, class _Tp, class _Compare, class _Allocator>
528 class map;
529template <class _Key, class _Tp, class _Compare, class _Allocator>
530 class multimap;
531template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000532
533template <class _TreeIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000534class _LIBCPP_VISIBLE __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000535{
536 _TreeIterator __i_;
537
538 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000539 typedef const typename _TreeIterator::value_type::first_type __key_type;
540 typedef typename _TreeIterator::value_type::second_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000541public:
542 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000543 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000544 typedef typename _TreeIterator::difference_type difference_type;
545 typedef value_type& reference;
546 typedef typename __pointer_traits::template
547#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
548 rebind<value_type>
549#else
550 rebind<value_type>::other
551#endif
552 pointer;
553
Howard Hinnant756c69b2010-09-22 16:48:34 +0000554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000555 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000556
Howard Hinnant756c69b2010-09-22 16:48:34 +0000557 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000558 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000559
Howard Hinnant756c69b2010-09-22 16:48:34 +0000560 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000561 reference operator*() const {return *operator->();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000562 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000563 pointer operator->() const {return (pointer)__i_.operator->();}
564
Howard Hinnant756c69b2010-09-22 16:48:34 +0000565 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000566 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000567 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000568 __map_iterator operator++(int)
569 {
570 __map_iterator __t(*this);
571 ++(*this);
572 return __t;
573 }
574
Howard Hinnant756c69b2010-09-22 16:48:34 +0000575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000576 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000578 __map_iterator operator--(int)
579 {
580 __map_iterator __t(*this);
581 --(*this);
582 return __t;
583 }
584
Howard Hinnant756c69b2010-09-22 16:48:34 +0000585 friend _LIBCPP_INLINE_VISIBILITY
586 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000587 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000588 friend
589 _LIBCPP_INLINE_VISIBILITY
590 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000591 {return __x.__i_ != __y.__i_;}
592
Howard Hinnant756c69b2010-09-22 16:48:34 +0000593 template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
594 template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
595 template <class> friend class _LIBCPP_VISIBLE __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000596};
597
598template <class _TreeIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000599class _LIBCPP_VISIBLE __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000600{
601 _TreeIterator __i_;
602
603 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000604 typedef const typename _TreeIterator::value_type::first_type __key_type;
605 typedef typename _TreeIterator::value_type::second_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000606public:
607 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000608 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000609 typedef typename _TreeIterator::difference_type difference_type;
610 typedef const value_type& reference;
611 typedef typename __pointer_traits::template
612#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000613 rebind<const value_type>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000614#else
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000615 rebind<const value_type>::other
Howard Hinnantc51e1022010-05-11 19:42:16 +0000616#endif
617 pointer;
618
Howard Hinnant756c69b2010-09-22 16:48:34 +0000619 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000620 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000621
Howard Hinnant756c69b2010-09-22 16:48:34 +0000622 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000623 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000624 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000625 __map_const_iterator(
626 __map_iterator<typename _TreeIterator::__non_const_iterator> __i)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000627 _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000628 : __i_(__i.__i_) {}
629
Howard Hinnant756c69b2010-09-22 16:48:34 +0000630 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000631 reference operator*() const {return *operator->();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000632 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000633 pointer operator->() const {return (pointer)__i_.operator->();}
634
Howard Hinnant756c69b2010-09-22 16:48:34 +0000635 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000636 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000637 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000638 __map_const_iterator operator++(int)
639 {
640 __map_const_iterator __t(*this);
641 ++(*this);
642 return __t;
643 }
644
Howard Hinnant756c69b2010-09-22 16:48:34 +0000645 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000646 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000647 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000648 __map_const_iterator operator--(int)
649 {
650 __map_const_iterator __t(*this);
651 --(*this);
652 return __t;
653 }
654
Howard Hinnant756c69b2010-09-22 16:48:34 +0000655 friend _LIBCPP_INLINE_VISIBILITY
656 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000657 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000658 friend _LIBCPP_INLINE_VISIBILITY
659 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000660 {return __x.__i_ != __y.__i_;}
661
Howard Hinnant756c69b2010-09-22 16:48:34 +0000662 template <class, class, class, class> friend class _LIBCPP_VISIBLE map;
663 template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap;
664 template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000665};
666
667template <class _Key, class _Tp, class _Compare = less<_Key>,
668 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnant756c69b2010-09-22 16:48:34 +0000669class _LIBCPP_VISIBLE map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000670{
671public:
672 // types:
673 typedef _Key key_type;
674 typedef _Tp mapped_type;
675 typedef pair<const key_type, mapped_type> value_type;
676 typedef _Compare key_compare;
677 typedef _Allocator allocator_type;
678 typedef value_type& reference;
679 typedef const value_type& const_reference;
680
Howard Hinnant756c69b2010-09-22 16:48:34 +0000681 class _LIBCPP_VISIBLE value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000682 : public binary_function<value_type, value_type, bool>
683 {
684 friend class map;
685 protected:
686 key_compare comp;
687
Howard Hinnant756c69b2010-09-22 16:48:34 +0000688 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000689 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000690 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000691 bool operator()(const value_type& __x, const value_type& __y) const
692 {return comp(__x.first, __y.first);}
693 };
694
695private:
696 typedef pair<key_type, mapped_type> __value_type;
697 typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
698 typedef typename allocator_traits<allocator_type>::template
699#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
700 rebind_alloc<__value_type>
701#else
702 rebind_alloc<__value_type>::other
703#endif
704 __allocator_type;
705 typedef __tree<__value_type, __vc, __allocator_type> __base;
706 typedef typename __base::__node_traits __node_traits;
707 typedef allocator_traits<allocator_type> __alloc_traits;
708
709 __base __tree_;
710
711public:
712 typedef typename __alloc_traits::pointer pointer;
713 typedef typename __alloc_traits::const_pointer const_pointer;
714 typedef typename __alloc_traits::size_type size_type;
715 typedef typename __alloc_traits::difference_type difference_type;
716 typedef __map_iterator<typename __base::iterator> iterator;
717 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000718 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
719 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000720
Howard Hinnant756c69b2010-09-22 16:48:34 +0000721 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000722 explicit map(const key_compare& __comp = key_compare())
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000723 _NOEXCEPT_(
724 is_nothrow_default_constructible<allocator_type>::value &&
725 is_nothrow_default_constructible<key_compare>::value &&
726 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000727 : __tree_(__vc(__comp)) {}
728
Howard Hinnant756c69b2010-09-22 16:48:34 +0000729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000730 explicit map(const key_compare& __comp, const allocator_type& __a)
731 : __tree_(__vc(__comp), __a) {}
732
733 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000734 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735 map(_InputIterator __f, _InputIterator __l,
736 const key_compare& __comp = key_compare())
737 : __tree_(__vc(__comp))
738 {
739 insert(__f, __l);
740 }
741
742 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000743 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000744 map(_InputIterator __f, _InputIterator __l,
745 const key_compare& __comp, const allocator_type& __a)
746 : __tree_(__vc(__comp), __a)
747 {
748 insert(__f, __l);
749 }
750
Howard Hinnant756c69b2010-09-22 16:48:34 +0000751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000752 map(const map& __m)
753 : __tree_(__m.__tree_)
754 {
755 insert(__m.begin(), __m.end());
756 }
757
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000758 _LIBCPP_INLINE_VISIBILITY
759 map& operator=(const map& __m)
760 {
761 __tree_ = __m.__tree_;
762 return *this;
763 }
764
Howard Hinnant74279a52010-09-04 23:28:19 +0000765#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000766
Howard Hinnant756c69b2010-09-22 16:48:34 +0000767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000768 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000769 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000770 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771 {
772 }
773
774 map(map&& __m, const allocator_type& __a);
775
Howard Hinnant756c69b2010-09-22 16:48:34 +0000776 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +0000777 map& operator=(map&& __m)
778 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
779 {
780 __tree_ = _VSTD::move(__m.__tree_);
781 return *this;
782 }
783
784#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
785
786#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
787
788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000789 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
790 : __tree_(__vc(__comp))
791 {
792 insert(__il.begin(), __il.end());
793 }
794
Howard Hinnant756c69b2010-09-22 16:48:34 +0000795 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000796 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
797 : __tree_(__vc(__comp), __a)
798 {
799 insert(__il.begin(), __il.end());
800 }
801
Howard Hinnant756c69b2010-09-22 16:48:34 +0000802 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000803 map& operator=(initializer_list<value_type> __il)
804 {
805 __tree_.__assign_unique(__il.begin(), __il.end());
806 return *this;
807 }
808
Howard Hinnant33711792011-08-12 21:56:02 +0000809#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +0000810
Howard Hinnant756c69b2010-09-22 16:48:34 +0000811 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000812 explicit map(const allocator_type& __a)
813 : __tree_(__a)
814 {
815 }
816
Howard Hinnant756c69b2010-09-22 16:48:34 +0000817 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000818 map(const map& __m, const allocator_type& __a)
819 : __tree_(__m.__tree_.value_comp(), __a)
820 {
821 insert(__m.begin(), __m.end());
822 }
823
Howard Hinnant756c69b2010-09-22 16:48:34 +0000824 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000825 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000826 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000827 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000829 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000830 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000831 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000832
Howard Hinnant756c69b2010-09-22 16:48:34 +0000833 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000834 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000836 const_reverse_iterator rbegin() const _NOEXCEPT
837 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000839 reverse_iterator rend() _NOEXCEPT
840 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000841 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000842 const_reverse_iterator rend() const _NOEXCEPT
843 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000844
Howard Hinnant756c69b2010-09-22 16:48:34 +0000845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000846 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000847 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000848 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000849 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000850 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000852 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000853
Howard Hinnant756c69b2010-09-22 16:48:34 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000855 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000857 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000858 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000859 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000860
861 mapped_type& operator[](const key_type& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +0000862#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000863 mapped_type& operator[](key_type&& __k);
864#endif
865
866 mapped_type& at(const key_type& __k);
867 const mapped_type& at(const key_type& __k) const;
868
Howard Hinnant756c69b2010-09-22 16:48:34 +0000869 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000870 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000871 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000872 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000874 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
875
Howard Hinnant74279a52010-09-04 23:28:19 +0000876#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000877
Howard Hinnant756c69b2010-09-22 16:48:34 +0000878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000879 pair<iterator, bool>
880 emplace() {return __tree_.__emplace_unique();}
881
882 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000883 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000884 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000885 pair<iterator, bool>
886 emplace(_A0&& __a0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000887 {return __tree_.__emplace_unique(_VSTD::forward<_A0>(__a0));}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000888
Howard Hinnant74279a52010-09-04 23:28:19 +0000889#ifndef _LIBCPP_HAS_NO_VARIADICS
890
Howard Hinnantc51e1022010-05-11 19:42:16 +0000891 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000892 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 pair<iterator, bool>
894 emplace(_A0&& __a0, _Args&& ...__args);
895
Howard Hinnant74279a52010-09-04 23:28:19 +0000896#endif // _LIBCPP_HAS_NO_VARIADICS
897
Howard Hinnant756c69b2010-09-22 16:48:34 +0000898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000899 iterator
900 emplace_hint(const_iterator __p)
901 {return __tree_.__emplace_hint_unique(__p.__i_);}
902
903 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000904 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000905 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000906 iterator
907 emplace_hint(const_iterator __p, _A0&& __a0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000908 {return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_A0>(__a0));}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000909
Howard Hinnant74279a52010-09-04 23:28:19 +0000910#ifndef _LIBCPP_HAS_NO_VARIADICS
911
Howard Hinnantc51e1022010-05-11 19:42:16 +0000912 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000913 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000914 iterator
915 emplace_hint(const_iterator __p, _A0&& __a0, _Args&& ...__args);
916
Howard Hinnant74279a52010-09-04 23:28:19 +0000917#endif // _LIBCPP_HAS_NO_VARIADICS
918
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919 template <class _P,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000920 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000921 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000922 pair<iterator, bool> insert(_P&& __p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000923 {return __tree_.__insert_unique(_VSTD::forward<_P>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000924
925 template <class _P,
Howard Hinnante383ebc2011-06-19 21:45:00 +0000926 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000927 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000928 iterator insert(const_iterator __pos, _P&& __p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000929 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_P>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000930
Howard Hinnant74279a52010-09-04 23:28:19 +0000931#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000932
Howard Hinnant756c69b2010-09-22 16:48:34 +0000933 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000934 pair<iterator, bool>
935 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
936
Howard Hinnant756c69b2010-09-22 16:48:34 +0000937 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000938 iterator
939 insert(const_iterator __p, const value_type& __v)
940 {return __tree_.__insert_unique(__p.__i_, __v);}
941
942 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000943 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944 void insert(_InputIterator __f, _InputIterator __l)
945 {
946 for (const_iterator __e = cend(); __f != __l; ++__f)
947 insert(__e.__i_, *__f);
948 }
949
Howard Hinnant33711792011-08-12 21:56:02 +0000950#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
951
Howard Hinnant756c69b2010-09-22 16:48:34 +0000952 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000953 void insert(initializer_list<value_type> __il)
954 {insert(__il.begin(), __il.end());}
955
Howard Hinnant33711792011-08-12 21:56:02 +0000956#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
957
Howard Hinnant756c69b2010-09-22 16:48:34 +0000958 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000960 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000961 size_type erase(const key_type& __k)
962 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000963 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000964 iterator erase(const_iterator __f, const_iterator __l)
965 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000966 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000967 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000968
Howard Hinnant756c69b2010-09-22 16:48:34 +0000969 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000970 void swap(map& __m)
971 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
972 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000973
Howard Hinnant756c69b2010-09-22 16:48:34 +0000974 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000975 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000976 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000977 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000978 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979 size_type count(const key_type& __k) const
980 {return __tree_.__count_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000981 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000982 iterator lower_bound(const key_type& __k)
983 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000984 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000985 const_iterator lower_bound(const key_type& __k) const
986 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000988 iterator upper_bound(const key_type& __k)
989 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000990 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000991 const_iterator upper_bound(const key_type& __k) const
992 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000993 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000994 pair<iterator,iterator> equal_range(const key_type& __k)
995 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000996 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000997 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
998 {return __tree_.__equal_range_unique(__k);}
999
1000private:
1001 typedef typename __base::__node __node;
1002 typedef typename __base::__node_allocator __node_allocator;
1003 typedef typename __base::__node_pointer __node_pointer;
1004 typedef typename __base::__node_const_pointer __node_const_pointer;
1005 typedef typename __base::__node_base_pointer __node_base_pointer;
1006 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
1007 typedef __map_node_destructor<__node_allocator> _D;
1008 typedef unique_ptr<__node, _D> __node_holder;
1009
Howard Hinnant74279a52010-09-04 23:28:19 +00001010#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001011 __node_holder __construct_node();
1012 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001013 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001014 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant74279a52010-09-04 23:28:19 +00001015#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001017 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001018 __node_holder __construct_node(_A0&& __a0, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001019#endif // _LIBCPP_HAS_NO_VARIADICS
1020#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001021 __node_holder __construct_node(const key_type& __k);
1022#endif
1023
1024 __node_base_pointer&
1025 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
1026 __node_base_pointer&
1027 __find_equal_key(const_iterator __hint,
1028 __node_base_pointer& __parent, const key_type& __k);
1029 __node_base_const_pointer
1030 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1031};
1032
1033// Find place to insert if __k doesn't exist
1034// Set __parent to parent of null leaf
1035// Return reference to null leaf
1036// If __k exists, set parent to node of __k and return reference to node of __k
1037template <class _Key, class _Tp, class _Compare, class _Allocator>
1038typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1039map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1040 const key_type& __k)
1041{
1042 __node_pointer __nd = __tree_.__root();
1043 if (__nd != nullptr)
1044 {
1045 while (true)
1046 {
1047 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
1048 {
1049 if (__nd->__left_ != nullptr)
1050 __nd = static_cast<__node_pointer>(__nd->__left_);
1051 else
1052 {
1053 __parent = __nd;
1054 return __parent->__left_;
1055 }
1056 }
1057 else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
1058 {
1059 if (__nd->__right_ != nullptr)
1060 __nd = static_cast<__node_pointer>(__nd->__right_);
1061 else
1062 {
1063 __parent = __nd;
1064 return __parent->__right_;
1065 }
1066 }
1067 else
1068 {
1069 __parent = __nd;
1070 return __parent;
1071 }
1072 }
1073 }
1074 __parent = __tree_.__end_node();
1075 return __parent->__left_;
1076}
1077
1078// Find place to insert if __k doesn't exist
1079// First check prior to __hint.
1080// Next check after __hint.
1081// Next do O(log N) search.
1082// Set __parent to parent of null leaf
1083// Return reference to null leaf
1084// If __k exists, set parent to node of __k and return reference to node of __k
1085template <class _Key, class _Tp, class _Compare, class _Allocator>
1086typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1087map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(const_iterator __hint,
1088 __node_base_pointer& __parent,
1089 const key_type& __k)
1090{
1091 if (__hint == end() || __tree_.value_comp().key_comp()(__k, __hint->first)) // check before
1092 {
1093 // __k < *__hint
1094 const_iterator __prior = __hint;
1095 if (__prior == begin() || __tree_.value_comp().key_comp()((--__prior)->first, __k))
1096 {
1097 // *prev(__hint) < __k < *__hint
1098 if (__hint.__ptr_->__left_ == nullptr)
1099 {
1100 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1101 return __parent->__left_;
1102 }
1103 else
1104 {
1105 __parent = const_cast<__node_pointer&>(__prior.__ptr_);
1106 return __parent->__right_;
1107 }
1108 }
1109 // __k <= *prev(__hint)
1110 return __find_equal_key(__parent, __k);
1111 }
1112 else if (__tree_.value_comp().key_comp()(__hint->first, __k)) // check after
1113 {
1114 // *__hint < __k
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001115 const_iterator __next = _VSTD::next(__hint);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001116 if (__next == end() || __tree_.value_comp().key_comp()(__k, __next->first))
1117 {
1118 // *__hint < __k < *next(__hint)
1119 if (__hint.__ptr_->__right_ == nullptr)
1120 {
1121 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1122 return __parent->__right_;
1123 }
1124 else
1125 {
1126 __parent = const_cast<__node_pointer&>(__next.__ptr_);
1127 return __parent->__left_;
1128 }
1129 }
1130 // *next(__hint) <= __k
1131 return __find_equal_key(__parent, __k);
1132 }
1133 // else __k == *__hint
1134 __parent = const_cast<__node_pointer&>(__hint.__ptr_);
1135 return __parent;
1136}
1137
1138// Find __k
1139// Set __parent to parent of null leaf and
1140// return reference to null leaf iv __k does not exist.
1141// If __k exists, set parent to node of __k and return reference to node of __k
1142template <class _Key, class _Tp, class _Compare, class _Allocator>
1143typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1144map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1145 const key_type& __k) const
1146{
1147 __node_const_pointer __nd = __tree_.__root();
1148 if (__nd != nullptr)
1149 {
1150 while (true)
1151 {
1152 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.first))
1153 {
1154 if (__nd->__left_ != nullptr)
1155 __nd = static_cast<__node_pointer>(__nd->__left_);
1156 else
1157 {
1158 __parent = __nd;
1159 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1160 }
1161 }
1162 else if (__tree_.value_comp().key_comp()(__nd->__value_.first, __k))
1163 {
1164 if (__nd->__right_ != nullptr)
1165 __nd = static_cast<__node_pointer>(__nd->__right_);
1166 else
1167 {
1168 __parent = __nd;
1169 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1170 }
1171 }
1172 else
1173 {
1174 __parent = __nd;
1175 return __parent;
1176 }
1177 }
1178 }
1179 __parent = __tree_.__end_node();
1180 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1181}
1182
Howard Hinnant74279a52010-09-04 23:28:19 +00001183#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001184
1185template <class _Key, class _Tp, class _Compare, class _Allocator>
1186map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001187 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001188{
1189 if (__a != __m.get_allocator())
1190 {
1191 const_iterator __e = cend();
1192 while (!__m.empty())
1193 __tree_.__insert_unique(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001194 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195 }
1196}
1197
1198template <class _Key, class _Tp, class _Compare, class _Allocator>
1199typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1200map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1201{
1202 __node_allocator& __na = __tree_.__node_alloc();
1203 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001204 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001205 __h.get_deleter().__first_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001206 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001207 __h.get_deleter().__second_constructed = true;
1208 return __h;
1209}
1210
1211template <class _Key, class _Tp, class _Compare, class _Allocator>
1212template <class _A0,
1213 class>
1214typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1215map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1216{
1217 __node_allocator& __na = __tree_.__node_alloc();
1218 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001219 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001220 __h.get_deleter().__first_constructed = true;
1221 __h.get_deleter().__second_constructed = true;
1222 return __h;
1223}
1224
Howard Hinnant74279a52010-09-04 23:28:19 +00001225#ifndef _LIBCPP_HAS_NO_VARIADICS
1226
Howard Hinnantc51e1022010-05-11 19:42:16 +00001227template <class _Key, class _Tp, class _Compare, class _Allocator>
1228template <class _A0, class ..._Args,
1229 class>
1230typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1231map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _Args&& ...__args)
1232{
1233 __node_allocator& __na = __tree_.__node_alloc();
1234 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001235 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001236 __h.get_deleter().__first_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001237 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001238 __h.get_deleter().__second_constructed = true;
1239 return __h;
1240}
1241
Howard Hinnant74279a52010-09-04 23:28:19 +00001242#endif // _LIBCPP_HAS_NO_VARIADICS
1243
1244#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001245
1246template <class _Key, class _Tp, class _Compare, class _Allocator>
1247typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1248map<_Key, _Tp, _Compare, _Allocator>::__construct_node(const key_type& __k)
1249{
1250 __node_allocator& __na = __tree_.__node_alloc();
1251 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001252 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001253 __h.get_deleter().__first_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001254 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001255 __h.get_deleter().__second_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001256 return _VSTD::move(__h);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001257}
1258
Howard Hinnant74279a52010-09-04 23:28:19 +00001259#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001260
1261template <class _Key, class _Tp, class _Compare, class _Allocator>
1262_Tp&
1263map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1264{
1265 __node_base_pointer __parent;
1266 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1267 __node_pointer __r = static_cast<__node_pointer>(__child);
1268 if (__child == nullptr)
1269 {
1270 __node_holder __h = __construct_node(__k);
1271 __tree_.__insert_node_at(__parent, __child, __h.get());
1272 __r = __h.release();
1273 }
1274 return __r->__value_.second;
1275}
1276
Howard Hinnant74279a52010-09-04 23:28:19 +00001277#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001278
1279template <class _Key, class _Tp, class _Compare, class _Allocator>
1280_Tp&
1281map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1282{
1283 __node_base_pointer __parent;
1284 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1285 __node_pointer __r = static_cast<__node_pointer>(__child);
1286 if (__child == nullptr)
1287 {
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001288 __node_holder __h = __construct_node(_VSTD::move(__k));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001289 __tree_.__insert_node_at(__parent, __child, __h.get());
1290 __r = __h.release();
1291 }
1292 return __r->__value_.second;
1293}
1294
Howard Hinnant74279a52010-09-04 23:28:19 +00001295#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001296
1297template <class _Key, class _Tp, class _Compare, class _Allocator>
1298_Tp&
1299map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1300{
1301 __node_base_pointer __parent;
1302 __node_base_pointer& __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001303#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001304 if (__child == nullptr)
1305 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001306#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001307 return static_cast<__node_pointer>(__child)->__value_.second;
1308}
1309
1310template <class _Key, class _Tp, class _Compare, class _Allocator>
1311const _Tp&
1312map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1313{
1314 __node_base_const_pointer __parent;
1315 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001316#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001317 if (__child == nullptr)
1318 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001319#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001320 return static_cast<__node_const_pointer>(__child)->__value_.second;
1321}
1322
Howard Hinnant74279a52010-09-04 23:28:19 +00001323#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001324
1325template <class _Key, class _Tp, class _Compare, class _Allocator>
1326template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001327 class //= typename enable_if<is_constructible<_Key, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001328 >
1329pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
1330map<_Key, _Tp, _Compare, _Allocator>::emplace(_A0&& __a0, _Args&& ...__args)
1331{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001332 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1333 _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1335 if (__r.second)
1336 __h.release();
1337 return __r;
1338}
1339
1340template <class _Key, class _Tp, class _Compare, class _Allocator>
1341template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001342 class //= typename enable_if<is_constructible<_Key, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001343 >
1344typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1345map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1346 _A0&& __a0, _Args&& ...__args)
1347{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001348 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1349 _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001350 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1351 if (__r.__i_.__ptr_ == __h.get())
1352 __h.release();
1353 return __r;
1354}
1355
Howard Hinnant74279a52010-09-04 23:28:19 +00001356#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001357
1358template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001359inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001360bool
1361operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1362 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1363{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001364 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001365}
1366
1367template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001368inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001369bool
1370operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1371 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1372{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001373 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001374}
1375
1376template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001377inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001378bool
1379operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1380 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1381{
1382 return !(__x == __y);
1383}
1384
1385template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001386inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001387bool
1388operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1389 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1390{
1391 return __y < __x;
1392}
1393
1394template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001395inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001396bool
1397operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1398 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1399{
1400 return !(__x < __y);
1401}
1402
1403template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001404inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001405bool
1406operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1407 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1408{
1409 return !(__y < __x);
1410}
1411
1412template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001413inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001414void
1415swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1416 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001417 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001418{
1419 __x.swap(__y);
1420}
1421
1422template <class _Key, class _Tp, class _Compare = less<_Key>,
1423 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnant756c69b2010-09-22 16:48:34 +00001424class _LIBCPP_VISIBLE multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001425{
1426public:
1427 // types:
1428 typedef _Key key_type;
1429 typedef _Tp mapped_type;
1430 typedef pair<const key_type, mapped_type> value_type;
1431 typedef _Compare key_compare;
1432 typedef _Allocator allocator_type;
1433 typedef value_type& reference;
1434 typedef const value_type& const_reference;
1435
Howard Hinnant756c69b2010-09-22 16:48:34 +00001436 class _LIBCPP_VISIBLE value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001437 : public binary_function<value_type, value_type, bool>
1438 {
1439 friend class multimap;
1440 protected:
1441 key_compare comp;
1442
Howard Hinnant756c69b2010-09-22 16:48:34 +00001443 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001444 value_compare(key_compare c) : comp(c) {}
1445 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001446 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001447 bool operator()(const value_type& __x, const value_type& __y) const
1448 {return comp(__x.first, __y.first);}
1449 };
1450
1451private:
1452 typedef pair<key_type, mapped_type> __value_type;
1453 typedef __map_value_compare<key_type, mapped_type, key_compare> __vc;
1454 typedef typename allocator_traits<allocator_type>::template
1455#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1456 rebind_alloc<__value_type>
1457#else
1458 rebind_alloc<__value_type>::other
1459#endif
1460 __allocator_type;
1461 typedef __tree<__value_type, __vc, __allocator_type> __base;
1462 typedef typename __base::__node_traits __node_traits;
1463 typedef allocator_traits<allocator_type> __alloc_traits;
1464
1465 __base __tree_;
1466
1467public:
1468 typedef typename __alloc_traits::pointer pointer;
1469 typedef typename __alloc_traits::const_pointer const_pointer;
1470 typedef typename __alloc_traits::size_type size_type;
1471 typedef typename __alloc_traits::difference_type difference_type;
1472 typedef __map_iterator<typename __base::iterator> iterator;
1473 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001474 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1475 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001476
Howard Hinnant756c69b2010-09-22 16:48:34 +00001477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001478 explicit multimap(const key_compare& __comp = key_compare())
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001479 _NOEXCEPT_(
1480 is_nothrow_default_constructible<allocator_type>::value &&
1481 is_nothrow_default_constructible<key_compare>::value &&
1482 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001483 : __tree_(__vc(__comp)) {}
1484
Howard Hinnant756c69b2010-09-22 16:48:34 +00001485 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001486 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1487 : __tree_(__vc(__comp), __a) {}
1488
1489 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001491 multimap(_InputIterator __f, _InputIterator __l,
1492 const key_compare& __comp = key_compare())
1493 : __tree_(__vc(__comp))
1494 {
1495 insert(__f, __l);
1496 }
1497
1498 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001499 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001500 multimap(_InputIterator __f, _InputIterator __l,
1501 const key_compare& __comp, const allocator_type& __a)
1502 : __tree_(__vc(__comp), __a)
1503 {
1504 insert(__f, __l);
1505 }
1506
Howard Hinnant756c69b2010-09-22 16:48:34 +00001507 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001508 multimap(const multimap& __m)
1509 : __tree_(__m.__tree_.value_comp(),
1510 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1511 {
1512 insert(__m.begin(), __m.end());
1513 }
1514
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001515 _LIBCPP_INLINE_VISIBILITY
1516 multimap& operator=(const multimap& __m)
1517 {
1518 __tree_ = __m.__tree_;
1519 return *this;
1520 }
1521
Howard Hinnant74279a52010-09-04 23:28:19 +00001522#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001523
Howard Hinnant756c69b2010-09-22 16:48:34 +00001524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001525 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001526 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001527 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001528 {
1529 }
1530
1531 multimap(multimap&& __m, const allocator_type& __a);
1532
Howard Hinnant756c69b2010-09-22 16:48:34 +00001533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001534 multimap& operator=(multimap&& __m)
1535 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1536 {
1537 __tree_ = _VSTD::move(__m.__tree_);
1538 return *this;
1539 }
1540
1541#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1542
1543#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1544
1545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001546 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1547 : __tree_(__vc(__comp))
1548 {
1549 insert(__il.begin(), __il.end());
1550 }
1551
Howard Hinnant756c69b2010-09-22 16:48:34 +00001552 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001553 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1554 : __tree_(__vc(__comp), __a)
1555 {
1556 insert(__il.begin(), __il.end());
1557 }
1558
Howard Hinnant756c69b2010-09-22 16:48:34 +00001559 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001560 multimap& operator=(initializer_list<value_type> __il)
1561 {
1562 __tree_.__assign_multi(__il.begin(), __il.end());
1563 return *this;
1564 }
Howard Hinnant33711792011-08-12 21:56:02 +00001565
1566#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001567
Howard Hinnant756c69b2010-09-22 16:48:34 +00001568 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001569 explicit multimap(const allocator_type& __a)
1570 : __tree_(__a)
1571 {
1572 }
1573
Howard Hinnant756c69b2010-09-22 16:48:34 +00001574 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001575 multimap(const multimap& __m, const allocator_type& __a)
1576 : __tree_(__m.__tree_.value_comp(), __a)
1577 {
1578 insert(__m.begin(), __m.end());
1579 }
1580
Howard Hinnant756c69b2010-09-22 16:48:34 +00001581 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001582 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001583 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001584 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001585 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001586 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001588 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001589
Howard Hinnant756c69b2010-09-22 16:48:34 +00001590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001591 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001592 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001593 const_reverse_iterator rbegin() const _NOEXCEPT
1594 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001595 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001596 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001598 const_reverse_iterator rend() const _NOEXCEPT
1599 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001600
Howard Hinnant756c69b2010-09-22 16:48:34 +00001601 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001602 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001603 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001604 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001605 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001606 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001607 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001608 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001609
Howard Hinnant756c69b2010-09-22 16:48:34 +00001610 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001611 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001612 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001613 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001614 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001615 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001616
Howard Hinnant756c69b2010-09-22 16:48:34 +00001617 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001618 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001619 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001620 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001621 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001622 value_compare value_comp() const
1623 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001624
Howard Hinnant74279a52010-09-04 23:28:19 +00001625#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001626
Howard Hinnant756c69b2010-09-22 16:48:34 +00001627 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001628 iterator emplace() {return __tree_.__emplace_multi();}
1629
1630 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001631 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001632 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001633 iterator
1634 emplace(_A0&& __a0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001635 {return __tree_.__emplace_multi(_VSTD::forward<_A0>(__a0));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001636
Howard Hinnant74279a52010-09-04 23:28:19 +00001637#ifndef _LIBCPP_HAS_NO_VARIADICS
1638
Howard Hinnantc51e1022010-05-11 19:42:16 +00001639 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001640 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001641 iterator
1642 emplace(_A0&& __a0, _Args&& ...__args);
1643
Howard Hinnant74279a52010-09-04 23:28:19 +00001644#endif // _LIBCPP_HAS_NO_VARIADICS
1645
Howard Hinnant756c69b2010-09-22 16:48:34 +00001646 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001647 iterator emplace_hint(const_iterator __p)
1648 {return __tree_.__emplace_hint_multi(__p.__i_);}
1649
1650 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001651 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001653 iterator
1654 emplace_hint(const_iterator __p, _A0&& __a0)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001655 {return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_A0>(__a0));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001656
Howard Hinnant74279a52010-09-04 23:28:19 +00001657#ifndef _LIBCPP_HAS_NO_VARIADICS
1658
Howard Hinnantc51e1022010-05-11 19:42:16 +00001659 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001660 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001661 iterator
1662 emplace_hint(const_iterator __p, _A0&& __a0, _Args&& ...__args);
1663
Howard Hinnant74279a52010-09-04 23:28:19 +00001664#endif // _LIBCPP_HAS_NO_VARIADICS
1665
Howard Hinnantc51e1022010-05-11 19:42:16 +00001666 template <class _P,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001667 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001668 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001669 iterator insert(_P&& __p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001670 {return __tree_.__insert_multi(_VSTD::forward<_P>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001671
1672 template <class _P,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001673 class = typename enable_if<is_constructible<value_type, _P>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001674 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001675 iterator insert(const_iterator __pos, _P&& __p)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001676 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_P>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001677
Howard Hinnant74279a52010-09-04 23:28:19 +00001678#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001679
Howard Hinnant756c69b2010-09-22 16:48:34 +00001680 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001681 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1682
Howard Hinnant756c69b2010-09-22 16:48:34 +00001683 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001684 iterator insert(const_iterator __p, const value_type& __v)
1685 {return __tree_.__insert_multi(__p.__i_, __v);}
1686
1687 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001688 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001689 void insert(_InputIterator __f, _InputIterator __l)
1690 {
1691 for (const_iterator __e = cend(); __f != __l; ++__f)
1692 __tree_.__insert_multi(__e.__i_, *__f);
1693 }
1694
Howard Hinnant33711792011-08-12 21:56:02 +00001695#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1696
Howard Hinnant756c69b2010-09-22 16:48:34 +00001697 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001698 void insert(initializer_list<value_type> __il)
1699 {insert(__il.begin(), __il.end());}
1700
Howard Hinnant33711792011-08-12 21:56:02 +00001701#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1702
Howard Hinnant756c69b2010-09-22 16:48:34 +00001703 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001704 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001708 iterator erase(const_iterator __f, const_iterator __l)
1709 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001710 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001711 void clear() {__tree_.clear();}
1712
Howard Hinnant756c69b2010-09-22 16:48:34 +00001713 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001714 void swap(multimap& __m)
1715 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1716 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001717
Howard Hinnant756c69b2010-09-22 16:48:34 +00001718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001719 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001721 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001722 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001723 size_type count(const key_type& __k) const
1724 {return __tree_.__count_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001726 iterator lower_bound(const key_type& __k)
1727 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001728 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001729 const_iterator lower_bound(const key_type& __k) const
1730 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001732 iterator upper_bound(const key_type& __k)
1733 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001734 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001735 const_iterator upper_bound(const key_type& __k) const
1736 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001737 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001738 pair<iterator,iterator> equal_range(const key_type& __k)
1739 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001740 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001741 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1742 {return __tree_.__equal_range_multi(__k);}
1743
1744private:
1745 typedef typename __base::__node __node;
1746 typedef typename __base::__node_allocator __node_allocator;
1747 typedef typename __base::__node_pointer __node_pointer;
1748 typedef typename __base::__node_const_pointer __node_const_pointer;
1749 typedef __map_node_destructor<__node_allocator> _D;
1750 typedef unique_ptr<__node, _D> __node_holder;
1751
Howard Hinnant74279a52010-09-04 23:28:19 +00001752#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001753 __node_holder __construct_node();
1754 template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001755 class = typename enable_if<is_constructible<value_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001756 __node_holder __construct_node(_A0&& __a0);
Howard Hinnant74279a52010-09-04 23:28:19 +00001757#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001758 template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001759 class = typename enable_if<is_constructible<key_type, _A0>::value>::type>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001760 __node_holder __construct_node(_A0&& __a0, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001761#endif // _LIBCPP_HAS_NO_VARIADICS
1762#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001763};
1764
Howard Hinnant74279a52010-09-04 23:28:19 +00001765#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001766
1767template <class _Key, class _Tp, class _Compare, class _Allocator>
1768multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001769 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001770{
1771 if (__a != __m.get_allocator())
1772 {
1773 const_iterator __e = cend();
1774 while (!__m.empty())
1775 __tree_.__insert_multi(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001776 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001777 }
1778}
1779
1780template <class _Key, class _Tp, class _Compare, class _Allocator>
1781typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1782multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1783{
1784 __node_allocator& __na = __tree_.__node_alloc();
1785 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001786 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001787 __h.get_deleter().__first_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001788 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001789 __h.get_deleter().__second_constructed = true;
1790 return __h;
1791}
1792
1793template <class _Key, class _Tp, class _Compare, class _Allocator>
1794template <class _A0,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001795 class // = typename enable_if<is_constructible<value_type, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001796 >
1797typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1798multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1799{
1800 __node_allocator& __na = __tree_.__node_alloc();
1801 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001802 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001803 __h.get_deleter().__first_constructed = true;
1804 __h.get_deleter().__second_constructed = true;
1805 return __h;
1806}
1807
Howard Hinnant74279a52010-09-04 23:28:19 +00001808#ifndef _LIBCPP_HAS_NO_VARIADICS
1809
Howard Hinnantc51e1022010-05-11 19:42:16 +00001810template <class _Key, class _Tp, class _Compare, class _Allocator>
1811template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001812 class // = typename enable_if<is_constructible<key_type, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001813 >
1814typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1815multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _Args&& ...__args)
1816{
1817 __node_allocator& __na = __tree_.__node_alloc();
1818 __node_holder __h(__node_traits::allocate(__na, 1), _D(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001819 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.first), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001820 __h.get_deleter().__first_constructed = true;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001821 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.second), _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001822 __h.get_deleter().__second_constructed = true;
1823 return __h;
1824}
1825
Howard Hinnant74279a52010-09-04 23:28:19 +00001826#endif // _LIBCPP_HAS_NO_VARIADICS
1827#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001828
Howard Hinnant74279a52010-09-04 23:28:19 +00001829#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001830
1831template <class _Key, class _Tp, class _Compare, class _Allocator>
1832template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001833 class //= typename enable_if<is_constructible<_Key, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001834 >
1835typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1836multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_A0&& __a0, _Args&& ...__args)
1837{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001838 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1839 _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001840 iterator __r = __tree_.__node_insert_multi(__h.get());
1841 __h.release();
1842 return __r;
1843}
1844
1845template <class _Key, class _Tp, class _Compare, class _Allocator>
1846template <class _A0, class ..._Args,
Howard Hinnante383ebc2011-06-19 21:45:00 +00001847 class //= typename enable_if<is_constructible<_Key, _A0>::value>::type
Howard Hinnantc51e1022010-05-11 19:42:16 +00001848 >
1849typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1850multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
1851 _A0&& __a0,
1852 _Args&& ...__args)
1853{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001854 __node_holder __h = __construct_node(_VSTD::forward<_A0>(__a0),
1855 _VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001856 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1857 __h.release();
1858 return __r;
1859}
1860
Howard Hinnant74279a52010-09-04 23:28:19 +00001861#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001862
1863template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001864inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001865bool
1866operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1867 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1868{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001869 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001870}
1871
1872template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001873inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001874bool
1875operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1876 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1877{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001878 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001879}
1880
1881template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001882inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001883bool
1884operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1885 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1886{
1887 return !(__x == __y);
1888}
1889
1890template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001891inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001892bool
1893operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1894 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1895{
1896 return __y < __x;
1897}
1898
1899template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001900inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001901bool
1902operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1903 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1904{
1905 return !(__x < __y);
1906}
1907
1908template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001909inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001910bool
1911operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1912 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1913{
1914 return !(__y < __x);
1915}
1916
1917template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001918inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001919void
1920swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1921 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001922 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001923{
1924 __x.swap(__y);
1925}
1926
1927_LIBCPP_END_NAMESPACE_STD
1928
1929#endif // _LIBCPP_MAP