libstdc++
|
00001 // Debugging multiset implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003-2014 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file debug/multiset.h 00026 * This file is a GNU debug extension to the Standard C++ Library. 00027 */ 00028 00029 #ifndef _GLIBCXX_DEBUG_MULTISET_H 00030 #define _GLIBCXX_DEBUG_MULTISET_H 1 00031 00032 #include <debug/safe_sequence.h> 00033 #include <debug/safe_iterator.h> 00034 #include <utility> 00035 00036 namespace std _GLIBCXX_VISIBILITY(default) 00037 { 00038 namespace __debug 00039 { 00040 /// Class std::multiset with safety/checking/debug instrumentation. 00041 template<typename _Key, typename _Compare = std::less<_Key>, 00042 typename _Allocator = std::allocator<_Key> > 00043 class multiset 00044 : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>, 00045 public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> > 00046 { 00047 typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base; 00048 00049 typedef typename _Base::const_iterator _Base_const_iterator; 00050 typedef typename _Base::iterator _Base_iterator; 00051 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00052 00053 #if __cplusplus >= 201103L 00054 typedef __gnu_cxx::__alloc_traits<typename 00055 _Base::allocator_type> _Alloc_traits; 00056 #endif 00057 public: 00058 // types: 00059 typedef _Key key_type; 00060 typedef _Key value_type; 00061 typedef _Compare key_compare; 00062 typedef _Compare value_compare; 00063 typedef _Allocator allocator_type; 00064 typedef typename _Base::reference reference; 00065 typedef typename _Base::const_reference const_reference; 00066 00067 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset> 00068 iterator; 00069 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00070 multiset> const_iterator; 00071 00072 typedef typename _Base::size_type size_type; 00073 typedef typename _Base::difference_type difference_type; 00074 typedef typename _Base::pointer pointer; 00075 typedef typename _Base::const_pointer const_pointer; 00076 typedef std::reverse_iterator<iterator> reverse_iterator; 00077 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00078 00079 // 23.3.3.1 construct/copy/destroy: 00080 00081 multiset() : _Base() { } 00082 00083 explicit multiset(const _Compare& __comp, 00084 const _Allocator& __a = _Allocator()) 00085 : _Base(__comp, __a) { } 00086 00087 template<typename _InputIterator> 00088 multiset(_InputIterator __first, _InputIterator __last, 00089 const _Compare& __comp = _Compare(), 00090 const _Allocator& __a = _Allocator()) 00091 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00092 __last)), 00093 __gnu_debug::__base(__last), 00094 __comp, __a) { } 00095 00096 multiset(const multiset& __x) 00097 : _Base(__x) { } 00098 00099 multiset(const _Base& __x) 00100 : _Base(__x) { } 00101 00102 #if __cplusplus >= 201103L 00103 multiset(multiset&& __x) 00104 noexcept(is_nothrow_copy_constructible<_Compare>::value) 00105 : _Base(std::move(__x)) 00106 { this->_M_swap(__x); } 00107 00108 multiset(initializer_list<value_type> __l, 00109 const _Compare& __comp = _Compare(), 00110 const allocator_type& __a = allocator_type()) 00111 : _Base(__l, __comp, __a) { } 00112 00113 explicit 00114 multiset(const allocator_type& __a) 00115 : _Base(__a) { } 00116 00117 multiset(const multiset& __m, const allocator_type& __a) 00118 : _Base(__m, __a) { } 00119 00120 multiset(multiset&& __m, const allocator_type& __a) 00121 : _Base(std::move(__m._M_base()), __a) { } 00122 00123 multiset(initializer_list<value_type> __l, const allocator_type& __a) 00124 : _Base(__l, __a) 00125 { } 00126 00127 template<typename _InputIterator> 00128 multiset(_InputIterator __first, _InputIterator __last, 00129 const allocator_type& __a) 00130 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00131 __last)), 00132 __gnu_debug::__base(__last), __a) 00133 { } 00134 #endif 00135 00136 ~multiset() _GLIBCXX_NOEXCEPT { } 00137 00138 multiset& 00139 operator=(const multiset& __x) 00140 { 00141 _M_base() = __x; 00142 this->_M_invalidate_all(); 00143 return *this; 00144 } 00145 00146 #if __cplusplus >= 201103L 00147 multiset& 00148 operator=(multiset&& __x) 00149 noexcept(_Alloc_traits::_S_nothrow_move()) 00150 { 00151 __glibcxx_check_self_move_assign(__x); 00152 bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign() 00153 || __x.get_allocator() == this->get_allocator(); 00154 _M_base() = std::move(__x._M_base()); 00155 if (__xfer_memory) 00156 this->_M_swap(__x); 00157 else 00158 this->_M_invalidate_all(); 00159 __x._M_invalidate_all(); 00160 return *this; 00161 } 00162 00163 multiset& 00164 operator=(initializer_list<value_type> __l) 00165 { 00166 _M_base() = __l; 00167 this->_M_invalidate_all(); 00168 return *this; 00169 } 00170 #endif 00171 00172 using _Base::get_allocator; 00173 00174 // iterators: 00175 iterator 00176 begin() _GLIBCXX_NOEXCEPT 00177 { return iterator(_Base::begin(), this); } 00178 00179 const_iterator 00180 begin() const _GLIBCXX_NOEXCEPT 00181 { return const_iterator(_Base::begin(), this); } 00182 00183 iterator 00184 end() _GLIBCXX_NOEXCEPT 00185 { return iterator(_Base::end(), this); } 00186 00187 const_iterator 00188 end() const _GLIBCXX_NOEXCEPT 00189 { return const_iterator(_Base::end(), this); } 00190 00191 reverse_iterator 00192 rbegin() _GLIBCXX_NOEXCEPT 00193 { return reverse_iterator(end()); } 00194 00195 const_reverse_iterator 00196 rbegin() const _GLIBCXX_NOEXCEPT 00197 { return const_reverse_iterator(end()); } 00198 00199 reverse_iterator 00200 rend() _GLIBCXX_NOEXCEPT 00201 { return reverse_iterator(begin()); } 00202 00203 const_reverse_iterator 00204 rend() const _GLIBCXX_NOEXCEPT 00205 { return const_reverse_iterator(begin()); } 00206 00207 #if __cplusplus >= 201103L 00208 const_iterator 00209 cbegin() const noexcept 00210 { return const_iterator(_Base::begin(), this); } 00211 00212 const_iterator 00213 cend() const noexcept 00214 { return const_iterator(_Base::end(), this); } 00215 00216 const_reverse_iterator 00217 crbegin() const noexcept 00218 { return const_reverse_iterator(end()); } 00219 00220 const_reverse_iterator 00221 crend() const noexcept 00222 { return const_reverse_iterator(begin()); } 00223 #endif 00224 00225 // capacity: 00226 using _Base::empty; 00227 using _Base::size; 00228 using _Base::max_size; 00229 00230 // modifiers: 00231 #if __cplusplus >= 201103L 00232 template<typename... _Args> 00233 iterator 00234 emplace(_Args&&... __args) 00235 { 00236 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 00237 } 00238 00239 template<typename... _Args> 00240 iterator 00241 emplace_hint(const_iterator __pos, _Args&&... __args) 00242 { 00243 __glibcxx_check_insert(__pos); 00244 return iterator(_Base::emplace_hint(__pos.base(), 00245 std::forward<_Args>(__args)...), 00246 this); 00247 } 00248 #endif 00249 00250 iterator 00251 insert(const value_type& __x) 00252 { return iterator(_Base::insert(__x), this); } 00253 00254 #if __cplusplus >= 201103L 00255 iterator 00256 insert(value_type&& __x) 00257 { return iterator(_Base::insert(std::move(__x)), this); } 00258 #endif 00259 00260 iterator 00261 insert(const_iterator __position, const value_type& __x) 00262 { 00263 __glibcxx_check_insert(__position); 00264 return iterator(_Base::insert(__position.base(), __x), this); 00265 } 00266 00267 #if __cplusplus >= 201103L 00268 iterator 00269 insert(const_iterator __position, value_type&& __x) 00270 { 00271 __glibcxx_check_insert(__position); 00272 return iterator(_Base::insert(__position.base(), std::move(__x)), 00273 this); 00274 } 00275 #endif 00276 00277 template<typename _InputIterator> 00278 void 00279 insert(_InputIterator __first, _InputIterator __last) 00280 { 00281 __glibcxx_check_valid_range(__first, __last); 00282 _Base::insert(__gnu_debug::__base(__first), 00283 __gnu_debug::__base(__last)); 00284 } 00285 00286 #if __cplusplus >= 201103L 00287 void 00288 insert(initializer_list<value_type> __l) 00289 { _Base::insert(__l); } 00290 #endif 00291 00292 #if __cplusplus >= 201103L 00293 iterator 00294 erase(const_iterator __position) 00295 { 00296 __glibcxx_check_erase(__position); 00297 this->_M_invalidate_if(_Equal(__position.base())); 00298 return iterator(_Base::erase(__position.base()), this); 00299 } 00300 #else 00301 void 00302 erase(iterator __position) 00303 { 00304 __glibcxx_check_erase(__position); 00305 this->_M_invalidate_if(_Equal(__position.base())); 00306 _Base::erase(__position.base()); 00307 } 00308 #endif 00309 00310 size_type 00311 erase(const key_type& __x) 00312 { 00313 std::pair<_Base_iterator, _Base_iterator> __victims = 00314 _Base::equal_range(__x); 00315 size_type __count = 0; 00316 _Base_iterator __victim = __victims.first; 00317 while (__victim != __victims.second) 00318 { 00319 this->_M_invalidate_if(_Equal(__victim)); 00320 _Base::erase(__victim++); 00321 ++__count; 00322 } 00323 return __count; 00324 } 00325 00326 #if __cplusplus >= 201103L 00327 iterator 00328 erase(const_iterator __first, const_iterator __last) 00329 { 00330 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00331 // 151. can't currently clear() empty container 00332 __glibcxx_check_erase_range(__first, __last); 00333 for (_Base_const_iterator __victim = __first.base(); 00334 __victim != __last.base(); ++__victim) 00335 { 00336 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00337 _M_message(__gnu_debug::__msg_valid_range) 00338 ._M_iterator(__first, "first") 00339 ._M_iterator(__last, "last")); 00340 this->_M_invalidate_if(_Equal(__victim)); 00341 } 00342 return iterator(_Base::erase(__first.base(), __last.base()), this); 00343 } 00344 #else 00345 void 00346 erase(iterator __first, iterator __last) 00347 { 00348 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00349 // 151. can't currently clear() empty container 00350 __glibcxx_check_erase_range(__first, __last); 00351 for (_Base_iterator __victim = __first.base(); 00352 __victim != __last.base(); ++__victim) 00353 { 00354 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00355 _M_message(__gnu_debug::__msg_valid_range) 00356 ._M_iterator(__first, "first") 00357 ._M_iterator(__last, "last")); 00358 this->_M_invalidate_if(_Equal(__victim)); 00359 } 00360 _Base::erase(__first.base(), __last.base()); 00361 } 00362 #endif 00363 00364 void 00365 swap(multiset& __x) 00366 #if __cplusplus >= 201103L 00367 noexcept(_Alloc_traits::_S_nothrow_swap()) 00368 #endif 00369 { 00370 #if __cplusplus >= 201103L 00371 if (!_Alloc_traits::_S_propagate_on_swap()) 00372 __glibcxx_check_equal_allocs(__x); 00373 #endif 00374 _Base::swap(__x); 00375 this->_M_swap(__x); 00376 } 00377 00378 void 00379 clear() _GLIBCXX_NOEXCEPT 00380 { 00381 this->_M_invalidate_all(); 00382 _Base::clear(); 00383 } 00384 00385 // observers: 00386 using _Base::key_comp; 00387 using _Base::value_comp; 00388 00389 // multiset operations: 00390 iterator 00391 find(const key_type& __x) 00392 { return iterator(_Base::find(__x), this); } 00393 00394 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00395 // 214. set::find() missing const overload 00396 const_iterator 00397 find(const key_type& __x) const 00398 { return const_iterator(_Base::find(__x), this); } 00399 00400 using _Base::count; 00401 00402 iterator 00403 lower_bound(const key_type& __x) 00404 { return iterator(_Base::lower_bound(__x), this); } 00405 00406 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00407 // 214. set::find() missing const overload 00408 const_iterator 00409 lower_bound(const key_type& __x) const 00410 { return const_iterator(_Base::lower_bound(__x), this); } 00411 00412 iterator 00413 upper_bound(const key_type& __x) 00414 { return iterator(_Base::upper_bound(__x), this); } 00415 00416 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00417 // 214. set::find() missing const overload 00418 const_iterator 00419 upper_bound(const key_type& __x) const 00420 { return const_iterator(_Base::upper_bound(__x), this); } 00421 00422 std::pair<iterator,iterator> 00423 equal_range(const key_type& __x) 00424 { 00425 std::pair<_Base_iterator, _Base_iterator> __res = 00426 _Base::equal_range(__x); 00427 return std::make_pair(iterator(__res.first, this), 00428 iterator(__res.second, this)); 00429 } 00430 00431 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00432 // 214. set::find() missing const overload 00433 std::pair<const_iterator,const_iterator> 00434 equal_range(const key_type& __x) const 00435 { 00436 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00437 _Base::equal_range(__x); 00438 return std::make_pair(const_iterator(__res.first, this), 00439 const_iterator(__res.second, this)); 00440 } 00441 00442 _Base& 00443 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 00444 00445 const _Base& 00446 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 00447 00448 private: 00449 void 00450 _M_invalidate_all() 00451 { 00452 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00453 this->_M_invalidate_if(_Not_equal(_Base::end())); 00454 } 00455 }; 00456 00457 template<typename _Key, typename _Compare, typename _Allocator> 00458 inline bool 00459 operator==(const multiset<_Key, _Compare, _Allocator>& __lhs, 00460 const multiset<_Key, _Compare, _Allocator>& __rhs) 00461 { return __lhs._M_base() == __rhs._M_base(); } 00462 00463 template<typename _Key, typename _Compare, typename _Allocator> 00464 inline bool 00465 operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs, 00466 const multiset<_Key, _Compare, _Allocator>& __rhs) 00467 { return __lhs._M_base() != __rhs._M_base(); } 00468 00469 template<typename _Key, typename _Compare, typename _Allocator> 00470 inline bool 00471 operator<(const multiset<_Key, _Compare, _Allocator>& __lhs, 00472 const multiset<_Key, _Compare, _Allocator>& __rhs) 00473 { return __lhs._M_base() < __rhs._M_base(); } 00474 00475 template<typename _Key, typename _Compare, typename _Allocator> 00476 inline bool 00477 operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs, 00478 const multiset<_Key, _Compare, _Allocator>& __rhs) 00479 { return __lhs._M_base() <= __rhs._M_base(); } 00480 00481 template<typename _Key, typename _Compare, typename _Allocator> 00482 inline bool 00483 operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs, 00484 const multiset<_Key, _Compare, _Allocator>& __rhs) 00485 { return __lhs._M_base() >= __rhs._M_base(); } 00486 00487 template<typename _Key, typename _Compare, typename _Allocator> 00488 inline bool 00489 operator>(const multiset<_Key, _Compare, _Allocator>& __lhs, 00490 const multiset<_Key, _Compare, _Allocator>& __rhs) 00491 { return __lhs._M_base() > __rhs._M_base(); } 00492 00493 template<typename _Key, typename _Compare, typename _Allocator> 00494 void 00495 swap(multiset<_Key, _Compare, _Allocator>& __x, 00496 multiset<_Key, _Compare, _Allocator>& __y) 00497 { return __x.swap(__y); } 00498 00499 } // namespace __debug 00500 } // namespace std 00501 00502 #endif