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