1 // List implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011 Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
29 * Hewlett-Packard Company
31 * Permission to use, copy, modify, distribute and sell this software
32 * and its documentation for any purpose is hereby granted without fee,
33 * provided that the above copyright notice appear in all copies and
34 * that both that copyright notice and this permission notice appear
35 * in supporting documentation. Hewlett-Packard Company makes no
36 * representations about the suitability of this software for any
37 * purpose. It is provided "as is" without express or implied warranty.
40 * Copyright (c) 1996,1997
41 * Silicon Graphics Computer Systems, Inc.
43 * Permission to use, copy, modify, distribute and sell this software
44 * and its documentation for any purpose is hereby granted without fee,
45 * provided that the above copyright notice appear in all copies and
46 * that both that copyright notice and this permission notice appear
47 * in supporting documentation. Silicon Graphics makes no
48 * representations about the suitability of this software for any
49 * purpose. It is provided "as is" without express or implied warranty.
52 /** @file bits/list.tcc
53 * This is an internal header file, included by other library headers.
54 * Do not attempt to use it directly. @headername{list}
60 namespace std _GLIBCXX_VISIBILITY(default)
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
64 template<typename _Tp, typename _Alloc>
66 _List_base<_Tp, _Alloc>::
69 typedef _List_node<_Tp> _Node;
70 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
71 while (__cur != &this->_M_impl._M_node)
74 __cur = static_cast<_Node*>(__cur->_M_next);
75 #ifdef __GXX_EXPERIMENTAL_CXX0X__
76 _M_get_Node_allocator().destroy(__tmp);
78 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
84 #ifdef __GXX_EXPERIMENTAL_CXX0X__
85 template<typename _Tp, typename _Alloc>
86 template<typename... _Args>
87 typename list<_Tp, _Alloc>::iterator
89 emplace(iterator __position, _Args&&... __args)
91 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
92 __tmp->_M_hook(__position._M_node);
93 return iterator(__tmp);
97 template<typename _Tp, typename _Alloc>
98 typename list<_Tp, _Alloc>::iterator
100 insert(iterator __position, const value_type& __x)
102 _Node* __tmp = _M_create_node(__x);
103 __tmp->_M_hook(__position._M_node);
104 return iterator(__tmp);
107 template<typename _Tp, typename _Alloc>
108 typename list<_Tp, _Alloc>::iterator
110 erase(iterator __position)
112 iterator __ret = iterator(__position._M_node->_M_next);
113 _M_erase(__position);
117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
118 template<typename _Tp, typename _Alloc>
121 _M_default_append(size_type __n)
126 for (; __i < __n; ++__i)
133 __throw_exception_again;
137 template<typename _Tp, typename _Alloc>
140 resize(size_type __new_size)
142 iterator __i = begin();
144 for (; __i != end() && __len < __new_size; ++__i, ++__len)
146 if (__len == __new_size)
149 _M_default_append(__new_size - __len);
152 template<typename _Tp, typename _Alloc>
155 resize(size_type __new_size, const value_type& __x)
157 iterator __i = begin();
159 for (; __i != end() && __len < __new_size; ++__i, ++__len)
161 if (__len == __new_size)
164 insert(end(), __new_size - __len, __x);
167 template<typename _Tp, typename _Alloc>
170 resize(size_type __new_size, value_type __x)
172 iterator __i = begin();
174 for (; __i != end() && __len < __new_size; ++__i, ++__len)
176 if (__len == __new_size)
179 insert(end(), __new_size - __len, __x);
183 template<typename _Tp, typename _Alloc>
186 operator=(const list& __x)
190 iterator __first1 = begin();
191 iterator __last1 = end();
192 const_iterator __first2 = __x.begin();
193 const_iterator __last2 = __x.end();
194 for (; __first1 != __last1 && __first2 != __last2;
195 ++__first1, ++__first2)
196 *__first1 = *__first2;
197 if (__first2 == __last2)
198 erase(__first1, __last1);
200 insert(__last1, __first2, __last2);
205 template<typename _Tp, typename _Alloc>
208 _M_fill_assign(size_type __n, const value_type& __val)
210 iterator __i = begin();
211 for (; __i != end() && __n > 0; ++__i, --__n)
214 insert(end(), __n, __val);
219 template<typename _Tp, typename _Alloc>
220 template <typename _InputIterator>
223 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
226 iterator __first1 = begin();
227 iterator __last1 = end();
228 for (; __first1 != __last1 && __first2 != __last2;
229 ++__first1, ++__first2)
230 *__first1 = *__first2;
231 if (__first2 == __last2)
232 erase(__first1, __last1);
234 insert(__last1, __first2, __last2);
237 template<typename _Tp, typename _Alloc>
240 remove(const value_type& __value)
242 iterator __first = begin();
243 iterator __last = end();
244 iterator __extra = __last;
245 while (__first != __last)
247 iterator __next = __first;
249 if (*__first == __value)
251 // _GLIBCXX_RESOLVE_LIB_DEFECTS
252 // 526. Is it undefined if a function in the standard changes
254 if (std::__addressof(*__first) != std::__addressof(__value))
261 if (__extra != __last)
265 template<typename _Tp, typename _Alloc>
270 iterator __first = begin();
271 iterator __last = end();
272 if (__first == __last)
274 iterator __next = __first;
275 while (++__next != __last)
277 if (*__first == *__next)
285 template<typename _Tp, typename _Alloc>
288 #ifdef __GXX_EXPERIMENTAL_CXX0X__
294 // _GLIBCXX_RESOLVE_LIB_DEFECTS
295 // 300. list::merge() specification incomplete
298 _M_check_equal_allocators(__x);
300 iterator __first1 = begin();
301 iterator __last1 = end();
302 iterator __first2 = __x.begin();
303 iterator __last2 = __x.end();
304 while (__first1 != __last1 && __first2 != __last2)
305 if (*__first2 < *__first1)
307 iterator __next = __first2;
308 _M_transfer(__first1, __first2, ++__next);
313 if (__first2 != __last2)
314 _M_transfer(__last1, __first2, __last2);
318 template<typename _Tp, typename _Alloc>
319 template <typename _StrictWeakOrdering>
322 #ifdef __GXX_EXPERIMENTAL_CXX0X__
323 merge(list&& __x, _StrictWeakOrdering __comp)
325 merge(list& __x, _StrictWeakOrdering __comp)
328 // _GLIBCXX_RESOLVE_LIB_DEFECTS
329 // 300. list::merge() specification incomplete
332 _M_check_equal_allocators(__x);
334 iterator __first1 = begin();
335 iterator __last1 = end();
336 iterator __first2 = __x.begin();
337 iterator __last2 = __x.end();
338 while (__first1 != __last1 && __first2 != __last2)
339 if (__comp(*__first2, *__first1))
341 iterator __next = __first2;
342 _M_transfer(__first1, __first2, ++__next);
347 if (__first2 != __last2)
348 _M_transfer(__last1, __first2, __last2);
352 template<typename _Tp, typename _Alloc>
357 // Do nothing if the list has length 0 or 1.
358 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
359 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
363 list * __fill = &__tmp[0];
368 __carry.splice(__carry.begin(), *this, begin());
370 for(__counter = &__tmp[0];
371 __counter != __fill && !__counter->empty();
374 __counter->merge(__carry);
375 __carry.swap(*__counter);
377 __carry.swap(*__counter);
378 if (__counter == __fill)
383 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
384 __counter->merge(*(__counter - 1));
385 swap( *(__fill - 1) );
389 template<typename _Tp, typename _Alloc>
390 template <typename _Predicate>
393 remove_if(_Predicate __pred)
395 iterator __first = begin();
396 iterator __last = end();
397 while (__first != __last)
399 iterator __next = __first;
401 if (__pred(*__first))
407 template<typename _Tp, typename _Alloc>
408 template <typename _BinaryPredicate>
411 unique(_BinaryPredicate __binary_pred)
413 iterator __first = begin();
414 iterator __last = end();
415 if (__first == __last)
417 iterator __next = __first;
418 while (++__next != __last)
420 if (__binary_pred(*__first, *__next))
428 template<typename _Tp, typename _Alloc>
429 template <typename _StrictWeakOrdering>
432 sort(_StrictWeakOrdering __comp)
434 // Do nothing if the list has length 0 or 1.
435 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
436 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
440 list * __fill = &__tmp[0];
445 __carry.splice(__carry.begin(), *this, begin());
447 for(__counter = &__tmp[0];
448 __counter != __fill && !__counter->empty();
451 __counter->merge(__carry, __comp);
452 __carry.swap(*__counter);
454 __carry.swap(*__counter);
455 if (__counter == __fill)
460 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
461 __counter->merge(*(__counter - 1), __comp);
466 _GLIBCXX_END_NAMESPACE_CONTAINER
469 #endif /* _LIST_TCC */