libstdc++
|
00001 // List implementation (out of line) -*- C++ -*- 00002 00003 // Copyright (C) 2001-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 /* 00026 * 00027 * Copyright (c) 1994 00028 * Hewlett-Packard Company 00029 * 00030 * Permission to use, copy, modify, distribute and sell this software 00031 * and its documentation for any purpose is hereby granted without fee, 00032 * provided that the above copyright notice appear in all copies and 00033 * that both that copyright notice and this permission notice appear 00034 * in supporting documentation. Hewlett-Packard Company makes no 00035 * representations about the suitability of this software for any 00036 * purpose. It is provided "as is" without express or implied warranty. 00037 * 00038 * 00039 * Copyright (c) 1996,1997 00040 * Silicon Graphics Computer Systems, Inc. 00041 * 00042 * Permission to use, copy, modify, distribute and sell this software 00043 * and its documentation for any purpose is hereby granted without fee, 00044 * provided that the above copyright notice appear in all copies and 00045 * that both that copyright notice and this permission notice appear 00046 * in supporting documentation. Silicon Graphics makes no 00047 * representations about the suitability of this software for any 00048 * purpose. It is provided "as is" without express or implied warranty. 00049 */ 00050 00051 /** @file bits/list.tcc 00052 * This is an internal header file, included by other library headers. 00053 * Do not attempt to use it directly. @headername{list} 00054 */ 00055 00056 #ifndef _LIST_TCC 00057 #define _LIST_TCC 1 00058 00059 namespace std _GLIBCXX_VISIBILITY(default) 00060 { 00061 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 00062 00063 template<typename _Tp, typename _Alloc> 00064 void 00065 _List_base<_Tp, _Alloc>:: 00066 _M_clear() 00067 { 00068 typedef _List_node<_Tp> _Node; 00069 _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next); 00070 while (__cur != &_M_impl._M_node) 00071 { 00072 _Node* __tmp = __cur; 00073 __cur = static_cast<_Node*>(__cur->_M_next); 00074 #if __cplusplus >= 201103L 00075 _M_get_Node_allocator().destroy(__tmp); 00076 #else 00077 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); 00078 #endif 00079 _M_put_node(__tmp); 00080 } 00081 } 00082 00083 #if __cplusplus >= 201103L 00084 template<typename _Tp, typename _Alloc> 00085 template<typename... _Args> 00086 typename list<_Tp, _Alloc>::iterator 00087 list<_Tp, _Alloc>:: 00088 emplace(iterator __position, _Args&&... __args) 00089 { 00090 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 00091 __tmp->_M_hook(__position._M_node); 00092 return iterator(__tmp); 00093 } 00094 #endif 00095 00096 template<typename _Tp, typename _Alloc> 00097 typename list<_Tp, _Alloc>::iterator 00098 list<_Tp, _Alloc>:: 00099 insert(iterator __position, const value_type& __x) 00100 { 00101 _Node* __tmp = _M_create_node(__x); 00102 __tmp->_M_hook(__position._M_node); 00103 return iterator(__tmp); 00104 } 00105 00106 template<typename _Tp, typename _Alloc> 00107 typename list<_Tp, _Alloc>::iterator 00108 list<_Tp, _Alloc>:: 00109 erase(iterator __position) 00110 { 00111 iterator __ret = iterator(__position._M_node->_M_next); 00112 _M_erase(__position); 00113 return __ret; 00114 } 00115 00116 #if __cplusplus >= 201103L 00117 template<typename _Tp, typename _Alloc> 00118 void 00119 list<_Tp, _Alloc>:: 00120 _M_default_append(size_type __n) 00121 { 00122 size_type __i = 0; 00123 __try 00124 { 00125 for (; __i < __n; ++__i) 00126 emplace_back(); 00127 } 00128 __catch(...) 00129 { 00130 for (; __i; --__i) 00131 pop_back(); 00132 __throw_exception_again; 00133 } 00134 } 00135 00136 template<typename _Tp, typename _Alloc> 00137 void 00138 list<_Tp, _Alloc>:: 00139 resize(size_type __new_size) 00140 { 00141 iterator __i = begin(); 00142 size_type __len = 0; 00143 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00144 ; 00145 if (__len == __new_size) 00146 erase(__i, end()); 00147 else // __i == end() 00148 _M_default_append(__new_size - __len); 00149 } 00150 00151 template<typename _Tp, typename _Alloc> 00152 void 00153 list<_Tp, _Alloc>:: 00154 resize(size_type __new_size, const value_type& __x) 00155 { 00156 iterator __i = begin(); 00157 size_type __len = 0; 00158 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00159 ; 00160 if (__len == __new_size) 00161 erase(__i, end()); 00162 else // __i == end() 00163 insert(end(), __new_size - __len, __x); 00164 } 00165 #else 00166 template<typename _Tp, typename _Alloc> 00167 void 00168 list<_Tp, _Alloc>:: 00169 resize(size_type __new_size, value_type __x) 00170 { 00171 iterator __i = begin(); 00172 size_type __len = 0; 00173 for (; __i != end() && __len < __new_size; ++__i, ++__len) 00174 ; 00175 if (__len == __new_size) 00176 erase(__i, end()); 00177 else // __i == end() 00178 insert(end(), __new_size - __len, __x); 00179 } 00180 #endif 00181 00182 template<typename _Tp, typename _Alloc> 00183 list<_Tp, _Alloc>& 00184 list<_Tp, _Alloc>:: 00185 operator=(const list& __x) 00186 { 00187 if (this != &__x) 00188 { 00189 iterator __first1 = begin(); 00190 iterator __last1 = end(); 00191 const_iterator __first2 = __x.begin(); 00192 const_iterator __last2 = __x.end(); 00193 for (; __first1 != __last1 && __first2 != __last2; 00194 ++__first1, ++__first2) 00195 *__first1 = *__first2; 00196 if (__first2 == __last2) 00197 erase(__first1, __last1); 00198 else 00199 insert(__last1, __first2, __last2); 00200 } 00201 return *this; 00202 } 00203 00204 template<typename _Tp, typename _Alloc> 00205 void 00206 list<_Tp, _Alloc>:: 00207 _M_fill_assign(size_type __n, const value_type& __val) 00208 { 00209 iterator __i = begin(); 00210 for (; __i != end() && __n > 0; ++__i, --__n) 00211 *__i = __val; 00212 if (__n > 0) 00213 insert(end(), __n, __val); 00214 else 00215 erase(__i, end()); 00216 } 00217 00218 template<typename _Tp, typename _Alloc> 00219 template <typename _InputIterator> 00220 void 00221 list<_Tp, _Alloc>:: 00222 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 00223 __false_type) 00224 { 00225 iterator __first1 = begin(); 00226 iterator __last1 = end(); 00227 for (; __first1 != __last1 && __first2 != __last2; 00228 ++__first1, ++__first2) 00229 *__first1 = *__first2; 00230 if (__first2 == __last2) 00231 erase(__first1, __last1); 00232 else 00233 insert(__last1, __first2, __last2); 00234 } 00235 00236 template<typename _Tp, typename _Alloc> 00237 void 00238 list<_Tp, _Alloc>:: 00239 remove(const value_type& __value) 00240 { 00241 iterator __first = begin(); 00242 iterator __last = end(); 00243 iterator __extra = __last; 00244 while (__first != __last) 00245 { 00246 iterator __next = __first; 00247 ++__next; 00248 if (*__first == __value) 00249 { 00250 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00251 // 526. Is it undefined if a function in the standard changes 00252 // in parameters? 00253 if (std::__addressof(*__first) != std::__addressof(__value)) 00254 _M_erase(__first); 00255 else 00256 __extra = __first; 00257 } 00258 __first = __next; 00259 } 00260 if (__extra != __last) 00261 _M_erase(__extra); 00262 } 00263 00264 template<typename _Tp, typename _Alloc> 00265 void 00266 list<_Tp, _Alloc>:: 00267 unique() 00268 { 00269 iterator __first = begin(); 00270 iterator __last = end(); 00271 if (__first == __last) 00272 return; 00273 iterator __next = __first; 00274 while (++__next != __last) 00275 { 00276 if (*__first == *__next) 00277 _M_erase(__next); 00278 else 00279 __first = __next; 00280 __next = __first; 00281 } 00282 } 00283 00284 template<typename _Tp, typename _Alloc> 00285 void 00286 list<_Tp, _Alloc>:: 00287 #if __cplusplus >= 201103L 00288 merge(list&& __x) 00289 #else 00290 merge(list& __x) 00291 #endif 00292 { 00293 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00294 // 300. list::merge() specification incomplete 00295 if (this != &__x) 00296 { 00297 _M_check_equal_allocators(__x); 00298 00299 iterator __first1 = begin(); 00300 iterator __last1 = end(); 00301 iterator __first2 = __x.begin(); 00302 iterator __last2 = __x.end(); 00303 while (__first1 != __last1 && __first2 != __last2) 00304 if (*__first2 < *__first1) 00305 { 00306 iterator __next = __first2; 00307 _M_transfer(__first1, __first2, ++__next); 00308 __first2 = __next; 00309 } 00310 else 00311 ++__first1; 00312 if (__first2 != __last2) 00313 _M_transfer(__last1, __first2, __last2); 00314 } 00315 } 00316 00317 template<typename _Tp, typename _Alloc> 00318 template <typename _StrictWeakOrdering> 00319 void 00320 list<_Tp, _Alloc>:: 00321 #if __cplusplus >= 201103L 00322 merge(list&& __x, _StrictWeakOrdering __comp) 00323 #else 00324 merge(list& __x, _StrictWeakOrdering __comp) 00325 #endif 00326 { 00327 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00328 // 300. list::merge() specification incomplete 00329 if (this != &__x) 00330 { 00331 _M_check_equal_allocators(__x); 00332 00333 iterator __first1 = begin(); 00334 iterator __last1 = end(); 00335 iterator __first2 = __x.begin(); 00336 iterator __last2 = __x.end(); 00337 while (__first1 != __last1 && __first2 != __last2) 00338 if (__comp(*__first2, *__first1)) 00339 { 00340 iterator __next = __first2; 00341 _M_transfer(__first1, __first2, ++__next); 00342 __first2 = __next; 00343 } 00344 else 00345 ++__first1; 00346 if (__first2 != __last2) 00347 _M_transfer(__last1, __first2, __last2); 00348 } 00349 } 00350 00351 template<typename _Tp, typename _Alloc> 00352 void 00353 list<_Tp, _Alloc>:: 00354 sort() 00355 { 00356 // Do nothing if the list has length 0 or 1. 00357 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00358 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00359 { 00360 list __carry; 00361 list __tmp[64]; 00362 list * __fill = &__tmp[0]; 00363 list * __counter; 00364 00365 do 00366 { 00367 __carry.splice(__carry.begin(), *this, begin()); 00368 00369 for(__counter = &__tmp[0]; 00370 __counter != __fill && !__counter->empty(); 00371 ++__counter) 00372 { 00373 __counter->merge(__carry); 00374 __carry.swap(*__counter); 00375 } 00376 __carry.swap(*__counter); 00377 if (__counter == __fill) 00378 ++__fill; 00379 } 00380 while ( !empty() ); 00381 00382 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00383 __counter->merge(*(__counter - 1)); 00384 swap( *(__fill - 1) ); 00385 } 00386 } 00387 00388 template<typename _Tp, typename _Alloc> 00389 template <typename _Predicate> 00390 void 00391 list<_Tp, _Alloc>:: 00392 remove_if(_Predicate __pred) 00393 { 00394 iterator __first = begin(); 00395 iterator __last = end(); 00396 while (__first != __last) 00397 { 00398 iterator __next = __first; 00399 ++__next; 00400 if (__pred(*__first)) 00401 _M_erase(__first); 00402 __first = __next; 00403 } 00404 } 00405 00406 template<typename _Tp, typename _Alloc> 00407 template <typename _BinaryPredicate> 00408 void 00409 list<_Tp, _Alloc>:: 00410 unique(_BinaryPredicate __binary_pred) 00411 { 00412 iterator __first = begin(); 00413 iterator __last = end(); 00414 if (__first == __last) 00415 return; 00416 iterator __next = __first; 00417 while (++__next != __last) 00418 { 00419 if (__binary_pred(*__first, *__next)) 00420 _M_erase(__next); 00421 else 00422 __first = __next; 00423 __next = __first; 00424 } 00425 } 00426 00427 template<typename _Tp, typename _Alloc> 00428 template <typename _StrictWeakOrdering> 00429 void 00430 list<_Tp, _Alloc>:: 00431 sort(_StrictWeakOrdering __comp) 00432 { 00433 // Do nothing if the list has length 0 or 1. 00434 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 00435 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 00436 { 00437 list __carry; 00438 list __tmp[64]; 00439 list * __fill = &__tmp[0]; 00440 list * __counter; 00441 00442 do 00443 { 00444 __carry.splice(__carry.begin(), *this, begin()); 00445 00446 for(__counter = &__tmp[0]; 00447 __counter != __fill && !__counter->empty(); 00448 ++__counter) 00449 { 00450 __counter->merge(__carry, __comp); 00451 __carry.swap(*__counter); 00452 } 00453 __carry.swap(*__counter); 00454 if (__counter == __fill) 00455 ++__fill; 00456 } 00457 while ( !empty() ); 00458 00459 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 00460 __counter->merge(*(__counter - 1), __comp); 00461 swap(*(__fill - 1)); 00462 } 00463 } 00464 00465 _GLIBCXX_END_NAMESPACE_CONTAINER 00466 } // namespace std 00467 00468 #endif /* _LIST_TCC */ 00469