Debian Codegraph @

libcxx/include/__cxx03/map

raw
1 // -*- C++ -*-
2 //===----------------------------------------------------------------------===//
3 //
4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
5 // See https://llvm.org/LICENSE.txt for license information.
6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___CXX03_MAP
11 #define _LIBCPP___CXX03_MAP
12
13 /*
14
15 map synopsis
16
17 namespace std
18 {
19
20 template <class Key, class T, class Compare = less<Key>,
21 class Allocator = allocator<pair<const Key, T>>>
22 class map
23 {
24 public:
25 // types:
26 typedef Key key_type;
27 typedef T mapped_type;
28 typedef pair<const key_type, mapped_type> value_type;
29 typedef Compare key_compare;
30 typedef Allocator allocator_type;
31 typedef typename allocator_type::reference reference;
32 typedef typename allocator_type::const_reference const_reference;
33 typedef typename allocator_type::pointer pointer;
34 typedef typename allocator_type::const_pointer const_pointer;
35 typedef typename allocator_type::size_type size_type;
36 typedef typename allocator_type::difference_type difference_type;
37
38 typedef implementation-defined iterator;
39 typedef implementation-defined const_iterator;
40 typedef std::reverse_iterator<iterator> reverse_iterator;
41 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
42 typedef unspecified node_type; // C++17
43 typedef INSERT_RETURN_TYPE<iterator, node_type> insert_return_type; // C++17
44
45 class value_compare
46 {
47 friend class map;
48 protected:
49 key_compare comp;
50
51 value_compare(key_compare c);
52 public:
53 typedef bool result_type; // deprecated in C++17, removed in C++20
54 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
55 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
56 bool operator()(const value_type& x, const value_type& y) const;
57 };
58
59 // construct/copy/destroy:
60 map()
61 noexcept(
62 is_nothrow_default_constructible<allocator_type>::value &&
63 is_nothrow_default_constructible<key_compare>::value &&
64 is_nothrow_copy_constructible<key_compare>::value);
65 explicit map(const key_compare& comp);
66 map(const key_compare& comp, const allocator_type& a);
67 template <class InputIterator>
68 map(InputIterator first, InputIterator last,
69 const key_compare& comp = key_compare());
70 template <class InputIterator>
71 map(InputIterator first, InputIterator last,
72 const key_compare& comp, const allocator_type& a);
73 template<container-compatible-range<value_type> R>
74 map(from_range_t, R&& rg, const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
75 map(const map& m);
76 map(map&& m)
77 noexcept(
78 is_nothrow_move_constructible<allocator_type>::value &&
79 is_nothrow_move_constructible<key_compare>::value);
80 explicit map(const allocator_type& a);
81 map(const map& m, const allocator_type& a);
82 map(map&& m, const allocator_type& a);
83 map(initializer_list<value_type> il, const key_compare& comp = key_compare());
84 map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
85 template <class InputIterator>
86 map(InputIterator first, InputIterator last, const allocator_type& a)
87 : map(first, last, Compare(), a) {} // C++14
88 template<container-compatible-range<value_type> R>
89 map(from_range_t, R&& rg, const Allocator& a))
90 : map(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
91 map(initializer_list<value_type> il, const allocator_type& a)
92 : map(il, Compare(), a) {} // C++14
93 ~map();
94
95 map& operator=(const map& m);
96 map& operator=(map&& m)
97 noexcept(
98 allocator_type::propagate_on_container_move_assignment::value &&
99 is_nothrow_move_assignable<allocator_type>::value &&
100 is_nothrow_move_assignable<key_compare>::value);
101 map& operator=(initializer_list<value_type> il);
102
103 // iterators:
104 iterator begin() noexcept;
105 const_iterator begin() const noexcept;
106 iterator end() noexcept;
107 const_iterator end() const noexcept;
108
109 reverse_iterator rbegin() noexcept;
110 const_reverse_iterator rbegin() const noexcept;
111 reverse_iterator rend() noexcept;
112 const_reverse_iterator rend() const noexcept;
113
114 const_iterator cbegin() const noexcept;
115 const_iterator cend() const noexcept;
116 const_reverse_iterator crbegin() const noexcept;
117 const_reverse_iterator crend() const noexcept;
118
119 // capacity:
120 bool empty() const noexcept;
121 size_type size() const noexcept;
122 size_type max_size() const noexcept;
123
124 // element access:
125 mapped_type& operator[](const key_type& k);
126 mapped_type& operator[](key_type&& k);
127
128 mapped_type& at(const key_type& k);
129 const mapped_type& at(const key_type& k) const;
130
131 // modifiers:
132 template <class... Args>
133 pair<iterator, bool> emplace(Args&&... args);
134 template <class... Args>
135 iterator emplace_hint(const_iterator position, Args&&... args);
136 pair<iterator, bool> insert(const value_type& v);
137 pair<iterator, bool> insert( value_type&& v); // C++17
138 template <class P>
139 pair<iterator, bool> insert(P&& p);
140 iterator insert(const_iterator position, const value_type& v);
141 iterator insert(const_iterator position, value_type&& v); // C++17
142 template <class P>
143 iterator insert(const_iterator position, P&& p);
144 template <class InputIterator>
145 void insert(InputIterator first, InputIterator last);
146 template<container-compatible-range<value_type> R>
147 void insert_range(R&& rg); // C++23
148 void insert(initializer_list<value_type> il);
149
150 node_type extract(const_iterator position); // C++17
151 node_type extract(const key_type& x); // C++17
152 insert_return_type insert(node_type&& nh); // C++17
153 iterator insert(const_iterator hint, node_type&& nh); // C++17
154
155 template <class... Args>
156 pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
157 template <class... Args>
158 pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
159 template <class... Args>
160 iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
161 template <class... Args>
162 iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
163 template <class M>
164 pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
165 template <class M>
166 pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
167 template <class M>
168 iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
169 template <class M>
170 iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
171
172 iterator erase(const_iterator position);
173 iterator erase(iterator position); // C++14
174 size_type erase(const key_type& k);
175 iterator erase(const_iterator first, const_iterator last);
176 void clear() noexcept;
177
178 template<class C2>
179 void merge(map<Key, T, C2, Allocator>& source); // C++17
180 template<class C2>
181 void merge(map<Key, T, C2, Allocator>&& source); // C++17
182 template<class C2>
183 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
184 template<class C2>
185 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
186
187 void swap(map& m)
188 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
189 is_nothrow_swappable<key_compare>::value); // C++17
190
191 // observers:
192 allocator_type get_allocator() const noexcept;
193 key_compare key_comp() const;
194 value_compare value_comp() const;
195
196 // map operations:
197 iterator find(const key_type& k);
198 const_iterator find(const key_type& k) const;
199 template<typename K>
200 iterator find(const K& x); // C++14
201 template<typename K>
202 const_iterator find(const K& x) const; // C++14
203
204 template<typename K>
205 size_type count(const K& x) const; // C++14
206 size_type count(const key_type& k) const;
207
208 bool contains(const key_type& x) const; // C++20
209 template<class K> bool contains(const K& x) const; // C++20
210
211 iterator lower_bound(const key_type& k);
212 const_iterator lower_bound(const key_type& k) const;
213 template<typename K>
214 iterator lower_bound(const K& x); // C++14
215 template<typename K>
216 const_iterator lower_bound(const K& x) const; // C++14
217
218 iterator upper_bound(const key_type& k);
219 const_iterator upper_bound(const key_type& k) const;
220 template<typename K>
221 iterator upper_bound(const K& x); // C++14
222 template<typename K>
223 const_iterator upper_bound(const K& x) const; // C++14
224
225 pair<iterator,iterator> equal_range(const key_type& k);
226 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
227 template<typename K>
228 pair<iterator,iterator> equal_range(const K& x); // C++14
229 template<typename K>
230 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
231 };
232
233 template <class InputIterator,
234 class Compare = less<iter_key_t<InputIterator>>,
235 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
236 map(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
237 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
238
239 template<ranges::input_range R, class Compare = less<range-key-type<R>,
240 class Allocator = allocator<range-to-alloc-type<R>>>
241 map(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
242 -> map<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
243
244 template<class Key, class T, class Compare = less<Key>,
245 class Allocator = allocator<pair<const Key, T>>>
246 map(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
247 -> map<Key, T, Compare, Allocator>; // C++17
248
249 template <class InputIterator, class Allocator>
250 map(InputIterator, InputIterator, Allocator)
251 -> map<iter_key_t<InputIterator>, iter_val_t<InputIterator>, less<iter_key_t<InputIterator>>,
252 Allocator>; // C++17
253
254 template<ranges::input_range R, class Allocator>
255 map(from_range_t, R&&, Allocator)
256 -> map<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
257
258 template<class Key, class T, class Allocator>
259 map(initializer_list<pair<const Key, T>>, Allocator) -> map<Key, T, less<Key>, Allocator>; // C++17
260
261 template <class Key, class T, class Compare, class Allocator>
262 bool
263 operator==(const map<Key, T, Compare, Allocator>& x,
264 const map<Key, T, Compare, Allocator>& y);
265
266 template <class Key, class T, class Compare, class Allocator>
267 bool
268 operator< (const map<Key, T, Compare, Allocator>& x,
269 const map<Key, T, Compare, Allocator>& y); // removed in C++20
270
271 template <class Key, class T, class Compare, class Allocator>
272 bool
273 operator!=(const map<Key, T, Compare, Allocator>& x,
274 const map<Key, T, Compare, Allocator>& y); // removed in C++20
275
276 template <class Key, class T, class Compare, class Allocator>
277 bool
278 operator> (const map<Key, T, Compare, Allocator>& x,
279 const map<Key, T, Compare, Allocator>& y); // removed in C++20
280
281 template <class Key, class T, class Compare, class Allocator>
282 bool
283 operator>=(const map<Key, T, Compare, Allocator>& x,
284 const map<Key, T, Compare, Allocator>& y); // removed in C++20
285
286 template <class Key, class T, class Compare, class Allocator>
287 bool
288 operator<=(const map<Key, T, Compare, Allocator>& x,
289 const map<Key, T, Compare, Allocator>& y); // removed in C++20
290
291 template<class Key, class T, class Compare, class Allocator>
292 synth-three-way-result<pair<const Key, T>>
293 operator<=>(const map<Key, T, Compare, Allocator>& x,
294 const map<Key, T, Compare, Allocator>& y); // since C++20
295
296 // specialized algorithms:
297 template <class Key, class T, class Compare, class Allocator>
298 void
299 swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
300 noexcept(noexcept(x.swap(y)));
301
302 template <class Key, class T, class Compare, class Allocator, class Predicate>
303 typename map<Key, T, Compare, Allocator>::size_type
304 erase_if(map<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
305
306
307 template <class Key, class T, class Compare = less<Key>,
308 class Allocator = allocator<pair<const Key, T>>>
309 class multimap
310 {
311 public:
312 // types:
313 typedef Key key_type;
314 typedef T mapped_type;
315 typedef pair<const key_type,mapped_type> value_type;
316 typedef Compare key_compare;
317 typedef Allocator allocator_type;
318 typedef typename allocator_type::reference reference;
319 typedef typename allocator_type::const_reference const_reference;
320 typedef typename allocator_type::size_type size_type;
321 typedef typename allocator_type::difference_type difference_type;
322 typedef typename allocator_type::pointer pointer;
323 typedef typename allocator_type::const_pointer const_pointer;
324
325 typedef implementation-defined iterator;
326 typedef implementation-defined const_iterator;
327 typedef std::reverse_iterator<iterator> reverse_iterator;
328 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
329 typedef unspecified node_type; // C++17
330
331 class value_compare
332 {
333 friend class multimap;
334 protected:
335 key_compare comp;
336 value_compare(key_compare c);
337 public:
338 typedef bool result_type; // deprecated in C++17, removed in C++20
339 typedef value_type first_argument_type; // deprecated in C++17, removed in C++20
340 typedef value_type second_argument_type; // deprecated in C++17, removed in C++20
341 bool operator()(const value_type& x, const value_type& y) const;
342 };
343
344 // construct/copy/destroy:
345 multimap()
346 noexcept(
347 is_nothrow_default_constructible<allocator_type>::value &&
348 is_nothrow_default_constructible<key_compare>::value &&
349 is_nothrow_copy_constructible<key_compare>::value);
350 explicit multimap(const key_compare& comp);
351 multimap(const key_compare& comp, const allocator_type& a);
352 template <class InputIterator>
353 multimap(InputIterator first, InputIterator last, const key_compare& comp);
354 template <class InputIterator>
355 multimap(InputIterator first, InputIterator last, const key_compare& comp,
356 const allocator_type& a);
357 template<container-compatible-range<value_type> R>
358 multimap(from_range_t, R&& rg,
359 const Compare& comp = Compare(), const Allocator& = Allocator()); // C++23
360 multimap(const multimap& m);
361 multimap(multimap&& m)
362 noexcept(
363 is_nothrow_move_constructible<allocator_type>::value &&
364 is_nothrow_move_constructible<key_compare>::value);
365 explicit multimap(const allocator_type& a);
366 multimap(const multimap& m, const allocator_type& a);
367 multimap(multimap&& m, const allocator_type& a);
368 multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
369 multimap(initializer_list<value_type> il, const key_compare& comp,
370 const allocator_type& a);
371 template <class InputIterator>
372 multimap(InputIterator first, InputIterator last, const allocator_type& a)
373 : multimap(first, last, Compare(), a) {} // C++14
374 template<container-compatible-range<value_type> R>
375 multimap(from_range_t, R&& rg, const Allocator& a))
376 : multimap(from_range, std::forward<R>(rg), Compare(), a) { } // C++23
377 multimap(initializer_list<value_type> il, const allocator_type& a)
378 : multimap(il, Compare(), a) {} // C++14
379 ~multimap();
380
381 multimap& operator=(const multimap& m);
382 multimap& operator=(multimap&& m)
383 noexcept(
384 allocator_type::propagate_on_container_move_assignment::value &&
385 is_nothrow_move_assignable<allocator_type>::value &&
386 is_nothrow_move_assignable<key_compare>::value);
387 multimap& operator=(initializer_list<value_type> il);
388
389 // iterators:
390 iterator begin() noexcept;
391 const_iterator begin() const noexcept;
392 iterator end() noexcept;
393 const_iterator end() const noexcept;
394
395 reverse_iterator rbegin() noexcept;
396 const_reverse_iterator rbegin() const noexcept;
397 reverse_iterator rend() noexcept;
398 const_reverse_iterator rend() const noexcept;
399
400 const_iterator cbegin() const noexcept;
401 const_iterator cend() const noexcept;
402 const_reverse_iterator crbegin() const noexcept;
403 const_reverse_iterator crend() const noexcept;
404
405 // capacity:
406 bool empty() const noexcept;
407 size_type size() const noexcept;
408 size_type max_size() const noexcept;
409
410 // modifiers:
411 template <class... Args>
412 iterator emplace(Args&&... args);
413 template <class... Args>
414 iterator emplace_hint(const_iterator position, Args&&... args);
415 iterator insert(const value_type& v);
416 iterator insert( value_type&& v); // C++17
417 template <class P>
418 iterator insert(P&& p);
419 iterator insert(const_iterator position, const value_type& v);
420 iterator insert(const_iterator position, value_type&& v); // C++17
421 template <class P>
422 iterator insert(const_iterator position, P&& p);
423 template <class InputIterator>
424 void insert(InputIterator first, InputIterator last);
425 template<container-compatible-range<value_type> R>
426 void insert_range(R&& rg); // C++23
427 void insert(initializer_list<value_type> il);
428
429 node_type extract(const_iterator position); // C++17
430 node_type extract(const key_type& x); // C++17
431 iterator insert(node_type&& nh); // C++17
432 iterator insert(const_iterator hint, node_type&& nh); // C++17
433
434 iterator erase(const_iterator position);
435 iterator erase(iterator position); // C++14
436 size_type erase(const key_type& k);
437 iterator erase(const_iterator first, const_iterator last);
438 void clear() noexcept;
439
440 template<class C2>
441 void merge(multimap<Key, T, C2, Allocator>& source); // C++17
442 template<class C2>
443 void merge(multimap<Key, T, C2, Allocator>&& source); // C++17
444 template<class C2>
445 void merge(map<Key, T, C2, Allocator>& source); // C++17
446 template<class C2>
447 void merge(map<Key, T, C2, Allocator>&& source); // C++17
448
449 void swap(multimap& m)
450 noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
451 is_nothrow_swappable<key_compare>::value); // C++17
452
453 // observers:
454 allocator_type get_allocator() const noexcept;
455 key_compare key_comp() const;
456 value_compare value_comp() const;
457
458 // map operations:
459 iterator find(const key_type& k);
460 const_iterator find(const key_type& k) const;
461 template<typename K>
462 iterator find(const K& x); // C++14
463 template<typename K>
464 const_iterator find(const K& x) const; // C++14
465
466 template<typename K>
467 size_type count(const K& x) const; // C++14
468 size_type count(const key_type& k) const;
469
470 bool contains(const key_type& x) const; // C++20
471 template<class K> bool contains(const K& x) const; // C++20
472
473 iterator lower_bound(const key_type& k);
474 const_iterator lower_bound(const key_type& k) const;
475 template<typename K>
476 iterator lower_bound(const K& x); // C++14
477 template<typename K>
478 const_iterator lower_bound(const K& x) const; // C++14
479
480 iterator upper_bound(const key_type& k);
481 const_iterator upper_bound(const key_type& k) const;
482 template<typename K>
483 iterator upper_bound(const K& x); // C++14
484 template<typename K>
485 const_iterator upper_bound(const K& x) const; // C++14
486
487 pair<iterator,iterator> equal_range(const key_type& k);
488 pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
489 template<typename K>
490 pair<iterator,iterator> equal_range(const K& x); // C++14
491 template<typename K>
492 pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
493 };
494
495 template <class InputIterator,
496 class Compare = less<iter_key_t<InputIterator>>,
497 class Allocator = allocator<iter_to_alloc_t<InputIterator>>>
498 multimap(InputIterator, InputIterator, Compare = Compare(), Allocator = Allocator())
499 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>, Compare, Allocator>; // C++17
500
501 template<ranges::input_range R, class Compare = less<range-key-type<R>>,
502 class Allocator = allocator<range-to-alloc-type<R>>>
503 multimap(from_range_t, R&&, Compare = Compare(), Allocator = Allocator())
504 -> multimap<range-key-type<R>, range-mapped-type<R>, Compare, Allocator>; // C++23
505
506 template<class Key, class T, class Compare = less<Key>,
507 class Allocator = allocator<pair<const Key, T>>>
508 multimap(initializer_list<pair<const Key, T>>, Compare = Compare(), Allocator = Allocator())
509 -> multimap<Key, T, Compare, Allocator>; // C++17
510
511 template <class InputIterator, class Allocator>
512 multimap(InputIterator, InputIterator, Allocator)
513 -> multimap<iter_key_t<InputIterator>, iter_val_t<InputIterator>,
514 less<iter_key_t<InputIterator>>, Allocator>; // C++17
515
516 template<ranges::input_range R, class Allocator>
517 multimap(from_range_t, R&&, Allocator)
518 -> multimap<range-key-type<R>, range-mapped-type<R>, less<range-key-type<R>>, Allocator>; // C++23
519
520 template<class Key, class T, class Allocator>
521 multimap(initializer_list<pair<const Key, T>>, Allocator)
522 -> multimap<Key, T, less<Key>, Allocator>; // C++17
523
524 template <class Key, class T, class Compare, class Allocator>
525 bool
526 operator==(const multimap<Key, T, Compare, Allocator>& x,
527 const multimap<Key, T, Compare, Allocator>& y);
528
529 template <class Key, class T, class Compare, class Allocator>
530 bool
531 operator< (const multimap<Key, T, Compare, Allocator>& x,
532 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
533
534 template <class Key, class T, class Compare, class Allocator>
535 bool
536 operator!=(const multimap<Key, T, Compare, Allocator>& x,
537 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
538
539 template <class Key, class T, class Compare, class Allocator>
540 bool
541 operator> (const multimap<Key, T, Compare, Allocator>& x,
542 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
543
544 template <class Key, class T, class Compare, class Allocator>
545 bool
546 operator>=(const multimap<Key, T, Compare, Allocator>& x,
547 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
548
549 template <class Key, class T, class Compare, class Allocator>
550 bool
551 operator<=(const multimap<Key, T, Compare, Allocator>& x,
552 const multimap<Key, T, Compare, Allocator>& y); // removed in C++20
553
554 template<class Key, class T, class Compare, class Allocator>
555 synth-three-way-result<pair<const Key, T>>
556 operator<=>(const multimap<Key, T, Compare, Allocator>& x,
557 const multimap<Key, T, Compare, Allocator>& y); // since c++20
558
559 // specialized algorithms:
560 template <class Key, class T, class Compare, class Allocator>
561 void
562 swap(multimap<Key, T, Compare, Allocator>& x,
563 multimap<Key, T, Compare, Allocator>& y)
564 noexcept(noexcept(x.swap(y)));
565
566 template <class Key, class T, class Compare, class Allocator, class Predicate>
567 typename multimap<Key, T, Compare, Allocator>::size_type
568 erase_if(multimap<Key, T, Compare, Allocator>& c, Predicate pred); // C++20
569
570 } // std
571
572 */
573
574 #include <__cxx03/__algorithm/equal.h>
575 #include <__cxx03/__algorithm/lexicographical_compare.h>
576 #include <__cxx03/__assert>
577 #include <__cxx03/__config>
578 #include <__cxx03/__functional/binary_function.h>
579 #include <__cxx03/__functional/operations.h>
580 #include <__cxx03/__iterator/erase_if_container.h>
581 #include <__cxx03/__iterator/iterator_traits.h>
582 #include <__cxx03/__iterator/reverse_iterator.h>
583 #include <__cxx03/__memory/addressof.h>
584 #include <__cxx03/__memory/allocator.h>
585 #include <__cxx03/__tree>
586 #include <__cxx03/__type_traits/is_allocator.h>
587 #include <__cxx03/__utility/forward.h>
588 #include <__cxx03/__utility/piecewise_construct.h>
589 #include <__cxx03/__utility/swap.h>
590 #include <__cxx03/stdexcept>
591 #include <__cxx03/version>
592
593 // standard-mandated includes
594
595 // [iterator.range]
596 #include <__cxx03/__iterator/access.h>
597
598 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
599 # pragma GCC system_header
600 #endif
601
602 _LIBCPP_PUSH_MACROS
603 #include <__cxx03/__undef_macros>
604
605 _LIBCPP_BEGIN_NAMESPACE_STD
606
607 template <class _Key,
608 class _CP,
609 class _Compare,
610 bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>
611 class __map_value_compare : private _Compare {
612 public:
613 _LIBCPP_HIDE_FROM_ABI __map_value_compare() : _Compare() {}
614 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) : _Compare(__c) {}
615 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return *this; }
616 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
617 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y.__get_value().first);
618 }
619 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
620 return static_cast<const _Compare&>(*this)(__x.__get_value().first, __y);
621 }
622 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
623 return static_cast<const _Compare&>(*this)(__x, __y.__get_value().first);
624 }
625 _LIBCPP_HIDE_FROM_ABI void swap(__map_value_compare& __y) {
626 using std::swap;
627 swap(static_cast<_Compare&>(*this), static_cast<_Compare&>(__y));
628 }
629 };
630
631 template <class _Key, class _CP, class _Compare>
632 class __map_value_compare<_Key, _CP, _Compare, false> {
633 _Compare __comp_;
634
635 public:
636 _LIBCPP_HIDE_FROM_ABI __map_value_compare() : __comp_() {}
637 _LIBCPP_HIDE_FROM_ABI __map_value_compare(_Compare __c) : __comp_(__c) {}
638 _LIBCPP_HIDE_FROM_ABI const _Compare& key_comp() const _NOEXCEPT { return __comp_; }
639
640 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _CP& __y) const {
641 return __comp_(__x.__get_value().first, __y.__get_value().first);
642 }
643 _LIBCPP_HIDE_FROM_ABI bool operator()(const _CP& __x, const _Key& __y) const {
644 return __comp_(__x.__get_value().first, __y);
645 }
646 _LIBCPP_HIDE_FROM_ABI bool operator()(const _Key& __x, const _CP& __y) const {
647 return __comp_(__x, __y.__get_value().first);
648 }
649 void swap(__map_value_compare& __y) {
650 using std::swap;
651 swap(__comp_, __y.__comp_);
652 }
653 };
654
655 template <class _Key, class _CP, class _Compare, bool __b>
656 inline _LIBCPP_HIDE_FROM_ABI void
657 swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x, __map_value_compare<_Key, _CP, _Compare, __b>& __y) {
658 __x.swap(__y);
659 }
660
661 template <class _Allocator>
662 class __map_node_destructor {
663 typedef _Allocator allocator_type;
664 typedef allocator_traits<allocator_type> __alloc_traits;
665
666 public:
667 typedef typename __alloc_traits::pointer pointer;
668
669 private:
670 allocator_type& __na_;
671
672 public:
673 bool __first_constructed;
674 bool __second_constructed;
675
676 _LIBCPP_HIDE_FROM_ABI explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
677 : __na_(__na),
678 __first_constructed(false),
679 __second_constructed(false) {}
680
681 __map_node_destructor& operator=(const __map_node_destructor&) = delete;
682
683 _LIBCPP_HIDE_FROM_ABI void operator()(pointer __p) _NOEXCEPT {
684 if (__second_constructed)
685 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().second));
686 if (__first_constructed)
687 __alloc_traits::destroy(__na_, std::addressof(__p->__value_.__get_value().first));
688 if (__p)
689 __alloc_traits::deallocate(__na_, __p, 1);
690 }
691 };
692
693 template <class _Key, class _Tp, class _Compare, class _Allocator>
694 class map;
695 template <class _Key, class _Tp, class _Compare, class _Allocator>
696 class multimap;
697 template <class _TreeIterator>
698 class __map_const_iterator;
699
700 template <class _Key, class _Tp>
701 struct __value_type {
702 typedef _Key key_type;
703 typedef _Tp mapped_type;
704 typedef pair<const key_type, mapped_type> value_type;
705
706 private:
707 value_type __cc_;
708
709 public:
710 _LIBCPP_HIDE_FROM_ABI value_type& __get_value() { return __cc_; }
711 _LIBCPP_HIDE_FROM_ABI const value_type& __get_value() const { return __cc_; }
712
713 __value_type() = delete;
714 __value_type(__value_type const&) = delete;
715 __value_type& operator=(__value_type const&) = delete;
716 ~__value_type() = delete;
717 };
718
719 template <class _Tp>
720 struct __extract_key_value_types;
721
722 template <class _Key, class _Tp>
723 struct __extract_key_value_types<__value_type<_Key, _Tp> > {
724 typedef _Key const __key_type;
725 typedef _Tp __mapped_type;
726 };
727
728 template <class _TreeIterator>
729 class _LIBCPP_TEMPLATE_VIS __map_iterator {
730 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
731 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
732
733 _TreeIterator __i_;
734
735 public:
736 typedef bidirectional_iterator_tag iterator_category;
737 typedef typename _NodeTypes::__map_value_type value_type;
738 typedef typename _TreeIterator::difference_type difference_type;
739 typedef value_type& reference;
740 typedef typename _NodeTypes::__map_value_type_pointer pointer;
741
742 _LIBCPP_HIDE_FROM_ABI __map_iterator() _NOEXCEPT {}
743
744 _LIBCPP_HIDE_FROM_ABI __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
745
746 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
747 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
748
749 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator++() {
750 ++__i_;
751 return *this;
752 }
753 _LIBCPP_HIDE_FROM_ABI __map_iterator operator++(int) {
754 __map_iterator __t(*this);
755 ++(*this);
756 return __t;
757 }
758
759 _LIBCPP_HIDE_FROM_ABI __map_iterator& operator--() {
760 --__i_;
761 return *this;
762 }
763 _LIBCPP_HIDE_FROM_ABI __map_iterator operator--(int) {
764 __map_iterator __t(*this);
765 --(*this);
766 return __t;
767 }
768
769 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_iterator& __x, const __map_iterator& __y) {
770 return __x.__i_ == __y.__i_;
771 }
772 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_iterator& __x, const __map_iterator& __y) {
773 return __x.__i_ != __y.__i_;
774 }
775
776 template <class, class, class, class>
777 friend class _LIBCPP_TEMPLATE_VIS map;
778 template <class, class, class, class>
779 friend class _LIBCPP_TEMPLATE_VIS multimap;
780 template <class>
781 friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;
782 };
783
784 template <class _TreeIterator>
785 class _LIBCPP_TEMPLATE_VIS __map_const_iterator {
786 typedef typename _TreeIterator::_NodeTypes _NodeTypes;
787 typedef typename _TreeIterator::__pointer_traits __pointer_traits;
788
789 _TreeIterator __i_;
790
791 public:
792 typedef bidirectional_iterator_tag iterator_category;
793 typedef typename _NodeTypes::__map_value_type value_type;
794 typedef typename _TreeIterator::difference_type difference_type;
795 typedef const value_type& reference;
796 typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
797
798 _LIBCPP_HIDE_FROM_ABI __map_const_iterator() _NOEXCEPT {}
799
800 _LIBCPP_HIDE_FROM_ABI __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
801 _LIBCPP_HIDE_FROM_ABI
802 __map_const_iterator(__map_iterator< typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT : __i_(__i.__i_) {}
803
804 _LIBCPP_HIDE_FROM_ABI reference operator*() const { return __i_->__get_value(); }
805 _LIBCPP_HIDE_FROM_ABI pointer operator->() const { return pointer_traits<pointer>::pointer_to(__i_->__get_value()); }
806
807 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator++() {
808 ++__i_;
809 return *this;
810 }
811 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator++(int) {
812 __map_const_iterator __t(*this);
813 ++(*this);
814 return __t;
815 }
816
817 _LIBCPP_HIDE_FROM_ABI __map_const_iterator& operator--() {
818 --__i_;
819 return *this;
820 }
821 _LIBCPP_HIDE_FROM_ABI __map_const_iterator operator--(int) {
822 __map_const_iterator __t(*this);
823 --(*this);
824 return __t;
825 }
826
827 friend _LIBCPP_HIDE_FROM_ABI bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y) {
828 return __x.__i_ == __y.__i_;
829 }
830 friend _LIBCPP_HIDE_FROM_ABI bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y) {
831 return __x.__i_ != __y.__i_;
832 }
833
834 template <class, class, class, class>
835 friend class _LIBCPP_TEMPLATE_VIS map;
836 template <class, class, class, class>
837 friend class _LIBCPP_TEMPLATE_VIS multimap;
838 template <class, class, class>
839 friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;
840 };
841
842 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
843 class _LIBCPP_TEMPLATE_VIS map {
844 public:
845 // types:
846 typedef _Key key_type;
847 typedef _Tp mapped_type;
848 typedef pair<const key_type, mapped_type> value_type;
849 typedef __type_identity_t<_Compare> key_compare;
850 typedef __type_identity_t<_Allocator> allocator_type;
851 typedef value_type& reference;
852 typedef const value_type& const_reference;
853
854 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
855 "Allocator::value_type must be same type as value_type");
856
857 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
858 friend class map;
859
860 protected:
861 key_compare comp;
862
863 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
864
865 public:
866 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
867 return comp(__x.first, __y.first);
868 }
869 };
870
871 private:
872 typedef std::__value_type<key_type, mapped_type> __value_type;
873 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
874 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
875 typedef __tree<__value_type, __vc, __allocator_type> __base;
876 typedef typename __base::__node_traits __node_traits;
877 typedef allocator_traits<allocator_type> __alloc_traits;
878
879 static_assert(__check_valid_allocator<allocator_type>::value, "");
880
881 __base __tree_;
882
883 public:
884 typedef typename __alloc_traits::pointer pointer;
885 typedef typename __alloc_traits::const_pointer const_pointer;
886 typedef typename __alloc_traits::size_type size_type;
887 typedef typename __alloc_traits::difference_type difference_type;
888 typedef __map_iterator<typename __base::iterator> iterator;
889 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
890 typedef std::reverse_iterator<iterator> reverse_iterator;
891 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
892
893 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
894 friend class _LIBCPP_TEMPLATE_VIS map;
895 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
896 friend class _LIBCPP_TEMPLATE_VIS multimap;
897
898 _LIBCPP_HIDE_FROM_ABI map() : __tree_(__vc(key_compare())) {}
899
900 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp) : __tree_(__vc(__comp)) {}
901
902 _LIBCPP_HIDE_FROM_ABI explicit map(const key_compare& __comp, const allocator_type& __a)
903 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
904
905 template <class _InputIterator>
906 _LIBCPP_HIDE_FROM_ABI map(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
907 : __tree_(__vc(__comp)) {
908 insert(__f, __l);
909 }
910
911 template <class _InputIterator>
912 _LIBCPP_HIDE_FROM_ABI
913 map(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
914 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
915 insert(__f, __l);
916 }
917
918 _LIBCPP_HIDE_FROM_ABI map(const map& __m) : __tree_(__m.__tree_) { insert(__m.begin(), __m.end()); }
919
920 _LIBCPP_HIDE_FROM_ABI map& operator=(const map& __m) {
921 if (this != std::addressof(__m)) {
922 __tree_.clear();
923 __tree_.value_comp() = __m.__tree_.value_comp();
924 __tree_.__copy_assign_alloc(__m.__tree_);
925 insert(__m.begin(), __m.end());
926 }
927 return *this;
928 }
929
930 _LIBCPP_HIDE_FROM_ABI explicit map(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
931
932 _LIBCPP_HIDE_FROM_ABI map(const map& __m, const allocator_type& __a)
933 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
934 insert(__m.begin(), __m.end());
935 }
936
937 _LIBCPP_HIDE_FROM_ABI ~map() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
938
939 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
940 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
941 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
942 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
943
944 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
945 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
946 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
947 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
948
949 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
950 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
951 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
952 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
953
954 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
955 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
956 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
957
958 _LIBCPP_HIDE_FROM_ABI mapped_type& operator[](const key_type& __k);
959
960 _LIBCPP_HIDE_FROM_ABI mapped_type& at(const key_type& __k);
961 _LIBCPP_HIDE_FROM_ABI const mapped_type& at(const key_type& __k) const;
962
963 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
964 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
965 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
966
967 _LIBCPP_HIDE_FROM_ABI pair<iterator, bool> insert(const value_type& __v) { return __tree_.__insert_unique(__v); }
968
969 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
970 return __tree_.__insert_unique(__p.__i_, __v);
971 }
972
973 template <class _InputIterator>
974 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
975 for (const_iterator __e = cend(); __f != __l; ++__f)
976 insert(__e.__i_, *__f);
977 }
978
979 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
980 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
981 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_unique(__k); }
982 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
983 return __tree_.erase(__f.__i_, __l.__i_);
984 }
985 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
986
987 _LIBCPP_HIDE_FROM_ABI void swap(map& __m) { __tree_.swap(__m.__tree_); }
988
989 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
990 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
991
992 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_unique(__k); }
993
994 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
995 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
996
997 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
998 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
999
1000 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1001 return __tree_.__equal_range_unique(__k);
1002 }
1003 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1004 return __tree_.__equal_range_unique(__k);
1005 }
1006
1007 private:
1008 typedef typename __base::__node __node;
1009 typedef typename __base::__node_allocator __node_allocator;
1010 typedef typename __base::__node_pointer __node_pointer;
1011 typedef typename __base::__node_base_pointer __node_base_pointer;
1012 typedef typename __base::__parent_pointer __parent_pointer;
1013
1014 typedef __map_node_destructor<__node_allocator> _Dp;
1015 typedef unique_ptr<__node, _Dp> __node_holder;
1016
1017 _LIBCPP_HIDE_FROM_ABI __node_holder __construct_node_with_key(const key_type& __k);
1018 };
1019
1020 template <class _Key, class _Tp, class _Compare, class _Allocator>
1021 typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
1022 map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k) {
1023 __node_allocator& __na = __tree_.__node_alloc();
1024 __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
1025 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().first), __k);
1026 __h.get_deleter().__first_constructed = true;
1027 __node_traits::construct(__na, std::addressof(__h->__value_.__get_value().second));
1028 __h.get_deleter().__second_constructed = true;
1029 return __h;
1030 }
1031
1032 template <class _Key, class _Tp, class _Compare, class _Allocator>
1033 _Tp& map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k) {
1034 __parent_pointer __parent;
1035 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1036 __node_pointer __r = static_cast<__node_pointer>(__child);
1037 if (__child == nullptr) {
1038 __node_holder __h = __construct_node_with_key(__k);
1039 __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
1040 __r = __h.release();
1041 }
1042 return __r->__value_.__get_value().second;
1043 }
1044
1045 template <class _Key, class _Tp, class _Compare, class _Allocator>
1046 _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) {
1047 __parent_pointer __parent;
1048 __node_base_pointer& __child = __tree_.__find_equal(__parent, __k);
1049 if (__child == nullptr)
1050 __throw_out_of_range("map::at: key not found");
1051 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1052 }
1053
1054 template <class _Key, class _Tp, class _Compare, class _Allocator>
1055 const _Tp& map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const {
1056 __parent_pointer __parent;
1057 __node_base_pointer __child = __tree_.__find_equal(__parent, __k);
1058 if (__child == nullptr)
1059 __throw_out_of_range("map::at: key not found");
1060 return static_cast<__node_pointer>(__child)->__value_.__get_value().second;
1061 }
1062
1063 template <class _Key, class _Tp, class _Compare, class _Allocator>
1064 inline _LIBCPP_HIDE_FROM_ABI bool
1065 operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1066 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1067 }
1068
1069 template <class _Key, class _Tp, class _Compare, class _Allocator>
1070 inline _LIBCPP_HIDE_FROM_ABI bool
1071 operator<(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1072 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1073 }
1074
1075 template <class _Key, class _Tp, class _Compare, class _Allocator>
1076 inline _LIBCPP_HIDE_FROM_ABI bool
1077 operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1078 return !(__x == __y);
1079 }
1080
1081 template <class _Key, class _Tp, class _Compare, class _Allocator>
1082 inline _LIBCPP_HIDE_FROM_ABI bool
1083 operator>(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1084 return __y < __x;
1085 }
1086
1087 template <class _Key, class _Tp, class _Compare, class _Allocator>
1088 inline _LIBCPP_HIDE_FROM_ABI bool
1089 operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1090 return !(__x < __y);
1091 }
1092
1093 template <class _Key, class _Tp, class _Compare, class _Allocator>
1094 inline _LIBCPP_HIDE_FROM_ABI bool
1095 operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x, const map<_Key, _Tp, _Compare, _Allocator>& __y) {
1096 return !(__y < __x);
1097 }
1098
1099 template <class _Key, class _Tp, class _Compare, class _Allocator>
1100 inline _LIBCPP_HIDE_FROM_ABI void
1101 swap(map<_Key, _Tp, _Compare, _Allocator>& __x, map<_Key, _Tp, _Compare, _Allocator>& __y) {
1102 __x.swap(__y);
1103 }
1104
1105 template <class _Key, class _Tp, class _Compare = less<_Key>, class _Allocator = allocator<pair<const _Key, _Tp> > >
1106 class _LIBCPP_TEMPLATE_VIS multimap {
1107 public:
1108 // types:
1109 typedef _Key key_type;
1110 typedef _Tp mapped_type;
1111 typedef pair<const key_type, mapped_type> value_type;
1112 typedef __type_identity_t<_Compare> key_compare;
1113 typedef __type_identity_t<_Allocator> allocator_type;
1114 typedef value_type& reference;
1115 typedef const value_type& const_reference;
1116
1117 static_assert(__check_valid_allocator<allocator_type>::value, "");
1118 static_assert(is_same<typename allocator_type::value_type, value_type>::value,
1119 "Allocator::value_type must be same type as value_type");
1120
1121 class _LIBCPP_TEMPLATE_VIS value_compare : public __binary_function<value_type, value_type, bool> {
1122 friend class multimap;
1123
1124 protected:
1125 key_compare comp;
1126
1127 _LIBCPP_HIDE_FROM_ABI value_compare(key_compare __c) : comp(__c) {}
1128
1129 public:
1130 _LIBCPP_HIDE_FROM_ABI bool operator()(const value_type& __x, const value_type& __y) const {
1131 return comp(__x.first, __y.first);
1132 }
1133 };
1134
1135 private:
1136 typedef std::__value_type<key_type, mapped_type> __value_type;
1137 typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
1138 typedef __rebind_alloc<allocator_traits<allocator_type>, __value_type> __allocator_type;
1139 typedef __tree<__value_type, __vc, __allocator_type> __base;
1140 typedef typename __base::__node_traits __node_traits;
1141 typedef allocator_traits<allocator_type> __alloc_traits;
1142
1143 __base __tree_;
1144
1145 public:
1146 typedef typename __alloc_traits::pointer pointer;
1147 typedef typename __alloc_traits::const_pointer const_pointer;
1148 typedef typename __alloc_traits::size_type size_type;
1149 typedef typename __alloc_traits::difference_type difference_type;
1150 typedef __map_iterator<typename __base::iterator> iterator;
1151 typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
1152 typedef std::reverse_iterator<iterator> reverse_iterator;
1153 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1154
1155 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1156 friend class _LIBCPP_TEMPLATE_VIS map;
1157 template <class _Key2, class _Value2, class _Comp2, class _Alloc2>
1158 friend class _LIBCPP_TEMPLATE_VIS multimap;
1159
1160 _LIBCPP_HIDE_FROM_ABI multimap() : __tree_(__vc(key_compare())) {}
1161
1162 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp) : __tree_(__vc(__comp)) {}
1163
1164 _LIBCPP_HIDE_FROM_ABI explicit multimap(const key_compare& __comp, const allocator_type& __a)
1165 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
1166
1167 template <class _InputIterator>
1168 _LIBCPP_HIDE_FROM_ABI multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp = key_compare())
1169 : __tree_(__vc(__comp)) {
1170 insert(__f, __l);
1171 }
1172
1173 template <class _InputIterator>
1174 _LIBCPP_HIDE_FROM_ABI
1175 multimap(_InputIterator __f, _InputIterator __l, const key_compare& __comp, const allocator_type& __a)
1176 : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {
1177 insert(__f, __l);
1178 }
1179
1180 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m)
1181 : __tree_(__m.__tree_.value_comp(),
1182 __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc())) {
1183 insert(__m.begin(), __m.end());
1184 }
1185
1186 _LIBCPP_HIDE_FROM_ABI multimap& operator=(const multimap& __m) {
1187 if (this != std::addressof(__m)) {
1188 __tree_.clear();
1189 __tree_.value_comp() = __m.__tree_.value_comp();
1190 __tree_.__copy_assign_alloc(__m.__tree_);
1191 insert(__m.begin(), __m.end());
1192 }
1193 return *this;
1194 }
1195
1196 _LIBCPP_HIDE_FROM_ABI explicit multimap(const allocator_type& __a) : __tree_(typename __base::allocator_type(__a)) {}
1197
1198 _LIBCPP_HIDE_FROM_ABI multimap(const multimap& __m, const allocator_type& __a)
1199 : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a)) {
1200 insert(__m.begin(), __m.end());
1201 }
1202
1203 _LIBCPP_HIDE_FROM_ABI ~multimap() { static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), ""); }
1204
1205 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __tree_.begin(); }
1206 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __tree_.begin(); }
1207 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __tree_.end(); }
1208 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __tree_.end(); }
1209
1210 _LIBCPP_HIDE_FROM_ABI reverse_iterator rbegin() _NOEXCEPT { return reverse_iterator(end()); }
1211 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rbegin() const _NOEXCEPT { return const_reverse_iterator(end()); }
1212 _LIBCPP_HIDE_FROM_ABI reverse_iterator rend() _NOEXCEPT { return reverse_iterator(begin()); }
1213 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator rend() const _NOEXCEPT { return const_reverse_iterator(begin()); }
1214
1215 _LIBCPP_HIDE_FROM_ABI const_iterator cbegin() const _NOEXCEPT { return begin(); }
1216 _LIBCPP_HIDE_FROM_ABI const_iterator cend() const _NOEXCEPT { return end(); }
1217 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crbegin() const _NOEXCEPT { return rbegin(); }
1218 _LIBCPP_HIDE_FROM_ABI const_reverse_iterator crend() const _NOEXCEPT { return rend(); }
1219
1220 _LIBCPP_NODISCARD _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __tree_.size() == 0; }
1221 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __tree_.size(); }
1222 _LIBCPP_HIDE_FROM_ABI size_type max_size() const _NOEXCEPT { return __tree_.max_size(); }
1223
1224 _LIBCPP_HIDE_FROM_ABI allocator_type get_allocator() const _NOEXCEPT { return allocator_type(__tree_.__alloc()); }
1225 _LIBCPP_HIDE_FROM_ABI key_compare key_comp() const { return __tree_.value_comp().key_comp(); }
1226 _LIBCPP_HIDE_FROM_ABI value_compare value_comp() const { return value_compare(__tree_.value_comp().key_comp()); }
1227
1228 _LIBCPP_HIDE_FROM_ABI iterator insert(const value_type& __v) { return __tree_.__insert_multi(__v); }
1229
1230 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __p, const value_type& __v) {
1231 return __tree_.__insert_multi(__p.__i_, __v);
1232 }
1233
1234 template <class _InputIterator>
1235 _LIBCPP_HIDE_FROM_ABI void insert(_InputIterator __f, _InputIterator __l) {
1236 for (const_iterator __e = cend(); __f != __l; ++__f)
1237 __tree_.__insert_multi(__e.__i_, *__f);
1238 }
1239
1240 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __p) { return __tree_.erase(__p.__i_); }
1241 _LIBCPP_HIDE_FROM_ABI iterator erase(iterator __p) { return __tree_.erase(__p.__i_); }
1242 _LIBCPP_HIDE_FROM_ABI size_type erase(const key_type& __k) { return __tree_.__erase_multi(__k); }
1243 _LIBCPP_HIDE_FROM_ABI iterator erase(const_iterator __f, const_iterator __l) {
1244 return __tree_.erase(__f.__i_, __l.__i_);
1245 }
1246
1247 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __tree_.clear(); }
1248
1249 _LIBCPP_HIDE_FROM_ABI void swap(multimap& __m) { __tree_.swap(__m.__tree_); }
1250
1251 _LIBCPP_HIDE_FROM_ABI iterator find(const key_type& __k) { return __tree_.find(__k); }
1252 _LIBCPP_HIDE_FROM_ABI const_iterator find(const key_type& __k) const { return __tree_.find(__k); }
1253
1254 _LIBCPP_HIDE_FROM_ABI size_type count(const key_type& __k) const { return __tree_.__count_multi(__k); }
1255
1256 _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
1257 _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
1258
1259 _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
1260 _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
1261
1262 _LIBCPP_HIDE_FROM_ABI pair<iterator, iterator> equal_range(const key_type& __k) {
1263 return __tree_.__equal_range_multi(__k);
1264 }
1265 _LIBCPP_HIDE_FROM_ABI pair<const_iterator, const_iterator> equal_range(const key_type& __k) const {
1266 return __tree_.__equal_range_multi(__k);
1267 }
1268
1269 private:
1270 typedef typename __base::__node __node;
1271 typedef typename __base::__node_allocator __node_allocator;
1272 typedef typename __base::__node_pointer __node_pointer;
1273
1274 typedef __map_node_destructor<__node_allocator> _Dp;
1275 typedef unique_ptr<__node, _Dp> __node_holder;
1276 };
1277
1278 template <class _Key, class _Tp, class _Compare, class _Allocator>
1279 inline _LIBCPP_HIDE_FROM_ABI bool
1280 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1281 return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
1282 }
1283
1284 template <class _Key, class _Tp, class _Compare, class _Allocator>
1285 inline _LIBCPP_HIDE_FROM_ABI bool
1286 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1287 return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
1288 }
1289
1290 template <class _Key, class _Tp, class _Compare, class _Allocator>
1291 inline _LIBCPP_HIDE_FROM_ABI bool
1292 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1293 return !(__x == __y);
1294 }
1295
1296 template <class _Key, class _Tp, class _Compare, class _Allocator>
1297 inline _LIBCPP_HIDE_FROM_ABI bool
1298 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1299 return __y < __x;
1300 }
1301
1302 template <class _Key, class _Tp, class _Compare, class _Allocator>
1303 inline _LIBCPP_HIDE_FROM_ABI bool
1304 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1305 return !(__x < __y);
1306 }
1307
1308 template <class _Key, class _Tp, class _Compare, class _Allocator>
1309 inline _LIBCPP_HIDE_FROM_ABI bool
1310 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x, const multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1311 return !(__y < __x);
1312 }
1313
1314 template <class _Key, class _Tp, class _Compare, class _Allocator>
1315 inline _LIBCPP_HIDE_FROM_ABI void
1316 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x, multimap<_Key, _Tp, _Compare, _Allocator>& __y) {
1317 __x.swap(__y);
1318 }
1319
1320 _LIBCPP_END_NAMESPACE_STD
1321
1322 _LIBCPP_POP_MACROS
1323
1324 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES)
1325 # include <__cxx03/cstdlib>
1326 # include <__cxx03/functional>
1327 # include <__cxx03/iterator>
1328 # include <__cxx03/type_traits>
1329 # include <__cxx03/utility>
1330 #endif
1331
1332 #endif // _LIBCPP___CXX03_MAP