1 // Debugging multimap implementation -*- C++ -*- 2 3 // Copyright (C) 2003-2013 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file debug/multimap.h 26 * This file is a GNU debug extension to the Standard C++ Library. 27 */ 28 29 #ifndef _GLIBCXX_DEBUG_MULTIMAP_H 30 #define _GLIBCXX_DEBUG_MULTIMAP_H 1 31 32 #include <debug/safe_sequence.h> 33 #include <debug/safe_iterator.h> 34 #include <utility> 35 36 namespace std _GLIBCXX_VISIBILITY(default) 37 { 38 namespace __debug 39 { 40 /// Class std::multimap with safety/checking/debug instrumentation. 41 template<typename _Key, typename _Tp, typename _Compare = std::less<_Key>, 42 typename _Allocator = std::allocator<std::pair<const _Key, _Tp> > > 43 class multimap 44 : public _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator>, 45 public __gnu_debug::_Safe_sequence<multimap<_Key, _Tp, 46 _Compare, _Allocator> > 47 { 48 typedef _GLIBCXX_STD_C::multimap<_Key, _Tp, _Compare, _Allocator> _Base; 49 50 typedef typename _Base::const_iterator _Base_const_iterator; 51 typedef typename _Base::iterator _Base_iterator; 52 typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal; 53 public: 54 // types: 55 typedef _Key key_type; 56 typedef _Tp mapped_type; 57 typedef std::pair<const _Key, _Tp> value_type; 58 typedef _Compare key_compare; 59 typedef _Allocator allocator_type; 60 typedef typename _Base::reference reference; 61 typedef typename _Base::const_reference const_reference; 62 63 typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap> 64 iterator; 65 typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, 66 multimap> const_iterator; 67 68 typedef typename _Base::size_type size_type; 69 typedef typename _Base::difference_type difference_type; 70 typedef typename _Base::pointer pointer; 71 typedef typename _Base::const_pointer const_pointer; 72 typedef std::reverse_iterator<iterator> reverse_iterator; 73 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 74 75 // 23.3.1.1 construct/copy/destroy: 76 explicit multimap(const _Compare& __comp = _Compare(), 77 const _Allocator& __a = _Allocator()) 78 : _Base(__comp, __a) { } 79 80 template<typename _InputIterator> 81 multimap(_InputIterator __first, _InputIterator __last, 82 const _Compare& __comp = _Compare(), 83 const _Allocator& __a = _Allocator()) 84 : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, 85 __last)), 86 __gnu_debug::__base(__last), 87 __comp, __a) { } 88 89 multimap(const multimap& __x) 90 : _Base(__x) { } 91 92 multimap(const _Base& __x) 93 : _Base(__x) { } 94 95 #if __cplusplus >= 201103L 96 multimap(multimap&& __x) 97 noexcept(is_nothrow_copy_constructible<_Compare>::value) 98 : _Base(std::move(__x)) 99 { this->_M_swap(__x); } 100 101 multimap(initializer_list<value_type> __l, 102 const _Compare& __c = _Compare(), 103 const allocator_type& __a = allocator_type()) 104 : _Base(__l, __c, __a) { } 105 #endif 106 107 ~multimap() _GLIBCXX_NOEXCEPT { } 108 109 multimap& 110 operator=(const multimap& __x) 111 { 112 *static_cast<_Base*>(this) = __x; 113 this->_M_invalidate_all(); 114 return *this; 115 } 116 117 #if __cplusplus >= 201103L 118 multimap& 119 operator=(multimap&& __x) 120 { 121 // NB: DR 1204. 122 // NB: DR 675. 123 __glibcxx_check_self_move_assign(__x); 124 clear(); 125 swap(__x); 126 return *this; 127 } 128 129 multimap& 130 operator=(initializer_list<value_type> __l) 131 { 132 this->clear(); 133 this->insert(__l); 134 return *this; 135 } 136 #endif 137 138 using _Base::get_allocator; 139 140 // iterators: 141 iterator 142 begin() _GLIBCXX_NOEXCEPT 143 { return iterator(_Base::begin(), this); } 144 145 const_iterator 146 begin() const _GLIBCXX_NOEXCEPT 147 { return const_iterator(_Base::begin(), this); } 148 149 iterator 150 end() _GLIBCXX_NOEXCEPT 151 { return iterator(_Base::end(), this); } 152 153 const_iterator 154 end() const _GLIBCXX_NOEXCEPT 155 { return const_iterator(_Base::end(), this); } 156 157 reverse_iterator 158 rbegin() _GLIBCXX_NOEXCEPT 159 { return reverse_iterator(end()); } 160 161 const_reverse_iterator 162 rbegin() const _GLIBCXX_NOEXCEPT 163 { return const_reverse_iterator(end()); } 164 165 reverse_iterator 166 rend() _GLIBCXX_NOEXCEPT 167 { return reverse_iterator(begin()); } 168 169 const_reverse_iterator 170 rend() const _GLIBCXX_NOEXCEPT 171 { return const_reverse_iterator(begin()); } 172 173 #if __cplusplus >= 201103L 174 const_iterator 175 cbegin() const noexcept 176 { return const_iterator(_Base::begin(), this); } 177 178 const_iterator 179 cend() const noexcept 180 { return const_iterator(_Base::end(), this); } 181 182 const_reverse_iterator 183 crbegin() const noexcept 184 { return const_reverse_iterator(end()); } 185 186 const_reverse_iterator 187 crend() const noexcept 188 { return const_reverse_iterator(begin()); } 189 #endif 190 191 // capacity: 192 using _Base::empty; 193 using _Base::size; 194 using _Base::max_size; 195 196 // modifiers: 197 #if __cplusplus >= 201103L 198 template<typename... _Args> 199 iterator 200 emplace(_Args&&... __args) 201 { 202 return iterator(_Base::emplace(std::forward<_Args>(__args)...), this); 203 } 204 205 template<typename... _Args> 206 iterator 207 emplace_hint(const_iterator __pos, _Args&&... __args) 208 { 209 __glibcxx_check_insert(__pos); 210 return iterator(_Base::emplace_hint(__pos.base(), 211 std::forward<_Args>(__args)...), 212 this); 213 } 214 #endif 215 216 iterator 217 insert(const value_type& __x) 218 { return iterator(_Base::insert(__x), this); } 219 220 #if __cplusplus >= 201103L 221 template<typename _Pair, typename = typename 222 std::enable_if<std::is_constructible<value_type, 223 _Pair&&>::value>::type> 224 iterator 225 insert(_Pair&& __x) 226 { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); } 227 #endif 228 229 #if __cplusplus >= 201103L 230 void 231 insert(std::initializer_list<value_type> __list) 232 { _Base::insert(__list); } 233 #endif 234 235 iterator 236 #if __cplusplus >= 201103L 237 insert(const_iterator __position, const value_type& __x) 238 #else 239 insert(iterator __position, const value_type& __x) 240 #endif 241 { 242 __glibcxx_check_insert(__position); 243 return iterator(_Base::insert(__position.base(), __x), this); 244 } 245 246 #if __cplusplus >= 201103L 247 template<typename _Pair, typename = typename 248 std::enable_if<std::is_constructible<value_type, 249 _Pair&&>::value>::type> 250 iterator 251 insert(const_iterator __position, _Pair&& __x) 252 { 253 __glibcxx_check_insert(__position); 254 return iterator(_Base::insert(__position.base(), 255 std::forward<_Pair>(__x)), this); 256 } 257 #endif 258 259 template<typename _InputIterator> 260 void 261 insert(_InputIterator __first, _InputIterator __last) 262 { 263 __glibcxx_check_valid_range(__first, __last); 264 _Base::insert(__gnu_debug::__base(__first), 265 __gnu_debug::__base(__last)); 266 } 267 268 #if __cplusplus >= 201103L 269 iterator 270 erase(const_iterator __position) 271 { 272 __glibcxx_check_erase(__position); 273 this->_M_invalidate_if(_Equal(__position.base())); 274 return iterator(_Base::erase(__position.base()), this); 275 } 276 277 iterator 278 erase(iterator __position) 279 { return erase(const_iterator(__position)); } 280 #else 281 void 282 erase(iterator __position) 283 { 284 __glibcxx_check_erase(__position); 285 this->_M_invalidate_if(_Equal(__position.base())); 286 _Base::erase(__position.base()); 287 } 288 #endif 289 290 size_type 291 erase(const key_type& __x) 292 { 293 std::pair<_Base_iterator, _Base_iterator> __victims = 294 _Base::equal_range(__x); 295 size_type __count = 0; 296 _Base_iterator __victim = __victims.first; 297 while (__victim != __victims.second) 298 { 299 this->_M_invalidate_if(_Equal(__victim)); 300 _Base::erase(__victim++); 301 ++__count; 302 } 303 return __count; 304 } 305 306 #if __cplusplus >= 201103L 307 iterator 308 erase(const_iterator __first, const_iterator __last) 309 { 310 // _GLIBCXX_RESOLVE_LIB_DEFECTS 311 // 151. can't currently clear() empty container 312 __glibcxx_check_erase_range(__first, __last); 313 for (_Base_const_iterator __victim = __first.base(); 314 __victim != __last.base(); ++__victim) 315 { 316 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 317 _M_message(__gnu_debug::__msg_valid_range) 318 ._M_iterator(__first, "first") 319 ._M_iterator(__last, "last")); 320 this->_M_invalidate_if(_Equal(__victim)); 321 } 322 return iterator(_Base::erase(__first.base(), __last.base()), this); 323 } 324 #else 325 void 326 erase(iterator __first, iterator __last) 327 { 328 // _GLIBCXX_RESOLVE_LIB_DEFECTS 329 // 151. can't currently clear() empty container 330 __glibcxx_check_erase_range(__first, __last); 331 for (_Base_iterator __victim = __first.base(); 332 __victim != __last.base(); ++__victim) 333 { 334 _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), 335 _M_message(__gnu_debug::__msg_valid_range) 336 ._M_iterator(__first, "first") 337 ._M_iterator(__last, "last")); 338 this->_M_invalidate_if(_Equal(__victim)); 339 } 340 _Base::erase(__first.base(), __last.base()); 341 } 342 #endif 343 344 void 345 swap(multimap& __x) 346 { 347 _Base::swap(__x); 348 this->_M_swap(__x); 349 } 350 351 void 352 clear() _GLIBCXX_NOEXCEPT 353 { 354 this->_M_invalidate_all(); 355 _Base::clear(); 356 } 357 358 // observers: 359 using _Base::key_comp; 360 using _Base::value_comp; 361 362 // 23.3.1.3 multimap operations: 363 iterator 364 find(const key_type& __x) 365 { return iterator(_Base::find(__x), this); } 366 367 const_iterator 368 find(const key_type& __x) const 369 { return const_iterator(_Base::find(__x), this); } 370 371 using _Base::count; 372 373 iterator 374 lower_bound(const key_type& __x) 375 { return iterator(_Base::lower_bound(__x), this); } 376 377 const_iterator 378 lower_bound(const key_type& __x) const 379 { return const_iterator(_Base::lower_bound(__x), this); } 380 381 iterator 382 upper_bound(const key_type& __x) 383 { return iterator(_Base::upper_bound(__x), this); } 384 385 const_iterator 386 upper_bound(const key_type& __x) const 387 { return const_iterator(_Base::upper_bound(__x), this); } 388 389 std::pair<iterator,iterator> 390 equal_range(const key_type& __x) 391 { 392 std::pair<_Base_iterator, _Base_iterator> __res = 393 _Base::equal_range(__x); 394 return std::make_pair(iterator(__res.first, this), 395 iterator(__res.second, this)); 396 } 397 398 std::pair<const_iterator,const_iterator> 399 equal_range(const key_type& __x) const 400 { 401 std::pair<_Base_const_iterator, _Base_const_iterator> __res = 402 _Base::equal_range(__x); 403 return std::make_pair(const_iterator(__res.first, this), 404 const_iterator(__res.second, this)); 405 } 406 407 _Base& 408 _M_base() _GLIBCXX_NOEXCEPT { return *this; } 409 410 const _Base& 411 _M_base() const _GLIBCXX_NOEXCEPT { return *this; } 412 413 private: 414 void 415 _M_invalidate_all() 416 { 417 typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal; 418 this->_M_invalidate_if(_Not_equal(_Base::end())); 419 } 420 }; 421 422 template<typename _Key, typename _Tp, 423 typename _Compare, typename _Allocator> 424 inline bool 425 operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 426 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 427 { return __lhs._M_base() == __rhs._M_base(); } 428 429 template<typename _Key, typename _Tp, 430 typename _Compare, typename _Allocator> 431 inline bool 432 operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 433 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 434 { return __lhs._M_base() != __rhs._M_base(); } 435 436 template<typename _Key, typename _Tp, 437 typename _Compare, typename _Allocator> 438 inline bool 439 operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 440 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 441 { return __lhs._M_base() < __rhs._M_base(); } 442 443 template<typename _Key, typename _Tp, 444 typename _Compare, typename _Allocator> 445 inline bool 446 operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 447 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 448 { return __lhs._M_base() <= __rhs._M_base(); } 449 450 template<typename _Key, typename _Tp, 451 typename _Compare, typename _Allocator> 452 inline bool 453 operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 454 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 455 { return __lhs._M_base() >= __rhs._M_base(); } 456 457 template<typename _Key, typename _Tp, 458 typename _Compare, typename _Allocator> 459 inline bool 460 operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 461 const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 462 { return __lhs._M_base() > __rhs._M_base(); } 463 464 template<typename _Key, typename _Tp, 465 typename _Compare, typename _Allocator> 466 inline void 467 swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs, 468 multimap<_Key, _Tp, _Compare, _Allocator>& __rhs) 469 { __lhs.swap(__rhs); } 470 471 } // namespace __debug 472 } // namespace std 473 474 #endif 475
