1 // List implementation (out of line) -*- C++ -*-
3 // Copyright (C) 2001-2015 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
28 * Hewlett-Packard Company
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Hewlett-Packard Company makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
39 * Copyright (c) 1996,1997
40 * Silicon Graphics Computer Systems, Inc.
42 * Permission to use, copy, modify, distribute and sell this software
43 * and its documentation for any purpose is hereby granted without fee,
44 * provided that the above copyright notice appear in all copies and
45 * that both that copyright notice and this permission notice appear
46 * in supporting documentation. Silicon Graphics makes no
47 * representations about the suitability of this software for any
48 * purpose. It is provided "as is" without express or implied warranty.
51 /** @file bits/list.tcc
52 * This is an internal header file, included by other library headers.
53 * Do not attempt to use it directly. @headername{list}
59 namespace std _GLIBCXX_VISIBILITY(default)
61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 template<typename _Tp, typename _Alloc>
65 _List_base<_Tp, _Alloc>::
66 _M_clear() _GLIBCXX_NOEXCEPT
68 typedef _List_node<_Tp> _Node;
69 __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
70 while (__cur != &_M_impl._M_node)
72 _Node* __tmp = static_cast<_Node*>(__cur);
73 __cur = __tmp->_M_next;
74 #if __cplusplus >= 201103L
75 _M_get_Node_allocator().destroy(__tmp);
77 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
83 #if __cplusplus >= 201103L
84 template<typename _Tp, typename _Alloc>
85 template<typename... _Args>
86 typename list<_Tp, _Alloc>::iterator
88 emplace(const_iterator __position, _Args&&... __args)
90 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
91 __tmp->_M_hook(__position._M_const_cast()._M_node);
93 return iterator(__tmp);
97 template<typename _Tp, typename _Alloc>
98 typename list<_Tp, _Alloc>::iterator
100 #if __cplusplus >= 201103L
101 insert(const_iterator __position, const value_type& __x)
103 insert(iterator __position, const value_type& __x)
106 _Node* __tmp = _M_create_node(__x);
107 __tmp->_M_hook(__position._M_const_cast()._M_node);
108 this->_M_inc_size(1);
109 return iterator(__tmp);
112 #if __cplusplus >= 201103L
113 template<typename _Tp, typename _Alloc>
114 typename list<_Tp, _Alloc>::iterator
116 insert(const_iterator __position, size_type __n, const value_type& __x)
120 list __tmp(__n, __x, get_allocator());
121 iterator __it = __tmp.begin();
122 splice(__position, __tmp);
125 return __position._M_const_cast();
128 template<typename _Tp, typename _Alloc>
129 template<typename _InputIterator, typename>
130 typename list<_Tp, _Alloc>::iterator
132 insert(const_iterator __position, _InputIterator __first,
133 _InputIterator __last)
135 list __tmp(__first, __last, get_allocator());
138 iterator __it = __tmp.begin();
139 splice(__position, __tmp);
142 return __position._M_const_cast();
146 template<typename _Tp, typename _Alloc>
147 typename list<_Tp, _Alloc>::iterator
149 #if __cplusplus >= 201103L
150 erase(const_iterator __position) noexcept
152 erase(iterator __position)
155 iterator __ret = iterator(__position._M_node->_M_next);
156 _M_erase(__position._M_const_cast());
160 #if __cplusplus >= 201103L
161 template<typename _Tp, typename _Alloc>
164 _M_default_append(size_type __n)
169 for (; __i < __n; ++__i)
176 __throw_exception_again;
180 template<typename _Tp, typename _Alloc>
183 resize(size_type __new_size)
185 iterator __i = begin();
187 for (; __i != end() && __len < __new_size; ++__i, ++__len)
189 if (__len == __new_size)
192 _M_default_append(__new_size - __len);
195 template<typename _Tp, typename _Alloc>
198 resize(size_type __new_size, const value_type& __x)
200 iterator __i = begin();
202 for (; __i != end() && __len < __new_size; ++__i, ++__len)
204 if (__len == __new_size)
207 insert(end(), __new_size - __len, __x);
210 template<typename _Tp, typename _Alloc>
213 resize(size_type __new_size, value_type __x)
215 iterator __i = begin();
217 for (; __i != end() && __len < __new_size; ++__i, ++__len)
219 if (__len == __new_size)
222 insert(end(), __new_size - __len, __x);
226 template<typename _Tp, typename _Alloc>
229 operator=(const list& __x)
233 iterator __first1 = begin();
234 iterator __last1 = end();
235 const_iterator __first2 = __x.begin();
236 const_iterator __last2 = __x.end();
237 for (; __first1 != __last1 && __first2 != __last2;
238 ++__first1, ++__first2)
239 *__first1 = *__first2;
240 if (__first2 == __last2)
241 erase(__first1, __last1);
243 insert(__last1, __first2, __last2);
248 template<typename _Tp, typename _Alloc>
251 _M_fill_assign(size_type __n, const value_type& __val)
253 iterator __i = begin();
254 for (; __i != end() && __n > 0; ++__i, --__n)
257 insert(end(), __n, __val);
262 template<typename _Tp, typename _Alloc>
263 template <typename _InputIterator>
266 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
269 iterator __first1 = begin();
270 iterator __last1 = end();
271 for (; __first1 != __last1 && __first2 != __last2;
272 ++__first1, ++__first2)
273 *__first1 = *__first2;
274 if (__first2 == __last2)
275 erase(__first1, __last1);
277 insert(__last1, __first2, __last2);
280 template<typename _Tp, typename _Alloc>
283 remove(const value_type& __value)
285 iterator __first = begin();
286 iterator __last = end();
287 iterator __extra = __last;
288 while (__first != __last)
290 iterator __next = __first;
292 if (*__first == __value)
294 // _GLIBCXX_RESOLVE_LIB_DEFECTS
295 // 526. Is it undefined if a function in the standard changes
297 if (std::__addressof(*__first) != std::__addressof(__value))
304 if (__extra != __last)
308 template<typename _Tp, typename _Alloc>
313 iterator __first = begin();
314 iterator __last = end();
315 if (__first == __last)
317 iterator __next = __first;
318 while (++__next != __last)
320 if (*__first == *__next)
328 template<typename _Tp, typename _Alloc>
331 #if __cplusplus >= 201103L
337 // _GLIBCXX_RESOLVE_LIB_DEFECTS
338 // 300. list::merge() specification incomplete
341 _M_check_equal_allocators(__x);
343 iterator __first1 = begin();
344 iterator __last1 = end();
345 iterator __first2 = __x.begin();
346 iterator __last2 = __x.end();
347 while (__first1 != __last1 && __first2 != __last2)
348 if (*__first2 < *__first1)
350 iterator __next = __first2;
351 _M_transfer(__first1, __first2, ++__next);
356 if (__first2 != __last2)
357 _M_transfer(__last1, __first2, __last2);
359 this->_M_inc_size(__x._M_get_size());
364 template<typename _Tp, typename _Alloc>
365 template <typename _StrictWeakOrdering>
368 #if __cplusplus >= 201103L
369 merge(list&& __x, _StrictWeakOrdering __comp)
371 merge(list& __x, _StrictWeakOrdering __comp)
374 // _GLIBCXX_RESOLVE_LIB_DEFECTS
375 // 300. list::merge() specification incomplete
378 _M_check_equal_allocators(__x);
380 iterator __first1 = begin();
381 iterator __last1 = end();
382 iterator __first2 = __x.begin();
383 iterator __last2 = __x.end();
384 while (__first1 != __last1 && __first2 != __last2)
385 if (__comp(*__first2, *__first1))
387 iterator __next = __first2;
388 _M_transfer(__first1, __first2, ++__next);
393 if (__first2 != __last2)
394 _M_transfer(__last1, __first2, __last2);
396 this->_M_inc_size(__x._M_get_size());
401 template<typename _Tp, typename _Alloc>
406 // Do nothing if the list has length 0 or 1.
407 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
408 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
412 list * __fill = &__tmp[0];
417 __carry.splice(__carry.begin(), *this, begin());
419 for(__counter = &__tmp[0];
420 __counter != __fill && !__counter->empty();
423 __counter->merge(__carry);
424 __carry.swap(*__counter);
426 __carry.swap(*__counter);
427 if (__counter == __fill)
432 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
433 __counter->merge(*(__counter - 1));
434 swap( *(__fill - 1) );
438 template<typename _Tp, typename _Alloc>
439 template <typename _Predicate>
442 remove_if(_Predicate __pred)
444 iterator __first = begin();
445 iterator __last = end();
446 while (__first != __last)
448 iterator __next = __first;
450 if (__pred(*__first))
456 template<typename _Tp, typename _Alloc>
457 template <typename _BinaryPredicate>
460 unique(_BinaryPredicate __binary_pred)
462 iterator __first = begin();
463 iterator __last = end();
464 if (__first == __last)
466 iterator __next = __first;
467 while (++__next != __last)
469 if (__binary_pred(*__first, *__next))
477 template<typename _Tp, typename _Alloc>
478 template <typename _StrictWeakOrdering>
481 sort(_StrictWeakOrdering __comp)
483 // Do nothing if the list has length 0 or 1.
484 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
485 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
489 list * __fill = &__tmp[0];
494 __carry.splice(__carry.begin(), *this, begin());
496 for(__counter = &__tmp[0];
497 __counter != __fill && !__counter->empty();
500 __counter->merge(__carry, __comp);
501 __carry.swap(*__counter);
503 __carry.swap(*__counter);
504 if (__counter == __fill)
509 for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
510 __counter->merge(*(__counter - 1), __comp);
515 _GLIBCXX_END_NAMESPACE_CONTAINER
518 #endif /* _LIST_TCC */