]>
Commit | Line | Data |
---|---|---|
285b36d6 BK |
1 | // Debugging multimap implementation -*- C++ -*- |
2 | ||
99dee823 | 3 | // Copyright (C) 2003-2021 Free Software Foundation, Inc. |
285b36d6 BK |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
285b36d6 BK |
9 | // any later version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
19 | ||
20 | // You should have received a copy of the GNU General Public License and | |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
285b36d6 | 24 | |
78a53887 BK |
25 | /** @file debug/multimap.h |
26 | * This file is a GNU debug extension to the Standard C++ Library. | |
27 | */ | |
28 | ||
285b36d6 BK |
29 | #ifndef _GLIBCXX_DEBUG_MULTIMAP_H |
30 | #define _GLIBCXX_DEBUG_MULTIMAP_H 1 | |
31 | ||
32 | #include <debug/safe_sequence.h> | |
15ee1a77 | 33 | #include <debug/safe_container.h> |
285b36d6 | 34 | #include <debug/safe_iterator.h> |
16158c96 | 35 | #include <bits/stl_pair.h> |
285b36d6 | 36 | |
12ffa228 | 37 | namespace std _GLIBCXX_VISIBILITY(default) |
3cbc7af0 | 38 | { |
45f388bb | 39 | namespace __debug |
285b36d6 | 40 | { |
1ceb9e06 | 41 | /// Class std::multimap with safety/checking/debug instrumentation. |
285b36d6 BK |
42 | template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, |
43 | typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > | |
526da49c | 44 | class multimap |
15ee1a77 FD |
45 | : public __gnu_debug::_Safe_container< |
46 | multimap<_Key, _Tp, _Compare, _Allocator>, _Allocator, | |
47 | __gnu_debug::_Safe_node_sequence>, | |
48 | public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> | |
285b36d6 | 49 | { |
15ee1a77 FD |
50 | typedef _GLIBCXX_STD_C::multimap< |
51 | _Key, _Tp, _Compare, _Allocator> _Base; | |
52 | typedef __gnu_debug::_Safe_container< | |
53 | multimap, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; | |
526da49c | 54 | |
15ee1a77 FD |
55 | typedef typename _Base::const_iterator _Base_const_iterator; |
56 | typedef typename _Base::iterator _Base_iterator; | |
afe96d41 | 57 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; |
51835a80 | 58 | |
e9afbed0 FD |
59 | template<typename _ItT, typename _SeqT, typename _CatT> |
60 | friend class ::__gnu_debug::_Safe_iterator; | |
61 | ||
eca833b8 JW |
62 | // Reference wrapper for base class. Disambiguates multimap(const _Base&) |
63 | // from copy constructor by requiring a user-defined conversion. | |
64 | // See PR libstdc++/90102. | |
65 | struct _Base_ref | |
66 | { | |
67 | _Base_ref(const _Base& __r) : _M_ref(__r) { } | |
68 | ||
69 | const _Base& _M_ref; | |
70 | }; | |
71 | ||
285b36d6 BK |
72 | public: |
73 | // types: | |
15ee1a77 FD |
74 | typedef _Key key_type; |
75 | typedef _Tp mapped_type; | |
76 | typedef std::pair<const _Key, _Tp> value_type; | |
77 | typedef _Compare key_compare; | |
78 | typedef _Allocator allocator_type; | |
79 | typedef typename _Base::reference reference; | |
80 | typedef typename _Base::const_reference const_reference; | |
526da49c | 81 | |
afe96d41 | 82 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> |
15ee1a77 | 83 | iterator; |
afe96d41 | 84 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
15ee1a77 | 85 | multimap> const_iterator; |
285b36d6 | 86 | |
15ee1a77 FD |
87 | typedef typename _Base::size_type size_type; |
88 | typedef typename _Base::difference_type difference_type; | |
89 | typedef typename _Base::pointer pointer; | |
90 | typedef typename _Base::const_pointer const_pointer; | |
91 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
92 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
526da49c | 93 | |
285b36d6 | 94 | // 23.3.1.1 construct/copy/destroy: |
c3cdd71f | 95 | |
15ee1a77 | 96 | #if __cplusplus < 201103L |
c3cdd71f JW |
97 | multimap() : _Base() { } |
98 | ||
ed540c0a | 99 | multimap(const multimap& __x) |
4c2d93db | 100 | : _Base(__x) { } |
285b36d6 | 101 | |
15ee1a77 FD |
102 | ~multimap() { } |
103 | #else | |
104 | multimap() = default; | |
105 | multimap(const multimap&) = default; | |
106 | multimap(multimap&&) = default; | |
988499f4 JM |
107 | |
108 | multimap(initializer_list<value_type> __l, | |
109 | const _Compare& __c = _Compare(), | |
110 | const allocator_type& __a = allocator_type()) | |
4c2d93db | 111 | : _Base(__l, __c, __a) { } |
51835a80 FD |
112 | |
113 | explicit | |
114 | multimap(const allocator_type& __a) | |
115 | : _Base(__a) { } | |
116 | ||
22d34a2a JW |
117 | multimap(const multimap& __m, |
118 | const __type_identity_t<allocator_type>& __a) | |
51835a80 FD |
119 | : _Base(__m, __a) { } |
120 | ||
22d34a2a | 121 | multimap(multimap&& __m, const __type_identity_t<allocator_type>& __a) |
8b0cd47a | 122 | noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) ) |
15ee1a77 FD |
123 | : _Safe(std::move(__m._M_safe()), __a), |
124 | _Base(std::move(__m._M_base()), __a) { } | |
51835a80 FD |
125 | |
126 | multimap(initializer_list<value_type> __l, const allocator_type& __a) | |
15ee1a77 | 127 | : _Base(__l, __a) { } |
51835a80 FD |
128 | |
129 | template<typename _InputIterator> | |
15ee1a77 | 130 | multimap(_InputIterator __first, _InputIterator __last, |
51835a80 | 131 | const allocator_type& __a) |
90aabc7e FD |
132 | : _Base(__gnu_debug::__base( |
133 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
15ee1a77 FD |
134 | __gnu_debug::__base(__last), __a) { } |
135 | ||
136 | ~multimap() = default; | |
ed540c0a | 137 | #endif |
285b36d6 | 138 | |
15ee1a77 FD |
139 | explicit multimap(const _Compare& __comp, |
140 | const _Allocator& __a = _Allocator()) | |
141 | : _Base(__comp, __a) { } | |
142 | ||
143 | template<typename _InputIterator> | |
144 | multimap(_InputIterator __first, _InputIterator __last, | |
145 | const _Compare& __comp = _Compare(), | |
146 | const _Allocator& __a = _Allocator()) | |
90aabc7e FD |
147 | : _Base(__gnu_debug::__base( |
148 | __glibcxx_check_valid_constructor_range(__first, __last)), | |
15ee1a77 FD |
149 | __gnu_debug::__base(__last), |
150 | __comp, __a) { } | |
151 | ||
eca833b8 JW |
152 | multimap(_Base_ref __x) |
153 | : _Base(__x._M_ref) { } | |
285b36d6 | 154 | |
15ee1a77 | 155 | #if __cplusplus < 201103L |
ed540c0a CJ |
156 | multimap& |
157 | operator=(const multimap& __x) | |
285b36d6 | 158 | { |
15ee1a77 | 159 | this->_M_safe() = __x; |
51835a80 | 160 | _M_base() = __x; |
285b36d6 BK |
161 | return *this; |
162 | } | |
15ee1a77 FD |
163 | #else |
164 | multimap& | |
165 | operator=(const multimap&) = default; | |
285b36d6 | 166 | |
ed540c0a | 167 | multimap& |
15ee1a77 | 168 | operator=(multimap&&) = default; |
988499f4 JM |
169 | |
170 | multimap& | |
171 | operator=(initializer_list<value_type> __l) | |
172 | { | |
51835a80 FD |
173 | _M_base() = __l; |
174 | this->_M_invalidate_all(); | |
988499f4 JM |
175 | return *this; |
176 | } | |
ed540c0a CJ |
177 | #endif |
178 | ||
285b36d6 BK |
179 | using _Base::get_allocator; |
180 | ||
181 | // iterators: | |
526da49c | 182 | iterator |
d3677132 | 183 | begin() _GLIBCXX_NOEXCEPT |
285b36d6 BK |
184 | { return iterator(_Base::begin(), this); } |
185 | ||
526da49c | 186 | const_iterator |
d3677132 | 187 | begin() const _GLIBCXX_NOEXCEPT |
285b36d6 BK |
188 | { return const_iterator(_Base::begin(), this); } |
189 | ||
526da49c | 190 | iterator |
d3677132 | 191 | end() _GLIBCXX_NOEXCEPT |
285b36d6 BK |
192 | { return iterator(_Base::end(), this); } |
193 | ||
526da49c | 194 | const_iterator |
d3677132 | 195 | end() const _GLIBCXX_NOEXCEPT |
285b36d6 BK |
196 | { return const_iterator(_Base::end(), this); } |
197 | ||
526da49c | 198 | reverse_iterator |
d3677132 | 199 | rbegin() _GLIBCXX_NOEXCEPT |
285b36d6 BK |
200 | { return reverse_iterator(end()); } |
201 | ||
526da49c | 202 | const_reverse_iterator |
d3677132 | 203 | rbegin() const _GLIBCXX_NOEXCEPT |
285b36d6 BK |
204 | { return const_reverse_iterator(end()); } |
205 | ||
526da49c | 206 | reverse_iterator |
d3677132 | 207 | rend() _GLIBCXX_NOEXCEPT |
285b36d6 BK |
208 | { return reverse_iterator(begin()); } |
209 | ||
526da49c | 210 | const_reverse_iterator |
d3677132 | 211 | rend() const _GLIBCXX_NOEXCEPT |
285b36d6 BK |
212 | { return const_reverse_iterator(begin()); } |
213 | ||
734f5023 | 214 | #if __cplusplus >= 201103L |
0cd50f89 | 215 | const_iterator |
d3677132 | 216 | cbegin() const noexcept |
0cd50f89 PC |
217 | { return const_iterator(_Base::begin(), this); } |
218 | ||
219 | const_iterator | |
d3677132 | 220 | cend() const noexcept |
0cd50f89 PC |
221 | { return const_iterator(_Base::end(), this); } |
222 | ||
223 | const_reverse_iterator | |
d3677132 | 224 | crbegin() const noexcept |
0cd50f89 PC |
225 | { return const_reverse_iterator(end()); } |
226 | ||
227 | const_reverse_iterator | |
d3677132 | 228 | crend() const noexcept |
0cd50f89 PC |
229 | { return const_reverse_iterator(begin()); } |
230 | #endif | |
231 | ||
285b36d6 BK |
232 | // capacity: |
233 | using _Base::empty; | |
234 | using _Base::size; | |
235 | using _Base::max_size; | |
236 | ||
237 | // modifiers: | |
734f5023 | 238 | #if __cplusplus >= 201103L |
55826ab6 FD |
239 | template<typename... _Args> |
240 | iterator | |
241 | emplace(_Args&&... __args) | |
784779d4 | 242 | { return { _Base::emplace(std::forward<_Args>(__args)...), this }; } |
55826ab6 FD |
243 | |
244 | template<typename... _Args> | |
245 | iterator | |
246 | emplace_hint(const_iterator __pos, _Args&&... __args) | |
247 | { | |
248 | __glibcxx_check_insert(__pos); | |
784779d4 FD |
249 | return |
250 | { | |
251 | _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...), | |
252 | this | |
253 | }; | |
55826ab6 FD |
254 | } |
255 | #endif | |
15ee1a77 | 256 | |
526da49c | 257 | iterator |
285b36d6 BK |
258 | insert(const value_type& __x) |
259 | { return iterator(_Base::insert(__x), this); } | |
260 | ||
734f5023 | 261 | #if __cplusplus >= 201103L |
1679da15 FD |
262 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
263 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
264 | iterator | |
265 | insert(value_type&& __x) | |
266 | { return { _Base::insert(std::move(__x)), this }; } | |
267 | ||
e6a05448 | 268 | template<typename _Pair, typename = typename |
57cee56a PC |
269 | std::enable_if<std::is_constructible<value_type, |
270 | _Pair&&>::value>::type> | |
15ee1a77 FD |
271 | iterator |
272 | insert(_Pair&& __x) | |
784779d4 | 273 | { return { _Base::insert(std::forward<_Pair>(__x)), this }; } |
e6a05448 PC |
274 | #endif |
275 | ||
734f5023 | 276 | #if __cplusplus >= 201103L |
988499f4 JM |
277 | void |
278 | insert(std::initializer_list<value_type> __list) | |
279 | { _Base::insert(__list); } | |
280 | #endif | |
281 | ||
526da49c | 282 | iterator |
734f5023 | 283 | #if __cplusplus >= 201103L |
6b6d5d09 PC |
284 | insert(const_iterator __position, const value_type& __x) |
285 | #else | |
afe96d41 | 286 | insert(iterator __position, const value_type& __x) |
6b6d5d09 | 287 | #endif |
285b36d6 BK |
288 | { |
289 | __glibcxx_check_insert(__position); | |
290 | return iterator(_Base::insert(__position.base(), __x), this); | |
291 | } | |
292 | ||
734f5023 | 293 | #if __cplusplus >= 201103L |
1679da15 FD |
294 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
295 | // 2354. Unnecessary copying when inserting into maps with braced-init | |
296 | iterator | |
297 | insert(const_iterator __position, value_type&& __x) | |
298 | { | |
299 | __glibcxx_check_insert(__position); | |
300 | return { _Base::insert(__position.base(), std::move(__x)), this }; | |
301 | } | |
302 | ||
e6a05448 | 303 | template<typename _Pair, typename = typename |
57cee56a PC |
304 | std::enable_if<std::is_constructible<value_type, |
305 | _Pair&&>::value>::type> | |
15ee1a77 FD |
306 | iterator |
307 | insert(const_iterator __position, _Pair&& __x) | |
308 | { | |
e6a05448 | 309 | __glibcxx_check_insert(__position); |
784779d4 FD |
310 | return |
311 | { | |
312 | _Base::insert(__position.base(), std::forward<_Pair>(__x)), | |
313 | this | |
314 | }; | |
e6a05448 PC |
315 | } |
316 | #endif | |
317 | ||
285b36d6 | 318 | template<typename _InputIterator> |
15ee1a77 FD |
319 | void |
320 | insert(_InputIterator __first, _InputIterator __last) | |
321 | { | |
24167c42 FD |
322 | typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist; |
323 | __glibcxx_check_valid_range2(__first, __last, __dist); | |
324 | ||
325 | if (__dist.second >= __gnu_debug::__dp_sign) | |
326 | _Base::insert(__gnu_debug::__unsafe(__first), | |
327 | __gnu_debug::__unsafe(__last)); | |
328 | else | |
329 | _Base::insert(__first, __last); | |
285b36d6 BK |
330 | } |
331 | ||
2dbe56bd JW |
332 | #if __cplusplus > 201402L |
333 | using node_type = typename _Base::node_type; | |
334 | ||
335 | node_type | |
336 | extract(const_iterator __position) | |
337 | { | |
338 | __glibcxx_check_erase(__position); | |
339 | this->_M_invalidate_if(_Equal(__position.base())); | |
340 | return _Base::extract(__position.base()); | |
341 | } | |
342 | ||
343 | node_type | |
344 | extract(const key_type& __key) | |
345 | { | |
346 | const auto __position = find(__key); | |
347 | if (__position != end()) | |
348 | return extract(__position); | |
349 | return {}; | |
350 | } | |
351 | ||
352 | iterator | |
353 | insert(node_type&& __nh) | |
784779d4 | 354 | { return { _Base::insert(std::move(__nh)), this }; } |
2dbe56bd JW |
355 | |
356 | iterator | |
357 | insert(const_iterator __hint, node_type&& __nh) | |
358 | { | |
359 | __glibcxx_check_insert(__hint); | |
784779d4 | 360 | return { _Base::insert(__hint.base(), std::move(__nh)), this }; |
2dbe56bd JW |
361 | } |
362 | ||
363 | using _Base::merge; | |
364 | #endif // C++17 | |
365 | ||
734f5023 | 366 | #if __cplusplus >= 201103L |
5ab06c6d | 367 | iterator |
6b6d5d09 | 368 | erase(const_iterator __position) |
5ab06c6d PC |
369 | { |
370 | __glibcxx_check_erase(__position); | |
afe96d41 | 371 | this->_M_invalidate_if(_Equal(__position.base())); |
784779d4 | 372 | return { _Base::erase(__position.base()), this }; |
5ab06c6d | 373 | } |
6dc88283 | 374 | |
7b1e8acf | 375 | _GLIBCXX_ABI_TAG_CXX11 |
6dc88283 PC |
376 | iterator |
377 | erase(iterator __position) | |
378 | { return erase(const_iterator(__position)); } | |
5ab06c6d | 379 | #else |
526da49c | 380 | void |
285b36d6 BK |
381 | erase(iterator __position) |
382 | { | |
383 | __glibcxx_check_erase(__position); | |
afe96d41 | 384 | this->_M_invalidate_if(_Equal(__position.base())); |
285b36d6 BK |
385 | _Base::erase(__position.base()); |
386 | } | |
5ab06c6d | 387 | #endif |
285b36d6 | 388 | |
526da49c | 389 | size_type |
285b36d6 BK |
390 | erase(const key_type& __x) |
391 | { | |
afe96d41 FD |
392 | std::pair<_Base_iterator, _Base_iterator> __victims = |
393 | _Base::equal_range(__x); | |
285b36d6 | 394 | size_type __count = 0; |
afe96d41 FD |
395 | _Base_iterator __victim = __victims.first; |
396 | while (__victim != __victims.second) | |
397 | { | |
398 | this->_M_invalidate_if(_Equal(__victim)); | |
399 | _Base::erase(__victim++); | |
400 | ++__count; | |
401 | } | |
285b36d6 BK |
402 | return __count; |
403 | } | |
404 | ||
734f5023 | 405 | #if __cplusplus >= 201103L |
5ab06c6d | 406 | iterator |
6b6d5d09 | 407 | erase(const_iterator __first, const_iterator __last) |
5ab06c6d PC |
408 | { |
409 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
410 | // 151. can't currently clear() empty container | |
411 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
412 | for (_Base_const_iterator __victim = __first.base(); |
413 | __victim != __last.base(); ++__victim) | |
414 | { | |
e0b9bc23 | 415 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(), |
afe96d41 FD |
416 | _M_message(__gnu_debug::__msg_valid_range) |
417 | ._M_iterator(__first, "first") | |
418 | ._M_iterator(__last, "last")); | |
419 | this->_M_invalidate_if(_Equal(__victim)); | |
420 | } | |
784779d4 FD |
421 | |
422 | return { _Base::erase(__first.base(), __last.base()), this }; | |
5ab06c6d PC |
423 | } |
424 | #else | |
526da49c | 425 | void |
285b36d6 BK |
426 | erase(iterator __first, iterator __last) |
427 | { | |
428 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
429 | // 151. can't currently clear() empty container | |
430 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
431 | for (_Base_iterator __victim = __first.base(); |
432 | __victim != __last.base(); ++__victim) | |
433 | { | |
434 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), | |
435 | _M_message(__gnu_debug::__msg_valid_range) | |
436 | ._M_iterator(__first, "first") | |
437 | ._M_iterator(__last, "last")); | |
438 | this->_M_invalidate_if(_Equal(__victim)); | |
439 | } | |
440 | _Base::erase(__first.base(), __last.base()); | |
285b36d6 | 441 | } |
5ab06c6d | 442 | #endif |
285b36d6 | 443 | |
526da49c | 444 | void |
ed540c0a | 445 | swap(multimap& __x) |
c5d9ec56 | 446 | _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) ) |
285b36d6 | 447 | { |
15ee1a77 | 448 | _Safe::_M_swap(__x); |
285b36d6 | 449 | _Base::swap(__x); |
285b36d6 BK |
450 | } |
451 | ||
526da49c | 452 | void |
d3677132 | 453 | clear() _GLIBCXX_NOEXCEPT |
afe96d41 FD |
454 | { |
455 | this->_M_invalidate_all(); | |
456 | _Base::clear(); | |
457 | } | |
285b36d6 BK |
458 | |
459 | // observers: | |
460 | using _Base::key_comp; | |
461 | using _Base::value_comp; | |
462 | ||
463 | // 23.3.1.3 multimap operations: | |
526da49c | 464 | iterator |
285b36d6 BK |
465 | find(const key_type& __x) |
466 | { return iterator(_Base::find(__x), this); } | |
467 | ||
d7b35f22 FD |
468 | #if __cplusplus > 201103L |
469 | template<typename _Kt, | |
470 | typename _Req = | |
471 | typename __has_is_transparent<_Compare, _Kt>::type> | |
472 | iterator | |
473 | find(const _Kt& __x) | |
474 | { return { _Base::find(__x), this }; } | |
475 | #endif | |
476 | ||
526da49c | 477 | const_iterator |
285b36d6 BK |
478 | find(const key_type& __x) const |
479 | { return const_iterator(_Base::find(__x), this); } | |
480 | ||
d7b35f22 FD |
481 | #if __cplusplus > 201103L |
482 | template<typename _Kt, | |
483 | typename _Req = | |
484 | typename __has_is_transparent<_Compare, _Kt>::type> | |
485 | const_iterator | |
486 | find(const _Kt& __x) const | |
487 | { return { _Base::find(__x), this }; } | |
488 | #endif | |
489 | ||
285b36d6 BK |
490 | using _Base::count; |
491 | ||
526da49c | 492 | iterator |
285b36d6 BK |
493 | lower_bound(const key_type& __x) |
494 | { return iterator(_Base::lower_bound(__x), this); } | |
495 | ||
d7b35f22 FD |
496 | #if __cplusplus > 201103L |
497 | template<typename _Kt, | |
498 | typename _Req = | |
499 | typename __has_is_transparent<_Compare, _Kt>::type> | |
500 | iterator | |
501 | lower_bound(const _Kt& __x) | |
502 | { return { _Base::lower_bound(__x), this }; } | |
503 | #endif | |
504 | ||
526da49c | 505 | const_iterator |
285b36d6 BK |
506 | lower_bound(const key_type& __x) const |
507 | { return const_iterator(_Base::lower_bound(__x), this); } | |
508 | ||
d7b35f22 FD |
509 | #if __cplusplus > 201103L |
510 | template<typename _Kt, | |
511 | typename _Req = | |
512 | typename __has_is_transparent<_Compare, _Kt>::type> | |
513 | const_iterator | |
514 | lower_bound(const _Kt& __x) const | |
515 | { return { _Base::lower_bound(__x), this }; } | |
516 | #endif | |
517 | ||
526da49c | 518 | iterator |
285b36d6 BK |
519 | upper_bound(const key_type& __x) |
520 | { return iterator(_Base::upper_bound(__x), this); } | |
521 | ||
d7b35f22 FD |
522 | #if __cplusplus > 201103L |
523 | template<typename _Kt, | |
524 | typename _Req = | |
525 | typename __has_is_transparent<_Compare, _Kt>::type> | |
526 | iterator | |
527 | upper_bound(const _Kt& __x) | |
528 | { return { _Base::upper_bound(__x), this }; } | |
529 | #endif | |
530 | ||
526da49c | 531 | const_iterator |
285b36d6 BK |
532 | upper_bound(const key_type& __x) const |
533 | { return const_iterator(_Base::upper_bound(__x), this); } | |
534 | ||
d7b35f22 FD |
535 | #if __cplusplus > 201103L |
536 | template<typename _Kt, | |
537 | typename _Req = | |
538 | typename __has_is_transparent<_Compare, _Kt>::type> | |
539 | const_iterator | |
540 | upper_bound(const _Kt& __x) const | |
541 | { return { _Base::upper_bound(__x), this }; } | |
542 | #endif | |
543 | ||
285b36d6 BK |
544 | std::pair<iterator,iterator> |
545 | equal_range(const key_type& __x) | |
546 | { | |
285b36d6 BK |
547 | std::pair<_Base_iterator, _Base_iterator> __res = |
548 | _Base::equal_range(__x); | |
549 | return std::make_pair(iterator(__res.first, this), | |
550 | iterator(__res.second, this)); | |
551 | } | |
552 | ||
d7b35f22 FD |
553 | #if __cplusplus > 201103L |
554 | template<typename _Kt, | |
555 | typename _Req = | |
556 | typename __has_is_transparent<_Compare, _Kt>::type> | |
557 | std::pair<iterator, iterator> | |
558 | equal_range(const _Kt& __x) | |
559 | { | |
560 | auto __res = _Base::equal_range(__x); | |
561 | return { { __res.first, this }, { __res.second, this } }; | |
562 | } | |
563 | #endif | |
564 | ||
285b36d6 BK |
565 | std::pair<const_iterator,const_iterator> |
566 | equal_range(const key_type& __x) const | |
567 | { | |
285b36d6 | 568 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
afe96d41 | 569 | _Base::equal_range(__x); |
285b36d6 BK |
570 | return std::make_pair(const_iterator(__res.first, this), |
571 | const_iterator(__res.second, this)); | |
572 | } | |
573 | ||
d7b35f22 FD |
574 | #if __cplusplus > 201103L |
575 | template<typename _Kt, | |
576 | typename _Req = | |
577 | typename __has_is_transparent<_Compare, _Kt>::type> | |
578 | std::pair<const_iterator, const_iterator> | |
579 | equal_range(const _Kt& __x) const | |
580 | { | |
581 | auto __res = _Base::equal_range(__x); | |
582 | return { { __res.first, this }, { __res.second, this } }; | |
583 | } | |
584 | #endif | |
585 | ||
526da49c | 586 | _Base& |
15ee1a77 | 587 | _M_base() _GLIBCXX_NOEXCEPT { return *this; } |
285b36d6 | 588 | |
526da49c | 589 | const _Base& |
d3677132 | 590 | _M_base() const _GLIBCXX_NOEXCEPT { return *this; } |
285b36d6 BK |
591 | }; |
592 | ||
957f5fea VV |
593 | #if __cpp_deduction_guides >= 201606 |
594 | ||
595 | template<typename _InputIterator, | |
596 | typename _Compare = less<__iter_key_t<_InputIterator>>, | |
597 | typename _Allocator = allocator<__iter_to_alloc_t<_InputIterator>>, | |
598 | typename = _RequireInputIter<_InputIterator>, | |
c0cb38c2 | 599 | typename = _RequireNotAllocator<_Compare>, |
957f5fea VV |
600 | typename = _RequireAllocator<_Allocator>> |
601 | multimap(_InputIterator, _InputIterator, | |
602 | _Compare = _Compare(), _Allocator = _Allocator()) | |
603 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, | |
604 | _Compare, _Allocator>; | |
605 | ||
606 | template<typename _Key, typename _Tp, typename _Compare = less<_Key>, | |
607 | typename _Allocator = allocator<pair<const _Key, _Tp>>, | |
c0cb38c2 | 608 | typename = _RequireNotAllocator<_Compare>, |
957f5fea VV |
609 | typename = _RequireAllocator<_Allocator>> |
610 | multimap(initializer_list<pair<_Key, _Tp>>, | |
611 | _Compare = _Compare(), _Allocator = _Allocator()) | |
612 | -> multimap<_Key, _Tp, _Compare, _Allocator>; | |
613 | ||
614 | template<typename _InputIterator, typename _Allocator, | |
615 | typename = _RequireInputIter<_InputIterator>, | |
616 | typename = _RequireAllocator<_Allocator>> | |
617 | multimap(_InputIterator, _InputIterator, _Allocator) | |
618 | -> multimap<__iter_key_t<_InputIterator>, __iter_val_t<_InputIterator>, | |
619 | less<__iter_key_t<_InputIterator>>, _Allocator>; | |
620 | ||
621 | template<typename _Key, typename _Tp, typename _Allocator, | |
622 | typename = _RequireAllocator<_Allocator>> | |
623 | multimap(initializer_list<pair<_Key, _Tp>>, _Allocator) | |
624 | -> multimap<_Key, _Tp, less<_Key>, _Allocator>; | |
625 | ||
626 | #endif | |
627 | ||
ed540c0a CJ |
628 | template<typename _Key, typename _Tp, |
629 | typename _Compare, typename _Allocator> | |
285b36d6 | 630 | inline bool |
ed540c0a CJ |
631 | operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
632 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
633 | { return __lhs._M_base() == __rhs._M_base(); } |
634 | ||
93843da6 JW |
635 | #if __cpp_lib_three_way_comparison |
636 | template<typename _Key, typename _Tp, typename _Compare, typename _Alloc> | |
637 | inline __detail::__synth3way_t<pair<const _Key, _Tp>> | |
638 | operator<=>(const multimap<_Key, _Tp, _Compare, _Alloc>& __lhs, | |
639 | const multimap<_Key, _Tp, _Compare, _Alloc>& __rhs) | |
640 | { return __lhs._M_base() <=> __rhs._M_base(); } | |
641 | #else | |
ed540c0a CJ |
642 | template<typename _Key, typename _Tp, |
643 | typename _Compare, typename _Allocator> | |
285b36d6 | 644 | inline bool |
ed540c0a CJ |
645 | operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
646 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
647 | { return __lhs._M_base() != __rhs._M_base(); } |
648 | ||
ed540c0a CJ |
649 | template<typename _Key, typename _Tp, |
650 | typename _Compare, typename _Allocator> | |
285b36d6 | 651 | inline bool |
ed540c0a CJ |
652 | operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
653 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
654 | { return __lhs._M_base() < __rhs._M_base(); } |
655 | ||
ed540c0a CJ |
656 | template<typename _Key, typename _Tp, |
657 | typename _Compare, typename _Allocator> | |
285b36d6 | 658 | inline bool |
ed540c0a CJ |
659 | operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
660 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
661 | { return __lhs._M_base() <= __rhs._M_base(); } |
662 | ||
ed540c0a CJ |
663 | template<typename _Key, typename _Tp, |
664 | typename _Compare, typename _Allocator> | |
285b36d6 | 665 | inline bool |
ed540c0a CJ |
666 | operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
667 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
668 | { return __lhs._M_base() >= __rhs._M_base(); } |
669 | ||
ed540c0a CJ |
670 | template<typename _Key, typename _Tp, |
671 | typename _Compare, typename _Allocator> | |
285b36d6 | 672 | inline bool |
ed540c0a CJ |
673 | operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
674 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 | 675 | { return __lhs._M_base() > __rhs._M_base(); } |
93843da6 | 676 | #endif // three-way comparison |
285b36d6 | 677 | |
ed540c0a CJ |
678 | template<typename _Key, typename _Tp, |
679 | typename _Compare, typename _Allocator> | |
285b36d6 | 680 | inline void |
ed540c0a CJ |
681 | swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
682 | multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
c5d9ec56 | 683 | _GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs))) |
285b36d6 | 684 | { __lhs.swap(__rhs); } |
ed540c0a | 685 | |
45f388bb | 686 | } // namespace __debug |
3cbc7af0 | 687 | } // namespace std |
285b36d6 | 688 | |
526da49c | 689 | #endif |