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