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