blob: 0b5eb209490f660c76470aff8fe3b5e86a7637fa [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>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000162 size_type count(const K& x) const; // C++14
Marshall Clowebb57322013-08-13 22:18:47 +0000163
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>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000356 size_type count(const K& x) const; // C++14
Marshall Clowebb57322013-08-13 22:18:47 +0000357
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
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000647template <class _Tp>
648struct __extract_key_value_types;
649
650template <class _Key, class _Tp>
651struct __extract_key_value_types<__value_type<_Key, _Tp> >
652{
653 typedef _Key const __key_type;
654 typedef _Tp __mapped_type;
655};
656
Howard Hinnantc51e1022010-05-11 19:42:16 +0000657template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000658class _LIBCPP_TYPE_VIS_ONLY __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000659{
660 _TreeIterator __i_;
661
662 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000663 typedef typename _TreeIterator::value_type __value_type;
664 typedef typename __extract_key_value_types<__value_type>::__key_type __key_type;
665 typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000666public:
667 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000668 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000669 typedef typename _TreeIterator::difference_type difference_type;
670 typedef value_type& reference;
671 typedef typename __pointer_traits::template
672#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
673 rebind<value_type>
674#else
675 rebind<value_type>::other
676#endif
677 pointer;
678
Howard Hinnant756c69b2010-09-22 16:48:34 +0000679 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000680 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000681
Howard Hinnant756c69b2010-09-22 16:48:34 +0000682 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000683 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000684
Howard Hinnant756c69b2010-09-22 16:48:34 +0000685 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000686 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000687 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000688 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000689
Howard Hinnant756c69b2010-09-22 16:48:34 +0000690 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000691 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000692 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000693 __map_iterator operator++(int)
694 {
695 __map_iterator __t(*this);
696 ++(*this);
697 return __t;
698 }
699
Howard Hinnant756c69b2010-09-22 16:48:34 +0000700 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000701 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000702 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000703 __map_iterator operator--(int)
704 {
705 __map_iterator __t(*this);
706 --(*this);
707 return __t;
708 }
709
Howard Hinnant756c69b2010-09-22 16:48:34 +0000710 friend _LIBCPP_INLINE_VISIBILITY
711 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000712 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000713 friend
714 _LIBCPP_INLINE_VISIBILITY
715 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000716 {return __x.__i_ != __y.__i_;}
717
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000718 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
719 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
720 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000721};
722
723template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000724class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000725{
726 _TreeIterator __i_;
727
728 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000729 typedef typename _TreeIterator::value_type __value_type;
730 typedef typename __extract_key_value_types<__value_type>::__key_type __key_type;
731 typedef typename __extract_key_value_types<__value_type>::__mapped_type __mapped_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000732public:
733 typedef bidirectional_iterator_tag iterator_category;
Howard Hinnantb2e8a422011-02-27 18:02:02 +0000734 typedef pair<__key_type, __mapped_type> value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000735 typedef typename _TreeIterator::difference_type difference_type;
736 typedef const value_type& reference;
737 typedef typename __pointer_traits::template
738#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000739 rebind<const value_type>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000740#else
Howard Hinnant73f3c8a2011-04-11 02:18:41 +0000741 rebind<const value_type>::other
Howard Hinnantc51e1022010-05-11 19:42:16 +0000742#endif
743 pointer;
744
Howard Hinnant756c69b2010-09-22 16:48:34 +0000745 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000746 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000747
Howard Hinnant756c69b2010-09-22 16:48:34 +0000748 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000749 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000750 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000751 __map_const_iterator(__map_iterator<
752 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
753 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000754
Howard Hinnant756c69b2010-09-22 16:48:34 +0000755 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000756 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000757 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000758 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000759
Howard Hinnant756c69b2010-09-22 16:48:34 +0000760 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000761 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000762 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000763 __map_const_iterator operator++(int)
764 {
765 __map_const_iterator __t(*this);
766 ++(*this);
767 return __t;
768 }
769
Howard Hinnant756c69b2010-09-22 16:48:34 +0000770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000771 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000772 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000773 __map_const_iterator operator--(int)
774 {
775 __map_const_iterator __t(*this);
776 --(*this);
777 return __t;
778 }
779
Howard Hinnant756c69b2010-09-22 16:48:34 +0000780 friend _LIBCPP_INLINE_VISIBILITY
781 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000782 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000783 friend _LIBCPP_INLINE_VISIBILITY
784 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000785 {return __x.__i_ != __y.__i_;}
786
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000787 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
788 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
789 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000790};
791
792template <class _Key, class _Tp, class _Compare = less<_Key>,
793 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000794class _LIBCPP_TYPE_VIS_ONLY map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000795{
796public:
797 // types:
798 typedef _Key key_type;
799 typedef _Tp mapped_type;
800 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000801 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000802 typedef _Compare key_compare;
803 typedef _Allocator allocator_type;
804 typedef value_type& reference;
805 typedef const value_type& const_reference;
806
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000807 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000808 : public binary_function<value_type, value_type, bool>
809 {
810 friend class map;
811 protected:
812 key_compare comp;
813
Howard Hinnant756c69b2010-09-22 16:48:34 +0000814 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000816 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000817 bool operator()(const value_type& __x, const value_type& __y) const
818 {return comp(__x.first, __y.first);}
819 };
820
821private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000822
Howard Hinnant89f8b792013-09-30 19:08:22 +0000823 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000824 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000825 typedef typename allocator_traits<allocator_type>::template
826#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
827 rebind_alloc<__value_type>
828#else
829 rebind_alloc<__value_type>::other
830#endif
831 __allocator_type;
832 typedef __tree<__value_type, __vc, __allocator_type> __base;
833 typedef typename __base::__node_traits __node_traits;
834 typedef allocator_traits<allocator_type> __alloc_traits;
835
836 __base __tree_;
837
838public:
839 typedef typename __alloc_traits::pointer pointer;
840 typedef typename __alloc_traits::const_pointer const_pointer;
841 typedef typename __alloc_traits::size_type size_type;
842 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000843 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000844 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000845 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
846 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000847
Howard Hinnant756c69b2010-09-22 16:48:34 +0000848 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000849 map()
850 _NOEXCEPT_(
851 is_nothrow_default_constructible<allocator_type>::value &&
852 is_nothrow_default_constructible<key_compare>::value &&
853 is_nothrow_copy_constructible<key_compare>::value)
854 : __tree_(__vc(key_compare())) {}
855
856 _LIBCPP_INLINE_VISIBILITY
857 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000858 _NOEXCEPT_(
859 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000860 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000861 : __tree_(__vc(__comp)) {}
862
Howard Hinnant756c69b2010-09-22 16:48:34 +0000863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000864 explicit map(const key_compare& __comp, const allocator_type& __a)
865 : __tree_(__vc(__comp), __a) {}
866
867 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000869 map(_InputIterator __f, _InputIterator __l,
870 const key_compare& __comp = key_compare())
871 : __tree_(__vc(__comp))
872 {
873 insert(__f, __l);
874 }
875
876 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000877 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000878 map(_InputIterator __f, _InputIterator __l,
879 const key_compare& __comp, const allocator_type& __a)
880 : __tree_(__vc(__comp), __a)
881 {
882 insert(__f, __l);
883 }
884
Marshall Clow300abfb2013-09-11 01:15:47 +0000885#if _LIBCPP_STD_VER > 11
886 template <class _InputIterator>
887 _LIBCPP_INLINE_VISIBILITY
888 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
889 : map(__f, __l, key_compare(), __a) {}
890#endif
891
Howard Hinnant756c69b2010-09-22 16:48:34 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000893 map(const map& __m)
894 : __tree_(__m.__tree_)
895 {
896 insert(__m.begin(), __m.end());
897 }
898
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000899 _LIBCPP_INLINE_VISIBILITY
900 map& operator=(const map& __m)
901 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000902#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000903 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000904#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +0000905 if (this != &__m) {
906 __tree_.clear();
907 __tree_.value_comp() = __m.__tree_.value_comp();
908 __tree_.__copy_assign_alloc(__m.__tree_);
909 insert(__m.begin(), __m.end());
910 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000911#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000912 return *this;
913 }
914
Howard Hinnant74279a52010-09-04 23:28:19 +0000915#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000916
Howard Hinnant756c69b2010-09-22 16:48:34 +0000917 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000918 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000919 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000920 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000921 {
922 }
923
924 map(map&& __m, const allocator_type& __a);
925
Howard Hinnant756c69b2010-09-22 16:48:34 +0000926 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +0000927 map& operator=(map&& __m)
928 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
929 {
930 __tree_ = _VSTD::move(__m.__tree_);
931 return *this;
932 }
933
934#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
935
936#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
937
938 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000939 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
940 : __tree_(__vc(__comp))
941 {
942 insert(__il.begin(), __il.end());
943 }
944
Howard Hinnant756c69b2010-09-22 16:48:34 +0000945 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000946 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
947 : __tree_(__vc(__comp), __a)
948 {
949 insert(__il.begin(), __il.end());
950 }
951
Marshall Clow300abfb2013-09-11 01:15:47 +0000952#if _LIBCPP_STD_VER > 11
953 _LIBCPP_INLINE_VISIBILITY
954 map(initializer_list<value_type> __il, const allocator_type& __a)
955 : map(__il, key_compare(), __a) {}
956#endif
957
Howard Hinnant756c69b2010-09-22 16:48:34 +0000958 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000959 map& operator=(initializer_list<value_type> __il)
960 {
961 __tree_.__assign_unique(__il.begin(), __il.end());
962 return *this;
963 }
964
Howard Hinnant33711792011-08-12 21:56:02 +0000965#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +0000966
Howard Hinnant756c69b2010-09-22 16:48:34 +0000967 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000968 explicit map(const allocator_type& __a)
969 : __tree_(__a)
970 {
971 }
972
Howard Hinnant756c69b2010-09-22 16:48:34 +0000973 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000974 map(const map& __m, const allocator_type& __a)
975 : __tree_(__m.__tree_.value_comp(), __a)
976 {
977 insert(__m.begin(), __m.end());
978 }
979
Howard Hinnant756c69b2010-09-22 16:48:34 +0000980 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000981 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000982 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000983 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000984 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000985 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000986 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000987 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000988
Howard Hinnant756c69b2010-09-22 16:48:34 +0000989 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000990 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000991 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000992 const_reverse_iterator rbegin() const _NOEXCEPT
993 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000995 reverse_iterator rend() _NOEXCEPT
996 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000997 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000998 const_reverse_iterator rend() const _NOEXCEPT
999 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001000
Howard Hinnant756c69b2010-09-22 16:48:34 +00001001 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001002 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001003 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001004 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001005 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001006 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001007 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001008 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001009
Howard Hinnant756c69b2010-09-22 16:48:34 +00001010 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001011 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001012 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001013 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001014 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001015 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001016
1017 mapped_type& operator[](const key_type& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +00001018#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001019 mapped_type& operator[](key_type&& __k);
1020#endif
1021
1022 mapped_type& at(const key_type& __k);
1023 const mapped_type& at(const key_type& __k) const;
1024
Howard Hinnant756c69b2010-09-22 16:48:34 +00001025 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001026 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001027 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001028 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001029 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001030 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1031
Howard Hinnant74279a52010-09-04 23:28:19 +00001032#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant74279a52010-09-04 23:28:19 +00001033#ifndef _LIBCPP_HAS_NO_VARIADICS
1034
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001035 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001036 pair<iterator, bool>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001037 emplace(_Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001038
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001039 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001040 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001041 emplace_hint(const_iterator __p, _Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001042
Howard Hinnant74279a52010-09-04 23:28:19 +00001043#endif // _LIBCPP_HAS_NO_VARIADICS
1044
Howard Hinnantc834c512011-11-29 18:15:50 +00001045 template <class _Pp,
1046 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001047 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001048 pair<iterator, bool> insert(_Pp&& __p)
1049 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001050
Howard Hinnantc834c512011-11-29 18:15:50 +00001051 template <class _Pp,
1052 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001053 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001054 iterator insert(const_iterator __pos, _Pp&& __p)
1055 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001056
Howard Hinnant74279a52010-09-04 23:28:19 +00001057#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001058
Howard Hinnant756c69b2010-09-22 16:48:34 +00001059 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001060 pair<iterator, bool>
1061 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1062
Howard Hinnant756c69b2010-09-22 16:48:34 +00001063 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001064 iterator
1065 insert(const_iterator __p, const value_type& __v)
1066 {return __tree_.__insert_unique(__p.__i_, __v);}
1067
1068 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001069 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001070 void insert(_InputIterator __f, _InputIterator __l)
1071 {
1072 for (const_iterator __e = cend(); __f != __l; ++__f)
1073 insert(__e.__i_, *__f);
1074 }
1075
Howard Hinnant33711792011-08-12 21:56:02 +00001076#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1077
Howard Hinnant756c69b2010-09-22 16:48:34 +00001078 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001079 void insert(initializer_list<value_type> __il)
1080 {insert(__il.begin(), __il.end());}
1081
Howard Hinnant33711792011-08-12 21:56:02 +00001082#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1083
Howard Hinnant756c69b2010-09-22 16:48:34 +00001084 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001085 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001086 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001087 size_type erase(const key_type& __k)
1088 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001089 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001090 iterator erase(const_iterator __f, const_iterator __l)
1091 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001093 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001094
Howard Hinnant756c69b2010-09-22 16:48:34 +00001095 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001096 void swap(map& __m)
1097 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1098 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001099
Howard Hinnant756c69b2010-09-22 16:48:34 +00001100 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001101 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001102 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001103 const_iterator find(const key_type& __k) const {return __tree_.find(__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 find(const _K2& __k) {return __tree_.find(__k);}
1109 template <typename _K2>
1110 _LIBCPP_INLINE_VISIBILITY
1111 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1112 find(const _K2& __k) const {return __tree_.find(__k);}
1113#endif
1114
Howard Hinnant756c69b2010-09-22 16:48:34 +00001115 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001116 size_type count(const key_type& __k) const
1117 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001118#if _LIBCPP_STD_VER > 11
1119 template <typename _K2>
1120 _LIBCPP_INLINE_VISIBILITY
1121 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1122 count(const _K2& __k) {return __tree_.__count_unique(__k);}
1123#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001124 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001125 iterator lower_bound(const key_type& __k)
1126 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001127 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001128 const_iterator lower_bound(const key_type& __k) const
1129 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001130#if _LIBCPP_STD_VER > 11
1131 template <typename _K2>
1132 _LIBCPP_INLINE_VISIBILITY
1133 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1134 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1135
1136 template <typename _K2>
1137 _LIBCPP_INLINE_VISIBILITY
1138 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1139 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1140#endif
1141
Howard Hinnant756c69b2010-09-22 16:48:34 +00001142 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001143 iterator upper_bound(const key_type& __k)
1144 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001145 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001146 const_iterator upper_bound(const key_type& __k) const
1147 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001148#if _LIBCPP_STD_VER > 11
1149 template <typename _K2>
1150 _LIBCPP_INLINE_VISIBILITY
1151 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1152 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1153 template <typename _K2>
1154 _LIBCPP_INLINE_VISIBILITY
1155 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1156 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1157#endif
1158
Howard Hinnant756c69b2010-09-22 16:48:34 +00001159 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001160 pair<iterator,iterator> equal_range(const key_type& __k)
1161 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001162 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001163 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1164 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001165#if _LIBCPP_STD_VER > 11
1166 template <typename _K2>
1167 _LIBCPP_INLINE_VISIBILITY
1168 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1169 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1170 template <typename _K2>
1171 _LIBCPP_INLINE_VISIBILITY
1172 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1173 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1174#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001175
1176private:
1177 typedef typename __base::__node __node;
1178 typedef typename __base::__node_allocator __node_allocator;
1179 typedef typename __base::__node_pointer __node_pointer;
1180 typedef typename __base::__node_const_pointer __node_const_pointer;
1181 typedef typename __base::__node_base_pointer __node_base_pointer;
1182 typedef typename __base::__node_base_const_pointer __node_base_const_pointer;
Howard Hinnantc834c512011-11-29 18:15:50 +00001183 typedef __map_node_destructor<__node_allocator> _Dp;
1184 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001185
Howard Hinnant74279a52010-09-04 23:28:19 +00001186#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001187 __node_holder __construct_node();
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001188 template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001189 __node_holder __construct_node(_A0&& __a0);
1190 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +00001191#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001192 template <class _A0, class _A1, class ..._Args>
1193 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001194#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001195#endif
Howard Hinnantac7e7482013-07-04 20:59:16 +00001196 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001197
1198 __node_base_pointer&
1199 __find_equal_key(__node_base_pointer& __parent, const key_type& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001200 __node_base_const_pointer
1201 __find_equal_key(__node_base_const_pointer& __parent, const key_type& __k) const;
1202};
1203
1204// Find place to insert if __k doesn't exist
1205// Set __parent to parent of null leaf
1206// Return reference to null leaf
1207// If __k exists, set parent to node of __k and return reference to node of __k
1208template <class _Key, class _Tp, class _Compare, class _Allocator>
1209typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer&
1210map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
1211 const key_type& __k)
1212{
1213 __node_pointer __nd = __tree_.__root();
1214 if (__nd != nullptr)
1215 {
1216 while (true)
1217 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001218 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001219 {
1220 if (__nd->__left_ != nullptr)
1221 __nd = static_cast<__node_pointer>(__nd->__left_);
1222 else
1223 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001224 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001225 return __parent->__left_;
1226 }
1227 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001228 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001229 {
1230 if (__nd->__right_ != nullptr)
1231 __nd = static_cast<__node_pointer>(__nd->__right_);
1232 else
1233 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001234 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001235 return __parent->__right_;
1236 }
1237 }
1238 else
1239 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001240 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001241 return __parent;
1242 }
1243 }
1244 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001245 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001246 return __parent->__left_;
1247}
1248
Howard Hinnantc51e1022010-05-11 19:42:16 +00001249// Find __k
1250// Set __parent to parent of null leaf and
1251// return reference to null leaf iv __k does not exist.
1252// If __k exists, set parent to node of __k and return reference to node of __k
1253template <class _Key, class _Tp, class _Compare, class _Allocator>
1254typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_const_pointer
1255map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_const_pointer& __parent,
1256 const key_type& __k) const
1257{
1258 __node_const_pointer __nd = __tree_.__root();
1259 if (__nd != nullptr)
1260 {
1261 while (true)
1262 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001263 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001264 {
1265 if (__nd->__left_ != nullptr)
1266 __nd = static_cast<__node_pointer>(__nd->__left_);
1267 else
1268 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001269 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001270 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1271 }
1272 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001273 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001274 {
1275 if (__nd->__right_ != nullptr)
1276 __nd = static_cast<__node_pointer>(__nd->__right_);
1277 else
1278 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001279 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001280 return const_cast<const __node_base_const_pointer&>(__parent->__right_);
1281 }
1282 }
1283 else
1284 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001285 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001286 return __parent;
1287 }
1288 }
1289 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001290 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001291 return const_cast<const __node_base_const_pointer&>(__parent->__left_);
1292}
1293
Howard Hinnant74279a52010-09-04 23:28:19 +00001294#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001295
1296template <class _Key, class _Tp, class _Compare, class _Allocator>
1297map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001298 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001299{
1300 if (__a != __m.get_allocator())
1301 {
1302 const_iterator __e = cend();
1303 while (!__m.empty())
1304 __tree_.__insert_unique(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001305 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001306 }
1307}
1308
1309template <class _Key, class _Tp, class _Compare, class _Allocator>
1310typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1311map<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1312{
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 Hinnant2d0046b2013-06-19 21:29:40 +00001315 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
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 Hinnantc51e1022010-05-11 19:42:16 +00001318 __h.get_deleter().__second_constructed = true;
1319 return __h;
1320}
1321
1322template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001323template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001324typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantc51e1022010-05-11 19:42:16 +00001325map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1326{
1327 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001328 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001329 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001330 __h.get_deleter().__first_constructed = true;
1331 __h.get_deleter().__second_constructed = true;
1332 return __h;
1333}
1334
1335template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001336typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1337map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001338{
1339 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001340 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantac7e7482013-07-04 20:59:16 +00001341 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001342 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001343 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001344 __h.get_deleter().__second_constructed = true;
Howard Hinnanta31e9682013-08-22 18:29:50 +00001345 return __h;
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001346}
1347
1348#ifndef _LIBCPP_HAS_NO_VARIADICS
1349
1350template <class _Key, class _Tp, class _Compare, class _Allocator>
1351template <class _A0, class _A1, class ..._Args>
1352typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1353map<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1354{
1355 __node_allocator& __na = __tree_.__node_alloc();
1356 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1357 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1358 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1359 _VSTD::forward<_Args>(__args)...);
1360 __h.get_deleter().__first_constructed = true;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001361 __h.get_deleter().__second_constructed = true;
1362 return __h;
1363}
1364
Howard Hinnant74279a52010-09-04 23:28:19 +00001365#endif // _LIBCPP_HAS_NO_VARIADICS
1366
Howard Hinnantac7e7482013-07-04 20:59:16 +00001367#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001368
1369template <class _Key, class _Tp, class _Compare, class _Allocator>
1370typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001371map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001372{
1373 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001374 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001375 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001376 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001377 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001378 __h.get_deleter().__second_constructed = true;
Howard Hinnanta31e9682013-08-22 18:29:50 +00001379 return _VSTD::move(__h); // explicitly moved for C++03
Howard Hinnantc51e1022010-05-11 19:42:16 +00001380}
1381
Howard Hinnantc51e1022010-05-11 19:42:16 +00001382template <class _Key, class _Tp, class _Compare, class _Allocator>
1383_Tp&
1384map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1385{
1386 __node_base_pointer __parent;
1387 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1388 __node_pointer __r = static_cast<__node_pointer>(__child);
1389 if (__child == nullptr)
1390 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001391 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001392 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001393 __r = __h.release();
1394 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001395 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001396}
1397
Howard Hinnant74279a52010-09-04 23:28:19 +00001398#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001399
1400template <class _Key, class _Tp, class _Compare, class _Allocator>
1401_Tp&
1402map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1403{
1404 __node_base_pointer __parent;
1405 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1406 __node_pointer __r = static_cast<__node_pointer>(__child);
1407 if (__child == nullptr)
1408 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001409 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001410 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001411 __r = __h.release();
1412 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001413 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001414}
1415
Howard Hinnant74279a52010-09-04 23:28:19 +00001416#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001417
1418template <class _Key, class _Tp, class _Compare, class _Allocator>
1419_Tp&
1420map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1421{
1422 __node_base_pointer __parent;
1423 __node_base_pointer& __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001424#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001425 if (__child == nullptr)
1426 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001427#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001428 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001429}
1430
1431template <class _Key, class _Tp, class _Compare, class _Allocator>
1432const _Tp&
1433map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1434{
1435 __node_base_const_pointer __parent;
1436 __node_base_const_pointer __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001437#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001438 if (__child == nullptr)
1439 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001440#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001441 return static_cast<__node_const_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001442}
1443
Howard Hinnant74279a52010-09-04 23:28:19 +00001444#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001445
1446template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001447template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001448pair<typename map<_Key, _Tp, _Compare, _Allocator>::iterator, bool>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001449map<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001450{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001451 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001452 pair<iterator, bool> __r = __tree_.__node_insert_unique(__h.get());
1453 if (__r.second)
1454 __h.release();
1455 return __r;
1456}
1457
1458template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001459template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001460typename map<_Key, _Tp, _Compare, _Allocator>::iterator
1461map<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001462 _Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001463{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001464 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001465 iterator __r = __tree_.__node_insert_unique(__p.__i_, __h.get());
1466 if (__r.__i_.__ptr_ == __h.get())
1467 __h.release();
1468 return __r;
1469}
1470
Howard Hinnant74279a52010-09-04 23:28:19 +00001471#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001472
1473template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001474inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001475bool
1476operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1477 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1478{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001479 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001480}
1481
1482template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001483inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001484bool
1485operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1486 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1487{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001488 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001489}
1490
1491template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001492inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001493bool
1494operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1495 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1496{
1497 return !(__x == __y);
1498}
1499
1500template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001501inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001502bool
1503operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1504 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1505{
1506 return __y < __x;
1507}
1508
1509template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001510inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001511bool
1512operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1513 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1514{
1515 return !(__x < __y);
1516}
1517
1518template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001519inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001520bool
1521operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1522 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1523{
1524 return !(__y < __x);
1525}
1526
1527template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001528inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001529void
1530swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1531 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001532 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001533{
1534 __x.swap(__y);
1535}
1536
1537template <class _Key, class _Tp, class _Compare = less<_Key>,
1538 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001539class _LIBCPP_TYPE_VIS_ONLY multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001540{
1541public:
1542 // types:
1543 typedef _Key key_type;
1544 typedef _Tp mapped_type;
1545 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001546 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001547 typedef _Compare key_compare;
1548 typedef _Allocator allocator_type;
1549 typedef value_type& reference;
1550 typedef const value_type& const_reference;
1551
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001552 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001553 : public binary_function<value_type, value_type, bool>
1554 {
1555 friend class multimap;
1556 protected:
1557 key_compare comp;
1558
Howard Hinnant756c69b2010-09-22 16:48:34 +00001559 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001560 value_compare(key_compare c) : comp(c) {}
1561 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001562 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001563 bool operator()(const value_type& __x, const value_type& __y) const
1564 {return comp(__x.first, __y.first);}
1565 };
1566
1567private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001568
Howard Hinnant89f8b792013-09-30 19:08:22 +00001569 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001570 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001571 typedef typename allocator_traits<allocator_type>::template
1572#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
1573 rebind_alloc<__value_type>
1574#else
1575 rebind_alloc<__value_type>::other
1576#endif
1577 __allocator_type;
1578 typedef __tree<__value_type, __vc, __allocator_type> __base;
1579 typedef typename __base::__node_traits __node_traits;
1580 typedef allocator_traits<allocator_type> __alloc_traits;
1581
1582 __base __tree_;
1583
1584public:
1585 typedef typename __alloc_traits::pointer pointer;
1586 typedef typename __alloc_traits::const_pointer const_pointer;
1587 typedef typename __alloc_traits::size_type size_type;
1588 typedef typename __alloc_traits::difference_type difference_type;
1589 typedef __map_iterator<typename __base::iterator> iterator;
1590 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001591 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1592 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001593
Howard Hinnant756c69b2010-09-22 16:48:34 +00001594 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001595 multimap()
1596 _NOEXCEPT_(
1597 is_nothrow_default_constructible<allocator_type>::value &&
1598 is_nothrow_default_constructible<key_compare>::value &&
1599 is_nothrow_copy_constructible<key_compare>::value)
1600 : __tree_(__vc(key_compare())) {}
1601
1602 _LIBCPP_INLINE_VISIBILITY
1603 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001604 _NOEXCEPT_(
1605 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001606 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001607 : __tree_(__vc(__comp)) {}
1608
Howard Hinnant756c69b2010-09-22 16:48:34 +00001609 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001610 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1611 : __tree_(__vc(__comp), __a) {}
1612
1613 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001614 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001615 multimap(_InputIterator __f, _InputIterator __l,
1616 const key_compare& __comp = key_compare())
1617 : __tree_(__vc(__comp))
1618 {
1619 insert(__f, __l);
1620 }
1621
1622 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001623 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001624 multimap(_InputIterator __f, _InputIterator __l,
1625 const key_compare& __comp, const allocator_type& __a)
1626 : __tree_(__vc(__comp), __a)
1627 {
1628 insert(__f, __l);
1629 }
1630
Marshall Clow300abfb2013-09-11 01:15:47 +00001631#if _LIBCPP_STD_VER > 11
1632 template <class _InputIterator>
1633 _LIBCPP_INLINE_VISIBILITY
1634 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1635 : multimap(__f, __l, key_compare(), __a) {}
1636#endif
1637
Howard Hinnant756c69b2010-09-22 16:48:34 +00001638 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001639 multimap(const multimap& __m)
1640 : __tree_(__m.__tree_.value_comp(),
1641 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1642 {
1643 insert(__m.begin(), __m.end());
1644 }
1645
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001646 _LIBCPP_INLINE_VISIBILITY
1647 multimap& operator=(const multimap& __m)
1648 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001649#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001650 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001651#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001652 if (this != &__m) {
1653 __tree_.clear();
1654 __tree_.value_comp() = __m.__tree_.value_comp();
1655 __tree_.__copy_assign_alloc(__m.__tree_);
1656 insert(__m.begin(), __m.end());
1657 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001658#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001659 return *this;
1660 }
1661
Howard Hinnant74279a52010-09-04 23:28:19 +00001662#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001663
Howard Hinnant756c69b2010-09-22 16:48:34 +00001664 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001665 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001666 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001667 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001668 {
1669 }
1670
1671 multimap(multimap&& __m, const allocator_type& __a);
1672
Howard Hinnant756c69b2010-09-22 16:48:34 +00001673 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001674 multimap& operator=(multimap&& __m)
1675 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1676 {
1677 __tree_ = _VSTD::move(__m.__tree_);
1678 return *this;
1679 }
1680
1681#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1682
1683#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1684
1685 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001686 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1687 : __tree_(__vc(__comp))
1688 {
1689 insert(__il.begin(), __il.end());
1690 }
1691
Howard Hinnant756c69b2010-09-22 16:48:34 +00001692 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001693 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1694 : __tree_(__vc(__comp), __a)
1695 {
1696 insert(__il.begin(), __il.end());
1697 }
1698
Marshall Clow300abfb2013-09-11 01:15:47 +00001699#if _LIBCPP_STD_VER > 11
1700 _LIBCPP_INLINE_VISIBILITY
1701 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1702 : multimap(__il, key_compare(), __a) {}
1703#endif
1704
Howard Hinnant756c69b2010-09-22 16:48:34 +00001705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706 multimap& operator=(initializer_list<value_type> __il)
1707 {
1708 __tree_.__assign_multi(__il.begin(), __il.end());
1709 return *this;
1710 }
Howard Hinnant33711792011-08-12 21:56:02 +00001711
1712#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001713
Howard Hinnant756c69b2010-09-22 16:48:34 +00001714 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001715 explicit multimap(const allocator_type& __a)
1716 : __tree_(__a)
1717 {
1718 }
1719
Howard Hinnant756c69b2010-09-22 16:48:34 +00001720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001721 multimap(const multimap& __m, const allocator_type& __a)
1722 : __tree_(__m.__tree_.value_comp(), __a)
1723 {
1724 insert(__m.begin(), __m.end());
1725 }
1726
Howard Hinnant756c69b2010-09-22 16:48:34 +00001727 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001728 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001729 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001730 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001732 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001733 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001734 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001735
Howard Hinnant756c69b2010-09-22 16:48:34 +00001736 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001737 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001738 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001739 const_reverse_iterator rbegin() const _NOEXCEPT
1740 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001741 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001742 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001743 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001744 const_reverse_iterator rend() const _NOEXCEPT
1745 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001746
Howard Hinnant756c69b2010-09-22 16:48:34 +00001747 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001748 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001749 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001750 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001752 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001753 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001754 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001755
Howard Hinnant756c69b2010-09-22 16:48:34 +00001756 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001757 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001758 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001759 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001760 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001761 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001762
Howard Hinnant756c69b2010-09-22 16:48:34 +00001763 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001764 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001765 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001766 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001768 value_compare value_comp() const
1769 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001770
Howard Hinnant74279a52010-09-04 23:28:19 +00001771#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant74279a52010-09-04 23:28:19 +00001772#ifndef _LIBCPP_HAS_NO_VARIADICS
1773
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001774 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001775 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001776 emplace(_Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001777
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001778 template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001779 iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001780 emplace_hint(const_iterator __p, _Args&& ...__args);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001781
Howard Hinnant74279a52010-09-04 23:28:19 +00001782#endif // _LIBCPP_HAS_NO_VARIADICS
1783
Howard Hinnantc834c512011-11-29 18:15:50 +00001784 template <class _Pp,
1785 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001786 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001787 iterator insert(_Pp&& __p)
1788 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001789
Howard Hinnantc834c512011-11-29 18:15:50 +00001790 template <class _Pp,
1791 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001792 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001793 iterator insert(const_iterator __pos, _Pp&& __p)
1794 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001795
Howard Hinnant74279a52010-09-04 23:28:19 +00001796#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001797
Howard Hinnant756c69b2010-09-22 16:48:34 +00001798 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001799 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1800
Howard Hinnant756c69b2010-09-22 16:48:34 +00001801 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001802 iterator insert(const_iterator __p, const value_type& __v)
1803 {return __tree_.__insert_multi(__p.__i_, __v);}
1804
1805 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001806 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001807 void insert(_InputIterator __f, _InputIterator __l)
1808 {
1809 for (const_iterator __e = cend(); __f != __l; ++__f)
1810 __tree_.__insert_multi(__e.__i_, *__f);
1811 }
1812
Howard Hinnant33711792011-08-12 21:56:02 +00001813#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1814
Howard Hinnant756c69b2010-09-22 16:48:34 +00001815 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001816 void insert(initializer_list<value_type> __il)
1817 {insert(__il.begin(), __il.end());}
1818
Howard Hinnant33711792011-08-12 21:56:02 +00001819#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1820
Howard Hinnant756c69b2010-09-22 16:48:34 +00001821 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001822 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001823 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001824 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001825 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001826 iterator erase(const_iterator __f, const_iterator __l)
1827 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001828 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001829 void clear() {__tree_.clear();}
1830
Howard Hinnant756c69b2010-09-22 16:48:34 +00001831 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001832 void swap(multimap& __m)
1833 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1834 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001835
Howard Hinnant756c69b2010-09-22 16:48:34 +00001836 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001837 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001838 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001839 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001840#if _LIBCPP_STD_VER > 11
1841 template <typename _K2>
1842 _LIBCPP_INLINE_VISIBILITY
1843 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1844 find(const _K2& __k) {return __tree_.find(__k);}
1845 template <typename _K2>
1846 _LIBCPP_INLINE_VISIBILITY
1847 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1848 find(const _K2& __k) const {return __tree_.find(__k);}
1849#endif
1850
Howard Hinnant756c69b2010-09-22 16:48:34 +00001851 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001852 size_type count(const key_type& __k) const
1853 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001854#if _LIBCPP_STD_VER > 11
1855 template <typename _K2>
1856 _LIBCPP_INLINE_VISIBILITY
1857 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
1858 count(const _K2& __k) {return __tree_.__count_multi(__k);}
1859#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001860 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001861 iterator lower_bound(const key_type& __k)
1862 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001864 const_iterator lower_bound(const key_type& __k) const
1865 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001866#if _LIBCPP_STD_VER > 11
1867 template <typename _K2>
1868 _LIBCPP_INLINE_VISIBILITY
1869 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1870 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1871
1872 template <typename _K2>
1873 _LIBCPP_INLINE_VISIBILITY
1874 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1875 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1876#endif
1877
Howard Hinnant756c69b2010-09-22 16:48:34 +00001878 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001879 iterator upper_bound(const key_type& __k)
1880 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001881 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001882 const_iterator upper_bound(const key_type& __k) const
1883 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001884#if _LIBCPP_STD_VER > 11
1885 template <typename _K2>
1886 _LIBCPP_INLINE_VISIBILITY
1887 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1888 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1889 template <typename _K2>
1890 _LIBCPP_INLINE_VISIBILITY
1891 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1892 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1893#endif
1894
Howard Hinnant756c69b2010-09-22 16:48:34 +00001895 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001896 pair<iterator,iterator> equal_range(const key_type& __k)
1897 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001899 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1900 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001901#if _LIBCPP_STD_VER > 11
1902 template <typename _K2>
1903 _LIBCPP_INLINE_VISIBILITY
1904 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1905 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1906 template <typename _K2>
1907 _LIBCPP_INLINE_VISIBILITY
1908 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1909 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1910#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001911
1912private:
1913 typedef typename __base::__node __node;
1914 typedef typename __base::__node_allocator __node_allocator;
1915 typedef typename __base::__node_pointer __node_pointer;
1916 typedef typename __base::__node_const_pointer __node_const_pointer;
Howard Hinnantc834c512011-11-29 18:15:50 +00001917 typedef __map_node_destructor<__node_allocator> _Dp;
1918 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001919
Howard Hinnant74279a52010-09-04 23:28:19 +00001920#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001921 __node_holder __construct_node();
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001922 template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001923 __node_holder
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001924 __construct_node(_A0&& __a0);
Howard Hinnant74279a52010-09-04 23:28:19 +00001925#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001926 template <class _A0, class _A1, class ..._Args>
1927 __node_holder __construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args);
Howard Hinnant74279a52010-09-04 23:28:19 +00001928#endif // _LIBCPP_HAS_NO_VARIADICS
1929#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001930};
1931
Howard Hinnant74279a52010-09-04 23:28:19 +00001932#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001933
1934template <class _Key, class _Tp, class _Compare, class _Allocator>
1935multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001936 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001937{
1938 if (__a != __m.get_allocator())
1939 {
1940 const_iterator __e = cend();
1941 while (!__m.empty())
1942 __tree_.__insert_multi(__e.__i_,
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001943 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001944 }
1945}
1946
1947template <class _Key, class _Tp, class _Compare, class _Allocator>
1948typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1949multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node()
1950{
1951 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001952 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001953 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001954 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001955 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001956 __h.get_deleter().__second_constructed = true;
1957 return __h;
1958}
1959
1960template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001961template <class _A0>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001962typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantc51e1022010-05-11 19:42:16 +00001963multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0)
1964{
1965 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001966 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001967 __node_traits::construct(__na, _VSTD::addressof(__h->__value_), _VSTD::forward<_A0>(__a0));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001968 __h.get_deleter().__first_constructed = true;
1969 __h.get_deleter().__second_constructed = true;
1970 return __h;
1971}
1972
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001973#ifndef _LIBCPP_HAS_NO_VARIADICS
1974
1975template <class _Key, class _Tp, class _Compare, class _Allocator>
1976template <class _A0, class _A1, class ..._Args>
1977typename multimap<_Key, _Tp, _Compare, _Allocator>::__node_holder
1978multimap<_Key, _Tp, _Compare, _Allocator>::__construct_node(_A0&& __a0, _A1&& __a1, _Args&& ...__args)
1979{
1980 __node_allocator& __na = __tree_.__node_alloc();
1981 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1982 __node_traits::construct(__na, _VSTD::addressof(__h->__value_),
1983 _VSTD::forward<_A0>(__a0), _VSTD::forward<_A1>(__a1),
1984 _VSTD::forward<_Args>(__args)...);
1985 __h.get_deleter().__first_constructed = true;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001986 __h.get_deleter().__second_constructed = true;
1987 return __h;
1988}
1989
Howard Hinnant74279a52010-09-04 23:28:19 +00001990#endif // _LIBCPP_HAS_NO_VARIADICS
1991#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001992
Howard Hinnant74279a52010-09-04 23:28:19 +00001993#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001994
1995template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001996template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00001997typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001998multimap<_Key, _Tp, _Compare, _Allocator>::emplace(_Args&& ...__args)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001999{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00002000 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002001 iterator __r = __tree_.__node_insert_multi(__h.get());
2002 __h.release();
2003 return __r;
2004}
2005
2006template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant29eb9b82012-05-25 22:04:21 +00002007template <class ..._Args>
Howard Hinnantc51e1022010-05-11 19:42:16 +00002008typename multimap<_Key, _Tp, _Compare, _Allocator>::iterator
2009multimap<_Key, _Tp, _Compare, _Allocator>::emplace_hint(const_iterator __p,
Howard Hinnantc51e1022010-05-11 19:42:16 +00002010 _Args&& ...__args)
2011{
Howard Hinnant29eb9b82012-05-25 22:04:21 +00002012 __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);
Howard Hinnantc51e1022010-05-11 19:42:16 +00002013 iterator __r = __tree_.__node_insert_multi(__p.__i_, __h.get());
2014 __h.release();
2015 return __r;
2016}
2017
Howard Hinnant74279a52010-09-04 23:28:19 +00002018#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
Howard Hinnantc51e1022010-05-11 19:42:16 +00002019
2020template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002021inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002022bool
2023operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2024 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2025{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002026 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002027}
2028
2029template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002030inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002031bool
2032operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2033 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2034{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00002035 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00002036}
2037
2038template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002039inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002040bool
2041operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2042 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2043{
2044 return !(__x == __y);
2045}
2046
2047template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002048inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002049bool
2050operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2051 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2052{
2053 return __y < __x;
2054}
2055
2056template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002057inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002058bool
2059operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2060 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2061{
2062 return !(__x < __y);
2063}
2064
2065template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002066inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002067bool
2068operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2069 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2070{
2071 return !(__y < __x);
2072}
2073
2074template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002075inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002076void
2077swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2078 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002079 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002080{
2081 __x.swap(__y);
2082}
2083
2084_LIBCPP_END_NAMESPACE_STD
2085
2086#endif // _LIBCPP_MAP