libstdc++
list
Go to the documentation of this file.
00001 // Profiling list implementation -*- C++ -*-
00002 
00003 // Copyright (C) 2009-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 profile/list
00026  *  This file is a GNU profile extension to the Standard C++ Library.
00027  */
00028 
00029 #ifndef _GLIBCXX_PROFILE_LIST
00030 #define _GLIBCXX_PROFILE_LIST 1
00031 
00032 #include <list>
00033 #include <profile/base.h> 
00034 #include <profile/iterator_tracker.h> 
00035 
00036 namespace std _GLIBCXX_VISIBILITY(default)
00037 {
00038 namespace __profile
00039 {
00040   /** @brief List wrapper with performance instrumentation.  */
00041 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
00042     class list
00043     : public _GLIBCXX_STD_C::list<_Tp, _Allocator>
00044     {
00045       typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
00046 
00047     public:
00048       typedef typename _Base::reference             reference;
00049       typedef typename _Base::const_reference       const_reference;
00050 
00051       typedef __iterator_tracker<typename _Base::iterator, list>        
00052                                     iterator;
00053       typedef __iterator_tracker<typename _Base::const_iterator, list>  
00054                                                     const_iterator;
00055 
00056       typedef typename _Base::size_type             size_type;
00057       typedef typename _Base::difference_type       difference_type;
00058 
00059       typedef _Tp                   value_type;
00060       typedef _Allocator                allocator_type;
00061       typedef typename _Base::pointer               pointer;
00062       typedef typename _Base::const_pointer         const_pointer;
00063       typedef std::reverse_iterator<iterator>       reverse_iterator;
00064       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00065 
00066       // 23.2.2.1 construct/copy/destroy:
00067 
00068       list() _GLIBCXX_NOEXCEPT
00069       : _Base()
00070       {
00071         __profcxx_list_construct(this);     // list2slist
00072         __profcxx_list_construct2(this);    // list2vector
00073       }
00074 
00075       explicit
00076       list(const _Allocator& __a) _GLIBCXX_NOEXCEPT
00077       : _Base(__a) 
00078       {
00079         __profcxx_list_construct(this);     // list2slist
00080         __profcxx_list_construct2(this);    // list2vector
00081       }
00082 
00083 #if __cplusplus >= 201103L
00084       explicit
00085       list(size_type __n)
00086       : _Base(__n) 
00087       {
00088         __profcxx_list_construct(this); 
00089         __profcxx_list_construct2(this); 
00090       }
00091 
00092       list(size_type __n, const _Tp& __value,
00093        const _Allocator& __a = _Allocator())
00094       : _Base(__n, __value, __a) 
00095       {
00096         __profcxx_list_construct(this); 
00097         __profcxx_list_construct2(this); 
00098       }
00099 #else
00100       explicit
00101       list(size_type __n, const _Tp& __value = _Tp(),
00102        const _Allocator& __a = _Allocator())
00103       : _Base(__n, __value, __a) 
00104       {
00105         __profcxx_list_construct(this); 
00106         __profcxx_list_construct2(this); 
00107       }
00108 #endif
00109 
00110 #if __cplusplus >= 201103L
00111       template<typename _InputIterator,
00112            typename = std::_RequireInputIter<_InputIterator>>
00113 #else
00114       template<class _InputIterator>
00115 #endif
00116       list(_InputIterator __first, _InputIterator __last,
00117        const _Allocator& __a = _Allocator())
00118       : _Base(__first, __last, __a)
00119       {
00120         __profcxx_list_construct(this); 
00121         __profcxx_list_construct2(this); 
00122       }
00123 
00124       list(const list& __x)
00125       : _Base(__x) 
00126       {
00127         __profcxx_list_construct(this); 
00128         __profcxx_list_construct2(this); 
00129       }
00130 
00131       list(const _Base& __x)
00132       : _Base(__x) 
00133       {
00134         __profcxx_list_construct(this); 
00135         __profcxx_list_construct2(this); 
00136       }
00137 
00138 #if __cplusplus >= 201103L
00139       list(list&& __x) noexcept
00140       : _Base(std::move(__x))
00141       {
00142         __profcxx_list_construct(this); 
00143         __profcxx_list_construct2(this); 
00144       }
00145 
00146       list(initializer_list<value_type> __l,
00147            const allocator_type& __a = allocator_type())
00148         : _Base(__l, __a) { }
00149 #endif
00150 
00151       ~list() _GLIBCXX_NOEXCEPT
00152       { 
00153         __profcxx_list_destruct(this); 
00154         __profcxx_list_destruct2(this); 
00155       }
00156 
00157       list&
00158       operator=(const list& __x)
00159       {
00160     static_cast<_Base&>(*this) = __x;
00161     return *this;
00162       }
00163 
00164 #if __cplusplus >= 201103L
00165       list&
00166       operator=(list&& __x)
00167       {
00168     // NB: DR 1204.
00169     // NB: DR 675.
00170     this->clear();
00171     this->swap(__x);
00172     return *this;
00173       }
00174 
00175       list&
00176       operator=(initializer_list<value_type> __l)
00177       {
00178     static_cast<_Base&>(*this) = __l;
00179     return *this;
00180       }
00181 
00182       void
00183       assign(initializer_list<value_type> __l)
00184       { _Base::assign(__l); }
00185 #endif
00186 
00187 #if __cplusplus >= 201103L
00188       template<typename _InputIterator,
00189            typename = std::_RequireInputIter<_InputIterator>>
00190 #else
00191       template<class _InputIterator>
00192 #endif
00193         void
00194         assign(_InputIterator __first, _InputIterator __last)
00195         { _Base::assign(__first, __last); }
00196 
00197       void
00198       assign(size_type __n, const _Tp& __t)
00199       { _Base::assign(__n, __t); }
00200 
00201       using _Base::get_allocator;
00202 
00203       // iterators:
00204       iterator
00205       begin() _GLIBCXX_NOEXCEPT
00206       { return iterator(_Base::begin(), this); }
00207 
00208       const_iterator
00209       begin() const _GLIBCXX_NOEXCEPT
00210       { return const_iterator(_Base::begin(), this); }
00211 
00212       iterator
00213       end() _GLIBCXX_NOEXCEPT
00214       {
00215         __profcxx_list_rewind(this);
00216         return iterator(_Base::end(), this);
00217       }
00218 
00219       const_iterator
00220       end() const _GLIBCXX_NOEXCEPT
00221       {
00222         __profcxx_list_rewind(this);
00223         return const_iterator(_Base::end(), this);
00224       }
00225 
00226       reverse_iterator
00227       rbegin() _GLIBCXX_NOEXCEPT
00228       {
00229         __profcxx_list_rewind(this);
00230         return reverse_iterator(end());
00231       }
00232 
00233       const_reverse_iterator
00234       rbegin() const _GLIBCXX_NOEXCEPT
00235       { 
00236         __profcxx_list_rewind(this);
00237         return const_reverse_iterator(end());
00238       }
00239 
00240       reverse_iterator
00241       rend() _GLIBCXX_NOEXCEPT
00242       { return reverse_iterator(begin()); }
00243 
00244       const_reverse_iterator
00245       rend() const _GLIBCXX_NOEXCEPT
00246       { return const_reverse_iterator(begin()); }
00247 
00248 #if __cplusplus >= 201103L
00249       const_iterator
00250       cbegin() const noexcept
00251       { return const_iterator(_Base::begin(), this); }
00252 
00253       const_iterator
00254       cend() const noexcept
00255       { return const_iterator(_Base::end(), this); }
00256 
00257       const_reverse_iterator
00258       crbegin() const noexcept
00259       { return const_reverse_iterator(end()); }
00260 
00261       const_reverse_iterator
00262       crend() const noexcept
00263       { return const_reverse_iterator(begin()); }
00264 #endif
00265 
00266       // 23.2.2.2 capacity:
00267       using _Base::empty;
00268       using _Base::size;
00269       using _Base::max_size;
00270 
00271 #if __cplusplus >= 201103L
00272       void
00273       resize(size_type __sz)
00274       { _Base::resize(__sz); }
00275 
00276       void
00277       resize(size_type __sz, const _Tp& __c)
00278       { _Base::resize(__sz, __c); }
00279 #else
00280       void
00281       resize(size_type __sz, _Tp __c = _Tp())
00282       { _Base::resize(__sz, __c); }
00283 #endif
00284 
00285       // element access:
00286       reference
00287       front() _GLIBCXX_NOEXCEPT
00288       { return _Base::front(); }
00289 
00290       const_reference
00291       front() const _GLIBCXX_NOEXCEPT
00292       { return _Base::front(); }
00293 
00294       reference
00295       back() _GLIBCXX_NOEXCEPT
00296       {
00297         __profcxx_list_rewind(this);
00298     return _Base::back();
00299       }
00300 
00301       const_reference
00302       back() const _GLIBCXX_NOEXCEPT
00303       {
00304         __profcxx_list_rewind(this);
00305     return _Base::back();
00306       }
00307 
00308       // 23.2.2.3 modifiers:
00309       void
00310       push_front(const value_type& __x)
00311       {
00312         __profcxx_list_invalid_operator(this);
00313         __profcxx_list_operation(this);
00314         _Base::push_front(__x);
00315       }
00316 
00317 #if __cplusplus >= 201103L
00318       using _Base::emplace_front;
00319 #endif
00320 
00321       void
00322       pop_front() _GLIBCXX_NOEXCEPT
00323       {
00324         __profcxx_list_operation(this);
00325     _Base::pop_front();
00326       }
00327 
00328       using _Base::push_back;
00329 
00330 #if __cplusplus >= 201103L
00331       using _Base::emplace_back;
00332 #endif
00333 
00334       void
00335       pop_back() _GLIBCXX_NOEXCEPT
00336       {
00337     iterator __victim = end();
00338     --__victim;
00339     _Base::pop_back();
00340         __profcxx_list_rewind(this);
00341       }
00342 
00343 #if __cplusplus >= 201103L
00344       template<typename... _Args>
00345         iterator
00346         emplace(const_iterator __position, _Args&&... __args)
00347     {
00348       return iterator(_Base::emplace(__position.base(),
00349                                          std::forward<_Args>(__args)...),
00350               this);
00351     }
00352 #endif
00353 
00354       iterator
00355 #if __cplusplus >= 201103L
00356       insert(const_iterator __position, const _Tp& __x)
00357 #else
00358       insert(iterator __position, const _Tp& __x)
00359 #endif
00360       {
00361         _M_profile_insert(this, __position, size());
00362         return iterator(_Base::insert(__position.base(), __x), this);
00363       }
00364 
00365 #if __cplusplus >= 201103L
00366       iterator
00367       insert(const_iterator __position, _Tp&& __x)
00368       {
00369         _M_profile_insert(this, __position, size());
00370         return iterator(_Base::emplace(__position.base(), std::move(__x)),
00371                         this); 
00372       }
00373 
00374       iterator
00375       insert(const_iterator __position, initializer_list<value_type> __l)
00376       {
00377         _M_profile_insert(this, __position, size());
00378         return iterator(_Base::insert(__position.base(), __l), this);
00379       }
00380 #endif
00381 
00382 #if __cplusplus >= 201103L
00383       iterator
00384       insert(const_iterator __position, size_type __n, const _Tp& __x)
00385       {
00386         _M_profile_insert(this, __position, size());
00387     return iterator(_Base::insert(__position.base(), __n, __x), this);
00388       }
00389 #else
00390       void
00391       insert(iterator __position, size_type __n, const _Tp& __x)
00392       {
00393         _M_profile_insert(this, __position, size());
00394     _Base::insert(__position.base(), __n, __x);
00395       }
00396 #endif
00397 
00398 #if __cplusplus >= 201103L
00399       template<typename _InputIterator,
00400            typename = std::_RequireInputIter<_InputIterator>>
00401     iterator
00402         insert(const_iterator __position, _InputIterator __first,
00403            _InputIterator __last)
00404     {
00405       _M_profile_insert(this, __position, size());
00406       return iterator(_Base::insert(__position.base(), __first, __last),
00407               this);
00408     }
00409 #else
00410       template<class _InputIterator>
00411         void
00412         insert(iterator __position, _InputIterator __first,
00413            _InputIterator __last)
00414     {
00415       _M_profile_insert(this, __position, size());
00416       _Base::insert(__position.base(), __first, __last);
00417     }
00418 #endif
00419 
00420       iterator
00421 #if __cplusplus >= 201103L
00422       erase(const_iterator __position) noexcept
00423 #else
00424       erase(iterator __position)
00425 #endif
00426       { return iterator(_Base::erase(__position.base()), this); }
00427 
00428       iterator
00429 #if __cplusplus >= 201103L
00430       erase(const_iterator __position, const_iterator __last) noexcept
00431 #else
00432       erase(iterator __position, iterator __last)
00433 #endif
00434       {
00435     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00436     // 151. can't currently clear() empty container
00437     return iterator(_Base::erase(__position.base(), __last.base()), this);
00438       }
00439 
00440       void
00441       swap(list& __x)
00442       { _Base::swap(__x); }
00443 
00444       void
00445       clear() _GLIBCXX_NOEXCEPT
00446       { _Base::clear(); }
00447 
00448       // 23.2.2.4 list operations:
00449       void
00450 #if __cplusplus >= 201103L
00451       splice(const_iterator __position, list&& __x) noexcept
00452 #else
00453       splice(iterator __position, list& __x)
00454 #endif
00455       { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
00456 
00457 #if __cplusplus >= 201103L
00458       void
00459       splice(const_iterator __position, list& __x) noexcept
00460       { this->splice(__position, std::move(__x)); }
00461 
00462       void
00463       splice(const_iterator __position, list& __x, const_iterator __i)
00464       { this->splice(__position, std::move(__x), __i); }
00465 #endif
00466 
00467       void
00468 #if __cplusplus >= 201103L
00469       splice(const_iterator __position, list&& __x, const_iterator __i) noexcept
00470 #else
00471       splice(iterator __position, list& __x, iterator __i)
00472 #endif
00473       {
00474     // We used to perform the splice_alloc check:  not anymore, redundant
00475     // after implementing the relevant bits of N1599.
00476 
00477     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00478     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00479               __i.base());
00480       }
00481 
00482       void
00483 #if __cplusplus >= 201103L
00484       splice(const_iterator __position, list&& __x, const_iterator __first,
00485          const_iterator __last) noexcept
00486 #else
00487       splice(iterator __position, list& __x, iterator __first,
00488          iterator __last)
00489 #endif
00490       {
00491     // We used to perform the splice_alloc check:  not anymore, redundant
00492     // after implementing the relevant bits of N1599.
00493 
00494     _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
00495               __first.base(), __last.base());
00496       }
00497 
00498 #if __cplusplus >= 201103L
00499       void
00500       splice(const_iterator __position, list& __x,
00501          const_iterator __first, const_iterator __last) noexcept
00502       { this->splice(__position, std::move(__x), __first, __last); }
00503 #endif
00504 
00505       void
00506       remove(const _Tp& __value)
00507       {
00508     for (iterator __x = begin(); __x != end(); )
00509       {
00510         if (*__x == __value)
00511           __x = erase(__x);
00512         else
00513           ++__x;
00514       }
00515       }
00516 
00517       template<class _Predicate>
00518         void
00519         remove_if(_Predicate __pred)
00520         {
00521       for (iterator __x = begin(); __x != end(); )
00522         {
00523               __profcxx_list_operation(this);
00524           if (__pred(*__x))
00525         __x = erase(__x);
00526           else
00527         ++__x;
00528         }
00529     }
00530 
00531       void
00532       unique()
00533       {
00534     iterator __first = begin();
00535     iterator __last = end();
00536     if (__first == __last)
00537       return;
00538     iterator __next = __first;
00539     while (++__next != __last)
00540       {
00541             __profcxx_list_operation(this);
00542         if (*__first == *__next)
00543           erase(__next);
00544         else
00545           __first = __next;
00546         __next = __first;
00547       }
00548       }
00549 
00550       template<class _BinaryPredicate>
00551         void
00552         unique(_BinaryPredicate __binary_pred)
00553         {
00554       iterator __first = begin();
00555       iterator __last = end();
00556       if (__first == __last)
00557         return;
00558       iterator __next = __first;
00559       while (++__next != __last)
00560         {
00561               __profcxx_list_operation(this);
00562           if (__binary_pred(*__first, *__next))
00563         erase(__next);
00564           else
00565         __first = __next;
00566           __next = __first;
00567         }
00568     }
00569 
00570       void
00571 #if __cplusplus >= 201103L
00572       merge(list&& __x)
00573 #else
00574       merge(list& __x)
00575 #endif
00576       {
00577     // _GLIBCXX_RESOLVE_LIB_DEFECTS
00578     // 300. list::merge() specification incomplete
00579     if (this != &__x)
00580       { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
00581       }
00582 
00583 #if __cplusplus >= 201103L
00584       void
00585       merge(list& __x)
00586       { this->merge(std::move(__x)); }
00587 #endif
00588 
00589       template<class _Compare>
00590         void
00591 #if __cplusplus >= 201103L
00592         merge(list&& __x, _Compare __comp)
00593 #else
00594         merge(list& __x, _Compare __comp)
00595 #endif
00596         {
00597       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00598       // 300. list::merge() specification incomplete
00599       if (this != &__x)
00600         { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
00601     }
00602 
00603 #if __cplusplus >= 201103L
00604       template<typename _Compare>
00605         void
00606         merge(list& __x, _Compare __comp)
00607         { this->merge(std::move(__x), __comp); }
00608 #endif
00609 
00610       void
00611       sort() { _Base::sort(); }
00612 
00613       template<typename _StrictWeakOrdering>
00614         void
00615         sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
00616 
00617       using _Base::reverse;
00618 
00619       _Base&
00620       _M_base() _GLIBCXX_NOEXCEPT       { return *this; }
00621 
00622       const _Base&
00623       _M_base() const _GLIBCXX_NOEXCEPT { return *this; }
00624 
00625       void _M_profile_find() const
00626       { }
00627 
00628       void _M_profile_iterate(int __rewind = 0) const 
00629       {
00630         __profcxx_list_operation(this);
00631         __profcxx_list_iterate(this); 
00632         if (__rewind)
00633           __profcxx_list_rewind(this);
00634       }
00635 
00636     private:
00637       size_type
00638       _M_profile_insert(void* obj, const_iterator __pos, size_type __size)
00639       {
00640         size_type __shift = 0;
00641         typename _Base::const_iterator __it = __pos.base();
00642         for (; __it != _Base::end(); ++__it)
00643           __shift++;
00644         __profcxx_list_rewind(this);
00645         __profcxx_list_operation(this);
00646         __profcxx_list_insert(this, __shift, __size);
00647       }
00648     };
00649 
00650   template<typename _Tp, typename _Alloc>
00651     inline bool
00652     operator==(const list<_Tp, _Alloc>& __lhs,
00653            const list<_Tp, _Alloc>& __rhs)
00654     { return __lhs._M_base() == __rhs._M_base(); }
00655 
00656   template<typename _Tp, typename _Alloc>
00657     inline bool
00658     operator!=(const list<_Tp, _Alloc>& __lhs,
00659            const list<_Tp, _Alloc>& __rhs)
00660     { return __lhs._M_base() != __rhs._M_base(); }
00661 
00662   template<typename _Tp, typename _Alloc>
00663     inline bool
00664     operator<(const list<_Tp, _Alloc>& __lhs,
00665           const list<_Tp, _Alloc>& __rhs)
00666     { return __lhs._M_base() < __rhs._M_base(); }
00667 
00668   template<typename _Tp, typename _Alloc>
00669     inline bool
00670     operator<=(const list<_Tp, _Alloc>& __lhs,
00671            const list<_Tp, _Alloc>& __rhs)
00672     { return __lhs._M_base() <= __rhs._M_base(); }
00673 
00674   template<typename _Tp, typename _Alloc>
00675     inline bool
00676     operator>=(const list<_Tp, _Alloc>& __lhs,
00677            const list<_Tp, _Alloc>& __rhs)
00678     { return __lhs._M_base() >= __rhs._M_base(); }
00679 
00680   template<typename _Tp, typename _Alloc>
00681     inline bool
00682     operator>(const list<_Tp, _Alloc>& __lhs,
00683           const list<_Tp, _Alloc>& __rhs)
00684     { return __lhs._M_base() > __rhs._M_base(); }
00685 
00686   template<typename _Tp, typename _Alloc>
00687     inline void
00688     swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
00689     { __lhs.swap(__rhs); }
00690 
00691 } // namespace __profile
00692 } // namespace std
00693 
00694 #endif