]>
Commit | Line | Data |
---|---|---|
285b36d6 BK |
1 | // Debugging multimap implementation -*- C++ -*- |
2 | ||
5ab06c6d | 3 | // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010 |
285b36d6 BK |
4 | // Free Software Foundation, Inc. |
5 | // | |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
748086b7 | 9 | // Free Software Foundation; either version 3, or (at your option) |
285b36d6 BK |
10 | // any later version. |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
748086b7 JJ |
17 | // Under Section 7 of GPL version 3, you are granted additional |
18 | // permissions described in the GCC Runtime Library Exception, version | |
19 | // 3.1, as published by the Free Software Foundation. | |
20 | ||
21 | // You should have received a copy of the GNU General Public License and | |
22 | // a copy of the GCC Runtime Library Exception along with this program; | |
23 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
24 | // <http://www.gnu.org/licenses/>. | |
285b36d6 | 25 | |
78a53887 BK |
26 | /** @file debug/multimap.h |
27 | * This file is a GNU debug extension to the Standard C++ Library. | |
28 | */ | |
29 | ||
285b36d6 BK |
30 | #ifndef _GLIBCXX_DEBUG_MULTIMAP_H |
31 | #define _GLIBCXX_DEBUG_MULTIMAP_H 1 | |
32 | ||
33 | #include <debug/safe_sequence.h> | |
34 | #include <debug/safe_iterator.h> | |
35 | #include <utility> | |
36 | ||
3cbc7af0 BK |
37 | namespace std |
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 |
c2ba9709 | 45 | : public _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator>, |
ed540c0a CJ |
46 | public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp, |
47 | _Compare, _Allocator> > | |
285b36d6 | 48 | { |
c2ba9709 | 49 | typedef _GLIBCXX_STD_D::multimap<_Key, _Tp, _Compare, _Allocator> _Base; |
285b36d6 | 50 | typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base; |
526da49c | 51 | |
afe96d41 FD |
52 | typedef typename _Base::const_iterator _Base_const_iterator; |
53 | typedef typename _Base::iterator _Base_iterator; | |
54 | typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; | |
285b36d6 BK |
55 | public: |
56 | // types: | |
526da49c BI |
57 | typedef _Key key_type; |
58 | typedef _Tp mapped_type; | |
285b36d6 BK |
59 | typedef std::pair<const _Key, _Tp> value_type; |
60 | typedef _Compare key_compare; | |
61 | typedef _Allocator allocator_type; | |
09952acc PC |
62 | typedef typename _Base::reference reference; |
63 | typedef typename _Base::const_reference const_reference; | |
526da49c | 64 | |
afe96d41 | 65 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> |
285b36d6 | 66 | iterator; |
afe96d41 | 67 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
285b36d6 BK |
68 | multimap> const_iterator; |
69 | ||
70 | typedef typename _Base::size_type size_type; | |
71 | typedef typename _Base::difference_type difference_type; | |
09952acc PC |
72 | typedef typename _Base::pointer pointer; |
73 | typedef typename _Base::const_pointer const_pointer; | |
285b36d6 BK |
74 | typedef std::reverse_iterator<iterator> reverse_iterator; |
75 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
526da49c | 76 | |
285b36d6 | 77 | using _Base::value_compare; |
526da49c | 78 | |
285b36d6 BK |
79 | // 23.3.1.1 construct/copy/destroy: |
80 | explicit multimap(const _Compare& __comp = _Compare(), | |
81 | const _Allocator& __a = _Allocator()) | |
82 | : _Base(__comp, __a) { } | |
83 | ||
84 | template<typename _InputIterator> | |
85 | multimap(_InputIterator __first, _InputIterator __last, | |
526da49c | 86 | const _Compare& __comp = _Compare(), |
285b36d6 | 87 | const _Allocator& __a = _Allocator()) |
1f5ca1a1 PC |
88 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, |
89 | __last)), | |
90 | __gnu_debug::__base(__last), | |
285b36d6 BK |
91 | __comp, __a) { } |
92 | ||
ed540c0a | 93 | multimap(const multimap& __x) |
526da49c | 94 | : _Base(__x), _Safe_base() { } |
285b36d6 | 95 | |
ed540c0a CJ |
96 | multimap(const _Base& __x) |
97 | : _Base(__x), _Safe_base() { } | |
98 | ||
99 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
100 | multimap(multimap&& __x) | |
5f1fd346 | 101 | : _Base(std::move(__x)), _Safe_base() |
ed540c0a | 102 | { this->_M_swap(__x); } |
988499f4 JM |
103 | |
104 | multimap(initializer_list<value_type> __l, | |
105 | const _Compare& __c = _Compare(), | |
106 | const allocator_type& __a = allocator_type()) | |
b798df05 | 107 | : _Base(__l, __c, __a), _Safe_base() { } |
ed540c0a | 108 | #endif |
285b36d6 BK |
109 | |
110 | ~multimap() { } | |
111 | ||
ed540c0a CJ |
112 | multimap& |
113 | operator=(const multimap& __x) | |
285b36d6 BK |
114 | { |
115 | *static_cast<_Base*>(this) = __x; | |
116 | this->_M_invalidate_all(); | |
117 | return *this; | |
118 | } | |
119 | ||
ed540c0a CJ |
120 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
121 | multimap& | |
122 | operator=(multimap&& __x) | |
123 | { | |
0462fd5e PC |
124 | // NB: DR 1204. |
125 | // NB: DR 675. | |
126 | clear(); | |
127 | swap(__x); | |
ed540c0a CJ |
128 | return *this; |
129 | } | |
988499f4 JM |
130 | |
131 | multimap& | |
132 | operator=(initializer_list<value_type> __l) | |
133 | { | |
134 | this->clear(); | |
135 | this->insert(__l); | |
136 | return *this; | |
137 | } | |
ed540c0a CJ |
138 | #endif |
139 | ||
285b36d6 BK |
140 | using _Base::get_allocator; |
141 | ||
142 | // iterators: | |
526da49c BI |
143 | iterator |
144 | begin() | |
285b36d6 BK |
145 | { return iterator(_Base::begin(), this); } |
146 | ||
526da49c BI |
147 | const_iterator |
148 | begin() const | |
285b36d6 BK |
149 | { return const_iterator(_Base::begin(), this); } |
150 | ||
526da49c BI |
151 | iterator |
152 | end() | |
285b36d6 BK |
153 | { return iterator(_Base::end(), this); } |
154 | ||
526da49c BI |
155 | const_iterator |
156 | end() const | |
285b36d6 BK |
157 | { return const_iterator(_Base::end(), this); } |
158 | ||
526da49c BI |
159 | reverse_iterator |
160 | rbegin() | |
285b36d6 BK |
161 | { return reverse_iterator(end()); } |
162 | ||
526da49c | 163 | const_reverse_iterator |
285b36d6 BK |
164 | rbegin() const |
165 | { return const_reverse_iterator(end()); } | |
166 | ||
526da49c BI |
167 | reverse_iterator |
168 | rend() | |
285b36d6 BK |
169 | { return reverse_iterator(begin()); } |
170 | ||
526da49c BI |
171 | const_reverse_iterator |
172 | rend() const | |
285b36d6 BK |
173 | { return const_reverse_iterator(begin()); } |
174 | ||
0cd50f89 PC |
175 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
176 | const_iterator | |
177 | cbegin() const | |
178 | { return const_iterator(_Base::begin(), this); } | |
179 | ||
180 | const_iterator | |
181 | cend() const | |
182 | { return const_iterator(_Base::end(), this); } | |
183 | ||
184 | const_reverse_iterator | |
185 | crbegin() const | |
186 | { return const_reverse_iterator(end()); } | |
187 | ||
188 | const_reverse_iterator | |
189 | crend() const | |
190 | { return const_reverse_iterator(begin()); } | |
191 | #endif | |
192 | ||
285b36d6 BK |
193 | // capacity: |
194 | using _Base::empty; | |
195 | using _Base::size; | |
196 | using _Base::max_size; | |
197 | ||
198 | // modifiers: | |
526da49c | 199 | iterator |
285b36d6 BK |
200 | insert(const value_type& __x) |
201 | { return iterator(_Base::insert(__x), this); } | |
202 | ||
e6a05448 PC |
203 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
204 | template<typename _Pair, typename = typename | |
205 | std::enable_if<std::is_convertible<_Pair, | |
206 | value_type>::value>::type> | |
207 | iterator | |
208 | insert(_Pair&& __x) | |
209 | { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } | |
210 | #endif | |
211 | ||
988499f4 JM |
212 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
213 | void | |
214 | insert(std::initializer_list<value_type> __list) | |
215 | { _Base::insert(__list); } | |
216 | #endif | |
217 | ||
526da49c | 218 | iterator |
6b6d5d09 PC |
219 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
220 | insert(const_iterator __position, const value_type& __x) | |
221 | #else | |
afe96d41 | 222 | insert(iterator __position, const value_type& __x) |
6b6d5d09 | 223 | #endif |
285b36d6 BK |
224 | { |
225 | __glibcxx_check_insert(__position); | |
226 | return iterator(_Base::insert(__position.base(), __x), this); | |
227 | } | |
228 | ||
e6a05448 PC |
229 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
230 | template<typename _Pair, typename = typename | |
231 | std::enable_if<std::is_convertible<_Pair, | |
232 | value_type>::value>::type> | |
233 | iterator | |
234 | insert(const_iterator __position, _Pair&& __x) | |
235 | { | |
236 | __glibcxx_check_insert(__position); | |
237 | return iterator(_Base::insert(__position.base(), | |
238 | std::forward<_Pair>(__x)), this); | |
239 | } | |
240 | #endif | |
241 | ||
285b36d6 | 242 | template<typename _InputIterator> |
526da49c | 243 | void |
285b36d6 BK |
244 | insert(_InputIterator __first, _InputIterator __last) |
245 | { | |
246 | __glibcxx_check_valid_range(__first, __last); | |
1f5ca1a1 PC |
247 | _Base::insert(__gnu_debug::__base(__first), |
248 | __gnu_debug::__base(__last)); | |
285b36d6 BK |
249 | } |
250 | ||
5ab06c6d PC |
251 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
252 | iterator | |
6b6d5d09 | 253 | erase(const_iterator __position) |
5ab06c6d PC |
254 | { |
255 | __glibcxx_check_erase(__position); | |
afe96d41 | 256 | this->_M_invalidate_if(_Equal(__position.base())); |
5ab06c6d PC |
257 | return iterator(_Base::erase(__position.base()), this); |
258 | } | |
259 | #else | |
526da49c | 260 | void |
285b36d6 BK |
261 | erase(iterator __position) |
262 | { | |
263 | __glibcxx_check_erase(__position); | |
afe96d41 | 264 | this->_M_invalidate_if(_Equal(__position.base())); |
285b36d6 BK |
265 | _Base::erase(__position.base()); |
266 | } | |
5ab06c6d | 267 | #endif |
285b36d6 | 268 | |
526da49c | 269 | size_type |
285b36d6 BK |
270 | erase(const key_type& __x) |
271 | { | |
afe96d41 FD |
272 | std::pair<_Base_iterator, _Base_iterator> __victims = |
273 | _Base::equal_range(__x); | |
285b36d6 | 274 | size_type __count = 0; |
afe96d41 FD |
275 | _Base_iterator __victim = __victims.first; |
276 | while (__victim != __victims.second) | |
277 | { | |
278 | this->_M_invalidate_if(_Equal(__victim)); | |
279 | _Base::erase(__victim++); | |
280 | ++__count; | |
281 | } | |
285b36d6 BK |
282 | return __count; |
283 | } | |
284 | ||
5ab06c6d PC |
285 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
286 | iterator | |
6b6d5d09 | 287 | erase(const_iterator __first, const_iterator __last) |
5ab06c6d PC |
288 | { |
289 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
290 | // 151. can't currently clear() empty container | |
291 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
292 | for (_Base_const_iterator __victim = __first.base(); |
293 | __victim != __last.base(); ++__victim) | |
294 | { | |
295 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), | |
296 | _M_message(__gnu_debug::__msg_valid_range) | |
297 | ._M_iterator(__first, "first") | |
298 | ._M_iterator(__last, "last")); | |
299 | this->_M_invalidate_if(_Equal(__victim)); | |
300 | } | |
301 | return iterator(_Base::erase(__first.base(), __last.base()), this); | |
5ab06c6d PC |
302 | } |
303 | #else | |
526da49c | 304 | void |
285b36d6 BK |
305 | erase(iterator __first, iterator __last) |
306 | { | |
307 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
308 | // 151. can't currently clear() empty container | |
309 | __glibcxx_check_erase_range(__first, __last); | |
afe96d41 FD |
310 | for (_Base_iterator __victim = __first.base(); |
311 | __victim != __last.base(); ++__victim) | |
312 | { | |
313 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), | |
314 | _M_message(__gnu_debug::__msg_valid_range) | |
315 | ._M_iterator(__first, "first") | |
316 | ._M_iterator(__last, "last")); | |
317 | this->_M_invalidate_if(_Equal(__victim)); | |
318 | } | |
319 | _Base::erase(__first.base(), __last.base()); | |
285b36d6 | 320 | } |
5ab06c6d | 321 | #endif |
285b36d6 | 322 | |
526da49c | 323 | void |
ed540c0a | 324 | swap(multimap& __x) |
285b36d6 BK |
325 | { |
326 | _Base::swap(__x); | |
327 | this->_M_swap(__x); | |
328 | } | |
329 | ||
526da49c | 330 | void |
285b36d6 | 331 | clear() |
afe96d41 FD |
332 | { |
333 | this->_M_invalidate_all(); | |
334 | _Base::clear(); | |
335 | } | |
285b36d6 BK |
336 | |
337 | // observers: | |
338 | using _Base::key_comp; | |
339 | using _Base::value_comp; | |
340 | ||
341 | // 23.3.1.3 multimap operations: | |
526da49c | 342 | iterator |
285b36d6 BK |
343 | find(const key_type& __x) |
344 | { return iterator(_Base::find(__x), this); } | |
345 | ||
526da49c | 346 | const_iterator |
285b36d6 BK |
347 | find(const key_type& __x) const |
348 | { return const_iterator(_Base::find(__x), this); } | |
349 | ||
350 | using _Base::count; | |
351 | ||
526da49c | 352 | iterator |
285b36d6 BK |
353 | lower_bound(const key_type& __x) |
354 | { return iterator(_Base::lower_bound(__x), this); } | |
355 | ||
526da49c | 356 | const_iterator |
285b36d6 BK |
357 | lower_bound(const key_type& __x) const |
358 | { return const_iterator(_Base::lower_bound(__x), this); } | |
359 | ||
526da49c | 360 | iterator |
285b36d6 BK |
361 | upper_bound(const key_type& __x) |
362 | { return iterator(_Base::upper_bound(__x), this); } | |
363 | ||
526da49c | 364 | const_iterator |
285b36d6 BK |
365 | upper_bound(const key_type& __x) const |
366 | { return const_iterator(_Base::upper_bound(__x), this); } | |
367 | ||
368 | std::pair<iterator,iterator> | |
369 | equal_range(const key_type& __x) | |
370 | { | |
285b36d6 BK |
371 | std::pair<_Base_iterator, _Base_iterator> __res = |
372 | _Base::equal_range(__x); | |
373 | return std::make_pair(iterator(__res.first, this), | |
374 | iterator(__res.second, this)); | |
375 | } | |
376 | ||
377 | std::pair<const_iterator,const_iterator> | |
378 | equal_range(const key_type& __x) const | |
379 | { | |
285b36d6 | 380 | std::pair<_Base_const_iterator, _Base_const_iterator> __res = |
afe96d41 | 381 | _Base::equal_range(__x); |
285b36d6 BK |
382 | return std::make_pair(const_iterator(__res.first, this), |
383 | const_iterator(__res.second, this)); | |
384 | } | |
385 | ||
526da49c | 386 | _Base& |
285b36d6 BK |
387 | _M_base() { return *this; } |
388 | ||
526da49c | 389 | const _Base& |
285b36d6 BK |
390 | _M_base() const { return *this; } |
391 | ||
392 | private: | |
526da49c | 393 | void |
285b36d6 BK |
394 | _M_invalidate_all() |
395 | { | |
285b36d6 | 396 | typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; |
afe96d41 | 397 | this->_M_invalidate_if(_Not_equal(_Base::end())); |
285b36d6 BK |
398 | } |
399 | }; | |
400 | ||
ed540c0a CJ |
401 | template<typename _Key, typename _Tp, |
402 | typename _Compare, typename _Allocator> | |
285b36d6 | 403 | inline bool |
ed540c0a CJ |
404 | operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
405 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
406 | { return __lhs._M_base() == __rhs._M_base(); } |
407 | ||
ed540c0a CJ |
408 | template<typename _Key, typename _Tp, |
409 | typename _Compare, typename _Allocator> | |
285b36d6 | 410 | inline bool |
ed540c0a CJ |
411 | operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
412 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
413 | { return __lhs._M_base() != __rhs._M_base(); } |
414 | ||
ed540c0a CJ |
415 | template<typename _Key, typename _Tp, |
416 | typename _Compare, typename _Allocator> | |
285b36d6 | 417 | inline bool |
ed540c0a CJ |
418 | operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
419 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
420 | { return __lhs._M_base() < __rhs._M_base(); } |
421 | ||
ed540c0a CJ |
422 | template<typename _Key, typename _Tp, |
423 | typename _Compare, typename _Allocator> | |
285b36d6 | 424 | inline bool |
ed540c0a CJ |
425 | operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
426 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
427 | { return __lhs._M_base() <= __rhs._M_base(); } |
428 | ||
ed540c0a CJ |
429 | template<typename _Key, typename _Tp, |
430 | typename _Compare, typename _Allocator> | |
285b36d6 | 431 | inline bool |
ed540c0a CJ |
432 | operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
433 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
434 | { return __lhs._M_base() >= __rhs._M_base(); } |
435 | ||
ed540c0a CJ |
436 | template<typename _Key, typename _Tp, |
437 | typename _Compare, typename _Allocator> | |
285b36d6 | 438 | inline bool |
ed540c0a CJ |
439 | operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
440 | const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 BK |
441 | { return __lhs._M_base() > __rhs._M_base(); } |
442 | ||
ed540c0a CJ |
443 | template<typename _Key, typename _Tp, |
444 | typename _Compare, typename _Allocator> | |
285b36d6 | 445 | inline void |
ed540c0a CJ |
446 | swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, |
447 | multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) | |
285b36d6 | 448 | { __lhs.swap(__rhs); } |
ed540c0a | 449 | |
45f388bb | 450 | } // namespace __debug |
3cbc7af0 | 451 | } // namespace std |
285b36d6 | 452 | |
526da49c | 453 | #endif |