blob: a459146021c985d50611013519f413bc58f9cc20 [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);
Marshall Clowd430d022016-01-05 19:32:41 +0000129 pair<iterator, bool> insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000130 template <class P>
131 pair<iterator, bool> insert(P&& p);
132 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000133 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000134 template <class P>
135 iterator insert(const_iterator position, P&& p);
136 template <class InputIterator>
137 void insert(InputIterator first, InputIterator last);
138 void insert(initializer_list<value_type> il);
139
Marshall Clow3223db82015-07-07 03:37:33 +0000140 template <class... Args>
141 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
142 template <class... Args>
143 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
144 template <class... Args>
145 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
146 template <class... Args>
147 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
148 template <class M>
149 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
150 template <class M>
151 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
152 template <class M>
153 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
154 template <class M>
155 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
156
Howard Hinnantc51e1022010-05-11 19:42:16 +0000157 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000158 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000159 size_type erase(const key_type& k);
160 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000161 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000162
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000163 void swap(map& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000164 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
165 __is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000166
167 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000168 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000169 key_compare key_comp() const;
170 value_compare value_comp() const;
171
172 // map operations:
173 iterator find(const key_type& k);
174 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000175 template<typename K>
176 iterator find(const K& x); // C++14
177 template<typename K>
178 const_iterator find(const K& x) const; // C++14
179 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000180 size_type count(const K& x) const; // C++14
Marshall Clowebb57322013-08-13 22:18:47 +0000181
Howard Hinnantc51e1022010-05-11 19:42:16 +0000182 size_type count(const key_type& k) const;
183 iterator lower_bound(const key_type& k);
184 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000185 template<typename K>
186 iterator lower_bound(const K& x); // C++14
187 template<typename K>
188 const_iterator lower_bound(const K& x) const; // C++14
189
Howard Hinnantc51e1022010-05-11 19:42:16 +0000190 iterator upper_bound(const key_type& k);
191 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000192 template<typename K>
193 iterator upper_bound(const K& x); // C++14
194 template<typename K>
195 const_iterator upper_bound(const K& x) const; // C++14
196
Howard Hinnantc51e1022010-05-11 19:42:16 +0000197 pair<iterator,iterator> equal_range(const key_type& k);
198 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000199 template<typename K>
200 pair<iterator,iterator> equal_range(const K& x); // C++14
201 template<typename K>
202 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000203};
204
205template <class Key, class T, class Compare, class Allocator>
206bool
207operator==(const map<Key, T, Compare, Allocator>& x,
208 const map<Key, T, Compare, Allocator>& y);
209
210template <class Key, class T, class Compare, class Allocator>
211bool
212operator< (const map<Key, T, Compare, Allocator>& x,
213 const map<Key, T, Compare, Allocator>& y);
214
215template <class Key, class T, class Compare, class Allocator>
216bool
217operator!=(const map<Key, T, Compare, Allocator>& x,
218 const map<Key, T, Compare, Allocator>& y);
219
220template <class Key, class T, class Compare, class Allocator>
221bool
222operator> (const map<Key, T, Compare, Allocator>& x,
223 const map<Key, T, Compare, Allocator>& y);
224
225template <class Key, class T, class Compare, class Allocator>
226bool
227operator>=(const map<Key, T, Compare, Allocator>& x,
228 const map<Key, T, Compare, Allocator>& y);
229
230template <class Key, class T, class Compare, class Allocator>
231bool
232operator<=(const map<Key, T, Compare, Allocator>& x,
233 const map<Key, T, Compare, Allocator>& y);
234
235// specialized algorithms:
236template <class Key, class T, class Compare, class Allocator>
237void
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000238swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
239 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000240
241template <class Key, class T, class Compare = less<Key>,
242 class Allocator = allocator<pair<const Key, T>>>
243class multimap
244{
245public:
246 // types:
247 typedef Key key_type;
248 typedef T mapped_type;
249 typedef pair<const key_type,mapped_type> value_type;
250 typedef Compare key_compare;
251 typedef Allocator allocator_type;
252 typedef typename allocator_type::reference reference;
253 typedef typename allocator_type::const_reference const_reference;
254 typedef typename allocator_type::size_type size_type;
255 typedef typename allocator_type::difference_type difference_type;
256 typedef typename allocator_type::pointer pointer;
257 typedef typename allocator_type::const_pointer const_pointer;
258
259 typedef implementation-defined iterator;
260 typedef implementation-defined const_iterator;
261 typedef std::reverse_iterator<iterator> reverse_iterator;
262 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
263
264 class value_compare
265 : public binary_function<value_type,value_type,bool>
266 {
267 friend class multimap;
268 protected:
269 key_compare comp;
270 value_compare(key_compare c);
271 public:
272 bool operator()(const value_type& x, const value_type& y) const;
273 };
274
275 // construct/copy/destroy:
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000276 multimap()
277 noexcept(
278 is_nothrow_default_constructible<allocator_type>::value &&
279 is_nothrow_default_constructible<key_compare>::value &&
280 is_nothrow_copy_constructible<key_compare>::value);
281 explicit multimap(const key_compare& comp);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000282 multimap(const key_compare& comp, const allocator_type& a);
283 template <class InputIterator>
284 multimap(InputIterator first, InputIterator last, const key_compare& comp);
285 template <class InputIterator>
286 multimap(InputIterator first, InputIterator last, const key_compare& comp,
287 const allocator_type& a);
288 multimap(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000289 multimap(multimap&& m)
290 noexcept(
291 is_nothrow_move_constructible<allocator_type>::value &&
292 is_nothrow_move_constructible<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000293 explicit multimap(const allocator_type& a);
294 multimap(const multimap& m, const allocator_type& a);
295 multimap(multimap&& m, const allocator_type& a);
296 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
297 multimap(initializer_list<value_type> il, const key_compare& comp,
298 const allocator_type& a);
Marshall Clow300abfb2013-09-11 01:15:47 +0000299 template <class InputIterator>
300 multimap(InputIterator first, InputIterator last, const allocator_type& a)
301 : multimap(first, last, Compare(), a) {} // C++14
302 multimap(initializer_list<value_type> il, const allocator_type& a)
303 : multimap(il, Compare(), a) {} // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000304 ~multimap();
305
306 multimap& operator=(const multimap& m);
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000307 multimap& operator=(multimap&& m)
308 noexcept(
309 allocator_type::propagate_on_container_move_assignment::value &&
310 is_nothrow_move_assignable<allocator_type>::value &&
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000311 is_nothrow_move_assignable<key_compare>::value);
Howard Hinnantc51e1022010-05-11 19:42:16 +0000312 multimap& operator=(initializer_list<value_type> il);
313
314 // iterators:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000315 iterator begin() noexcept;
316 const_iterator begin() const noexcept;
317 iterator end() noexcept;
318 const_iterator end() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000319
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000320 reverse_iterator rbegin() noexcept;
321 const_reverse_iterator rbegin() const noexcept;
322 reverse_iterator rend() noexcept;
323 const_reverse_iterator rend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000324
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000325 const_iterator cbegin() const noexcept;
326 const_iterator cend() const noexcept;
327 const_reverse_iterator crbegin() const noexcept;
328 const_reverse_iterator crend() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000329
330 // capacity:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000331 bool empty() const noexcept;
332 size_type size() const noexcept;
333 size_type max_size() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000334
335 // modifiers:
336 template <class... Args>
337 iterator emplace(Args&&... args);
338 template <class... Args>
339 iterator emplace_hint(const_iterator position, Args&&... args);
340 iterator insert(const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000341 iterator insert( value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000342 template <class P>
343 iterator insert(P&& p);
344 iterator insert(const_iterator position, const value_type& v);
Marshall Clowd430d022016-01-05 19:32:41 +0000345 iterator insert(const_iterator position, value_type&& v); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000346 template <class P>
347 iterator insert(const_iterator position, P&& p);
348 template <class InputIterator>
349 void insert(InputIterator first, InputIterator last);
350 void insert(initializer_list<value_type> il);
351
352 iterator erase(const_iterator position);
Marshall Clow22ea5b82015-05-10 13:35:00 +0000353 iterator erase(iterator position); // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000354 size_type erase(const key_type& k);
355 iterator erase(const_iterator first, const_iterator last);
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000356 void clear() noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000357
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000358 void swap(multimap& m)
Marshall Clow8982dcd2015-07-13 20:04:56 +0000359 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
360 __is_nothrow_swappable<key_compare>::value); // C++17
Howard Hinnantc51e1022010-05-11 19:42:16 +0000361
362 // observers:
Howard Hinnantf95f4f52011-06-04 15:22:34 +0000363 allocator_type get_allocator() const noexcept;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000364 key_compare key_comp() const;
365 value_compare value_comp() const;
366
367 // map operations:
368 iterator find(const key_type& k);
369 const_iterator find(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000370 template<typename K>
371 iterator find(const K& x); // C++14
372 template<typename K>
373 const_iterator find(const K& x) const; // C++14
374 template<typename K>
Marshall Clowe6a5f522014-08-24 23:54:16 +0000375 size_type count(const K& x) const; // C++14
Marshall Clowebb57322013-08-13 22:18:47 +0000376
Howard Hinnantc51e1022010-05-11 19:42:16 +0000377 size_type count(const key_type& k) const;
378 iterator lower_bound(const key_type& k);
379 const_iterator lower_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000380 template<typename K>
381 iterator lower_bound(const K& x); // C++14
382 template<typename K>
383 const_iterator lower_bound(const K& x) const; // C++14
384
Howard Hinnantc51e1022010-05-11 19:42:16 +0000385 iterator upper_bound(const key_type& k);
386 const_iterator upper_bound(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000387 template<typename K>
388 iterator upper_bound(const K& x); // C++14
389 template<typename K>
390 const_iterator upper_bound(const K& x) const; // C++14
391
Howard Hinnantc51e1022010-05-11 19:42:16 +0000392 pair<iterator,iterator> equal_range(const key_type& k);
393 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
Marshall Clowebb57322013-08-13 22:18:47 +0000394 template<typename K>
395 pair<iterator,iterator> equal_range(const K& x); // C++14
396 template<typename K>
397 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
Howard Hinnantc51e1022010-05-11 19:42:16 +0000398};
399
400template <class Key, class T, class Compare, class Allocator>
401bool
402operator==(const multimap<Key, T, Compare, Allocator>& x,
403 const multimap<Key, T, Compare, Allocator>& y);
404
405template <class Key, class T, class Compare, class Allocator>
406bool
407operator< (const multimap<Key, T, Compare, Allocator>& x,
408 const multimap<Key, T, Compare, Allocator>& y);
409
410template <class Key, class T, class Compare, class Allocator>
411bool
412operator!=(const multimap<Key, T, Compare, Allocator>& x,
413 const multimap<Key, T, Compare, Allocator>& y);
414
415template <class Key, class T, class Compare, class Allocator>
416bool
417operator> (const multimap<Key, T, Compare, Allocator>& x,
418 const multimap<Key, T, Compare, Allocator>& y);
419
420template <class Key, class T, class Compare, class Allocator>
421bool
422operator>=(const multimap<Key, T, Compare, Allocator>& x,
423 const multimap<Key, T, Compare, Allocator>& y);
424
425template <class Key, class T, class Compare, class Allocator>
426bool
427operator<=(const multimap<Key, T, Compare, Allocator>& x,
428 const multimap<Key, T, Compare, Allocator>& y);
429
430// specialized algorithms:
431template <class Key, class T, class Compare, class Allocator>
432void
433swap(multimap<Key, T, Compare, Allocator>& x,
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000434 multimap<Key, T, Compare, Allocator>& y)
435 noexcept(noexcept(x.swap(y)));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000436
437} // std
438
439*/
440
441#include <__config>
442#include <__tree>
443#include <iterator>
444#include <memory>
445#include <utility>
446#include <functional>
447#include <initializer_list>
Eric Fiselierf7394302015-06-13 07:08:02 +0000448#include <type_traits>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000449
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000450#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000451#pragma GCC system_header
Howard Hinnantaaaa52b2011-10-17 20:05:10 +0000452#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000453
454_LIBCPP_BEGIN_NAMESPACE_STD
455
Eric Fiselierf7394302015-06-13 07:08:02 +0000456template <class _Key, class _CP, class _Compare,
457 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value
Howard Hinnantd0aabf82011-12-11 20:31:33 +0000458 >
Howard Hinnantc51e1022010-05-11 19:42:16 +0000459class __map_value_compare
460 : private _Compare
461{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000462public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000463 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000464 __map_value_compare()
465 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
466 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000467 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000468 __map_value_compare(_Compare c)
469 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
470 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000472 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000473 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000474 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000475 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000476 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000477 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000478 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000479 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000480 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000481 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000482 void swap(__map_value_compare&__y)
483 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
484 {
485 using _VSTD::swap;
486 swap(static_cast<const _Compare&>(*this), static_cast<const _Compare&>(__y));
487 }
Marshall Clowebb57322013-08-13 22:18:47 +0000488
489#if _LIBCPP_STD_VER > 11
490 template <typename _K2>
491 _LIBCPP_INLINE_VISIBILITY
492 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
493 operator () ( const _K2& __x, const _CP& __y ) const
494 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
495
496 template <typename _K2>
497 _LIBCPP_INLINE_VISIBILITY
498 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
499 operator () (const _CP& __x, const _K2& __y) const
500 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
501#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000502};
503
Howard Hinnant90b91592013-07-05 18:06:00 +0000504template <class _Key, class _CP, class _Compare>
505class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000506{
507 _Compare comp;
508
Howard Hinnantc51e1022010-05-11 19:42:16 +0000509public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000510 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000511 __map_value_compare()
512 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
513 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000515 __map_value_compare(_Compare c)
516 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
517 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000518 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000519 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000520
Howard Hinnant756c69b2010-09-22 16:48:34 +0000521 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000522 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000523 {return comp(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000524 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000525 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000526 {return comp(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000527 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000528 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000529 {return comp(__x, __y.__cc.first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000530 void swap(__map_value_compare&__y)
531 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
532 {
533 using _VSTD::swap;
534 swap(comp, __y.comp);
535 }
536
Marshall Clowebb57322013-08-13 22:18:47 +0000537#if _LIBCPP_STD_VER > 11
538 template <typename _K2>
539 _LIBCPP_INLINE_VISIBILITY
540 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
541 operator () ( const _K2& __x, const _CP& __y ) const
542 {return comp (__x, __y.__cc.first);}
543
544 template <typename _K2>
545 _LIBCPP_INLINE_VISIBILITY
546 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
547 operator () (const _CP& __x, const _K2& __y) const
548 {return comp (__x.__cc.first, __y);}
549#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000550};
551
Marshall Clow8982dcd2015-07-13 20:04:56 +0000552template <class _Key, class _CP, class _Compare, bool __b>
553inline _LIBCPP_INLINE_VISIBILITY
554void
555swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
556 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
557 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
558{
559 __x.swap(__y);
560}
561
Howard Hinnantc51e1022010-05-11 19:42:16 +0000562template <class _Allocator>
563class __map_node_destructor
564{
565 typedef _Allocator allocator_type;
566 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000567
Howard Hinnantc51e1022010-05-11 19:42:16 +0000568public:
569 typedef typename __alloc_traits::pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000570
Eric Fiseliera00b4842016-02-20 05:28:30 +0000571private:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000572 allocator_type& __na_;
573
574 __map_node_destructor& operator=(const __map_node_destructor&);
575
576public:
577 bool __first_constructed;
578 bool __second_constructed;
579
Howard Hinnant756c69b2010-09-22 16:48:34 +0000580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000581 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000582 : __na_(__na),
583 __first_constructed(false),
584 __second_constructed(false)
585 {}
586
Howard Hinnant74279a52010-09-04 23:28:19 +0000587#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant756c69b2010-09-22 16:48:34 +0000588 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000589 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000590 : __na_(__x.__na_),
591 __first_constructed(__x.__value_constructed),
592 __second_constructed(__x.__value_constructed)
593 {
594 __x.__value_constructed = false;
595 }
Howard Hinnant5dc89112010-09-04 23:46:48 +0000596#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000597
Howard Hinnant756c69b2010-09-22 16:48:34 +0000598 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000599 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000600 {
601 if (__second_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000602 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000603 if (__first_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000604 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000605 if (__p)
606 __alloc_traits::deallocate(__na_, __p, 1);
607 }
608};
609
Howard Hinnant944510a2011-06-14 19:58:17 +0000610template <class _Key, class _Tp, class _Compare, class _Allocator>
611 class map;
612template <class _Key, class _Tp, class _Compare, class _Allocator>
613 class multimap;
614template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000615
Eric Fiseliera00b4842016-02-20 05:28:30 +0000616#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000617
618template <class _Key, class _Tp>
619union __value_type
620{
621 typedef _Key key_type;
622 typedef _Tp mapped_type;
623 typedef pair<const key_type, mapped_type> value_type;
624 typedef pair<key_type, mapped_type> __nc_value_type;
625
626 value_type __cc;
627 __nc_value_type __nc;
628
Howard Hinnant89f8b792013-09-30 19:08:22 +0000629 _LIBCPP_INLINE_VISIBILITY
630 __value_type& operator=(const __value_type& __v)
631 {__nc = __v.__cc; return *this;}
632
633 _LIBCPP_INLINE_VISIBILITY
634 __value_type& operator=(__value_type&& __v)
Eric Fiselierd06276b2016-03-31 02:15:15 +0000635 {__nc = _VSTD::move(__v.__nc); return *this;}
Howard Hinnant89f8b792013-09-30 19:08:22 +0000636
Eric Fiselierd06276b2016-03-31 02:15:15 +0000637 template <class _ValueTp,
638 class = typename enable_if<
639 __is_same_uncvref<_ValueTp, value_type>::value
640 >::type
641 >
Howard Hinnant89f8b792013-09-30 19:08:22 +0000642 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +0000643 __value_type& operator=(_ValueTp&& __v) {
644 __nc = _VSTD::forward<_ValueTp>(__v); return *this;
645 }
646
647private:
648 __value_type() _LIBCPP_EQUAL_DELETE;
649 ~__value_type() _LIBCPP_EQUAL_DELETE;
650 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
651 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000652};
653
654#else
655
656template <class _Key, class _Tp>
657struct __value_type
658{
659 typedef _Key key_type;
660 typedef _Tp mapped_type;
661 typedef pair<const key_type, mapped_type> value_type;
662
663 value_type __cc;
664
Eric Fiselierd06276b2016-03-31 02:15:15 +0000665private:
666 __value_type();
667 __value_type(__value_type const&);
668 __value_type& operator=(__value_type const&);
669 ~__value_type();
Howard Hinnant89f8b792013-09-30 19:08:22 +0000670};
671
672#endif
673
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000674template <class _Tp>
675struct __extract_key_value_types;
676
677template <class _Key, class _Tp>
678struct __extract_key_value_types<__value_type<_Key, _Tp> >
679{
680 typedef _Key const __key_type;
681 typedef _Tp __mapped_type;
682};
683
Howard Hinnantc51e1022010-05-11 19:42:16 +0000684template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000685class _LIBCPP_TYPE_VIS_ONLY __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000686{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000687 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
688 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
689
Howard Hinnantc51e1022010-05-11 19:42:16 +0000690 _TreeIterator __i_;
691
Howard Hinnantc51e1022010-05-11 19:42:16 +0000692public:
693 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000694 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000695 typedef typename _TreeIterator::difference_type difference_type;
696 typedef value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000697 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000698
Howard Hinnant756c69b2010-09-22 16:48:34 +0000699 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000700 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000701
Howard Hinnant756c69b2010-09-22 16:48:34 +0000702 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000703 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000704
Howard Hinnant756c69b2010-09-22 16:48:34 +0000705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000706 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000707 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000708 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000709
Howard Hinnant756c69b2010-09-22 16:48:34 +0000710 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000711 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000712 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000713 __map_iterator operator++(int)
714 {
715 __map_iterator __t(*this);
716 ++(*this);
717 return __t;
718 }
719
Howard Hinnant756c69b2010-09-22 16:48:34 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000721 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000722 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000723 __map_iterator operator--(int)
724 {
725 __map_iterator __t(*this);
726 --(*this);
727 return __t;
728 }
729
Howard Hinnant756c69b2010-09-22 16:48:34 +0000730 friend _LIBCPP_INLINE_VISIBILITY
731 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000732 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000733 friend
734 _LIBCPP_INLINE_VISIBILITY
735 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000736 {return __x.__i_ != __y.__i_;}
737
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000738 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
739 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
740 template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000741};
742
743template <class _TreeIterator>
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000744class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000745{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000746 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
747 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
748
Howard Hinnantc51e1022010-05-11 19:42:16 +0000749 _TreeIterator __i_;
750
Howard Hinnantc51e1022010-05-11 19:42:16 +0000751public:
752 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000753 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000754 typedef typename _TreeIterator::difference_type difference_type;
755 typedef const value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000756 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000757
Howard Hinnant756c69b2010-09-22 16:48:34 +0000758 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000759 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000760
Howard Hinnant756c69b2010-09-22 16:48:34 +0000761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000762 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000763 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000764 __map_const_iterator(__map_iterator<
765 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
766 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000767
Howard Hinnant756c69b2010-09-22 16:48:34 +0000768 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000769 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000770 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000771 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000772
Howard Hinnant756c69b2010-09-22 16:48:34 +0000773 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000774 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000776 __map_const_iterator operator++(int)
777 {
778 __map_const_iterator __t(*this);
779 ++(*this);
780 return __t;
781 }
782
Howard Hinnant756c69b2010-09-22 16:48:34 +0000783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000786 __map_const_iterator operator--(int)
787 {
788 __map_const_iterator __t(*this);
789 --(*this);
790 return __t;
791 }
792
Howard Hinnant756c69b2010-09-22 16:48:34 +0000793 friend _LIBCPP_INLINE_VISIBILITY
794 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000795 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000796 friend _LIBCPP_INLINE_VISIBILITY
797 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000798 {return __x.__i_ != __y.__i_;}
799
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000800 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
801 template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
802 template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000803};
804
805template <class _Key, class _Tp, class _Compare = less<_Key>,
806 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000807class _LIBCPP_TYPE_VIS_ONLY map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000808{
809public:
810 // types:
811 typedef _Key key_type;
812 typedef _Tp mapped_type;
813 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000814 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000815 typedef _Compare key_compare;
816 typedef _Allocator allocator_type;
817 typedef value_type& reference;
818 typedef const value_type& const_reference;
819
Marshall Clow5128cf32015-11-26 01:24:04 +0000820 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
821 "Allocator::value_type must be same type as value_type");
822
Howard Hinnanta37d3cf2013-08-12 18:38:34 +0000823 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000824 : public binary_function<value_type, value_type, bool>
825 {
826 friend class map;
827 protected:
828 key_compare comp;
829
Howard Hinnant756c69b2010-09-22 16:48:34 +0000830 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000831 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000832 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000833 bool operator()(const value_type& __x, const value_type& __y) const
834 {return comp(__x.first, __y.first);}
835 };
836
837private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000838
Howard Hinnant89f8b792013-09-30 19:08:22 +0000839 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000840 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +0000841 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
842 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000843 typedef __tree<__value_type, __vc, __allocator_type> __base;
844 typedef typename __base::__node_traits __node_traits;
845 typedef allocator_traits<allocator_type> __alloc_traits;
846
847 __base __tree_;
848
849public:
850 typedef typename __alloc_traits::pointer pointer;
851 typedef typename __alloc_traits::const_pointer const_pointer;
852 typedef typename __alloc_traits::size_type size_type;
853 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000854 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000855 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000856 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
857 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000858
Howard Hinnant756c69b2010-09-22 16:48:34 +0000859 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000860 map()
861 _NOEXCEPT_(
862 is_nothrow_default_constructible<allocator_type>::value &&
863 is_nothrow_default_constructible<key_compare>::value &&
864 is_nothrow_copy_constructible<key_compare>::value)
865 : __tree_(__vc(key_compare())) {}
866
867 _LIBCPP_INLINE_VISIBILITY
868 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000869 _NOEXCEPT_(
870 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000871 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000872 : __tree_(__vc(__comp)) {}
873
Howard Hinnant756c69b2010-09-22 16:48:34 +0000874 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000875 explicit map(const key_compare& __comp, const allocator_type& __a)
876 : __tree_(__vc(__comp), __a) {}
877
878 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000880 map(_InputIterator __f, _InputIterator __l,
881 const key_compare& __comp = key_compare())
882 : __tree_(__vc(__comp))
883 {
884 insert(__f, __l);
885 }
886
887 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000889 map(_InputIterator __f, _InputIterator __l,
890 const key_compare& __comp, const allocator_type& __a)
891 : __tree_(__vc(__comp), __a)
892 {
893 insert(__f, __l);
894 }
895
Marshall Clow300abfb2013-09-11 01:15:47 +0000896#if _LIBCPP_STD_VER > 11
897 template <class _InputIterator>
898 _LIBCPP_INLINE_VISIBILITY
899 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
900 : map(__f, __l, key_compare(), __a) {}
901#endif
902
Howard Hinnant756c69b2010-09-22 16:48:34 +0000903 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000904 map(const map& __m)
905 : __tree_(__m.__tree_)
906 {
907 insert(__m.begin(), __m.end());
908 }
909
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000910 _LIBCPP_INLINE_VISIBILITY
911 map& operator=(const map& __m)
912 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000913#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000914 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000915#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +0000916 if (this != &__m) {
917 __tree_.clear();
918 __tree_.value_comp() = __m.__tree_.value_comp();
919 __tree_.__copy_assign_alloc(__m.__tree_);
920 insert(__m.begin(), __m.end());
921 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000922#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000923 return *this;
924 }
925
Howard Hinnant74279a52010-09-04 23:28:19 +0000926#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +0000927
Howard Hinnant756c69b2010-09-22 16:48:34 +0000928 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000929 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000930 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000931 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000932 {
933 }
934
935 map(map&& __m, const allocator_type& __a);
936
Howard Hinnant756c69b2010-09-22 16:48:34 +0000937 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +0000938 map& operator=(map&& __m)
939 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
940 {
941 __tree_ = _VSTD::move(__m.__tree_);
942 return *this;
943 }
944
945#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
946
947#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
948
949 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000950 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
951 : __tree_(__vc(__comp))
952 {
953 insert(__il.begin(), __il.end());
954 }
955
Howard Hinnant756c69b2010-09-22 16:48:34 +0000956 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000957 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
958 : __tree_(__vc(__comp), __a)
959 {
960 insert(__il.begin(), __il.end());
961 }
962
Marshall Clow300abfb2013-09-11 01:15:47 +0000963#if _LIBCPP_STD_VER > 11
964 _LIBCPP_INLINE_VISIBILITY
965 map(initializer_list<value_type> __il, const allocator_type& __a)
966 : map(__il, key_compare(), __a) {}
967#endif
968
Howard Hinnant756c69b2010-09-22 16:48:34 +0000969 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000970 map& operator=(initializer_list<value_type> __il)
971 {
972 __tree_.__assign_unique(__il.begin(), __il.end());
973 return *this;
974 }
975
Howard Hinnant33711792011-08-12 21:56:02 +0000976#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +0000977
Howard Hinnant756c69b2010-09-22 16:48:34 +0000978 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979 explicit map(const allocator_type& __a)
980 : __tree_(__a)
981 {
982 }
983
Howard Hinnant756c69b2010-09-22 16:48:34 +0000984 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000985 map(const map& __m, const allocator_type& __a)
986 : __tree_(__m.__tree_.value_comp(), __a)
987 {
988 insert(__m.begin(), __m.end());
989 }
990
Howard Hinnant756c69b2010-09-22 16:48:34 +0000991 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000992 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000993 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000994 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000995 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000996 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000997 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000998 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000999
Howard Hinnant756c69b2010-09-22 16:48:34 +00001000 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001001 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001002 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001003 const_reverse_iterator rbegin() const _NOEXCEPT
1004 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001005 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001006 reverse_iterator rend() _NOEXCEPT
1007 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001008 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001009 const_reverse_iterator rend() const _NOEXCEPT
1010 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001011
Howard Hinnant756c69b2010-09-22 16:48:34 +00001012 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001013 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001014 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001015 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001016 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001017 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001018 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001019 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001020
Howard Hinnant756c69b2010-09-22 16:48:34 +00001021 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001022 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001023 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001024 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001025 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001026 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001027
1028 mapped_type& operator[](const key_type& __k);
Howard Hinnant74279a52010-09-04 23:28:19 +00001029#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001030 mapped_type& operator[](key_type&& __k);
1031#endif
1032
1033 mapped_type& at(const key_type& __k);
1034 const mapped_type& at(const key_type& __k) const;
1035
Howard Hinnant756c69b2010-09-22 16:48:34 +00001036 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001037 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001038 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001039 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001040 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001041 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1042
Eric Fiselierd06276b2016-03-31 02:15:15 +00001043#ifndef _LIBCPP_CXX03_LANG
1044 template <class ..._Args>
1045 _LIBCPP_INLINE_VISIBILITY
1046 pair<iterator, bool> emplace(_Args&& ...__args) {
1047 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1048 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001049
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001050 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001051 _LIBCPP_INLINE_VISIBILITY
1052 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1053 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1054 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001055
Howard Hinnantc834c512011-11-29 18:15:50 +00001056 template <class _Pp,
1057 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001058 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001059 pair<iterator, bool> insert(_Pp&& __p)
1060 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001061
Howard Hinnantc834c512011-11-29 18:15:50 +00001062 template <class _Pp,
1063 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001064 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001065 iterator insert(const_iterator __pos, _Pp&& __p)
1066 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001067
Eric Fiselierd06276b2016-03-31 02:15:15 +00001068#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001069
Howard Hinnant756c69b2010-09-22 16:48:34 +00001070 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001071 pair<iterator, bool>
1072 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1073
Howard Hinnant756c69b2010-09-22 16:48:34 +00001074 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001075 iterator
1076 insert(const_iterator __p, const value_type& __v)
1077 {return __tree_.__insert_unique(__p.__i_, __v);}
1078
Marshall Clowd430d022016-01-05 19:32:41 +00001079#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Eric Fiselierd06276b2016-03-31 02:15:15 +00001080 // TODO(EricWF): These functions are C++17 only but they should probably
1081 // be exposed in C++11.
Marshall Clowd430d022016-01-05 19:32:41 +00001082 _LIBCPP_INLINE_VISIBILITY
1083 pair<iterator, bool>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001084 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001085
1086 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001087 iterator insert(const_iterator __p, value_type&& __v)
1088 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001089#endif
1090
Howard Hinnantc51e1022010-05-11 19:42:16 +00001091 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001092 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001093 void insert(_InputIterator __f, _InputIterator __l)
1094 {
1095 for (const_iterator __e = cend(); __f != __l; ++__f)
1096 insert(__e.__i_, *__f);
1097 }
1098
Howard Hinnant33711792011-08-12 21:56:02 +00001099#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1100
Howard Hinnant756c69b2010-09-22 16:48:34 +00001101 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001102 void insert(initializer_list<value_type> __il)
1103 {insert(__il.begin(), __il.end());}
1104
Howard Hinnant33711792011-08-12 21:56:02 +00001105#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1106
Marshall Clow3223db82015-07-07 03:37:33 +00001107#if _LIBCPP_STD_VER > 14
1108#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1109#ifndef _LIBCPP_HAS_NO_VARIADICS
1110 template <class... _Args>
1111 _LIBCPP_INLINE_VISIBILITY
1112 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1113 {
1114 iterator __p = lower_bound(__k);
1115 if ( __p != end() && !key_comp()(__k, __p->first))
1116 return _VSTD::make_pair(__p, false);
1117 else
1118 return _VSTD::make_pair(
1119 emplace_hint(__p,
1120 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1121 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1122 true);
1123 }
1124
1125 template <class... _Args>
1126 _LIBCPP_INLINE_VISIBILITY
1127 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1128 {
1129 iterator __p = lower_bound(__k);
1130 if ( __p != end() && !key_comp()(__k, __p->first))
1131 return _VSTD::make_pair(__p, false);
1132 else
1133 return _VSTD::make_pair(
1134 emplace_hint(__p,
1135 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1136 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...)),
1137 true);
1138 }
1139
1140 template <class... _Args>
1141 _LIBCPP_INLINE_VISIBILITY
1142 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1143 {
1144 iterator __p = lower_bound(__k);
1145 if ( __p != end() && !key_comp()(__k, __p->first))
1146 return __p;
1147 else
1148 return emplace_hint(__p,
1149 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(__k),
1150 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1151 }
1152
1153 template <class... _Args>
1154 _LIBCPP_INLINE_VISIBILITY
1155 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1156 {
1157 iterator __p = lower_bound(__k);
1158 if ( __p != end() && !key_comp()(__k, __p->first))
1159 return __p;
1160 else
1161 return emplace_hint(__p,
1162 _VSTD::piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__k)),
1163 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
1164 }
1165
1166 template <class _Vp>
1167 _LIBCPP_INLINE_VISIBILITY
1168 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1169 {
1170 iterator __p = lower_bound(__k);
1171 if ( __p != end() && !key_comp()(__k, __p->first))
1172 {
1173 __p->second = _VSTD::forward<_Vp>(__v);
1174 return _VSTD::make_pair(__p, false);
1175 }
1176 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1177 }
1178
1179 template <class _Vp>
1180 _LIBCPP_INLINE_VISIBILITY
1181 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1182 {
1183 iterator __p = lower_bound(__k);
1184 if ( __p != end() && !key_comp()(__k, __p->first))
1185 {
1186 __p->second = _VSTD::forward<_Vp>(__v);
1187 return _VSTD::make_pair(__p, false);
1188 }
1189 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1190 }
1191
1192 template <class _Vp>
1193 _LIBCPP_INLINE_VISIBILITY
1194 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1195 {
1196 iterator __p = lower_bound(__k);
1197 if ( __p != end() && !key_comp()(__k, __p->first))
1198 {
1199 __p->second = _VSTD::forward<_Vp>(__v);
1200 return __p;
1201 }
1202 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1203 }
1204
1205 template <class _Vp>
1206 _LIBCPP_INLINE_VISIBILITY
1207 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1208 {
1209 iterator __p = lower_bound(__k);
1210 if ( __p != end() && !key_comp()(__k, __p->first))
1211 {
1212 __p->second = _VSTD::forward<_Vp>(__v);
1213 return __p;
1214 }
1215 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1216 }
1217#endif
1218#endif
1219#endif
1220
Howard Hinnant756c69b2010-09-22 16:48:34 +00001221 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001222 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001223 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001224 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1225 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001226 size_type erase(const key_type& __k)
1227 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001228 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001229 iterator erase(const_iterator __f, const_iterator __l)
1230 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001231 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001232 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001233
Howard Hinnant756c69b2010-09-22 16:48:34 +00001234 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001235 void swap(map& __m)
1236 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1237 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001238
Howard Hinnant756c69b2010-09-22 16:48:34 +00001239 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001240 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001241 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001242 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001243#if _LIBCPP_STD_VER > 11
1244 template <typename _K2>
1245 _LIBCPP_INLINE_VISIBILITY
1246 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1247 find(const _K2& __k) {return __tree_.find(__k);}
1248 template <typename _K2>
1249 _LIBCPP_INLINE_VISIBILITY
1250 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1251 find(const _K2& __k) const {return __tree_.find(__k);}
1252#endif
1253
Howard Hinnant756c69b2010-09-22 16:48:34 +00001254 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001255 size_type count(const key_type& __k) const
1256 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001257#if _LIBCPP_STD_VER > 11
1258 template <typename _K2>
1259 _LIBCPP_INLINE_VISIBILITY
1260 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00001261 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001262#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001263 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001264 iterator lower_bound(const key_type& __k)
1265 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001266 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001267 const_iterator lower_bound(const key_type& __k) const
1268 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001269#if _LIBCPP_STD_VER > 11
1270 template <typename _K2>
1271 _LIBCPP_INLINE_VISIBILITY
1272 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1273 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1274
1275 template <typename _K2>
1276 _LIBCPP_INLINE_VISIBILITY
1277 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1278 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1279#endif
1280
Howard Hinnant756c69b2010-09-22 16:48:34 +00001281 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001282 iterator upper_bound(const key_type& __k)
1283 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001284 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001285 const_iterator upper_bound(const key_type& __k) const
1286 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001287#if _LIBCPP_STD_VER > 11
1288 template <typename _K2>
1289 _LIBCPP_INLINE_VISIBILITY
1290 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1291 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1292 template <typename _K2>
1293 _LIBCPP_INLINE_VISIBILITY
1294 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1295 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1296#endif
1297
Howard Hinnant756c69b2010-09-22 16:48:34 +00001298 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001299 pair<iterator,iterator> equal_range(const key_type& __k)
1300 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001301 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001302 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1303 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001304#if _LIBCPP_STD_VER > 11
1305 template <typename _K2>
1306 _LIBCPP_INLINE_VISIBILITY
1307 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1308 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1309 template <typename _K2>
1310 _LIBCPP_INLINE_VISIBILITY
1311 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1312 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1313#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001314
1315private:
1316 typedef typename __base::__node __node;
1317 typedef typename __base::__node_allocator __node_allocator;
1318 typedef typename __base::__node_pointer __node_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001319 typedef typename __base::__node_base_pointer __node_base_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001320
Howard Hinnantc834c512011-11-29 18:15:50 +00001321 typedef __map_node_destructor<__node_allocator> _Dp;
1322 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001323
Eric Fiselierd06276b2016-03-31 02:15:15 +00001324#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantac7e7482013-07-04 20:59:16 +00001325 __node_holder __construct_node_with_key(key_type&& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001326#endif
Eric Fiselierd06276b2016-03-31 02:15:15 +00001327
Howard Hinnantac7e7482013-07-04 20:59:16 +00001328 __node_holder __construct_node_with_key(const key_type& __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001329
Eric Fiseliera92b0732016-02-20 07:12:17 +00001330 __node_base_pointer const&
1331 __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const;
1332
1333 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001334 __node_base_pointer&
Eric Fiseliera92b0732016-02-20 07:12:17 +00001335 __find_equal_key(__node_base_pointer& __parent, const key_type& __k) {
1336 map const* __const_this = this;
1337 return const_cast<__node_base_pointer&>(
1338 __const_this->__find_equal_key(__parent, __k));
1339 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001340};
1341
Eric Fiseliera92b0732016-02-20 07:12:17 +00001342
1343// Find __k
1344// Set __parent to parent of null leaf and
1345// return reference to null leaf iv __k does not exist.
Howard Hinnantc51e1022010-05-11 19:42:16 +00001346// If __k exists, set parent to node of __k and return reference to node of __k
1347template <class _Key, class _Tp, class _Compare, class _Allocator>
Eric Fiseliera92b0732016-02-20 07:12:17 +00001348typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer const&
Howard Hinnantc51e1022010-05-11 19:42:16 +00001349map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
Eric Fiseliera92b0732016-02-20 07:12:17 +00001350 const key_type& __k) const
Howard Hinnantc51e1022010-05-11 19:42:16 +00001351{
1352 __node_pointer __nd = __tree_.__root();
1353 if (__nd != nullptr)
1354 {
1355 while (true)
1356 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001357 if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001358 {
1359 if (__nd->__left_ != nullptr)
1360 __nd = static_cast<__node_pointer>(__nd->__left_);
1361 else
1362 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001363 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001364 return __parent->__left_;
1365 }
1366 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001367 else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001368 {
1369 if (__nd->__right_ != nullptr)
1370 __nd = static_cast<__node_pointer>(__nd->__right_);
1371 else
1372 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001373 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001374 return __parent->__right_;
1375 }
1376 }
1377 else
1378 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001379 __parent = static_cast<__node_base_pointer>(__nd);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001380 return __parent;
1381 }
1382 }
1383 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001384 __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001385 return __parent->__left_;
1386}
1387
Eric Fiselierd06276b2016-03-31 02:15:15 +00001388#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001389
1390template <class _Key, class _Tp, class _Compare, class _Allocator>
1391map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001392 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001393{
1394 if (__a != __m.get_allocator())
1395 {
1396 const_iterator __e = cend();
1397 while (!__m.empty())
1398 __tree_.__insert_unique(__e.__i_,
Eric Fiselierd06276b2016-03-31 02:15:15 +00001399 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001400 }
1401}
1402
Howard Hinnantc51e1022010-05-11 19:42:16 +00001403
1404template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnantac7e7482013-07-04 20:59:16 +00001405typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1406map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(key_type&& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001407{
1408 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001409 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnantac7e7482013-07-04 20:59:16 +00001410 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), _VSTD::move(__k));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001411 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001412 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001413 __h.get_deleter().__second_constructed = true;
Howard Hinnanta31e9682013-08-22 18:29:50 +00001414 return __h;
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001415}
1416
Eric Fiselierd06276b2016-03-31 02:15:15 +00001417#endif // !_LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001418
1419template <class _Key, class _Tp, class _Compare, class _Allocator>
1420typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001421map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001422{
1423 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001424 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001425 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001426 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001427 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001428 __h.get_deleter().__second_constructed = true;
Dimitry Andric830fb602015-08-19 06:43:33 +00001429 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnantc51e1022010-05-11 19:42:16 +00001430}
1431
Howard Hinnantc51e1022010-05-11 19:42:16 +00001432template <class _Key, class _Tp, class _Compare, class _Allocator>
1433_Tp&
1434map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1435{
1436 __node_base_pointer __parent;
1437 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1438 __node_pointer __r = static_cast<__node_pointer>(__child);
1439 if (__child == nullptr)
1440 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001441 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001442 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001443 __r = __h.release();
1444 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001445 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001446}
1447
Howard Hinnant74279a52010-09-04 23:28:19 +00001448#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001449
1450template <class _Key, class _Tp, class _Compare, class _Allocator>
1451_Tp&
1452map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1453{
1454 __node_base_pointer __parent;
1455 __node_base_pointer& __child = __find_equal_key(__parent, __k);
1456 __node_pointer __r = static_cast<__node_pointer>(__child);
1457 if (__child == nullptr)
1458 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001459 __node_holder __h = __construct_node_with_key(_VSTD::move(__k));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001460 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001461 __r = __h.release();
1462 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001463 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001464}
1465
Howard Hinnant74279a52010-09-04 23:28:19 +00001466#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001467
1468template <class _Key, class _Tp, class _Compare, class _Allocator>
1469_Tp&
1470map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1471{
1472 __node_base_pointer __parent;
1473 __node_base_pointer& __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001474#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001475 if (__child == nullptr)
1476 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001477#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001478 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001479}
1480
1481template <class _Key, class _Tp, class _Compare, class _Allocator>
1482const _Tp&
1483map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1484{
Eric Fiseliera92b0732016-02-20 07:12:17 +00001485 __node_base_pointer __parent;
1486 __node_base_pointer __child = __find_equal_key(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001487#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001488 if (__child == nullptr)
1489 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001490#endif // _LIBCPP_NO_EXCEPTIONS
Eric Fiseliera92b0732016-02-20 07:12:17 +00001491 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001492}
1493
Howard Hinnantc51e1022010-05-11 19:42:16 +00001494
1495template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001496inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001497bool
1498operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1499 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1500{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001501 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001502}
1503
1504template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001505inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001506bool
1507operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1508 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1509{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001510 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001511}
1512
1513template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001514inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001515bool
1516operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1517 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1518{
1519 return !(__x == __y);
1520}
1521
1522template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001523inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001524bool
1525operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1526 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1527{
1528 return __y < __x;
1529}
1530
1531template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001532inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001533bool
1534operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1535 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1536{
1537 return !(__x < __y);
1538}
1539
1540template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001541inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001542bool
1543operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1544 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1545{
1546 return !(__y < __x);
1547}
1548
1549template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001550inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001551void
1552swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1553 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001554 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001555{
1556 __x.swap(__y);
1557}
1558
1559template <class _Key, class _Tp, class _Compare = less<_Key>,
1560 class _Allocator = allocator<pair<const _Key, _Tp> > >
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001561class _LIBCPP_TYPE_VIS_ONLY multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001562{
1563public:
1564 // types:
1565 typedef _Key key_type;
1566 typedef _Tp mapped_type;
1567 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001568 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001569 typedef _Compare key_compare;
1570 typedef _Allocator allocator_type;
1571 typedef value_type& reference;
1572 typedef const value_type& const_reference;
1573
Marshall Clow5128cf32015-11-26 01:24:04 +00001574 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1575 "Allocator::value_type must be same type as value_type");
1576
Howard Hinnanta37d3cf2013-08-12 18:38:34 +00001577 class _LIBCPP_TYPE_VIS_ONLY value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001578 : public binary_function<value_type, value_type, bool>
1579 {
1580 friend class multimap;
1581 protected:
1582 key_compare comp;
1583
Howard Hinnant756c69b2010-09-22 16:48:34 +00001584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001585 value_compare(key_compare c) : comp(c) {}
1586 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001588 bool operator()(const value_type& __x, const value_type& __y) const
1589 {return comp(__x.first, __y.first);}
1590 };
1591
1592private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001593
Howard Hinnant89f8b792013-09-30 19:08:22 +00001594 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001595 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +00001596 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1597 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001598 typedef __tree<__value_type, __vc, __allocator_type> __base;
1599 typedef typename __base::__node_traits __node_traits;
1600 typedef allocator_traits<allocator_type> __alloc_traits;
1601
1602 __base __tree_;
1603
1604public:
1605 typedef typename __alloc_traits::pointer pointer;
1606 typedef typename __alloc_traits::const_pointer const_pointer;
1607 typedef typename __alloc_traits::size_type size_type;
1608 typedef typename __alloc_traits::difference_type difference_type;
1609 typedef __map_iterator<typename __base::iterator> iterator;
1610 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001611 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1612 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001613
Howard Hinnant756c69b2010-09-22 16:48:34 +00001614 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001615 multimap()
1616 _NOEXCEPT_(
1617 is_nothrow_default_constructible<allocator_type>::value &&
1618 is_nothrow_default_constructible<key_compare>::value &&
1619 is_nothrow_copy_constructible<key_compare>::value)
1620 : __tree_(__vc(key_compare())) {}
1621
1622 _LIBCPP_INLINE_VISIBILITY
1623 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001624 _NOEXCEPT_(
1625 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001626 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001627 : __tree_(__vc(__comp)) {}
1628
Howard Hinnant756c69b2010-09-22 16:48:34 +00001629 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001630 explicit multimap(const key_compare& __comp, const allocator_type& __a)
1631 : __tree_(__vc(__comp), __a) {}
1632
1633 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001634 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001635 multimap(_InputIterator __f, _InputIterator __l,
1636 const key_compare& __comp = key_compare())
1637 : __tree_(__vc(__comp))
1638 {
1639 insert(__f, __l);
1640 }
1641
1642 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001643 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001644 multimap(_InputIterator __f, _InputIterator __l,
1645 const key_compare& __comp, const allocator_type& __a)
1646 : __tree_(__vc(__comp), __a)
1647 {
1648 insert(__f, __l);
1649 }
1650
Marshall Clow300abfb2013-09-11 01:15:47 +00001651#if _LIBCPP_STD_VER > 11
1652 template <class _InputIterator>
1653 _LIBCPP_INLINE_VISIBILITY
1654 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1655 : multimap(__f, __l, key_compare(), __a) {}
1656#endif
1657
Howard Hinnant756c69b2010-09-22 16:48:34 +00001658 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001659 multimap(const multimap& __m)
1660 : __tree_(__m.__tree_.value_comp(),
1661 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1662 {
1663 insert(__m.begin(), __m.end());
1664 }
1665
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001666 _LIBCPP_INLINE_VISIBILITY
1667 multimap& operator=(const multimap& __m)
1668 {
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001669#if __cplusplus >= 201103L
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001670 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001671#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001672 if (this != &__m) {
1673 __tree_.clear();
1674 __tree_.value_comp() = __m.__tree_.value_comp();
1675 __tree_.__copy_assign_alloc(__m.__tree_);
1676 insert(__m.begin(), __m.end());
1677 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001678#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001679 return *this;
1680 }
1681
Howard Hinnant74279a52010-09-04 23:28:19 +00001682#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc51e1022010-05-11 19:42:16 +00001683
Howard Hinnant756c69b2010-09-22 16:48:34 +00001684 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001685 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001686 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001687 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001688 {
1689 }
1690
1691 multimap(multimap&& __m, const allocator_type& __a);
1692
Howard Hinnant756c69b2010-09-22 16:48:34 +00001693 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001694 multimap& operator=(multimap&& __m)
1695 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1696 {
1697 __tree_ = _VSTD::move(__m.__tree_);
1698 return *this;
1699 }
1700
1701#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
1702
1703#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1704
1705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1707 : __tree_(__vc(__comp))
1708 {
1709 insert(__il.begin(), __il.end());
1710 }
1711
Howard Hinnant756c69b2010-09-22 16:48:34 +00001712 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001713 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
1714 : __tree_(__vc(__comp), __a)
1715 {
1716 insert(__il.begin(), __il.end());
1717 }
1718
Marshall Clow300abfb2013-09-11 01:15:47 +00001719#if _LIBCPP_STD_VER > 11
1720 _LIBCPP_INLINE_VISIBILITY
1721 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1722 : multimap(__il, key_compare(), __a) {}
1723#endif
1724
Howard Hinnant756c69b2010-09-22 16:48:34 +00001725 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001726 multimap& operator=(initializer_list<value_type> __il)
1727 {
1728 __tree_.__assign_multi(__il.begin(), __il.end());
1729 return *this;
1730 }
Howard Hinnant33711792011-08-12 21:56:02 +00001731
1732#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001733
Howard Hinnant756c69b2010-09-22 16:48:34 +00001734 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001735 explicit multimap(const allocator_type& __a)
1736 : __tree_(__a)
1737 {
1738 }
1739
Howard Hinnant756c69b2010-09-22 16:48:34 +00001740 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001741 multimap(const multimap& __m, const allocator_type& __a)
1742 : __tree_(__m.__tree_.value_comp(), __a)
1743 {
1744 insert(__m.begin(), __m.end());
1745 }
1746
Howard Hinnant756c69b2010-09-22 16:48:34 +00001747 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001748 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001749 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001750 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001751 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001752 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001753 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001754 const_iterator end() const _NOEXCEPT {return __tree_.end();}
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 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001758 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001759 const_reverse_iterator rbegin() const _NOEXCEPT
1760 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001761 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001762 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001763 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001764 const_reverse_iterator rend() const _NOEXCEPT
1765 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001766
Howard Hinnant756c69b2010-09-22 16:48:34 +00001767 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001768 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001769 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001770 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001771 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001772 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001773 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001774 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001775
Howard Hinnant756c69b2010-09-22 16:48:34 +00001776 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001777 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001778 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001779 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001780 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001781 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001782
Howard Hinnant756c69b2010-09-22 16:48:34 +00001783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001784 allocator_type get_allocator() const _NOEXCEPT {return __tree_.__alloc();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001785 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001786 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001788 value_compare value_comp() const
1789 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001790
Eric Fiselierd06276b2016-03-31 02:15:15 +00001791#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00001792
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001793 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001794 _LIBCPP_INLINE_VISIBILITY
1795 iterator emplace(_Args&& ...__args) {
1796 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1797 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001798
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001799 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001800 _LIBCPP_INLINE_VISIBILITY
1801 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1802 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1803 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001804
Howard Hinnantc834c512011-11-29 18:15:50 +00001805 template <class _Pp,
1806 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001807 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001808 iterator insert(_Pp&& __p)
1809 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001810
Howard Hinnantc834c512011-11-29 18:15:50 +00001811 template <class _Pp,
1812 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001813 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001814 iterator insert(const_iterator __pos, _Pp&& __p)
1815 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001816
Eric Fiselierd06276b2016-03-31 02:15:15 +00001817#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001818
Howard Hinnant756c69b2010-09-22 16:48:34 +00001819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001820 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1821
Howard Hinnant756c69b2010-09-22 16:48:34 +00001822 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001823 iterator insert(const_iterator __p, const value_type& __v)
1824 {return __tree_.__insert_multi(__p.__i_, __v);}
1825
Marshall Clowd430d022016-01-05 19:32:41 +00001826#if _LIBCPP_STD_VER > 14 && !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES)
Eric Fiselierd06276b2016-03-31 02:15:15 +00001827 // TODO(EricWF): These functions are C++17 only but they should probably
1828 // be exposed in C++11.
Marshall Clowd430d022016-01-05 19:32:41 +00001829 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001830 iterator insert(value_type&& __v)
1831 {return __tree_.__insert_multi(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001832
1833 _LIBCPP_INLINE_VISIBILITY
1834 iterator insert(const_iterator __p, value_type&& __v)
Eric Fiselierd06276b2016-03-31 02:15:15 +00001835 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001836#endif
1837
Howard Hinnantc51e1022010-05-11 19:42:16 +00001838 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001839 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001840 void insert(_InputIterator __f, _InputIterator __l)
1841 {
1842 for (const_iterator __e = cend(); __f != __l; ++__f)
1843 __tree_.__insert_multi(__e.__i_, *__f);
1844 }
1845
Howard Hinnant33711792011-08-12 21:56:02 +00001846#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1847
Howard Hinnant756c69b2010-09-22 16:48:34 +00001848 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001849 void insert(initializer_list<value_type> __il)
1850 {insert(__il.begin(), __il.end());}
1851
Howard Hinnant33711792011-08-12 21:56:02 +00001852#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1853
Howard Hinnant756c69b2010-09-22 16:48:34 +00001854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001855 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001856 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001857 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1858 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001859 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001860 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001861 iterator erase(const_iterator __f, const_iterator __l)
1862 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001863 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001864 void clear() {__tree_.clear();}
1865
Howard Hinnant756c69b2010-09-22 16:48:34 +00001866 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001867 void swap(multimap& __m)
1868 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1869 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001870
Howard Hinnant756c69b2010-09-22 16:48:34 +00001871 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001872 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001874 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001875#if _LIBCPP_STD_VER > 11
1876 template <typename _K2>
1877 _LIBCPP_INLINE_VISIBILITY
1878 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1879 find(const _K2& __k) {return __tree_.find(__k);}
1880 template <typename _K2>
1881 _LIBCPP_INLINE_VISIBILITY
1882 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1883 find(const _K2& __k) const {return __tree_.find(__k);}
1884#endif
1885
Howard Hinnant756c69b2010-09-22 16:48:34 +00001886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001887 size_type count(const key_type& __k) const
1888 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001889#if _LIBCPP_STD_VER > 11
1890 template <typename _K2>
1891 _LIBCPP_INLINE_VISIBILITY
1892 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00001893 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001894#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001895 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001896 iterator lower_bound(const key_type& __k)
1897 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001899 const_iterator lower_bound(const key_type& __k) const
1900 {return __tree_.lower_bound(__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,iterator>::type
1905 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1906
1907 template <typename _K2>
1908 _LIBCPP_INLINE_VISIBILITY
1909 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1910 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1911#endif
1912
Howard Hinnant756c69b2010-09-22 16:48:34 +00001913 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001914 iterator upper_bound(const key_type& __k)
1915 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001916 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001917 const_iterator upper_bound(const key_type& __k) const
1918 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001919#if _LIBCPP_STD_VER > 11
1920 template <typename _K2>
1921 _LIBCPP_INLINE_VISIBILITY
1922 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1923 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1924 template <typename _K2>
1925 _LIBCPP_INLINE_VISIBILITY
1926 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1927 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1928#endif
1929
Howard Hinnant756c69b2010-09-22 16:48:34 +00001930 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001931 pair<iterator,iterator> equal_range(const key_type& __k)
1932 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001933 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001934 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1935 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001936#if _LIBCPP_STD_VER > 11
1937 template <typename _K2>
1938 _LIBCPP_INLINE_VISIBILITY
1939 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1940 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1941 template <typename _K2>
1942 _LIBCPP_INLINE_VISIBILITY
1943 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1944 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1945#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001946
1947private:
1948 typedef typename __base::__node __node;
1949 typedef typename __base::__node_allocator __node_allocator;
1950 typedef typename __base::__node_pointer __node_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001951
Howard Hinnantc834c512011-11-29 18:15:50 +00001952 typedef __map_node_destructor<__node_allocator> _Dp;
1953 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001954};
1955
Eric Fiselierd06276b2016-03-31 02:15:15 +00001956#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001957template <class _Key, class _Tp, class _Compare, class _Allocator>
1958multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001959 : __tree_(_VSTD::move(__m.__tree_), __a)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001960{
1961 if (__a != __m.get_allocator())
1962 {
1963 const_iterator __e = cend();
1964 while (!__m.empty())
1965 __tree_.__insert_multi(__e.__i_,
Eric Fiselierd06276b2016-03-31 02:15:15 +00001966 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001967 }
1968}
Eric Fiselierd06276b2016-03-31 02:15:15 +00001969#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001970
1971template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001972inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001973bool
1974operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1975 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1976{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001977 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001978}
1979
1980template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001981inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001982bool
1983operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1984 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1985{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001986 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001987}
1988
1989template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001990inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001991bool
1992operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1993 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1994{
1995 return !(__x == __y);
1996}
1997
1998template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001999inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002000bool
2001operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2002 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2003{
2004 return __y < __x;
2005}
2006
2007template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002008inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002009bool
2010operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2011 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2012{
2013 return !(__x < __y);
2014}
2015
2016template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002017inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002018bool
2019operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2020 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
2021{
2022 return !(__y < __x);
2023}
2024
2025template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00002026inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00002027void
2028swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
2029 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00002030 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00002031{
2032 __x.swap(__y);
2033}
2034
2035_LIBCPP_END_NAMESPACE_STD
2036
2037#endif // _LIBCPP_MAP