63 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_D)
73 _List_node_base* _M_next;
74 _List_node_base* _M_prev;
77 swap(_List_node_base& __x, _List_node_base& __y);
80 transfer(_List_node_base *
const __first,
81 _List_node_base *
const __last);
87 hook(_List_node_base *
const __position);
94 template<
typename _Tp>
100 #ifdef __GXX_EXPERIMENTAL_CXX0X__
101 template<
typename... _Args>
112 template<
typename _Tp>
118 typedef ptrdiff_t difference_type;
120 typedef _Tp value_type;
121 typedef _Tp* pointer;
122 typedef _Tp& reference;
134 {
return static_cast<_Node*
>(_M_node)->_M_data; }
138 {
return &
static_cast<_Node*
>(_M_node)->_M_data; }
143 _M_node = _M_node->_M_next;
151 _M_node = _M_node->_M_next;
158 _M_node = _M_node->_M_prev;
166 _M_node = _M_node->_M_prev;
172 {
return _M_node == __x._M_node; }
176 {
return _M_node != __x._M_node; }
187 template<
typename _Tp>
194 typedef ptrdiff_t difference_type;
196 typedef _Tp value_type;
197 typedef const _Tp* pointer;
198 typedef const _Tp& reference;
208 : _M_node(__x._M_node) { }
214 {
return static_cast<_Node*
>(_M_node)->_M_data; }
218 {
return &
static_cast<_Node*
>(_M_node)->_M_data; }
223 _M_node = _M_node->_M_next;
231 _M_node = _M_node->_M_next;
238 _M_node = _M_node->_M_prev;
246 _M_node = _M_node->_M_prev;
252 {
return _M_node == __x._M_node; }
256 {
return _M_node != __x._M_node; }
262 template<
typename _Val>
266 {
return __x._M_node == __y._M_node; }
268 template<
typename _Val>
271 const _List_const_iterator<_Val>& __y)
272 {
return __x._M_node != __y._M_node; }
276 template<
typename _Tp,
typename _Alloc>
293 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
296 typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;
299 :
public _Node_alloc_type
304 : _Node_alloc_type(), _M_node()
307 _List_impl(
const _Node_alloc_type& __a)
308 : _Node_alloc_type(__a), _M_node()
316 {
return _M_impl._Node_alloc_type::allocate(1); }
320 { _M_impl._Node_alloc_type::deallocate(__p, 1); }
323 typedef _Alloc allocator_type;
326 _M_get_Node_allocator()
327 {
return *
static_cast<_Node_alloc_type*
>(&this->_M_impl); }
329 const _Node_alloc_type&
330 _M_get_Node_allocator()
const
331 {
return *
static_cast<const _Node_alloc_type*
>(&this->_M_impl); }
334 _M_get_Tp_allocator()
const
335 {
return _Tp_alloc_type(_M_get_Node_allocator()); }
338 get_allocator()
const
339 {
return allocator_type(_M_get_Node_allocator()); }
349 #ifdef __GXX_EXPERIMENTAL_CXX0X__
351 : _M_impl(__x._M_get_Node_allocator())
354 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
368 this->_M_impl._M_node._M_next = &this->_M_impl._M_node;
369 this->_M_impl._M_node._M_prev = &this->_M_impl._M_node;
416 template<
typename _Tp,
typename _Alloc = std::allocator<_Tp> >
420 typedef typename _Alloc::value_type _Alloc_value_type;
421 __glibcxx_class_requires(_Tp, _SGIAssignableConcept)
422 __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept)
425 typedef typename _Base::_Tp_alloc_type _Tp_alloc_type;
428 typedef _Tp value_type;
429 typedef typename _Tp_alloc_type::pointer pointer;
430 typedef typename _Tp_alloc_type::const_pointer const_pointer;
431 typedef typename _Tp_alloc_type::reference reference;
432 typedef typename _Tp_alloc_type::const_reference const_reference;
437 typedef size_t size_type;
438 typedef ptrdiff_t difference_type;
439 typedef _Alloc allocator_type;
446 using _Base::_M_impl;
447 using _Base::_M_put_node;
448 using _Base::_M_get_node;
449 using _Base::_M_get_Tp_allocator;
450 using _Base::_M_get_Node_allocator;
457 #ifndef __GXX_EXPERIMENTAL_CXX0X__
459 _M_create_node(
const value_type& __x)
461 _Node* __p = this->_M_get_node();
464 _M_get_Tp_allocator().construct(&__p->
_M_data, __x);
469 __throw_exception_again;
474 template<
typename... _Args>
478 _Node* __p = this->_M_get_node();
481 _M_get_Node_allocator().construct(__p,
482 std::forward<_Args>(__args)...);
487 __throw_exception_again;
507 list(
const allocator_type& __a)
519 list(size_type __n,
const value_type& __value = value_type(),
520 const allocator_type& __a = allocator_type())
522 { _M_fill_initialize(__n, __value); }
532 :
_Base(__x._M_get_Node_allocator())
533 { _M_initialize_dispatch(__x.
begin(), __x.
end(), __false_type()); }
535 #ifdef __GXX_EXPERIMENTAL_CXX0X__
555 const allocator_type& __a = allocator_type())
557 { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); }
570 template<
typename _InputIterator>
571 list(_InputIterator __first, _InputIterator __last,
572 const allocator_type& __a = allocator_type())
576 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
577 _M_initialize_dispatch(__first, __last, _Integral());
596 operator=(
const list& __x);
598 #ifdef __GXX_EXPERIMENTAL_CXX0X__
625 this->assign(__l.begin(), __l.end());
641 assign(size_type __n,
const value_type& __val)
642 { _M_fill_assign(__n, __val); }
656 template<
typename _InputIterator>
658 assign(_InputIterator __first, _InputIterator __last)
661 typedef typename std::__is_integer<_InputIterator>::__type _Integral;
662 _M_assign_dispatch(__first, __last, _Integral());
665 #ifdef __GXX_EXPERIMENTAL_CXX0X__
675 { this->assign(__l.begin(), __l.end()); }
681 {
return _Base::get_allocator(); }
690 {
return iterator(this->_M_impl._M_node._M_next); }
708 {
return iterator(&this->_M_impl._M_node); }
733 const_reverse_iterator
751 const_reverse_iterator
755 #ifdef __GXX_EXPERIMENTAL_CXX0X__
779 const_reverse_iterator
788 const_reverse_iterator
800 {
return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
810 {
return _M_get_Node_allocator().max_size(); }
823 resize(size_type __new_size, value_type __x = value_type());
879 { this->_M_insert(begin(), __x); }
881 #ifdef __GXX_EXPERIMENTAL_CXX0X__
883 push_front(value_type&& __x)
884 { this->_M_insert(begin(), std::move(__x)); }
886 template<
typename... _Args>
888 emplace_front(_Args&&... __args)
889 { this->_M_insert(begin(), std::forward<_Args>(__args)...); }
906 { this->_M_erase(begin()); }
920 { this->_M_insert(end(), __x); }
922 #ifdef __GXX_EXPERIMENTAL_CXX0X__
924 push_back(value_type&& __x)
925 { this->_M_insert(end(), std::move(__x)); }
927 template<
typename... _Args>
929 emplace_back(_Args&&... __args)
930 { this->_M_insert(end(), std::forward<_Args>(__args)...); }
946 { this->_M_erase(
iterator(this->_M_impl._M_node._M_prev)); }
948 #ifdef __GXX_EXPERIMENTAL_CXX0X__
961 template<
typename... _Args>
963 emplace(
iterator __position, _Args&&... __args);
978 insert(
iterator __position,
const value_type& __x);
980 #ifdef __GXX_EXPERIMENTAL_CXX0X__
994 {
return emplace(__position,
std::move(__x)); }
1011 { this->insert(__p, __l.begin(), __l.end()); }
1029 list __tmp(__n, __x, _M_get_Node_allocator());
1030 splice(__position, __tmp);
1046 template<
typename _InputIterator>
1049 _InputIterator __last)
1051 list __tmp(__first, __last, _M_get_Node_allocator());
1052 splice(__position, __tmp);
1094 while (__first != __last)
1095 __first = erase(__first);
1109 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1115 _List_node_base::swap(this->_M_impl._M_node, __x._M_impl._M_node);
1119 std::__alloc_swap<typename _Base::_Node_alloc_type>::
1120 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator());
1149 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1157 _M_check_equal_allocators(__x);
1159 this->_M_transfer(__position, __x.
begin(), __x.
end());
1173 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1181 if (__position == __i || __position == __j)
1185 _M_check_equal_allocators(__x);
1187 this->_M_transfer(__position, __i, __j);
1203 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1211 if (__first != __last)
1214 _M_check_equal_allocators(__x);
1216 this->_M_transfer(__position, __first, __last);
1232 remove(
const _Tp& __value);
1245 template<
typename _Predicate>
1247 remove_if(_Predicate);
1274 template<
typename _BinaryPredicate>
1276 unique(_BinaryPredicate);
1288 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1306 template<
typename _StrictWeakOrdering>
1308 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1309 merge(
list&&, _StrictWeakOrdering);
1311 merge(
list&, _StrictWeakOrdering);
1321 { this->_M_impl._M_node.reverse(); }
1338 template<
typename _StrictWeakOrdering>
1340 sort(_StrictWeakOrdering);
1349 template<
typename _Integer>
1351 _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type)
1352 { _M_fill_initialize(static_cast<size_type>(__n), __x); }
1355 template<
typename _InputIterator>
1357 _M_initialize_dispatch(_InputIterator __first, _InputIterator __last,
1360 for (; __first != __last; ++__first)
1361 push_back(*__first);
1367 _M_fill_initialize(size_type __n,
const value_type& __x)
1369 for (; __n > 0; --__n)
1380 template<
typename _Integer>
1382 _M_assign_dispatch(_Integer __n, _Integer __val, __true_type)
1383 { _M_fill_assign(__n, __val); }
1386 template<
typename _InputIterator>
1388 _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1394 _M_fill_assign(size_type __n,
const value_type& __val);
1399 _M_transfer(iterator __position, iterator __first, iterator __last)
1400 { __position._M_node->transfer(__first._M_node, __last._M_node); }
1403 #ifndef __GXX_EXPERIMENTAL_CXX0X__
1405 _M_insert(iterator __position,
const value_type& __x)
1407 _Node* __tmp = _M_create_node(__x);
1408 __tmp->hook(__position._M_node);
1411 template<
typename... _Args>
1413 _M_insert(iterator __position, _Args&&... __args)
1415 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
1416 __tmp->hook(__position._M_node);
1422 _M_erase(iterator __position)
1424 __position._M_node->unhook();
1425 _Node* __n =
static_cast<_Node*
>(__position._M_node);
1426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1427 _M_get_Node_allocator().destroy(__n);
1429 _M_get_Tp_allocator().destroy(&__n->_M_data);
1436 _M_check_equal_allocators(list& __x)
1438 if (std::__alloc_neq<typename _Base::_Node_alloc_type>::
1439 _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()))
1440 __throw_runtime_error(__N(
"list::_M_check_equal_allocators"));
1454 template<
typename _Tp,
typename _Alloc>
1459 const_iterator __end1 = __x.
end();
1460 const_iterator __end2 = __y.
end();
1462 const_iterator __i1 = __x.
begin();
1463 const_iterator __i2 = __y.
begin();
1464 while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2)
1469 return __i1 == __end1 && __i2 == __end2;
1483 template<
typename _Tp,
typename _Alloc>
1487 __y.begin(), __y.end()); }
1490 template<
typename _Tp,
typename _Alloc>
1493 {
return !(__x == __y); }
1496 template<
typename _Tp,
typename _Alloc>
1499 {
return __y < __x; }
1502 template<
typename _Tp,
typename _Alloc>
1505 {
return !(__y < __x); }
1508 template<
typename _Tp,
typename _Alloc>
1511 {
return !(__x < __y); }
1514 template<
typename _Tp,
typename _Alloc>
1519 #ifdef __GXX_EXPERIMENTAL_CXX0X__
1520 template<
typename _Tp,
typename _Alloc>
1522 swap(list<_Tp, _Alloc>&& __x, list<_Tp, _Alloc>& __y)
1525 template<
typename _Tp,
typename _Alloc>
1527 swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>&& __y)
1531 _GLIBCXX_END_NESTED_NAMESPACE
size_type max_size() const
const_reverse_iterator rend() const
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
const_reference back() const
void push_front(const value_type &__x)
Add data to the front of the list.
_Node * _M_create_node(_Args &&...__args)
list & operator=(initializer_list< value_type > __l)
List initializer list assignment operator.
iterator erase(iterator __first, iterator __last)
Remove a range of elements.
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
void splice(iterator __position, list &&__x, iterator __first, iterator __last)
Insert range from another list.
void pop_back()
Removes last element.
bool operator>=(const list< _Tp, _Alloc > &__x, const list< _Tp, _Alloc > &__y)
Based on operator<.
bool operator==(const list< _Tp, _Alloc > &__x, const list< _Tp, _Alloc > &__y)
List equality comparison.
Bidirectional iterators support a superset of forward iterator operations.
void assign(size_type __n, const value_type &__val)
Assigns a given value to a list.
const_iterator cbegin() const
void swap(list &&__x)
Swaps data with another list.
list(list &&__x)
List move constructor.
iterator insert(iterator __position, value_type &&__x)
Inserts given rvalue into list before specified iterator.
list(size_type __n, const value_type &__value=value_type(), const allocator_type &__a=allocator_type())
Creates a list with copies of an exemplar element.
const_reverse_iterator crend() const
reverse_iterator rbegin()
list & operator=(list &&__x)
List move assignment operator.
void reverse()
Reverse the elements in list.
void push_back(const value_type &__x)
Add data to the end of the list.
const_iterator begin() const
void splice(iterator __position, list &&__x, iterator __i)
Insert element from another list.
const_reference front() const
const_reverse_iterator rbegin() const
allocator_type get_allocator() const
Get a copy of the memory allocation object.
void insert(iterator __position, _InputIterator __first, _InputIterator __last)
Inserts a range into the list.
_OI move(_II __first, _II __last, _OI __result)
Moves the range [first,last) into result.
list(_InputIterator __first, _InputIterator __last, const allocator_type &__a=allocator_type())
Builds a list from a range.
void insert(iterator __p, initializer_list< value_type > __l)
Inserts the contents of an initializer_list into list before specified iterator.
void assign(initializer_list< value_type > __l)
Assigns an initializer_list to a list.
_Tp _M_data
< User's data.
void splice(iterator __position, list &&__x)
Insert contents of another list.
const_iterator end() const
Common part of a node in the list.
list(const list &__x)
List copy constructor.
void pop_front()
Removes first element.
bool operator>(const list< _Tp, _Alloc > &__x, const list< _Tp, _Alloc > &__y)
Based on operator<.
void insert(iterator __position, size_type __n, const value_type &__x)
Inserts a number of copies of given data into the list.
const_iterator cend() const
const_reverse_iterator crbegin() const
bool operator!=(const list< _Tp, _Alloc > &__x, const list< _Tp, _Alloc > &__y)
Based on operator==.
bool lexicographical_compare(_II1 __first1, _II1 __last1, _II2 __first2, _II2 __last2, _Compare __comp)
Performs "dictionary" comparison on ranges.
list(const allocator_type &__a)
Creates a list with no elements.
void assign(_InputIterator __first, _InputIterator __last)
Assigns a range to a list.
list()
Default constructor creates no elements.
An actual node in the list.
list(initializer_list< value_type > __l, const allocator_type &__a=allocator_type())
Builds a list from an initializer_list.
See bits/stl_deque.h's _Deque_base for an explanation.