libstdc++
multiset.h
Go to the documentation of this file.
00001 // Debugging multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2019 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file debug/multiset.h
00026  *  This file is a GNU debug extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_DEBUG_MULTISET_H
00030 #define _GLIBCXX_DEBUG_MULTISET_H 1
00031 
00032 #include <debug/safe_sequence.h>
00033 #include <debug/safe_container.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::multiset with safety/checking/debug instrumentation.
00042   template<typename _Key, typename _Compare = std::less<_Key>,
00043            typename _Allocator = std::allocator<_Key> >
00044     class multiset
00045     : public __gnu_debug::_Safe_container<
00046         multiset<_Key, _Compare, _Allocator>, _Allocator,
00047         __gnu_debug::_Safe_node_sequence>,
00048       public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>
00049     {
00050       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>      _Base;
00051       typedef __gnu_debug::_Safe_container<
00052         multiset, _Allocator, __gnu_debug::_Safe_node_sequence>         _Safe;
00053 
00054       typedef typename _Base::const_iterator    _Base_const_iterator;
00055       typedef typename _Base::iterator          _Base_iterator;
00056       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00057 
00058       template<typename _ItT, typename _SeqT, typename _CatT>
00059         friend class ::__gnu_debug::_Safe_iterator;
00060 
00061     public:
00062       // types:
00063       typedef _Key                                      key_type;
00064       typedef _Key                                      value_type;
00065       typedef _Compare                                  key_compare;
00066       typedef _Compare                                  value_compare;
00067       typedef _Allocator                                allocator_type;
00068       typedef typename _Base::reference                 reference;
00069       typedef typename _Base::const_reference           const_reference;
00070 
00071       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
00072                                                         iterator;
00073       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00074                                           multiset>     const_iterator;
00075 
00076       typedef typename _Base::size_type                 size_type;
00077       typedef typename _Base::difference_type           difference_type;
00078       typedef typename _Base::pointer                   pointer;
00079       typedef typename _Base::const_pointer             const_pointer;
00080       typedef std::reverse_iterator<iterator>           reverse_iterator;
00081       typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
00082 
00083       // 23.3.3.1 construct/copy/destroy:
00084 
00085 #if __cplusplus < 201103L
00086       multiset() : _Base() { }
00087 
00088       multiset(const multiset& __x)
00089       : _Base(__x) { }
00090 
00091       ~multiset() { }
00092 #else
00093       multiset() = default;
00094       multiset(const multiset&) = default;
00095       multiset(multiset&&) = default;
00096 
00097       multiset(initializer_list<value_type> __l,
00098                const _Compare& __comp = _Compare(),
00099                const allocator_type& __a = allocator_type())
00100       : _Base(__l, __comp, __a) { }
00101 
00102       explicit
00103       multiset(const allocator_type& __a)
00104       : _Base(__a) { }
00105 
00106       multiset(const multiset& __m, const allocator_type& __a)
00107       : _Base(__m, __a) { }
00108 
00109       multiset(multiset&& __m, const allocator_type& __a)
00110       noexcept( noexcept(_Base(std::move(__m._M_base()), __a)) )
00111       : _Safe(std::move(__m._M_safe()), __a),
00112         _Base(std::move(__m._M_base()), __a) { }
00113 
00114       multiset(initializer_list<value_type> __l, const allocator_type& __a)
00115         : _Base(__l, __a)
00116       { }
00117 
00118       template<typename _InputIterator>
00119         multiset(_InputIterator __first, _InputIterator __last,
00120                  const allocator_type& __a)
00121         : _Base(__gnu_debug::__base(
00122                   __glibcxx_check_valid_constructor_range(__first, __last)),
00123                 __gnu_debug::__base(__last), __a) { }
00124 
00125       ~multiset() = default;
00126 #endif
00127 
00128       explicit multiset(const _Compare& __comp,
00129                         const _Allocator& __a = _Allocator())
00130       : _Base(__comp, __a) { }
00131 
00132       template<typename _InputIterator>
00133         multiset(_InputIterator __first, _InputIterator __last,
00134                  const _Compare& __comp = _Compare(),
00135                  const _Allocator& __a = _Allocator())
00136         : _Base(__gnu_debug::__base(
00137                   __glibcxx_check_valid_constructor_range(__first, __last)),
00138                 __gnu_debug::__base(__last),
00139                 __comp, __a) { }
00140 
00141       multiset(const _Base& __x)
00142       : _Base(__x) { }
00143 
00144 #if __cplusplus < 201103L
00145       multiset&
00146       operator=(const multiset& __x)
00147       {
00148         this->_M_safe() = __x;
00149         _M_base() = __x;
00150         return *this;
00151       }
00152 #else
00153       multiset&
00154       operator=(const multiset&) = default;
00155 
00156       multiset&
00157       operator=(multiset&&) = default;
00158 
00159       multiset&
00160       operator=(initializer_list<value_type> __l)
00161       {
00162         _M_base() = __l;
00163         this->_M_invalidate_all();
00164         return *this;
00165       }
00166 #endif
00167 
00168       using _Base::get_allocator;
00169 
00170       // iterators:
00171       iterator
00172       begin() _GLIBCXX_NOEXCEPT
00173       { return iterator(_Base::begin(), this); }
00174 
00175       const_iterator
00176       begin() const _GLIBCXX_NOEXCEPT
00177       { return const_iterator(_Base::begin(), this); }
00178 
00179       iterator
00180       end() _GLIBCXX_NOEXCEPT
00181       { return iterator(_Base::end(), this); }
00182 
00183       const_iterator
00184       end() const _GLIBCXX_NOEXCEPT
00185       { return const_iterator(_Base::end(), this); }
00186 
00187       reverse_iterator
00188       rbegin() _GLIBCXX_NOEXCEPT
00189       { return reverse_iterator(end()); }
00190 
00191       const_reverse_iterator
00192       rbegin() const _GLIBCXX_NOEXCEPT
00193       { return const_reverse_iterator(end()); }
00194 
00195       reverse_iterator
00196       rend() _GLIBCXX_NOEXCEPT
00197       { return reverse_iterator(begin()); }
00198 
00199       const_reverse_iterator
00200       rend() const _GLIBCXX_NOEXCEPT
00201       { return const_reverse_iterator(begin()); }
00202 
00203 #if __cplusplus >= 201103L
00204       const_iterator
00205       cbegin() const noexcept
00206       { return const_iterator(_Base::begin(), this); }
00207 
00208       const_iterator
00209       cend() const noexcept
00210       { return const_iterator(_Base::end(), this); }
00211 
00212       const_reverse_iterator
00213       crbegin() const noexcept
00214       { return const_reverse_iterator(end()); }
00215 
00216       const_reverse_iterator
00217       crend() const noexcept
00218       { return const_reverse_iterator(begin()); }
00219 #endif
00220 
00221       // capacity:
00222       using _Base::empty;
00223       using _Base::size;
00224       using _Base::max_size;
00225 
00226       // modifiers:
00227 #if __cplusplus >= 201103L
00228       template<typename... _Args>
00229         iterator
00230         emplace(_Args&&... __args)
00231         { return { _Base::emplace(std::forward<_Args>(__args)...), this }; }
00232 
00233       template<typename... _Args>
00234         iterator
00235         emplace_hint(const_iterator __pos, _Args&&... __args)
00236         {
00237           __glibcxx_check_insert(__pos);
00238           return
00239             {
00240               _Base::emplace_hint(__pos.base(), std::forward<_Args>(__args)...),
00241               this
00242             };
00243         }
00244 #endif
00245 
00246       iterator
00247       insert(const value_type& __x)
00248       { return iterator(_Base::insert(__x), this); }
00249 
00250 #if __cplusplus >= 201103L
00251       iterator
00252       insert(value_type&& __x)
00253       { return { _Base::insert(std::move(__x)), this }; }
00254 #endif
00255 
00256       iterator
00257       insert(const_iterator __position, const value_type& __x)
00258       {
00259         __glibcxx_check_insert(__position);
00260         return iterator(_Base::insert(__position.base(), __x), this);
00261       }
00262 
00263 #if __cplusplus >= 201103L
00264       iterator
00265       insert(const_iterator __position, value_type&& __x)
00266       {
00267         __glibcxx_check_insert(__position);
00268         return { _Base::insert(__position.base(), std::move(__x)), this };
00269       }
00270 #endif
00271 
00272       template<typename _InputIterator>
00273         void
00274         insert(_InputIterator __first, _InputIterator __last)
00275         {
00276           typename __gnu_debug::_Distance_traits<_InputIterator>::__type __dist;
00277           __glibcxx_check_valid_range2(__first, __last, __dist);
00278 
00279           if (__dist.second >= __gnu_debug::__dp_sign)
00280             _Base::insert(__gnu_debug::__unsafe(__first),
00281                           __gnu_debug::__unsafe(__last));
00282           else
00283             _Base::insert(__first, __last);
00284         }
00285 
00286 #if __cplusplus >= 201103L
00287       void
00288       insert(initializer_list<value_type> __l)
00289       { _Base::insert(__l); }
00290 #endif
00291 
00292 #if __cplusplus > 201402L
00293       using node_type = typename _Base::node_type;
00294 
00295       node_type
00296       extract(const_iterator __position)
00297       {
00298         __glibcxx_check_erase(__position);
00299         this->_M_invalidate_if(_Equal(__position.base()));
00300         return _Base::extract(__position.base());
00301       }
00302 
00303       node_type
00304       extract(const key_type& __key)
00305       {
00306         const auto __position = find(__key);
00307         if (__position != end())
00308           return extract(__position);
00309         return {};
00310       }
00311 
00312       iterator
00313       insert(node_type&& __nh)
00314       { return { _Base::insert(std::move(__nh)), this }; }
00315 
00316       iterator
00317       insert(const_iterator __hint, node_type&& __nh)
00318       {
00319         __glibcxx_check_insert(__hint);
00320         return { _Base::insert(__hint.base(), std::move(__nh)), this };
00321       }
00322 
00323       using _Base::merge;
00324 #endif // C++17
00325 
00326 #if __cplusplus >= 201103L
00327       _GLIBCXX_ABI_TAG_CXX11
00328       iterator
00329       erase(const_iterator __position)
00330       {
00331         __glibcxx_check_erase(__position);
00332         this->_M_invalidate_if(_Equal(__position.base()));
00333         return { _Base::erase(__position.base()), this };
00334       }
00335 #else
00336       void
00337       erase(iterator __position)
00338       {
00339         __glibcxx_check_erase(__position);
00340         this->_M_invalidate_if(_Equal(__position.base()));
00341         _Base::erase(__position.base());
00342       }
00343 #endif
00344 
00345       size_type
00346       erase(const key_type& __x)
00347       {
00348         std::pair<_Base_iterator, _Base_iterator> __victims =
00349           _Base::equal_range(__x);
00350         size_type __count = 0;
00351         _Base_iterator __victim = __victims.first;
00352         while (__victim != __victims.second)
00353           {
00354             this->_M_invalidate_if(_Equal(__victim));
00355             _Base::erase(__victim++);
00356             ++__count;
00357           }
00358         return __count;
00359       }
00360 
00361 #if __cplusplus >= 201103L
00362       _GLIBCXX_ABI_TAG_CXX11
00363       iterator
00364       erase(const_iterator __first, const_iterator __last)
00365       {
00366         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00367         // 151. can't currently clear() empty container
00368         __glibcxx_check_erase_range(__first, __last);
00369         for (_Base_const_iterator __victim = __first.base();
00370              __victim != __last.base(); ++__victim)
00371           {
00372             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::cend(),
00373                                   _M_message(__gnu_debug::__msg_valid_range)
00374                                   ._M_iterator(__first, "first")
00375                                   ._M_iterator(__last, "last"));
00376             this->_M_invalidate_if(_Equal(__victim));
00377           }
00378 
00379         return { _Base::erase(__first.base(), __last.base()), this };
00380       }
00381 #else
00382       void
00383       erase(iterator __first, iterator __last)
00384       {
00385         // _GLIBCXX_RESOLVE_LIB_DEFECTS
00386         // 151. can't currently clear() empty container
00387         __glibcxx_check_erase_range(__first, __last);
00388         for (_Base_iterator __victim = __first.base();
00389              __victim != __last.base(); ++__victim)
00390           {
00391             _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00392                                   _M_message(__gnu_debug::__msg_valid_range)
00393                                   ._M_iterator(__first, "first")
00394                                   ._M_iterator(__last, "last"));
00395             this->_M_invalidate_if(_Equal(__victim));
00396           }
00397         _Base::erase(__first.base(), __last.base());
00398       }
00399 #endif
00400 
00401       void
00402       swap(multiset& __x)
00403       _GLIBCXX_NOEXCEPT_IF( noexcept(declval<_Base&>().swap(__x)) )
00404       {
00405         _Safe::_M_swap(__x);
00406         _Base::swap(__x);
00407       }
00408 
00409       void
00410       clear() _GLIBCXX_NOEXCEPT
00411       {
00412         this->_M_invalidate_all();
00413         _Base::clear();
00414       }
00415 
00416       // observers:
00417       using _Base::key_comp;
00418       using _Base::value_comp;
00419 
00420       // multiset operations:
00421       iterator
00422       find(const key_type& __x)
00423       { return iterator(_Base::find(__x), this); }
00424 
00425       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00426       // 214. set::find() missing const overload
00427       const_iterator
00428       find(const key_type& __x) const
00429       { return const_iterator(_Base::find(__x), this); }
00430 
00431 #if __cplusplus > 201103L
00432       template<typename _Kt,
00433                typename _Req =
00434                  typename __has_is_transparent<_Compare, _Kt>::type>
00435         iterator
00436         find(const _Kt& __x)
00437         { return { _Base::find(__x), this }; }
00438 
00439       template<typename _Kt,
00440                typename _Req =
00441                  typename __has_is_transparent<_Compare, _Kt>::type>
00442         const_iterator
00443         find(const _Kt& __x) const
00444         { return { _Base::find(__x), this }; }
00445 #endif
00446 
00447       using _Base::count;
00448 
00449       iterator
00450       lower_bound(const key_type& __x)
00451       { return iterator(_Base::lower_bound(__x), this); }
00452 
00453       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00454       // 214. set::find() missing const overload
00455       const_iterator
00456       lower_bound(const key_type& __x) const
00457       { return const_iterator(_Base::lower_bound(__x), this); }
00458 
00459 #if __cplusplus > 201103L
00460       template<typename _Kt,
00461                typename _Req =
00462                  typename __has_is_transparent<_Compare, _Kt>::type>
00463         iterator
00464         lower_bound(const _Kt& __x)
00465         { return { _Base::lower_bound(__x), this }; }
00466 
00467       template<typename _Kt,
00468                typename _Req =
00469                  typename __has_is_transparent<_Compare, _Kt>::type>
00470         const_iterator
00471         lower_bound(const _Kt& __x) const
00472         { return { _Base::lower_bound(__x), this }; }
00473 #endif
00474 
00475       iterator
00476       upper_bound(const key_type& __x)
00477       { return iterator(_Base::upper_bound(__x), this); }
00478 
00479       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00480       // 214. set::find() missing const overload
00481       const_iterator
00482       upper_bound(const key_type& __x) const
00483       { return const_iterator(_Base::upper_bound(__x), this); }
00484 
00485 #if __cplusplus > 201103L
00486       template<typename _Kt,
00487                typename _Req =
00488                  typename __has_is_transparent<_Compare, _Kt>::type>
00489         iterator
00490         upper_bound(const _Kt& __x)
00491         { return { _Base::upper_bound(__x), this }; }
00492 
00493       template<typename _Kt,
00494                typename _Req =
00495                  typename __has_is_transparent<_Compare, _Kt>::type>
00496         const_iterator
00497         upper_bound(const _Kt& __x) const
00498         { return { _Base::upper_bound(__x), this }; }
00499 #endif
00500 
00501       std::pair<iterator,iterator>
00502       equal_range(const key_type& __x)
00503       {
00504         std::pair<_Base_iterator, _Base_iterator> __res =
00505           _Base::equal_range(__x);
00506         return std::make_pair(iterator(__res.first, this),
00507                               iterator(__res.second, this));
00508       }
00509 
00510       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00511       // 214. set::find() missing const overload
00512       std::pair<const_iterator,const_iterator>
00513       equal_range(const key_type& __x) const
00514       {
00515         std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00516           _Base::equal_range(__x);
00517         return std::make_pair(const_iterator(__res.first, this),
00518                               const_iterator(__res.second, this));
00519       }
00520 
00521 #if __cplusplus > 201103L
00522       template<typename _Kt,
00523                typename _Req =
00524                  typename __has_is_transparent<_Compare, _Kt>::type>
00525         std::pair<iterator, iterator>
00526         equal_range(const _Kt& __x)
00527         {
00528           auto __res = _Base::equal_range(__x);
00529           return { { __res.first, this }, { __res.second, this } };
00530         }
00531 
00532       template<typename _Kt,
00533                typename _Req =
00534                  typename __has_is_transparent<_Compare, _Kt>::type>
00535         std::pair<const_iterator, const_iterator>
00536         equal_range(const _Kt& __x) const
00537         {
00538           auto __res = _Base::equal_range(__x);
00539           return { { __res.first, this }, { __res.second, this } };
00540         }
00541 #endif
00542 
00543       _Base&
00544       _M_base() _GLIBCXX_NOEXCEPT { return *this; }
00545 
00546       const _Base&
00547       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00548     };
00549 
00550 #if __cpp_deduction_guides >= 201606
00551 
00552   template<typename _InputIterator,
00553            typename _Compare =
00554              less<typename iterator_traits<_InputIterator>::value_type>,
00555            typename _Allocator =
00556              allocator<typename iterator_traits<_InputIterator>::value_type>,
00557            typename = _RequireInputIter<_InputIterator>,
00558            typename = _RequireNotAllocator<_Compare>,
00559            typename = _RequireAllocator<_Allocator>>
00560     multiset(_InputIterator, _InputIterator,
00561              _Compare = _Compare(), _Allocator = _Allocator())
00562     -> multiset<typename iterator_traits<_InputIterator>::value_type,
00563                 _Compare, _Allocator>;
00564 
00565   template<typename _Key,
00566            typename _Compare = less<_Key>,
00567            typename _Allocator = allocator<_Key>,
00568            typename = _RequireNotAllocator<_Compare>,
00569            typename = _RequireAllocator<_Allocator>>
00570     multiset(initializer_list<_Key>,
00571              _Compare = _Compare(), _Allocator = _Allocator())
00572     -> multiset<_Key, _Compare, _Allocator>;
00573 
00574   template<typename _InputIterator, typename _Allocator,
00575            typename = _RequireInputIter<_InputIterator>,
00576            typename = _RequireAllocator<_Allocator>>
00577     multiset(_InputIterator, _InputIterator, _Allocator)
00578     -> multiset<typename iterator_traits<_InputIterator>::value_type,
00579                 less<typename iterator_traits<_InputIterator>::value_type>,
00580                 _Allocator>;
00581 
00582   template<typename _Key, typename _Allocator,
00583            typename = _RequireAllocator<_Allocator>>
00584     multiset(initializer_list<_Key>, _Allocator)
00585     -> multiset<_Key, less<_Key>, _Allocator>;
00586 
00587 #endif
00588 
00589   template<typename _Key, typename _Compare, typename _Allocator>
00590     inline bool
00591     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00592                const multiset<_Key, _Compare, _Allocator>& __rhs)
00593     { return __lhs._M_base() == __rhs._M_base(); }
00594 
00595   template<typename _Key, typename _Compare, typename _Allocator>
00596     inline bool
00597     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00598                const multiset<_Key, _Compare, _Allocator>& __rhs)
00599     { return __lhs._M_base() != __rhs._M_base(); }
00600 
00601   template<typename _Key, typename _Compare, typename _Allocator>
00602     inline bool
00603     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00604               const multiset<_Key, _Compare, _Allocator>& __rhs)
00605     { return __lhs._M_base() < __rhs._M_base(); }
00606 
00607   template<typename _Key, typename _Compare, typename _Allocator>
00608     inline bool
00609     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00610                const multiset<_Key, _Compare, _Allocator>& __rhs)
00611     { return __lhs._M_base() <= __rhs._M_base(); }
00612 
00613   template<typename _Key, typename _Compare, typename _Allocator>
00614     inline bool
00615     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00616                const multiset<_Key, _Compare, _Allocator>& __rhs)
00617     { return __lhs._M_base() >= __rhs._M_base(); }
00618 
00619   template<typename _Key, typename _Compare, typename _Allocator>
00620     inline bool
00621     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00622               const multiset<_Key, _Compare, _Allocator>& __rhs)
00623     { return __lhs._M_base() > __rhs._M_base(); }
00624 
00625   template<typename _Key, typename _Compare, typename _Allocator>
00626     void
00627     swap(multiset<_Key, _Compare, _Allocator>& __x,
00628          multiset<_Key, _Compare, _Allocator>& __y)
00629     _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y)))
00630     { return __x.swap(__y); }
00631 
00632 } // namespace __debug
00633 } // namespace std
00634 
00635 #endif