]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // List implementation -*- C++ -*- |
2 | ||
405feeb8 | 3 | // Copyright (C) 2001-2013 Free Software Foundation, Inc. |
42526146 PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
9 | // any later version. |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
748086b7 JJ |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version | |
18 | // 3.1, as published by the Free Software Foundation. | |
42526146 | 19 | |
748086b7 JJ |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; | |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
23 | // <http://www.gnu.org/licenses/>. | |
42526146 | 24 | |
725dc051 BK |
25 | /* |
26 | * | |
27 | * Copyright (c) 1994 | |
28 | * Hewlett-Packard Company | |
29 | * | |
30 | * Permission to use, copy, modify, distribute and sell this software | |
31 | * and its documentation for any purpose is hereby granted without fee, | |
32 | * provided that the above copyright notice appear in all copies and | |
33 | * that both that copyright notice and this permission notice appear | |
34 | * in supporting documentation. Hewlett-Packard Company makes no | |
35 | * representations about the suitability of this software for any | |
36 | * purpose. It is provided "as is" without express or implied warranty. | |
37 | * | |
38 | * | |
39 | * Copyright (c) 1996,1997 | |
40 | * Silicon Graphics Computer Systems, Inc. | |
41 | * | |
42 | * Permission to use, copy, modify, distribute and sell this software | |
43 | * and its documentation for any purpose is hereby granted without fee, | |
44 | * provided that the above copyright notice appear in all copies and | |
45 | * that both that copyright notice and this permission notice appear | |
46 | * in supporting documentation. Silicon Graphics makes no | |
47 | * representations about the suitability of this software for any | |
48 | * purpose. It is provided "as is" without express or implied warranty. | |
49 | */ | |
50 | ||
f910786b | 51 | /** @file bits/stl_list.h |
729e3d3f | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{list} |
725dc051 BK |
54 | */ |
55 | ||
046d30f4 PC |
56 | #ifndef _STL_LIST_H |
57 | #define _STL_LIST_H 1 | |
725dc051 | 58 | |
30a20a1e | 59 | #include <bits/concept_check.h> |
734f5023 | 60 | #if __cplusplus >= 201103L |
988499f4 | 61 | #include <initializer_list> |
a7d5d7e2 | 62 | #endif |
725dc051 | 63 | |
12ffa228 BK |
64 | namespace std _GLIBCXX_VISIBILITY(default) |
65 | { | |
66 | namespace __detail | |
5cb6369d | 67 | { |
12ffa228 | 68 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
e135a038 | 69 | |
12ffa228 BK |
70 | // Supporting structures are split into common and templated |
71 | // types; the latter publicly inherits from the former in an | |
72 | // effort to reduce code duplication. This results in some | |
73 | // "needless" static_cast'ing later on, but it's all safe | |
74 | // downcasting. | |
e135a038 | 75 | |
12ffa228 BK |
76 | /// Common part of a node in the %list. |
77 | struct _List_node_base | |
78 | { | |
79 | _List_node_base* _M_next; | |
80 | _List_node_base* _M_prev; | |
d3677132 | 81 | |
12ffa228 | 82 | static void |
d3677132 PC |
83 | swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT; |
84 | ||
12ffa228 BK |
85 | void |
86 | _M_transfer(_List_node_base* const __first, | |
d3677132 PC |
87 | _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT; |
88 | ||
12ffa228 | 89 | void |
d3677132 PC |
90 | _M_reverse() _GLIBCXX_USE_NOEXCEPT; |
91 | ||
12ffa228 | 92 | void |
d3677132 PC |
93 | _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT; |
94 | ||
12ffa228 | 95 | void |
d3677132 | 96 | _M_unhook() _GLIBCXX_USE_NOEXCEPT; |
12ffa228 | 97 | }; |
83042fca | 98 | |
12ffa228 BK |
99 | _GLIBCXX_END_NAMESPACE_VERSION |
100 | } // namespace detail | |
ed6814f7 | 101 | |
12ffa228 | 102 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
ed6814f7 | 103 | |
4312e020 | 104 | /// An actual node in the %list. |
3971a4d2 | 105 | template<typename _Tp> |
12ffa228 | 106 | struct _List_node : public __detail::_List_node_base |
4d54539c | 107 | { |
4312e020 BK |
108 | ///< User's data. |
109 | _Tp _M_data; | |
c841843f | 110 | |
734f5023 | 111 | #if __cplusplus >= 201103L |
c841843f PC |
112 | template<typename... _Args> |
113 | _List_node(_Args&&... __args) | |
12ffa228 BK |
114 | : __detail::_List_node_base(), _M_data(std::forward<_Args>(__args)...) |
115 | { } | |
c841843f | 116 | #endif |
4d54539c | 117 | }; |
ed6814f7 | 118 | |
5cb6369d | 119 | /** |
e135a038 | 120 | * @brief A list::iterator. |
5cb6369d | 121 | * |
e135a038 | 122 | * All the functions are op overloads. |
5cb6369d | 123 | */ |
e135a038 BK |
124 | template<typename _Tp> |
125 | struct _List_iterator | |
126 | { | |
6323b34e PC |
127 | typedef _List_iterator<_Tp> _Self; |
128 | typedef _List_node<_Tp> _Node; | |
ed6814f7 | 129 | |
6323b34e PC |
130 | typedef ptrdiff_t difference_type; |
131 | typedef std::bidirectional_iterator_tag iterator_category; | |
132 | typedef _Tp value_type; | |
133 | typedef _Tp* pointer; | |
134 | typedef _Tp& reference; | |
ed6814f7 | 135 | |
a7a44441 VR |
136 | _List_iterator() |
137 | : _M_node() { } | |
e135a038 | 138 | |
e182017e | 139 | explicit |
12ffa228 | 140 | _List_iterator(__detail::_List_node_base* __x) |
e135a038 BK |
141 | : _M_node(__x) { } |
142 | ||
7b61c5a9 PC |
143 | _Self |
144 | _M_const_cast() const | |
145 | { return *this; } | |
146 | ||
882b3d5c | 147 | // Must downcast from _List_node_base to _List_node to get to _M_data. |
e135a038 BK |
148 | reference |
149 | operator*() const | |
150 | { return static_cast<_Node*>(_M_node)->_M_data; } | |
151 | ||
152 | pointer | |
153 | operator->() const | |
882b3d5c | 154 | { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } |
ed6814f7 | 155 | |
e135a038 BK |
156 | _Self& |
157 | operator++() | |
158 | { | |
159 | _M_node = _M_node->_M_next; | |
160 | return *this; | |
161 | } | |
ed6814f7 | 162 | |
e135a038 BK |
163 | _Self |
164 | operator++(int) | |
165 | { | |
166 | _Self __tmp = *this; | |
167 | _M_node = _M_node->_M_next; | |
168 | return __tmp; | |
169 | } | |
ed6814f7 | 170 | |
e135a038 BK |
171 | _Self& |
172 | operator--() | |
173 | { | |
174 | _M_node = _M_node->_M_prev; | |
175 | return *this; | |
176 | } | |
ed6814f7 | 177 | |
e135a038 BK |
178 | _Self |
179 | operator--(int) | |
180 | { | |
181 | _Self __tmp = *this; | |
182 | _M_node = _M_node->_M_prev; | |
183 | return __tmp; | |
184 | } | |
ed6814f7 | 185 | |
e135a038 BK |
186 | bool |
187 | operator==(const _Self& __x) const | |
188 | { return _M_node == __x._M_node; } | |
189 | ||
190 | bool | |
191 | operator!=(const _Self& __x) const | |
192 | { return _M_node != __x._M_node; } | |
ed6814f7 | 193 | |
e135a038 | 194 | // The only member points to the %list element. |
12ffa228 | 195 | __detail::_List_node_base* _M_node; |
e135a038 | 196 | }; |
ed6814f7 | 197 | |
5cb6369d | 198 | /** |
e135a038 | 199 | * @brief A list::const_iterator. |
3971a4d2 | 200 | * |
3971a4d2 | 201 | * All the functions are op overloads. |
5cb6369d | 202 | */ |
e135a038 BK |
203 | template<typename _Tp> |
204 | struct _List_const_iterator | |
3971a4d2 | 205 | { |
6323b34e PC |
206 | typedef _List_const_iterator<_Tp> _Self; |
207 | typedef const _List_node<_Tp> _Node; | |
208 | typedef _List_iterator<_Tp> iterator; | |
ed6814f7 | 209 | |
6323b34e PC |
210 | typedef ptrdiff_t difference_type; |
211 | typedef std::bidirectional_iterator_tag iterator_category; | |
212 | typedef _Tp value_type; | |
213 | typedef const _Tp* pointer; | |
214 | typedef const _Tp& reference; | |
ed6814f7 | 215 | |
a7a44441 VR |
216 | _List_const_iterator() |
217 | : _M_node() { } | |
e135a038 | 218 | |
e182017e | 219 | explicit |
12ffa228 | 220 | _List_const_iterator(const __detail::_List_node_base* __x) |
e135a038 BK |
221 | : _M_node(__x) { } |
222 | ||
223 | _List_const_iterator(const iterator& __x) | |
224 | : _M_node(__x._M_node) { } | |
225 | ||
94938aec PC |
226 | iterator |
227 | _M_const_cast() const | |
228 | { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); } | |
229 | ||
e135a038 BK |
230 | // Must downcast from List_node_base to _List_node to get to |
231 | // _M_data. | |
4d54539c BK |
232 | reference |
233 | operator*() const | |
234 | { return static_cast<_Node*>(_M_node)->_M_data; } | |
235 | ||
236 | pointer | |
237 | operator->() const | |
882b3d5c | 238 | { return std::__addressof(static_cast<_Node*>(_M_node)->_M_data); } |
ed6814f7 | 239 | |
4d54539c BK |
240 | _Self& |
241 | operator++() | |
242 | { | |
e135a038 | 243 | _M_node = _M_node->_M_next; |
4d54539c BK |
244 | return *this; |
245 | } | |
ed6814f7 | 246 | |
4d54539c BK |
247 | _Self |
248 | operator++(int) | |
249 | { | |
250 | _Self __tmp = *this; | |
e135a038 | 251 | _M_node = _M_node->_M_next; |
4d54539c BK |
252 | return __tmp; |
253 | } | |
ed6814f7 | 254 | |
4d54539c BK |
255 | _Self& |
256 | operator--() | |
257 | { | |
e135a038 | 258 | _M_node = _M_node->_M_prev; |
4d54539c BK |
259 | return *this; |
260 | } | |
ed6814f7 | 261 | |
4d54539c BK |
262 | _Self |
263 | operator--(int) | |
264 | { | |
265 | _Self __tmp = *this; | |
e135a038 BK |
266 | _M_node = _M_node->_M_prev; |
267 | return __tmp; | |
4d54539c | 268 | } |
ed6814f7 | 269 | |
e135a038 BK |
270 | bool |
271 | operator==(const _Self& __x) const | |
272 | { return _M_node == __x._M_node; } | |
ed6814f7 | 273 | |
e135a038 BK |
274 | bool |
275 | operator!=(const _Self& __x) const | |
276 | { return _M_node != __x._M_node; } | |
ed6814f7 | 277 | |
e135a038 | 278 | // The only member points to the %list element. |
12ffa228 | 279 | const __detail::_List_node_base* _M_node; |
4d54539c | 280 | }; |
ed6814f7 | 281 | |
e135a038 | 282 | template<typename _Val> |
ed6814f7 BI |
283 | inline bool |
284 | operator==(const _List_iterator<_Val>& __x, | |
285 | const _List_const_iterator<_Val>& __y) | |
e135a038 BK |
286 | { return __x._M_node == __y._M_node; } |
287 | ||
288 | template<typename _Val> | |
ed6814f7 | 289 | inline bool |
e135a038 | 290 | operator!=(const _List_iterator<_Val>& __x, |
ed6814f7 | 291 | const _List_const_iterator<_Val>& __y) |
e135a038 BK |
292 | { return __x._M_node != __y._M_node; } |
293 | ||
ed6814f7 | 294 | |
4312e020 | 295 | /// See bits/stl_deque.h's _Deque_base for an explanation. |
4d54539c | 296 | template<typename _Tp, typename _Alloc> |
8a1d8dd9 | 297 | class _List_base |
4d54539c BK |
298 | { |
299 | protected: | |
300 | // NOTA BENE | |
301 | // The stored instance is not actually of "allocator_type"'s | |
302 | // type. Instead we rebind the type to | |
303 | // Allocator<List_node<Tp>>, which according to [20.1.5]/4 | |
304 | // should probably be the same. List_node<Tp> is not the same | |
305 | // size as Tp (it's two pointers larger), and specializations on | |
306 | // Tp may go unused because List_node<Tp> is being bound | |
307 | // instead. | |
308 | // | |
309 | // We put this to the test in the constructors and in | |
310 | // get_allocator, where we use conversions between | |
4fd20a8f | 311 | // allocator_type and _Node_alloc_type. The conversion is |
4d54539c BK |
312 | // required by table 32 in [20.1.5]. |
313 | typedef typename _Alloc::template rebind<_List_node<_Tp> >::other | |
4fd20a8f | 314 | _Node_alloc_type; |
83042fca | 315 | |
4fd20a8f | 316 | typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type; |
8a1d8dd9 | 317 | |
0e83f45a | 318 | struct _List_impl |
4fd20a8f | 319 | : public _Node_alloc_type |
0d8c9baf | 320 | { |
12ffa228 | 321 | __detail::_List_node_base _M_node; |
dbc564ae | 322 | |
78b36b70 PC |
323 | _List_impl() |
324 | : _Node_alloc_type(), _M_node() | |
325 | { } | |
326 | ||
4fd20a8f | 327 | _List_impl(const _Node_alloc_type& __a) |
dbc564ae | 328 | : _Node_alloc_type(__a), _M_node() |
03f9ea44 | 329 | { } |
6f59ea25 | 330 | |
734f5023 | 331 | #if __cplusplus >= 201103L |
6f59ea25 | 332 | _List_impl(_Node_alloc_type&& __a) |
b4db974a | 333 | : _Node_alloc_type(std::move(__a)), _M_node() |
6f59ea25 PC |
334 | { } |
335 | #endif | |
03f9ea44 DM |
336 | }; |
337 | ||
338 | _List_impl _M_impl; | |
8a1d8dd9 | 339 | |
4d54539c BK |
340 | _List_node<_Tp>* |
341 | _M_get_node() | |
d695f915 | 342 | { return _M_impl._Node_alloc_type::allocate(1); } |
0e83f45a | 343 | |
4d54539c BK |
344 | void |
345 | _M_put_node(_List_node<_Tp>* __p) | |
d695f915 PC |
346 | { _M_impl._Node_alloc_type::deallocate(__p, 1); } |
347 | ||
3971a4d2 | 348 | public: |
4d54539c | 349 | typedef _Alloc allocator_type; |
8a1d8dd9 | 350 | |
31905f34 | 351 | _Node_alloc_type& |
d3677132 | 352 | _M_get_Node_allocator() _GLIBCXX_NOEXCEPT |
0e83f45a | 353 | { return *static_cast<_Node_alloc_type*>(&_M_impl); } |
31905f34 PC |
354 | |
355 | const _Node_alloc_type& | |
d3677132 | 356 | _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT |
0e83f45a | 357 | { return *static_cast<const _Node_alloc_type*>(&_M_impl); } |
31905f34 | 358 | |
4fd20a8f | 359 | _Tp_alloc_type |
d3677132 | 360 | _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT |
31905f34 | 361 | { return _Tp_alloc_type(_M_get_Node_allocator()); } |
4fd20a8f | 362 | |
ed6814f7 | 363 | allocator_type |
d3677132 | 364 | get_allocator() const _GLIBCXX_NOEXCEPT |
31905f34 | 365 | { return allocator_type(_M_get_Node_allocator()); } |
8a1d8dd9 | 366 | |
78b36b70 PC |
367 | _List_base() |
368 | : _M_impl() | |
369 | { _M_init(); } | |
370 | ||
ff15f019 | 371 | _List_base(const _Node_alloc_type& __a) |
0d8c9baf | 372 | : _M_impl(__a) |
e135a038 | 373 | { _M_init(); } |
ed6814f7 | 374 | |
734f5023 | 375 | #if __cplusplus >= 201103L |
053cc380 | 376 | _List_base(_List_base&& __x) |
6f59ea25 | 377 | : _M_impl(std::move(__x._M_get_Node_allocator())) |
053cc380 PC |
378 | { |
379 | _M_init(); | |
0e83f45a | 380 | __detail::_List_node_base::swap(_M_impl._M_node, __x._M_impl._M_node); |
053cc380 PC |
381 | } |
382 | #endif | |
383 | ||
4d54539c | 384 | // This is what actually destroys the list. |
6f59ea25 | 385 | ~_List_base() _GLIBCXX_NOEXCEPT |
4d54539c | 386 | { _M_clear(); } |
ed6814f7 | 387 | |
4d54539c BK |
388 | void |
389 | _M_clear(); | |
e135a038 BK |
390 | |
391 | void | |
392 | _M_init() | |
393 | { | |
03f9ea44 DM |
394 | this->_M_impl._M_node._M_next = &this->_M_impl._M_node; |
395 | this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; | |
e135a038 | 396 | } |
4d54539c | 397 | }; |
ed6814f7 | 398 | |
5cb6369d | 399 | /** |
4d54539c BK |
400 | * @brief A standard container with linear time access to elements, |
401 | * and fixed time insertion/deletion at any point in the sequence. | |
5cb6369d | 402 | * |
aac2878e | 403 | * @ingroup sequences |
5cb6369d | 404 | * |
d632488a BK |
405 | * @tparam _Tp Type of element. |
406 | * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. | |
407 | * | |
3971a4d2 PE |
408 | * Meets the requirements of a <a href="tables.html#65">container</a>, a |
409 | * <a href="tables.html#66">reversible container</a>, and a | |
410 | * <a href="tables.html#67">sequence</a>, including the | |
411 | * <a href="tables.html#68">optional sequence requirements</a> with the | |
412 | * %exception of @c at and @c operator[]. | |
5cb6369d | 413 | * |
285b36d6 BK |
414 | * This is a @e doubly @e linked %list. Traversal up and down the |
415 | * %list requires linear time, but adding and removing elements (or | |
416 | * @e nodes) is done in constant time, regardless of where the | |
417 | * change takes place. Unlike std::vector and std::deque, | |
418 | * random-access iterators are not provided, so subscripting ( @c | |
419 | * [] ) access is not allowed. For algorithms which only need | |
420 | * sequential access, this lack makes no difference. | |
5cb6369d | 421 | * |
285b36d6 BK |
422 | * Also unlike the other standard containers, std::list provides |
423 | * specialized algorithms %unique to linked lists, such as | |
424 | * splicing, sorting, and in-place reversal. | |
5cb6369d | 425 | * |
3971a4d2 | 426 | * A couple points on memory allocation for list<Tp>: |
5cb6369d | 427 | * |
285b36d6 BK |
428 | * First, we never actually allocate a Tp, we allocate |
429 | * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure | |
430 | * that after elements from %list<X,Alloc1> are spliced into | |
431 | * %list<X,Alloc2>, destroying the memory of the second %list is a | |
432 | * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. | |
5cb6369d | 433 | * |
3971a4d2 PE |
434 | * Second, a %list conceptually represented as |
435 | * @code | |
436 | * A <---> B <---> C <---> D | |
437 | * @endcode | |
285b36d6 BK |
438 | * is actually circular; a link exists between A and D. The %list |
439 | * class holds (as its only data member) a private list::iterator | |
440 | * pointing to @e D, not to @e A! To get to the head of the %list, | |
441 | * we start at the tail and move forward by one. When this member | |
442 | * iterator's next/previous pointers refer to itself, the %list is | |
4312e020 | 443 | * %empty. |
5cb6369d | 444 | */ |
6323b34e | 445 | template<typename _Tp, typename _Alloc = std::allocator<_Tp> > |
3971a4d2 | 446 | class list : protected _List_base<_Tp, _Alloc> |
5cb6369d | 447 | { |
4d54539c | 448 | // concept requirements |
4fd20a8f | 449 | typedef typename _Alloc::value_type _Alloc_value_type; |
4d54539c | 450 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |
4fd20a8f | 451 | __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) |
ed6814f7 | 452 | |
4fd20a8f PC |
453 | typedef _List_base<_Tp, _Alloc> _Base; |
454 | typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; | |
ff15f019 | 455 | typedef typename _Base::_Node_alloc_type _Node_alloc_type; |
ed6814f7 | 456 | |
4d54539c | 457 | public: |
7338fc64 | 458 | typedef _Tp value_type; |
4fd20a8f PC |
459 | typedef typename _Tp_alloc_type::pointer pointer; |
460 | typedef typename _Tp_alloc_type::const_pointer const_pointer; | |
461 | typedef typename _Tp_alloc_type::reference reference; | |
462 | typedef typename _Tp_alloc_type::const_reference const_reference; | |
7338fc64 PC |
463 | typedef _List_iterator<_Tp> iterator; |
464 | typedef _List_const_iterator<_Tp> const_iterator; | |
465 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | |
466 | typedef std::reverse_iterator<iterator> reverse_iterator; | |
467 | typedef size_t size_type; | |
468 | typedef ptrdiff_t difference_type; | |
4fd20a8f | 469 | typedef _Alloc allocator_type; |
ed6814f7 | 470 | |
4d54539c BK |
471 | protected: |
472 | // Note that pointers-to-_Node's can be ctor-converted to | |
473 | // iterator types. | |
4fd20a8f | 474 | typedef _List_node<_Tp> _Node; |
ed6814f7 | 475 | |
03f9ea44 | 476 | using _Base::_M_impl; |
4d54539c BK |
477 | using _Base::_M_put_node; |
478 | using _Base::_M_get_node; | |
4fd20a8f | 479 | using _Base::_M_get_Tp_allocator; |
31905f34 | 480 | using _Base::_M_get_Node_allocator; |
ed6814f7 | 481 | |
4d54539c | 482 | /** |
93c66bc6 | 483 | * @param __args An instance of user data. |
4d54539c | 484 | * |
93c66bc6 BK |
485 | * Allocates space for a new node and constructs a copy of |
486 | * @a __args in it. | |
4d54539c | 487 | */ |
734f5023 | 488 | #if __cplusplus < 201103L |
4d54539c BK |
489 | _Node* |
490 | _M_create_node(const value_type& __x) | |
3971a4d2 | 491 | { |
4d54539c | 492 | _Node* __p = this->_M_get_node(); |
bc2631e0 | 493 | __try |
4d54539c | 494 | { |
882b3d5c PC |
495 | _M_get_Tp_allocator().construct |
496 | (std::__addressof(__p->_M_data), __x); | |
4d54539c | 497 | } |
bc2631e0 | 498 | __catch(...) |
4d54539c BK |
499 | { |
500 | _M_put_node(__p); | |
501 | __throw_exception_again; | |
502 | } | |
503 | return __p; | |
3971a4d2 | 504 | } |
84237dbb PC |
505 | #else |
506 | template<typename... _Args> | |
507 | _Node* | |
508 | _M_create_node(_Args&&... __args) | |
509 | { | |
510 | _Node* __p = this->_M_get_node(); | |
bc2631e0 | 511 | __try |
84237dbb | 512 | { |
c841843f PC |
513 | _M_get_Node_allocator().construct(__p, |
514 | std::forward<_Args>(__args)...); | |
84237dbb | 515 | } |
bc2631e0 | 516 | __catch(...) |
84237dbb PC |
517 | { |
518 | _M_put_node(__p); | |
519 | __throw_exception_again; | |
520 | } | |
521 | return __p; | |
522 | } | |
523 | #endif | |
ed6814f7 | 524 | |
4d54539c BK |
525 | public: |
526 | // [23.2.2.1] construct/copy/destroy | |
527 | // (assign() and get_allocator() are also listed in this section) | |
528 | /** | |
529 | * @brief Default constructor creates no elements. | |
530 | */ | |
78b36b70 PC |
531 | list() |
532 | : _Base() { } | |
533 | ||
534 | /** | |
535 | * @brief Creates a %list with no elements. | |
93c66bc6 | 536 | * @param __a An allocator object. |
78b36b70 | 537 | */ |
4d54539c | 538 | explicit |
78b36b70 | 539 | list(const allocator_type& __a) |
ff15f019 | 540 | : _Base(_Node_alloc_type(__a)) { } |
ed6814f7 | 541 | |
734f5023 | 542 | #if __cplusplus >= 201103L |
dc2cf706 PC |
543 | /** |
544 | * @brief Creates a %list with default constructed elements. | |
93c66bc6 | 545 | * @param __n The number of elements to initially create. |
dc2cf706 | 546 | * |
93c66bc6 | 547 | * This constructor fills the %list with @a __n default |
dc2cf706 PC |
548 | * constructed elements. |
549 | */ | |
550 | explicit | |
551 | list(size_type __n) | |
552 | : _Base() | |
553 | { _M_default_initialize(__n); } | |
554 | ||
555 | /** | |
556 | * @brief Creates a %list with copies of an exemplar element. | |
93c66bc6 BK |
557 | * @param __n The number of elements to initially create. |
558 | * @param __value An element to copy. | |
559 | * @param __a An allocator object. | |
dc2cf706 | 560 | * |
93c66bc6 | 561 | * This constructor fills the %list with @a __n copies of @a __value. |
dc2cf706 PC |
562 | */ |
563 | list(size_type __n, const value_type& __value, | |
564 | const allocator_type& __a = allocator_type()) | |
ff15f019 | 565 | : _Base(_Node_alloc_type(__a)) |
dc2cf706 PC |
566 | { _M_fill_initialize(__n, __value); } |
567 | #else | |
4d54539c | 568 | /** |
78b36b70 | 569 | * @brief Creates a %list with copies of an exemplar element. |
93c66bc6 BK |
570 | * @param __n The number of elements to initially create. |
571 | * @param __value An element to copy. | |
572 | * @param __a An allocator object. | |
ed6814f7 | 573 | * |
93c66bc6 | 574 | * This constructor fills the %list with @a __n copies of @a __value. |
4d54539c | 575 | */ |
2fecaef4 PC |
576 | explicit |
577 | list(size_type __n, const value_type& __value = value_type(), | |
4d54539c | 578 | const allocator_type& __a = allocator_type()) |
ff15f019 | 579 | : _Base(_Node_alloc_type(__a)) |
0cb855b7 | 580 | { _M_fill_initialize(__n, __value); } |
dc2cf706 | 581 | #endif |
ed6814f7 | 582 | |
4d54539c BK |
583 | /** |
584 | * @brief %List copy constructor. | |
93c66bc6 | 585 | * @param __x A %list of identical element and allocator types. |
ed6814f7 | 586 | * |
4d54539c | 587 | * The newly-created %list uses a copy of the allocation object used |
93c66bc6 | 588 | * by @a __x. |
4d54539c BK |
589 | */ |
590 | list(const list& __x) | |
31905f34 | 591 | : _Base(__x._M_get_Node_allocator()) |
0cb855b7 | 592 | { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } |
ed6814f7 | 593 | |
734f5023 | 594 | #if __cplusplus >= 201103L |
78b36b70 PC |
595 | /** |
596 | * @brief %List move constructor. | |
93c66bc6 | 597 | * @param __x A %list of identical element and allocator types. |
78b36b70 | 598 | * |
93c66bc6 BK |
599 | * The newly-created %list contains the exact contents of @a __x. |
600 | * The contents of @a __x are a valid, but unspecified %list. | |
78b36b70 | 601 | */ |
6f59ea25 | 602 | list(list&& __x) noexcept |
5f1fd346 | 603 | : _Base(std::move(__x)) { } |
988499f4 JM |
604 | |
605 | /** | |
606 | * @brief Builds a %list from an initializer_list | |
93c66bc6 BK |
607 | * @param __l An initializer_list of value_type. |
608 | * @param __a An allocator object. | |
988499f4 JM |
609 | * |
610 | * Create a %list consisting of copies of the elements in the | |
93c66bc6 | 611 | * initializer_list @a __l. This is linear in __l.size(). |
988499f4 JM |
612 | */ |
613 | list(initializer_list<value_type> __l, | |
614 | const allocator_type& __a = allocator_type()) | |
ff15f019 | 615 | : _Base(_Node_alloc_type(__a)) |
988499f4 | 616 | { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } |
78b36b70 PC |
617 | #endif |
618 | ||
4d54539c BK |
619 | /** |
620 | * @brief Builds a %list from a range. | |
93c66bc6 BK |
621 | * @param __first An input iterator. |
622 | * @param __last An input iterator. | |
623 | * @param __a An allocator object. | |
ed6814f7 | 624 | * |
4d54539c | 625 | * Create a %list consisting of copies of the elements from |
93c66bc6 BK |
626 | * [@a __first,@a __last). This is linear in N (where N is |
627 | * distance(@a __first,@a __last)). | |
4d54539c | 628 | */ |
734f5023 | 629 | #if __cplusplus >= 201103L |
2203cb90 PC |
630 | template<typename _InputIterator, |
631 | typename = std::_RequireInputIter<_InputIterator>> | |
632 | list(_InputIterator __first, _InputIterator __last, | |
633 | const allocator_type& __a = allocator_type()) | |
634 | : _Base(_Node_alloc_type(__a)) | |
635 | { _M_initialize_dispatch(__first, __last, __false_type()); } | |
636 | #else | |
4d54539c BK |
637 | template<typename _InputIterator> |
638 | list(_InputIterator __first, _InputIterator __last, | |
639 | const allocator_type& __a = allocator_type()) | |
ff15f019 | 640 | : _Base(_Node_alloc_type(__a)) |
0cb855b7 PC |
641 | { |
642 | // Check whether it's an integral type. If so, it's not an iterator. | |
643 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; | |
644 | _M_initialize_dispatch(__first, __last, _Integral()); | |
645 | } | |
2203cb90 | 646 | #endif |
ed6814f7 | 647 | |
4d54539c BK |
648 | /** |
649 | * No explicit dtor needed as the _Base dtor takes care of | |
650 | * things. The _Base dtor only erases the elements, and note | |
651 | * that if the elements themselves are pointers, the pointed-to | |
652 | * memory is not touched in any way. Managing the pointer is | |
28dac70a | 653 | * the user's responsibility. |
4d54539c | 654 | */ |
ed6814f7 | 655 | |
4d54539c BK |
656 | /** |
657 | * @brief %List assignment operator. | |
93c66bc6 | 658 | * @param __x A %list of identical element and allocator types. |
ed6814f7 | 659 | * |
93c66bc6 | 660 | * All the elements of @a __x are copied, but unlike the copy |
4d54539c BK |
661 | * constructor, the allocator object is not copied. |
662 | */ | |
663 | list& | |
664 | operator=(const list& __x); | |
ed6814f7 | 665 | |
734f5023 | 666 | #if __cplusplus >= 201103L |
78b36b70 PC |
667 | /** |
668 | * @brief %List move assignment operator. | |
93c66bc6 | 669 | * @param __x A %list of identical element and allocator types. |
78b36b70 | 670 | * |
93c66bc6 BK |
671 | * The contents of @a __x are moved into this %list (without copying). |
672 | * @a __x is a valid, but unspecified %list | |
78b36b70 PC |
673 | */ |
674 | list& | |
675 | operator=(list&& __x) | |
676 | { | |
0462fd5e PC |
677 | // NB: DR 1204. |
678 | // NB: DR 675. | |
679 | this->clear(); | |
680 | this->swap(__x); | |
78b36b70 PC |
681 | return *this; |
682 | } | |
988499f4 JM |
683 | |
684 | /** | |
685 | * @brief %List initializer list assignment operator. | |
93c66bc6 | 686 | * @param __l An initializer_list of value_type. |
988499f4 JM |
687 | * |
688 | * Replace the contents of the %list with copies of the elements | |
93c66bc6 | 689 | * in the initializer_list @a __l. This is linear in l.size(). |
988499f4 JM |
690 | */ |
691 | list& | |
692 | operator=(initializer_list<value_type> __l) | |
693 | { | |
694 | this->assign(__l.begin(), __l.end()); | |
695 | return *this; | |
696 | } | |
78b36b70 PC |
697 | #endif |
698 | ||
4d54539c BK |
699 | /** |
700 | * @brief Assigns a given value to a %list. | |
93c66bc6 BK |
701 | * @param __n Number of elements to be assigned. |
702 | * @param __val Value to be assigned. | |
4d54539c | 703 | * |
93c66bc6 | 704 | * This function fills a %list with @a __n copies of the given |
4d54539c BK |
705 | * value. Note that the assignment completely changes the %list |
706 | * and that the resulting %list's size is the same as the number | |
707 | * of elements assigned. Old data may be lost. | |
708 | */ | |
709 | void | |
ed6814f7 | 710 | assign(size_type __n, const value_type& __val) |
4d54539c | 711 | { _M_fill_assign(__n, __val); } |
ed6814f7 | 712 | |
4d54539c BK |
713 | /** |
714 | * @brief Assigns a range to a %list. | |
93c66bc6 BK |
715 | * @param __first An input iterator. |
716 | * @param __last An input iterator. | |
4d54539c BK |
717 | * |
718 | * This function fills a %list with copies of the elements in the | |
93c66bc6 | 719 | * range [@a __first,@a __last). |
4d54539c BK |
720 | * |
721 | * Note that the assignment completely changes the %list and | |
722 | * that the resulting %list's size is the same as the number of | |
723 | * elements assigned. Old data may be lost. | |
724 | */ | |
734f5023 | 725 | #if __cplusplus >= 201103L |
2203cb90 PC |
726 | template<typename _InputIterator, |
727 | typename = std::_RequireInputIter<_InputIterator>> | |
728 | void | |
729 | assign(_InputIterator __first, _InputIterator __last) | |
730 | { _M_assign_dispatch(__first, __last, __false_type()); } | |
731 | #else | |
4d54539c BK |
732 | template<typename _InputIterator> |
733 | void | |
734 | assign(_InputIterator __first, _InputIterator __last) | |
ed6814f7 | 735 | { |
4d54539c | 736 | // Check whether it's an integral type. If so, it's not an iterator. |
c0736a9d | 737 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
4d54539c BK |
738 | _M_assign_dispatch(__first, __last, _Integral()); |
739 | } | |
2203cb90 | 740 | #endif |
ed6814f7 | 741 | |
734f5023 | 742 | #if __cplusplus >= 201103L |
988499f4 JM |
743 | /** |
744 | * @brief Assigns an initializer_list to a %list. | |
93c66bc6 | 745 | * @param __l An initializer_list of value_type. |
988499f4 JM |
746 | * |
747 | * Replace the contents of the %list with copies of the elements | |
93c66bc6 | 748 | * in the initializer_list @a __l. This is linear in __l.size(). |
988499f4 JM |
749 | */ |
750 | void | |
751 | assign(initializer_list<value_type> __l) | |
752 | { this->assign(__l.begin(), __l.end()); } | |
753 | #endif | |
754 | ||
4d54539c BK |
755 | /// Get a copy of the memory allocation object. |
756 | allocator_type | |
d3677132 | 757 | get_allocator() const _GLIBCXX_NOEXCEPT |
f6592a9e | 758 | { return _Base::get_allocator(); } |
ed6814f7 | 759 | |
4d54539c BK |
760 | // iterators |
761 | /** | |
762 | * Returns a read/write iterator that points to the first element in the | |
763 | * %list. Iteration is done in ordinary element order. | |
764 | */ | |
765 | iterator | |
d3677132 | 766 | begin() _GLIBCXX_NOEXCEPT |
e182017e | 767 | { return iterator(this->_M_impl._M_node._M_next); } |
ed6814f7 | 768 | |
4d54539c BK |
769 | /** |
770 | * Returns a read-only (constant) iterator that points to the | |
771 | * first element in the %list. Iteration is done in ordinary | |
772 | * element order. | |
773 | */ | |
774 | const_iterator | |
d3677132 | 775 | begin() const _GLIBCXX_NOEXCEPT |
e182017e | 776 | { return const_iterator(this->_M_impl._M_node._M_next); } |
ed6814f7 | 777 | |
4d54539c BK |
778 | /** |
779 | * Returns a read/write iterator that points one past the last | |
780 | * element in the %list. Iteration is done in ordinary element | |
781 | * order. | |
782 | */ | |
783 | iterator | |
d3677132 | 784 | end() _GLIBCXX_NOEXCEPT |
e182017e | 785 | { return iterator(&this->_M_impl._M_node); } |
ed6814f7 | 786 | |
4d54539c BK |
787 | /** |
788 | * Returns a read-only (constant) iterator that points one past | |
789 | * the last element in the %list. Iteration is done in ordinary | |
790 | * element order. | |
791 | */ | |
792 | const_iterator | |
d3677132 | 793 | end() const _GLIBCXX_NOEXCEPT |
e182017e | 794 | { return const_iterator(&this->_M_impl._M_node); } |
ed6814f7 | 795 | |
4d54539c BK |
796 | /** |
797 | * Returns a read/write reverse iterator that points to the last | |
798 | * element in the %list. Iteration is done in reverse element | |
799 | * order. | |
800 | */ | |
801 | reverse_iterator | |
d3677132 | 802 | rbegin() _GLIBCXX_NOEXCEPT |
f6592a9e | 803 | { return reverse_iterator(end()); } |
ed6814f7 | 804 | |
4d54539c BK |
805 | /** |
806 | * Returns a read-only (constant) reverse iterator that points to | |
807 | * the last element in the %list. Iteration is done in reverse | |
808 | * element order. | |
809 | */ | |
810 | const_reverse_iterator | |
d3677132 | 811 | rbegin() const _GLIBCXX_NOEXCEPT |
f6592a9e | 812 | { return const_reverse_iterator(end()); } |
ed6814f7 | 813 | |
4d54539c BK |
814 | /** |
815 | * Returns a read/write reverse iterator that points to one | |
816 | * before the first element in the %list. Iteration is done in | |
817 | * reverse element order. | |
818 | */ | |
819 | reverse_iterator | |
d3677132 | 820 | rend() _GLIBCXX_NOEXCEPT |
f6592a9e | 821 | { return reverse_iterator(begin()); } |
ed6814f7 | 822 | |
4d54539c BK |
823 | /** |
824 | * Returns a read-only (constant) reverse iterator that points to one | |
825 | * before the first element in the %list. Iteration is done in reverse | |
826 | * element order. | |
827 | */ | |
828 | const_reverse_iterator | |
d3677132 | 829 | rend() const _GLIBCXX_NOEXCEPT |
4d54539c | 830 | { return const_reverse_iterator(begin()); } |
ed6814f7 | 831 | |
734f5023 | 832 | #if __cplusplus >= 201103L |
0cd50f89 PC |
833 | /** |
834 | * Returns a read-only (constant) iterator that points to the | |
835 | * first element in the %list. Iteration is done in ordinary | |
836 | * element order. | |
837 | */ | |
838 | const_iterator | |
d3677132 | 839 | cbegin() const noexcept |
0cd50f89 PC |
840 | { return const_iterator(this->_M_impl._M_node._M_next); } |
841 | ||
842 | /** | |
843 | * Returns a read-only (constant) iterator that points one past | |
844 | * the last element in the %list. Iteration is done in ordinary | |
845 | * element order. | |
846 | */ | |
847 | const_iterator | |
d3677132 | 848 | cend() const noexcept |
0cd50f89 PC |
849 | { return const_iterator(&this->_M_impl._M_node); } |
850 | ||
851 | /** | |
852 | * Returns a read-only (constant) reverse iterator that points to | |
853 | * the last element in the %list. Iteration is done in reverse | |
854 | * element order. | |
855 | */ | |
856 | const_reverse_iterator | |
d3677132 | 857 | crbegin() const noexcept |
0cd50f89 PC |
858 | { return const_reverse_iterator(end()); } |
859 | ||
860 | /** | |
861 | * Returns a read-only (constant) reverse iterator that points to one | |
862 | * before the first element in the %list. Iteration is done in reverse | |
863 | * element order. | |
864 | */ | |
865 | const_reverse_iterator | |
d3677132 | 866 | crend() const noexcept |
0cd50f89 PC |
867 | { return const_reverse_iterator(begin()); } |
868 | #endif | |
869 | ||
4d54539c BK |
870 | // [23.2.2.2] capacity |
871 | /** | |
872 | * Returns true if the %list is empty. (Thus begin() would equal | |
873 | * end().) | |
874 | */ | |
875 | bool | |
d3677132 | 876 | empty() const _GLIBCXX_NOEXCEPT |
03f9ea44 | 877 | { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } |
ed6814f7 | 878 | |
4d54539c BK |
879 | /** Returns the number of elements in the %list. */ |
880 | size_type | |
d3677132 | 881 | size() const _GLIBCXX_NOEXCEPT |
d695f915 | 882 | { return std::distance(begin(), end()); } |
ed6814f7 | 883 | |
4d54539c BK |
884 | /** Returns the size() of the largest possible %list. */ |
885 | size_type | |
d3677132 | 886 | max_size() const _GLIBCXX_NOEXCEPT |
1fea874e | 887 | { return _M_get_Node_allocator().max_size(); } |
ed6814f7 | 888 | |
734f5023 | 889 | #if __cplusplus >= 201103L |
dc2cf706 PC |
890 | /** |
891 | * @brief Resizes the %list to the specified number of elements. | |
93c66bc6 | 892 | * @param __new_size Number of elements the %list should contain. |
dc2cf706 PC |
893 | * |
894 | * This function will %resize the %list to the specified number | |
895 | * of elements. If the number is smaller than the %list's | |
896 | * current size the %list is truncated, otherwise default | |
897 | * constructed elements are appended. | |
898 | */ | |
899 | void | |
900 | resize(size_type __new_size); | |
901 | ||
902 | /** | |
903 | * @brief Resizes the %list to the specified number of elements. | |
93c66bc6 BK |
904 | * @param __new_size Number of elements the %list should contain. |
905 | * @param __x Data with which new elements should be populated. | |
dc2cf706 PC |
906 | * |
907 | * This function will %resize the %list to the specified number | |
908 | * of elements. If the number is smaller than the %list's | |
909 | * current size the %list is truncated, otherwise the %list is | |
910 | * extended and new elements are populated with given data. | |
911 | */ | |
912 | void | |
913 | resize(size_type __new_size, const value_type& __x); | |
914 | #else | |
4d54539c BK |
915 | /** |
916 | * @brief Resizes the %list to the specified number of elements. | |
93c66bc6 BK |
917 | * @param __new_size Number of elements the %list should contain. |
918 | * @param __x Data with which new elements should be populated. | |
4d54539c BK |
919 | * |
920 | * This function will %resize the %list to the specified number | |
921 | * of elements. If the number is smaller than the %list's | |
922 | * current size the %list is truncated, otherwise the %list is | |
923 | * extended and new elements are populated with given data. | |
924 | */ | |
925 | void | |
2fecaef4 | 926 | resize(size_type __new_size, value_type __x = value_type()); |
dc2cf706 | 927 | #endif |
ed6814f7 | 928 | |
4d54539c BK |
929 | // element access |
930 | /** | |
931 | * Returns a read/write reference to the data at the first | |
932 | * element of the %list. | |
933 | */ | |
934 | reference | |
f6592a9e PC |
935 | front() |
936 | { return *begin(); } | |
ed6814f7 | 937 | |
4d54539c BK |
938 | /** |
939 | * Returns a read-only (constant) reference to the data at the first | |
940 | * element of the %list. | |
941 | */ | |
942 | const_reference | |
f6592a9e PC |
943 | front() const |
944 | { return *begin(); } | |
ed6814f7 | 945 | |
4d54539c BK |
946 | /** |
947 | * Returns a read/write reference to the data at the last element | |
948 | * of the %list. | |
949 | */ | |
950 | reference | |
f6592a9e | 951 | back() |
f4e5280b PC |
952 | { |
953 | iterator __tmp = end(); | |
954 | --__tmp; | |
955 | return *__tmp; | |
956 | } | |
ed6814f7 | 957 | |
4d54539c BK |
958 | /** |
959 | * Returns a read-only (constant) reference to the data at the last | |
960 | * element of the %list. | |
961 | */ | |
962 | const_reference | |
f6592a9e | 963 | back() const |
f4e5280b PC |
964 | { |
965 | const_iterator __tmp = end(); | |
966 | --__tmp; | |
967 | return *__tmp; | |
968 | } | |
ed6814f7 | 969 | |
4d54539c BK |
970 | // [23.2.2.3] modifiers |
971 | /** | |
972 | * @brief Add data to the front of the %list. | |
93c66bc6 | 973 | * @param __x Data to be added. |
4d54539c BK |
974 | * |
975 | * This is a typical stack operation. The function creates an | |
976 | * element at the front of the %list and assigns the given data | |
977 | * to it. Due to the nature of a %list this operation can be | |
978 | * done in constant time, and does not invalidate iterators and | |
979 | * references. | |
980 | */ | |
3971a4d2 | 981 | void |
f6592a9e PC |
982 | push_front(const value_type& __x) |
983 | { this->_M_insert(begin(), __x); } | |
4dc3e453 | 984 | |
734f5023 | 985 | #if __cplusplus >= 201103L |
4dc3e453 PC |
986 | void |
987 | push_front(value_type&& __x) | |
988 | { this->_M_insert(begin(), std::move(__x)); } | |
989 | ||
84237dbb PC |
990 | template<typename... _Args> |
991 | void | |
4dc3e453 PC |
992 | emplace_front(_Args&&... __args) |
993 | { this->_M_insert(begin(), std::forward<_Args>(__args)...); } | |
84237dbb | 994 | #endif |
ed6814f7 | 995 | |
4d54539c BK |
996 | /** |
997 | * @brief Removes first element. | |
998 | * | |
999 | * This is a typical stack operation. It shrinks the %list by | |
1000 | * one. Due to the nature of a %list this operation can be done | |
1001 | * in constant time, and only invalidates iterators/references to | |
1002 | * the element being removed. | |
1003 | * | |
1004 | * Note that no data is returned, and if the first element's data | |
1005 | * is needed, it should be retrieved before pop_front() is | |
1006 | * called. | |
1007 | */ | |
1008 | void | |
f6592a9e PC |
1009 | pop_front() |
1010 | { this->_M_erase(begin()); } | |
ed6814f7 | 1011 | |
4d54539c BK |
1012 | /** |
1013 | * @brief Add data to the end of the %list. | |
93c66bc6 | 1014 | * @param __x Data to be added. |
4d54539c BK |
1015 | * |
1016 | * This is a typical stack operation. The function creates an | |
1017 | * element at the end of the %list and assigns the given data to | |
1018 | * it. Due to the nature of a %list this operation can be done | |
1019 | * in constant time, and does not invalidate iterators and | |
1020 | * references. | |
1021 | */ | |
1022 | void | |
f6592a9e PC |
1023 | push_back(const value_type& __x) |
1024 | { this->_M_insert(end(), __x); } | |
4dc3e453 | 1025 | |
734f5023 | 1026 | #if __cplusplus >= 201103L |
4dc3e453 PC |
1027 | void |
1028 | push_back(value_type&& __x) | |
1029 | { this->_M_insert(end(), std::move(__x)); } | |
1030 | ||
84237dbb PC |
1031 | template<typename... _Args> |
1032 | void | |
4dc3e453 PC |
1033 | emplace_back(_Args&&... __args) |
1034 | { this->_M_insert(end(), std::forward<_Args>(__args)...); } | |
84237dbb | 1035 | #endif |
ed6814f7 | 1036 | |
4d54539c BK |
1037 | /** |
1038 | * @brief Removes last element. | |
1039 | * | |
1040 | * This is a typical stack operation. It shrinks the %list by | |
1041 | * one. Due to the nature of a %list this operation can be done | |
1042 | * in constant time, and only invalidates iterators/references to | |
1043 | * the element being removed. | |
1044 | * | |
1045 | * Note that no data is returned, and if the last element's data | |
1046 | * is needed, it should be retrieved before pop_back() is called. | |
1047 | */ | |
1048 | void | |
f6592a9e | 1049 | pop_back() |
e182017e | 1050 | { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } |
ed6814f7 | 1051 | |
734f5023 | 1052 | #if __cplusplus >= 201103L |
84237dbb PC |
1053 | /** |
1054 | * @brief Constructs object in %list before specified iterator. | |
93c66bc6 BK |
1055 | * @param __position A const_iterator into the %list. |
1056 | * @param __args Arguments. | |
84237dbb PC |
1057 | * @return An iterator that points to the inserted data. |
1058 | * | |
1059 | * This function will insert an object of type T constructed | |
1060 | * with T(std::forward<Args>(args)...) before the specified | |
1061 | * location. Due to the nature of a %list this operation can | |
1062 | * be done in constant time, and does not invalidate iterators | |
1063 | * and references. | |
1064 | */ | |
1065 | template<typename... _Args> | |
1066 | iterator | |
7b61c5a9 | 1067 | emplace(const_iterator __position, _Args&&... __args); |
84237dbb | 1068 | |
7b61c5a9 PC |
1069 | /** |
1070 | * @brief Inserts given value into %list before specified iterator. | |
1071 | * @param __position A const_iterator into the %list. | |
1072 | * @param __x Data to be inserted. | |
1073 | * @return An iterator that points to the inserted data. | |
1074 | * | |
1075 | * This function will insert a copy of the given value before | |
1076 | * the specified location. Due to the nature of a %list this | |
1077 | * operation can be done in constant time, and does not | |
1078 | * invalidate iterators and references. | |
1079 | */ | |
1080 | iterator | |
1081 | insert(const_iterator __position, const value_type& __x); | |
1082 | #else | |
4d54539c BK |
1083 | /** |
1084 | * @brief Inserts given value into %list before specified iterator. | |
93c66bc6 BK |
1085 | * @param __position An iterator into the %list. |
1086 | * @param __x Data to be inserted. | |
4d54539c BK |
1087 | * @return An iterator that points to the inserted data. |
1088 | * | |
1089 | * This function will insert a copy of the given value before | |
1090 | * the specified location. Due to the nature of a %list this | |
1091 | * operation can be done in constant time, and does not | |
1092 | * invalidate iterators and references. | |
1093 | */ | |
1094 | iterator | |
1095 | insert(iterator __position, const value_type& __x); | |
7b61c5a9 | 1096 | #endif |
ed6814f7 | 1097 | |
734f5023 | 1098 | #if __cplusplus >= 201103L |
84237dbb PC |
1099 | /** |
1100 | * @brief Inserts given rvalue into %list before specified iterator. | |
7b61c5a9 | 1101 | * @param __position A const_iterator into the %list. |
93c66bc6 | 1102 | * @param __x Data to be inserted. |
84237dbb PC |
1103 | * @return An iterator that points to the inserted data. |
1104 | * | |
1105 | * This function will insert a copy of the given rvalue before | |
1106 | * the specified location. Due to the nature of a %list this | |
1107 | * operation can be done in constant time, and does not | |
1108 | * invalidate iterators and references. | |
1109 | */ | |
1110 | iterator | |
7b61c5a9 | 1111 | insert(const_iterator __position, value_type&& __x) |
360b7bff | 1112 | { return emplace(__position, std::move(__x)); } |
988499f4 JM |
1113 | |
1114 | /** | |
1115 | * @brief Inserts the contents of an initializer_list into %list | |
019fdb79 PC |
1116 | * before specified const_iterator. |
1117 | * @param __p A const_iterator into the %list. | |
93c66bc6 | 1118 | * @param __l An initializer_list of value_type. |
019fdb79 PC |
1119 | * @return An iterator pointing to the first element inserted |
1120 | * (or __position). | |
988499f4 JM |
1121 | * |
1122 | * This function will insert copies of the data in the | |
1123 | * initializer_list @a l into the %list before the location | |
1124 | * specified by @a p. | |
1125 | * | |
1126 | * This operation is linear in the number of elements inserted and | |
1127 | * does not invalidate iterators and references. | |
1128 | */ | |
019fdb79 PC |
1129 | iterator |
1130 | insert(const_iterator __p, initializer_list<value_type> __l) | |
1131 | { return this->insert(__p, __l.begin(), __l.end()); } | |
84237dbb PC |
1132 | #endif |
1133 | ||
019fdb79 PC |
1134 | #if __cplusplus >= 201103L |
1135 | /** | |
1136 | * @brief Inserts a number of copies of given data into the %list. | |
1137 | * @param __position A const_iterator into the %list. | |
1138 | * @param __n Number of elements to be inserted. | |
1139 | * @param __x Data to be inserted. | |
1140 | * @return An iterator pointing to the first element inserted | |
1141 | * (or __position). | |
1142 | * | |
1143 | * This function will insert a specified number of copies of the | |
1144 | * given data before the location specified by @a position. | |
1145 | * | |
1146 | * This operation is linear in the number of elements inserted and | |
1147 | * does not invalidate iterators and references. | |
1148 | */ | |
1149 | iterator | |
1150 | insert(const_iterator __position, size_type __n, const value_type& __x); | |
1151 | #else | |
4d54539c BK |
1152 | /** |
1153 | * @brief Inserts a number of copies of given data into the %list. | |
93c66bc6 BK |
1154 | * @param __position An iterator into the %list. |
1155 | * @param __n Number of elements to be inserted. | |
1156 | * @param __x Data to be inserted. | |
4d54539c BK |
1157 | * |
1158 | * This function will insert a specified number of copies of the | |
1159 | * given data before the location specified by @a position. | |
1160 | * | |
0cb855b7 PC |
1161 | * This operation is linear in the number of elements inserted and |
1162 | * does not invalidate iterators and references. | |
4d54539c | 1163 | */ |
3971a4d2 | 1164 | void |
4d54539c | 1165 | insert(iterator __position, size_type __n, const value_type& __x) |
ff15f019 PC |
1166 | { |
1167 | list __tmp(__n, __x, get_allocator()); | |
874e360b | 1168 | splice(__position, __tmp); |
0cb855b7 | 1169 | } |
019fdb79 | 1170 | #endif |
ed6814f7 | 1171 | |
019fdb79 | 1172 | #if __cplusplus >= 201103L |
4d54539c BK |
1173 | /** |
1174 | * @brief Inserts a range into the %list. | |
019fdb79 | 1175 | * @param __position A const_iterator into the %list. |
93c66bc6 BK |
1176 | * @param __first An input iterator. |
1177 | * @param __last An input iterator. | |
019fdb79 PC |
1178 | * @return An iterator pointing to the first element inserted |
1179 | * (or __position). | |
4d54539c BK |
1180 | * |
1181 | * This function will insert copies of the data in the range [@a | |
1182 | * first,@a last) into the %list before the location specified by | |
1183 | * @a position. | |
1184 | * | |
0cb855b7 PC |
1185 | * This operation is linear in the number of elements inserted and |
1186 | * does not invalidate iterators and references. | |
4d54539c | 1187 | */ |
2203cb90 PC |
1188 | template<typename _InputIterator, |
1189 | typename = std::_RequireInputIter<_InputIterator>> | |
019fdb79 PC |
1190 | iterator |
1191 | insert(const_iterator __position, _InputIterator __first, | |
1192 | _InputIterator __last); | |
2203cb90 | 1193 | #else |
019fdb79 PC |
1194 | /** |
1195 | * @brief Inserts a range into the %list. | |
1196 | * @param __position An iterator into the %list. | |
1197 | * @param __first An input iterator. | |
1198 | * @param __last An input iterator. | |
1199 | * | |
1200 | * This function will insert copies of the data in the range [@a | |
1201 | * first,@a last) into the %list before the location specified by | |
1202 | * @a position. | |
1203 | * | |
1204 | * This operation is linear in the number of elements inserted and | |
1205 | * does not invalidate iterators and references. | |
1206 | */ | |
4d54539c BK |
1207 | template<typename _InputIterator> |
1208 | void | |
ed6814f7 | 1209 | insert(iterator __position, _InputIterator __first, |
4d54539c BK |
1210 | _InputIterator __last) |
1211 | { | |
ff15f019 | 1212 | list __tmp(__first, __last, get_allocator()); |
0cb855b7 | 1213 | splice(__position, __tmp); |
4d54539c | 1214 | } |
019fdb79 | 1215 | #endif |
ed6814f7 | 1216 | |
4d54539c BK |
1217 | /** |
1218 | * @brief Remove element at given position. | |
93c66bc6 | 1219 | * @param __position Iterator pointing to element to be erased. |
4d54539c BK |
1220 | * @return An iterator pointing to the next element (or end()). |
1221 | * | |
1222 | * This function will erase the element at the given position and thus | |
1223 | * shorten the %list by one. | |
1224 | * | |
1225 | * Due to the nature of a %list this operation can be done in | |
1226 | * constant time, and only invalidates iterators/references to | |
1227 | * the element being removed. The user is also cautioned that | |
1228 | * this function only erases the element, and that if the element | |
1229 | * is itself a pointer, the pointed-to memory is not touched in | |
28dac70a | 1230 | * any way. Managing the pointer is the user's responsibility. |
4d54539c BK |
1231 | */ |
1232 | iterator | |
94938aec PC |
1233 | #if __cplusplus >= 201103L |
1234 | erase(const_iterator __position); | |
1235 | #else | |
4d54539c | 1236 | erase(iterator __position); |
94938aec | 1237 | #endif |
ed6814f7 | 1238 | |
4d54539c BK |
1239 | /** |
1240 | * @brief Remove a range of elements. | |
93c66bc6 BK |
1241 | * @param __first Iterator pointing to the first element to be erased. |
1242 | * @param __last Iterator pointing to one past the last element to be | |
4d54539c BK |
1243 | * erased. |
1244 | * @return An iterator pointing to the element pointed to by @a last | |
1245 | * prior to erasing (or end()). | |
1246 | * | |
1247 | * This function will erase the elements in the range @a | |
1248 | * [first,last) and shorten the %list accordingly. | |
1249 | * | |
0cb855b7 PC |
1250 | * This operation is linear time in the size of the range and only |
1251 | * invalidates iterators/references to the element being removed. | |
1252 | * The user is also cautioned that this function only erases the | |
1253 | * elements, and that if the elements themselves are pointers, the | |
1254 | * pointed-to memory is not touched in any way. Managing the pointer | |
28dac70a | 1255 | * is the user's responsibility. |
4d54539c BK |
1256 | */ |
1257 | iterator | |
94938aec PC |
1258 | #if __cplusplus >= 201103L |
1259 | erase(const_iterator __first, const_iterator __last) | |
1260 | #else | |
4d54539c | 1261 | erase(iterator __first, iterator __last) |
94938aec | 1262 | #endif |
3971a4d2 | 1263 | { |
4d54539c | 1264 | while (__first != __last) |
e135a038 | 1265 | __first = erase(__first); |
94938aec | 1266 | return __last._M_const_cast(); |
3971a4d2 | 1267 | } |
ed6814f7 | 1268 | |
4d54539c BK |
1269 | /** |
1270 | * @brief Swaps data with another %list. | |
93c66bc6 | 1271 | * @param __x A %list of the same element and allocator types. |
4d54539c BK |
1272 | * |
1273 | * This exchanges the elements between two lists in constant | |
1274 | * time. Note that the global std::swap() function is | |
1275 | * specialized such that std::swap(l1,l2) will feed to this | |
1276 | * function. | |
1277 | */ | |
3971a4d2 | 1278 | void |
f6592a9e | 1279 | swap(list& __x) |
f7ace77f | 1280 | { |
12ffa228 BK |
1281 | __detail::_List_node_base::swap(this->_M_impl._M_node, |
1282 | __x._M_impl._M_node); | |
f7ace77f PC |
1283 | |
1284 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1285 | // 431. Swapping containers with unequal allocators. | |
1286 | std::__alloc_swap<typename _Base::_Node_alloc_type>:: | |
1287 | _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator()); | |
1288 | } | |
ed6814f7 | 1289 | |
4d54539c BK |
1290 | /** |
1291 | * Erases all the elements. Note that this function only erases | |
1292 | * the elements, and that if the elements themselves are | |
1293 | * pointers, the pointed-to memory is not touched in any way. | |
28dac70a | 1294 | * Managing the pointer is the user's responsibility. |
4d54539c | 1295 | */ |
3971a4d2 | 1296 | void |
d3677132 | 1297 | clear() _GLIBCXX_NOEXCEPT |
e135a038 BK |
1298 | { |
1299 | _Base::_M_clear(); | |
1300 | _Base::_M_init(); | |
1301 | } | |
ed6814f7 | 1302 | |
4d54539c BK |
1303 | // [23.2.2.4] list operations |
1304 | /** | |
1305 | * @brief Insert contents of another %list. | |
93c66bc6 BK |
1306 | * @param __position Iterator referencing the element to insert before. |
1307 | * @param __x Source list. | |
4d54539c | 1308 | * |
93c66bc6 BK |
1309 | * The elements of @a __x are inserted in constant time in front of |
1310 | * the element referenced by @a __position. @a __x becomes an empty | |
4d54539c | 1311 | * list. |
af8590d2 | 1312 | * |
93c66bc6 | 1313 | * Requires this != @a __x. |
4d54539c | 1314 | */ |
3971a4d2 | 1315 | void |
734f5023 | 1316 | #if __cplusplus >= 201103L |
019fdb79 | 1317 | splice(const_iterator __position, list&& __x) |
84237dbb | 1318 | #else |
4d54539c | 1319 | splice(iterator __position, list& __x) |
84237dbb | 1320 | #endif |
4d54539c BK |
1321 | { |
1322 | if (!__x.empty()) | |
af8590d2 PC |
1323 | { |
1324 | _M_check_equal_allocators(__x); | |
1325 | ||
019fdb79 PC |
1326 | this->_M_transfer(__position._M_const_cast(), |
1327 | __x.begin(), __x.end()); | |
af8590d2 | 1328 | } |
4d54539c | 1329 | } |
ed6814f7 | 1330 | |
734f5023 | 1331 | #if __cplusplus >= 201103L |
874e360b | 1332 | void |
019fdb79 | 1333 | splice(const_iterator __position, list& __x) |
874e360b PC |
1334 | { splice(__position, std::move(__x)); } |
1335 | #endif | |
1336 | ||
019fdb79 PC |
1337 | #if __cplusplus >= 201103L |
1338 | /** | |
1339 | * @brief Insert element from another %list. | |
1340 | * @param __position Const_iterator referencing the element to | |
1341 | * insert before. | |
1342 | * @param __x Source list. | |
1343 | * @param __i Const_iterator referencing the element to move. | |
1344 | * | |
1345 | * Removes the element in list @a __x referenced by @a __i and | |
1346 | * inserts it into the current list before @a __position. | |
1347 | */ | |
1348 | void | |
1349 | splice(const_iterator __position, list&& __x, const_iterator __i) | |
1350 | #else | |
4d54539c BK |
1351 | /** |
1352 | * @brief Insert element from another %list. | |
93c66bc6 BK |
1353 | * @param __position Iterator referencing the element to insert before. |
1354 | * @param __x Source list. | |
1355 | * @param __i Iterator referencing the element to move. | |
4d54539c | 1356 | * |
93c66bc6 BK |
1357 | * Removes the element in list @a __x referenced by @a __i and |
1358 | * inserts it into the current list before @a __position. | |
4d54539c | 1359 | */ |
3971a4d2 | 1360 | void |
af8590d2 | 1361 | splice(iterator __position, list& __x, iterator __i) |
84237dbb | 1362 | #endif |
4d54539c | 1363 | { |
019fdb79 | 1364 | iterator __j = __i._M_const_cast(); |
4d54539c | 1365 | ++__j; |
f6592a9e PC |
1366 | if (__position == __i || __position == __j) |
1367 | return; | |
af8590d2 PC |
1368 | |
1369 | if (this != &__x) | |
d695f915 | 1370 | _M_check_equal_allocators(__x); |
af8590d2 | 1371 | |
019fdb79 PC |
1372 | this->_M_transfer(__position._M_const_cast(), |
1373 | __i._M_const_cast(), __j); | |
4d54539c | 1374 | } |
ed6814f7 | 1375 | |
734f5023 | 1376 | #if __cplusplus >= 201103L |
019fdb79 PC |
1377 | /** |
1378 | * @brief Insert element from another %list. | |
1379 | * @param __position Const_iterator referencing the element to | |
1380 | * insert before. | |
1381 | * @param __x Source list. | |
1382 | * @param __i Const_iterator referencing the element to move. | |
1383 | * | |
1384 | * Removes the element in list @a __x referenced by @a __i and | |
1385 | * inserts it into the current list before @a __position. | |
1386 | */ | |
874e360b | 1387 | void |
019fdb79 | 1388 | splice(const_iterator __position, list& __x, const_iterator __i) |
874e360b PC |
1389 | { splice(__position, std::move(__x), __i); } |
1390 | #endif | |
1391 | ||
019fdb79 PC |
1392 | #if __cplusplus >= 201103L |
1393 | /** | |
1394 | * @brief Insert range from another %list. | |
1395 | * @param __position Const_iterator referencing the element to | |
1396 | * insert before. | |
1397 | * @param __x Source list. | |
1398 | * @param __first Const_iterator referencing the start of range in x. | |
1399 | * @param __last Const_iterator referencing the end of range in x. | |
1400 | * | |
1401 | * Removes elements in the range [__first,__last) and inserts them | |
1402 | * before @a __position in constant time. | |
1403 | * | |
1404 | * Undefined if @a __position is in [__first,__last). | |
1405 | */ | |
1406 | void | |
1407 | splice(const_iterator __position, list&& __x, const_iterator __first, | |
1408 | const_iterator __last) | |
1409 | #else | |
4d54539c BK |
1410 | /** |
1411 | * @brief Insert range from another %list. | |
93c66bc6 BK |
1412 | * @param __position Iterator referencing the element to insert before. |
1413 | * @param __x Source list. | |
1414 | * @param __first Iterator referencing the start of range in x. | |
1415 | * @param __last Iterator referencing the end of range in x. | |
4d54539c | 1416 | * |
93c66bc6 BK |
1417 | * Removes elements in the range [__first,__last) and inserts them |
1418 | * before @a __position in constant time. | |
4d54539c | 1419 | * |
93c66bc6 | 1420 | * Undefined if @a __position is in [__first,__last). |
4d54539c | 1421 | */ |
3971a4d2 | 1422 | void |
84237dbb PC |
1423 | splice(iterator __position, list& __x, iterator __first, |
1424 | iterator __last) | |
1425 | #endif | |
3971a4d2 | 1426 | { |
4d54539c | 1427 | if (__first != __last) |
af8590d2 PC |
1428 | { |
1429 | if (this != &__x) | |
d695f915 | 1430 | _M_check_equal_allocators(__x); |
af8590d2 | 1431 | |
019fdb79 PC |
1432 | this->_M_transfer(__position._M_const_cast(), |
1433 | __first._M_const_cast(), | |
1434 | __last._M_const_cast()); | |
af8590d2 | 1435 | } |
3971a4d2 | 1436 | } |
ed6814f7 | 1437 | |
734f5023 | 1438 | #if __cplusplus >= 201103L |
019fdb79 PC |
1439 | /** |
1440 | * @brief Insert range from another %list. | |
1441 | * @param __position Const_iterator referencing the element to | |
1442 | * insert before. | |
1443 | * @param __x Source list. | |
1444 | * @param __first Const_iterator referencing the start of range in x. | |
1445 | * @param __last Const_iterator referencing the end of range in x. | |
1446 | * | |
1447 | * Removes elements in the range [__first,__last) and inserts them | |
1448 | * before @a __position in constant time. | |
1449 | * | |
1450 | * Undefined if @a __position is in [__first,__last). | |
1451 | */ | |
874e360b | 1452 | void |
019fdb79 PC |
1453 | splice(const_iterator __position, list& __x, const_iterator __first, |
1454 | const_iterator __last) | |
874e360b PC |
1455 | { splice(__position, std::move(__x), __first, __last); } |
1456 | #endif | |
1457 | ||
4d54539c BK |
1458 | /** |
1459 | * @brief Remove all elements equal to value. | |
93c66bc6 | 1460 | * @param __value The value to remove. |
4d54539c BK |
1461 | * |
1462 | * Removes every element in the list equal to @a value. | |
1463 | * Remaining elements stay in list order. Note that this | |
1464 | * function only erases the elements, and that if the elements | |
1465 | * themselves are pointers, the pointed-to memory is not | |
1466 | * touched in any way. Managing the pointer is the user's | |
28dac70a | 1467 | * responsibility. |
4d54539c | 1468 | */ |
3971a4d2 | 1469 | void |
4d54539c | 1470 | remove(const _Tp& __value); |
ed6814f7 | 1471 | |
4d54539c BK |
1472 | /** |
1473 | * @brief Remove all elements satisfying a predicate. | |
93c66bc6 | 1474 | * @tparam _Predicate Unary predicate function or object. |
4d54539c BK |
1475 | * |
1476 | * Removes every element in the list for which the predicate | |
1477 | * returns true. Remaining elements stay in list order. Note | |
1478 | * that this function only erases the elements, and that if the | |
1479 | * elements themselves are pointers, the pointed-to memory is | |
1480 | * not touched in any way. Managing the pointer is the user's | |
28dac70a | 1481 | * responsibility. |
4d54539c BK |
1482 | */ |
1483 | template<typename _Predicate> | |
af8590d2 PC |
1484 | void |
1485 | remove_if(_Predicate); | |
ed6814f7 | 1486 | |
4d54539c BK |
1487 | /** |
1488 | * @brief Remove consecutive duplicate elements. | |
1489 | * | |
1490 | * For each consecutive set of elements with the same value, | |
1491 | * remove all but the first one. Remaining elements stay in | |
1492 | * list order. Note that this function only erases the | |
1493 | * elements, and that if the elements themselves are pointers, | |
1494 | * the pointed-to memory is not touched in any way. Managing | |
28dac70a | 1495 | * the pointer is the user's responsibility. |
4d54539c BK |
1496 | */ |
1497 | void | |
1498 | unique(); | |
ed6814f7 | 1499 | |
4d54539c BK |
1500 | /** |
1501 | * @brief Remove consecutive elements satisfying a predicate. | |
93c66bc6 | 1502 | * @tparam _BinaryPredicate Binary predicate function or object. |
4d54539c BK |
1503 | * |
1504 | * For each consecutive set of elements [first,last) that | |
1505 | * satisfy predicate(first,i) where i is an iterator in | |
1506 | * [first,last), remove all but the first one. Remaining | |
1507 | * elements stay in list order. Note that this function only | |
1508 | * erases the elements, and that if the elements themselves are | |
1509 | * pointers, the pointed-to memory is not touched in any way. | |
28dac70a | 1510 | * Managing the pointer is the user's responsibility. |
4d54539c BK |
1511 | */ |
1512 | template<typename _BinaryPredicate> | |
1513 | void | |
1514 | unique(_BinaryPredicate); | |
ed6814f7 | 1515 | |
4d54539c BK |
1516 | /** |
1517 | * @brief Merge sorted lists. | |
93c66bc6 | 1518 | * @param __x Sorted list to merge. |
4d54539c | 1519 | * |
93c66bc6 BK |
1520 | * Assumes that both @a __x and this list are sorted according to |
1521 | * operator<(). Merges elements of @a __x into this list in | |
1522 | * sorted order, leaving @a __x empty when complete. Elements in | |
1523 | * this list precede elements in @a __x that are equal. | |
4d54539c | 1524 | */ |
734f5023 | 1525 | #if __cplusplus >= 201103L |
874e360b | 1526 | void |
84237dbb | 1527 | merge(list&& __x); |
874e360b PC |
1528 | |
1529 | void | |
1530 | merge(list& __x) | |
1531 | { merge(std::move(__x)); } | |
84237dbb | 1532 | #else |
874e360b | 1533 | void |
4d54539c | 1534 | merge(list& __x); |
84237dbb | 1535 | #endif |
ed6814f7 | 1536 | |
4d54539c BK |
1537 | /** |
1538 | * @brief Merge sorted lists according to comparison function. | |
93c66bc6 | 1539 | * @tparam _StrictWeakOrdering Comparison function defining |
4d54539c | 1540 | * sort order. |
7897a1c0 BK |
1541 | * @param __x Sorted list to merge. |
1542 | * @param __comp Comparison functor. | |
4d54539c | 1543 | * |
93c66bc6 BK |
1544 | * Assumes that both @a __x and this list are sorted according to |
1545 | * StrictWeakOrdering. Merges elements of @a __x into this list | |
1546 | * in sorted order, leaving @a __x empty when complete. Elements | |
1547 | * in this list precede elements in @a __x that are equivalent | |
4d54539c BK |
1548 | * according to StrictWeakOrdering(). |
1549 | */ | |
734f5023 | 1550 | #if __cplusplus >= 201103L |
4d54539c BK |
1551 | template<typename _StrictWeakOrdering> |
1552 | void | |
93c66bc6 | 1553 | merge(list&& __x, _StrictWeakOrdering __comp); |
874e360b PC |
1554 | |
1555 | template<typename _StrictWeakOrdering> | |
1556 | void | |
1557 | merge(list& __x, _StrictWeakOrdering __comp) | |
1558 | { merge(std::move(__x), __comp); } | |
84237dbb | 1559 | #else |
874e360b PC |
1560 | template<typename _StrictWeakOrdering> |
1561 | void | |
93c66bc6 | 1562 | merge(list& __x, _StrictWeakOrdering __comp); |
84237dbb | 1563 | #endif |
ed6814f7 | 1564 | |
4d54539c BK |
1565 | /** |
1566 | * @brief Reverse the elements in list. | |
1567 | * | |
1568 | * Reverse the order of elements in the list in linear time. | |
1569 | */ | |
1570 | void | |
d3677132 | 1571 | reverse() _GLIBCXX_NOEXCEPT |
240c7f7f | 1572 | { this->_M_impl._M_node._M_reverse(); } |
ed6814f7 | 1573 | |
4d54539c BK |
1574 | /** |
1575 | * @brief Sort the elements. | |
1576 | * | |
1577 | * Sorts the elements of this list in NlogN time. Equivalent | |
1578 | * elements remain in list order. | |
1579 | */ | |
1580 | void | |
1581 | sort(); | |
ed6814f7 | 1582 | |
4d54539c BK |
1583 | /** |
1584 | * @brief Sort the elements according to comparison function. | |
1585 | * | |
1586 | * Sorts the elements of this list in NlogN time. Equivalent | |
1587 | * elements remain in list order. | |
1588 | */ | |
1589 | template<typename _StrictWeakOrdering> | |
1590 | void | |
1591 | sort(_StrictWeakOrdering); | |
ed6814f7 | 1592 | |
4d54539c | 1593 | protected: |
0cb855b7 | 1594 | // Internal constructor functions follow. |
ed6814f7 | 1595 | |
0cb855b7 | 1596 | // Called by the range constructor to implement [23.1.1]/9 |
25959e29 PC |
1597 | |
1598 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1599 | // 438. Ambiguity in the "do the right thing" clause | |
4d54539c BK |
1600 | template<typename _Integer> |
1601 | void | |
0cb855b7 | 1602 | _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) |
25959e29 | 1603 | { _M_fill_initialize(static_cast<size_type>(__n), __x); } |
ed6814f7 | 1604 | |
0cb855b7 | 1605 | // Called by the range constructor to implement [23.1.1]/9 |
4d54539c BK |
1606 | template<typename _InputIterator> |
1607 | void | |
0cb855b7 PC |
1608 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |
1609 | __false_type) | |
1610 | { | |
1611 | for (; __first != __last; ++__first) | |
b4904956 PC |
1612 | #if __cplusplus >= 201103L |
1613 | emplace_back(*__first); | |
1614 | #else | |
0cb855b7 | 1615 | push_back(*__first); |
b4904956 | 1616 | #endif |
0cb855b7 | 1617 | } |
ed6814f7 | 1618 | |
0cb855b7 | 1619 | // Called by list(n,v,a), and the range constructor when it turns out |
4d54539c | 1620 | // to be the same thing. |
3971a4d2 | 1621 | void |
0cb855b7 PC |
1622 | _M_fill_initialize(size_type __n, const value_type& __x) |
1623 | { | |
dc2cf706 | 1624 | for (; __n; --__n) |
0cb855b7 PC |
1625 | push_back(__x); |
1626 | } | |
ed6814f7 | 1627 | |
734f5023 | 1628 | #if __cplusplus >= 201103L |
dc2cf706 PC |
1629 | // Called by list(n). |
1630 | void | |
1631 | _M_default_initialize(size_type __n) | |
1632 | { | |
1633 | for (; __n; --__n) | |
1634 | emplace_back(); | |
1635 | } | |
1636 | ||
1637 | // Called by resize(sz). | |
1638 | void | |
1639 | _M_default_append(size_type __n); | |
1640 | #endif | |
ed6814f7 | 1641 | |
0cb855b7 | 1642 | // Internal assign functions follow. |
ed6814f7 | 1643 | |
0cb855b7 | 1644 | // Called by the range assign to implement [23.1.1]/9 |
25959e29 PC |
1645 | |
1646 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
1647 | // 438. Ambiguity in the "do the right thing" clause | |
4d54539c BK |
1648 | template<typename _Integer> |
1649 | void | |
0cb855b7 | 1650 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) |
25959e29 | 1651 | { _M_fill_assign(__n, __val); } |
ed6814f7 | 1652 | |
0cb855b7 | 1653 | // Called by the range assign to implement [23.1.1]/9 |
4d54539c BK |
1654 | template<typename _InputIterator> |
1655 | void | |
0cb855b7 PC |
1656 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |
1657 | __false_type); | |
ed6814f7 | 1658 | |
0cb855b7 | 1659 | // Called by assign(n,t), and the range assign when it turns out |
4d54539c BK |
1660 | // to be the same thing. |
1661 | void | |
0cb855b7 | 1662 | _M_fill_assign(size_type __n, const value_type& __val); |
ed6814f7 BI |
1663 | |
1664 | ||
4d54539c | 1665 | // Moves the elements from [first,last) before position. |
3971a4d2 | 1666 | void |
4d54539c | 1667 | _M_transfer(iterator __position, iterator __first, iterator __last) |
240c7f7f | 1668 | { __position._M_node->_M_transfer(__first._M_node, __last._M_node); } |
e135a038 BK |
1669 | |
1670 | // Inserts new element at position given and with value given. | |
734f5023 | 1671 | #if __cplusplus < 201103L |
e135a038 BK |
1672 | void |
1673 | _M_insert(iterator __position, const value_type& __x) | |
1674 | { | |
1675 | _Node* __tmp = _M_create_node(__x); | |
240c7f7f | 1676 | __tmp->_M_hook(__position._M_node); |
e135a038 | 1677 | } |
84237dbb PC |
1678 | #else |
1679 | template<typename... _Args> | |
1680 | void | |
1681 | _M_insert(iterator __position, _Args&&... __args) | |
1682 | { | |
1683 | _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); | |
240c7f7f | 1684 | __tmp->_M_hook(__position._M_node); |
84237dbb PC |
1685 | } |
1686 | #endif | |
e135a038 BK |
1687 | |
1688 | // Erases element at position given. | |
1689 | void | |
1690 | _M_erase(iterator __position) | |
1691 | { | |
240c7f7f | 1692 | __position._M_node->_M_unhook(); |
e135a038 | 1693 | _Node* __n = static_cast<_Node*>(__position._M_node); |
734f5023 | 1694 | #if __cplusplus >= 201103L |
c841843f PC |
1695 | _M_get_Node_allocator().destroy(__n); |
1696 | #else | |
882b3d5c | 1697 | _M_get_Tp_allocator().destroy(std::__addressof(__n->_M_data)); |
c841843f | 1698 | #endif |
e135a038 | 1699 | _M_put_node(__n); |
3971a4d2 | 1700 | } |
af8590d2 PC |
1701 | |
1702 | // To implement the splice (and merge) bits of N1599. | |
1703 | void | |
1704 | _M_check_equal_allocators(list& __x) | |
1705 | { | |
67202da4 PC |
1706 | if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: |
1707 | _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) | |
af8590d2 PC |
1708 | __throw_runtime_error(__N("list::_M_check_equal_allocators")); |
1709 | } | |
4d54539c | 1710 | }; |
ed6814f7 | 1711 | |
3971a4d2 PE |
1712 | /** |
1713 | * @brief List equality comparison. | |
93c66bc6 BK |
1714 | * @param __x A %list. |
1715 | * @param __y A %list of the same type as @a __x. | |
3971a4d2 PE |
1716 | * @return True iff the size and elements of the lists are equal. |
1717 | * | |
285b36d6 BK |
1718 | * This is an equivalence relation. It is linear in the size of |
1719 | * the lists. Lists are considered equivalent if their sizes are | |
1720 | * equal, and if corresponding elements compare equal. | |
3971a4d2 PE |
1721 | */ |
1722 | template<typename _Tp, typename _Alloc> | |
4d54539c | 1723 | inline bool |
11aaf40c | 1724 | operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
3971a4d2 | 1725 | { |
11aaf40c | 1726 | typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; |
3971a4d2 PE |
1727 | const_iterator __end1 = __x.end(); |
1728 | const_iterator __end2 = __y.end(); | |
ed6814f7 | 1729 | |
3971a4d2 PE |
1730 | const_iterator __i1 = __x.begin(); |
1731 | const_iterator __i2 = __y.begin(); | |
ed6814f7 | 1732 | while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) |
4d54539c BK |
1733 | { |
1734 | ++__i1; | |
1735 | ++__i2; | |
f6592a9e | 1736 | } |
3971a4d2 PE |
1737 | return __i1 == __end1 && __i2 == __end2; |
1738 | } | |
ed6814f7 | 1739 | |
3971a4d2 PE |
1740 | /** |
1741 | * @brief List ordering relation. | |
93c66bc6 BK |
1742 | * @param __x A %list. |
1743 | * @param __y A %list of the same type as @a __x. | |
1744 | * @return True iff @a __x is lexicographically less than @a __y. | |
3971a4d2 PE |
1745 | * |
1746 | * This is a total ordering relation. It is linear in the size of the | |
1747 | * lists. The elements must be comparable with @c <. | |
1748 | * | |
9536ca34 | 1749 | * See std::lexicographical_compare() for how the determination is made. |
3971a4d2 PE |
1750 | */ |
1751 | template<typename _Tp, typename _Alloc> | |
1752 | inline bool | |
11aaf40c | 1753 | operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
f6592a9e PC |
1754 | { return std::lexicographical_compare(__x.begin(), __x.end(), |
1755 | __y.begin(), __y.end()); } | |
ed6814f7 | 1756 | |
3971a4d2 PE |
1757 | /// Based on operator== |
1758 | template<typename _Tp, typename _Alloc> | |
1759 | inline bool | |
11aaf40c | 1760 | operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
3971a4d2 | 1761 | { return !(__x == __y); } |
ed6814f7 | 1762 | |
3971a4d2 PE |
1763 | /// Based on operator< |
1764 | template<typename _Tp, typename _Alloc> | |
1765 | inline bool | |
11aaf40c | 1766 | operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
3971a4d2 | 1767 | { return __y < __x; } |
ed6814f7 | 1768 | |
3971a4d2 PE |
1769 | /// Based on operator< |
1770 | template<typename _Tp, typename _Alloc> | |
1771 | inline bool | |
11aaf40c | 1772 | operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
3971a4d2 | 1773 | { return !(__y < __x); } |
ed6814f7 | 1774 | |
3971a4d2 PE |
1775 | /// Based on operator< |
1776 | template<typename _Tp, typename _Alloc> | |
1777 | inline bool | |
11aaf40c | 1778 | operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |
3971a4d2 | 1779 | { return !(__x < __y); } |
ed6814f7 | 1780 | |
3971a4d2 PE |
1781 | /// See std::list::swap(). |
1782 | template<typename _Tp, typename _Alloc> | |
1783 | inline void | |
1784 | swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) | |
1785 | { __x.swap(__y); } | |
3cbc7af0 | 1786 | |
12ffa228 BK |
1787 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1788 | } // namespace std | |
725dc051 | 1789 | |
046d30f4 | 1790 | #endif /* _STL_LIST_H */ |