blob: 009e8e2162c5f7eb40531ff80efa525e31e39489 [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);
Marshall Clow300abfb2013-09-11 01:15:47 +000080 template <class InputIterator>
81 map(InputIterator first, InputIterator last, const allocator_type& a)
82 : map(first, last, Compare(), a) {} // C++14
83 map(initializer_list<value_type> il, const allocator_type& a)
84 : map(il, Compare(), a) {} // C++14
85 ~map();
Howard Hinnantc51e1022010-05-11 19:42:16 +000086
87 map& operator=(const map& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +000088 map& operator=(map&& m)
89 noexcept(
90 allocator_type::propagate_on_container_move_assignment::value &&
91 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +000092 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +000093 map& operator=(initializer_list<value_type> il);
94
95 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +000096 iterator begin() noexcept;
97 const_iterator begin() const noexcept;
98 iterator end() noexcept;
99 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000100
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000101 reverse_iterator rbegin() noexcept;
102 const_reverse_iterator rbegin() const noexcept;
103 reverse_iterator rend() noexcept;
104 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000105
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000106 const_iterator cbegin() const noexcept;
107 const_iterator cend() const noexcept;
108 const_reverse_iterator crbegin() const noexcept;
109 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000110
111 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000112 bool empty() const noexcept;
113 size_type size() const noexcept;
114 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000115
116 // element access:
117 mapped_type& operator[](const key_type& k);
118 mapped_type& operator[](key_type&& k);
119
120 mapped_type& at(const key_type& k);
121 const mapped_type& at(const key_type& k) const;
122
123 // modifiers:
124 template <class... Args>
125 pair<iterator, bool> emplace(Args&&... args);
126 template <class... Args>
127 iterator emplace_hint(const_iterator position, Args&&... args);
128 pair<iterator, bool> insert(const value_type& v);
129 template <class P>
130 pair<iterator, bool> insert(P&& p);
131 iterator insert(const_iterator position, const value_type& v);
132 template <class P>
133 iterator insert(const_iterator position, P&& p);
134 template <class InputIterator>
135 void insert(InputIterator first, InputIterator last);
136 void insert(initializer_list<value_type> il);
137
138 iterator erase(const_iterator position);
139 size_type erase(const key_type& k);
140 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000141 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000142
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000143 void swap(map& m)
144 noexcept(
145 __is_nothrow_swappable<key_compare>::value &&
146 (!allocator_type::propagate_on_container_swap::value ||
147 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000148
149 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000150 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000151 key_compare key_comp() const;
152 value_compare value_comp() const;
153
154 // map operations:
155 iterator find(const key_type& k);
156 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000157 template<typename K>
158 iterator find(const K& x); // C++14
159 template<typename K>
160 const_iterator find(const K& x) const; // C++14
161 template<typename K>
162 size_type count(const K& x) const;
163
Howard Hinnantc51e1022010-05-11 19:42:16 +0000164 size_type count(const key_type& k) const;
165 iterator lower_bound(const key_type& k);
166 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000167 template<typename K>
168 iterator lower_bound(const K& x); // C++14
169 template<typename K>
170 const_iterator lower_bound(const K& x) const; // C++14
171
Howard Hinnantc51e1022010-05-11 19:42:16 +0000172 iterator upper_bound(const key_type& k);
173 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000174 template<typename K>
175 iterator upper_bound(const K& x); // C++14
176 template<typename K>
177 const_iterator upper_bound(const K& x) const; // C++14
178
Howard Hinnantc51e1022010-05-11 19:42:16 +0000179 pair<iterator,iterator> equal_range(const key_type& k);
180 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000181 template<typename K>
182 pair<iterator,iterator> equal_range(const K& x); // C++14
183 template<typename K>
184 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000185};
186
187template <class Key, class T, class Compare, class Allocator>
188bool
189operator==(const map<Key, T, Compare, Allocator>& x,
190 const map<Key, T, Compare, Allocator>& y);
191
192template <class Key, class T, class Compare, class Allocator>
193bool
194operator< (const map<Key, T, Compare, Allocator>& x,
195 const map<Key, T, Compare, Allocator>& y);
196
197template <class Key, class T, class Compare, class Allocator>
198bool
199operator!=(const map<Key, T, Compare, Allocator>& x,
200 const map<Key, T, Compare, Allocator>& y);
201
202template <class Key, class T, class Compare, class Allocator>
203bool
204operator> (const map<Key, T, Compare, Allocator>& x,
205 const map<Key, T, Compare, Allocator>& y);
206
207template <class Key, class T, class Compare, class Allocator>
208bool
209operator>=(const map<Key, T, Compare, Allocator>& x,
210 const map<Key, T, Compare, Allocator>& y);
211
212template <class Key, class T, class Compare, class Allocator>
213bool
214operator<=(const map<Key, T, Compare, Allocator>& x,
215 const map<Key, T, Compare, Allocator>& y);
216
217// specialized algorithms:
218template <class Key, class T, class Compare, class Allocator>
219void
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000220swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
221 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000222
223template <class Key, class T, class Compare = less<Key>,
224 class Allocator = allocator<pair<const Key, T>>>
225class multimap
226{
227public:
228 // types:
229 typedef Key key_type;
230 typedef T mapped_type;
231 typedef pair<const key_type,mapped_type> value_type;
232 typedef Compare key_compare;
233 typedef Allocator allocator_type;
234 typedef typename allocator_type::reference reference;
235 typedef typename allocator_type::const_reference const_reference;
236 typedef typename allocator_type::size_type size_type;
237 typedef typename allocator_type::difference_type difference_type;
238 typedef typename allocator_type::pointer pointer;
239 typedef typename allocator_type::const_pointer const_pointer;
240
241 typedef implementation-defined iterator;
242 typedef implementation-defined const_iterator;
243 typedef std::reverse_iterator<iterator> reverse_iterator;
244 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
245
246 class value_compare
247 : public binary_function<value_type,value_type,bool>
248 {
249 friend class multimap;
250 protected:
251 key_compare comp;
252 value_compare(key_compare c);
253 public:
254 bool operator()(const value_type& x, const value_type& y) const;
255 };
256
257 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000258 multimap()
259 noexcept(
260 is_nothrow_default_constructible<allocator_type>::value &&
261 is_nothrow_default_constructible<key_compare>::value &&
262 is_nothrow_copy_constructible<key_compare>::value);
263 explicit multimap(const key_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000264 multimap(const key_compare& comp, const allocator_type& a);
265 template <class InputIterator>
266 multimap(InputIterator first, InputIterator last, const key_compare& comp);
267 template <class InputIterator>
268 multimap(InputIterator first, InputIterator last, const key_compare& comp,
269 const allocator_type& a);
270 multimap(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000271 multimap(multimap&& m)
272 noexcept(
273 is_nothrow_move_constructible<allocator_type>::value &&
274 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000275 explicit multimap(const allocator_type& a);
276 multimap(const multimap& m, const allocator_type& a);
277 multimap(multimap&& m, const allocator_type& a);
278 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
279 multimap(initializer_list<value_type> il, const key_compare& comp,
280 const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +0000281 template <class InputIterator>
282 multimap(InputIterator first, InputIterator last, const allocator_type& a)
283 : multimap(first, last, Compare(), a) {} // C++14
284 multimap(initializer_list<value_type> il, const allocator_type& a)
285 : multimap(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000286 ~multimap();
287
288 multimap& operator=(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000289 multimap& operator=(multimap&& m)
290 noexcept(
291 allocator_type::propagate_on_container_move_assignment::value &&
292 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000293 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000294 multimap& operator=(initializer_list<value_type> il);
295
296 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000297 iterator begin() noexcept;
298 const_iterator begin() const noexcept;
299 iterator end() noexcept;
300 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000301
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000302 reverse_iterator rbegin() noexcept;
303 const_reverse_iterator rbegin() const noexcept;
304 reverse_iterator rend() noexcept;
305 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000306
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000307 const_iterator cbegin() const noexcept;
308 const_iterator cend() const noexcept;
309 const_reverse_iterator crbegin() const noexcept;
310 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000311
312 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000313 bool empty() const noexcept;
314 size_type size() const noexcept;
315 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000316
317 // modifiers:
318 template <class... Args>
319 iterator emplace(Args&&... args);
320 template <class... Args>
321 iterator emplace_hint(const_iterator position, Args&&... args);
322 iterator insert(const value_type& v);
323 template <class P>
324 iterator insert(P&& p);
325 iterator insert(const_iterator position, const value_type& v);
326 template <class P>
327 iterator insert(const_iterator position, P&& p);
328 template <class InputIterator>
329 void insert(InputIterator first, InputIterator last);
330 void insert(initializer_list<value_type> il);
331
332 iterator erase(const_iterator position);
333 size_type erase(const key_type& k);
334 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000335 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000336
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000337 void swap(multimap& m)
338 noexcept(
339 __is_nothrow_swappable<key_compare>::value &&
340 (!allocator_type::propagate_on_container_swap::value ||
341 __is_nothrow_swappable<allocator_type>::value));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000342
343 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000344 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000345 key_compare key_comp() const;
346 value_compare value_comp() const;
347
348 // map operations:
349 iterator find(const key_type& k);
350 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000351 template<typename K>
352 iterator find(const K& x); // C++14
353 template<typename K>
354 const_iterator find(const K& x) const; // C++14
355 template<typename K>
356 size_type count(const K& x) const;
357
Howard Hinnantc51e1022010-05-11 19:42:16 +0000358 size_type count(const key_type& k) const;
359 iterator lower_bound(const key_type& k);
360 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000361 template<typename K>
362 iterator lower_bound(const K& x); // C++14
363 template<typename K>
364 const_iterator lower_bound(const K& x) const; // C++14
365
Howard Hinnantc51e1022010-05-11 19:42:16 +0000366 iterator upper_bound(const key_type& k);
367 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000368 template<typename K>
369 iterator upper_bound(const K& x); // C++14
370 template<typename K>
371 const_iterator upper_bound(const K& x) const; // C++14
372
Howard Hinnantc51e1022010-05-11 19:42:16 +0000373 pair<iterator,iterator> equal_range(const key_type& k);
374 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000375 template<typename K>
376 pair<iterator,iterator> equal_range(const K& x); // C++14
377 template<typename K>
378 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000379};
380
381template <class Key, class T, class Compare, class Allocator>
382bool
383operator==(const multimap<Key, T, Compare, Allocator>& x,
384 const multimap<Key, T, Compare, Allocator>& y);
385
386template <class Key, class T, class Compare, class Allocator>
387bool
388operator< (const multimap<Key, T, Compare, Allocator>& x,
389 const multimap<Key, T, Compare, Allocator>& y);
390
391template <class Key, class T, class Compare, class Allocator>
392bool
393operator!=(const multimap<Key, T, Compare, Allocator>& x,
394 const multimap<Key, T, Compare, Allocator>& y);
395
396template <class Key, class T, class Compare, class Allocator>
397bool
398operator> (const multimap<Key, T, Compare, Allocator>& x,
399 const multimap<Key, T, Compare, Allocator>& y);
400
401template <class Key, class T, class Compare, class Allocator>
402bool
403operator>=(const multimap<Key, T, Compare, Allocator>& x,
404 const multimap<Key, T, Compare, Allocator>& y);
405
406template <class Key, class T, class Compare, class Allocator>
407bool
408operator<=(const multimap<Key, T, Compare, Allocator>& x,
409 const multimap<Key, T, Compare, Allocator>& y);
410
411// specialized algorithms:
412template <class Key, class T, class Compare, class Allocator>
413void
414swap(multimap<Key, T, Compare, Allocator>& x,
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000415 multimap<Key, T, Compare, Allocator>& y)
416 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000417
418} // std
419
420*/
421
422#include <__config>
423#include <__tree>
424#include <iterator>
425#include <memory>
426#include <utility>
427#include <functional>
428#include <initializer_list>
429
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000430#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000431#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000432#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000433
434_LIBCPP_BEGIN_NAMESPACE_STD
435
Howard Hinnant90b91592013-07-05 18:06:00 +0000436template <class _Key, class _CP, class _Compare, bool = is_empty<_Compare>::value
Howard Hinnantd0aabf82011-12-11 20:31:33 +0000437#if __has_feature(is_final)
438 && !__is_final(_Compare)
439#endif
440 >
Howard Hinnantc51e1022010-05-11 19:42:16 +0000441class __map_value_compare
442 : private _Compare
443{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000444public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000445 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000446 __map_value_compare()
447 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
448 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000449 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000450 __map_value_compare(_Compare c)
451 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
452 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000453 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000454 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000456 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000457 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000458 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000459 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000460 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000462 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000463 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000464
465#if _LIBCPP_STD_VER > 11
466 template <typename _K2>
467 _LIBCPP_INLINE_VISIBILITY
468 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
469 operator () ( const _K2& __x, const _CP& __y ) const
470 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
471
472 template <typename _K2>
473 _LIBCPP_INLINE_VISIBILITY
474 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
475 operator () (const _CP& __x, const _K2& __y) const
476 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
477#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000478};
479
Howard Hinnant90b91592013-07-05 18:06:00 +0000480template <class _Key, class _CP, class _Compare>
481class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000482{
483 _Compare comp;
484
Howard Hinnantc51e1022010-05-11 19:42:16 +0000485public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000486 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000487 __map_value_compare()
488 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
489 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000490 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000491 __map_value_compare(_Compare c)
492 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
493 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000494 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000495 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000496
Howard Hinnant756c69b2010-09-22 16:48:34 +0000497 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000498 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000499 {return comp(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000500 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000501 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000502 {return comp(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000503 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000504 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000505 {return comp(__x, __y.__cc.first);}
Marshall Clowebb57322013-08-13 22:18:47 +0000506
507#if _LIBCPP_STD_VER > 11
508 template <typename _K2>
509 _LIBCPP_INLINE_VISIBILITY
510 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
511 operator () ( const _K2& __x, const _CP& __y ) const
512 {return comp (__x, __y.__cc.first);}
513
514 template <typename _K2>
515 _LIBCPP_INLINE_VISIBILITY
516 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
517 operator () (const _CP& __x, const _K2& __y) const
518 {return comp (__x.__cc.first, __y);}
519#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000520};
521
522template <class _Allocator>
523class __map_node_destructor
524{
525 typedef _Allocator allocator_type;
526 typedef allocator_traits<allocator_type> __alloc_traits;
527 typedef typename __alloc_traits::value_type::value_type value_type;
528public:
529 typedef typename __alloc_traits::pointer pointer;
530private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000531 typedef typename value_type::value_type::first_type first_type;
532 typedef typename value_type::value_type::second_type second_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000533
534 allocator_type& __na_;
535
536 __map_node_destructor& operator=(const __map_node_destructor&);
537
538public:
539 bool __first_constructed;
540 bool __second_constructed;
541
Howard Hinnant756c69b2010-09-22 16:48:34 +0000542 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000543 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000544 : __na_(__na),
545 __first_constructed(false),
546 __second_constructed(false)
547 {}
548
Howard Hinnant74279a52010-09-04 23:28:19 +0000549#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant756c69b2010-09-22 16:48:34 +0000550 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000551 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000552 : __na_(__x.__na_),
553 __first_constructed(__x.__value_constructed),
554 __second_constructed(__x.__value_constructed)
555 {
556 __x.__value_constructed = false;
557 }
Howard Hinnant5dc89112010-09-04 23:46:48 +0000558#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000559
Howard Hinnant756c69b2010-09-22 16:48:34 +0000560 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000561 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000562 {
563 if (__second_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000564 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000565 if (__first_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000566 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000567 if (__p)
568 __alloc_traits::deallocate(__na_, __p, 1);
569 }
570};
571
Howard Hinnant944510a2011-06-14 19:58:17 +0000572template <class _Key, class _Tp, class _Compare, class _Allocator>
573 class map;
574template <class _Key, class _Tp, class _Compare, class _Allocator>
575 class multimap;
576template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000577
Howard Hinnant89f8b792013-09-30 19:08:22 +0000578#if __cplusplus >= 201103L
579
580template <class _Key, class _Tp>
581union __value_type
582{
583 typedef _Key key_type;
584 typedef _Tp mapped_type;
585 typedef pair<const key_type, mapped_type> value_type;
586 typedef pair<key_type, mapped_type> __nc_value_type;
587
588 value_type __cc;
589 __nc_value_type __nc;
590
591 template <class ..._Args>
592 _LIBCPP_INLINE_VISIBILITY
593 __value_type(_Args&& ...__args)
594 : __cc(std::forward<_Args>(__args)...) {}
595
596 _LIBCPP_INLINE_VISIBILITY
597 __value_type(const __value_type& __v)
598 : __cc(__v.__cc) {}
599
600 _LIBCPP_INLINE_VISIBILITY
601 __value_type(__value_type& __v)
602 : __cc(__v.__cc) {}
603
604 _LIBCPP_INLINE_VISIBILITY
605 __value_type(__value_type&& __v)
606 : __nc(std::move(__v.__nc)) {}
607
608 _LIBCPP_INLINE_VISIBILITY
609 __value_type& operator=(const __value_type& __v)
610 {__nc = __v.__cc; return *this;}
611
612 _LIBCPP_INLINE_VISIBILITY
613 __value_type& operator=(__value_type&& __v)
614 {__nc = std::move(__v.__nc); return *this;}
615
616 _LIBCPP_INLINE_VISIBILITY
617 ~__value_type() {__cc.~value_type();}
618};
619
620#else
621
622template <class _Key, class _Tp>
623struct __value_type
624{
625 typedef _Key key_type;
626 typedef _Tp mapped_type;
627 typedef pair<const key_type, mapped_type> value_type;
628
629 value_type __cc;
630
631 _LIBCPP_INLINE_VISIBILITY
632 __value_type() {}
633
634 template <class _A0>
635 _LIBCPP_INLINE_VISIBILITY
636 __value_type(const _A0& __a0)
637 : __cc(__a0) {}
638
639 template <class _A0, class _A1>
640 _LIBCPP_INLINE_VISIBILITY
641 __value_type(const _A0& __a0, const _A1& __a1)
642 : __cc(__a0, __a1) {}
643};
644
645#endif
646
Howard Hinnantc51e1022010-05-11 19:42:16 +0000647template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000648class _LIBCPP_TYPE_VIS_ONLY __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000649{
650 _TreeIterator __i_;
651
652 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000653 typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
654 typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000655public:
656 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000657 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000658 typedef typename _TreeIterator::difference_type difference_type;
659 typedef value_type& reference;
660 typedef typename __pointer_traits::template
661#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
662 rebind<value_type>
663#else
664 rebind<value_type>::other
665#endif
666 pointer;
667
Howard Hinnant756c69b2010-09-22 16:48:34 +0000668 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000669 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000670
Howard Hinnant756c69b2010-09-22 16:48:34 +0000671 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000672 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000673
Howard Hinnant756c69b2010-09-22 16:48:34 +0000674 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000675 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000676 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000677 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000678
Howard Hinnant756c69b2010-09-22 16:48:34 +0000679 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000680 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000681 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000682 __map_iterator operator++(int)
683 {
684 __map_iterator __t(*this);
685 ++(*this);
686 return __t;
687 }
688
Howard Hinnant756c69b2010-09-22 16:48:34 +0000689 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000690 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000691 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000692 __map_iterator operator--(int)
693 {
694 __map_iterator __t(*this);
695 --(*this);
696 return __t;
697 }
698
Howard Hinnant756c69b2010-09-22 16:48:34 +0000699 friend _LIBCPP_INLINE_VISIBILITY
700 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000701 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000702 friend
703 _LIBCPP_INLINE_VISIBILITY
704 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000705 {return __x.__i_ != __y.__i_;}
706
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000707 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
708 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
709 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000710};
711
712template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000713class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000714{
715 _TreeIterator __i_;
716
717 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000718 typedef const typename _TreeIterator::value_type::value_type::first_type __key_type;
719 typedef typename _TreeIterator::value_type::value_type::second_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000720public:
721 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000722 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000723 typedef typename _TreeIterator::difference_type difference_type;
724 typedef const value_type& reference;
725 typedef typename __pointer_traits::template
726#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000727 rebind<const value_type>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000728#else
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000729 rebind<const value_type>::other
Howard Hinnantc51e1022010-05-11 19:42:16 +0000730#endif
731 pointer;
732
Howard Hinnant756c69b2010-09-22 16:48:34 +0000733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000734 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735
Howard Hinnant756c69b2010-09-22 16:48:34 +0000736 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000737 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000739 __map_const_iterator(
740 __map_iterator<typename _TreeIterator::__non_const_iterator> __i)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000741 _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000742 : __i_(__i.__i_) {}
743
Howard Hinnant756c69b2010-09-22 16:48:34 +0000744 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000745 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000746 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000747 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000748
Howard Hinnant756c69b2010-09-22 16:48:34 +0000749 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000750 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000752 __map_const_iterator operator++(int)
753 {
754 __map_const_iterator __t(*this);
755 ++(*this);
756 return __t;
757 }
758
Howard Hinnant756c69b2010-09-22 16:48:34 +0000759 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000760 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000762 __map_const_iterator operator--(int)
763 {
764 __map_const_iterator __t(*this);
765 --(*this);
766 return __t;
767 }
768
Howard Hinnant756c69b2010-09-22 16:48:34 +0000769 friend _LIBCPP_INLINE_VISIBILITY
770 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000772 friend _LIBCPP_INLINE_VISIBILITY
773 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000774 {return __x.__i_ != __y.__i_;}
775
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000776 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
777 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
778 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000779};
780
781template <class _Key, class _Tp, class _Compare = less<_Key>,
782 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000783class _LIBCPP_TYPE_VIS_ONLY map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784{
785public:
786 // types:
787 typedef _Key key_type;
788 typedef _Tp mapped_type;
789 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000790 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000791 typedef _Compare key_compare;
792 typedef _Allocator allocator_type;
793 typedef value_type& reference;
794 typedef const value_type& const_reference;
795
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000796 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000797 : public binary_function<value_type, value_type, bool>
798 {
799 friend class map;
800 protected:
801 key_compare comp;
802
Howard Hinnant756c69b2010-09-22 16:48:34 +0000803 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000804 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000806 bool operator()(const value_type& __x, const value_type& __y) const
807 {return comp(__x.first, __y.first);}
808 };
809
810private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000811
Howard Hinnant89f8b792013-09-30 19:08:22 +0000812 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000813 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000814 typedef typename allocator_traits<allocator_type>::template
815#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
816 rebind_alloc<__value_type>
817#else
818 rebind_alloc<__value_type>::other
819#endif
820 __allocator_type;
821 typedef __tree<__value_type, __vc, __allocator_type> __base;
822 typedef typename __base::__node_traits __node_traits;
823 typedef allocator_traits<allocator_type> __alloc_traits;
824
825 __base __tree_;
826
827public:
828 typedef typename __alloc_traits::pointer pointer;
829 typedef typename __alloc_traits::const_pointer const_pointer;
830 typedef typename __alloc_traits::size_type size_type;
831 typedef typename __alloc_traits::difference_type difference_type;
832 typedef __map_iterator<typename __base::iterator> iterator;
833 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000834 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
835 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000836
Howard Hinnant756c69b2010-09-22 16:48:34 +0000837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000838 explicit map(const key_compare& __comp = key_compare())
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000839 _NOEXCEPT_(
840 is_nothrow_default_constructible<allocator_type>::value &&
841 is_nothrow_default_constructible<key_compare>::value &&
842 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000843 : __tree_(__vc(__comp)) {}
844
Howard Hinnant756c69b2010-09-22 16:48:34 +0000845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000846 explicit map(const key_compare& __comp, const allocator_type& __a)
847 : __tree_(__vc(__comp), __a) {}
848
849 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000850 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000851 map(_InputIterator __f, _InputIterator __l,
852 const key_compare& __comp = key_compare())
853 : __tree_(__vc(__comp))
854 {
855 insert(__f, __l);
856 }
857
858 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000859 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000860 map(_InputIterator __f, _InputIterator __l,
861 const key_compare& __comp, const allocator_type& __a)
862 : __tree_(__vc(__comp), __a)
863 {
864 insert(__f, __l);
865 }
866
Marshall Clow300abfb2013-09-11 01:15:47 +0000867#if _LIBCPP_STD_VER > 11
868 template <class _InputIterator>
869 _LIBCPP_INLINE_VISIBILITY
870 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
871 : map(__f, __l, key_compare(), __a) {}
872#endif
873
Howard Hinnant756c69b2010-09-22 16:48:34 +0000874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000875 map(const map& __m)
876 : __tree_(__m.__tree_)
877 {
878 insert(__m.begin(), __m.end());
879 }
880
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000881 _LIBCPP_INLINE_VISIBILITY
882 map& operator=(const map& __m)
883 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000884#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000885 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000886#else
887 __tree_.clear();
888 __tree_.value_comp() = __m.__tree_.value_comp();
889 __tree_.__copy_assign_alloc(__m.__tree_);
890 insert(__m.begin(), __m.end());
891#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000892 return *this;
893 }
894
Howard Hinnant74279a52010-09-04 23:28:19 +0000895#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000896
Howard Hinnant756c69b2010-09-22 16:48:34 +0000897 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000898 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000899 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000900 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000901 {
902 }
903
904 map(map&& __m, const allocator_type& __a);
905
Howard Hinnant756c69b2010-09-22 16:48:34 +0000906 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +0000907 map& operator=(map&& __m)
908 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
909 {
910 __tree_ = _VSTD::move(__m.__tree_);
911 return *this;
912 }
913
914#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
915
916#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
917
918 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000919 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
920 : __tree_(__vc(__comp))
921 {
922 insert(__il.begin(), __il.end());
923 }
924
Howard Hinnant756c69b2010-09-22 16:48:34 +0000925 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000926 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
927 : __tree_(__vc(__comp), __a)
928 {
929 insert(__il.begin(), __il.end());
930 }
931
Marshall Clow300abfb2013-09-11 01:15:47 +0000932#if _LIBCPP_STD_VER > 11
933 _LIBCPP_INLINE_VISIBILITY
934 map(initializer_list<value_type> __il, const allocator_type& __a)
935 : map(__il, key_compare(), __a) {}
936#endif
937
Howard Hinnant756c69b2010-09-22 16:48:34 +0000938 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000939 map& operator=(initializer_list<value_type> __il)
940 {
941 __tree_.__assign_unique(__il.begin(), __il.end());
942 return *this;
943 }
944
Howard Hinnant33711792011-08-12 21:56:02 +0000945#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +0000946
Howard Hinnant756c69b2010-09-22 16:48:34 +0000947 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000948 explicit map(const allocator_type& __a)
949 : __tree_(__a)
950 {
951 }
952
Howard Hinnant756c69b2010-09-22 16:48:34 +0000953 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000954 map(const map& __m, const allocator_type& __a)
955 : __tree_(__m.__tree_.value_comp(), __a)
956 {
957 insert(__m.begin(), __m.end());
958 }
959
Howard Hinnant756c69b2010-09-22 16:48:34 +0000960 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000961 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000962 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000963 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000964 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000965 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000966 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000967 const_iterator end() const _NOEXCEPT {return __tree_.end();}
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 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000971 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000972 const_reverse_iterator rbegin() const _NOEXCEPT
973 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000974 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000975 reverse_iterator rend() _NOEXCEPT
976 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000977 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000978 const_reverse_iterator rend() const _NOEXCEPT
979 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000980
Howard Hinnant756c69b2010-09-22 16:48:34 +0000981 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000982 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000983 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000984 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000985 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000986 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000988 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000989
Howard Hinnant756c69b2010-09-22 16:48:34 +0000990 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000991 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000992 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000993 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000995 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000996
997 mapped_type& operator[](const key_type& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +0000998#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000999 mapped_type& operator[](key_type&& __k);
1000#endif
1001
1002 mapped_type& at(const key_type& __k);
1003 const mapped_type& at(const key_type& __k) const;
1004
Howard Hinnant756c69b2010-09-22 16:48:34 +00001005 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001006 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001007 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001008 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001009 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001010 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1011
Howard Hinnant74279a52010-09-04 23:28:19 +00001012#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant74279a52010-09-04 23:28:19 +00001013#ifndef _LIBCPP_HAS_NO_VARIADICS
1014
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001015 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016 pair<iterator, bool>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001017 emplace(_Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001018
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001019 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001020 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001021 emplace_hint(const_iterator __p, _Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001022
Howard Hinnant74279a52010-09-04 23:28:19 +00001023#endif // _LIBCPP_HAS_NO_VARIADICS
1024
Howard Hinnantc834c512011-11-29 18:15:50 +00001025 template <class _Pp,
1026 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001027 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001028 pair<iterator, bool> insert(_Pp&& __p)
1029 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001030
Howard Hinnantc834c512011-11-29 18:15:50 +00001031 template <class _Pp,
1032 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001033 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001034 iterator insert(const_iterator __pos, _Pp&& __p)
1035 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001036
Howard Hinnant74279a52010-09-04 23:28:19 +00001037#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001038
Howard Hinnant756c69b2010-09-22 16:48:34 +00001039 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001040 pair<iterator, bool>
1041 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1042
Howard Hinnant756c69b2010-09-22 16:48:34 +00001043 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001044 iterator
1045 insert(const_iterator __p, const value_type& __v)
1046 {return __tree_.__insert_unique(__p.__i_, __v);}
1047
1048 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001049 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001050 void insert(_InputIterator __f, _InputIterator __l)
1051 {
1052 for (const_iterator __e = cend(); __f != __l; ++__f)
1053 insert(__e.__i_, *__f);
1054 }
1055
Howard Hinnant33711792011-08-12 21:56:02 +00001056#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1057
Howard Hinnant756c69b2010-09-22 16:48:34 +00001058 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001059 void insert(initializer_list<value_type> __il)
1060 {insert(__il.begin(), __il.end());}
1061
Howard Hinnant33711792011-08-12 21:56:02 +00001062#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1063
Howard Hinnant756c69b2010-09-22 16:48:34 +00001064 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001065 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001066 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001067 size_type erase(const key_type& __k)
1068 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001069 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001070 iterator erase(const_iterator __f, const_iterator __l)
1071 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001072 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001073 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001074
Howard Hinnant756c69b2010-09-22 16:48:34 +00001075 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001076 void swap(map& __m)
1077 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1078 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001079
Howard Hinnant756c69b2010-09-22 16:48:34 +00001080 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001081 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001082 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001083 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001084#if _LIBCPP_STD_VER > 11
1085 template <typename _K2>
1086 _LIBCPP_INLINE_VISIBILITY
1087 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1088 find(const _K2& __k) {return __tree_.find(__k);}
1089 template <typename _K2>
1090 _LIBCPP_INLINE_VISIBILITY
1091 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1092 find(const _K2& __k) const {return __tree_.find(__k);}
1093#endif
1094
Howard Hinnant756c69b2010-09-22 16:48:34 +00001095 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001096 size_type count(const key_type& __k) const
1097 {return __tree_.__count_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001098 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001099 iterator lower_bound(const key_type& __k)
1100 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001101 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 const_iterator lower_bound(const key_type& __k) const
1103 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001104#if _LIBCPP_STD_VER > 11
1105 template <typename _K2>
1106 _LIBCPP_INLINE_VISIBILITY
1107 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1108 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1109
1110 template <typename _K2>
1111 _LIBCPP_INLINE_VISIBILITY
1112 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1113 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1114#endif
1115
Howard Hinnant756c69b2010-09-22 16:48:34 +00001116 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001117 iterator upper_bound(const key_type& __k)
1118 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001119 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001120 const_iterator upper_bound(const key_type& __k) const
1121 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001122#if _LIBCPP_STD_VER > 11
1123 template <typename _K2>
1124 _LIBCPP_INLINE_VISIBILITY
1125 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1126 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1127 template <typename _K2>
1128 _LIBCPP_INLINE_VISIBILITY
1129 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1130 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1131#endif
1132
Howard Hinnant756c69b2010-09-22 16:48:34 +00001133 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001134 pair<iterator,iterator> equal_range(const key_type& __k)
1135 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001136 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001137 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1138 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001139#if _LIBCPP_STD_VER > 11
1140 template <typename _K2>
1141 _LIBCPP_INLINE_VISIBILITY
1142 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1143 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1144 template <typename _K2>
1145 _LIBCPP_INLINE_VISIBILITY
1146 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1147 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1148#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001149
1150private:
1151 typedef typename __base::__node __node;
1152 typedef typename __base::__node_allocator __node_allocator;
1153 typedef typename __base::__node_pointer __node_pointer;
1154 typedef typename __base::__node_const_pointer __node_const_pointer;
1155 typedef typename __base::__node_base_pointer __node_base_pointer;
1156 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
Howard Hinnantc834c512011-11-29 18:15:50 +00001157 typedef __map_node_destructor<__node_allocator> _Dp;
1158 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001159
Howard Hinnant74279a52010-09-04 23:28:19 +00001160#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001161 __node_holder __construct_node();
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001162 template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001163 __node_holder __construct_node(_A0&& __a0);
1164 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +00001165#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001166 template <class _A0, class _A1, class ..._Args>
1167 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001168#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001169#endif
Howard Hinnantac7e7482013-07-04 20:59:16 +00001170 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001171
1172 __node_base_pointer&
1173 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001174 __node_base_const_pointer
1175 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1176};
1177
1178// Find place to insert if __k doesn't exist
1179// Set __parent to parent of null leaf
1180// Return reference to null leaf
1181// If __k exists, set parent to node of __k and return reference to node of __k
1182template <class _Key, class _Tp, class _Compare, class _Allocator>
1183typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1184map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1185 const key_type& __k)
1186{
1187 __node_pointer __nd = __tree_.__root();
1188 if (__nd != nullptr)
1189 {
1190 while (true)
1191 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001192 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001193 {
1194 if (__nd->__left_ != nullptr)
1195 __nd = static_cast<__node_pointer>(__nd->__left_);
1196 else
1197 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001198 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001199 return __parent->__left_;
1200 }
1201 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001202 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203 {
1204 if (__nd->__right_ != nullptr)
1205 __nd = static_cast<__node_pointer>(__nd->__right_);
1206 else
1207 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001208 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001209 return __parent->__right_;
1210 }
1211 }
1212 else
1213 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001214 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001215 return __parent;
1216 }
1217 }
1218 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001219 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001220 return __parent->__left_;
1221}
1222
Howard Hinnantc51e1022010-05-11 19:42:16 +00001223// Find __k
1224// Set __parent to parent of null leaf and
1225// return reference to null leaf iv __k does not exist.
1226// If __k exists, set parent to node of __k and return reference to node of __k
1227template <class _Key, class _Tp, class _Compare, class _Allocator>
1228typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1229map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1230 const key_type& __k) const
1231{
1232 __node_const_pointer __nd = __tree_.__root();
1233 if (__nd != nullptr)
1234 {
1235 while (true)
1236 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001237 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001238 {
1239 if (__nd->__left_ != nullptr)
1240 __nd = static_cast<__node_pointer>(__nd->__left_);
1241 else
1242 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001243 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001244 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1245 }
1246 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001247 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001248 {
1249 if (__nd->__right_ != nullptr)
1250 __nd = static_cast<__node_pointer>(__nd->__right_);
1251 else
1252 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001253 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001254 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1255 }
1256 }
1257 else
1258 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001259 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001260 return __parent;
1261 }
1262 }
1263 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001264 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001265 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1266}
1267
Howard Hinnant74279a52010-09-04 23:28:19 +00001268#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001269
1270template <class _Key, class _Tp, class _Compare, class _Allocator>
1271map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001272 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001273{
1274 if (__a != __m.get_allocator())
1275 {
1276 const_iterator __e = cend();
1277 while (!__m.empty())
1278 __tree_.__insert_unique(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001279 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001280 }
1281}
1282
1283template <class _Key, class _Tp, class _Compare, class _Allocator>
1284typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1285map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1286{
1287 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001288 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001289 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001290 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001291 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001292 __h.get_deleter().__second_constructed = true;
1293 return __h;
1294}
1295
1296template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001297template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001298typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantc51e1022010-05-11 19:42:16 +00001299map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1300{
1301 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001302 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001303 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001304 __h.get_deleter().__first_constructed = true;
1305 __h.get_deleter().__second_constructed = true;
1306 return __h;
1307}
1308
1309template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001310typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1311map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001312{
1313 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001314 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantac7e7482013-07-04 20:59:16 +00001315 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001316 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001317 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001318 __h.get_deleter().__second_constructed = true;
Howard Hinnanta31e9682013-08-22 18:29:50 +00001319 return __h;
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001320}
1321
1322#ifndef _LIBCPP_HAS_NO_VARIADICS
1323
1324template <class _Key, class _Tp, class _Compare, class _Allocator>
1325template <class _A0, class _A1, class ..._Args>
1326typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1327map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1328{
1329 __node_allocator& __na = __tree_.__node_alloc();
1330 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1331 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1332 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1333 _VSTD::forward<_Args>(__args)...);
1334 __h.get_deleter().__first_constructed = true;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001335 __h.get_deleter().__second_constructed = true;
1336 return __h;
1337}
1338
Howard Hinnant74279a52010-09-04 23:28:19 +00001339#endif // _LIBCPP_HAS_NO_VARIADICS
1340
Howard Hinnantac7e7482013-07-04 20:59:16 +00001341#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001342
1343template <class _Key, class _Tp, class _Compare, class _Allocator>
1344typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001345map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001346{
1347 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001348 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001349 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001350 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001351 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001352 __h.get_deleter().__second_constructed = true;
Howard Hinnanta31e9682013-08-22 18:29:50 +00001353 return _VSTD::move(__h); // explicitly moved for C++03
Howard Hinnantc51e1022010-05-11 19:42:16 +00001354}
1355
Howard Hinnantc51e1022010-05-11 19:42:16 +00001356template <class _Key, class _Tp, class _Compare, class _Allocator>
1357_Tp&
1358map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1359{
1360 __node_base_pointer __parent;
1361 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1362 __node_pointer __r = static_cast<__node_pointer>(__child);
1363 if (__child == nullptr)
1364 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001365 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001366 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001367 __r = __h.release();
1368 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001369 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001370}
1371
Howard Hinnant74279a52010-09-04 23:28:19 +00001372#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001373
1374template <class _Key, class _Tp, class _Compare, class _Allocator>
1375_Tp&
1376map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1377{
1378 __node_base_pointer __parent;
1379 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1380 __node_pointer __r = static_cast<__node_pointer>(__child);
1381 if (__child == nullptr)
1382 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001383 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001384 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001385 __r = __h.release();
1386 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001387 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001388}
1389
Howard Hinnant74279a52010-09-04 23:28:19 +00001390#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001391
1392template <class _Key, class _Tp, class _Compare, class _Allocator>
1393_Tp&
1394map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1395{
1396 __node_base_pointer __parent;
1397 __node_base_pointer& __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001398#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001399 if (__child == nullptr)
1400 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001401#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001402 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001403}
1404
1405template <class _Key, class _Tp, class _Compare, class _Allocator>
1406const _Tp&
1407map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1408{
1409 __node_base_const_pointer __parent;
1410 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001411#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001412 if (__child == nullptr)
1413 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001414#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001415 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001416}
1417
Howard Hinnant74279a52010-09-04 23:28:19 +00001418#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001419
1420template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001421template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001422pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001423map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001424{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001425 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001426 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1427 if (__r.second)
1428 __h.release();
1429 return __r;
1430}
1431
1432template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001433template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001434typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1435map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001436 _Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001437{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001438 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001439 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1440 if (__r.__i_.__ptr_ == __h.get())
1441 __h.release();
1442 return __r;
1443}
1444
Howard Hinnant74279a52010-09-04 23:28:19 +00001445#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001446
1447template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001448inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001449bool
1450operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1451 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1452{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001453 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001454}
1455
1456template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001457inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001458bool
1459operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1460 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1461{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001462 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001463}
1464
1465template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001466inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001467bool
1468operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1469 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1470{
1471 return !(__x == __y);
1472}
1473
1474template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001475inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001476bool
1477operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1478 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1479{
1480 return __y < __x;
1481}
1482
1483template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001484inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001485bool
1486operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1487 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1488{
1489 return !(__x < __y);
1490}
1491
1492template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001493inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001494bool
1495operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1496 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1497{
1498 return !(__y < __x);
1499}
1500
1501template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001502inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001503void
1504swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1505 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001506 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001507{
1508 __x.swap(__y);
1509}
1510
1511template <class _Key, class _Tp, class _Compare = less<_Key>,
1512 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001513class _LIBCPP_TYPE_VIS_ONLY multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001514{
1515public:
1516 // types:
1517 typedef _Key key_type;
1518 typedef _Tp mapped_type;
1519 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001520 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001521 typedef _Compare key_compare;
1522 typedef _Allocator allocator_type;
1523 typedef value_type& reference;
1524 typedef const value_type& const_reference;
1525
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001526 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001527 : public binary_function<value_type, value_type, bool>
1528 {
1529 friend class multimap;
1530 protected:
1531 key_compare comp;
1532
Howard Hinnant756c69b2010-09-22 16:48:34 +00001533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001534 value_compare(key_compare c) : comp(c) {}
1535 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001536 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001537 bool operator()(const value_type& __x, const value_type& __y) const
1538 {return comp(__x.first, __y.first);}
1539 };
1540
1541private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001542
Howard Hinnant89f8b792013-09-30 19:08:22 +00001543 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001544 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001545 typedef typename allocator_traits<allocator_type>::template
1546#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1547 rebind_alloc<__value_type>
1548#else
1549 rebind_alloc<__value_type>::other
1550#endif
1551 __allocator_type;
1552 typedef __tree<__value_type, __vc, __allocator_type> __base;
1553 typedef typename __base::__node_traits __node_traits;
1554 typedef allocator_traits<allocator_type> __alloc_traits;
1555
1556 __base __tree_;
1557
1558public:
1559 typedef typename __alloc_traits::pointer pointer;
1560 typedef typename __alloc_traits::const_pointer const_pointer;
1561 typedef typename __alloc_traits::size_type size_type;
1562 typedef typename __alloc_traits::difference_type difference_type;
1563 typedef __map_iterator<typename __base::iterator> iterator;
1564 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001565 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1566 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
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 key_compare& __comp = key_compare())
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001570 _NOEXCEPT_(
1571 is_nothrow_default_constructible<allocator_type>::value &&
1572 is_nothrow_default_constructible<key_compare>::value &&
1573 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001574 : __tree_(__vc(__comp)) {}
1575
Howard Hinnant756c69b2010-09-22 16:48:34 +00001576 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001577 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1578 : __tree_(__vc(__comp), __a) {}
1579
1580 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001581 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001582 multimap(_InputIterator __f, _InputIterator __l,
1583 const key_compare& __comp = key_compare())
1584 : __tree_(__vc(__comp))
1585 {
1586 insert(__f, __l);
1587 }
1588
1589 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001590 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001591 multimap(_InputIterator __f, _InputIterator __l,
1592 const key_compare& __comp, const allocator_type& __a)
1593 : __tree_(__vc(__comp), __a)
1594 {
1595 insert(__f, __l);
1596 }
1597
Marshall Clow300abfb2013-09-11 01:15:47 +00001598#if _LIBCPP_STD_VER > 11
1599 template <class _InputIterator>
1600 _LIBCPP_INLINE_VISIBILITY
1601 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1602 : multimap(__f, __l, key_compare(), __a) {}
1603#endif
1604
Howard Hinnant756c69b2010-09-22 16:48:34 +00001605 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001606 multimap(const multimap& __m)
1607 : __tree_(__m.__tree_.value_comp(),
1608 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1609 {
1610 insert(__m.begin(), __m.end());
1611 }
1612
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001613 _LIBCPP_INLINE_VISIBILITY
1614 multimap& operator=(const multimap& __m)
1615 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001616#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001617 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001618#else
1619 __tree_.clear();
1620 __tree_.value_comp() = __m.__tree_.value_comp();
1621 __tree_.__copy_assign_alloc(__m.__tree_);
1622 insert(__m.begin(), __m.end());
1623#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001624 return *this;
1625 }
1626
Howard Hinnant74279a52010-09-04 23:28:19 +00001627#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001628
Howard Hinnant756c69b2010-09-22 16:48:34 +00001629 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001630 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001631 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001632 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001633 {
1634 }
1635
1636 multimap(multimap&& __m, const allocator_type& __a);
1637
Howard Hinnant756c69b2010-09-22 16:48:34 +00001638 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001639 multimap& operator=(multimap&& __m)
1640 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1641 {
1642 __tree_ = _VSTD::move(__m.__tree_);
1643 return *this;
1644 }
1645
1646#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1647
1648#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1649
1650 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001651 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1652 : __tree_(__vc(__comp))
1653 {
1654 insert(__il.begin(), __il.end());
1655 }
1656
Howard Hinnant756c69b2010-09-22 16:48:34 +00001657 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001658 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1659 : __tree_(__vc(__comp), __a)
1660 {
1661 insert(__il.begin(), __il.end());
1662 }
1663
Marshall Clow300abfb2013-09-11 01:15:47 +00001664#if _LIBCPP_STD_VER > 11
1665 _LIBCPP_INLINE_VISIBILITY
1666 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1667 : multimap(__il, key_compare(), __a) {}
1668#endif
1669
Howard Hinnant756c69b2010-09-22 16:48:34 +00001670 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001671 multimap& operator=(initializer_list<value_type> __il)
1672 {
1673 __tree_.__assign_multi(__il.begin(), __il.end());
1674 return *this;
1675 }
Howard Hinnant33711792011-08-12 21:56:02 +00001676
1677#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001678
Howard Hinnant756c69b2010-09-22 16:48:34 +00001679 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001680 explicit multimap(const allocator_type& __a)
1681 : __tree_(__a)
1682 {
1683 }
1684
Howard Hinnant756c69b2010-09-22 16:48:34 +00001685 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001686 multimap(const multimap& __m, const allocator_type& __a)
1687 : __tree_(__m.__tree_.value_comp(), __a)
1688 {
1689 insert(__m.begin(), __m.end());
1690 }
1691
Howard Hinnant756c69b2010-09-22 16:48:34 +00001692 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001693 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001694 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001695 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001696 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001697 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001698 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001699 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001700
Howard Hinnant756c69b2010-09-22 16:48:34 +00001701 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001702 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001703 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001704 const_reverse_iterator rbegin() const _NOEXCEPT
1705 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001706 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001707 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001708 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001709 const_reverse_iterator rend() const _NOEXCEPT
1710 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001711
Howard Hinnant756c69b2010-09-22 16:48:34 +00001712 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001713 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001714 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001715 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001716 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001717 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001719 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001720
Howard Hinnant756c69b2010-09-22 16:48:34 +00001721 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001722 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001723 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001724 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001726 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001727
Howard Hinnant756c69b2010-09-22 16:48:34 +00001728 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001729 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001730 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001731 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001732 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001733 value_compare value_comp() const
1734 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001735
Howard Hinnant74279a52010-09-04 23:28:19 +00001736#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant74279a52010-09-04 23:28:19 +00001737#ifndef _LIBCPP_HAS_NO_VARIADICS
1738
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001739 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001740 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001741 emplace(_Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001742
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001743 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001744 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001745 emplace_hint(const_iterator __p, _Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001746
Howard Hinnant74279a52010-09-04 23:28:19 +00001747#endif // _LIBCPP_HAS_NO_VARIADICS
1748
Howard Hinnantc834c512011-11-29 18:15:50 +00001749 template <class _Pp,
1750 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001752 iterator insert(_Pp&& __p)
1753 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001754
Howard Hinnantc834c512011-11-29 18:15:50 +00001755 template <class _Pp,
1756 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001757 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001758 iterator insert(const_iterator __pos, _Pp&& __p)
1759 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001760
Howard Hinnant74279a52010-09-04 23:28:19 +00001761#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001762
Howard Hinnant756c69b2010-09-22 16:48:34 +00001763 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001764 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1765
Howard Hinnant756c69b2010-09-22 16:48:34 +00001766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001767 iterator insert(const_iterator __p, const value_type& __v)
1768 {return __tree_.__insert_multi(__p.__i_, __v);}
1769
1770 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001771 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001772 void insert(_InputIterator __f, _InputIterator __l)
1773 {
1774 for (const_iterator __e = cend(); __f != __l; ++__f)
1775 __tree_.__insert_multi(__e.__i_, *__f);
1776 }
1777
Howard Hinnant33711792011-08-12 21:56:02 +00001778#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1779
Howard Hinnant756c69b2010-09-22 16:48:34 +00001780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001781 void insert(initializer_list<value_type> __il)
1782 {insert(__il.begin(), __il.end());}
1783
Howard Hinnant33711792011-08-12 21:56:02 +00001784#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1785
Howard Hinnant756c69b2010-09-22 16:48:34 +00001786 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001787 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001788 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001789 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001790 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001791 iterator erase(const_iterator __f, const_iterator __l)
1792 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001794 void clear() {__tree_.clear();}
1795
Howard Hinnant756c69b2010-09-22 16:48:34 +00001796 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001797 void swap(multimap& __m)
1798 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1799 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001800
Howard Hinnant756c69b2010-09-22 16:48:34 +00001801 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001802 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001803 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001804 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001805#if _LIBCPP_STD_VER > 11
1806 template <typename _K2>
1807 _LIBCPP_INLINE_VISIBILITY
1808 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1809 find(const _K2& __k) {return __tree_.find(__k);}
1810 template <typename _K2>
1811 _LIBCPP_INLINE_VISIBILITY
1812 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1813 find(const _K2& __k) const {return __tree_.find(__k);}
1814#endif
1815
Howard Hinnant756c69b2010-09-22 16:48:34 +00001816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001817 size_type count(const key_type& __k) const
1818 {return __tree_.__count_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001820 iterator lower_bound(const key_type& __k)
1821 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001822 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001823 const_iterator lower_bound(const key_type& __k) const
1824 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001825#if _LIBCPP_STD_VER > 11
1826 template <typename _K2>
1827 _LIBCPP_INLINE_VISIBILITY
1828 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1829 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1830
1831 template <typename _K2>
1832 _LIBCPP_INLINE_VISIBILITY
1833 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1834 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1835#endif
1836
Howard Hinnant756c69b2010-09-22 16:48:34 +00001837 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838 iterator upper_bound(const key_type& __k)
1839 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001840 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001841 const_iterator upper_bound(const key_type& __k) const
1842 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001843#if _LIBCPP_STD_VER > 11
1844 template <typename _K2>
1845 _LIBCPP_INLINE_VISIBILITY
1846 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1847 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1848 template <typename _K2>
1849 _LIBCPP_INLINE_VISIBILITY
1850 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1851 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1852#endif
1853
Howard Hinnant756c69b2010-09-22 16:48:34 +00001854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001855 pair<iterator,iterator> equal_range(const key_type& __k)
1856 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001857 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001858 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1859 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001860#if _LIBCPP_STD_VER > 11
1861 template <typename _K2>
1862 _LIBCPP_INLINE_VISIBILITY
1863 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1864 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1865 template <typename _K2>
1866 _LIBCPP_INLINE_VISIBILITY
1867 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1868 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1869#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001870
1871private:
1872 typedef typename __base::__node __node;
1873 typedef typename __base::__node_allocator __node_allocator;
1874 typedef typename __base::__node_pointer __node_pointer;
1875 typedef typename __base::__node_const_pointer __node_const_pointer;
Howard Hinnantc834c512011-11-29 18:15:50 +00001876 typedef __map_node_destructor<__node_allocator> _Dp;
1877 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001878
Howard Hinnant74279a52010-09-04 23:28:19 +00001879#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001880 __node_holder __construct_node();
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001881 template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001882 __node_holder
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001883 __construct_node(_A0&& __a0);
Howard Hinnant74279a52010-09-04 23:28:19 +00001884#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001885 template <class _A0, class _A1, class ..._Args>
1886 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001887#endif // _LIBCPP_HAS_NO_VARIADICS
1888#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001889};
1890
Howard Hinnant74279a52010-09-04 23:28:19 +00001891#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001892
1893template <class _Key, class _Tp, class _Compare, class _Allocator>
1894multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001895 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001896{
1897 if (__a != __m.get_allocator())
1898 {
1899 const_iterator __e = cend();
1900 while (!__m.empty())
1901 __tree_.__insert_multi(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001902 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001903 }
1904}
1905
1906template <class _Key, class _Tp, class _Compare, class _Allocator>
1907typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1908multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1909{
1910 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001911 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001912 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001913 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001914 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001915 __h.get_deleter().__second_constructed = true;
1916 return __h;
1917}
1918
1919template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001920template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001921typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantc51e1022010-05-11 19:42:16 +00001922multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1923{
1924 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001925 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001926 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001927 __h.get_deleter().__first_constructed = true;
1928 __h.get_deleter().__second_constructed = true;
1929 return __h;
1930}
1931
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001932#ifndef _LIBCPP_HAS_NO_VARIADICS
1933
1934template <class _Key, class _Tp, class _Compare, class _Allocator>
1935template <class _A0, class _A1, class ..._Args>
1936typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1937multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1938{
1939 __node_allocator& __na = __tree_.__node_alloc();
1940 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1941 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1942 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1943 _VSTD::forward<_Args>(__args)...);
1944 __h.get_deleter().__first_constructed = true;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001945 __h.get_deleter().__second_constructed = true;
1946 return __h;
1947}
1948
Howard Hinnant74279a52010-09-04 23:28:19 +00001949#endif // _LIBCPP_HAS_NO_VARIADICS
1950#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001951
Howard Hinnant74279a52010-09-04 23:28:19 +00001952#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001953
1954template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001955template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001956typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001957multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001958{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001959 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001960 iterator __r = __tree_.__node_insert_multi(__h.get());
1961 __h.release();
1962 return __r;
1963}
1964
1965template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001966template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001967typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
1968multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
Howard Hinnantc51e1022010-05-11 19:42:16 +00001969 _Args&& ...__args)
1970{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001971 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001972 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
1973 __h.release();
1974 return __r;
1975}
1976
Howard Hinnant74279a52010-09-04 23:28:19 +00001977#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001978
1979template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001980inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001981bool
1982operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1983 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1984{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001985 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001986}
1987
1988template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001989inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001990bool
1991operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1992 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1993{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001994 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001995}
1996
1997template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001998inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001999bool
2000operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2001 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2002{
2003 return !(__x == __y);
2004}
2005
2006template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002007inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002008bool
2009operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2010 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2011{
2012 return __y < __x;
2013}
2014
2015template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002016inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002017bool
2018operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2019 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2020{
2021 return !(__x < __y);
2022}
2023
2024template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002025inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002026bool
2027operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2028 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2029{
2030 return !(__y < __x);
2031}
2032
2033template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002034inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002035void
2036swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2037 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002038 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002039{
2040 __x.swap(__y);
2041}
2042
2043_LIBCPP_END_NAMESPACE_STD
2044
2045#endif // _LIBCPP_MAP