libstdc++
multiset.h
Go to the documentation of this file.
00001 // Debugging multiset implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2003-2014 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_iterator.h>
00034 #include <utility>
00035 
00036 namespace std _GLIBCXX_VISIBILITY(default)
00037 {
00038 namespace __debug
00039 {
00040   /// Class std::multiset with safety/checking/debug instrumentation.
00041   template<typename _Key, typename _Compare = std::less<_Key>,
00042        typename _Allocator = std::allocator<_Key> >
00043     class multiset
00044     : public _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator>,
00045       public __gnu_debug::_Safe_sequence<multiset<_Key, _Compare, _Allocator> >
00046     {
00047       typedef _GLIBCXX_STD_C::multiset<_Key, _Compare, _Allocator> _Base;
00048 
00049       typedef typename _Base::const_iterator _Base_const_iterator;
00050       typedef typename _Base::iterator _Base_iterator;
00051       typedef __gnu_debug::_Equal_to<_Base_const_iterator> _Equal;
00052 
00053 #if __cplusplus >= 201103L
00054       typedef __gnu_cxx::__alloc_traits<typename
00055                     _Base::allocator_type> _Alloc_traits;
00056 #endif
00057     public:
00058       // types:
00059       typedef _Key                   key_type;
00060       typedef _Key                   value_type;
00061       typedef _Compare                   key_compare;
00062       typedef _Compare                   value_compare;
00063       typedef _Allocator                 allocator_type;
00064       typedef typename _Base::reference              reference;
00065       typedef typename _Base::const_reference        const_reference;
00066 
00067       typedef __gnu_debug::_Safe_iterator<_Base_iterator, multiset>
00068       iterator;
00069       typedef __gnu_debug::_Safe_iterator<_Base_const_iterator,
00070                       multiset> const_iterator;
00071 
00072       typedef typename _Base::size_type              size_type;
00073       typedef typename _Base::difference_type        difference_type;
00074       typedef typename _Base::pointer                pointer;
00075       typedef typename _Base::const_pointer          const_pointer;
00076       typedef std::reverse_iterator<iterator>        reverse_iterator;
00077       typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
00078 
00079       // 23.3.3.1 construct/copy/destroy:
00080 
00081       multiset() : _Base() { }
00082 
00083       explicit multiset(const _Compare& __comp,
00084             const _Allocator& __a = _Allocator())
00085       : _Base(__comp, __a) { }
00086 
00087       template<typename _InputIterator>
00088         multiset(_InputIterator __first, _InputIterator __last,
00089          const _Compare& __comp = _Compare(),
00090          const _Allocator& __a = _Allocator())
00091     : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00092                                      __last)),
00093         __gnu_debug::__base(__last),
00094         __comp, __a) { }
00095 
00096       multiset(const multiset& __x)
00097       : _Base(__x) { }
00098 
00099       multiset(const _Base& __x)
00100       : _Base(__x) { }
00101 
00102 #if __cplusplus >= 201103L
00103       multiset(multiset&& __x)
00104       noexcept(is_nothrow_copy_constructible<_Compare>::value)
00105       : _Base(std::move(__x))
00106       { this->_M_swap(__x); }
00107 
00108       multiset(initializer_list<value_type> __l,
00109            const _Compare& __comp = _Compare(),
00110            const allocator_type& __a = allocator_type())
00111       : _Base(__l, __comp, __a) { }
00112 
00113       explicit
00114       multiset(const allocator_type& __a)
00115       : _Base(__a) { }
00116 
00117       multiset(const multiset& __m, const allocator_type& __a)
00118       : _Base(__m, __a) { }
00119 
00120       multiset(multiset&& __m, const allocator_type& __a)
00121       : _Base(std::move(__m._M_base()), __a) { }
00122 
00123       multiset(initializer_list<value_type> __l, const allocator_type& __a)
00124     : _Base(__l, __a)
00125       { }
00126 
00127       template<typename _InputIterator>
00128         multiset(_InputIterator __first, _InputIterator __last,
00129          const allocator_type& __a)
00130       : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first,
00131                                        __last)),
00132           __gnu_debug::__base(__last), __a)
00133         { }
00134 #endif
00135 
00136       ~multiset() _GLIBCXX_NOEXCEPT { }
00137 
00138       multiset&
00139       operator=(const multiset& __x)
00140       {
00141     _M_base() = __x;
00142     this->_M_invalidate_all();
00143     return *this;
00144       }
00145 
00146 #if __cplusplus >= 201103L
00147       multiset&
00148       operator=(multiset&& __x)
00149       noexcept(_Alloc_traits::_S_nothrow_move())
00150       {
00151     __glibcxx_check_self_move_assign(__x);
00152     bool __xfer_memory = _Alloc_traits::_S_propagate_on_move_assign()
00153         || __x.get_allocator() == this->get_allocator();
00154     _M_base() = std::move(__x._M_base());
00155     if (__xfer_memory)
00156       this->_M_swap(__x);
00157     else
00158       this->_M_invalidate_all();
00159     __x._M_invalidate_all();
00160     return *this;
00161       }
00162 
00163       multiset&
00164       operator=(initializer_list<value_type> __l)
00165       {
00166     _M_base() = __l;
00167     this->_M_invalidate_all();
00168     return *this;
00169       }
00170 #endif
00171 
00172       using _Base::get_allocator;
00173 
00174       // iterators:
00175       iterator
00176       begin() _GLIBCXX_NOEXCEPT
00177       { return iterator(_Base::begin(), this); }
00178 
00179       const_iterator
00180       begin() const _GLIBCXX_NOEXCEPT
00181       { return const_iterator(_Base::begin(), this); }
00182 
00183       iterator
00184       end() _GLIBCXX_NOEXCEPT
00185       { return iterator(_Base::end(), this); }
00186 
00187       const_iterator
00188       end() const _GLIBCXX_NOEXCEPT
00189       { return const_iterator(_Base::end(), this); }
00190 
00191       reverse_iterator
00192       rbegin() _GLIBCXX_NOEXCEPT
00193       { return reverse_iterator(end()); }
00194 
00195       const_reverse_iterator
00196       rbegin() const _GLIBCXX_NOEXCEPT
00197       { return const_reverse_iterator(end()); }
00198 
00199       reverse_iterator
00200       rend() _GLIBCXX_NOEXCEPT
00201       { return reverse_iterator(begin()); }
00202 
00203       const_reverse_iterator
00204       rend() const _GLIBCXX_NOEXCEPT
00205       { return const_reverse_iterator(begin()); }
00206 
00207 #if __cplusplus >= 201103L
00208       const_iterator
00209       cbegin() const noexcept
00210       { return const_iterator(_Base::begin(), this); }
00211 
00212       const_iterator
00213       cend() const noexcept
00214       { return const_iterator(_Base::end(), this); }
00215 
00216       const_reverse_iterator
00217       crbegin() const noexcept
00218       { return const_reverse_iterator(end()); }
00219 
00220       const_reverse_iterator
00221       crend() const noexcept
00222       { return const_reverse_iterator(begin()); }
00223 #endif
00224 
00225       // capacity:
00226       using _Base::empty;
00227       using _Base::size;
00228       using _Base::max_size;
00229 
00230       // modifiers:
00231 #if __cplusplus >= 201103L
00232       template<typename... _Args>
00233     iterator
00234     emplace(_Args&&... __args)
00235     {
00236       return iterator(_Base::emplace(std::forward<_Args>(__args)...), this);
00237     }
00238 
00239       template<typename... _Args>
00240     iterator
00241     emplace_hint(const_iterator __pos, _Args&&... __args)
00242     {
00243       __glibcxx_check_insert(__pos);
00244       return iterator(_Base::emplace_hint(__pos.base(),
00245                           std::forward<_Args>(__args)...),
00246               this);
00247     }
00248 #endif
00249 
00250       iterator
00251       insert(const value_type& __x)
00252       { return iterator(_Base::insert(__x), this); }
00253 
00254 #if __cplusplus >= 201103L
00255       iterator
00256       insert(value_type&& __x)
00257       { return iterator(_Base::insert(std::move(__x)), this); }
00258 #endif
00259 
00260       iterator
00261       insert(const_iterator __position, const value_type& __x)
00262       {
00263     __glibcxx_check_insert(__position);
00264     return iterator(_Base::insert(__position.base(), __x), this);
00265       }
00266 
00267 #if __cplusplus >= 201103L
00268       iterator
00269       insert(const_iterator __position, value_type&& __x)
00270       {
00271     __glibcxx_check_insert(__position);
00272     return iterator(_Base::insert(__position.base(), std::move(__x)),
00273             this);
00274       }
00275 #endif
00276 
00277       template<typename _InputIterator>
00278     void
00279     insert(_InputIterator __first, _InputIterator __last)
00280     {
00281       __glibcxx_check_valid_range(__first, __last);
00282       _Base::insert(__gnu_debug::__base(__first),
00283             __gnu_debug::__base(__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 >= 201103L
00293       iterator
00294       erase(const_iterator __position)
00295       {
00296     __glibcxx_check_erase(__position);
00297     this->_M_invalidate_if(_Equal(__position.base()));
00298     return iterator(_Base::erase(__position.base()), this);
00299       }
00300 #else
00301       void
00302       erase(iterator __position)
00303       {
00304     __glibcxx_check_erase(__position);
00305     this->_M_invalidate_if(_Equal(__position.base()));
00306     _Base::erase(__position.base());
00307       }
00308 #endif
00309 
00310       size_type
00311       erase(const key_type& __x)
00312       {
00313     std::pair<_Base_iterator, _Base_iterator> __victims =
00314       _Base::equal_range(__x);
00315     size_type __count = 0;
00316     _Base_iterator __victim = __victims.first;
00317     while (__victim != __victims.second)
00318       {
00319         this->_M_invalidate_if(_Equal(__victim));
00320         _Base::erase(__victim++);
00321         ++__count;
00322       }
00323     return __count;
00324       }
00325 
00326 #if __cplusplus >= 201103L
00327       iterator
00328       erase(const_iterator __first, const_iterator __last)
00329       {
00330     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00331     // 151. can't currently clear() empty container
00332     __glibcxx_check_erase_range(__first, __last);
00333     for (_Base_const_iterator __victim = __first.base();
00334          __victim != __last.base(); ++__victim)
00335       {
00336         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00337                   _M_message(__gnu_debug::__msg_valid_range)
00338                   ._M_iterator(__first, "first")
00339                   ._M_iterator(__last, "last"));
00340         this->_M_invalidate_if(_Equal(__victim));
00341       }
00342     return iterator(_Base::erase(__first.base(), __last.base()), this);
00343       }
00344 #else
00345       void
00346       erase(iterator __first, iterator __last)
00347       {
00348     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00349     // 151. can't currently clear() empty container
00350     __glibcxx_check_erase_range(__first, __last);
00351     for (_Base_iterator __victim = __first.base();
00352          __victim != __last.base(); ++__victim)
00353       {
00354         _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(),
00355                   _M_message(__gnu_debug::__msg_valid_range)
00356                   ._M_iterator(__first, "first")
00357                   ._M_iterator(__last, "last"));
00358         this->_M_invalidate_if(_Equal(__victim));
00359       }
00360     _Base::erase(__first.base(), __last.base());
00361       }
00362 #endif
00363 
00364       void
00365       swap(multiset& __x)
00366 #if __cplusplus >= 201103L
00367       noexcept(_Alloc_traits::_S_nothrow_swap())
00368 #endif
00369       {
00370 #if __cplusplus >= 201103L
00371     if (!_Alloc_traits::_S_propagate_on_swap())
00372       __glibcxx_check_equal_allocs(__x);
00373 #endif
00374     _Base::swap(__x);
00375     this->_M_swap(__x);
00376       }
00377 
00378       void
00379       clear() _GLIBCXX_NOEXCEPT
00380       {
00381     this->_M_invalidate_all();
00382     _Base::clear();
00383       }
00384 
00385       // observers:
00386       using _Base::key_comp;
00387       using _Base::value_comp;
00388 
00389       // multiset operations:
00390       iterator
00391       find(const key_type& __x)
00392       { return iterator(_Base::find(__x), this); }
00393 
00394       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00395       // 214. set::find() missing const overload
00396       const_iterator
00397       find(const key_type& __x) const
00398       { return const_iterator(_Base::find(__x), this); }
00399 
00400       using _Base::count;
00401 
00402       iterator
00403       lower_bound(const key_type& __x)
00404       { return iterator(_Base::lower_bound(__x), this); }
00405 
00406       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00407       // 214. set::find() missing const overload
00408       const_iterator
00409       lower_bound(const key_type& __x) const
00410       { return const_iterator(_Base::lower_bound(__x), this); }
00411 
00412       iterator
00413       upper_bound(const key_type& __x)
00414       { return iterator(_Base::upper_bound(__x), this); }
00415 
00416       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00417       // 214. set::find() missing const overload
00418       const_iterator
00419       upper_bound(const key_type& __x) const
00420       { return const_iterator(_Base::upper_bound(__x), this); }
00421 
00422       std::pair<iterator,iterator>
00423       equal_range(const key_type& __x)
00424       {
00425     std::pair<_Base_iterator, _Base_iterator> __res =
00426       _Base::equal_range(__x);
00427     return std::make_pair(iterator(__res.first, this),
00428                   iterator(__res.second, this));
00429       }
00430 
00431       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00432       // 214. set::find() missing const overload
00433       std::pair<const_iterator,const_iterator>
00434       equal_range(const key_type& __x) const
00435       {
00436     std::pair<_Base_const_iterator, _Base_const_iterator> __res =
00437       _Base::equal_range(__x);
00438     return std::make_pair(const_iterator(__res.first, this),
00439                   const_iterator(__res.second, this));
00440       }
00441 
00442       _Base&
00443       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00444 
00445       const _Base&
00446       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00447 
00448     private:
00449       void
00450       _M_invalidate_all()
00451       {
00452     typedef __gnu_debug::_Not_equal_to<_Base_const_iterator> _Not_equal;
00453     this->_M_invalidate_if(_Not_equal(_Base::end()));
00454       }
00455     };
00456 
00457   template<typename _Key, typename _Compare, typename _Allocator>
00458     inline bool
00459     operator==(const multiset<_Key, _Compare, _Allocator>& __lhs,
00460            const multiset<_Key, _Compare, _Allocator>& __rhs)
00461     { return __lhs._M_base() == __rhs._M_base(); }
00462 
00463   template<typename _Key, typename _Compare, typename _Allocator>
00464     inline bool
00465     operator!=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00466            const multiset<_Key, _Compare, _Allocator>& __rhs)
00467     { return __lhs._M_base() != __rhs._M_base(); }
00468 
00469   template<typename _Key, typename _Compare, typename _Allocator>
00470     inline bool
00471     operator<(const multiset<_Key, _Compare, _Allocator>& __lhs,
00472           const multiset<_Key, _Compare, _Allocator>& __rhs)
00473     { return __lhs._M_base() < __rhs._M_base(); }
00474 
00475   template<typename _Key, typename _Compare, typename _Allocator>
00476     inline bool
00477     operator<=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00478            const multiset<_Key, _Compare, _Allocator>& __rhs)
00479     { return __lhs._M_base() <= __rhs._M_base(); }
00480 
00481   template<typename _Key, typename _Compare, typename _Allocator>
00482     inline bool
00483     operator>=(const multiset<_Key, _Compare, _Allocator>& __lhs,
00484            const multiset<_Key, _Compare, _Allocator>& __rhs)
00485     { return __lhs._M_base() >= __rhs._M_base(); }
00486 
00487   template<typename _Key, typename _Compare, typename _Allocator>
00488     inline bool
00489     operator>(const multiset<_Key, _Compare, _Allocator>& __lhs,
00490           const multiset<_Key, _Compare, _Allocator>& __rhs)
00491     { return __lhs._M_base() > __rhs._M_base(); }
00492 
00493   template<typename _Key, typename _Compare, typename _Allocator>
00494     void
00495     swap(multiset<_Key, _Compare, _Allocator>& __x,
00496      multiset<_Key, _Compare, _Allocator>& __y)
00497     { return __x.swap(__y); }
00498 
00499 } // namespace __debug
00500 } // namespace std
00501 
00502 #endif