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