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