libstdc++-v3/include/debug/multimap.h

   1 // Debugging multimap implementation -*- C++ -*-
   2
   3 // Copyright (C) 2003-2014 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
  54 #if __cplusplus >= 201103L
  55       typedef __gnu_cxx::__alloc_traits<typename
  56                                         _Base::allocator_type> _Alloc_traits;
  57 #endif
  58     public:
  59       // types:
  60       typedef _Key                                   key_type;
  61       typedef _Tp                                    mapped_type;
  62       typedef std::pair<const _Key, _Tp>             value_type;
  63       typedef _Compare                               key_compare;
  64       typedef _Allocator                             allocator_type;
  65       typedef typename _Base::reference              reference;
  66       typedef typename _Base::const_reference        const_reference;
  67
  68       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multimap>
  69                                                      iterator;
  70       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
  71                                            multimap> const_iterator;
  72
  73       typedef typename _Base::size_type              size_type;
  74       typedef typename _Base::difference_type        difference_type;
  75       typedef typename _Base::pointer                pointer;
  76       typedef typename _Base::const_pointer          const_pointer;
  77       typedef std::reverse_iterator<iterator>        reverse_iterator;
  78       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
  79
  80       // 23.3.1.1 construct/copy/destroy:
  81       explicit multimap(const _Compare& __comp = _Compare(),
  82                         const _Allocator& __a = _Allocator())
  83       : _Base(__comp, __a) { }
  84
  85       template<typename _InputIterator>
  86       multimap(_InputIterator __first, _InputIterator __last,
  87                const _Compare& __comp = _Compare(),
  88                const _Allocator& __a = _Allocator())
  89         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
  90                                                                      __last)),
  91                 __gnu_debug::__base(__last),
  92               __comp, __a) { }
  93
  94       multimap(const multimap& __x)
  95       : _Base(__x) { }
  96
  97       multimap(const _Base& __x)
  98       : _Base(__x) { }
  99
 100 #if __cplusplus >= 201103L
 101       multimap(multimap&& __x)
 102       noexcept(is_nothrow_copy_constructible<_Compare>::value)
 103       : _Base(std::move(__x))
 104       { this->_M_swap(__x); }
 105
 106       multimap(initializer_list<value_type> __l,
 107                const _Compare& __c = _Compare(),
 108                const allocator_type& __a = allocator_type())
 109       : _Base(__l, __c, __a) { }
 110
 111       explicit
 112       multimap(const allocator_type& __a)
 113       : _Base(__a) { }
 114
 115       multimap(const multimap& __m, const allocator_type& __a)
 116       : _Base(__m, __a) { }
 117
 118       multimap(multimap&& __m, const allocator_type& __a)
 119       : _Base(std::move(__m._M_base()), __a) { }
 120
 121       multimap(initializer_list<value_type> __l, const allocator_type& __a)
 122       : _Base(__l, __a)
 123       { }
 124
 125       template<typename _InputIterator>
 126         multimap(_InputIterator __first, _InputIterator __last,
 127                  const allocator_type& __a)
 128         : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
 129                                                                      __last)),
 130                 __gnu_debug::__base(__last), __a)
 131       { }
 132 #endif
 133
 134       ~multimap() _GLIBCXX_NOEXCEPT { }
 135
 136       multimap&
 137       operator=(const multimap& __x)
 138       {
 139         _M_base() = __x;
 140         this->_M_invalidate_all();
 141         return *this;
 142       }
 143
 144 #if __cplusplus >= 201103L
 145       multimap&
 146       operator=(multimap&& __x)
 147       noexcept(_Alloc_traits::_S_nothrow_move())
 148       {
 149         __glibcxx_check_self_move_assign(__x);
 150         bool xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
 151             || __x.get_allocator() == this->get_allocator();
 152         _M_base() = std::move(__x._M_base());
 153         if (xfer_memory)
 154           this->_M_swap(__x);
 155         else
 156           this->_M_invalidate_all();
 157         __x._M_invalidate_all();
 158         return *this;
 159       }
 160
 161       multimap&
 162       operator=(initializer_list<value_type> __l)
 163       {
 164         _M_base() = __l;
 165         this->_M_invalidate_all();
 166         return *this;
 167       }
 168 #endif
 169
 170       using _Base::get_allocator;
 171
 172       // iterators:
 173       iterator
 174       begin() _GLIBCXX_NOEXCEPT
 175       { return iterator(_Base::begin(), this); }
 176
 177       const_iterator
 178       begin() const _GLIBCXX_NOEXCEPT
 179       { return const_iterator(_Base::begin(), this); }
 180
 181       iterator
 182       end() _GLIBCXX_NOEXCEPT
 183       { return iterator(_Base::end(), this); }
 184
 185       const_iterator
 186       end() const _GLIBCXX_NOEXCEPT
 187       { return const_iterator(_Base::end(), this); }
 188
 189       reverse_iterator
 190       rbegin() _GLIBCXX_NOEXCEPT
 191       { return reverse_iterator(end()); }
 192
 193       const_reverse_iterator
 194       rbegin() const _GLIBCXX_NOEXCEPT
 195       { return const_reverse_iterator(end()); }
 196
 197       reverse_iterator
 198       rend() _GLIBCXX_NOEXCEPT
 199       { return reverse_iterator(begin()); }
 200
 201       const_reverse_iterator
 202       rend() const _GLIBCXX_NOEXCEPT
 203       { return const_reverse_iterator(begin()); }
 204
 205 #if __cplusplus >= 201103L
 206       const_iterator
 207       cbegin() const noexcept
 208       { return const_iterator(_Base::begin(), this); }
 209
 210       const_iterator
 211       cend() const noexcept
 212       { return const_iterator(_Base::end(), this); }
 213
 214       const_reverse_iterator
 215       crbegin() const noexcept
 216       { return const_reverse_iterator(end()); }
 217
 218       const_reverse_iterator
 219       crend() const noexcept
 220       { return const_reverse_iterator(begin()); }
 221 #endif
 222
 223       // capacity:
 224       using _Base::empty;
 225       using _Base::size;
 226       using _Base::max_size;
 227
 228       // modifiers:
 229 #if __cplusplus >= 201103L
 230       template<typename... _Args>
 231         iterator
 232         emplace(_Args&&... __args)
 233         {
 234           return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
 235         }
 236
 237       template<typename... _Args>
 238         iterator
 239         emplace_hint(const_iterator __pos, _Args&&... __args)
 240         {
 241           __glibcxx_check_insert(__pos);
 242           return iterator(_Base::emplace_hint(__pos.base(),
 243                                               std::forward<_Args>(__args)...),
 244                           this);
 245         }
 246 #endif
 247
 248       iterator
 249       insert(const value_type& __x)
 250       { return iterator(_Base::insert(__x), this); }
 251
 252 #if __cplusplus >= 201103L
 253       template<typename _Pair, typename = typename
 254                std::enable_if<std::is_constructible<value_type,
 255                                                     _Pair&&>::value>::type>
 256         iterator
 257         insert(_Pair&& __x)
 258         { return iterator(_Base::insert(std::forward<_Pair>(__x)), this); }
 259 #endif
 260
 261 #if __cplusplus >= 201103L
 262       void
 263       insert(std::initializer_list<value_type> __list)
 264       { _Base::insert(__list); }
 265 #endif
 266
 267       iterator
 268 #if __cplusplus >= 201103L
 269       insert(const_iterator __position, const value_type& __x)
 270 #else
 271       insert(iterator __position, const value_type& __x)
 272 #endif
 273       {
 274         __glibcxx_check_insert(__position);
 275         return iterator(_Base::insert(__position.base(), __x), this);
 276       }
 277
 278 #if __cplusplus >= 201103L
 279       template<typename _Pair, typename = typename
 280                std::enable_if<std::is_constructible<value_type,
 281                                                     _Pair&&>::value>::type>
 282         iterator
 283         insert(const_iterator __position, _Pair&& __x)
 284         {
 285           __glibcxx_check_insert(__position);
 286           return iterator(_Base::insert(__position.base(),
 287                                         std::forward<_Pair>(__x)), this);
 288         }
 289 #endif
 290
 291       template<typename _InputIterator>
 292         void
 293         insert(_InputIterator __first, _InputIterator __last)
 294         {
 295           __glibcxx_check_valid_range(__first, __last);
 296           _Base::insert(__gnu_debug::__base(__first),
 297                         __gnu_debug::__base(__last));
 298         }
 299
 300 #if __cplusplus >= 201103L
 301       iterator
 302       erase(const_iterator __position)
 303       {
 304         __glibcxx_check_erase(__position);
 305         this->_M_invalidate_if(_Equal(__position.base()));
 306         return iterator(_Base::erase(__position.base()), this);
 307       }
 308
 309       iterator
 310       erase(iterator __position)
 311       { return erase(const_iterator(__position)); }
 312 #else
 313       void
 314       erase(iterator __position)
 315       {
 316         __glibcxx_check_erase(__position);
 317         this->_M_invalidate_if(_Equal(__position.base()));
 318         _Base::erase(__position.base());
 319       }
 320 #endif
 321
 322       size_type
 323       erase(const key_type& __x)
 324       {
 325         std::pair<_Base_iterator, _Base_iterator> __victims =
 326           _Base::equal_range(__x);
 327         size_type __count = 0;
 328         _Base_iterator __victim = __victims.first;
 329         while (__victim !=  __victims.second)
 330           {
 331             this->_M_invalidate_if(_Equal(__victim));
 332             _Base::erase(__victim++);
 333             ++__count;
 334           }
 335         return __count;
 336       }
 337
 338 #if __cplusplus >= 201103L
 339       iterator
 340       erase(const_iterator __first, const_iterator __last)
 341       {
 342         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 343         // 151. can't currently clear() empty container
 344         __glibcxx_check_erase_range(__first, __last);
 345         for (_Base_const_iterator __victim = __first.base();
 346              __victim != __last.base(); ++__victim)
 347           {
 348             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 349                                   _M_message(__gnu_debug::__msg_valid_range)
 350                                   ._M_iterator(__first, "first")
 351                                   ._M_iterator(__last, "last"));
 352             this->_M_invalidate_if(_Equal(__victim));
 353           }
 354         return iterator(_Base::erase(__first.base(), __last.base()), this);
 355       }
 356 #else
 357       void
 358       erase(iterator __first, iterator __last)
 359       {
 360         // _GLIBCXX_RESOLVE_LIB_DEFECTS
 361         // 151. can't currently clear() empty container
 362         __glibcxx_check_erase_range(__first, __last);
 363         for (_Base_iterator __victim = __first.base();
 364              __victim != __last.base(); ++__victim)
 365           {
 366             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
 367                                   _M_message(__gnu_debug::__msg_valid_range)
 368                                   ._M_iterator(__first, "first")
 369                                   ._M_iterator(__last, "last"));
 370             this->_M_invalidate_if(_Equal(__victim));
 371           }
 372         _Base::erase(__first.base(), __last.base());
 373       }
 374 #endif
 375
 376       void
 377       swap(multimap& __x)
 378 #if __cplusplus >= 201103L
 379       noexcept(_Alloc_traits::_S_nothrow_swap())
 380 #endif
 381       {
 382 #if __cplusplus >= 201103L
 383         if (!_Alloc_traits::_S_propagate_on_swap())
 384           __glibcxx_check_equal_allocs(__x);
 385 #endif
 386         _Base::swap(__x);
 387         this->_M_swap(__x);
 388       }
 389
 390       void
 391       clear() _GLIBCXX_NOEXCEPT
 392       {
 393         this->_M_invalidate_all();
 394         _Base::clear();
 395       }
 396
 397       // observers:
 398       using _Base::key_comp;
 399       using _Base::value_comp;
 400
 401       // 23.3.1.3 multimap operations:
 402       iterator
 403       find(const key_type& __x)
 404       { return iterator(_Base::find(__x), this); }
 405
 406       const_iterator
 407       find(const key_type& __x) const
 408       { return const_iterator(_Base::find(__x), this); }
 409
 410       using _Base::count;
 411
 412       iterator
 413       lower_bound(const key_type& __x)
 414       { return iterator(_Base::lower_bound(__x), this); }
 415
 416       const_iterator
 417       lower_bound(const key_type& __x) const
 418       { return const_iterator(_Base::lower_bound(__x), this); }
 419
 420       iterator
 421       upper_bound(const key_type& __x)
 422       { return iterator(_Base::upper_bound(__x), this); }
 423
 424       const_iterator
 425       upper_bound(const key_type& __x) const
 426       { return const_iterator(_Base::upper_bound(__x), this); }
 427
 428       std::pair<iterator,iterator>
 429       equal_range(const key_type& __x)
 430       {
 431         std::pair<_Base_iterator, _Base_iterator> __res =
 432         _Base::equal_range(__x);
 433         return std::make_pair(iterator(__res.first, this),
 434                               iterator(__res.second, this));
 435       }
 436
 437       std::pair<const_iterator,const_iterator>
 438       equal_range(const key_type& __x) const
 439       {
 440         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
 441           _Base::equal_range(__x);
 442         return std::make_pair(const_iterator(__res.first, this),
 443                               const_iterator(__res.second, this));
 444       }
 445
 446       _Base&
 447       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
 448
 449       const _Base&
 450       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
 451
 452     private:
 453       void
 454       _M_invalidate_all()
 455       {
 456         typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
 457         this->_M_invalidate_if(_Not_equal(_Base::end()));
 458       }
 459     };
 460
 461   template<typename _Key, typename _Tp,
 462            typename _Compare, typename _Allocator>
 463     inline bool
 464     operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 465                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 466     { return __lhs._M_base() == __rhs._M_base(); }
 467
 468   template<typename _Key, typename _Tp,
 469            typename _Compare, typename _Allocator>
 470     inline bool
 471     operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 472                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 473     { return __lhs._M_base() != __rhs._M_base(); }
 474
 475   template<typename _Key, typename _Tp,
 476            typename _Compare, typename _Allocator>
 477     inline bool
 478     operator<(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 479               const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 480     { return __lhs._M_base() < __rhs._M_base(); }
 481
 482   template<typename _Key, typename _Tp,
 483            typename _Compare, typename _Allocator>
 484     inline bool
 485     operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 486                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 487     { return __lhs._M_base() <= __rhs._M_base(); }
 488
 489   template<typename _Key, typename _Tp,
 490            typename _Compare, typename _Allocator>
 491     inline bool
 492     operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 493                const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 494     { return __lhs._M_base() >= __rhs._M_base(); }
 495
 496   template<typename _Key, typename _Tp,
 497            typename _Compare, typename _Allocator>
 498     inline bool
 499     operator>(const multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 500               const multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 501     { return __lhs._M_base() > __rhs._M_base(); }
 502
 503   template<typename _Key, typename _Tp,
 504            typename _Compare, typename _Allocator>
 505     inline void
 506     swap(multimap<_Key, _Tp, _Compare, _Allocator>& __lhs,
 507          multimap<_Key, _Tp, _Compare, _Allocator>& __rhs)
 508     { __lhs.swap(__rhs); }
 509
 510 } // namespace __debug
 511 } // namespace std
 512
 513 #endif