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