blob: 345f24dbbe4d02a1b7fb14ea1cb6b3df214333f4 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===---------------------------- list ------------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
Howard Hinnantb64f8b02010-11-16 22:09:02 +00006// This file is dual licensed under the MIT and the University of Illinois Open
7// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00008//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_LIST
12#define _LIBCPP_LIST
13
14/*
15 list synopsis
16
17namespace std
18{
19
20template <class T, class Alloc = allocator<T> >
21class list
22{
23public:
24
25 // types:
26 typedef T value_type;
27 typedef Alloc allocator_type;
28 typedef typename allocator_type::reference reference;
29 typedef typename allocator_type::const_reference const_reference;
30 typedef typename allocator_type::pointer pointer;
31 typedef typename allocator_type::const_pointer const_pointer;
32 typedef implementation-defined iterator;
33 typedef implementation-defined const_iterator;
34 typedef implementation-defined size_type;
35 typedef implementation-defined difference_type;
36 typedef reverse_iterator<iterator> reverse_iterator;
37 typedef reverse_iterator<const_iterator> const_reverse_iterator;
38
Howard Hinnantc5607272011-06-03 17:30:28 +000039 list()
40 noexcept(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000041 explicit list(const allocator_type& a);
42 explicit list(size_type n);
43 list(size_type n, const value_type& value);
44 list(size_type n, const value_type& value, const allocator_type& a);
45 template <class Iter>
46 list(Iter first, Iter last);
47 template <class Iter>
48 list(Iter first, Iter last, const allocator_type& a);
49 list(const list& x);
50 list(const list&, const allocator_type& a);
Howard Hinnantc5607272011-06-03 17:30:28 +000051 list(list&& x)
52 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000053 list(list&&, const allocator_type& a);
54 list(initializer_list<value_type>);
55 list(initializer_list<value_type>, const allocator_type& a);
56
57 ~list();
58
59 list& operator=(const list& x);
Howard Hinnantc5607272011-06-03 17:30:28 +000060 list& operator=(list&& x)
61 noexcept(
62 allocator_type::propagate_on_container_move_assignment::value &&
63 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000064 list& operator=(initializer_list<value_type>);
65 template <class Iter>
66 void assign(Iter first, Iter last);
67 void assign(size_type n, const value_type& t);
68 void assign(initializer_list<value_type>);
69
Howard Hinnantc5607272011-06-03 17:30:28 +000070 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000071
Howard Hinnantc5607272011-06-03 17:30:28 +000072 iterator begin() noexcept;
73 const_iterator begin() const noexcept;
74 iterator end() noexcept;
75 const_iterator end() const noexcept;
76 reverse_iterator rbegin() noexcept;
77 const_reverse_iterator rbegin() const noexcept;
78 reverse_iterator rend() noexcept;
79 const_reverse_iterator rend() const noexcept;
80 const_iterator cbegin() const noexcept;
81 const_iterator cend() const noexcept;
82 const_reverse_iterator crbegin() const noexcept;
83 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000084
85 reference front();
86 const_reference front() const;
87 reference back();
88 const_reference back() const;
89
Howard Hinnantc5607272011-06-03 17:30:28 +000090 bool empty() const noexcept;
91 size_type size() const noexcept;
92 size_type max_size() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000093
94 template <class... Args>
95 void emplace_front(Args&&... args);
96 void pop_front();
97 template <class... Args>
98 void emplace_back(Args&&... args);
99 void pop_back();
100 void push_front(const value_type& x);
101 void push_front(value_type&& x);
102 void push_back(const value_type& x);
103 void push_back(value_type&& x);
104 template <class... Args>
105 iterator emplace(const_iterator position, Args&&... args);
106 iterator insert(const_iterator position, const value_type& x);
107 iterator insert(const_iterator position, value_type&& x);
108 iterator insert(const_iterator position, size_type n, const value_type& x);
109 template <class Iter>
110 iterator insert(const_iterator position, Iter first, Iter last);
111 iterator insert(const_iterator position, initializer_list<value_type> il);
112
113 iterator erase(const_iterator position);
114 iterator erase(const_iterator position, const_iterator last);
115
116 void resize(size_type sz);
117 void resize(size_type sz, const value_type& c);
118
Howard Hinnantc5607272011-06-03 17:30:28 +0000119 void swap(list&)
120 noexcept(!allocator_type::propagate_on_container_swap::value ||
121 __is_nothrow_swappable<allocator_type>::value);
122 void clear() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000123
124 void splice(const_iterator position, list& x);
125 void splice(const_iterator position, list&& x);
126 void splice(const_iterator position, list& x, const_iterator i);
127 void splice(const_iterator position, list&& x, const_iterator i);
128 void splice(const_iterator position, list& x, const_iterator first,
129 const_iterator last);
130 void splice(const_iterator position, list&& x, const_iterator first,
131 const_iterator last);
132
133 void remove(const value_type& value);
134 template <class Pred> void remove_if(Pred pred);
135 void unique();
136 template <class BinaryPredicate>
137 void unique(BinaryPredicate binary_pred);
138 void merge(list& x);
139 void merge(list&& x);
140 template <class Compare>
141 void merge(list& x, Compare comp);
142 template <class Compare>
143 void merge(list&& x, Compare comp);
144 void sort();
145 template <class Compare>
146 void sort(Compare comp);
Howard Hinnantc5607272011-06-03 17:30:28 +0000147 void reverse() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000148};
149
150template <class T, class Alloc>
151 bool operator==(const list<T,Alloc>& x, const list<T,Alloc>& y);
152template <class T, class Alloc>
153 bool operator< (const list<T,Alloc>& x, const list<T,Alloc>& y);
154template <class T, class Alloc>
155 bool operator!=(const list<T,Alloc>& x, const list<T,Alloc>& y);
156template <class T, class Alloc>
157 bool operator> (const list<T,Alloc>& x, const list<T,Alloc>& y);
158template <class T, class Alloc>
159 bool operator>=(const list<T,Alloc>& x, const list<T,Alloc>& y);
160template <class T, class Alloc>
161 bool operator<=(const list<T,Alloc>& x, const list<T,Alloc>& y);
162
163template <class T, class Alloc>
Howard Hinnantc5607272011-06-03 17:30:28 +0000164 void swap(list<T,Alloc>& x, list<T,Alloc>& y)
165 noexcept(noexcept(x.swap(y)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000166
167} // std
168
169*/
170
171#include <__config>
172
173#include <memory>
174#include <limits>
175#include <initializer_list>
176#include <iterator>
177#include <algorithm>
178
Howard Hinnant08e17472011-10-17 20:05:10 +0000179#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000180#pragma GCC system_header
Howard Hinnant08e17472011-10-17 20:05:10 +0000181#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000182
183_LIBCPP_BEGIN_NAMESPACE_STD
184
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000185template <class _Tp, class _VoidPtr> struct __list_node;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000186
187template <class _Tp, class _VoidPtr>
188struct __list_node_base
189{
190 typedef typename pointer_traits<_VoidPtr>::template
191#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
192 rebind<__list_node<_Tp, _VoidPtr> > pointer;
193#else
194 rebind<__list_node<_Tp, _VoidPtr> >::other pointer;
195#endif
196
197 pointer __prev_;
198 pointer __next_;
199
Howard Hinnant82894812010-09-22 16:48:34 +0000200 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000201 __list_node_base()
202 : __prev_(static_cast<pointer>(this)),
203 __next_(static_cast<pointer>(this))
204 {}
205};
206
207template <class _Tp, class _VoidPtr>
208struct __list_node
209 : public __list_node_base<_Tp, _VoidPtr>
210{
211 _Tp __value_;
212};
213
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000214template <class _Tp, class _Alloc> class list;
215template <class _Tp, class _Alloc> class __list_imp;
216template <class _Tp, class _VoidPtr> class __list_const_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000217
218template <class _Tp, class _VoidPtr>
Howard Hinnant82894812010-09-22 16:48:34 +0000219class _LIBCPP_VISIBLE __list_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000220{
221 typedef typename pointer_traits<_VoidPtr>::template
222#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
223 rebind<__list_node<_Tp, _VoidPtr> > __node_pointer;
224#else
225 rebind<__list_node<_Tp, _VoidPtr> >::other __node_pointer;
226#endif
227
228 __node_pointer __ptr_;
229
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000230#if _LIBCPP_DEBUG_LEVEL >= 2
231 _LIBCPP_INLINE_VISIBILITY
232 explicit __list_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
233 : __ptr_(__p)
234 {
235 __get_db()->__insert_ic(this, __c);
236 }
237#else
Howard Hinnant82894812010-09-22 16:48:34 +0000238 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000239 explicit __list_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000240#endif
241
242
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000243
244 template<class, class> friend class list;
245 template<class, class> friend class __list_imp;
246 template<class, class> friend class __list_const_iterator;
247public:
248 typedef bidirectional_iterator_tag iterator_category;
249 typedef _Tp value_type;
250 typedef value_type& reference;
251 typedef typename pointer_traits<_VoidPtr>::template
252#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
253 rebind<value_type>
254#else
255 rebind<value_type>::other
256#endif
257 pointer;
258 typedef typename pointer_traits<pointer>::difference_type difference_type;
259
Howard Hinnant82894812010-09-22 16:48:34 +0000260 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000261 __list_iterator() _NOEXCEPT
262 {
263#if _LIBCPP_DEBUG_LEVEL >= 2
264 __get_db()->__insert_i(this);
265#endif
266 }
267
268#if _LIBCPP_DEBUG_LEVEL >= 2
269
Howard Hinnant211f0ee2011-01-28 23:46:28 +0000270 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000271 __list_iterator(const __list_iterator& __p)
272 : __ptr_(__p.__ptr_)
273 {
274 __get_db()->__iterator_copy(this, &__p);
275 }
276
277 _LIBCPP_INLINE_VISIBILITY
278 ~__list_iterator()
279 {
280 __get_db()->__erase_i(this);
281 }
282
283 _LIBCPP_INLINE_VISIBILITY
284 __list_iterator& operator=(const __list_iterator& __p)
285 {
286 if (this != &__p)
287 {
288 __get_db()->__iterator_copy(this, &__p);
289 __ptr_ = __p.__ptr_;
290 }
291 return *this;
292 }
293
294#endif // _LIBCPP_DEBUG_LEVEL >= 2
295
296 _LIBCPP_INLINE_VISIBILITY
297 reference operator*() const
298 {
299#if _LIBCPP_DEBUG_LEVEL >= 2
300 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
301 "Attempted to dereference a non-dereferenceable list::iterator");
302#endif
303 return __ptr_->__value_;
304 }
Howard Hinnant82894812010-09-22 16:48:34 +0000305 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000306 pointer operator->() const {return &(operator*());}
307
Howard Hinnant82894812010-09-22 16:48:34 +0000308 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000309 __list_iterator& operator++()
310 {
311#if _LIBCPP_DEBUG_LEVEL >= 2
312 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
313 "Attempted to increment non-incrementable list::iterator");
314#endif
315 __ptr_ = __ptr_->__next_;
316 return *this;
317 }
Howard Hinnant82894812010-09-22 16:48:34 +0000318 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000319 __list_iterator operator++(int) {__list_iterator __t(*this); ++(*this); return __t;}
320
Howard Hinnant82894812010-09-22 16:48:34 +0000321 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000322 __list_iterator& operator--()
323 {
324#if _LIBCPP_DEBUG_LEVEL >= 2
325 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
326 "Attempted to decrement non-decrementable list::iterator");
327#endif
328 __ptr_ = __ptr_->__prev_;
329 return *this;
330 }
Howard Hinnant82894812010-09-22 16:48:34 +0000331 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000332 __list_iterator operator--(int) {__list_iterator __t(*this); --(*this); return __t;}
333
Howard Hinnant82894812010-09-22 16:48:34 +0000334 friend _LIBCPP_INLINE_VISIBILITY
335 bool operator==(const __list_iterator& __x, const __list_iterator& __y)
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000336 {
337#if _LIBCPP_DEBUG_LEVEL >= 2
338 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
339 "Attempted to compare non-comparable list::iterator");
340#endif
341 return __x.__ptr_ == __y.__ptr_;
342 }
Howard Hinnant82894812010-09-22 16:48:34 +0000343 friend _LIBCPP_INLINE_VISIBILITY
344 bool operator!=(const __list_iterator& __x, const __list_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000345 {return !(__x == __y);}
346};
347
348template <class _Tp, class _VoidPtr>
Howard Hinnant82894812010-09-22 16:48:34 +0000349class _LIBCPP_VISIBLE __list_const_iterator
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000350{
351 typedef typename pointer_traits<_VoidPtr>::template
352#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
353 rebind<const __list_node<_Tp, _VoidPtr> > __node_pointer;
354#else
355 rebind<const __list_node<_Tp, _VoidPtr> >::other __node_pointer;
356#endif
357
358 __node_pointer __ptr_;
359
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000360#if _LIBCPP_DEBUG_LEVEL >= 2
361 _LIBCPP_INLINE_VISIBILITY
362 explicit __list_const_iterator(__node_pointer __p, const void* __c) _NOEXCEPT
363 : __ptr_(__p)
364 {
365 __get_db()->__insert_ic(this, __c);
366 }
367#else
Howard Hinnant82894812010-09-22 16:48:34 +0000368 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000369 explicit __list_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {}
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000370#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000371
372 template<class, class> friend class list;
373 template<class, class> friend class __list_imp;
374public:
375 typedef bidirectional_iterator_tag iterator_category;
376 typedef _Tp value_type;
377 typedef const value_type& reference;
378 typedef typename pointer_traits<_VoidPtr>::template
379#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
380 rebind<const value_type>
381#else
382 rebind<const value_type>::other
383#endif
384 pointer;
385 typedef typename pointer_traits<pointer>::difference_type difference_type;
386
Howard Hinnant82894812010-09-22 16:48:34 +0000387 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000388 __list_const_iterator() _NOEXCEPT
389 {
390#if _LIBCPP_DEBUG_LEVEL >= 2
391 __get_db()->__insert_i(this);
392#endif
393 }
Howard Hinnant211f0ee2011-01-28 23:46:28 +0000394 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000395 __list_const_iterator(__list_iterator<_Tp, _VoidPtr> __p) _NOEXCEPT
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000396 : __ptr_(__p.__ptr_)
397 {
398#if _LIBCPP_DEBUG_LEVEL >= 2
399 __get_db()->__iterator_copy(this, &__p);
400#endif
401 }
402
403#if _LIBCPP_DEBUG_LEVEL >= 2
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000404
Howard Hinnant82894812010-09-22 16:48:34 +0000405 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000406 __list_const_iterator(const __list_const_iterator& __p)
407 : __ptr_(__p.__ptr_)
408 {
409 __get_db()->__iterator_copy(this, &__p);
410 }
411
412 _LIBCPP_INLINE_VISIBILITY
413 ~__list_const_iterator()
414 {
415 __get_db()->__erase_i(this);
416 }
417
418 _LIBCPP_INLINE_VISIBILITY
419 __list_const_iterator& operator=(const __list_const_iterator& __p)
420 {
421 if (this != &__p)
422 {
423 __get_db()->__iterator_copy(this, &__p);
424 __ptr_ = __p.__ptr_;
425 }
426 return *this;
427 }
428
429#endif // _LIBCPP_DEBUG_LEVEL >= 2
430 _LIBCPP_INLINE_VISIBILITY
431 reference operator*() const
432 {
433#if _LIBCPP_DEBUG_LEVEL >= 2
434 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
435 "Attempted to dereference a non-dereferenceable list::const_iterator");
436#endif
437 return __ptr_->__value_;
438 }
Howard Hinnant82894812010-09-22 16:48:34 +0000439 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000440 pointer operator->() const {return &(operator*());}
441
Howard Hinnant82894812010-09-22 16:48:34 +0000442 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000443 __list_const_iterator& operator++()
444 {
445#if _LIBCPP_DEBUG_LEVEL >= 2
446 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
447 "Attempted to increment non-incrementable list::const_iterator");
448#endif
449 __ptr_ = __ptr_->__next_;
450 return *this;
451 }
Howard Hinnant82894812010-09-22 16:48:34 +0000452 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000453 __list_const_iterator operator++(int) {__list_const_iterator __t(*this); ++(*this); return __t;}
454
Howard Hinnant82894812010-09-22 16:48:34 +0000455 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000456 __list_const_iterator& operator--()
457 {
458#if _LIBCPP_DEBUG_LEVEL >= 2
459 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
460 "Attempted to decrement non-decrementable list::const_iterator");
461#endif
462 __ptr_ = __ptr_->__prev_;
463 return *this;
464 }
Howard Hinnant82894812010-09-22 16:48:34 +0000465 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000466 __list_const_iterator operator--(int) {__list_const_iterator __t(*this); --(*this); return __t;}
467
Howard Hinnant82894812010-09-22 16:48:34 +0000468 friend _LIBCPP_INLINE_VISIBILITY
469 bool operator==(const __list_const_iterator& __x, const __list_const_iterator& __y)
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000470 {
471#if _LIBCPP_DEBUG_LEVEL >= 2
472 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
473 "Attempted to compare non-comparable list::const_iterator");
474#endif
475 return __x.__ptr_ == __y.__ptr_;
476 }
Howard Hinnant82894812010-09-22 16:48:34 +0000477 friend _LIBCPP_INLINE_VISIBILITY
478 bool operator!=(const __list_const_iterator& __x, const __list_const_iterator& __y)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000479 {return !(__x == __y);}
480};
481
482template <class _Tp, class _Alloc>
483class __list_imp
484{
485 __list_imp(const __list_imp&);
486 __list_imp& operator=(const __list_imp&);
487protected:
488 typedef _Tp value_type;
489 typedef _Alloc allocator_type;
490 typedef allocator_traits<allocator_type> __alloc_traits;
491 typedef typename __alloc_traits::size_type size_type;
492 typedef typename __alloc_traits::void_pointer __void_pointer;
493 typedef __list_iterator<value_type, __void_pointer> iterator;
494 typedef __list_const_iterator<value_type, __void_pointer> const_iterator;
495 typedef __list_node_base<value_type, __void_pointer> __node_base;
496 typedef __list_node<value_type, __void_pointer> __node;
497 typedef typename __alloc_traits::template
498#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES
499 rebind_alloc<__node>
500#else
501 rebind_alloc<__node>::other
502#endif
503 __node_allocator;
504 typedef allocator_traits<__node_allocator> __node_alloc_traits;
505 typedef typename __node_alloc_traits::pointer __node_pointer;
506 typedef typename __node_alloc_traits::const_pointer __node_const_pointer;
507 typedef typename __alloc_traits::pointer pointer;
508 typedef typename __alloc_traits::const_pointer const_pointer;
509 typedef typename __alloc_traits::difference_type difference_type;
510
511 __node_base __end_;
512 __compressed_pair<size_type, __node_allocator> __size_alloc_;
513
Howard Hinnant82894812010-09-22 16:48:34 +0000514 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000515 size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
Howard Hinnant82894812010-09-22 16:48:34 +0000516 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000517 const size_type& __sz() const _NOEXCEPT
518 {return __size_alloc_.first();}
Howard Hinnant82894812010-09-22 16:48:34 +0000519 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000520 __node_allocator& __node_alloc() _NOEXCEPT
521 {return __size_alloc_.second();}
Howard Hinnant82894812010-09-22 16:48:34 +0000522 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000523 const __node_allocator& __node_alloc() const _NOEXCEPT
524 {return __size_alloc_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000525
Howard Hinnantc5607272011-06-03 17:30:28 +0000526 static void __unlink_nodes(__node_base& __f, __node_base& __l) _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000527
Howard Hinnantc5607272011-06-03 17:30:28 +0000528 __list_imp()
529 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000530 __list_imp(const allocator_type& __a);
531 ~__list_imp();
Howard Hinnantc5607272011-06-03 17:30:28 +0000532 void clear() _NOEXCEPT;
Howard Hinnant82894812010-09-22 16:48:34 +0000533 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000534 bool empty() const _NOEXCEPT {return __sz() == 0;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000535
Howard Hinnant82894812010-09-22 16:48:34 +0000536 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000537 iterator begin() _NOEXCEPT
538 {
539#if _LIBCPP_DEBUG_LEVEL >= 2
540 return iterator(__end_.__next_, this);
541#else
542 return iterator(__end_.__next_);
543#endif
544 }
Howard Hinnant82894812010-09-22 16:48:34 +0000545 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000546 const_iterator begin() const _NOEXCEPT
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000547 {
548#if _LIBCPP_DEBUG_LEVEL >= 2
549 return const_iterator(__end_.__next_, this);
550#else
551 return const_iterator(__end_.__next_);
552#endif
553 }
Howard Hinnant82894812010-09-22 16:48:34 +0000554 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000555 iterator end() _NOEXCEPT
556 {
557#if _LIBCPP_DEBUG_LEVEL >= 2
558 return iterator(static_cast<__node_pointer>(&__end_), this);
559#else
560 return iterator(static_cast<__node_pointer>(&__end_));
561#endif
562 }
Howard Hinnant82894812010-09-22 16:48:34 +0000563 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000564 const_iterator end() const _NOEXCEPT
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000565 {
566#if _LIBCPP_DEBUG_LEVEL >= 2
567 return const_iterator(static_cast<__node_const_pointer>(&__end_), this);
568#else
569 return const_iterator(static_cast<__node_const_pointer>(&__end_));
570#endif
571 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000572
Howard Hinnantc5607272011-06-03 17:30:28 +0000573 void swap(__list_imp& __c)
574 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
575 __is_nothrow_swappable<__node_allocator>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000576
Howard Hinnant82894812010-09-22 16:48:34 +0000577 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000578 void __copy_assign_alloc(const __list_imp& __c)
579 {__copy_assign_alloc(__c, integral_constant<bool,
580 __node_alloc_traits::propagate_on_container_copy_assignment::value>());}
581
Howard Hinnant82894812010-09-22 16:48:34 +0000582 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000583 void __move_assign_alloc(__list_imp& __c)
Howard Hinnantc5607272011-06-03 17:30:28 +0000584 _NOEXCEPT_(
585 !__node_alloc_traits::propagate_on_container_move_assignment::value ||
586 is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000587 {__move_assign_alloc(__c, integral_constant<bool,
588 __node_alloc_traits::propagate_on_container_move_assignment::value>());}
589
590private:
Howard Hinnant82894812010-09-22 16:48:34 +0000591 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000592 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y)
Howard Hinnantc5607272011-06-03 17:30:28 +0000593 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
594 __is_nothrow_swappable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000595 {__swap_alloc(__x, __y, integral_constant<bool,
596 __node_alloc_traits::propagate_on_container_swap::value>());}
Howard Hinnant82894812010-09-22 16:48:34 +0000597 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000598 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, true_type)
Howard Hinnantc5607272011-06-03 17:30:28 +0000599 _NOEXCEPT_(__is_nothrow_swappable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000600 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000601 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000602 swap(__x, __y);
603 }
Howard Hinnant82894812010-09-22 16:48:34 +0000604 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000605 static void __swap_alloc(__node_allocator& __x, __node_allocator& __y, false_type)
Howard Hinnantc5607272011-06-03 17:30:28 +0000606 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000607 {}
608
Howard Hinnant82894812010-09-22 16:48:34 +0000609 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000610 void __copy_assign_alloc(const __list_imp& __c, true_type)
611 {
612 if (__node_alloc() != __c.__node_alloc())
613 clear();
614 __node_alloc() = __c.__node_alloc();
615 }
616
Howard Hinnant82894812010-09-22 16:48:34 +0000617 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000618 void __copy_assign_alloc(const __list_imp& __c, false_type)
619 {}
620
Howard Hinnant82894812010-09-22 16:48:34 +0000621 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +0000622 void __move_assign_alloc(__list_imp& __c, true_type)
Howard Hinnantc5607272011-06-03 17:30:28 +0000623 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000624 {
Howard Hinnant0949eed2011-06-30 21:18:19 +0000625 __node_alloc() = _VSTD::move(__c.__node_alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000626 }
627
Howard Hinnant82894812010-09-22 16:48:34 +0000628 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant9cbee432011-09-02 20:42:31 +0000629 void __move_assign_alloc(__list_imp& __c, false_type)
Howard Hinnantc5607272011-06-03 17:30:28 +0000630 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000631 {}
632};
633
634// Unlink nodes [__f, __l]
635template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +0000636inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000637void
638__list_imp<_Tp, _Alloc>::__unlink_nodes(__node_base& __f, __node_base& __l)
Howard Hinnantc5607272011-06-03 17:30:28 +0000639 _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000640{
641 __f.__prev_->__next_ = __l.__next_;
642 __l.__next_->__prev_ = __f.__prev_;
643}
644
645template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +0000646inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000647__list_imp<_Tp, _Alloc>::__list_imp()
Howard Hinnantc5607272011-06-03 17:30:28 +0000648 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000649 : __size_alloc_(0)
650{
651}
652
653template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +0000654inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000655__list_imp<_Tp, _Alloc>::__list_imp(const allocator_type& __a)
656 : __size_alloc_(0, __node_allocator(__a))
657{
658}
659
660template <class _Tp, class _Alloc>
661__list_imp<_Tp, _Alloc>::~__list_imp()
662{
663 clear();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000664#if _LIBCPP_DEBUG_LEVEL >= 2
665 __get_db()->__erase_c(this);
666#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000667}
668
669template <class _Tp, class _Alloc>
670void
Howard Hinnantc5607272011-06-03 17:30:28 +0000671__list_imp<_Tp, _Alloc>::clear() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000672{
673 if (!empty())
674 {
675 __node_allocator& __na = __node_alloc();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000676 __node_pointer __f = __end_.__next_;
677 __node_pointer __l = static_cast<__node_pointer>(&__end_);
678 __unlink_nodes(*__f, *__l->__prev_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000679 __sz() = 0;
680 while (__f != __l)
681 {
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000682 __node& __n = *__f;
683 __f = __f->__next_;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000684 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
685 __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000686 }
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000687#if _LIBCPP_DEBUG_LEVEL >= 2
688 __c_node* __c = __get_db()->__find_c_and_lock(this);
689 for (__i_node** __p = __c->end_; __p != __c->beg_; )
690 {
691 --__p;
692 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
693 if (__i->__ptr_ != __l)
694 {
695 (*__p)->__c_ = nullptr;
696 if (--__c->end_ != __p)
697 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
698 }
699 }
700 __get_db()->unlock();
701#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000702 }
703}
704
705template <class _Tp, class _Alloc>
706void
707__list_imp<_Tp, _Alloc>::swap(__list_imp& __c)
Howard Hinnantc5607272011-06-03 17:30:28 +0000708 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
709 __is_nothrow_swappable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000710{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000711 _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
712 this->__node_alloc() == __c.__node_alloc(),
713 "list::swap: Either propagate_on_container_swap must be true"
714 " or the allocators must compare equal");
Howard Hinnant0949eed2011-06-30 21:18:19 +0000715 using _VSTD::swap;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000716 __swap_alloc(__node_alloc(), __c.__node_alloc());
717 swap(__sz(), __c.__sz());
718 swap(__end_, __c.__end_);
719 if (__sz() == 0)
720 __end_.__next_ = __end_.__prev_ = &static_cast<__node&>(__end_);
721 else
722 __end_.__prev_->__next_ = __end_.__next_->__prev_
723 = &static_cast<__node&>(__end_);
724 if (__c.__sz() == 0)
725 __c.__end_.__next_ = __c.__end_.__prev_
726 = &static_cast<__node&>(__c.__end_);
727 else
728 __c.__end_.__prev_->__next_ = __c.__end_.__next_->__prev_
729 = &static_cast<__node&>(__c.__end_);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000730#if _LIBCPP_DEBUG_LEVEL >= 2
731 __libcpp_db* __db = __get_db();
732 __c_node* __cn1 = __db->__find_c_and_lock(this);
733 __c_node* __cn2 = __db->__find_c(&__c);
734 std::swap(__cn1->beg_, __cn2->beg_);
735 std::swap(__cn1->end_, __cn2->end_);
736 std::swap(__cn1->cap_, __cn2->cap_);
737 for (__i_node** __p = __cn1->end_; __p != __cn1->beg_;)
738 {
739 --__p;
740 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
741 if (__i->__ptr_ == static_cast<__node_pointer>(&__c.__end_))
742 {
743 __cn2->__add(*__p);
744 if (--__cn1->end_ != __p)
745 memmove(__p, __p+1, (__cn1->end_ - __p)*sizeof(__i_node*));
746 }
747 else
748 (*__p)->__c_ = __cn1;
749 }
750 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
751 {
752 --__p;
753 const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
754 if (__i->__ptr_ == static_cast<__node_pointer>(&__end_))
755 {
756 __cn1->__add(*__p);
757 if (--__cn2->end_ != __p)
758 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
759 }
760 else
761 (*__p)->__c_ = __cn2;
762 }
763 __db->unlock();
764#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000765}
766
767template <class _Tp, class _Alloc = allocator<_Tp> >
Howard Hinnant82894812010-09-22 16:48:34 +0000768class _LIBCPP_VISIBLE list
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000769 : private __list_imp<_Tp, _Alloc>
770{
771 typedef __list_imp<_Tp, _Alloc> base;
772 typedef typename base::__node __node;
773 typedef typename base::__node_allocator __node_allocator;
774 typedef typename base::__node_pointer __node_pointer;
775 typedef typename base::__node_alloc_traits __node_alloc_traits;
776
777public:
778 typedef _Tp value_type;
779 typedef _Alloc allocator_type;
780 static_assert((is_same<value_type, typename allocator_type::value_type>::value),
781 "Invalid allocator::value_type");
782 typedef value_type& reference;
783 typedef const value_type& const_reference;
784 typedef typename base::pointer pointer;
785 typedef typename base::const_pointer const_pointer;
786 typedef typename base::size_type size_type;
787 typedef typename base::difference_type difference_type;
788 typedef typename base::iterator iterator;
789 typedef typename base::const_iterator const_iterator;
Howard Hinnant0949eed2011-06-30 21:18:19 +0000790 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
791 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000792
Howard Hinnant82894812010-09-22 16:48:34 +0000793 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000794 list()
795 _NOEXCEPT_(is_nothrow_default_constructible<__node_allocator>::value)
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000796 {
797#if _LIBCPP_DEBUG_LEVEL >= 2
798 __get_db()->__insert_c(this);
799#endif
800 }
Howard Hinnant82894812010-09-22 16:48:34 +0000801 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000802 list(const allocator_type& __a) : base(__a)
803 {
804#if _LIBCPP_DEBUG_LEVEL >= 2
805 __get_db()->__insert_c(this);
806#endif
807 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000808 list(size_type __n);
809 list(size_type __n, const value_type& __x);
810 list(size_type __n, const value_type& __x, const allocator_type& __a);
811 template <class _InpIter>
812 list(_InpIter __f, _InpIter __l,
813 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
814 template <class _InpIter>
815 list(_InpIter __f, _InpIter __l, const allocator_type& __a,
816 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
817
818 list(const list& __c);
819 list(const list& __c, const allocator_type& __a);
820 list& operator=(const list& __c);
Howard Hinnante3e32912011-08-12 21:56:02 +0000821#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000822 list(initializer_list<value_type> __il);
823 list(initializer_list<value_type> __il, const allocator_type& __a);
Howard Hinnante3e32912011-08-12 21:56:02 +0000824#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant73d21a42010-09-04 23:28:19 +0000825#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantc5607272011-06-03 17:30:28 +0000826 list(list&& __c)
827 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000828 list(list&& __c, const allocator_type& __a);
Howard Hinnantc5607272011-06-03 17:30:28 +0000829 list& operator=(list&& __c)
830 _NOEXCEPT_(
831 __node_alloc_traits::propagate_on_container_move_assignment::value &&
832 is_nothrow_move_assignable<__node_allocator>::value);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000833#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnante3e32912011-08-12 21:56:02 +0000834#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant82894812010-09-22 16:48:34 +0000835 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000836 list& operator=(initializer_list<value_type> __il)
837 {assign(__il.begin(), __il.end()); return *this;}
Howard Hinnante3e32912011-08-12 21:56:02 +0000838#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000839
840 template <class _InpIter>
841 void assign(_InpIter __f, _InpIter __l,
842 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
843 void assign(size_type __n, const value_type& __x);
Howard Hinnante3e32912011-08-12 21:56:02 +0000844#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant82894812010-09-22 16:48:34 +0000845 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000846 void assign(initializer_list<value_type> __il)
847 {assign(__il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000848#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000849
Howard Hinnantc5607272011-06-03 17:30:28 +0000850 allocator_type get_allocator() const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000851
Howard Hinnant82894812010-09-22 16:48:34 +0000852 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000853 size_type size() const _NOEXCEPT {return base::__sz();}
Howard Hinnant82894812010-09-22 16:48:34 +0000854 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000855 bool empty() const _NOEXCEPT {return base::empty();}
Howard Hinnant82894812010-09-22 16:48:34 +0000856 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000857 size_type max_size() const _NOEXCEPT
858 {return numeric_limits<difference_type>::max();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000859
Howard Hinnant82894812010-09-22 16:48:34 +0000860 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000861 iterator begin() _NOEXCEPT {return base::begin();}
Howard Hinnant82894812010-09-22 16:48:34 +0000862 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000863 const_iterator begin() const _NOEXCEPT {return base::begin();}
Howard Hinnant82894812010-09-22 16:48:34 +0000864 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000865 iterator end() _NOEXCEPT {return base::end();}
Howard Hinnant82894812010-09-22 16:48:34 +0000866 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000867 const_iterator end() const _NOEXCEPT {return base::end();}
Howard Hinnant82894812010-09-22 16:48:34 +0000868 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000869 const_iterator cbegin() const _NOEXCEPT {return base::begin();}
Howard Hinnant82894812010-09-22 16:48:34 +0000870 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000871 const_iterator cend() const _NOEXCEPT {return base::end();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000872
Howard Hinnant82894812010-09-22 16:48:34 +0000873 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000874 reverse_iterator rbegin() _NOEXCEPT
875 {return reverse_iterator(end());}
Howard Hinnant82894812010-09-22 16:48:34 +0000876 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000877 const_reverse_iterator rbegin() const _NOEXCEPT
878 {return const_reverse_iterator(end());}
Howard Hinnant82894812010-09-22 16:48:34 +0000879 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000880 reverse_iterator rend() _NOEXCEPT
881 {return reverse_iterator(begin());}
Howard Hinnant82894812010-09-22 16:48:34 +0000882 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000883 const_reverse_iterator rend() const _NOEXCEPT
884 {return const_reverse_iterator(begin());}
Howard Hinnant82894812010-09-22 16:48:34 +0000885 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000886 const_reverse_iterator crbegin() const _NOEXCEPT
887 {return const_reverse_iterator(end());}
Howard Hinnant82894812010-09-22 16:48:34 +0000888 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000889 const_reverse_iterator crend() const _NOEXCEPT
890 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000891
Howard Hinnant82894812010-09-22 16:48:34 +0000892 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000893 reference front()
894 {
895 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
896 return base::__end_.__next_->__value_;
897 }
Howard Hinnant82894812010-09-22 16:48:34 +0000898 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000899 const_reference front() const
900 {
901 _LIBCPP_ASSERT(!empty(), "list::front called on empty list");
902 return base::__end_.__next_->__value_;
903 }
Howard Hinnant82894812010-09-22 16:48:34 +0000904 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000905 reference back()
906 {
907 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
908 return base::__end_.__prev_->__value_;
909 }
Howard Hinnant82894812010-09-22 16:48:34 +0000910 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +0000911 const_reference back() const
912 {
913 _LIBCPP_ASSERT(!empty(), "list::back called on empty list");
914 return base::__end_.__prev_->__value_;
915 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000916
Howard Hinnant73d21a42010-09-04 23:28:19 +0000917#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000918 void push_front(value_type&& __x);
919 void push_back(value_type&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000920#ifndef _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000921 template <class... _Args>
922 void emplace_front(_Args&&... __args);
923 template <class... _Args>
924 void emplace_back(_Args&&... __args);
925 template <class... _Args>
926 iterator emplace(const_iterator __p, _Args&&... __args);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000927#endif // _LIBCPP_HAS_NO_VARIADICS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000928 iterator insert(const_iterator __p, value_type&& __x);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000929#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000930
931 void push_front(const value_type& __x);
932 void push_back(const value_type& __x);
933
934 iterator insert(const_iterator __p, const value_type& __x);
935 iterator insert(const_iterator __p, size_type __n, const value_type& __x);
936 template <class _InpIter>
937 iterator insert(const_iterator __p, _InpIter __f, _InpIter __l,
938 typename enable_if<__is_input_iterator<_InpIter>::value>::type* = 0);
Howard Hinnante3e32912011-08-12 21:56:02 +0000939#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnant82894812010-09-22 16:48:34 +0000940 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000941 iterator insert(const_iterator __p, initializer_list<value_type> __il)
942 {return insert(__p, __il.begin(), __il.end());}
Howard Hinnante3e32912011-08-12 21:56:02 +0000943#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000944
Howard Hinnant82894812010-09-22 16:48:34 +0000945 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000946 void swap(list& __c)
947 _NOEXCEPT_(!__node_alloc_traits::propagate_on_container_swap::value ||
948 __is_nothrow_swappable<__node_allocator>::value)
949 {base::swap(__c);}
Howard Hinnant82894812010-09-22 16:48:34 +0000950 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantc5607272011-06-03 17:30:28 +0000951 void clear() _NOEXCEPT {base::clear();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000952
953 void pop_front();
954 void pop_back();
955
956 iterator erase(const_iterator __p);
957 iterator erase(const_iterator __f, const_iterator __l);
958
959 void resize(size_type __n);
960 void resize(size_type __n, const value_type& __x);
961
962 void splice(const_iterator __p, list& __c);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000963#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant82894812010-09-22 16:48:34 +0000964 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000965 void splice(const_iterator __p, list&& __c) {splice(__p, __c);}
966#endif
967 void splice(const_iterator __p, list& __c, const_iterator __i);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000968#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant82894812010-09-22 16:48:34 +0000969 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000970 void splice(const_iterator __p, list&& __c, const_iterator __i)
971 {splice(__p, __c, __i);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000972#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000973 void splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000974#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant82894812010-09-22 16:48:34 +0000975 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000976 void splice(const_iterator __p, list&& __c, const_iterator __f, const_iterator __l)
977 {splice(__p, __c, __f, __l);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000978#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000979
980 void remove(const value_type& __x);
981 template <class _Pred> void remove_if(_Pred __pred);
982 void unique();
983 template <class _BinaryPred>
984 void unique(_BinaryPred __binary_pred);
985 void merge(list& __c);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000986#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant82894812010-09-22 16:48:34 +0000987 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000988 void merge(list&& __c) {merge(__c);}
989#endif
990 template <class _Comp>
991 void merge(list& __c, _Comp __comp);
Howard Hinnant73d21a42010-09-04 23:28:19 +0000992#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000993 template <class _Comp>
Howard Hinnant82894812010-09-22 16:48:34 +0000994 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000995 void merge(list&& __c, _Comp __comp) {merge(__c, __comp);}
Howard Hinnant73d21a42010-09-04 23:28:19 +0000996#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000997 void sort();
998 template <class _Comp>
999 void sort(_Comp __comp);
1000
Howard Hinnantc5607272011-06-03 17:30:28 +00001001 void reverse() _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001002
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001003 bool __invariants() const;
1004
1005#if _LIBCPP_DEBUG_LEVEL >= 2
1006
1007 bool __dereferenceable(const const_iterator* __i) const;
1008 bool __decrementable(const const_iterator* __i) const;
1009 bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
1010 bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
1011
1012#endif // _LIBCPP_DEBUG_LEVEL >= 2
1013
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001014private:
1015 static void __link_nodes(__node& __p, __node& __f, __node& __l);
1016 iterator __iterator(size_type __n);
1017 template <class _Comp>
1018 static iterator __sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp);
1019
Howard Hinnantc5607272011-06-03 17:30:28 +00001020 void __move_assign(list& __c, true_type)
1021 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001022 void __move_assign(list& __c, false_type);
1023};
1024
1025// Link in nodes [__f, __l] just prior to __p
1026template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001027inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001028void
1029list<_Tp, _Alloc>::__link_nodes(__node& __p, __node& __f, __node& __l)
1030{
1031 __p.__prev_->__next_ = &__f;
1032 __f.__prev_ = __p.__prev_;
1033 __p.__prev_ = &__l;
1034 __l.__next_ = &__p;
1035}
1036
1037template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001038inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001039typename list<_Tp, _Alloc>::iterator
1040list<_Tp, _Alloc>::__iterator(size_type __n)
1041{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001042 return __n <= base::__sz() / 2 ? _VSTD::next(begin(), __n)
1043 : _VSTD::prev(end(), base::__sz() - __n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001044}
1045
1046template <class _Tp, class _Alloc>
1047list<_Tp, _Alloc>::list(size_type __n)
1048{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001049#if _LIBCPP_DEBUG_LEVEL >= 2
1050 __get_db()->__insert_c(this);
1051#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001052 for (; __n > 0; --__n)
Howard Hinnant73d21a42010-09-04 23:28:19 +00001053#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001054 emplace_back();
1055#else
1056 push_back(value_type());
1057#endif
1058}
1059
1060template <class _Tp, class _Alloc>
1061list<_Tp, _Alloc>::list(size_type __n, const value_type& __x)
1062{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001063#if _LIBCPP_DEBUG_LEVEL >= 2
1064 __get_db()->__insert_c(this);
1065#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001066 for (; __n > 0; --__n)
1067 push_back(__x);
1068}
1069
1070template <class _Tp, class _Alloc>
1071list<_Tp, _Alloc>::list(size_type __n, const value_type& __x, const allocator_type& __a)
1072 : base(__a)
1073{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001074#if _LIBCPP_DEBUG_LEVEL >= 2
1075 __get_db()->__insert_c(this);
1076#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001077 for (; __n > 0; --__n)
1078 push_back(__x);
1079}
1080
1081template <class _Tp, class _Alloc>
1082template <class _InpIter>
1083list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l,
1084 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1085{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001086#if _LIBCPP_DEBUG_LEVEL >= 2
1087 __get_db()->__insert_c(this);
1088#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001089 for (; __f != __l; ++__f)
1090 push_back(*__f);
1091}
1092
1093template <class _Tp, class _Alloc>
1094template <class _InpIter>
1095list<_Tp, _Alloc>::list(_InpIter __f, _InpIter __l, const allocator_type& __a,
1096 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1097 : base(__a)
1098{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001099#if _LIBCPP_DEBUG_LEVEL >= 2
1100 __get_db()->__insert_c(this);
1101#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001102 for (; __f != __l; ++__f)
1103 push_back(*__f);
1104}
1105
1106template <class _Tp, class _Alloc>
1107list<_Tp, _Alloc>::list(const list& __c)
1108 : base(allocator_type(
1109 __node_alloc_traits::select_on_container_copy_construction(
1110 __c.__node_alloc())))
1111{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001112#if _LIBCPP_DEBUG_LEVEL >= 2
1113 __get_db()->__insert_c(this);
1114#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001115 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1116 push_back(*__i);
1117}
1118
1119template <class _Tp, class _Alloc>
1120list<_Tp, _Alloc>::list(const list& __c, const allocator_type& __a)
1121 : base(__a)
1122{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001123#if _LIBCPP_DEBUG_LEVEL >= 2
1124 __get_db()->__insert_c(this);
1125#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001126 for (const_iterator __i = __c.begin(), __e = __c.end(); __i != __e; ++__i)
1127 push_back(*__i);
1128}
1129
Howard Hinnante3e32912011-08-12 21:56:02 +00001130#ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1131
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001132template <class _Tp, class _Alloc>
1133list<_Tp, _Alloc>::list(initializer_list<value_type> __il, const allocator_type& __a)
1134 : base(__a)
1135{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001136#if _LIBCPP_DEBUG_LEVEL >= 2
1137 __get_db()->__insert_c(this);
1138#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001139 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1140 __e = __il.end(); __i != __e; ++__i)
1141 push_back(*__i);
1142}
1143
1144template <class _Tp, class _Alloc>
1145list<_Tp, _Alloc>::list(initializer_list<value_type> __il)
1146{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001147#if _LIBCPP_DEBUG_LEVEL >= 2
1148 __get_db()->__insert_c(this);
1149#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001150 for (typename initializer_list<value_type>::const_iterator __i = __il.begin(),
1151 __e = __il.end(); __i != __e; ++__i)
1152 push_back(*__i);
1153}
1154
Howard Hinnante3e32912011-08-12 21:56:02 +00001155#endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
1156
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001157template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001158inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001159list<_Tp, _Alloc>&
1160list<_Tp, _Alloc>::operator=(const list& __c)
1161{
1162 if (this != &__c)
1163 {
1164 base::__copy_assign_alloc(__c);
1165 assign(__c.begin(), __c.end());
1166 }
1167 return *this;
1168}
1169
Howard Hinnant73d21a42010-09-04 23:28:19 +00001170#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001171
1172template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001173inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001174list<_Tp, _Alloc>::list(list&& __c)
Howard Hinnantc5607272011-06-03 17:30:28 +00001175 _NOEXCEPT_(is_nothrow_move_constructible<__node_allocator>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001176 : base(allocator_type(_VSTD::move(__c.__node_alloc())))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001177{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001178#if _LIBCPP_DEBUG_LEVEL >= 2
1179 __get_db()->__insert_c(this);
1180#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001181 splice(end(), __c);
1182}
1183
1184template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001185inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001186list<_Tp, _Alloc>::list(list&& __c, const allocator_type& __a)
1187 : base(__a)
1188{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001189#if _LIBCPP_DEBUG_LEVEL >= 2
1190 __get_db()->__insert_c(this);
1191#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001192 if (__a == __c.get_allocator())
1193 splice(end(), __c);
1194 else
1195 {
1196 typedef move_iterator<iterator> _I;
1197 assign(_I(__c.begin()), _I(__c.end()));
1198 }
1199}
1200
1201template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001202inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001203list<_Tp, _Alloc>&
1204list<_Tp, _Alloc>::operator=(list&& __c)
Howard Hinnantc5607272011-06-03 17:30:28 +00001205 _NOEXCEPT_(
1206 __node_alloc_traits::propagate_on_container_move_assignment::value &&
1207 is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001208{
1209 __move_assign(__c, integral_constant<bool,
1210 __node_alloc_traits::propagate_on_container_move_assignment::value>());
1211 return *this;
1212}
1213
1214template <class _Tp, class _Alloc>
1215void
1216list<_Tp, _Alloc>::__move_assign(list& __c, false_type)
1217{
1218 if (base::__node_alloc() != __c.__node_alloc())
1219 {
1220 typedef move_iterator<iterator> _I;
1221 assign(_I(__c.begin()), _I(__c.end()));
1222 }
1223 else
1224 __move_assign(__c, true_type());
1225}
1226
1227template <class _Tp, class _Alloc>
1228void
1229list<_Tp, _Alloc>::__move_assign(list& __c, true_type)
Howard Hinnantc5607272011-06-03 17:30:28 +00001230 _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001231{
1232 clear();
1233 base::__move_assign_alloc(__c);
1234 splice(end(), __c);
1235}
1236
Howard Hinnant73d21a42010-09-04 23:28:19 +00001237#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001238
1239template <class _Tp, class _Alloc>
1240template <class _InpIter>
1241void
1242list<_Tp, _Alloc>::assign(_InpIter __f, _InpIter __l,
1243 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1244{
1245 iterator __i = begin();
1246 iterator __e = end();
1247 for (; __f != __l && __i != __e; ++__f, ++__i)
1248 *__i = *__f;
1249 if (__i == __e)
1250 insert(__e, __f, __l);
1251 else
1252 erase(__i, __e);
1253}
1254
1255template <class _Tp, class _Alloc>
1256void
1257list<_Tp, _Alloc>::assign(size_type __n, const value_type& __x)
1258{
1259 iterator __i = begin();
1260 iterator __e = end();
1261 for (; __n > 0 && __i != __e; --__n, ++__i)
1262 *__i = __x;
1263 if (__i == __e)
1264 insert(__e, __n, __x);
1265 else
1266 erase(__i, __e);
1267}
1268
1269template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001270inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001271_Alloc
Howard Hinnantc5607272011-06-03 17:30:28 +00001272list<_Tp, _Alloc>::get_allocator() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001273{
1274 return allocator_type(base::__node_alloc());
1275}
1276
1277template <class _Tp, class _Alloc>
1278typename list<_Tp, _Alloc>::iterator
1279list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
1280{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001281#if _LIBCPP_DEBUG_LEVEL >= 2
1282 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1283 "list::insert(iterator, x) called with an iterator not"
1284 " referring to this list");
1285#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001286 __node_allocator& __na = base::__node_alloc();
1287 typedef __allocator_destructor<__node_allocator> _D;
1288 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1289 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001290 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001291 __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1292 ++base::__sz();
1293 return iterator(__hold.release());
1294}
1295
1296template <class _Tp, class _Alloc>
1297typename list<_Tp, _Alloc>::iterator
1298list<_Tp, _Alloc>::insert(const_iterator __p, size_type __n, const value_type& __x)
1299{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001300#if _LIBCPP_DEBUG_LEVEL >= 2
1301 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1302 "list::insert(iterator, n, x) called with an iterator not"
1303 " referring to this list");
1304 iterator __r(const_cast<__node_pointer>(__p.__ptr_), this);
1305#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001306 iterator __r(const_cast<__node_pointer>(__p.__ptr_));
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001307#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001308 if (__n > 0)
1309 {
1310 size_type __ds = 0;
1311 __node_allocator& __na = base::__node_alloc();
1312 typedef __allocator_destructor<__node_allocator> _D;
1313 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1314 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001315 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001316 ++__ds;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001317#if _LIBCPP_DEBUG_LEVEL >= 2
1318 __r = iterator(__hold.get(), this);
1319#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001320 __r = iterator(__hold.get());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001321#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001322 __hold.release();
1323 iterator __e = __r;
1324#ifndef _LIBCPP_NO_EXCEPTIONS
1325 try
1326 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001327#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001328 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1329 {
1330 __hold.reset(__node_alloc_traits::allocate(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001331 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001332 __e.__ptr_->__next_ = __hold.get();
1333 __hold->__prev_ = __e.__ptr_;
1334 __hold.release();
1335 }
1336#ifndef _LIBCPP_NO_EXCEPTIONS
1337 }
1338 catch (...)
1339 {
1340 while (true)
1341 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001342 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001343 __node_pointer __prev = __e.__ptr_->__prev_;
1344 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1345 if (__prev == 0)
1346 break;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001347#if _LIBCPP_DEBUG_LEVEL >= 2
1348 __e = iterator(__prev, this);
1349#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001350 __e = iterator(__prev);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001351#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001352 }
1353 throw;
1354 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001355#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001356 __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
1357 base::__sz() += __ds;
1358 }
1359 return __r;
1360}
1361
1362template <class _Tp, class _Alloc>
1363template <class _InpIter>
1364typename list<_Tp, _Alloc>::iterator
1365list<_Tp, _Alloc>::insert(const_iterator __p, _InpIter __f, _InpIter __l,
1366 typename enable_if<__is_input_iterator<_InpIter>::value>::type*)
1367{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001368#if _LIBCPP_DEBUG_LEVEL >= 2
1369 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1370 "list::insert(iterator, range) called with an iterator not"
1371 " referring to this list");
1372 iterator __r(const_cast<__node_pointer>(__p.__ptr_), this);
1373#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001374 iterator __r(const_cast<__node_pointer>(__p.__ptr_));
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001375#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001376 if (__f != __l)
1377 {
1378 size_type __ds = 0;
1379 __node_allocator& __na = base::__node_alloc();
1380 typedef __allocator_destructor<__node_allocator> _D;
1381 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1382 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001383 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001384 ++__ds;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001385#if _LIBCPP_DEBUG_LEVEL >= 2
1386 __r = iterator(__hold.get(), this);
1387#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001388 __r = iterator(__hold.get());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001389#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001390 __hold.release();
1391 iterator __e = __r;
1392#ifndef _LIBCPP_NO_EXCEPTIONS
1393 try
1394 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001395#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001396 for (++__f; __f != __l; ++__f, ++__e, ++__ds)
1397 {
1398 __hold.reset(__node_alloc_traits::allocate(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001399 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), *__f);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001400 __e.__ptr_->__next_ = __hold.get();
1401 __hold->__prev_ = __e.__ptr_;
1402 __hold.release();
1403 }
1404#ifndef _LIBCPP_NO_EXCEPTIONS
1405 }
1406 catch (...)
1407 {
1408 while (true)
1409 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001410 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001411 __node_pointer __prev = __e.__ptr_->__prev_;
1412 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1413 if (__prev == 0)
1414 break;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001415#if _LIBCPP_DEBUG_LEVEL >= 2
1416 __e = iterator(__prev, this);
1417#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001418 __e = iterator(__prev);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001419#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001420 }
1421 throw;
1422 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001423#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001424 __link_nodes(const_cast<__node&>(*__p.__ptr_), *__r.__ptr_, *__e.__ptr_);
1425 base::__sz() += __ds;
1426 }
1427 return __r;
1428}
1429
1430template <class _Tp, class _Alloc>
1431void
1432list<_Tp, _Alloc>::push_front(const value_type& __x)
1433{
1434 __node_allocator& __na = base::__node_alloc();
1435 typedef __allocator_destructor<__node_allocator> _D;
1436 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001437 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001438 __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1439 ++base::__sz();
1440 __hold.release();
1441}
1442
1443template <class _Tp, class _Alloc>
1444void
1445list<_Tp, _Alloc>::push_back(const value_type& __x)
1446{
1447 __node_allocator& __na = base::__node_alloc();
1448 typedef __allocator_destructor<__node_allocator> _D;
1449 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001450 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001451 __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1452 ++base::__sz();
1453 __hold.release();
1454}
1455
Howard Hinnant73d21a42010-09-04 23:28:19 +00001456#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001457
1458template <class _Tp, class _Alloc>
1459void
1460list<_Tp, _Alloc>::push_front(value_type&& __x)
1461{
1462 __node_allocator& __na = base::__node_alloc();
1463 typedef __allocator_destructor<__node_allocator> _D;
1464 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001465 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001466 __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1467 ++base::__sz();
1468 __hold.release();
1469}
1470
1471template <class _Tp, class _Alloc>
1472void
1473list<_Tp, _Alloc>::push_back(value_type&& __x)
1474{
1475 __node_allocator& __na = base::__node_alloc();
1476 typedef __allocator_destructor<__node_allocator> _D;
1477 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001478 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001479 __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1480 ++base::__sz();
1481 __hold.release();
1482}
1483
Howard Hinnant73d21a42010-09-04 23:28:19 +00001484#ifndef _LIBCPP_HAS_NO_VARIADICS
1485
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001486template <class _Tp, class _Alloc>
1487template <class... _Args>
1488void
1489list<_Tp, _Alloc>::emplace_front(_Args&&... __args)
1490{
1491 __node_allocator& __na = base::__node_alloc();
1492 typedef __allocator_destructor<__node_allocator> _D;
1493 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001494 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001495 __link_nodes(*base::__end_.__next_, *__hold, *__hold);
1496 ++base::__sz();
1497 __hold.release();
1498}
1499
1500template <class _Tp, class _Alloc>
1501template <class... _Args>
1502void
1503list<_Tp, _Alloc>::emplace_back(_Args&&... __args)
1504{
1505 __node_allocator& __na = base::__node_alloc();
1506 typedef __allocator_destructor<__node_allocator> _D;
1507 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001508 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001509 __link_nodes(static_cast<__node&>(base::__end_), *__hold, *__hold);
1510 ++base::__sz();
1511 __hold.release();
1512}
1513
1514template <class _Tp, class _Alloc>
1515template <class... _Args>
1516typename list<_Tp, _Alloc>::iterator
1517list<_Tp, _Alloc>::emplace(const_iterator __p, _Args&&... __args)
1518{
1519 __node_allocator& __na = base::__node_alloc();
1520 typedef __allocator_destructor<__node_allocator> _D;
1521 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1522 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001523 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::forward<_Args>(__args)...);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001524 __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1525 ++base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001526#if _LIBCPP_DEBUG_LEVEL >= 2
1527 return iterator(__hold.release(), this);
1528#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001529 return iterator(__hold.release());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001530#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001531}
1532
Howard Hinnant73d21a42010-09-04 23:28:19 +00001533#endif // _LIBCPP_HAS_NO_VARIADICS
1534
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001535template <class _Tp, class _Alloc>
1536typename list<_Tp, _Alloc>::iterator
1537list<_Tp, _Alloc>::insert(const_iterator __p, value_type&& __x)
1538{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001539#if _LIBCPP_DEBUG_LEVEL >= 2
1540 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1541 "list::insert(iterator, x) called with an iterator not"
1542 " referring to this list");
1543#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001544 __node_allocator& __na = base::__node_alloc();
1545 typedef __allocator_destructor<__node_allocator> _D;
1546 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1547 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001548 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), _VSTD::move(__x));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001549 __link_nodes(const_cast<__node&>(*__p.__ptr_), *__hold, *__hold);
1550 ++base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001551#if _LIBCPP_DEBUG_LEVEL >= 2
1552 return iterator(__hold.release(), this);
1553#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001554 return iterator(__hold.release());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001555#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001556}
1557
Howard Hinnant73d21a42010-09-04 23:28:19 +00001558#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001559
1560template <class _Tp, class _Alloc>
1561void
1562list<_Tp, _Alloc>::pop_front()
1563{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001564 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001565 __node_allocator& __na = base::__node_alloc();
1566 __node& __n = *base::__end_.__next_;
1567 base::__unlink_nodes(__n, __n);
1568 --base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001569#if _LIBCPP_DEBUG_LEVEL >= 2
1570 __c_node* __c = __get_db()->__find_c_and_lock(this);
1571 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1572 {
1573 --__p;
1574 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1575 if (__i->__ptr_ == &__n)
1576 {
1577 (*__p)->__c_ = nullptr;
1578 if (--__c->end_ != __p)
1579 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1580 }
1581 }
1582 __get_db()->unlock();
1583#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001584 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1585 __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001586}
1587
1588template <class _Tp, class _Alloc>
1589void
1590list<_Tp, _Alloc>::pop_back()
1591{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001592 _LIBCPP_ASSERT(!empty(), "list::pop_front() called with empty list");
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001593 __node_allocator& __na = base::__node_alloc();
1594 __node& __n = *base::__end_.__prev_;
1595 base::__unlink_nodes(__n, __n);
1596 --base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001597#if _LIBCPP_DEBUG_LEVEL >= 2
1598 __c_node* __c = __get_db()->__find_c_and_lock(this);
1599 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1600 {
1601 --__p;
1602 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1603 if (__i->__ptr_ == &__n)
1604 {
1605 (*__p)->__c_ = nullptr;
1606 if (--__c->end_ != __p)
1607 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1608 }
1609 }
1610 __get_db()->unlock();
1611#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001612 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1613 __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001614}
1615
1616template <class _Tp, class _Alloc>
1617typename list<_Tp, _Alloc>::iterator
1618list<_Tp, _Alloc>::erase(const_iterator __p)
1619{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001620#if _LIBCPP_DEBUG_LEVEL >= 2
1621 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1622 "list::erase(iterator) called with an iterator not"
1623 " referring to this list");
1624#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001625 __node_allocator& __na = base::__node_alloc();
1626 __node& __n = const_cast<__node&>(*__p.__ptr_);
1627 __node_pointer __r = __n.__next_;
1628 base::__unlink_nodes(__n, __n);
1629 --base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001630#if _LIBCPP_DEBUG_LEVEL >= 2
1631 __c_node* __c = __get_db()->__find_c_and_lock(this);
1632 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1633 {
1634 --__p;
1635 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1636 if (__i->__ptr_ == &__n)
1637 {
1638 (*__p)->__c_ = nullptr;
1639 if (--__c->end_ != __p)
1640 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1641 }
1642 }
1643 __get_db()->unlock();
1644#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001645 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1646 __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001647#if _LIBCPP_DEBUG_LEVEL >= 2
1648 return iterator(__r, this);
1649#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001650 return iterator(__r);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001651#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001652}
1653
1654template <class _Tp, class _Alloc>
1655typename list<_Tp, _Alloc>::iterator
1656list<_Tp, _Alloc>::erase(const_iterator __f, const_iterator __l)
1657{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001658#if _LIBCPP_DEBUG_LEVEL >= 2
1659 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == this,
1660 "list::erase(iterator, iterator) called with an iterator not"
1661 " referring to this list");
1662#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001663 if (__f != __l)
1664 {
1665 __node_allocator& __na = base::__node_alloc();
1666 base::__unlink_nodes(const_cast<__node&>(*__f.__ptr_), *__l.__ptr_->__prev_);
1667 while (__f != __l)
1668 {
1669 __node& __n = const_cast<__node&>(*__f.__ptr_);
1670 ++__f;
1671 --base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001672#if _LIBCPP_DEBUG_LEVEL >= 2
1673 __c_node* __c = __get_db()->__find_c_and_lock(this);
1674 for (__i_node** __p = __c->end_; __p != __c->beg_; )
1675 {
1676 --__p;
1677 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1678 if (__i->__ptr_ == &__n)
1679 {
1680 (*__p)->__c_ = nullptr;
1681 if (--__c->end_ != __p)
1682 memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
1683 }
1684 }
1685 __get_db()->unlock();
1686#endif
Howard Hinnant0949eed2011-06-30 21:18:19 +00001687 __node_alloc_traits::destroy(__na, _VSTD::addressof(__n.__value_));
1688 __node_alloc_traits::deallocate(__na, _VSTD::addressof(__n), 1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001689 }
1690 }
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001691#if _LIBCPP_DEBUG_LEVEL >= 2
1692 return iterator(const_cast<__node_pointer>(__l.__ptr_), this);
1693#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001694 return iterator(const_cast<__node_pointer>(__l.__ptr_));
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001695#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001696}
1697
1698template <class _Tp, class _Alloc>
1699void
1700list<_Tp, _Alloc>::resize(size_type __n)
1701{
1702 if (__n < base::__sz())
1703 erase(__iterator(__n), end());
1704 else if (__n > base::__sz())
1705 {
1706 __n -= base::__sz();
1707 size_type __ds = 0;
1708 __node_allocator& __na = base::__node_alloc();
1709 typedef __allocator_destructor<__node_allocator> _D;
1710 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1711 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001712 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001713 ++__ds;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001714#if _LIBCPP_DEBUG_LEVEL >= 2
1715 iterator __r = iterator(__hold.release(), this);
1716#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001717 iterator __r = iterator(__hold.release());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001718#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001719 iterator __e = __r;
1720#ifndef _LIBCPP_NO_EXCEPTIONS
1721 try
1722 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001723#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001724 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1725 {
1726 __hold.reset(__node_alloc_traits::allocate(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001727 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001728 __e.__ptr_->__next_ = __hold.get();
1729 __hold->__prev_ = __e.__ptr_;
1730 __hold.release();
1731 }
1732#ifndef _LIBCPP_NO_EXCEPTIONS
1733 }
1734 catch (...)
1735 {
1736 while (true)
1737 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001738 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001739 __node_pointer __prev = __e.__ptr_->__prev_;
1740 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1741 if (__prev == 0)
1742 break;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001743#if _LIBCPP_DEBUG_LEVEL >= 2
1744 __e = iterator(__prev, this);
1745#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001746 __e = iterator(__prev);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001747#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001748 }
1749 throw;
1750 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001751#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001752 __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1753 base::__sz() += __ds;
1754 }
1755}
1756
1757template <class _Tp, class _Alloc>
1758void
1759list<_Tp, _Alloc>::resize(size_type __n, const value_type& __x)
1760{
1761 if (__n < base::__sz())
1762 erase(__iterator(__n), end());
1763 else if (__n > base::__sz())
1764 {
1765 __n -= base::__sz();
1766 size_type __ds = 0;
1767 __node_allocator& __na = base::__node_alloc();
1768 typedef __allocator_destructor<__node_allocator> _D;
1769 unique_ptr<__node, _D> __hold(__node_alloc_traits::allocate(__na, 1), _D(__na, 1));
1770 __hold->__prev_ = 0;
Howard Hinnant0949eed2011-06-30 21:18:19 +00001771 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001772 ++__ds;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001773#if _LIBCPP_DEBUG_LEVEL >= 2
1774 iterator __r = iterator(__hold.release(), this);
1775#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001776 iterator __r = iterator(__hold.release());
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001777#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001778 iterator __e = __r;
1779#ifndef _LIBCPP_NO_EXCEPTIONS
1780 try
1781 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001782#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001783 for (--__n; __n != 0; --__n, ++__e, ++__ds)
1784 {
1785 __hold.reset(__node_alloc_traits::allocate(__na, 1));
Howard Hinnant0949eed2011-06-30 21:18:19 +00001786 __node_alloc_traits::construct(__na, _VSTD::addressof(__hold->__value_), __x);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001787 __e.__ptr_->__next_ = __hold.get();
1788 __hold->__prev_ = __e.__ptr_;
1789 __hold.release();
1790 }
1791#ifndef _LIBCPP_NO_EXCEPTIONS
1792 }
1793 catch (...)
1794 {
1795 while (true)
1796 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001797 __node_alloc_traits::destroy(__na, _VSTD::addressof(*__e));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001798 __node_pointer __prev = __e.__ptr_->__prev_;
1799 __node_alloc_traits::deallocate(__na, __e.__ptr_, 1);
1800 if (__prev == 0)
1801 break;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001802#if _LIBCPP_DEBUG_LEVEL >= 2
1803 __e = iterator(__prev, this);
1804#else
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001805 __e = iterator(__prev);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001806#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001807 }
1808 throw;
1809 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001810#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001811 __link_nodes(static_cast<__node&>(base::__end_), *__r.__ptr_, *__e.__ptr_);
1812 base::__sz() += __ds;
Howard Hinnant324bb032010-08-22 00:02:43 +00001813 }
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001814}
1815
1816template <class _Tp, class _Alloc>
1817void
1818list<_Tp, _Alloc>::splice(const_iterator __p, list& __c)
1819{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001820 _LIBCPP_ASSERT(this != &__c,
1821 "list::splice(iterator, list) called with this == &list");
1822#if _LIBCPP_DEBUG_LEVEL >= 2
1823 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1824 "list::splice(iterator, list) called with an iterator not"
1825 " referring to this list");
1826#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001827 if (!__c.empty())
1828 {
1829 __node& __f = *__c.__end_.__next_;
1830 __node& __l = *__c.__end_.__prev_;
1831 base::__unlink_nodes(__f, __l);
1832 __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __l);
1833 base::__sz() += __c.__sz();
1834 __c.__sz() = 0;
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001835#if _LIBCPP_DEBUG_LEVEL >= 2
1836 __libcpp_db* __db = __get_db();
1837 __c_node* __cn1 = __db->__find_c_and_lock(this);
1838 __c_node* __cn2 = __db->__find_c(&__c);
1839 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1840 {
1841 --__p;
1842 iterator* __i = static_cast<iterator*>((*__p)->__i_);
1843 if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_))
1844 {
1845 __cn1->__add(*__p);
1846 (*__p)->__c_ = __cn1;
1847 if (--__cn2->end_ != __p)
1848 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1849 }
1850 }
1851 __db->unlock();
1852#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001853 }
1854}
1855
1856template <class _Tp, class _Alloc>
1857void
1858list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __i)
1859{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001860#if _LIBCPP_DEBUG_LEVEL >= 2
1861 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1862 "list::splice(iterator, list, iterator) called with first iterator not"
1863 " referring to this list");
1864 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__i) == &__c,
1865 "list::splice(iterator, list, iterator) called with second iterator not"
1866 " referring to list argument");
1867 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(&__i),
1868 "list::splice(iterator, list, iterator) called with second iterator not"
1869 " derefereceable");
1870#endif
1871 if (__p.__ptr_ != __i.__ptr_ && __p.__ptr_ != __i.__ptr_->__next_)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001872 {
1873 __node& __f = const_cast<__node&>(*__i.__ptr_);
1874 base::__unlink_nodes(__f, __f);
1875 __link_nodes(const_cast<__node&>(*__p.__ptr_), __f, __f);
1876 --__c.__sz();
1877 ++base::__sz();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001878#if _LIBCPP_DEBUG_LEVEL >= 2
1879 __libcpp_db* __db = __get_db();
1880 __c_node* __cn1 = __db->__find_c_and_lock(this);
1881 __c_node* __cn2 = __db->__find_c(&__c);
1882 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1883 {
1884 --__p;
1885 iterator* __j = static_cast<iterator*>((*__p)->__i_);
1886 if (__j->__ptr_ == &__f)
1887 {
1888 __cn1->__add(*__p);
1889 (*__p)->__c_ = __cn1;
1890 if (--__cn2->end_ != __p)
1891 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1892 }
1893 }
1894 __db->unlock();
1895#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001896 }
1897}
1898
1899template <class _Tp, class _Alloc>
1900void
1901list<_Tp, _Alloc>::splice(const_iterator __p, list& __c, const_iterator __f, const_iterator __l)
1902{
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001903#if _LIBCPP_DEBUG_LEVEL >= 2
1904 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
1905 "list::splice(iterator, list, iterator, iterator) called with first iterator not"
1906 " referring to this list");
1907 _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__f) == &__c,
1908 "list::splice(iterator, list, iterator, iterator) called with second iterator not"
1909 " referring to list argument");
1910 if (this == &__c)
1911 {
1912 for (const_iterator __i = __f; __i != __l; ++__i)
1913 _LIBCPP_ASSERT(__i != __p,
1914 "list::splice(iterator, list, iterator, iterator)"
1915 " called with the first iterator within the range"
1916 " of the second and third iterators");
1917 }
1918#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001919 if (__f != __l)
1920 {
1921 if (this != &__c)
1922 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001923 size_type __s = _VSTD::distance(__f, __l);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001924 __c.__sz() -= __s;
1925 base::__sz() += __s;
1926 }
1927 __node& __first = const_cast<__node&>(*__f.__ptr_);
1928 --__l;
1929 __node& __last = const_cast<__node&>(*__l.__ptr_);
1930 base::__unlink_nodes(__first, __last);
1931 __link_nodes(const_cast<__node&>(*__p.__ptr_), __first, __last);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00001932#if _LIBCPP_DEBUG_LEVEL >= 2
1933 __libcpp_db* __db = __get_db();
1934 __c_node* __cn1 = __db->__find_c_and_lock(this);
1935 __c_node* __cn2 = __db->__find_c(&__c);
1936 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
1937 {
1938 --__p;
1939 iterator* __j = static_cast<iterator*>((*__p)->__i_);
1940 for (__node_pointer __k = const_cast<__node_pointer>(__f.__ptr_);
1941 __k != __l.__ptr_; __k = __k->__next_)
1942 {
1943 if (__j->__ptr_ == __k)
1944 {
1945 __cn1->__add(*__p);
1946 (*__p)->__c_ = __cn1;
1947 if (--__cn2->end_ != __p)
1948 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
1949 }
1950 }
1951 }
1952 __db->unlock();
1953#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001954 }
1955}
1956
1957template <class _Tp, class _Alloc>
1958void
1959list<_Tp, _Alloc>::remove(const value_type& __x)
1960{
1961 for (iterator __i = begin(), __e = end(); __i != __e;)
1962 {
1963 if (*__i == __x)
1964 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001965 iterator __j = _VSTD::next(__i);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001966 for (; __j != __e && *__j == __x; ++__j)
1967 ;
1968 __i = erase(__i, __j);
1969 }
1970 else
1971 ++__i;
1972 }
1973}
1974
1975template <class _Tp, class _Alloc>
1976template <class _Pred>
1977void
1978list<_Tp, _Alloc>::remove_if(_Pred __pred)
1979{
1980 for (iterator __i = begin(), __e = end(); __i != __e;)
1981 {
1982 if (__pred(*__i))
1983 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001984 iterator __j = _VSTD::next(__i);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001985 for (; __j != __e && __pred(*__j); ++__j)
1986 ;
1987 __i = erase(__i, __j);
1988 }
1989 else
1990 ++__i;
1991 }
1992}
1993
1994template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00001995inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001996void
1997list<_Tp, _Alloc>::unique()
1998{
1999 unique(__equal_to<value_type>());
2000}
2001
2002template <class _Tp, class _Alloc>
2003template <class _BinaryPred>
2004void
2005list<_Tp, _Alloc>::unique(_BinaryPred __binary_pred)
2006{
2007 for (iterator __i = begin(), __e = end(); __i != __e;)
2008 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002009 iterator __j = _VSTD::next(__i);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002010 for (; __j != __e && __binary_pred(*__i, *__j); ++__j)
2011 ;
2012 if (++__i != __j)
2013 __i = erase(__i, __j);
2014 }
2015}
2016
2017template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002018inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002019void
2020list<_Tp, _Alloc>::merge(list& __c)
2021{
2022 merge(__c, __less<value_type>());
2023}
2024
2025template <class _Tp, class _Alloc>
2026template <class _Comp>
2027void
2028list<_Tp, _Alloc>::merge(list& __c, _Comp __comp)
2029{
2030 if (this != &__c)
2031 {
2032 iterator __f1 = begin();
2033 iterator __e1 = end();
2034 iterator __f2 = __c.begin();
2035 iterator __e2 = __c.end();
2036 while (__f1 != __e1 && __f2 != __e2)
2037 {
2038 if (__comp(*__f2, *__f1))
2039 {
2040 size_type __ds = 1;
Howard Hinnant0949eed2011-06-30 21:18:19 +00002041 iterator __m2 = _VSTD::next(__f2);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002042 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2, ++__ds)
2043 ;
2044 base::__sz() += __ds;
2045 __c.__sz() -= __ds;
2046 __node& __f = *__f2.__ptr_;
2047 __node& __l = *__m2.__ptr_->__prev_;
2048 __f2 = __m2;
2049 base::__unlink_nodes(__f, __l);
Howard Hinnant0949eed2011-06-30 21:18:19 +00002050 __m2 = _VSTD::next(__f1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002051 __link_nodes(*__f1.__ptr_, __f, __l);
2052 __f1 = __m2;
2053 }
2054 else
2055 ++__f1;
2056 }
2057 splice(__e1, __c);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00002058#if _LIBCPP_DEBUG_LEVEL >= 2
2059 __libcpp_db* __db = __get_db();
2060 __c_node* __cn1 = __db->__find_c_and_lock(this);
2061 __c_node* __cn2 = __db->__find_c(&__c);
2062 for (__i_node** __p = __cn2->end_; __p != __cn2->beg_;)
2063 {
2064 --__p;
2065 iterator* __i = static_cast<iterator*>((*__p)->__i_);
2066 if (__i->__ptr_ != static_cast<__node_pointer>(&__c.__end_))
2067 {
2068 __cn1->__add(*__p);
2069 (*__p)->__c_ = __cn1;
2070 if (--__cn2->end_ != __p)
2071 memmove(__p, __p+1, (__cn2->end_ - __p)*sizeof(__i_node*));
2072 }
2073 }
2074 __db->unlock();
2075#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002076 }
2077}
2078
2079template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002080inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002081void
2082list<_Tp, _Alloc>::sort()
2083{
2084 sort(__less<value_type>());
2085}
2086
2087template <class _Tp, class _Alloc>
2088template <class _Comp>
Howard Hinnant82894812010-09-22 16:48:34 +00002089inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002090void
2091list<_Tp, _Alloc>::sort(_Comp __comp)
2092{
2093 __sort(begin(), end(), base::__sz(), __comp);
2094}
2095
2096template <class _Tp, class _Alloc>
2097template <class _Comp>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002098typename list<_Tp, _Alloc>::iterator
2099list<_Tp, _Alloc>::__sort(iterator __f1, iterator __e2, size_type __n, _Comp& __comp)
2100{
2101 switch (__n)
2102 {
2103 case 0:
2104 case 1:
2105 return __f1;
2106 case 2:
2107 if (__comp(*--__e2, *__f1))
2108 {
2109 __node& __f = *__e2.__ptr_;
2110 base::__unlink_nodes(__f, __f);
2111 __link_nodes(*__f1.__ptr_, __f, __f);
2112 return __e2;
2113 }
2114 return __f1;
2115 }
2116 size_type __n2 = __n / 2;
Howard Hinnant0949eed2011-06-30 21:18:19 +00002117 iterator __e1 = _VSTD::next(__f1, __n2);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002118 iterator __r = __f1 = __sort(__f1, __e1, __n2, __comp);
2119 iterator __f2 = __e1 = __sort(__e1, __e2, __n - __n2, __comp);
2120 if (__comp(*__f2, *__f1))
2121 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002122 iterator __m2 = _VSTD::next(__f2);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002123 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2124 ;
2125 __node& __f = *__f2.__ptr_;
2126 __node& __l = *__m2.__ptr_->__prev_;
2127 __r = __f2;
2128 __e1 = __f2 = __m2;
2129 base::__unlink_nodes(__f, __l);
Howard Hinnant0949eed2011-06-30 21:18:19 +00002130 __m2 = _VSTD::next(__f1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002131 __link_nodes(*__f1.__ptr_, __f, __l);
2132 __f1 = __m2;
2133 }
2134 else
2135 ++__f1;
2136 while (__f1 != __e1 && __f2 != __e2)
2137 {
2138 if (__comp(*__f2, *__f1))
2139 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002140 iterator __m2 = _VSTD::next(__f2);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002141 for (; __m2 != __e2 && __comp(*__m2, *__f1); ++__m2)
2142 ;
2143 __node& __f = *__f2.__ptr_;
2144 __node& __l = *__m2.__ptr_->__prev_;
2145 if (__e1 == __f2)
2146 __e1 = __m2;
2147 __f2 = __m2;
2148 base::__unlink_nodes(__f, __l);
Howard Hinnant0949eed2011-06-30 21:18:19 +00002149 __m2 = _VSTD::next(__f1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002150 __link_nodes(*__f1.__ptr_, __f, __l);
2151 __f1 = __m2;
2152 }
2153 else
2154 ++__f1;
2155 }
2156 return __r;
2157}
2158
2159template <class _Tp, class _Alloc>
2160void
Howard Hinnantc5607272011-06-03 17:30:28 +00002161list<_Tp, _Alloc>::reverse() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002162{
2163 if (base::__sz() > 1)
2164 {
2165 iterator __e = end();
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00002166 for (iterator __i = begin(); __i.__ptr_ != __e.__ptr_;)
2167 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00002168 _VSTD::swap(__i.__ptr_->__prev_, __i.__ptr_->__next_);
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00002169 __i.__ptr_ = __i.__ptr_->__prev_;
2170 }
Howard Hinnant0949eed2011-06-30 21:18:19 +00002171 _VSTD::swap(__e.__ptr_->__prev_, __e.__ptr_->__next_);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002172 }
2173}
2174
2175template <class _Tp, class _Alloc>
Howard Hinnant1c3ec6d2011-09-27 23:55:03 +00002176bool
2177list<_Tp, _Alloc>::__invariants() const
2178{
2179 return size() == _VSTD::distance(begin(), end());
2180}
2181
2182#if _LIBCPP_DEBUG_LEVEL >= 2
2183
2184template <class _Tp, class _Alloc>
2185bool
2186list<_Tp, _Alloc>::__dereferenceable(const const_iterator* __i) const
2187{
2188 return __i->__ptr_ != &this->__end_;
2189}
2190
2191template <class _Tp, class _Alloc>
2192bool
2193list<_Tp, _Alloc>::__decrementable(const const_iterator* __i) const
2194{
2195 return !empty() && __i->__ptr_ != base::__end_.__next_;
2196}
2197
2198template <class _Tp, class _Alloc>
2199bool
2200list<_Tp, _Alloc>::__addable(const const_iterator* __i, ptrdiff_t __n) const
2201{
2202 return false;
2203}
2204
2205template <class _Tp, class _Alloc>
2206bool
2207list<_Tp, _Alloc>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
2208{
2209 return false;
2210}
2211
2212#endif // _LIBCPP_DEBUG_LEVEL >= 2
2213
2214template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002215inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002216bool
2217operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2218{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002219 return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002220}
2221
2222template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002223inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002224bool
2225operator< (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2226{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002227 return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002228}
2229
2230template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002231inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002232bool
2233operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2234{
2235 return !(__x == __y);
2236}
2237
2238template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002239inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002240bool
2241operator> (const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2242{
2243 return __y < __x;
2244}
2245
2246template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002247inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002248bool
2249operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2250{
2251 return !(__x < __y);
2252}
2253
2254template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002255inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002256bool
2257operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y)
2258{
2259 return !(__y < __x);
2260}
2261
2262template <class _Tp, class _Alloc>
Howard Hinnant82894812010-09-22 16:48:34 +00002263inline _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002264void
2265swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y)
Howard Hinnantc5607272011-06-03 17:30:28 +00002266 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002267{
2268 __x.swap(__y);
2269}
2270
2271_LIBCPP_END_NAMESPACE_STD
2272
2273#endif // _LIBCPP_LIST