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