libstdc++
|
00001 // Debugging multimap implementation -*- C++ -*- 00002 00003 // Copyright (C) 2003, 2004, 2005, 2006, 2007, 2009, 2010, 2011 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/multimap.h 00027 * This file is a GNU debug extension to the Standard C++ Library. 00028 */ 00029 00030 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H 00031 #define _GLIBCXX_DEBUG_MULTIMAP_H 1 00032 00033 #include <debug/safe_sequence.h> 00034 #include <debug/safe_iterator.h> 00035 #include <utility> 00036 00037 namespace std _GLIBCXX_VISIBILITY(default) 00038 { 00039 namespace __debug 00040 { 00041 /// Class std::multimap with safety/checking/debug instrumentation. 00042 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 00043 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 00044 class multimap 00045 : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>, 00046 public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp, 00047 _Compare, _Allocator> > 00048 { 00049 typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 00050 typedef __gnu_debug::_Safe_sequence<multimap> _Safe_base; 00051 00052 typedef typename _Base::const_iterator _Base_const_iterator; 00053 typedef typename _Base::iterator _Base_iterator; 00054 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 00055 public: 00056 // types: 00057 typedef _Key key_type; 00058 typedef _Tp mapped_type; 00059 typedef std::pair<const _Key, _Tp> value_type; 00060 typedef _Compare key_compare; 00061 typedef _Allocator allocator_type; 00062 typedef typename _Base::reference reference; 00063 typedef typename _Base::const_reference const_reference; 00064 00065 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 00066 iterator; 00067 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 00068 multimap> const_iterator; 00069 00070 typedef typename _Base::size_type size_type; 00071 typedef typename _Base::difference_type difference_type; 00072 typedef typename _Base::pointer pointer; 00073 typedef typename _Base::const_pointer const_pointer; 00074 typedef std::reverse_iterator<iterator> reverse_iterator; 00075 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 00076 00077 // 23.3.1.1 construct/copy/destroy: 00078 explicit multimap(const _Compare& __comp = _Compare(), 00079 const _Allocator& __a = _Allocator()) 00080 : _Base(__comp, __a) { } 00081 00082 template<typename _InputIterator> 00083 multimap(_InputIterator __first, _InputIterator __last, 00084 const _Compare& __comp = _Compare(), 00085 const _Allocator& __a = _Allocator()) 00086 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 00087 __last)), 00088 __gnu_debug::__base(__last), 00089 __comp, __a) { } 00090 00091 multimap(const multimap& __x) 00092 : _Base(__x), _Safe_base() { } 00093 00094 multimap(const _Base& __x) 00095 : _Base(__x), _Safe_base() { } 00096 00097 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00098 multimap(multimap&& __x) 00099 : _Base(std::move(__x)), _Safe_base() 00100 { this->_M_swap(__x); } 00101 00102 multimap(initializer_list<value_type> __l, 00103 const _Compare& __c = _Compare(), 00104 const allocator_type& __a = allocator_type()) 00105 : _Base(__l, __c, __a), _Safe_base() { } 00106 #endif 00107 00108 ~multimap() { } 00109 00110 multimap& 00111 operator=(const multimap& __x) 00112 { 00113 *static_cast<_Base*>(this) = __x; 00114 this->_M_invalidate_all(); 00115 return *this; 00116 } 00117 00118 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00119 multimap& 00120 operator=(multimap&& __x) 00121 { 00122 // NB: DR 1204. 00123 // NB: DR 675. 00124 clear(); 00125 swap(__x); 00126 return *this; 00127 } 00128 00129 multimap& 00130 operator=(initializer_list<value_type> __l) 00131 { 00132 this->clear(); 00133 this->insert(__l); 00134 return *this; 00135 } 00136 #endif 00137 00138 using _Base::get_allocator; 00139 00140 // iterators: 00141 iterator 00142 begin() 00143 { return iterator(_Base::begin(), this); } 00144 00145 const_iterator 00146 begin() const 00147 { return const_iterator(_Base::begin(), this); } 00148 00149 iterator 00150 end() 00151 { return iterator(_Base::end(), this); } 00152 00153 const_iterator 00154 end() const 00155 { return const_iterator(_Base::end(), this); } 00156 00157 reverse_iterator 00158 rbegin() 00159 { return reverse_iterator(end()); } 00160 00161 const_reverse_iterator 00162 rbegin() const 00163 { return const_reverse_iterator(end()); } 00164 00165 reverse_iterator 00166 rend() 00167 { return reverse_iterator(begin()); } 00168 00169 const_reverse_iterator 00170 rend() const 00171 { return const_reverse_iterator(begin()); } 00172 00173 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00174 const_iterator 00175 cbegin() const 00176 { return const_iterator(_Base::begin(), this); } 00177 00178 const_iterator 00179 cend() const 00180 { return const_iterator(_Base::end(), this); } 00181 00182 const_reverse_iterator 00183 crbegin() const 00184 { return const_reverse_iterator(end()); } 00185 00186 const_reverse_iterator 00187 crend() const 00188 { return const_reverse_iterator(begin()); } 00189 #endif 00190 00191 // capacity: 00192 using _Base::empty; 00193 using _Base::size; 00194 using _Base::max_size; 00195 00196 // modifiers: 00197 iterator 00198 insert(const value_type& __x) 00199 { return iterator(_Base::insert(__x), this); } 00200 00201 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00202 template<typename _Pair, typename = typename 00203 std::enable_if<std::is_convertible<_Pair, 00204 value_type>::value>::type> 00205 iterator 00206 insert(_Pair&& __x) 00207 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 00208 #endif 00209 00210 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00211 void 00212 insert(std::initializer_list<value_type> __list) 00213 { _Base::insert(__list); } 00214 #endif 00215 00216 iterator 00217 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00218 insert(const_iterator __position, const value_type& __x) 00219 #else 00220 insert(iterator __position, const value_type& __x) 00221 #endif 00222 { 00223 __glibcxx_check_insert(__position); 00224 return iterator(_Base::insert(__position.base(), __x), this); 00225 } 00226 00227 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00228 template<typename _Pair, typename = typename 00229 std::enable_if<std::is_convertible<_Pair, 00230 value_type>::value>::type> 00231 iterator 00232 insert(const_iterator __position, _Pair&& __x) 00233 { 00234 __glibcxx_check_insert(__position); 00235 return iterator(_Base::insert(__position.base(), 00236 std::forward<_Pair>(__x)), this); 00237 } 00238 #endif 00239 00240 template<typename _InputIterator> 00241 void 00242 insert(_InputIterator __first, _InputIterator __last) 00243 { 00244 __glibcxx_check_valid_range(__first, __last); 00245 _Base::insert(__gnu_debug::__base(__first), 00246 __gnu_debug::__base(__last)); 00247 } 00248 00249 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00250 iterator 00251 erase(const_iterator __position) 00252 { 00253 __glibcxx_check_erase(__position); 00254 this->_M_invalidate_if(_Equal(__position.base())); 00255 return iterator(_Base::erase(__position.base()), this); 00256 } 00257 #else 00258 void 00259 erase(iterator __position) 00260 { 00261 __glibcxx_check_erase(__position); 00262 this->_M_invalidate_if(_Equal(__position.base())); 00263 _Base::erase(__position.base()); 00264 } 00265 #endif 00266 00267 size_type 00268 erase(const key_type& __x) 00269 { 00270 std::pair<_Base_iterator, _Base_iterator> __victims = 00271 _Base::equal_range(__x); 00272 size_type __count = 0; 00273 _Base_iterator __victim = __victims.first; 00274 while (__victim != __victims.second) 00275 { 00276 this->_M_invalidate_if(_Equal(__victim)); 00277 _Base::erase(__victim++); 00278 ++__count; 00279 } 00280 return __count; 00281 } 00282 00283 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00284 iterator 00285 erase(const_iterator __first, const_iterator __last) 00286 { 00287 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00288 // 151. can't currently clear() empty container 00289 __glibcxx_check_erase_range(__first, __last); 00290 for (_Base_const_iterator __victim = __first.base(); 00291 __victim != __last.base(); ++__victim) 00292 { 00293 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00294 _M_message(__gnu_debug::__msg_valid_range) 00295 ._M_iterator(__first, "first") 00296 ._M_iterator(__last, "last")); 00297 this->_M_invalidate_if(_Equal(__victim)); 00298 } 00299 return iterator(_Base::erase(__first.base(), __last.base()), this); 00300 } 00301 #else 00302 void 00303 erase(iterator __first, iterator __last) 00304 { 00305 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00306 // 151. can't currently clear() empty container 00307 __glibcxx_check_erase_range(__first, __last); 00308 for (_Base_iterator __victim = __first.base(); 00309 __victim != __last.base(); ++__victim) 00310 { 00311 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 00312 _M_message(__gnu_debug::__msg_valid_range) 00313 ._M_iterator(__first, "first") 00314 ._M_iterator(__last, "last")); 00315 this->_M_invalidate_if(_Equal(__victim)); 00316 } 00317 _Base::erase(__first.base(), __last.base()); 00318 } 00319 #endif 00320 00321 void 00322 swap(multimap& __x) 00323 { 00324 _Base::swap(__x); 00325 this->_M_swap(__x); 00326 } 00327 00328 void 00329 clear() 00330 { 00331 this->_M_invalidate_all(); 00332 _Base::clear(); 00333 } 00334 00335 // observers: 00336 using _Base::key_comp; 00337 using _Base::value_comp; 00338 00339 // 23.3.1.3 multimap operations: 00340 iterator 00341 find(const key_type& __x) 00342 { return iterator(_Base::find(__x), this); } 00343 00344 const_iterator 00345 find(const key_type& __x) const 00346 { return const_iterator(_Base::find(__x), this); } 00347 00348 using _Base::count; 00349 00350 iterator 00351 lower_bound(const key_type& __x) 00352 { return iterator(_Base::lower_bound(__x), this); } 00353 00354 const_iterator 00355 lower_bound(const key_type& __x) const 00356 { return const_iterator(_Base::lower_bound(__x), this); } 00357 00358 iterator 00359 upper_bound(const key_type& __x) 00360 { return iterator(_Base::upper_bound(__x), this); } 00361 00362 const_iterator 00363 upper_bound(const key_type& __x) const 00364 { return const_iterator(_Base::upper_bound(__x), this); } 00365 00366 std::pair<iterator,iterator> 00367 equal_range(const key_type& __x) 00368 { 00369 std::pair<_Base_iterator, _Base_iterator> __res = 00370 _Base::equal_range(__x); 00371 return std::make_pair(iterator(__res.first, this), 00372 iterator(__res.second, this)); 00373 } 00374 00375 std::pair<const_iterator,const_iterator> 00376 equal_range(const key_type& __x) const 00377 { 00378 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 00379 _Base::equal_range(__x); 00380 return std::make_pair(const_iterator(__res.first, this), 00381 const_iterator(__res.second, this)); 00382 } 00383 00384 _Base& 00385 _M_base() { return *this; } 00386 00387 const _Base& 00388 _M_base() const { return *this; } 00389 00390 private: 00391 void 00392 _M_invalidate_all() 00393 { 00394 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 00395 this->_M_invalidate_if(_Not_equal(_Base::end())); 00396 } 00397 }; 00398 00399 template<typename _Key, typename _Tp, 00400 typename _Compare, typename _Allocator> 00401 inline bool 00402 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00403 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00404 { return __lhs._M_base() == __rhs._M_base(); } 00405 00406 template<typename _Key, typename _Tp, 00407 typename _Compare, typename _Allocator> 00408 inline bool 00409 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00410 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00411 { return __lhs._M_base() != __rhs._M_base(); } 00412 00413 template<typename _Key, typename _Tp, 00414 typename _Compare, typename _Allocator> 00415 inline bool 00416 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00417 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00418 { return __lhs._M_base() < __rhs._M_base(); } 00419 00420 template<typename _Key, typename _Tp, 00421 typename _Compare, typename _Allocator> 00422 inline bool 00423 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00424 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00425 { return __lhs._M_base() <= __rhs._M_base(); } 00426 00427 template<typename _Key, typename _Tp, 00428 typename _Compare, typename _Allocator> 00429 inline bool 00430 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00431 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00432 { return __lhs._M_base() >= __rhs._M_base(); } 00433 00434 template<typename _Key, typename _Tp, 00435 typename _Compare, typename _Allocator> 00436 inline bool 00437 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00438 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00439 { return __lhs._M_base() > __rhs._M_base(); } 00440 00441 template<typename _Key, typename _Tp, 00442 typename _Compare, typename _Allocator> 00443 inline void 00444 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 00445 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 00446 { __lhs.swap(__rhs); } 00447 00448 } // namespace __debug 00449 } // namespace std 00450 00451 #endif