| 6554 |
serge |
1 |
// Debugging multiset implementation -*- C++ -*- |
|
|
2 |
|
|
|
3 |
// Copyright (C) 2003-2015 Free Software Foundation, Inc. |
|
|
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 |
|
|
8 |
// Free Software Foundation; either version 3, or (at your option) |
|
|
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 |
|
|
|
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 |
// . |
|
|
24 |
|
|
|
25 |
/** @file debug/multiset.h |
|
|
26 |
* This file is a GNU debug extension to the Standard C++ Library. |
|
|
27 |
*/ |
|
|
28 |
|
|
|
29 |
#ifndef _GLIBCXX_DEBUG_MULTISET_H |
|
|
30 |
#define _GLIBCXX_DEBUG_MULTISET_H 1 |
|
|
31 |
|
|
|
32 |
#include |
|
|
33 |
#include |
|
|
34 |
#include |
|
|
35 |
#include |
|
|
36 |
|
|
|
37 |
namespace std _GLIBCXX_VISIBILITY(default) |
|
|
38 |
{ |
|
|
39 |
namespace __debug |
|
|
40 |
{ |
|
|
41 |
/// Class std::multiset with safety/checking/debug instrumentation. |
|
|
42 |
template, |
|
|
43 |
typename _Allocator = std::allocator<_Key> > |
|
|
44 |
class multiset |
|
|
45 |
: public __gnu_debug::_Safe_container< |
|
|
46 |
multiset<_Key, _Compare, _Allocator>, _Allocator, |
|
|
47 |
__gnu_debug::_Safe_node_sequence>, |
|
|
48 |
public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> |
|
|
49 |
{ |
|
|
50 |
typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base; |
|
|
51 |
typedef __gnu_debug::_Safe_container< |
|
|
52 |
multiset, _Allocator, __gnu_debug::_Safe_node_sequence> _Safe; |
|
|
53 |
|
|
|
54 |
typedef typename _Base::const_iterator _Base_const_iterator; |
|
|
55 |
typedef typename _Base::iterator _Base_iterator; |
|
|
56 |
typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; |
|
|
57 |
|
|
|
58 |
public: |
|
|
59 |
// types: |
|
|
60 |
typedef _Key key_type; |
|
|
61 |
typedef _Key value_type; |
|
|
62 |
typedef _Compare key_compare; |
|
|
63 |
typedef _Compare value_compare; |
|
|
64 |
typedef _Allocator allocator_type; |
|
|
65 |
typedef typename _Base::reference reference; |
|
|
66 |
typedef typename _Base::const_reference const_reference; |
|
|
67 |
|
|
|
68 |
typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset> |
|
|
69 |
iterator; |
|
|
70 |
typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
|
|
71 |
multiset> const_iterator; |
|
|
72 |
|
|
|
73 |
typedef typename _Base::size_type size_type; |
|
|
74 |
typedef typename _Base::difference_type difference_type; |
|
|
75 |
typedef typename _Base::pointer pointer; |
|
|
76 |
typedef typename _Base::const_pointer const_pointer; |
|
|
77 |
typedef std::reverse_iterator reverse_iterator; |
|
|
78 |
typedef std::reverse_iterator const_reverse_iterator; |
|
|
79 |
|
|
|
80 |
// 23.3.3.1 construct/copy/destroy: |
|
|
81 |
|
|
|
82 |
#if __cplusplus < 201103L |
|
|
83 |
multiset() : _Base() { } |
|
|
84 |
|
|
|
85 |
multiset(const multiset& __x) |
|
|
86 |
: _Base(__x) { } |
|
|
87 |
|
|
|
88 |
~multiset() { } |
|
|
89 |
#else |
|
|
90 |
multiset() = default; |
|
|
91 |
multiset(const multiset&) = default; |
|
|
92 |
multiset(multiset&&) = default; |
|
|
93 |
|
|
|
94 |
multiset(initializer_list __l, |
|
|
95 |
const _Compare& __comp = _Compare(), |
|
|
96 |
const allocator_type& __a = allocator_type()) |
|
|
97 |
: _Base(__l, __comp, __a) { } |
|
|
98 |
|
|
|
99 |
explicit |
|
|
100 |
multiset(const allocator_type& __a) |
|
|
101 |
: _Base(__a) { } |
|
|
102 |
|
|
|
103 |
multiset(const multiset& __m, const allocator_type& __a) |
|
|
104 |
: _Base(__m, __a) { } |
|
|
105 |
|
|
|
106 |
multiset(multiset&& __m, const allocator_type& __a) |
|
|
107 |
: _Safe(std::move(__m._M_safe()), __a), |
|
|
108 |
_Base(std::move(__m._M_base()), __a) { } |
|
|
109 |
|
|
|
110 |
multiset(initializer_list __l, const allocator_type& __a) |
|
|
111 |
: _Base(__l, __a) |
|
|
112 |
{ } |
|
|
113 |
|
|
|
114 |
template |
|
|
115 |
multiset(_InputIterator __first, _InputIterator __last, |
|
|
116 |
const allocator_type& __a) |
|
|
117 |
: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
|
|
118 |
__last)), |
|
|
119 |
__gnu_debug::__base(__last), __a) { } |
|
|
120 |
|
|
|
121 |
~multiset() = default; |
|
|
122 |
#endif |
|
|
123 |
|
|
|
124 |
explicit multiset(const _Compare& __comp, |
|
|
125 |
const _Allocator& __a = _Allocator()) |
|
|
126 |
: _Base(__comp, __a) { } |
|
|
127 |
|
|
|
128 |
template |
|
|
129 |
multiset(_InputIterator __first, _InputIterator __last, |
|
|
130 |
const _Compare& __comp = _Compare(), |
|
|
131 |
const _Allocator& __a = _Allocator()) |
|
|
132 |
: _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
|
|
133 |
__last)), |
|
|
134 |
__gnu_debug::__base(__last), |
|
|
135 |
__comp, __a) { } |
|
|
136 |
|
|
|
137 |
multiset(const _Base& __x) |
|
|
138 |
: _Base(__x) { } |
|
|
139 |
|
|
|
140 |
#if __cplusplus < 201103L |
|
|
141 |
multiset& |
|
|
142 |
operator=(const multiset& __x) |
|
|
143 |
{ |
|
|
144 |
this->_M_safe() = __x; |
|
|
145 |
_M_base() = __x; |
|
|
146 |
return *this; |
|
|
147 |
} |
|
|
148 |
#else |
|
|
149 |
multiset& |
|
|
150 |
operator=(const multiset&) = default; |
|
|
151 |
|
|
|
152 |
multiset& |
|
|
153 |
operator=(multiset&&) = default; |
|
|
154 |
|
|
|
155 |
multiset& |
|
|
156 |
operator=(initializer_list __l) |
|
|
157 |
{ |
|
|
158 |
_M_base() = __l; |
|
|
159 |
this->_M_invalidate_all(); |
|
|
160 |
return *this; |
|
|
161 |
} |
|
|
162 |
#endif |
|
|
163 |
|
|
|
164 |
using _Base::get_allocator; |
|
|
165 |
|
|
|
166 |
// iterators: |
|
|
167 |
iterator |
|
|
168 |
begin() _GLIBCXX_NOEXCEPT |
|
|
169 |
{ return iterator(_Base::begin(), this); } |
|
|
170 |
|
|
|
171 |
const_iterator |
|
|
172 |
begin() const _GLIBCXX_NOEXCEPT |
|
|
173 |
{ return const_iterator(_Base::begin(), this); } |
|
|
174 |
|
|
|
175 |
iterator |
|
|
176 |
end() _GLIBCXX_NOEXCEPT |
|
|
177 |
{ return iterator(_Base::end(), this); } |
|
|
178 |
|
|
|
179 |
const_iterator |
|
|
180 |
end() const _GLIBCXX_NOEXCEPT |
|
|
181 |
{ return const_iterator(_Base::end(), this); } |
|
|
182 |
|
|
|
183 |
reverse_iterator |
|
|
184 |
rbegin() _GLIBCXX_NOEXCEPT |
|
|
185 |
{ return reverse_iterator(end()); } |
|
|
186 |
|
|
|
187 |
const_reverse_iterator |
|
|
188 |
rbegin() const _GLIBCXX_NOEXCEPT |
|
|
189 |
{ return const_reverse_iterator(end()); } |
|
|
190 |
|
|
|
191 |
reverse_iterator |
|
|
192 |
rend() _GLIBCXX_NOEXCEPT |
|
|
193 |
{ return reverse_iterator(begin()); } |
|
|
194 |
|
|
|
195 |
const_reverse_iterator |
|
|
196 |
rend() const _GLIBCXX_NOEXCEPT |
|
|
197 |
{ return const_reverse_iterator(begin()); } |
|
|
198 |
|
|
|
199 |
#if __cplusplus >= 201103L |
|
|
200 |
const_iterator |
|
|
201 |
cbegin() const noexcept |
|
|
202 |
{ return const_iterator(_Base::begin(), this); } |
|
|
203 |
|
|
|
204 |
const_iterator |
|
|
205 |
cend() const noexcept |
|
|
206 |
{ return const_iterator(_Base::end(), this); } |
|
|
207 |
|
|
|
208 |
const_reverse_iterator |
|
|
209 |
crbegin() const noexcept |
|
|
210 |
{ return const_reverse_iterator(end()); } |
|
|
211 |
|
|
|
212 |
const_reverse_iterator |
|
|
213 |
crend() const noexcept |
|
|
214 |
{ return const_reverse_iterator(begin()); } |
|
|
215 |
#endif |
|
|
216 |
|
|
|
217 |
// capacity: |
|
|
218 |
using _Base::empty; |
|
|
219 |
using _Base::size; |
|
|
220 |
using _Base::max_size; |
|
|
221 |
|
|
|
222 |
// modifiers: |
|
|
223 |
#if __cplusplus >= 201103L |
|
|
224 |
template |
|
|
225 |
iterator |
|
|
226 |
emplace(_Args&&... __args) |
|
|
227 |
{ |
|
|
228 |
return iterator(_Base::emplace(std::forward<_Args>(__args)...), |
|
|
229 |
this); |
|
|
230 |
} |
|
|
231 |
|
|
|
232 |
template |
|
|
233 |
iterator |
|
|
234 |
emplace_hint(const_iterator __pos, _Args&&... __args) |
|
|
235 |
{ |
|
|
236 |
__glibcxx_check_insert(__pos); |
|
|
237 |
return iterator(_Base::emplace_hint(__pos.base(), |
|
|
238 |
std::forward<_Args>(__args)...), |
|
|
239 |
this); |
|
|
240 |
} |
|
|
241 |
#endif |
|
|
242 |
|
|
|
243 |
iterator |
|
|
244 |
insert(const value_type& __x) |
|
|
245 |
{ return iterator(_Base::insert(__x), this); } |
|
|
246 |
|
|
|
247 |
#if __cplusplus >= 201103L |
|
|
248 |
iterator |
|
|
249 |
insert(value_type&& __x) |
|
|
250 |
{ return iterator(_Base::insert(std::move(__x)), this); } |
|
|
251 |
#endif |
|
|
252 |
|
|
|
253 |
iterator |
|
|
254 |
insert(const_iterator __position, const value_type& __x) |
|
|
255 |
{ |
|
|
256 |
__glibcxx_check_insert(__position); |
|
|
257 |
return iterator(_Base::insert(__position.base(), __x), this); |
|
|
258 |
} |
|
|
259 |
|
|
|
260 |
#if __cplusplus >= 201103L |
|
|
261 |
iterator |
|
|
262 |
insert(const_iterator __position, value_type&& __x) |
|
|
263 |
{ |
|
|
264 |
__glibcxx_check_insert(__position); |
|
|
265 |
return iterator(_Base::insert(__position.base(), std::move(__x)), |
|
|
266 |
this); |
|
|
267 |
} |
|
|
268 |
#endif |
|
|
269 |
|
|
|
270 |
template |
|
|
271 |
void |
|
|
272 |
insert(_InputIterator __first, _InputIterator __last) |
|
|
273 |
{ |
|
|
274 |
__glibcxx_check_valid_range(__first, __last); |
|
|
275 |
_Base::insert(__gnu_debug::__base(__first), |
|
|
276 |
__gnu_debug::__base(__last)); |
|
|
277 |
} |
|
|
278 |
|
|
|
279 |
#if __cplusplus >= 201103L |
|
|
280 |
void |
|
|
281 |
insert(initializer_list __l) |
|
|
282 |
{ _Base::insert(__l); } |
|
|
283 |
#endif |
|
|
284 |
|
|
|
285 |
#if __cplusplus >= 201103L |
|
|
286 |
iterator |
|
|
287 |
erase(const_iterator __position) |
|
|
288 |
{ |
|
|
289 |
__glibcxx_check_erase(__position); |
|
|
290 |
this->_M_invalidate_if(_Equal(__position.base())); |
|
|
291 |
return iterator(_Base::erase(__position.base()), this); |
|
|
292 |
} |
|
|
293 |
#else |
|
|
294 |
void |
|
|
295 |
erase(iterator __position) |
|
|
296 |
{ |
|
|
297 |
__glibcxx_check_erase(__position); |
|
|
298 |
this->_M_invalidate_if(_Equal(__position.base())); |
|
|
299 |
_Base::erase(__position.base()); |
|
|
300 |
} |
|
|
301 |
#endif |
|
|
302 |
|
|
|
303 |
size_type |
|
|
304 |
erase(const key_type& __x) |
|
|
305 |
{ |
|
|
306 |
std::pair<_Base_iterator, _Base_iterator> __victims = |
|
|
307 |
_Base::equal_range(__x); |
|
|
308 |
size_type __count = 0; |
|
|
309 |
_Base_iterator __victim = __victims.first; |
|
|
310 |
while (__victim != __victims.second) |
|
|
311 |
{ |
|
|
312 |
this->_M_invalidate_if(_Equal(__victim)); |
|
|
313 |
_Base::erase(__victim++); |
|
|
314 |
++__count; |
|
|
315 |
} |
|
|
316 |
return __count; |
|
|
317 |
} |
|
|
318 |
|
|
|
319 |
#if __cplusplus >= 201103L |
|
|
320 |
iterator |
|
|
321 |
erase(const_iterator __first, const_iterator __last) |
|
|
322 |
{ |
|
|
323 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
324 |
// 151. can't currently clear() empty container |
|
|
325 |
__glibcxx_check_erase_range(__first, __last); |
|
|
326 |
for (_Base_const_iterator __victim = __first.base(); |
|
|
327 |
__victim != __last.base(); ++__victim) |
|
|
328 |
{ |
|
|
329 |
_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), |
|
|
330 |
_M_message(__gnu_debug::__msg_valid_range) |
|
|
331 |
._M_iterator(__first, "first") |
|
|
332 |
._M_iterator(__last, "last")); |
|
|
333 |
this->_M_invalidate_if(_Equal(__victim)); |
|
|
334 |
} |
|
|
335 |
return iterator(_Base::erase(__first.base(), __last.base()), this); |
|
|
336 |
} |
|
|
337 |
#else |
|
|
338 |
void |
|
|
339 |
erase(iterator __first, iterator __last) |
|
|
340 |
{ |
|
|
341 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
342 |
// 151. can't currently clear() empty container |
|
|
343 |
__glibcxx_check_erase_range(__first, __last); |
|
|
344 |
for (_Base_iterator __victim = __first.base(); |
|
|
345 |
__victim != __last.base(); ++__victim) |
|
|
346 |
{ |
|
|
347 |
_GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), |
|
|
348 |
_M_message(__gnu_debug::__msg_valid_range) |
|
|
349 |
._M_iterator(__first, "first") |
|
|
350 |
._M_iterator(__last, "last")); |
|
|
351 |
this->_M_invalidate_if(_Equal(__victim)); |
|
|
352 |
} |
|
|
353 |
_Base::erase(__first.base(), __last.base()); |
|
|
354 |
} |
|
|
355 |
#endif |
|
|
356 |
|
|
|
357 |
void |
|
|
358 |
swap(multiset& __x) |
|
|
359 |
#if __cplusplus >= 201103L |
|
|
360 |
noexcept( noexcept(declval<_Base>().swap(__x)) ) |
|
|
361 |
#endif |
|
|
362 |
{ |
|
|
363 |
_Safe::_M_swap(__x); |
|
|
364 |
_Base::swap(__x); |
|
|
365 |
} |
|
|
366 |
|
|
|
367 |
void |
|
|
368 |
clear() _GLIBCXX_NOEXCEPT |
|
|
369 |
{ |
|
|
370 |
this->_M_invalidate_all(); |
|
|
371 |
_Base::clear(); |
|
|
372 |
} |
|
|
373 |
|
|
|
374 |
// observers: |
|
|
375 |
using _Base::key_comp; |
|
|
376 |
using _Base::value_comp; |
|
|
377 |
|
|
|
378 |
// multiset operations: |
|
|
379 |
iterator |
|
|
380 |
find(const key_type& __x) |
|
|
381 |
{ return iterator(_Base::find(__x), this); } |
|
|
382 |
|
|
|
383 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
384 |
// 214. set::find() missing const overload |
|
|
385 |
const_iterator |
|
|
386 |
find(const key_type& __x) const |
|
|
387 |
{ return const_iterator(_Base::find(__x), this); } |
|
|
388 |
|
|
|
389 |
using _Base::count; |
|
|
390 |
|
|
|
391 |
iterator |
|
|
392 |
lower_bound(const key_type& __x) |
|
|
393 |
{ return iterator(_Base::lower_bound(__x), this); } |
|
|
394 |
|
|
|
395 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
396 |
// 214. set::find() missing const overload |
|
|
397 |
const_iterator |
|
|
398 |
lower_bound(const key_type& __x) const |
|
|
399 |
{ return const_iterator(_Base::lower_bound(__x), this); } |
|
|
400 |
|
|
|
401 |
iterator |
|
|
402 |
upper_bound(const key_type& __x) |
|
|
403 |
{ return iterator(_Base::upper_bound(__x), this); } |
|
|
404 |
|
|
|
405 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
406 |
// 214. set::find() missing const overload |
|
|
407 |
const_iterator |
|
|
408 |
upper_bound(const key_type& __x) const |
|
|
409 |
{ return const_iterator(_Base::upper_bound(__x), this); } |
|
|
410 |
|
|
|
411 |
std::pair |
|
|
412 |
equal_range(const key_type& __x) |
|
|
413 |
{ |
|
|
414 |
std::pair<_Base_iterator, _Base_iterator> __res = |
|
|
415 |
_Base::equal_range(__x); |
|
|
416 |
return std::make_pair(iterator(__res.first, this), |
|
|
417 |
iterator(__res.second, this)); |
|
|
418 |
} |
|
|
419 |
|
|
|
420 |
// _GLIBCXX_RESOLVE_LIB_DEFECTS |
|
|
421 |
// 214. set::find() missing const overload |
|
|
422 |
std::pair |
|
|
423 |
equal_range(const key_type& __x) const |
|
|
424 |
{ |
|
|
425 |
std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
|
|
426 |
_Base::equal_range(__x); |
|
|
427 |
return std::make_pair(const_iterator(__res.first, this), |
|
|
428 |
const_iterator(__res.second, this)); |
|
|
429 |
} |
|
|
430 |
|
|
|
431 |
_Base& |
|
|
432 |
_M_base() _GLIBCXX_NOEXCEPT { return *this; } |
|
|
433 |
|
|
|
434 |
const _Base& |
|
|
435 |
_M_base() const _GLIBCXX_NOEXCEPT { return *this; } |
|
|
436 |
}; |
|
|
437 |
|
|
|
438 |
template |
|
|
439 |
inline bool |
|
|
440 |
operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
441 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
442 |
{ return __lhs._M_base() == __rhs._M_base(); } |
|
|
443 |
|
|
|
444 |
template |
|
|
445 |
inline bool |
|
|
446 |
operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
447 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
448 |
{ return __lhs._M_base() != __rhs._M_base(); } |
|
|
449 |
|
|
|
450 |
template |
|
|
451 |
inline bool |
|
|
452 |
operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
453 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
454 |
{ return __lhs._M_base() < __rhs._M_base(); } |
|
|
455 |
|
|
|
456 |
template |
|
|
457 |
inline bool |
|
|
458 |
operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
459 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
460 |
{ return __lhs._M_base() <= __rhs._M_base(); } |
|
|
461 |
|
|
|
462 |
template |
|
|
463 |
inline bool |
|
|
464 |
operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
465 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
466 |
{ return __lhs._M_base() >= __rhs._M_base(); } |
|
|
467 |
|
|
|
468 |
template |
|
|
469 |
inline bool |
|
|
470 |
operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, |
|
|
471 |
const multiset<_Key, _Compare, _Allocator>& __rhs) |
|
|
472 |
{ return __lhs._M_base() > __rhs._M_base(); } |
|
|
473 |
|
|
|
474 |
template |
|
|
475 |
void |
|
|
476 |
swap(multiset<_Key, _Compare, _Allocator>& __x, |
|
|
477 |
multiset<_Key, _Compare, _Allocator>& __y) |
|
|
478 |
{ return __x.swap(__y); } |
|
|
479 |
|
|
|
480 |
} // namespace __debug |
|
|
481 |
} // namespace std |
|
|
482 |
|
|
|
483 |
#endif |