list.tcc
Go to the documentation of this file.
// List implementation (out of line) -*- C++ -*-
// Copyright (C) 2001-2026 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/** @file bits/list.tcc
* This is an internal header file, included by other library headers.
* Do not attempt to use it directly. @headername{list}
*/
#ifndef _LIST_TCC
#define _LIST_TCC 1
namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION
_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
template<typename _Tp, typename _Alloc>
void
_List_base<_Tp, _Alloc>::
_M_clear() _GLIBCXX_NOEXCEPT
{
typedef typename _Node_traits::_Node _Node;
typedef typename _Node_traits::_Node_base _Node_base;
typename _Node_base::_Base_ptr __cur = _M_impl._M_node._M_next;
while (__cur != _M_impl._M_node._M_base())
{
_Node& __tmp = static_cast<_Node&>(*__cur);
__cur = __tmp._M_next;
this->_M_destroy_node(__tmp._M_node_ptr());
}
}
#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
template<typename... _Args>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
emplace(const_iterator __position, _Args&&... __args)
{
_Node_ptr __tmp = _M_create_node(std::forward<_Args>(__args)...);
__tmp->_M_hook(__position._M_const_cast()._M_node);
this->_M_inc_size(1);
return iterator(__tmp->_M_base());
}
#endif
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
insert(const_iterator __position, const value_type& __x)
#else
insert(iterator __position, const value_type& __x)
#endif
{
_Node_ptr __tmp = _M_create_node(__x);
__tmp->_M_hook(__position._M_const_cast()._M_node);
this->_M_inc_size(1);
return iterator(__tmp->_M_base());
}
#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
insert(const_iterator __position, size_type __n, const value_type& __x)
{
if (__n)
{
list __tmp(__n, __x, get_allocator());
iterator __it = __tmp.begin();
splice(__position, __tmp);
return __it;
}
return __position._M_const_cast();
}
template<typename _Tp, typename _Alloc>
template<typename _InputIterator, typename>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
insert(const_iterator __position, _InputIterator __first,
_InputIterator __last)
{
list __tmp(__first, __last, get_allocator());
if (!__tmp.empty())
{
iterator __it = __tmp.begin();
splice(__position, __tmp);
return __it;
}
return __position._M_const_cast();
}
#endif
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
erase(const_iterator __position) noexcept
#else
erase(iterator __position)
#endif
{
iterator __ret = iterator(__position._M_node->_M_next);
_M_erase(__position._M_const_cast());
return __ret;
}
// Return a const_iterator indicating the position to start inserting or
// erasing elements (depending whether the list is growing or shrinking),
// and set __new_size to the number of new elements that must be appended.
// Equivalent to the following, but performed optimally:
// if (__new_size < size()) {
// __new_size = 0;
// return std::next(begin(), __new_size);
// } else {
// __newsize -= size();
// return end();
// }
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::const_iterator
list<_Tp, _Alloc>::
_M_resize_pos(size_type& __new_size) const
{
const_iterator __i;
#if _GLIBCXX_USE_CXX11_ABI
const size_type __len = size();
if (__new_size < __len)
{
if (__new_size <= __len / 2)
{
__i = begin();
std::advance(__i, __new_size);
}
else
{
__i = end();
ptrdiff_t __num_erase = __len - __new_size;
std::advance(__i, -__num_erase);
}
__new_size = 0;
return __i;
}
else
__i = end();
#else
size_type __len = 0;
for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
;
#endif
__new_size -= __len;
return __i;
}
#if __cplusplus >= 201103L
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
_M_default_append(size_type __n)
{
size_type __i = 0;
__try
{
for (; __i < __n; ++__i)
emplace_back();
}
__catch(...)
{
for (; __i; --__i)
pop_back();
__throw_exception_again;
}
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
resize(size_type __new_size)
{
const_iterator __i = _M_resize_pos(__new_size);
if (__new_size)
_M_default_append(__new_size);
else
erase(__i, end());
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
resize(size_type __new_size, const value_type& __x)
{
const_iterator __i = _M_resize_pos(__new_size);
if (__new_size)
insert(end(), __new_size, __x);
else
erase(__i, end());
}
#else
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
resize(size_type __new_size, value_type __x)
{
const_iterator __i = _M_resize_pos(__new_size);
if (__new_size)
insert(end(), __new_size, __x);
else
erase(__i._M_const_cast(), end());
}
#endif
template<typename _Tp, typename _Alloc>
list<_Tp, _Alloc>&
list<_Tp, _Alloc>::
operator=(const list& __x)
{
if (this != std::__addressof(__x))
{
#if __cplusplus >= 201103L
if (_Node_alloc_traits::_S_propagate_on_copy_assign())
{
auto& __this_alloc = this->_M_get_Node_allocator();
auto& __that_alloc = __x._M_get_Node_allocator();
if (!_Node_alloc_traits::_S_always_equal()
&& __this_alloc != __that_alloc)
{
// replacement allocator cannot free existing storage
clear();
}
std::__alloc_on_copy(__this_alloc, __that_alloc);
}
#endif
_M_assign_dispatch(__x.begin(), __x.end(), __false_type());
}
return *this;
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
_M_fill_assign(size_type __n, const value_type& __val)
{
iterator __i = begin();
for (; __i != end() && __n > 0; ++__i, --__n)
*__i = __val;
if (__n > 0)
insert(end(), __n, __val);
else
erase(__i, end());
}
template<typename _Tp, typename _Alloc>
template <typename _InputIterator>
void
list<_Tp, _Alloc>::
_M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
__false_type)
{
iterator __first1 = begin();
iterator __last1 = end();
for (; __first1 != __last1 && __first2 != __last2;
++__first1, (void)++__first2)
*__first1 = *__first2;
if (__first2 == __last2)
erase(__first1, __last1);
else
insert(__last1, __first2, __last2);
}
#if __cplusplus > 201703L
# define _GLIBCXX20_ONLY(__expr) __expr
#else
# define _GLIBCXX20_ONLY(__expr)
#endif
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::__remove_return_type
list<_Tp, _Alloc>::
remove(const value_type& __value)
{
#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
#endif
list __to_destroy(get_allocator());
iterator __first = begin();
iterator __last = end();
while (__first != __last)
{
iterator __next = __first;
++__next;
if (*__first == __value)
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 526. Is it undefined if a function in the standard changes
// in parameters?
__to_destroy.splice(__to_destroy.begin(), *this, __first);
#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
#endif
}
__first = __next;
}
#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
#else
return _GLIBCXX20_ONLY( __to_destroy.size() );
#endif
}
template<typename _Tp, typename _Alloc>
typename list<_Tp, _Alloc>::__remove_return_type
list<_Tp, _Alloc>::
unique()
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return _GLIBCXX20_ONLY( 0 );
#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
#endif
list __to_destroy(get_allocator());
iterator __next = __first;
while (++__next != __last)
{
if (*__first == *__next)
{
__to_destroy.splice(__to_destroy.begin(), *this, __next);
#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
#endif
}
else
__first = __next;
__next = __first;
}
#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
#else
return _GLIBCXX20_ONLY( __to_destroy.size() );
#endif
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
merge(list&& __x)
#else
merge(list& __x)
#endif
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 300. list::merge() specification incomplete
if (this != std::__addressof(__x))
{
_M_check_equal_allocators(__x);
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
const _Finalize_merge __fin(*this, __x, __first2);
while (__first1 != __last1 && __first2 != __last2)
if (*__first2 < *__first1)
{
iterator __next = __first2;
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
{
_M_transfer(__last1, __first2, __last2);
__first2 = __last2;
}
}
}
template<typename _Tp, typename _Alloc>
template <typename _StrictWeakOrdering>
void
list<_Tp, _Alloc>::
#if __cplusplus >= 201103L
merge(list&& __x, _StrictWeakOrdering __comp)
#else
merge(list& __x, _StrictWeakOrdering __comp)
#endif
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 300. list::merge() specification incomplete
if (this != std::__addressof(__x))
{
_M_check_equal_allocators(__x);
iterator __first1 = begin();
iterator __last1 = end();
iterator __first2 = __x.begin();
iterator __last2 = __x.end();
const _Finalize_merge __fin(*this, __x, __first2);
while (__first1 != __last1 && __first2 != __last2)
if (__comp(*__first2, *__first1))
{
iterator __next = __first2;
_M_transfer(__first1, __first2, ++__next);
__first2 = __next;
}
else
++__first1;
if (__first2 != __last2)
{
_M_transfer(__last1, __first2, __last2);
__first2 = __last2;
}
}
}
template<typename _Tp, typename _Alloc>
void
list<_Tp, _Alloc>::
sort()
{
// Do nothing if the list has length 0 or 1.
if (empty() || ++begin() == end())
return;
{
typedef __list::_Scratch_list<typename _Node_traits::_Node_base>
_Scratch_list;
// The algorithm used here is largely unchanged from the SGI STL
// and is described in The C++ Standard Template Library by Plauger,
// Stepanov, Lee, Musser.
// Each element of *this is spliced out and merged into one of the
// sorted lists in __tmp, then all the lists in __tmp are merged
// together and then swapped back into *this.
// Because all nodes end up back in *this we do not need to update
// this->size() while nodes are temporarily moved out.
_Scratch_list __carry;
_Scratch_list __tmp[64];
_Scratch_list* __fill = __tmp;
_Scratch_list* __counter;
typename _Scratch_list::template _Ptr_cmp<iterator, void> __ptr_comp;
__try
{
do
{
__carry._M_take_one(begin()._M_node);
for(__counter = __tmp;
__counter != __fill && !__counter->empty();
++__counter)
{
__counter->merge(__carry, __ptr_comp);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
if (__counter == __fill)
++__fill;
}
while ( !empty() );
for (__counter = __tmp + 1; __counter != __fill; ++__counter)
__counter->merge(__counter[-1], __ptr_comp);
__fill[-1].swap(this->_M_impl._M_node);
}
__catch(...)
{
// Move all nodes back into *this.
__carry._M_put_all(end()._M_node);
for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
__tmp[__i]._M_put_all(end()._M_node);
__throw_exception_again;
}
}
}
template<typename _Tp, typename _Alloc>
template <typename _Predicate>
typename list<_Tp, _Alloc>::__remove_return_type
list<_Tp, _Alloc>::
remove_if(_Predicate __pred)
{
#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
#endif
list __to_destroy(get_allocator());
iterator __first = begin();
iterator __last = end();
while (__first != __last)
{
iterator __next = __first;
++__next;
if (__pred(*__first))
{
__to_destroy.splice(__to_destroy.begin(), *this, __first);
#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
#endif
}
__first = __next;
}
#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
#else
return _GLIBCXX20_ONLY( __to_destroy.size() );
#endif
}
template<typename _Tp, typename _Alloc>
template <typename _BinaryPredicate>
typename list<_Tp, _Alloc>::__remove_return_type
list<_Tp, _Alloc>::
unique(_BinaryPredicate __binary_pred)
{
iterator __first = begin();
iterator __last = end();
if (__first == __last)
return _GLIBCXX20_ONLY(0);
#if !_GLIBCXX_USE_CXX11_ABI
size_type __removed __attribute__((__unused__)) = 0;
#endif
list __to_destroy(get_allocator());
iterator __next = __first;
while (++__next != __last)
{
if (__binary_pred(*__first, *__next))
{
__to_destroy.splice(__to_destroy.begin(), *this, __next);
#if !_GLIBCXX_USE_CXX11_ABI
_GLIBCXX20_ONLY( __removed++ );
#endif
}
else
__first = __next;
__next = __first;
}
#if !_GLIBCXX_USE_CXX11_ABI
return _GLIBCXX20_ONLY( __removed );
#else
return _GLIBCXX20_ONLY( __to_destroy.size() );
#endif
}
#undef _GLIBCXX20_ONLY
template<typename _Tp, typename _Alloc>
template <typename _StrictWeakOrdering>
void
list<_Tp, _Alloc>::
sort(_StrictWeakOrdering __comp)
{
// Do nothing if the list has length 0 or 1.
if (empty() || ++begin() == end())
return;
{
typedef __list::_Scratch_list<typename _Node_traits::_Node_base>
_Scratch_list;
_Scratch_list __carry;
_Scratch_list __tmp[64];
_Scratch_list* __fill = __tmp;
_Scratch_list* __counter;
typename _Scratch_list::
template _Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
= { __comp };
__try
{
do
{
__carry._M_take_one(begin()._M_node);
for(__counter = __tmp;
__counter != __fill && !__counter->empty();
++__counter)
{
__counter->merge(__carry, __ptr_comp);
__carry.swap(*__counter);
}
__carry.swap(*__counter);
if (__counter == __fill)
++__fill;
}
while ( !empty() );
for (__counter = __tmp + 1; __counter != __fill; ++__counter)
__counter->merge(__counter[-1], __ptr_comp);
__fill[-1].swap(this->_M_impl._M_node);
}
__catch(...)
{
// Move all nodes back into *this.
__carry._M_put_all(end()._M_node);
for (size_t __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
__tmp[__i]._M_put_all(end()._M_node);
__throw_exception_again;
}
}
}
_GLIBCXX_END_NAMESPACE_CONTAINER
_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
#endif /* _LIST_TCC */
std::__addressof
constexpr _Tp * __addressof(_Tp &__r) noexcept
Same as C++11 std::addressof.
Definition move.h:52
std::forward
constexpr _Tp && forward(typename std::remove_reference< _Tp >::type &__t) noexcept
Forward an lvalue.
Definition move.h:72
std::end
_Tp * end(valarray< _Tp > &__va) noexcept
Return an iterator pointing to one past the last element of the valarray.
Definition valarray:1251
std::begin
_Tp * begin(valarray< _Tp > &__va) noexcept
Return an iterator pointing to the first element of the valarray.
Definition valarray:1229
std
ISO C++ entities toplevel namespace is std.
std::empty
constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())
Return whether a container is empty.
Definition range_access.h:294
std::size
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Definition range_access.h:274
std::advance
constexpr void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
Definition stl_iterator_base_funcs.h:262
std::size_type
std::value_type
std::iterator
Common iterator class.
Definition stl_iterator_base_types.h:130
std::list
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition stl_list.h:1026
std::list::resize
void resize(size_type __new_size)
Resizes the list to the specified number of elements.
Definition list.tcc:226
std::list::insert
iterator insert(const_iterator __position, const value_type &__x)
Inserts given value into list before specified iterator.
Definition list.tcc:98
std::list::sort
void sort()
Sort the elements.
Definition list.tcc:477
std::list::begin
iterator begin() noexcept
Definition stl_list.h:1457
std::list::emplace
iterator emplace(const_iterator __position, _Args &&... __args)
Constructs object in list before specified iterator.
Definition list.tcc:85
std::list::get_allocator
allocator_type get_allocator() const noexcept
Get a copy of the memory allocation object.
Definition stl_list.h:1447
std::list::operator=
list & operator=(const list &__x)
List assignment operator.
Definition list.tcc:263
std::list::unique
__remove_return_type unique()
Remove consecutive duplicate elements.
Definition list.tcc:363
std::list::size
size_type size() const noexcept
Definition stl_list.h:1586
std::list::merge
void merge(list &&__x)
Merge sorted lists.
Definition list.tcc:399
std::list::_M_create_node
_Node_ptr _M_create_node(_Args &&... __args)
Definition stl_list.h:1102
std::list::remove
__remove_return_type remove(const _Tp &__value)
Remove all elements equal to value.
Definition list.tcc:327
std::list::list
list()=default
Creates a list with no elements.
std::list::remove_if
__remove_return_type remove_if(_Predicate)
Remove all elements satisfying a predicate.
Definition list.tcc:541
std::list::end
iterator end() noexcept
Definition stl_list.h:1477
std::list::splice
void splice(const_iterator __position, list &&__x) noexcept
Insert contents of another list.
Definition stl_list.h:2102
std::list::clear
void clear() noexcept
Definition stl_list.h:2082
std::list::erase
iterator erase(const_iterator __position) noexcept
Remove element at given position.
Definition list.tcc:147
std::list::empty
bool empty() const noexcept
Definition stl_list.h:1578
std::_List_base
See bits/stl_deque.h's _Deque_base for an explanation.
Definition stl_list.h:749