blob: 952149389814498fb4b492e092bd99533eef4fcd [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 &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000165 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 &&
Eric Fiselier6bfed252016-04-21 23:38:59 +0000360 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 Fiseliera7a14ed2017-01-13 22:02:08 +0000456template <class _Key, class _CP, class _Compare, bool _IsSmall>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000457class __map_value_compare
458 : private _Compare
459{
Howard Hinnantc51e1022010-05-11 19:42:16 +0000460public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000461 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000462 __map_value_compare()
463 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
464 : _Compare() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000466 __map_value_compare(_Compare c)
467 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
468 : _Compare(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000469 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000470 const _Compare& key_comp() const _NOEXCEPT {return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000471 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000472 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000473 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000474 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000475 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000476 {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000477 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000478 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000479 {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000480 void swap(__map_value_compare&__y)
481 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
482 {
Eric Fiselier68b5f0b2017-04-13 00:34:24 +0000483 using _VSTD::swap;
484 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
Marshall Clow8982dcd2015-07-13 20:04:56 +0000485 }
Marshall Clowebb57322013-08-13 22:18:47 +0000486
487#if _LIBCPP_STD_VER > 11
488 template <typename _K2>
489 _LIBCPP_INLINE_VISIBILITY
490 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
491 operator () ( const _K2& __x, const _CP& __y ) const
492 {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
493
494 template <typename _K2>
495 _LIBCPP_INLINE_VISIBILITY
496 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
497 operator () (const _CP& __x, const _K2& __y) const
498 {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
499#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000500};
501
Howard Hinnant90b91592013-07-05 18:06:00 +0000502template <class _Key, class _CP, class _Compare>
503class __map_value_compare<_Key, _CP, _Compare, false>
Howard Hinnantc51e1022010-05-11 19:42:16 +0000504{
505 _Compare comp;
506
Howard Hinnantc51e1022010-05-11 19:42:16 +0000507public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000508 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000509 __map_value_compare()
510 _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
511 : comp() {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000512 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000513 __map_value_compare(_Compare c)
514 _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
515 : comp(c) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000517 const _Compare& key_comp() const _NOEXCEPT {return comp;}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000518
Howard Hinnant756c69b2010-09-22 16:48:34 +0000519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000520 bool operator()(const _CP& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000521 {return comp(__x.__cc.first, __y.__cc.first);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000522 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000523 bool operator()(const _CP& __x, const _Key& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000524 {return comp(__x.__cc.first, __y);}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000525 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000526 bool operator()(const _Key& __x, const _CP& __y) const
Howard Hinnant90b91592013-07-05 18:06:00 +0000527 {return comp(__x, __y.__cc.first);}
Marshall Clow8982dcd2015-07-13 20:04:56 +0000528 void swap(__map_value_compare&__y)
529 _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
530 {
531 using _VSTD::swap;
532 swap(comp, __y.comp);
533 }
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000534
Marshall Clowebb57322013-08-13 22:18:47 +0000535#if _LIBCPP_STD_VER > 11
536 template <typename _K2>
537 _LIBCPP_INLINE_VISIBILITY
538 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
539 operator () ( const _K2& __x, const _CP& __y ) const
540 {return comp (__x, __y.__cc.first);}
541
542 template <typename _K2>
543 _LIBCPP_INLINE_VISIBILITY
544 typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
545 operator () (const _CP& __x, const _K2& __y) const
546 {return comp (__x.__cc.first, __y);}
547#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +0000548};
549
Marshall Clow8982dcd2015-07-13 20:04:56 +0000550template <class _Key, class _CP, class _Compare, bool __b>
551inline _LIBCPP_INLINE_VISIBILITY
552void
553swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
554 __map_value_compare<_Key, _CP, _Compare, __b>& __y)
555 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
556{
557 __x.swap(__y);
558}
559
Howard Hinnantc51e1022010-05-11 19:42:16 +0000560template <class _Allocator>
561class __map_node_destructor
562{
563 typedef _Allocator allocator_type;
564 typedef allocator_traits<allocator_type> __alloc_traits;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000565
Howard Hinnantc51e1022010-05-11 19:42:16 +0000566public:
567 typedef typename __alloc_traits::pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000568
Eric Fiseliera00b4842016-02-20 05:28:30 +0000569private:
Howard Hinnantc51e1022010-05-11 19:42:16 +0000570 allocator_type& __na_;
571
572 __map_node_destructor& operator=(const __map_node_destructor&);
573
574public:
575 bool __first_constructed;
576 bool __second_constructed;
577
Howard Hinnant756c69b2010-09-22 16:48:34 +0000578 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000579 explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000580 : __na_(__na),
581 __first_constructed(false),
582 __second_constructed(false)
583 {}
584
Eric Fiseliera85b1282017-04-18 21:08:06 +0000585#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant756c69b2010-09-22 16:48:34 +0000586 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000587 __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000588 : __na_(__x.__na_),
589 __first_constructed(__x.__value_constructed),
590 __second_constructed(__x.__value_constructed)
591 {
592 __x.__value_constructed = false;
593 }
Eric Fiseliera85b1282017-04-18 21:08:06 +0000594#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000595
Howard Hinnant756c69b2010-09-22 16:48:34 +0000596 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000597 void operator()(pointer __p) _NOEXCEPT
Howard Hinnantc51e1022010-05-11 19:42:16 +0000598 {
599 if (__second_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000600 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000601 if (__first_constructed)
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000602 __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
Howard Hinnantc51e1022010-05-11 19:42:16 +0000603 if (__p)
604 __alloc_traits::deallocate(__na_, __p, 1);
605 }
606};
607
Howard Hinnant944510a2011-06-14 19:58:17 +0000608template <class _Key, class _Tp, class _Compare, class _Allocator>
609 class map;
610template <class _Key, class _Tp, class _Compare, class _Allocator>
611 class multimap;
612template <class _TreeIterator> class __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000613
Eric Fiseliera00b4842016-02-20 05:28:30 +0000614#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000615
616template <class _Key, class _Tp>
617union __value_type
618{
619 typedef _Key key_type;
620 typedef _Tp mapped_type;
621 typedef pair<const key_type, mapped_type> value_type;
622 typedef pair<key_type, mapped_type> __nc_value_type;
623
624 value_type __cc;
625 __nc_value_type __nc;
626
Howard Hinnant89f8b792013-09-30 19:08:22 +0000627 _LIBCPP_INLINE_VISIBILITY
628 __value_type& operator=(const __value_type& __v)
629 {__nc = __v.__cc; return *this;}
630
631 _LIBCPP_INLINE_VISIBILITY
632 __value_type& operator=(__value_type&& __v)
Eric Fiselierd06276b2016-03-31 02:15:15 +0000633 {__nc = _VSTD::move(__v.__nc); return *this;}
Howard Hinnant89f8b792013-09-30 19:08:22 +0000634
Eric Fiselierd06276b2016-03-31 02:15:15 +0000635 template <class _ValueTp,
636 class = typename enable_if<
637 __is_same_uncvref<_ValueTp, value_type>::value
638 >::type
639 >
Howard Hinnant89f8b792013-09-30 19:08:22 +0000640 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +0000641 __value_type& operator=(_ValueTp&& __v) {
642 __nc = _VSTD::forward<_ValueTp>(__v); return *this;
643 }
644
645private:
646 __value_type() _LIBCPP_EQUAL_DELETE;
647 ~__value_type() _LIBCPP_EQUAL_DELETE;
648 __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
649 __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
Howard Hinnant89f8b792013-09-30 19:08:22 +0000650};
651
652#else
653
654template <class _Key, class _Tp>
655struct __value_type
656{
657 typedef _Key key_type;
658 typedef _Tp mapped_type;
659 typedef pair<const key_type, mapped_type> value_type;
660
661 value_type __cc;
662
Eric Fiselierd06276b2016-03-31 02:15:15 +0000663private:
664 __value_type();
665 __value_type(__value_type const&);
666 __value_type& operator=(__value_type const&);
667 ~__value_type();
Howard Hinnant89f8b792013-09-30 19:08:22 +0000668};
669
Eric Fiseliera85b1282017-04-18 21:08:06 +0000670#endif // _LIBCPP_CXX03_LANG
Howard Hinnant89f8b792013-09-30 19:08:22 +0000671
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000672template <class _Tp>
673struct __extract_key_value_types;
674
675template <class _Key, class _Tp>
676struct __extract_key_value_types<__value_type<_Key, _Tp> >
677{
678 typedef _Key const __key_type;
679 typedef _Tp __mapped_type;
680};
681
Howard Hinnantc51e1022010-05-11 19:42:16 +0000682template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000683class _LIBCPP_TEMPLATE_VIS __map_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000684{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000685 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
686 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
687
Howard Hinnantc51e1022010-05-11 19:42:16 +0000688 _TreeIterator __i_;
689
Howard Hinnantc51e1022010-05-11 19:42:16 +0000690public:
691 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000692 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000693 typedef typename _TreeIterator::difference_type difference_type;
694 typedef value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000695 typedef typename _NodeTypes::__map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000696
Howard Hinnant756c69b2010-09-22 16:48:34 +0000697 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000698 __map_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000699
Howard Hinnant756c69b2010-09-22 16:48:34 +0000700 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000701 __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000702
Howard Hinnant756c69b2010-09-22 16:48:34 +0000703 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000704 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000705 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000706 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000707
Howard Hinnant756c69b2010-09-22 16:48:34 +0000708 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000709 __map_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000710 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000711 __map_iterator operator++(int)
712 {
713 __map_iterator __t(*this);
714 ++(*this);
715 return __t;
716 }
717
Howard Hinnant756c69b2010-09-22 16:48:34 +0000718 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000719 __map_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000720 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000721 __map_iterator operator--(int)
722 {
723 __map_iterator __t(*this);
724 --(*this);
725 return __t;
726 }
727
Howard Hinnant756c69b2010-09-22 16:48:34 +0000728 friend _LIBCPP_INLINE_VISIBILITY
729 bool operator==(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000730 {return __x.__i_ == __y.__i_;}
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000731 friend
Howard Hinnant756c69b2010-09-22 16:48:34 +0000732 _LIBCPP_INLINE_VISIBILITY
733 bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000734 {return __x.__i_ != __y.__i_;}
735
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000736 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
737 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
738 template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000739};
740
741template <class _TreeIterator>
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000742class _LIBCPP_TEMPLATE_VIS __map_const_iterator
Howard Hinnantc51e1022010-05-11 19:42:16 +0000743{
Eric Fiseliera00b4842016-02-20 05:28:30 +0000744 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
745 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
746
Howard Hinnantc51e1022010-05-11 19:42:16 +0000747 _TreeIterator __i_;
748
Howard Hinnantc51e1022010-05-11 19:42:16 +0000749public:
750 typedef bidirectional_iterator_tag iterator_category;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000751 typedef typename _NodeTypes::__map_value_type value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000752 typedef typename _TreeIterator::difference_type difference_type;
753 typedef const value_type& reference;
Eric Fiseliera00b4842016-02-20 05:28:30 +0000754 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000755
Howard Hinnant756c69b2010-09-22 16:48:34 +0000756 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000757 __map_const_iterator() _NOEXCEPT {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000758
Howard Hinnant756c69b2010-09-22 16:48:34 +0000759 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000760 __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000761 _LIBCPP_INLINE_VISIBILITY
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000762 __map_const_iterator(__map_iterator<
763 typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
764 : __i_(__i.__i_) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000765
Howard Hinnant756c69b2010-09-22 16:48:34 +0000766 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000767 reference operator*() const {return __i_->__cc;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000768 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000769 pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000770
Howard Hinnant756c69b2010-09-22 16:48:34 +0000771 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000772 __map_const_iterator& operator++() {++__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000773 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000774 __map_const_iterator operator++(int)
775 {
776 __map_const_iterator __t(*this);
777 ++(*this);
778 return __t;
779 }
780
Howard Hinnant756c69b2010-09-22 16:48:34 +0000781 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000782 __map_const_iterator& operator--() {--__i_; return *this;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000783 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000784 __map_const_iterator operator--(int)
785 {
786 __map_const_iterator __t(*this);
787 --(*this);
788 return __t;
789 }
790
Howard Hinnant756c69b2010-09-22 16:48:34 +0000791 friend _LIBCPP_INLINE_VISIBILITY
792 bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000793 {return __x.__i_ == __y.__i_;}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000794 friend _LIBCPP_INLINE_VISIBILITY
795 bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000796 {return __x.__i_ != __y.__i_;}
797
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000798 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map;
799 template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;
800 template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000801};
802
803template <class _Key, class _Tp, class _Compare = less<_Key>,
804 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000805class _LIBCPP_TEMPLATE_VIS map
Howard Hinnantc51e1022010-05-11 19:42:16 +0000806{
807public:
808 // types:
809 typedef _Key key_type;
810 typedef _Tp mapped_type;
811 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000812 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000813 typedef _Compare key_compare;
814 typedef _Allocator allocator_type;
815 typedef value_type& reference;
816 typedef const value_type& const_reference;
817
Marshall Clow5128cf32015-11-26 01:24:04 +0000818 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
819 "Allocator::value_type must be same type as value_type");
820
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +0000821 class _LIBCPP_TEMPLATE_VIS value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +0000822 : public binary_function<value_type, value_type, bool>
823 {
824 friend class map;
825 protected:
826 key_compare comp;
827
Howard Hinnant756c69b2010-09-22 16:48:34 +0000828 _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000829 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +0000830 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000831 bool operator()(const value_type& __x, const value_type& __y) const
832 {return comp(__x.first, __y.first);}
833 };
834
835private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000836
Howard Hinnant89f8b792013-09-30 19:08:22 +0000837 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +0000838 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +0000839 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
840 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000841 typedef __tree<__value_type, __vc, __allocator_type> __base;
842 typedef typename __base::__node_traits __node_traits;
843 typedef allocator_traits<allocator_type> __alloc_traits;
844
845 __base __tree_;
846
847public:
848 typedef typename __alloc_traits::pointer pointer;
849 typedef typename __alloc_traits::const_pointer const_pointer;
850 typedef typename __alloc_traits::size_type size_type;
851 typedef typename __alloc_traits::difference_type difference_type;
Eric Fiselier44f9fd02015-03-03 20:10:01 +0000852 typedef __map_iterator<typename __base::iterator> iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000853 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000854 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
855 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +0000856
Howard Hinnant756c69b2010-09-22 16:48:34 +0000857 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +0000858 map()
859 _NOEXCEPT_(
860 is_nothrow_default_constructible<allocator_type>::value &&
861 is_nothrow_default_constructible<key_compare>::value &&
862 is_nothrow_copy_constructible<key_compare>::value)
863 : __tree_(__vc(key_compare())) {}
864
865 _LIBCPP_INLINE_VISIBILITY
866 explicit map(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000867 _NOEXCEPT_(
868 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000869 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +0000870 : __tree_(__vc(__comp)) {}
871
Howard Hinnant756c69b2010-09-22 16:48:34 +0000872 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000873 explicit map(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000874 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000875
876 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000877 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000878 map(_InputIterator __f, _InputIterator __l,
879 const key_compare& __comp = key_compare())
880 : __tree_(__vc(__comp))
881 {
882 insert(__f, __l);
883 }
884
885 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +0000886 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000887 map(_InputIterator __f, _InputIterator __l,
888 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000889 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000890 {
891 insert(__f, __l);
892 }
893
Marshall Clow300abfb2013-09-11 01:15:47 +0000894#if _LIBCPP_STD_VER > 11
895 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000896 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +0000897 map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
898 : map(__f, __l, key_compare(), __a) {}
899#endif
900
Howard Hinnant756c69b2010-09-22 16:48:34 +0000901 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000902 map(const map& __m)
903 : __tree_(__m.__tree_)
904 {
905 insert(__m.begin(), __m.end());
906 }
907
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000908 _LIBCPP_INLINE_VISIBILITY
909 map& operator=(const map& __m)
910 {
Marshall Clow476d3f42016-07-18 13:19:00 +0000911#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000912 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000913#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +0000914 if (this != &__m) {
915 __tree_.clear();
916 __tree_.value_comp() = __m.__tree_.value_comp();
917 __tree_.__copy_assign_alloc(__m.__tree_);
918 insert(__m.begin(), __m.end());
919 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +0000920#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +0000921 return *this;
922 }
923
Eric Fiseliera85b1282017-04-18 21:08:06 +0000924#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000925
Howard Hinnant756c69b2010-09-22 16:48:34 +0000926 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000927 map(map&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000928 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +0000929 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000930 {
931 }
932
933 map(map&& __m, const allocator_type& __a);
934
Howard Hinnant756c69b2010-09-22 16:48:34 +0000935 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +0000936 map& operator=(map&& __m)
937 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
938 {
939 __tree_ = _VSTD::move(__m.__tree_);
940 return *this;
941 }
942
Howard Hinnant33711792011-08-12 21:56:02 +0000943 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000944 map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
945 : __tree_(__vc(__comp))
946 {
947 insert(__il.begin(), __il.end());
948 }
949
Howard Hinnant756c69b2010-09-22 16:48:34 +0000950 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000951 map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000952 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000953 {
954 insert(__il.begin(), __il.end());
955 }
956
Marshall Clow300abfb2013-09-11 01:15:47 +0000957#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +0000958 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +0000959 map(initializer_list<value_type> __il, const allocator_type& __a)
960 : map(__il, key_compare(), __a) {}
961#endif
962
Howard Hinnant756c69b2010-09-22 16:48:34 +0000963 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000964 map& operator=(initializer_list<value_type> __il)
965 {
966 __tree_.__assign_unique(__il.begin(), __il.end());
967 return *this;
968 }
969
Eric Fiseliera85b1282017-04-18 21:08:06 +0000970#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +0000971
Howard Hinnant756c69b2010-09-22 16:48:34 +0000972 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000973 explicit map(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000974 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000975 {
976 }
977
Howard Hinnant756c69b2010-09-22 16:48:34 +0000978 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +0000979 map(const map& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +0000980 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +0000981 {
982 insert(__m.begin(), __m.end());
983 }
984
Howard Hinnant756c69b2010-09-22 16:48:34 +0000985 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000986 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000988 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000989 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000990 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000991 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000992 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +0000993
Howard Hinnant756c69b2010-09-22 16:48:34 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000995 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000996 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +0000997 const_reverse_iterator rbegin() const _NOEXCEPT
998 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +0000999 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001000 reverse_iterator rend() _NOEXCEPT
1001 {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001002 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001003 const_reverse_iterator rend() const _NOEXCEPT
1004 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001005
Howard Hinnant756c69b2010-09-22 16:48:34 +00001006 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001007 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001008 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001009 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001010 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001011 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001012 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001013 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001014
Marshall Clow425f5752017-11-15 05:51:26 +00001015 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001016 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001017 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001018 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001019 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001020 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001021
1022 mapped_type& operator[](const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001023#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001024 mapped_type& operator[](key_type&& __k);
1025#endif
1026
1027 mapped_type& at(const key_type& __k);
1028 const mapped_type& at(const key_type& __k) const;
1029
Howard Hinnant756c69b2010-09-22 16:48:34 +00001030 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001031 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001032 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001033 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001034 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001035 value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
1036
Eric Fiselierd06276b2016-03-31 02:15:15 +00001037#ifndef _LIBCPP_CXX03_LANG
1038 template <class ..._Args>
1039 _LIBCPP_INLINE_VISIBILITY
1040 pair<iterator, bool> emplace(_Args&& ...__args) {
1041 return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
1042 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001043
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001044 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001045 _LIBCPP_INLINE_VISIBILITY
1046 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1047 return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
1048 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001049
Howard Hinnantc834c512011-11-29 18:15:50 +00001050 template <class _Pp,
1051 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001052 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001053 pair<iterator, bool> insert(_Pp&& __p)
1054 {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +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 iterator insert(const_iterator __pos, _Pp&& __p)
1060 {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001061
Eric Fiselierd06276b2016-03-31 02:15:15 +00001062#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001063
Howard Hinnant756c69b2010-09-22 16:48:34 +00001064 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001065 pair<iterator, bool>
1066 insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
1067
Howard Hinnant756c69b2010-09-22 16:48:34 +00001068 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001069 iterator
1070 insert(const_iterator __p, const value_type& __v)
1071 {return __tree_.__insert_unique(__p.__i_, __v);}
1072
Eric Fiselierd6143132016-04-18 01:40:45 +00001073#ifndef _LIBCPP_CXX03_LANG
Marshall Clowd430d022016-01-05 19:32:41 +00001074 _LIBCPP_INLINE_VISIBILITY
1075 pair<iterator, bool>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001076 insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
Marshall Clowd430d022016-01-05 19:32:41 +00001077
1078 _LIBCPP_INLINE_VISIBILITY
Eric Fiselierd06276b2016-03-31 02:15:15 +00001079 iterator insert(const_iterator __p, value_type&& __v)
1080 {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
Eric Fiseliera85b1282017-04-18 21:08:06 +00001081
1082 _LIBCPP_INLINE_VISIBILITY
1083 void insert(initializer_list<value_type> __il)
1084 {insert(__il.begin(), __il.end());}
Marshall Clowd430d022016-01-05 19:32:41 +00001085#endif
1086
Howard Hinnantc51e1022010-05-11 19:42:16 +00001087 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001088 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001089 void insert(_InputIterator __f, _InputIterator __l)
1090 {
1091 for (const_iterator __e = cend(); __f != __l; ++__f)
1092 insert(__e.__i_, *__f);
1093 }
1094
Marshall Clow3223db82015-07-07 03:37:33 +00001095#if _LIBCPP_STD_VER > 14
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001096
Marshall Clow3223db82015-07-07 03:37:33 +00001097 template <class... _Args>
1098 _LIBCPP_INLINE_VISIBILITY
1099 pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
1100 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001101 return __tree_.__emplace_unique_key_args(__k,
1102 _VSTD::piecewise_construct,
1103 _VSTD::forward_as_tuple(__k),
1104 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001105 }
1106
1107 template <class... _Args>
1108 _LIBCPP_INLINE_VISIBILITY
1109 pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
1110 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001111 return __tree_.__emplace_unique_key_args(__k,
1112 _VSTD::piecewise_construct,
1113 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1114 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001115 }
1116
1117 template <class... _Args>
1118 _LIBCPP_INLINE_VISIBILITY
1119 iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
1120 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001121 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1122 _VSTD::piecewise_construct,
1123 _VSTD::forward_as_tuple(__k),
1124 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001125 }
1126
1127 template <class... _Args>
1128 _LIBCPP_INLINE_VISIBILITY
1129 iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
1130 {
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001131 return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
1132 _VSTD::piecewise_construct,
1133 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1134 _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
Marshall Clow3223db82015-07-07 03:37:33 +00001135 }
1136
1137 template <class _Vp>
1138 _LIBCPP_INLINE_VISIBILITY
1139 pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
1140 {
1141 iterator __p = lower_bound(__k);
1142 if ( __p != end() && !key_comp()(__k, __p->first))
1143 {
1144 __p->second = _VSTD::forward<_Vp>(__v);
1145 return _VSTD::make_pair(__p, false);
1146 }
1147 return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
1148 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001149
Marshall Clow3223db82015-07-07 03:37:33 +00001150 template <class _Vp>
1151 _LIBCPP_INLINE_VISIBILITY
1152 pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
1153 {
1154 iterator __p = lower_bound(__k);
1155 if ( __p != end() && !key_comp()(__k, __p->first))
1156 {
1157 __p->second = _VSTD::forward<_Vp>(__v);
1158 return _VSTD::make_pair(__p, false);
1159 }
1160 return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
1161 }
1162
1163 template <class _Vp>
1164 _LIBCPP_INLINE_VISIBILITY
1165 iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
1166 {
1167 iterator __p = lower_bound(__k);
1168 if ( __p != end() && !key_comp()(__k, __p->first))
1169 {
1170 __p->second = _VSTD::forward<_Vp>(__v);
1171 return __p;
1172 }
1173 return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
1174 }
1175
1176 template <class _Vp>
1177 _LIBCPP_INLINE_VISIBILITY
1178 iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
1179 {
1180 iterator __p = lower_bound(__k);
1181 if ( __p != end() && !key_comp()(__k, __p->first))
1182 {
1183 __p->second = _VSTD::forward<_Vp>(__v);
1184 return __p;
1185 }
1186 return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
1187 }
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001188
Eric Fiseliera85b1282017-04-18 21:08:06 +00001189#endif // _LIBCPP_STD_VER > 14
Marshall Clow3223db82015-07-07 03:37:33 +00001190
Howard Hinnant756c69b2010-09-22 16:48:34 +00001191 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001192 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001193 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001194 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1195 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001196 size_type erase(const key_type& __k)
1197 {return __tree_.__erase_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001198 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001199 iterator erase(const_iterator __f, const_iterator __l)
1200 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001201 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001202 void clear() _NOEXCEPT {__tree_.clear();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001203
Howard Hinnant756c69b2010-09-22 16:48:34 +00001204 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001205 void swap(map& __m)
1206 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1207 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001208
Howard Hinnant756c69b2010-09-22 16:48:34 +00001209 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001210 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001211 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001212 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001213#if _LIBCPP_STD_VER > 11
1214 template <typename _K2>
1215 _LIBCPP_INLINE_VISIBILITY
1216 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1217 find(const _K2& __k) {return __tree_.find(__k);}
1218 template <typename _K2>
1219 _LIBCPP_INLINE_VISIBILITY
1220 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1221 find(const _K2& __k) const {return __tree_.find(__k);}
1222#endif
1223
Howard Hinnant756c69b2010-09-22 16:48:34 +00001224 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001225 size_type count(const key_type& __k) const
1226 {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001227#if _LIBCPP_STD_VER > 11
1228 template <typename _K2>
1229 _LIBCPP_INLINE_VISIBILITY
1230 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00001231 count(const _K2& __k) const {return __tree_.__count_unique(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001232#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001233 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001234 iterator lower_bound(const key_type& __k)
1235 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001236 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001237 const_iterator lower_bound(const key_type& __k) const
1238 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001239#if _LIBCPP_STD_VER > 11
1240 template <typename _K2>
1241 _LIBCPP_INLINE_VISIBILITY
1242 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1243 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1244
1245 template <typename _K2>
1246 _LIBCPP_INLINE_VISIBILITY
1247 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1248 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1249#endif
1250
Howard Hinnant756c69b2010-09-22 16:48:34 +00001251 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001252 iterator upper_bound(const key_type& __k)
1253 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001254 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001255 const_iterator upper_bound(const key_type& __k) const
1256 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001257#if _LIBCPP_STD_VER > 11
1258 template <typename _K2>
1259 _LIBCPP_INLINE_VISIBILITY
1260 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1261 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1262 template <typename _K2>
1263 _LIBCPP_INLINE_VISIBILITY
1264 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1265 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1266#endif
1267
Howard Hinnant756c69b2010-09-22 16:48:34 +00001268 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001269 pair<iterator,iterator> equal_range(const key_type& __k)
1270 {return __tree_.__equal_range_unique(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001271 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001272 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1273 {return __tree_.__equal_range_unique(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001274#if _LIBCPP_STD_VER > 11
1275 template <typename _K2>
1276 _LIBCPP_INLINE_VISIBILITY
1277 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1278 equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
1279 template <typename _K2>
1280 _LIBCPP_INLINE_VISIBILITY
1281 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1282 equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
1283#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001284
1285private:
1286 typedef typename __base::__node __node;
1287 typedef typename __base::__node_allocator __node_allocator;
1288 typedef typename __base::__node_pointer __node_pointer;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001289 typedef typename __base::__node_base_pointer __node_base_pointer;
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001290 typedef typename __base::__parent_pointer __parent_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001291
Howard Hinnantc834c512011-11-29 18:15:50 +00001292 typedef __map_node_destructor<__node_allocator> _Dp;
1293 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001294
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001295#ifdef _LIBCPP_CXX03_LANG
Howard Hinnantac7e7482013-07-04 20:59:16 +00001296 __node_holder __construct_node_with_key(const key_type& __k);
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001297#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001298};
1299
Eric Fiseliera92b0732016-02-20 07:12:17 +00001300
Eric Fiselierd06276b2016-03-31 02:15:15 +00001301#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001302template <class _Key, class _Tp, class _Compare, class _Allocator>
1303map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001304 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001305{
1306 if (__a != __m.get_allocator())
1307 {
1308 const_iterator __e = cend();
1309 while (!__m.empty())
1310 __tree_.__insert_unique(__e.__i_,
Eric Fiselierd06276b2016-03-31 02:15:15 +00001311 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001312 }
1313}
1314
Eric Fiseliera85b1282017-04-18 21:08:06 +00001315template <class _Key, class _Tp, class _Compare, class _Allocator>
1316_Tp&
1317map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1318{
1319 return __tree_.__emplace_unique_key_args(__k,
1320 _VSTD::piecewise_construct,
1321 _VSTD::forward_as_tuple(__k),
1322 _VSTD::forward_as_tuple()).first->__cc.second;
1323}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001324
Eric Fiseliera85b1282017-04-18 21:08:06 +00001325template <class _Key, class _Tp, class _Compare, class _Allocator>
1326_Tp&
1327map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
1328{
1329 return __tree_.__emplace_unique_key_args(__k,
1330 _VSTD::piecewise_construct,
1331 _VSTD::forward_as_tuple(_VSTD::move(__k)),
1332 _VSTD::forward_as_tuple()).first->__cc.second;
1333}
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001334
Eric Fiseliera85b1282017-04-18 21:08:06 +00001335#else // _LIBCPP_CXX03_LANG
Eric Fiselierd63f38e2016-03-31 03:13:37 +00001336
Howard Hinnantc51e1022010-05-11 19:42:16 +00001337template <class _Key, class _Tp, class _Compare, class _Allocator>
1338typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
Howard Hinnantac7e7482013-07-04 20:59:16 +00001339map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001340{
1341 __node_allocator& __na = __tree_.__node_alloc();
Howard Hinnantc834c512011-11-29 18:15:50 +00001342 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001343 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001344 __h.get_deleter().__first_constructed = true;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001345 __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001346 __h.get_deleter().__second_constructed = true;
Dimitry Andric830fb602015-08-19 06:43:33 +00001347 return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
Howard Hinnantc51e1022010-05-11 19:42:16 +00001348}
1349
Howard Hinnantc51e1022010-05-11 19:42:16 +00001350template <class _Key, class _Tp, class _Compare, class _Allocator>
1351_Tp&
1352map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
1353{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001354 __parent_pointer __parent;
1355 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnantc51e1022010-05-11 19:42:16 +00001356 __node_pointer __r = static_cast<__node_pointer>(__child);
1357 if (__child == nullptr)
1358 {
Howard Hinnantac7e7482013-07-04 20:59:16 +00001359 __node_holder __h = __construct_node_with_key(__k);
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001360 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001361 __r = __h.release();
1362 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001363 return __r->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001364}
1365
Eric Fiseliera85b1282017-04-18 21:08:06 +00001366#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001367
1368template <class _Key, class _Tp, class _Compare, class _Allocator>
1369_Tp&
1370map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
1371{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001372 __parent_pointer __parent;
1373 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001374#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001375 if (__child == nullptr)
1376 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001377#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001378 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001379}
1380
1381template <class _Key, class _Tp, class _Compare, class _Allocator>
1382const _Tp&
1383map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
1384{
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001385 __parent_pointer __parent;
1386 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
Howard Hinnant72f73582010-08-11 17:04:31 +00001387#ifndef _LIBCPP_NO_EXCEPTIONS
Howard Hinnantc51e1022010-05-11 19:42:16 +00001388 if (__child == nullptr)
1389 throw out_of_range("map::at: key not found");
Howard Hinnant3b6579a2010-08-22 00:02:43 +00001390#endif // _LIBCPP_NO_EXCEPTIONS
Eric Fiseliera92b0732016-02-20 07:12:17 +00001391 return static_cast<__node_pointer>(__child)->__value_.__cc.second;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001392}
1393
Howard Hinnantc51e1022010-05-11 19:42:16 +00001394
1395template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001396inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001397bool
1398operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1399 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1400{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001401 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001402}
1403
1404template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001405inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001406bool
1407operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1408 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1409{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001410 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001411}
1412
1413template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001414inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001415bool
1416operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1417 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1418{
1419 return !(__x == __y);
1420}
1421
1422template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001423inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001424bool
1425operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
1426 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1427{
1428 return __y < __x;
1429}
1430
1431template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001432inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001433bool
1434operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1435 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1436{
1437 return !(__x < __y);
1438}
1439
1440template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001441inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001442bool
1443operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
1444 const map<_Key, _Tp, _Compare, _Allocator>& __y)
1445{
1446 return !(__y < __x);
1447}
1448
1449template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001450inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001451void
1452swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
1453 map<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001454 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001455{
1456 __x.swap(__y);
1457}
1458
1459template <class _Key, class _Tp, class _Compare = less<_Key>,
1460 class _Allocator = allocator<pair<const _Key, _Tp> > >
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001461class _LIBCPP_TEMPLATE_VIS multimap
Howard Hinnantc51e1022010-05-11 19:42:16 +00001462{
1463public:
1464 // types:
1465 typedef _Key key_type;
1466 typedef _Tp mapped_type;
1467 typedef pair<const key_type, mapped_type> value_type;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001468 typedef pair<key_type, mapped_type> __nc_value_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001469 typedef _Compare key_compare;
1470 typedef _Allocator allocator_type;
1471 typedef value_type& reference;
1472 typedef const value_type& const_reference;
1473
Marshall Clow5128cf32015-11-26 01:24:04 +00001474 static_assert((is_same<typename allocator_type::value_type, value_type>::value),
1475 "Allocator::value_type must be same type as value_type");
1476
Eric Fiselierb5eb1bf2017-01-04 23:56:00 +00001477 class _LIBCPP_TEMPLATE_VIS value_compare
Howard Hinnantc51e1022010-05-11 19:42:16 +00001478 : public binary_function<value_type, value_type, bool>
1479 {
1480 friend class multimap;
1481 protected:
1482 key_compare comp;
1483
Howard Hinnant756c69b2010-09-22 16:48:34 +00001484 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001485 value_compare(key_compare c) : comp(c) {}
1486 public:
Howard Hinnant756c69b2010-09-22 16:48:34 +00001487 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001488 bool operator()(const value_type& __x, const value_type& __y) const
1489 {return comp(__x.first, __y.first);}
1490 };
1491
1492private:
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001493
Howard Hinnant89f8b792013-09-30 19:08:22 +00001494 typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
Howard Hinnant90b91592013-07-05 18:06:00 +00001495 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
Marshall Clow940e01c2015-04-07 05:21:38 +00001496 typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
1497 __value_type>::type __allocator_type;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001498 typedef __tree<__value_type, __vc, __allocator_type> __base;
1499 typedef typename __base::__node_traits __node_traits;
1500 typedef allocator_traits<allocator_type> __alloc_traits;
1501
1502 __base __tree_;
1503
1504public:
1505 typedef typename __alloc_traits::pointer pointer;
1506 typedef typename __alloc_traits::const_pointer const_pointer;
1507 typedef typename __alloc_traits::size_type size_type;
1508 typedef typename __alloc_traits::difference_type difference_type;
1509 typedef __map_iterator<typename __base::iterator> iterator;
1510 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001511 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1512 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001513
Howard Hinnant756c69b2010-09-22 16:48:34 +00001514 _LIBCPP_INLINE_VISIBILITY
Marshall Clow7086a5a2014-03-10 04:50:10 +00001515 multimap()
1516 _NOEXCEPT_(
1517 is_nothrow_default_constructible<allocator_type>::value &&
1518 is_nothrow_default_constructible<key_compare>::value &&
1519 is_nothrow_copy_constructible<key_compare>::value)
1520 : __tree_(__vc(key_compare())) {}
1521
1522 _LIBCPP_INLINE_VISIBILITY
1523 explicit multimap(const key_compare& __comp)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001524 _NOEXCEPT_(
1525 is_nothrow_default_constructible<allocator_type>::value &&
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001526 is_nothrow_copy_constructible<key_compare>::value)
Howard Hinnantc51e1022010-05-11 19:42:16 +00001527 : __tree_(__vc(__comp)) {}
1528
Howard Hinnant756c69b2010-09-22 16:48:34 +00001529 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001530 explicit multimap(const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001531 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001532
1533 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001534 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001535 multimap(_InputIterator __f, _InputIterator __l,
1536 const key_compare& __comp = key_compare())
1537 : __tree_(__vc(__comp))
1538 {
1539 insert(__f, __l);
1540 }
1541
1542 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001543 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001544 multimap(_InputIterator __f, _InputIterator __l,
1545 const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001546 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001547 {
1548 insert(__f, __l);
1549 }
1550
Marshall Clow300abfb2013-09-11 01:15:47 +00001551#if _LIBCPP_STD_VER > 11
1552 template <class _InputIterator>
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001553 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001554 multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
1555 : multimap(__f, __l, key_compare(), __a) {}
1556#endif
1557
Howard Hinnant756c69b2010-09-22 16:48:34 +00001558 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001559 multimap(const multimap& __m)
1560 : __tree_(__m.__tree_.value_comp(),
1561 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
1562 {
1563 insert(__m.begin(), __m.end());
1564 }
1565
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001566 _LIBCPP_INLINE_VISIBILITY
1567 multimap& operator=(const multimap& __m)
1568 {
Marshall Clow476d3f42016-07-18 13:19:00 +00001569#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001570 __tree_ = __m.__tree_;
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001571#else
Marshall Clowdb3cfcb2014-02-08 04:03:14 +00001572 if (this != &__m) {
1573 __tree_.clear();
1574 __tree_.value_comp() = __m.__tree_.value_comp();
1575 __tree_.__copy_assign_alloc(__m.__tree_);
1576 insert(__m.begin(), __m.end());
1577 }
Howard Hinnant2d0046b2013-06-19 21:29:40 +00001578#endif
Howard Hinnantd3a657f2011-07-01 19:24:36 +00001579 return *this;
1580 }
1581
Eric Fiseliera85b1282017-04-18 21:08:06 +00001582#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001583
Howard Hinnant756c69b2010-09-22 16:48:34 +00001584 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001585 multimap(multimap&& __m)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001586 _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001587 : __tree_(_VSTD::move(__m.__tree_))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001588 {
1589 }
1590
1591 multimap(multimap&& __m, const allocator_type& __a);
1592
Howard Hinnant756c69b2010-09-22 16:48:34 +00001593 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant33711792011-08-12 21:56:02 +00001594 multimap& operator=(multimap&& __m)
1595 _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
1596 {
1597 __tree_ = _VSTD::move(__m.__tree_);
1598 return *this;
1599 }
1600
Howard Hinnant33711792011-08-12 21:56:02 +00001601 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001602 multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
1603 : __tree_(__vc(__comp))
1604 {
1605 insert(__il.begin(), __il.end());
1606 }
1607
Howard Hinnant756c69b2010-09-22 16:48:34 +00001608 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001609 multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001610 : __tree_(__vc(__comp), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001611 {
1612 insert(__il.begin(), __il.end());
1613 }
1614
Marshall Clow300abfb2013-09-11 01:15:47 +00001615#if _LIBCPP_STD_VER > 11
Eric Fiseliercf8c0212017-01-05 06:06:18 +00001616 _LIBCPP_INLINE_VISIBILITY
Marshall Clow300abfb2013-09-11 01:15:47 +00001617 multimap(initializer_list<value_type> __il, const allocator_type& __a)
1618 : multimap(__il, key_compare(), __a) {}
1619#endif
1620
Howard Hinnant756c69b2010-09-22 16:48:34 +00001621 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001622 multimap& operator=(initializer_list<value_type> __il)
1623 {
1624 __tree_.__assign_multi(__il.begin(), __il.end());
1625 return *this;
1626 }
Howard Hinnant33711792011-08-12 21:56:02 +00001627
Eric Fiseliera85b1282017-04-18 21:08:06 +00001628#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001629
Howard Hinnant756c69b2010-09-22 16:48:34 +00001630 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001631 explicit multimap(const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001632 : __tree_(typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001633 {
1634 }
1635
Howard Hinnant756c69b2010-09-22 16:48:34 +00001636 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001637 multimap(const multimap& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001638 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001639 {
1640 insert(__m.begin(), __m.end());
1641 }
1642
Howard Hinnant756c69b2010-09-22 16:48:34 +00001643 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001644 iterator begin() _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001645 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001646 const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001647 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001648 iterator end() _NOEXCEPT {return __tree_.end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001649 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001650 const_iterator end() const _NOEXCEPT {return __tree_.end();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001651
Howard Hinnant756c69b2010-09-22 16:48:34 +00001652 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001653 reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001654 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001655 const_reverse_iterator rbegin() const _NOEXCEPT
1656 {return const_reverse_iterator(end());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001657 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001658 reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001659 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001660 const_reverse_iterator rend() const _NOEXCEPT
1661 {return const_reverse_iterator(begin());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001662
Howard Hinnant756c69b2010-09-22 16:48:34 +00001663 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001664 const_iterator cbegin() const _NOEXCEPT {return begin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001665 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001666 const_iterator cend() const _NOEXCEPT {return end();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001667 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001668 const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001669 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001670 const_reverse_iterator crend() const _NOEXCEPT {return rend();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001671
Marshall Clow425f5752017-11-15 05:51:26 +00001672 _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001673 bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001674 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001675 size_type size() const _NOEXCEPT {return __tree_.size();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001676 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001677 size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001678
Howard Hinnant756c69b2010-09-22 16:48:34 +00001679 _LIBCPP_INLINE_VISIBILITY
Marshall Clow657cbc42016-08-17 05:58:40 +00001680 allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001681 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001682 key_compare key_comp() const {return __tree_.value_comp().key_comp();}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001683 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001684 value_compare value_comp() const
1685 {return value_compare(__tree_.value_comp().key_comp());}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001686
Eric Fiselierd06276b2016-03-31 02:15:15 +00001687#ifndef _LIBCPP_CXX03_LANG
Howard Hinnant74279a52010-09-04 23:28:19 +00001688
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001689 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001690 _LIBCPP_INLINE_VISIBILITY
1691 iterator emplace(_Args&& ...__args) {
1692 return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
1693 }
Howard Hinnantc51e1022010-05-11 19:42:16 +00001694
Howard Hinnant29eb9b82012-05-25 22:04:21 +00001695 template <class ..._Args>
Eric Fiselierd06276b2016-03-31 02:15:15 +00001696 _LIBCPP_INLINE_VISIBILITY
1697 iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
1698 return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
1699 }
Howard Hinnant74279a52010-09-04 23:28:19 +00001700
Howard Hinnantc834c512011-11-29 18:15:50 +00001701 template <class _Pp,
1702 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001703 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001704 iterator insert(_Pp&& __p)
1705 {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001706
Howard Hinnantc834c512011-11-29 18:15:50 +00001707 template <class _Pp,
1708 class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001709 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc834c512011-11-29 18:15:50 +00001710 iterator insert(const_iterator __pos, _Pp&& __p)
1711 {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001712
Eric Fiselierd6143132016-04-18 01:40:45 +00001713 _LIBCPP_INLINE_VISIBILITY
1714 iterator insert(value_type&& __v)
1715 {return __tree_.__insert_multi(_VSTD::move(__v));}
1716
1717 _LIBCPP_INLINE_VISIBILITY
1718 iterator insert(const_iterator __p, value_type&& __v)
1719 {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
1720
Eric Fiseliera85b1282017-04-18 21:08:06 +00001721
1722 _LIBCPP_INLINE_VISIBILITY
1723 void insert(initializer_list<value_type> __il)
1724 {insert(__il.begin(), __il.end());}
1725
Eric Fiselierd06276b2016-03-31 02:15:15 +00001726#endif // _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001727
Howard Hinnant756c69b2010-09-22 16:48:34 +00001728 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001729 iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
1730
Howard Hinnant756c69b2010-09-22 16:48:34 +00001731 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001732 iterator insert(const_iterator __p, const value_type& __v)
1733 {return __tree_.__insert_multi(__p.__i_, __v);}
1734
1735 template <class _InputIterator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001736 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001737 void insert(_InputIterator __f, _InputIterator __l)
1738 {
1739 for (const_iterator __e = cend(); __f != __l; ++__f)
1740 __tree_.__insert_multi(__e.__i_, *__f);
1741 }
1742
Howard Hinnant756c69b2010-09-22 16:48:34 +00001743 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001744 iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001745 _LIBCPP_INLINE_VISIBILITY
Marshall Clow22ea5b82015-05-10 13:35:00 +00001746 iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
1747 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001748 size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001749 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001750 iterator erase(const_iterator __f, const_iterator __l)
1751 {return __tree_.erase(__f.__i_, __l.__i_);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001752 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001753 void clear() {__tree_.clear();}
1754
Howard Hinnant756c69b2010-09-22 16:48:34 +00001755 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001756 void swap(multimap& __m)
1757 _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
1758 {__tree_.swap(__m.__tree_);}
Howard Hinnantc51e1022010-05-11 19:42:16 +00001759
Howard Hinnant756c69b2010-09-22 16:48:34 +00001760 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001761 iterator find(const key_type& __k) {return __tree_.find(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001762 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001763 const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001764#if _LIBCPP_STD_VER > 11
1765 template <typename _K2>
1766 _LIBCPP_INLINE_VISIBILITY
1767 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1768 find(const _K2& __k) {return __tree_.find(__k);}
1769 template <typename _K2>
1770 _LIBCPP_INLINE_VISIBILITY
1771 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1772 find(const _K2& __k) const {return __tree_.find(__k);}
1773#endif
1774
Howard Hinnant756c69b2010-09-22 16:48:34 +00001775 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001776 size_type count(const key_type& __k) const
1777 {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001778#if _LIBCPP_STD_VER > 11
1779 template <typename _K2>
1780 _LIBCPP_INLINE_VISIBILITY
1781 typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
Marshall Clow141e47b2015-06-30 18:15:41 +00001782 count(const _K2& __k) const {return __tree_.__count_multi(__k);}
Marshall Clowe6a5f522014-08-24 23:54:16 +00001783#endif
Howard Hinnant756c69b2010-09-22 16:48:34 +00001784 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001785 iterator lower_bound(const key_type& __k)
1786 {return __tree_.lower_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001787 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001788 const_iterator lower_bound(const key_type& __k) const
1789 {return __tree_.lower_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001790#if _LIBCPP_STD_VER > 11
1791 template <typename _K2>
1792 _LIBCPP_INLINE_VISIBILITY
1793 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1794 lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
1795
1796 template <typename _K2>
1797 _LIBCPP_INLINE_VISIBILITY
1798 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1799 lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
1800#endif
1801
Howard Hinnant756c69b2010-09-22 16:48:34 +00001802 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001803 iterator upper_bound(const key_type& __k)
1804 {return __tree_.upper_bound(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001805 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001806 const_iterator upper_bound(const key_type& __k) const
1807 {return __tree_.upper_bound(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001808#if _LIBCPP_STD_VER > 11
1809 template <typename _K2>
1810 _LIBCPP_INLINE_VISIBILITY
1811 typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
1812 upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
1813 template <typename _K2>
1814 _LIBCPP_INLINE_VISIBILITY
1815 typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
1816 upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
1817#endif
1818
Howard Hinnant756c69b2010-09-22 16:48:34 +00001819 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001820 pair<iterator,iterator> equal_range(const key_type& __k)
1821 {return __tree_.__equal_range_multi(__k);}
Howard Hinnant756c69b2010-09-22 16:48:34 +00001822 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001823 pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
1824 {return __tree_.__equal_range_multi(__k);}
Marshall Clowebb57322013-08-13 22:18:47 +00001825#if _LIBCPP_STD_VER > 11
1826 template <typename _K2>
1827 _LIBCPP_INLINE_VISIBILITY
1828 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
1829 equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
1830 template <typename _K2>
1831 _LIBCPP_INLINE_VISIBILITY
1832 typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
1833 equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
1834#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001835
1836private:
1837 typedef typename __base::__node __node;
1838 typedef typename __base::__node_allocator __node_allocator;
1839 typedef typename __base::__node_pointer __node_pointer;
Eric Fiseliera92b0732016-02-20 07:12:17 +00001840
Howard Hinnantc834c512011-11-29 18:15:50 +00001841 typedef __map_node_destructor<__node_allocator> _Dp;
1842 typedef unique_ptr<__node, _Dp> __node_holder;
Howard Hinnantc51e1022010-05-11 19:42:16 +00001843};
1844
Eric Fiselierd06276b2016-03-31 02:15:15 +00001845#ifndef _LIBCPP_CXX03_LANG
Howard Hinnantc51e1022010-05-11 19:42:16 +00001846template <class _Key, class _Tp, class _Compare, class _Allocator>
1847multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
Marshall Clow657cbc42016-08-17 05:58:40 +00001848 : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001849{
1850 if (__a != __m.get_allocator())
1851 {
1852 const_iterator __e = cend();
1853 while (!__m.empty())
1854 __tree_.__insert_multi(__e.__i_,
Eric Fiselierd06276b2016-03-31 02:15:15 +00001855 _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
Howard Hinnantc51e1022010-05-11 19:42:16 +00001856 }
1857}
Eric Fiselierd06276b2016-03-31 02:15:15 +00001858#endif
Howard Hinnantc51e1022010-05-11 19:42:16 +00001859
1860template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001861inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001862bool
1863operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1864 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1865{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001866 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001867}
1868
1869template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001870inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001871bool
1872operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1873 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1874{
Howard Hinnantb1ad5a82011-06-30 21:18:19 +00001875 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantc51e1022010-05-11 19:42:16 +00001876}
1877
1878template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001879inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001880bool
1881operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1882 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1883{
1884 return !(__x == __y);
1885}
1886
1887template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001888inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001889bool
1890operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1891 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1892{
1893 return __y < __x;
1894}
1895
1896template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001897inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001898bool
1899operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1900 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1901{
1902 return !(__x < __y);
1903}
1904
1905template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001906inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001907bool
1908operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1909 const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
1910{
1911 return !(__y < __x);
1912}
1913
1914template <class _Key, class _Tp, class _Compare, class _Allocator>
Howard Hinnant756c69b2010-09-22 16:48:34 +00001915inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc51e1022010-05-11 19:42:16 +00001916void
1917swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
1918 multimap<_Key, _Tp, _Compare, _Allocator>& __y)
Howard Hinnant2f1ea9c2011-06-04 14:31:57 +00001919 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantc51e1022010-05-11 19:42:16 +00001920{
1921 __x.swap(__y);
1922}
1923
1924_LIBCPP_END_NAMESPACE_STD
1925
1926#endif // _LIBCPP_MAP