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