1 | // List implementation -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2001-2017 Free Software Foundation, Inc. |

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 |

8 | // Free Software Foundation; either version 3, or (at your option) |

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 | |

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. |

19 | |

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/>. |

24 | |

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 | |

51 | /** @file bits/stl_list.h |

52 | * This is an internal header file, included by other library headers. |

53 | * Do not attempt to use it directly. @headername{list} |

54 | */ |

55 | |

56 | #ifndef _STL_LIST_H |

57 | #define _STL_LIST_H 1 |

58 | |

59 | #include <bits/concept_check.h> |

60 | #include <ext/alloc_traits.h> |

61 | #if __cplusplus >= 201103L |

62 | #include <initializer_list> |

63 | #include <bits/allocated_ptr.h> |

64 | #include <ext/aligned_buffer.h> |

65 | #endif |

66 | |

67 | namespace std _GLIBCXX_VISIBILITY(default) |

68 | { |

69 | namespace __detail |

70 | { |

71 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

72 | |

73 | // Supporting structures are split into common and templated |

74 | // types; the latter publicly inherits from the former in an |

75 | // effort to reduce code duplication. This results in some |

76 | // "needless" static_cast'ing later on, but it's all safe |

77 | // downcasting. |

78 | |

79 | /// Common part of a node in the %list. |

80 | struct _List_node_base |

81 | { |

82 | _List_node_base* _M_next; |

83 | _List_node_base* _M_prev; |

84 | |

85 | static void |

86 | swap(_List_node_base& __x, _List_node_base& __y) _GLIBCXX_USE_NOEXCEPT; |

87 | |

88 | void |

89 | _M_transfer(_List_node_base* const __first, |

90 | _List_node_base* const __last) _GLIBCXX_USE_NOEXCEPT; |

91 | |

92 | void |

93 | _M_reverse() _GLIBCXX_USE_NOEXCEPT; |

94 | |

95 | void |

96 | _M_hook(_List_node_base* const __position) _GLIBCXX_USE_NOEXCEPT; |

97 | |

98 | void |

99 | _M_unhook() _GLIBCXX_USE_NOEXCEPT; |

100 | }; |

101 | |

102 | _GLIBCXX_END_NAMESPACE_VERSION |

103 | } // namespace detail |

104 | |

105 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

106 | |

107 | /// An actual node in the %list. |

108 | template<typename _Tp> |

109 | struct _List_node : public __detail::_List_node_base |

110 | { |

111 | #if __cplusplus >= 201103L |

112 | __gnu_cxx::__aligned_membuf<_Tp> _M_storage; |

113 | _Tp* _M_valptr() { return _M_storage._M_ptr(); } |

114 | _Tp const* _M_valptr() const { return _M_storage._M_ptr(); } |

115 | #else |

116 | _Tp _M_data; |

117 | _Tp* _M_valptr() { return std::__addressof(_M_data); } |

118 | _Tp const* _M_valptr() const { return std::__addressof(_M_data); } |

119 | #endif |

120 | }; |

121 | |

122 | /** |

123 | * @brief A list::iterator. |

124 | * |

125 | * All the functions are op overloads. |

126 | */ |

127 | template<typename _Tp> |

128 | struct _List_iterator |

129 | { |

130 | typedef _List_iterator<_Tp> _Self; |

131 | typedef _List_node<_Tp> _Node; |

132 | |

133 | typedef ptrdiff_t difference_type; |

134 | typedef std::bidirectional_iterator_tag iterator_category; |

135 | typedef _Tp value_type; |

136 | typedef _Tp* pointer; |

137 | typedef _Tp& reference; |

138 | |

139 | _List_iterator() _GLIBCXX_NOEXCEPT |

140 | : _M_node() { } |

141 | |

142 | explicit |

143 | _List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT |

144 | : _M_node(__x) { } |

145 | |

146 | _Self |

147 | _M_const_cast() const _GLIBCXX_NOEXCEPT |

148 | { return *this; } |

149 | |

150 | // Must downcast from _List_node_base to _List_node to get to value. |

151 | reference |

152 | operator*() const _GLIBCXX_NOEXCEPT |

153 | { return *static_cast<_Node*>(_M_node)->_M_valptr(); } |

154 | |

155 | pointer |

156 | operator->() const _GLIBCXX_NOEXCEPT |

157 | { return static_cast<_Node*>(_M_node)->_M_valptr(); } |

158 | |

159 | _Self& |

160 | operator++() _GLIBCXX_NOEXCEPT |

161 | { |

162 | _M_node = _M_node->_M_next; |

163 | return *this; |

164 | } |

165 | |

166 | _Self |

167 | operator++(int) _GLIBCXX_NOEXCEPT |

168 | { |

169 | _Self __tmp = *this; |

170 | _M_node = _M_node->_M_next; |

171 | return __tmp; |

172 | } |

173 | |

174 | _Self& |

175 | operator--() _GLIBCXX_NOEXCEPT |

176 | { |

177 | _M_node = _M_node->_M_prev; |

178 | return *this; |

179 | } |

180 | |

181 | _Self |

182 | operator--(int) _GLIBCXX_NOEXCEPT |

183 | { |

184 | _Self __tmp = *this; |

185 | _M_node = _M_node->_M_prev; |

186 | return __tmp; |

187 | } |

188 | |

189 | bool |

190 | operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT |

191 | { return _M_node == __x._M_node; } |

192 | |

193 | bool |

194 | operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT |

195 | { return _M_node != __x._M_node; } |

196 | |

197 | // The only member points to the %list element. |

198 | __detail::_List_node_base* _M_node; |

199 | }; |

200 | |

201 | /** |

202 | * @brief A list::const_iterator. |

203 | * |

204 | * All the functions are op overloads. |

205 | */ |

206 | template<typename _Tp> |

207 | struct _List_const_iterator |

208 | { |

209 | typedef _List_const_iterator<_Tp> _Self; |

210 | typedef const _List_node<_Tp> _Node; |

211 | typedef _List_iterator<_Tp> iterator; |

212 | |

213 | typedef ptrdiff_t difference_type; |

214 | typedef std::bidirectional_iterator_tag iterator_category; |

215 | typedef _Tp value_type; |

216 | typedef const _Tp* pointer; |

217 | typedef const _Tp& reference; |

218 | |

219 | _List_const_iterator() _GLIBCXX_NOEXCEPT |

220 | : _M_node() { } |

221 | |

222 | explicit |

223 | _List_const_iterator(const __detail::_List_node_base* __x) |

224 | _GLIBCXX_NOEXCEPT |

225 | : _M_node(__x) { } |

226 | |

227 | _List_const_iterator(const iterator& __x) _GLIBCXX_NOEXCEPT |

228 | : _M_node(__x._M_node) { } |

229 | |

230 | iterator |

231 | _M_const_cast() const _GLIBCXX_NOEXCEPT |

232 | { return iterator(const_cast<__detail::_List_node_base*>(_M_node)); } |

233 | |

234 | // Must downcast from List_node_base to _List_node to get to value. |

235 | reference |

236 | operator*() const _GLIBCXX_NOEXCEPT |

237 | { return *static_cast<_Node*>(_M_node)->_M_valptr(); } |

238 | |

239 | pointer |

240 | operator->() const _GLIBCXX_NOEXCEPT |

241 | { return static_cast<_Node*>(_M_node)->_M_valptr(); } |

242 | |

243 | _Self& |

244 | operator++() _GLIBCXX_NOEXCEPT |

245 | { |

246 | _M_node = _M_node->_M_next; |

247 | return *this; |

248 | } |

249 | |

250 | _Self |

251 | operator++(int) _GLIBCXX_NOEXCEPT |

252 | { |

253 | _Self __tmp = *this; |

254 | _M_node = _M_node->_M_next; |

255 | return __tmp; |

256 | } |

257 | |

258 | _Self& |

259 | operator--() _GLIBCXX_NOEXCEPT |

260 | { |

261 | _M_node = _M_node->_M_prev; |

262 | return *this; |

263 | } |

264 | |

265 | _Self |

266 | operator--(int) _GLIBCXX_NOEXCEPT |

267 | { |

268 | _Self __tmp = *this; |

269 | _M_node = _M_node->_M_prev; |

270 | return __tmp; |

271 | } |

272 | |

273 | bool |

274 | operator==(const _Self& __x) const _GLIBCXX_NOEXCEPT |

275 | { return _M_node == __x._M_node; } |

276 | |

277 | bool |

278 | operator!=(const _Self& __x) const _GLIBCXX_NOEXCEPT |

279 | { return _M_node != __x._M_node; } |

280 | |

281 | // The only member points to the %list element. |

282 | const __detail::_List_node_base* _M_node; |

283 | }; |

284 | |

285 | template<typename _Val> |

286 | inline bool |

287 | operator==(const _List_iterator<_Val>& __x, |

288 | const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT |

289 | { return __x._M_node == __y._M_node; } |

290 | |

291 | template<typename _Val> |

292 | inline bool |

293 | operator!=(const _List_iterator<_Val>& __x, |

294 | const _List_const_iterator<_Val>& __y) _GLIBCXX_NOEXCEPT |

295 | { return __x._M_node != __y._M_node; } |

296 | |

297 | _GLIBCXX_BEGIN_NAMESPACE_CXX11 |

298 | /// See bits/stl_deque.h's _Deque_base for an explanation. |

299 | template<typename _Tp, typename _Alloc> |

300 | class _List_base |

301 | { |

302 | protected: |

303 | typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template |

304 | rebind<_Tp>::other _Tp_alloc_type; |

305 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tp_alloc_traits; |

306 | typedef typename _Tp_alloc_traits::template |

307 | rebind<_List_node<_Tp> >::other _Node_alloc_type; |

308 | typedef __gnu_cxx::__alloc_traits<_Node_alloc_type> _Node_alloc_traits; |

309 | |

310 | static size_t |

311 | _S_distance(const __detail::_List_node_base* __first, |

312 | const __detail::_List_node_base* __last) |

313 | { |

314 | size_t __n = 0; |

315 | while (__first != __last) |

316 | { |

317 | __first = __first->_M_next; |

318 | ++__n; |

319 | } |

320 | return __n; |

321 | } |

322 | |

323 | struct _List_impl |

324 | : public _Node_alloc_type |

325 | { |

326 | #if _GLIBCXX_USE_CXX11_ABI |

327 | _List_node<size_t> _M_node; |

328 | #else |

329 | __detail::_List_node_base _M_node; |

330 | #endif |

331 | |

332 | _List_impl() _GLIBCXX_NOEXCEPT |

333 | : _Node_alloc_type(), _M_node() |

334 | { } |

335 | |

336 | _List_impl(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT |

337 | : _Node_alloc_type(__a), _M_node() |

338 | { } |

339 | |

340 | #if __cplusplus >= 201103L |

341 | _List_impl(_Node_alloc_type&& __a) noexcept |

342 | : _Node_alloc_type(std::move(__a)), _M_node() |

343 | { } |

344 | #endif |

345 | }; |

346 | |

347 | _List_impl _M_impl; |

348 | |

349 | #if _GLIBCXX_USE_CXX11_ABI |

350 | size_t _M_get_size() const { return *_M_impl._M_node._M_valptr(); } |

351 | |

352 | void _M_set_size(size_t __n) { *_M_impl._M_node._M_valptr() = __n; } |

353 | |

354 | void _M_inc_size(size_t __n) { *_M_impl._M_node._M_valptr() += __n; } |

355 | |

356 | void _M_dec_size(size_t __n) { *_M_impl._M_node._M_valptr() -= __n; } |

357 | |

358 | size_t |

359 | _M_distance(const __detail::_List_node_base* __first, |

360 | const __detail::_List_node_base* __last) const |

361 | { return _S_distance(__first, __last); } |

362 | |

363 | // return the stored size |

364 | size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); } |

365 | #else |

366 | // dummy implementations used when the size is not stored |

367 | size_t _M_get_size() const { return 0; } |

368 | void _M_set_size(size_t) { } |

369 | void _M_inc_size(size_t) { } |

370 | void _M_dec_size(size_t) { } |

371 | size_t _M_distance(const void*, const void*) const { return 0; } |

372 | |

373 | // count the number of nodes |

374 | size_t _M_node_count() const |

375 | { |

376 | return _S_distance(_M_impl._M_node._M_next, |

377 | std::__addressof(_M_impl._M_node)); |

378 | } |

379 | #endif |

380 | |

381 | typename _Node_alloc_traits::pointer |

382 | _M_get_node() |

383 | { return _Node_alloc_traits::allocate(_M_impl, 1); } |

384 | |

385 | void |

386 | _M_put_node(typename _Node_alloc_traits::pointer __p) _GLIBCXX_NOEXCEPT |

387 | { _Node_alloc_traits::deallocate(_M_impl, __p, 1); } |

388 | |

389 | public: |

390 | typedef _Alloc allocator_type; |

391 | |

392 | _Node_alloc_type& |

393 | _M_get_Node_allocator() _GLIBCXX_NOEXCEPT |

394 | { return _M_impl; } |

395 | |

396 | const _Node_alloc_type& |

397 | _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT |

398 | { return _M_impl; } |

399 | |

400 | _List_base() |

401 | : _M_impl() |

402 | { _M_init(); } |

403 | |

404 | _List_base(const _Node_alloc_type& __a) _GLIBCXX_NOEXCEPT |

405 | : _M_impl(__a) |

406 | { _M_init(); } |

407 | |

408 | #if __cplusplus >= 201103L |

409 | _List_base(_List_base&& __x) noexcept |

410 | : _M_impl(std::move(__x._M_get_Node_allocator())) |

411 | { _M_move_nodes(std::move(__x)); } |

412 | |

413 | _List_base(_List_base&& __x, _Node_alloc_type&& __a) |

414 | : _M_impl(std::move(__a)) |

415 | { |

416 | if (__x._M_get_Node_allocator() == _M_get_Node_allocator()) |

417 | _M_move_nodes(std::move(__x)); |

418 | else |

419 | _M_init(); // Caller must move individual elements. |

420 | } |

421 | |

422 | void |

423 | _M_move_nodes(_List_base&& __x) |

424 | { |

425 | auto* const __xnode = std::__addressof(__x._M_impl._M_node); |

426 | if (__xnode->_M_next == __xnode) |

427 | _M_init(); |

428 | else |

429 | { |

430 | auto* const __node = std::__addressof(_M_impl._M_node); |

431 | __node->_M_next = __xnode->_M_next; |

432 | __node->_M_prev = __xnode->_M_prev; |

433 | __node->_M_next->_M_prev = __node->_M_prev->_M_next = __node; |

434 | _M_set_size(__x._M_get_size()); |

435 | __x._M_init(); |

436 | } |

437 | } |

438 | #endif |

439 | |

440 | // This is what actually destroys the list. |

441 | ~_List_base() _GLIBCXX_NOEXCEPT |

442 | { _M_clear(); } |

443 | |

444 | void |

445 | _M_clear() _GLIBCXX_NOEXCEPT; |

446 | |

447 | void |

448 | _M_init() _GLIBCXX_NOEXCEPT |

449 | { |

450 | this->_M_impl._M_node._M_next = &this->_M_impl._M_node; |

451 | this->_M_impl._M_node._M_prev = &this->_M_impl._M_node; |

452 | _M_set_size(0); |

453 | } |

454 | }; |

455 | |

456 | /** |

457 | * @brief A standard container with linear time access to elements, |

458 | * and fixed time insertion/deletion at any point in the sequence. |

459 | * |

460 | * @ingroup sequences |

461 | * |

462 | * @tparam _Tp Type of element. |

463 | * @tparam _Alloc Allocator type, defaults to allocator<_Tp>. |

464 | * |

465 | * Meets the requirements of a <a href="tables.html#65">container</a>, a |

466 | * <a href="tables.html#66">reversible container</a>, and a |

467 | * <a href="tables.html#67">sequence</a>, including the |

468 | * <a href="tables.html#68">optional sequence requirements</a> with the |

469 | * %exception of @c at and @c operator[]. |

470 | * |

471 | * This is a @e doubly @e linked %list. Traversal up and down the |

472 | * %list requires linear time, but adding and removing elements (or |

473 | * @e nodes) is done in constant time, regardless of where the |

474 | * change takes place. Unlike std::vector and std::deque, |

475 | * random-access iterators are not provided, so subscripting ( @c |

476 | * [] ) access is not allowed. For algorithms which only need |

477 | * sequential access, this lack makes no difference. |

478 | * |

479 | * Also unlike the other standard containers, std::list provides |

480 | * specialized algorithms %unique to linked lists, such as |

481 | * splicing, sorting, and in-place reversal. |

482 | * |

483 | * A couple points on memory allocation for list<Tp>: |

484 | * |

485 | * First, we never actually allocate a Tp, we allocate |

486 | * List_node<Tp>'s and trust [20.1.5]/4 to DTRT. This is to ensure |

487 | * that after elements from %list<X,Alloc1> are spliced into |

488 | * %list<X,Alloc2>, destroying the memory of the second %list is a |

489 | * valid operation, i.e., Alloc1 giveth and Alloc2 taketh away. |

490 | * |

491 | * Second, a %list conceptually represented as |

492 | * @code |

493 | * A <---> B <---> C <---> D |

494 | * @endcode |

495 | * is actually circular; a link exists between A and D. The %list |

496 | * class holds (as its only data member) a private list::iterator |

497 | * pointing to @e D, not to @e A! To get to the head of the %list, |

498 | * we start at the tail and move forward by one. When this member |

499 | * iterator's next/previous pointers refer to itself, the %list is |

500 | * %empty. |

501 | */ |

502 | template<typename _Tp, typename _Alloc = std::allocator<_Tp> > |

503 | class list : protected _List_base<_Tp, _Alloc> |

504 | { |

505 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

506 | // concept requirements |

507 | typedef typename _Alloc::value_type _Alloc_value_type; |

508 | # if __cplusplus < 201103L |

509 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

510 | # endif |

511 | __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) |

512 | #endif |

513 | |

514 | typedef _List_base<_Tp, _Alloc> _Base; |

515 | typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; |

516 | typedef typename _Base::_Tp_alloc_traits _Tp_alloc_traits; |

517 | typedef typename _Base::_Node_alloc_type _Node_alloc_type; |

518 | typedef typename _Base::_Node_alloc_traits _Node_alloc_traits; |

519 | |

520 | public: |

521 | typedef _Tp value_type; |

522 | typedef typename _Tp_alloc_traits::pointer pointer; |

523 | typedef typename _Tp_alloc_traits::const_pointer const_pointer; |

524 | typedef typename _Tp_alloc_traits::reference reference; |

525 | typedef typename _Tp_alloc_traits::const_reference const_reference; |

526 | typedef _List_iterator<_Tp> iterator; |

527 | typedef _List_const_iterator<_Tp> const_iterator; |

528 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |

529 | typedef std::reverse_iterator<iterator> reverse_iterator; |

530 | typedef size_t size_type; |

531 | typedef ptrdiff_t difference_type; |

532 | typedef _Alloc allocator_type; |

533 | |

534 | protected: |

535 | // Note that pointers-to-_Node's can be ctor-converted to |

536 | // iterator types. |

537 | typedef _List_node<_Tp> _Node; |

538 | |

539 | using _Base::_M_impl; |

540 | using _Base::_M_put_node; |

541 | using _Base::_M_get_node; |

542 | using _Base::_M_get_Node_allocator; |

543 | |

544 | /** |

545 | * @param __args An instance of user data. |

546 | * |

547 | * Allocates space for a new node and constructs a copy of |

548 | * @a __args in it. |

549 | */ |

550 | #if __cplusplus < 201103L |

551 | _Node* |

552 | _M_create_node(const value_type& __x) |

553 | { |

554 | _Node* __p = this->_M_get_node(); |

555 | __try |

556 | { |

557 | _Tp_alloc_type __alloc(_M_get_Node_allocator()); |

558 | __alloc.construct(__p->_M_valptr(), __x); |

559 | } |

560 | __catch(...) |

561 | { |

562 | _M_put_node(__p); |

563 | __throw_exception_again; |

564 | } |

565 | return __p; |

566 | } |

567 | #else |

568 | template<typename... _Args> |

569 | _Node* |

570 | _M_create_node(_Args&&... __args) |

571 | { |

572 | auto __p = this->_M_get_node(); |

573 | auto& __alloc = _M_get_Node_allocator(); |

574 | __allocated_ptr<_Node_alloc_type> __guard{__alloc, __p}; |

575 | _Node_alloc_traits::construct(__alloc, __p->_M_valptr(), |

576 | std::forward<_Args>(__args)...); |

577 | __guard = nullptr; |

578 | return __p; |

579 | } |

580 | #endif |

581 | |

582 | public: |

583 | // [23.2.2.1] construct/copy/destroy |

584 | // (assign() and get_allocator() are also listed in this section) |

585 | |

586 | /** |

587 | * @brief Creates a %list with no elements. |

588 | */ |

589 | list() |

590 | #if __cplusplus >= 201103L |

591 | noexcept(is_nothrow_default_constructible<_Node_alloc_type>::value) |

592 | #endif |

593 | : _Base() { } |

594 | |

595 | /** |

596 | * @brief Creates a %list with no elements. |

597 | * @param __a An allocator object. |

598 | */ |

599 | explicit |

600 | list(const allocator_type& __a) _GLIBCXX_NOEXCEPT |

601 | : _Base(_Node_alloc_type(__a)) { } |

602 | |

603 | #if __cplusplus >= 201103L |

604 | /** |

605 | * @brief Creates a %list with default constructed elements. |

606 | * @param __n The number of elements to initially create. |

607 | * @param __a An allocator object. |

608 | * |

609 | * This constructor fills the %list with @a __n default |

610 | * constructed elements. |

611 | */ |

612 | explicit |

613 | list(size_type __n, const allocator_type& __a = allocator_type()) |

614 | : _Base(_Node_alloc_type(__a)) |

615 | { _M_default_initialize(__n); } |

616 | |

617 | /** |

618 | * @brief Creates a %list with copies of an exemplar element. |

619 | * @param __n The number of elements to initially create. |

620 | * @param __value An element to copy. |

621 | * @param __a An allocator object. |

622 | * |

623 | * This constructor fills the %list with @a __n copies of @a __value. |

624 | */ |

625 | list(size_type __n, const value_type& __value, |

626 | const allocator_type& __a = allocator_type()) |

627 | : _Base(_Node_alloc_type(__a)) |

628 | { _M_fill_initialize(__n, __value); } |

629 | #else |

630 | /** |

631 | * @brief Creates a %list with copies of an exemplar element. |

632 | * @param __n The number of elements to initially create. |

633 | * @param __value An element to copy. |

634 | * @param __a An allocator object. |

635 | * |

636 | * This constructor fills the %list with @a __n copies of @a __value. |

637 | */ |

638 | explicit |

639 | list(size_type __n, const value_type& __value = value_type(), |

640 | const allocator_type& __a = allocator_type()) |

641 | : _Base(_Node_alloc_type(__a)) |

642 | { _M_fill_initialize(__n, __value); } |

643 | #endif |

644 | |

645 | /** |

646 | * @brief %List copy constructor. |

647 | * @param __x A %list of identical element and allocator types. |

648 | * |

649 | * The newly-created %list uses a copy of the allocation object used |

650 | * by @a __x (unless the allocator traits dictate a different object). |

651 | */ |

652 | list(const list& __x) |

653 | : _Base(_Node_alloc_traits:: |

654 | _S_select_on_copy(__x._M_get_Node_allocator())) |

655 | { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } |

656 | |

657 | #if __cplusplus >= 201103L |

658 | /** |

659 | * @brief %List move constructor. |

660 | * @param __x A %list of identical element and allocator types. |

661 | * |

662 | * The newly-created %list contains the exact contents of @a __x. |

663 | * The contents of @a __x are a valid, but unspecified %list. |

664 | */ |

665 | list(list&& __x) noexcept |

666 | : _Base(std::move(__x)) { } |

667 | |

668 | /** |

669 | * @brief Builds a %list from an initializer_list |

670 | * @param __l An initializer_list of value_type. |

671 | * @param __a An allocator object. |

672 | * |

673 | * Create a %list consisting of copies of the elements in the |

674 | * initializer_list @a __l. This is linear in __l.size(). |

675 | */ |

676 | list(initializer_list<value_type> __l, |

677 | const allocator_type& __a = allocator_type()) |

678 | : _Base(_Node_alloc_type(__a)) |

679 | { _M_initialize_dispatch(__l.begin(), __l.end(), __false_type()); } |

680 | |

681 | list(const list& __x, const allocator_type& __a) |

682 | : _Base(_Node_alloc_type(__a)) |

683 | { _M_initialize_dispatch(__x.begin(), __x.end(), __false_type()); } |

684 | |

685 | list(list&& __x, const allocator_type& __a) |

686 | noexcept(_Node_alloc_traits::_S_always_equal()) |

687 | : _Base(std::move(__x), _Node_alloc_type(__a)) |

688 | { |

689 | // If __x is not empty it means its allocator is not equal to __a, |

690 | // so we need to move from each element individually. |

691 | insert(begin(), std::__make_move_if_noexcept_iterator(__x.begin()), |

692 | std::__make_move_if_noexcept_iterator(__x.end())); |

693 | } |

694 | #endif |

695 | |

696 | /** |

697 | * @brief Builds a %list from a range. |

698 | * @param __first An input iterator. |

699 | * @param __last An input iterator. |

700 | * @param __a An allocator object. |

701 | * |

702 | * Create a %list consisting of copies of the elements from |

703 | * [@a __first,@a __last). This is linear in N (where N is |

704 | * distance(@a __first,@a __last)). |

705 | */ |

706 | #if __cplusplus >= 201103L |

707 | template<typename _InputIterator, |

708 | typename = std::_RequireInputIter<_InputIterator>> |

709 | list(_InputIterator __first, _InputIterator __last, |

710 | const allocator_type& __a = allocator_type()) |

711 | : _Base(_Node_alloc_type(__a)) |

712 | { _M_initialize_dispatch(__first, __last, __false_type()); } |

713 | #else |

714 | template<typename _InputIterator> |

715 | list(_InputIterator __first, _InputIterator __last, |

716 | const allocator_type& __a = allocator_type()) |

717 | : _Base(_Node_alloc_type(__a)) |

718 | { |

719 | // Check whether it's an integral type. If so, it's not an iterator. |

720 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |

721 | _M_initialize_dispatch(__first, __last, _Integral()); |

722 | } |

723 | #endif |

724 | |

725 | #if __cplusplus >= 201103L |

726 | /** |

727 | * No explicit dtor needed as the _Base dtor takes care of |

728 | * things. The _Base dtor only erases the elements, and note |

729 | * that if the elements themselves are pointers, the pointed-to |

730 | * memory is not touched in any way. Managing the pointer is |

731 | * the user's responsibility. |

732 | */ |

733 | ~list() = default; |

734 | #endif |

735 | |

736 | /** |

737 | * @brief %List assignment operator. |

738 | * @param __x A %list of identical element and allocator types. |

739 | * |

740 | * All the elements of @a __x are copied. |

741 | * |

742 | * Whether the allocator is copied depends on the allocator traits. |

743 | */ |

744 | list& |

745 | operator=(const list& __x); |

746 | |

747 | #if __cplusplus >= 201103L |

748 | /** |

749 | * @brief %List move assignment operator. |

750 | * @param __x A %list of identical element and allocator types. |

751 | * |

752 | * The contents of @a __x are moved into this %list (without copying). |

753 | * |

754 | * Afterwards @a __x is a valid, but unspecified %list |

755 | * |

756 | * Whether the allocator is moved depends on the allocator traits. |

757 | */ |

758 | list& |

759 | operator=(list&& __x) |

760 | noexcept(_Node_alloc_traits::_S_nothrow_move()) |

761 | { |

762 | constexpr bool __move_storage = |

763 | _Node_alloc_traits::_S_propagate_on_move_assign() |

764 | || _Node_alloc_traits::_S_always_equal(); |

765 | _M_move_assign(std::move(__x), __bool_constant<__move_storage>()); |

766 | return *this; |

767 | } |

768 | |

769 | /** |

770 | * @brief %List initializer list assignment operator. |

771 | * @param __l An initializer_list of value_type. |

772 | * |

773 | * Replace the contents of the %list with copies of the elements |

774 | * in the initializer_list @a __l. This is linear in l.size(). |

775 | */ |

776 | list& |

777 | operator=(initializer_list<value_type> __l) |

778 | { |

779 | this->assign(__l.begin(), __l.end()); |

780 | return *this; |

781 | } |

782 | #endif |

783 | |

784 | /** |

785 | * @brief Assigns a given value to a %list. |

786 | * @param __n Number of elements to be assigned. |

787 | * @param __val Value to be assigned. |

788 | * |

789 | * This function fills a %list with @a __n copies of the given |

790 | * value. Note that the assignment completely changes the %list |

791 | * and that the resulting %list's size is the same as the number |

792 | * of elements assigned. |

793 | */ |

794 | void |

795 | assign(size_type __n, const value_type& __val) |

796 | { _M_fill_assign(__n, __val); } |

797 | |

798 | /** |

799 | * @brief Assigns a range to a %list. |

800 | * @param __first An input iterator. |

801 | * @param __last An input iterator. |

802 | * |

803 | * This function fills a %list with copies of the elements in the |

804 | * range [@a __first,@a __last). |

805 | * |

806 | * Note that the assignment completely changes the %list and |

807 | * that the resulting %list's size is the same as the number of |

808 | * elements assigned. |

809 | */ |

810 | #if __cplusplus >= 201103L |

811 | template<typename _InputIterator, |

812 | typename = std::_RequireInputIter<_InputIterator>> |

813 | void |

814 | assign(_InputIterator __first, _InputIterator __last) |

815 | { _M_assign_dispatch(__first, __last, __false_type()); } |

816 | #else |

817 | template<typename _InputIterator> |

818 | void |

819 | assign(_InputIterator __first, _InputIterator __last) |

820 | { |

821 | // Check whether it's an integral type. If so, it's not an iterator. |

822 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |

823 | _M_assign_dispatch(__first, __last, _Integral()); |

824 | } |

825 | #endif |

826 | |

827 | #if __cplusplus >= 201103L |

828 | /** |

829 | * @brief Assigns an initializer_list to a %list. |

830 | * @param __l An initializer_list of value_type. |

831 | * |

832 | * Replace the contents of the %list with copies of the elements |

833 | * in the initializer_list @a __l. This is linear in __l.size(). |

834 | */ |

835 | void |

836 | assign(initializer_list<value_type> __l) |

837 | { this->_M_assign_dispatch(__l.begin(), __l.end(), __false_type()); } |

838 | #endif |

839 | |

840 | /// Get a copy of the memory allocation object. |

841 | allocator_type |

842 | get_allocator() const _GLIBCXX_NOEXCEPT |

843 | { return allocator_type(_Base::_M_get_Node_allocator()); } |

844 | |

845 | // iterators |

846 | /** |

847 | * Returns a read/write iterator that points to the first element in the |

848 | * %list. Iteration is done in ordinary element order. |

849 | */ |

850 | iterator |

851 | begin() _GLIBCXX_NOEXCEPT |

852 | { return iterator(this->_M_impl._M_node._M_next); } |

853 | |

854 | /** |

855 | * Returns a read-only (constant) iterator that points to the |

856 | * first element in the %list. Iteration is done in ordinary |

857 | * element order. |

858 | */ |

859 | const_iterator |

860 | begin() const _GLIBCXX_NOEXCEPT |

861 | { return const_iterator(this->_M_impl._M_node._M_next); } |

862 | |

863 | /** |

864 | * Returns a read/write iterator that points one past the last |

865 | * element in the %list. Iteration is done in ordinary element |

866 | * order. |

867 | */ |

868 | iterator |

869 | end() _GLIBCXX_NOEXCEPT |

870 | { return iterator(&this->_M_impl._M_node); } |

871 | |

872 | /** |

873 | * Returns a read-only (constant) iterator that points one past |

874 | * the last element in the %list. Iteration is done in ordinary |

875 | * element order. |

876 | */ |

877 | const_iterator |

878 | end() const _GLIBCXX_NOEXCEPT |

879 | { return const_iterator(&this->_M_impl._M_node); } |

880 | |

881 | /** |

882 | * Returns a read/write reverse iterator that points to the last |

883 | * element in the %list. Iteration is done in reverse element |

884 | * order. |

885 | */ |

886 | reverse_iterator |

887 | rbegin() _GLIBCXX_NOEXCEPT |

888 | { return reverse_iterator(end()); } |

889 | |

890 | /** |

891 | * Returns a read-only (constant) reverse iterator that points to |

892 | * the last element in the %list. Iteration is done in reverse |

893 | * element order. |

894 | */ |

895 | const_reverse_iterator |

896 | rbegin() const _GLIBCXX_NOEXCEPT |

897 | { return const_reverse_iterator(end()); } |

898 | |

899 | /** |

900 | * Returns a read/write reverse iterator that points to one |

901 | * before the first element in the %list. Iteration is done in |

902 | * reverse element order. |

903 | */ |

904 | reverse_iterator |

905 | rend() _GLIBCXX_NOEXCEPT |

906 | { return reverse_iterator(begin()); } |

907 | |

908 | /** |

909 | * Returns a read-only (constant) reverse iterator that points to one |

910 | * before the first element in the %list. Iteration is done in reverse |

911 | * element order. |

912 | */ |

913 | const_reverse_iterator |

914 | rend() const _GLIBCXX_NOEXCEPT |

915 | { return const_reverse_iterator(begin()); } |

916 | |

917 | #if __cplusplus >= 201103L |

918 | /** |

919 | * Returns a read-only (constant) iterator that points to the |

920 | * first element in the %list. Iteration is done in ordinary |

921 | * element order. |

922 | */ |

923 | const_iterator |

924 | cbegin() const noexcept |

925 | { return const_iterator(this->_M_impl._M_node._M_next); } |

926 | |

927 | /** |

928 | * Returns a read-only (constant) iterator that points one past |

929 | * the last element in the %list. Iteration is done in ordinary |

930 | * element order. |

931 | */ |

932 | const_iterator |

933 | cend() const noexcept |

934 | { return const_iterator(&this->_M_impl._M_node); } |

935 | |

936 | /** |

937 | * Returns a read-only (constant) reverse iterator that points to |

938 | * the last element in the %list. Iteration is done in reverse |

939 | * element order. |

940 | */ |

941 | const_reverse_iterator |

942 | crbegin() const noexcept |

943 | { return const_reverse_iterator(end()); } |

944 | |

945 | /** |

946 | * Returns a read-only (constant) reverse iterator that points to one |

947 | * before the first element in the %list. Iteration is done in reverse |

948 | * element order. |

949 | */ |

950 | const_reverse_iterator |

951 | crend() const noexcept |

952 | { return const_reverse_iterator(begin()); } |

953 | #endif |

954 | |

955 | // [23.2.2.2] capacity |

956 | /** |

957 | * Returns true if the %list is empty. (Thus begin() would equal |

958 | * end().) |

959 | */ |

960 | bool |

961 | empty() const _GLIBCXX_NOEXCEPT |

962 | { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; } |

963 | |

964 | /** Returns the number of elements in the %list. */ |

965 | size_type |

966 | size() const _GLIBCXX_NOEXCEPT |

967 | { return this->_M_node_count(); } |

968 | |

969 | /** Returns the size() of the largest possible %list. */ |

970 | size_type |

971 | max_size() const _GLIBCXX_NOEXCEPT |

972 | { return _Node_alloc_traits::max_size(_M_get_Node_allocator()); } |

973 | |

974 | #if __cplusplus >= 201103L |

975 | /** |

976 | * @brief Resizes the %list to the specified number of elements. |

977 | * @param __new_size Number of elements the %list should contain. |

978 | * |

979 | * This function will %resize the %list to the specified number |

980 | * of elements. If the number is smaller than the %list's |

981 | * current size the %list is truncated, otherwise default |

982 | * constructed elements are appended. |

983 | */ |

984 | void |

985 | resize(size_type __new_size); |

986 | |

987 | /** |

988 | * @brief Resizes the %list to the specified number of elements. |

989 | * @param __new_size Number of elements the %list should contain. |

990 | * @param __x Data with which new elements should be populated. |

991 | * |

992 | * This function will %resize the %list to the specified number |

993 | * of elements. If the number is smaller than the %list's |

994 | * current size the %list is truncated, otherwise the %list is |

995 | * extended and new elements are populated with given data. |

996 | */ |

997 | void |

998 | resize(size_type __new_size, const value_type& __x); |

999 | #else |

1000 | /** |

1001 | * @brief Resizes the %list to the specified number of elements. |

1002 | * @param __new_size Number of elements the %list should contain. |

1003 | * @param __x Data with which new elements should be populated. |

1004 | * |

1005 | * This function will %resize the %list to the specified number |

1006 | * of elements. If the number is smaller than the %list's |

1007 | * current size the %list is truncated, otherwise the %list is |

1008 | * extended and new elements are populated with given data. |

1009 | */ |

1010 | void |

1011 | resize(size_type __new_size, value_type __x = value_type()); |

1012 | #endif |

1013 | |

1014 | // element access |

1015 | /** |

1016 | * Returns a read/write reference to the data at the first |

1017 | * element of the %list. |

1018 | */ |

1019 | reference |

1020 | front() _GLIBCXX_NOEXCEPT |

1021 | { return *begin(); } |

1022 | |

1023 | /** |

1024 | * Returns a read-only (constant) reference to the data at the first |

1025 | * element of the %list. |

1026 | */ |

1027 | const_reference |

1028 | front() const _GLIBCXX_NOEXCEPT |

1029 | { return *begin(); } |

1030 | |

1031 | /** |

1032 | * Returns a read/write reference to the data at the last element |

1033 | * of the %list. |

1034 | */ |

1035 | reference |

1036 | back() _GLIBCXX_NOEXCEPT |

1037 | { |

1038 | iterator __tmp = end(); |

1039 | --__tmp; |

1040 | return *__tmp; |

1041 | } |

1042 | |

1043 | /** |

1044 | * Returns a read-only (constant) reference to the data at the last |

1045 | * element of the %list. |

1046 | */ |

1047 | const_reference |

1048 | back() const _GLIBCXX_NOEXCEPT |

1049 | { |

1050 | const_iterator __tmp = end(); |

1051 | --__tmp; |

1052 | return *__tmp; |

1053 | } |

1054 | |

1055 | // [23.2.2.3] modifiers |

1056 | /** |

1057 | * @brief Add data to the front of the %list. |

1058 | * @param __x Data to be added. |

1059 | * |

1060 | * This is a typical stack operation. The function creates an |

1061 | * element at the front of the %list and assigns the given data |

1062 | * to it. Due to the nature of a %list this operation can be |

1063 | * done in constant time, and does not invalidate iterators and |

1064 | * references. |

1065 | */ |

1066 | void |

1067 | push_front(const value_type& __x) |

1068 | { this->_M_insert(begin(), __x); } |

1069 | |

1070 | #if __cplusplus >= 201103L |

1071 | void |

1072 | push_front(value_type&& __x) |

1073 | { this->_M_insert(begin(), std::move(__x)); } |

1074 | |

1075 | template<typename... _Args> |

1076 | #if __cplusplus > 201402L |

1077 | reference |

1078 | #else |

1079 | void |

1080 | #endif |

1081 | emplace_front(_Args&&... __args) |

1082 | { |

1083 | this->_M_insert(begin(), std::forward<_Args>(__args)...); |

1084 | #if __cplusplus > 201402L |

1085 | return front(); |

1086 | #endif |

1087 | } |

1088 | #endif |

1089 | |

1090 | /** |

1091 | * @brief Removes first element. |

1092 | * |

1093 | * This is a typical stack operation. It shrinks the %list by |

1094 | * one. Due to the nature of a %list this operation can be done |

1095 | * in constant time, and only invalidates iterators/references to |

1096 | * the element being removed. |

1097 | * |

1098 | * Note that no data is returned, and if the first element's data |

1099 | * is needed, it should be retrieved before pop_front() is |

1100 | * called. |

1101 | */ |

1102 | void |

1103 | pop_front() _GLIBCXX_NOEXCEPT |

1104 | { this->_M_erase(begin()); } |

1105 | |

1106 | /** |

1107 | * @brief Add data to the end of the %list. |

1108 | * @param __x Data to be added. |

1109 | * |

1110 | * This is a typical stack operation. The function creates an |

1111 | * element at the end of the %list and assigns the given data to |

1112 | * it. Due to the nature of a %list this operation can be done |

1113 | * in constant time, and does not invalidate iterators and |

1114 | * references. |

1115 | */ |

1116 | void |

1117 | push_back(const value_type& __x) |

1118 | { this->_M_insert(end(), __x); } |

1119 | |

1120 | #if __cplusplus >= 201103L |

1121 | void |

1122 | push_back(value_type&& __x) |

1123 | { this->_M_insert(end(), std::move(__x)); } |

1124 | |

1125 | template<typename... _Args> |

1126 | #if __cplusplus > 201402L |

1127 | reference |

1128 | #else |

1129 | void |

1130 | #endif |

1131 | emplace_back(_Args&&... __args) |

1132 | { |

1133 | this->_M_insert(end(), std::forward<_Args>(__args)...); |

1134 | #if __cplusplus > 201402L |

1135 | return back(); |

1136 | #endif |

1137 | } |

1138 | #endif |

1139 | |

1140 | /** |

1141 | * @brief Removes last element. |

1142 | * |

1143 | * This is a typical stack operation. It shrinks the %list by |

1144 | * one. Due to the nature of a %list this operation can be done |

1145 | * in constant time, and only invalidates iterators/references to |

1146 | * the element being removed. |

1147 | * |

1148 | * Note that no data is returned, and if the last element's data |

1149 | * is needed, it should be retrieved before pop_back() is called. |

1150 | */ |

1151 | void |

1152 | pop_back() _GLIBCXX_NOEXCEPT |

1153 | { this->_M_erase(iterator(this->_M_impl._M_node._M_prev)); } |

1154 | |

1155 | #if __cplusplus >= 201103L |

1156 | /** |

1157 | * @brief Constructs object in %list before specified iterator. |

1158 | * @param __position A const_iterator into the %list. |

1159 | * @param __args Arguments. |

1160 | * @return An iterator that points to the inserted data. |

1161 | * |

1162 | * This function will insert an object of type T constructed |

1163 | * with T(std::forward<Args>(args)...) before the specified |

1164 | * location. Due to the nature of a %list this operation can |

1165 | * be done in constant time, and does not invalidate iterators |

1166 | * and references. |

1167 | */ |

1168 | template<typename... _Args> |

1169 | iterator |

1170 | emplace(const_iterator __position, _Args&&... __args); |

1171 | |

1172 | /** |

1173 | * @brief Inserts given value into %list before specified iterator. |

1174 | * @param __position A const_iterator into the %list. |

1175 | * @param __x Data to be inserted. |

1176 | * @return An iterator that points to the inserted data. |

1177 | * |

1178 | * This function will insert a copy of the given value before |

1179 | * the specified location. Due to the nature of a %list this |

1180 | * operation can be done in constant time, and does not |

1181 | * invalidate iterators and references. |

1182 | */ |

1183 | iterator |

1184 | insert(const_iterator __position, const value_type& __x); |

1185 | #else |

1186 | /** |

1187 | * @brief Inserts given value into %list before specified iterator. |

1188 | * @param __position An iterator into the %list. |

1189 | * @param __x Data to be inserted. |

1190 | * @return An iterator that points to the inserted data. |

1191 | * |

1192 | * This function will insert a copy of the given value before |

1193 | * the specified location. Due to the nature of a %list this |

1194 | * operation can be done in constant time, and does not |

1195 | * invalidate iterators and references. |

1196 | */ |

1197 | iterator |

1198 | insert(iterator __position, const value_type& __x); |

1199 | #endif |

1200 | |

1201 | #if __cplusplus >= 201103L |

1202 | /** |

1203 | * @brief Inserts given rvalue into %list before specified iterator. |

1204 | * @param __position A const_iterator into the %list. |

1205 | * @param __x Data to be inserted. |

1206 | * @return An iterator that points to the inserted data. |

1207 | * |

1208 | * This function will insert a copy of the given rvalue before |

1209 | * the specified location. Due to the nature of a %list this |

1210 | * operation can be done in constant time, and does not |

1211 | * invalidate iterators and references. |

1212 | */ |

1213 | iterator |

1214 | insert(const_iterator __position, value_type&& __x) |

1215 | { return emplace(__position, std::move(__x)); } |

1216 | |

1217 | /** |

1218 | * @brief Inserts the contents of an initializer_list into %list |

1219 | * before specified const_iterator. |

1220 | * @param __p A const_iterator into the %list. |

1221 | * @param __l An initializer_list of value_type. |

1222 | * @return An iterator pointing to the first element inserted |

1223 | * (or __position). |

1224 | * |

1225 | * This function will insert copies of the data in the |

1226 | * initializer_list @a l into the %list before the location |

1227 | * specified by @a p. |

1228 | * |

1229 | * This operation is linear in the number of elements inserted and |

1230 | * does not invalidate iterators and references. |

1231 | */ |

1232 | iterator |

1233 | insert(const_iterator __p, initializer_list<value_type> __l) |

1234 | { return this->insert(__p, __l.begin(), __l.end()); } |

1235 | #endif |

1236 | |

1237 | #if __cplusplus >= 201103L |

1238 | /** |

1239 | * @brief Inserts a number of copies of given data into the %list. |

1240 | * @param __position A const_iterator into the %list. |

1241 | * @param __n Number of elements to be inserted. |

1242 | * @param __x Data to be inserted. |

1243 | * @return An iterator pointing to the first element inserted |

1244 | * (or __position). |

1245 | * |

1246 | * This function will insert a specified number of copies of the |

1247 | * given data before the location specified by @a position. |

1248 | * |

1249 | * This operation is linear in the number of elements inserted and |

1250 | * does not invalidate iterators and references. |

1251 | */ |

1252 | iterator |

1253 | insert(const_iterator __position, size_type __n, const value_type& __x); |

1254 | #else |

1255 | /** |

1256 | * @brief Inserts a number of copies of given data into the %list. |

1257 | * @param __position An iterator into the %list. |

1258 | * @param __n Number of elements to be inserted. |

1259 | * @param __x Data to be inserted. |

1260 | * |

1261 | * This function will insert a specified number of copies of the |

1262 | * given data before the location specified by @a position. |

1263 | * |

1264 | * This operation is linear in the number of elements inserted and |

1265 | * does not invalidate iterators and references. |

1266 | */ |

1267 | void |

1268 | insert(iterator __position, size_type __n, const value_type& __x) |

1269 | { |

1270 | list __tmp(__n, __x, get_allocator()); |

1271 | splice(__position, __tmp); |

1272 | } |

1273 | #endif |

1274 | |

1275 | #if __cplusplus >= 201103L |

1276 | /** |

1277 | * @brief Inserts a range into the %list. |

1278 | * @param __position A const_iterator into the %list. |

1279 | * @param __first An input iterator. |

1280 | * @param __last An input iterator. |

1281 | * @return An iterator pointing to the first element inserted |

1282 | * (or __position). |

1283 | * |

1284 | * This function will insert copies of the data in the range [@a |

1285 | * first,@a last) into the %list before the location specified by |

1286 | * @a position. |

1287 | * |

1288 | * This operation is linear in the number of elements inserted and |

1289 | * does not invalidate iterators and references. |

1290 | */ |

1291 | template<typename _InputIterator, |

1292 | typename = std::_RequireInputIter<_InputIterator>> |

1293 | iterator |

1294 | insert(const_iterator __position, _InputIterator __first, |

1295 | _InputIterator __last); |

1296 | #else |

1297 | /** |

1298 | * @brief Inserts a range into the %list. |

1299 | * @param __position An iterator into the %list. |

1300 | * @param __first An input iterator. |

1301 | * @param __last An input iterator. |

1302 | * |

1303 | * This function will insert copies of the data in the range [@a |

1304 | * first,@a last) into the %list before the location specified by |

1305 | * @a position. |

1306 | * |

1307 | * This operation is linear in the number of elements inserted and |

1308 | * does not invalidate iterators and references. |

1309 | */ |

1310 | template<typename _InputIterator> |

1311 | void |

1312 | insert(iterator __position, _InputIterator __first, |

1313 | _InputIterator __last) |

1314 | { |

1315 | list __tmp(__first, __last, get_allocator()); |

1316 | splice(__position, __tmp); |

1317 | } |

1318 | #endif |

1319 | |

1320 | /** |

1321 | * @brief Remove element at given position. |

1322 | * @param __position Iterator pointing to element to be erased. |

1323 | * @return An iterator pointing to the next element (or end()). |

1324 | * |

1325 | * This function will erase the element at the given position and thus |

1326 | * shorten the %list by one. |

1327 | * |

1328 | * Due to the nature of a %list this operation can be done in |

1329 | * constant time, and only invalidates iterators/references to |

1330 | * the element being removed. The user is also cautioned that |

1331 | * this function only erases the element, and that if the element |

1332 | * is itself a pointer, the pointed-to memory is not touched in |

1333 | * any way. Managing the pointer is the user's responsibility. |

1334 | */ |

1335 | iterator |

1336 | #if __cplusplus >= 201103L |

1337 | erase(const_iterator __position) noexcept; |

1338 | #else |

1339 | erase(iterator __position); |

1340 | #endif |

1341 | |

1342 | /** |

1343 | * @brief Remove a range of elements. |

1344 | * @param __first Iterator pointing to the first element to be erased. |

1345 | * @param __last Iterator pointing to one past the last element to be |

1346 | * erased. |

1347 | * @return An iterator pointing to the element pointed to by @a last |

1348 | * prior to erasing (or end()). |

1349 | * |

1350 | * This function will erase the elements in the range @a |

1351 | * [first,last) and shorten the %list accordingly. |

1352 | * |

1353 | * This operation is linear time in the size of the range and only |

1354 | * invalidates iterators/references to the element being removed. |

1355 | * The user is also cautioned that this function only erases the |

1356 | * elements, and that if the elements themselves are pointers, the |

1357 | * pointed-to memory is not touched in any way. Managing the pointer |

1358 | * is the user's responsibility. |

1359 | */ |

1360 | iterator |

1361 | #if __cplusplus >= 201103L |

1362 | erase(const_iterator __first, const_iterator __last) noexcept |

1363 | #else |

1364 | erase(iterator __first, iterator __last) |

1365 | #endif |

1366 | { |

1367 | while (__first != __last) |

1368 | __first = erase(__first); |

1369 | return __last._M_const_cast(); |

1370 | } |

1371 | |

1372 | /** |

1373 | * @brief Swaps data with another %list. |

1374 | * @param __x A %list of the same element and allocator types. |

1375 | * |

1376 | * This exchanges the elements between two lists in constant |

1377 | * time. Note that the global std::swap() function is |

1378 | * specialized such that std::swap(l1,l2) will feed to this |

1379 | * function. |

1380 | * |

1381 | * Whether the allocators are swapped depends on the allocator traits. |

1382 | */ |

1383 | void |

1384 | swap(list& __x) _GLIBCXX_NOEXCEPT |

1385 | { |

1386 | __detail::_List_node_base::swap(this->_M_impl._M_node, |

1387 | __x._M_impl._M_node); |

1388 | |

1389 | size_t __xsize = __x._M_get_size(); |

1390 | __x._M_set_size(this->_M_get_size()); |

1391 | this->_M_set_size(__xsize); |

1392 | |

1393 | _Node_alloc_traits::_S_on_swap(this->_M_get_Node_allocator(), |

1394 | __x._M_get_Node_allocator()); |

1395 | } |

1396 | |

1397 | /** |

1398 | * Erases all the elements. Note that this function only erases |

1399 | * the elements, and that if the elements themselves are |

1400 | * pointers, the pointed-to memory is not touched in any way. |

1401 | * Managing the pointer is the user's responsibility. |

1402 | */ |

1403 | void |

1404 | clear() _GLIBCXX_NOEXCEPT |

1405 | { |

1406 | _Base::_M_clear(); |

1407 | _Base::_M_init(); |

1408 | } |

1409 | |

1410 | // [23.2.2.4] list operations |

1411 | /** |

1412 | * @brief Insert contents of another %list. |

1413 | * @param __position Iterator referencing the element to insert before. |

1414 | * @param __x Source list. |

1415 | * |

1416 | * The elements of @a __x are inserted in constant time in front of |

1417 | * the element referenced by @a __position. @a __x becomes an empty |

1418 | * list. |

1419 | * |

1420 | * Requires this != @a __x. |

1421 | */ |

1422 | void |

1423 | #if __cplusplus >= 201103L |

1424 | splice(const_iterator __position, list&& __x) noexcept |

1425 | #else |

1426 | splice(iterator __position, list& __x) |

1427 | #endif |

1428 | { |

1429 | if (!__x.empty()) |

1430 | { |

1431 | _M_check_equal_allocators(__x); |

1432 | |

1433 | this->_M_transfer(__position._M_const_cast(), |

1434 | __x.begin(), __x.end()); |

1435 | |

1436 | this->_M_inc_size(__x._M_get_size()); |

1437 | __x._M_set_size(0); |

1438 | } |

1439 | } |

1440 | |

1441 | #if __cplusplus >= 201103L |

1442 | void |

1443 | splice(const_iterator __position, list& __x) noexcept |

1444 | { splice(__position, std::move(__x)); } |

1445 | #endif |

1446 | |

1447 | #if __cplusplus >= 201103L |

1448 | /** |

1449 | * @brief Insert element from another %list. |

1450 | * @param __position Const_iterator referencing the element to |

1451 | * insert before. |

1452 | * @param __x Source list. |

1453 | * @param __i Const_iterator referencing the element to move. |

1454 | * |

1455 | * Removes the element in list @a __x referenced by @a __i and |

1456 | * inserts it into the current list before @a __position. |

1457 | */ |

1458 | void |

1459 | splice(const_iterator __position, list&& __x, const_iterator __i) noexcept |

1460 | #else |

1461 | /** |

1462 | * @brief Insert element from another %list. |

1463 | * @param __position Iterator referencing the element to insert before. |

1464 | * @param __x Source list. |

1465 | * @param __i Iterator referencing the element to move. |

1466 | * |

1467 | * Removes the element in list @a __x referenced by @a __i and |

1468 | * inserts it into the current list before @a __position. |

1469 | */ |

1470 | void |

1471 | splice(iterator __position, list& __x, iterator __i) |

1472 | #endif |

1473 | { |

1474 | iterator __j = __i._M_const_cast(); |

1475 | ++__j; |

1476 | if (__position == __i || __position == __j) |

1477 | return; |

1478 | |

1479 | if (this != std::__addressof(__x)) |

1480 | _M_check_equal_allocators(__x); |

1481 | |

1482 | this->_M_transfer(__position._M_const_cast(), |

1483 | __i._M_const_cast(), __j); |

1484 | |

1485 | this->_M_inc_size(1); |

1486 | __x._M_dec_size(1); |

1487 | } |

1488 | |

1489 | #if __cplusplus >= 201103L |

1490 | /** |

1491 | * @brief Insert element from another %list. |

1492 | * @param __position Const_iterator referencing the element to |

1493 | * insert before. |

1494 | * @param __x Source list. |

1495 | * @param __i Const_iterator referencing the element to move. |

1496 | * |

1497 | * Removes the element in list @a __x referenced by @a __i and |

1498 | * inserts it into the current list before @a __position. |

1499 | */ |

1500 | void |

1501 | splice(const_iterator __position, list& __x, const_iterator __i) noexcept |

1502 | { splice(__position, std::move(__x), __i); } |

1503 | #endif |

1504 | |

1505 | #if __cplusplus >= 201103L |

1506 | /** |

1507 | * @brief Insert range from another %list. |

1508 | * @param __position Const_iterator referencing the element to |

1509 | * insert before. |

1510 | * @param __x Source list. |

1511 | * @param __first Const_iterator referencing the start of range in x. |

1512 | * @param __last Const_iterator referencing the end of range in x. |

1513 | * |

1514 | * Removes elements in the range [__first,__last) and inserts them |

1515 | * before @a __position in constant time. |

1516 | * |

1517 | * Undefined if @a __position is in [__first,__last). |

1518 | */ |

1519 | void |

1520 | splice(const_iterator __position, list&& __x, const_iterator __first, |

1521 | const_iterator __last) noexcept |

1522 | #else |

1523 | /** |

1524 | * @brief Insert range from another %list. |

1525 | * @param __position Iterator referencing the element to insert before. |

1526 | * @param __x Source list. |

1527 | * @param __first Iterator referencing the start of range in x. |

1528 | * @param __last Iterator referencing the end of range in x. |

1529 | * |

1530 | * Removes elements in the range [__first,__last) and inserts them |

1531 | * before @a __position in constant time. |

1532 | * |

1533 | * Undefined if @a __position is in [__first,__last). |

1534 | */ |

1535 | void |

1536 | splice(iterator __position, list& __x, iterator __first, |

1537 | iterator __last) |

1538 | #endif |

1539 | { |

1540 | if (__first != __last) |

1541 | { |

1542 | if (this != std::__addressof(__x)) |

1543 | _M_check_equal_allocators(__x); |

1544 | |

1545 | size_t __n = this->_M_distance(__first._M_node, __last._M_node); |

1546 | this->_M_inc_size(__n); |

1547 | __x._M_dec_size(__n); |

1548 | |

1549 | this->_M_transfer(__position._M_const_cast(), |

1550 | __first._M_const_cast(), |

1551 | __last._M_const_cast()); |

1552 | } |

1553 | } |

1554 | |

1555 | #if __cplusplus >= 201103L |

1556 | /** |

1557 | * @brief Insert range from another %list. |

1558 | * @param __position Const_iterator referencing the element to |

1559 | * insert before. |

1560 | * @param __x Source list. |

1561 | * @param __first Const_iterator referencing the start of range in x. |

1562 | * @param __last Const_iterator referencing the end of range in x. |

1563 | * |

1564 | * Removes elements in the range [__first,__last) and inserts them |

1565 | * before @a __position in constant time. |

1566 | * |

1567 | * Undefined if @a __position is in [__first,__last). |

1568 | */ |

1569 | void |

1570 | splice(const_iterator __position, list& __x, const_iterator __first, |

1571 | const_iterator __last) noexcept |

1572 | { splice(__position, std::move(__x), __first, __last); } |

1573 | #endif |

1574 | |

1575 | /** |

1576 | * @brief Remove all elements equal to value. |

1577 | * @param __value The value to remove. |

1578 | * |

1579 | * Removes every element in the list equal to @a value. |

1580 | * Remaining elements stay in list order. Note that this |

1581 | * function only erases the elements, and that if the elements |

1582 | * themselves are pointers, the pointed-to memory is not |

1583 | * touched in any way. Managing the pointer is the user's |

1584 | * responsibility. |

1585 | */ |

1586 | void |

1587 | remove(const _Tp& __value); |

1588 | |

1589 | /** |

1590 | * @brief Remove all elements satisfying a predicate. |

1591 | * @tparam _Predicate Unary predicate function or object. |

1592 | * |

1593 | * Removes every element in the list for which the predicate |

1594 | * returns true. Remaining elements stay in list order. Note |

1595 | * that this function only erases the elements, and that if the |

1596 | * elements themselves are pointers, the pointed-to memory is |

1597 | * not touched in any way. Managing the pointer is the user's |

1598 | * responsibility. |

1599 | */ |

1600 | template<typename _Predicate> |

1601 | void |

1602 | remove_if(_Predicate); |

1603 | |

1604 | /** |

1605 | * @brief Remove consecutive duplicate elements. |

1606 | * |

1607 | * For each consecutive set of elements with the same value, |

1608 | * remove all but the first one. Remaining elements stay in |

1609 | * list order. Note that this function only erases the |

1610 | * elements, and that if the elements themselves are pointers, |

1611 | * the pointed-to memory is not touched in any way. Managing |

1612 | * the pointer is the user's responsibility. |

1613 | */ |

1614 | void |

1615 | unique(); |

1616 | |

1617 | /** |

1618 | * @brief Remove consecutive elements satisfying a predicate. |

1619 | * @tparam _BinaryPredicate Binary predicate function or object. |

1620 | * |

1621 | * For each consecutive set of elements [first,last) that |

1622 | * satisfy predicate(first,i) where i is an iterator in |

1623 | * [first,last), remove all but the first one. Remaining |

1624 | * elements stay in list order. Note that this function only |

1625 | * erases the elements, and that if the elements themselves are |

1626 | * pointers, the pointed-to memory is not touched in any way. |

1627 | * Managing the pointer is the user's responsibility. |

1628 | */ |

1629 | template<typename _BinaryPredicate> |

1630 | void |

1631 | unique(_BinaryPredicate); |

1632 | |

1633 | /** |

1634 | * @brief Merge sorted lists. |

1635 | * @param __x Sorted list to merge. |

1636 | * |

1637 | * Assumes that both @a __x and this list are sorted according to |

1638 | * operator<(). Merges elements of @a __x into this list in |

1639 | * sorted order, leaving @a __x empty when complete. Elements in |

1640 | * this list precede elements in @a __x that are equal. |

1641 | */ |

1642 | #if __cplusplus >= 201103L |

1643 | void |

1644 | merge(list&& __x); |

1645 | |

1646 | void |

1647 | merge(list& __x) |

1648 | { merge(std::move(__x)); } |

1649 | #else |

1650 | void |

1651 | merge(list& __x); |

1652 | #endif |

1653 | |

1654 | /** |

1655 | * @brief Merge sorted lists according to comparison function. |

1656 | * @tparam _StrictWeakOrdering Comparison function defining |

1657 | * sort order. |

1658 | * @param __x Sorted list to merge. |

1659 | * @param __comp Comparison functor. |

1660 | * |

1661 | * Assumes that both @a __x and this list are sorted according to |

1662 | * StrictWeakOrdering. Merges elements of @a __x into this list |

1663 | * in sorted order, leaving @a __x empty when complete. Elements |

1664 | * in this list precede elements in @a __x that are equivalent |

1665 | * according to StrictWeakOrdering(). |

1666 | */ |

1667 | #if __cplusplus >= 201103L |

1668 | template<typename _StrictWeakOrdering> |

1669 | void |

1670 | merge(list&& __x, _StrictWeakOrdering __comp); |

1671 | |

1672 | template<typename _StrictWeakOrdering> |

1673 | void |

1674 | merge(list& __x, _StrictWeakOrdering __comp) |

1675 | { merge(std::move(__x), __comp); } |

1676 | #else |

1677 | template<typename _StrictWeakOrdering> |

1678 | void |

1679 | merge(list& __x, _StrictWeakOrdering __comp); |

1680 | #endif |

1681 | |

1682 | /** |

1683 | * @brief Reverse the elements in list. |

1684 | * |

1685 | * Reverse the order of elements in the list in linear time. |

1686 | */ |

1687 | void |

1688 | reverse() _GLIBCXX_NOEXCEPT |

1689 | { this->_M_impl._M_node._M_reverse(); } |

1690 | |

1691 | /** |

1692 | * @brief Sort the elements. |

1693 | * |

1694 | * Sorts the elements of this list in NlogN time. Equivalent |

1695 | * elements remain in list order. |

1696 | */ |

1697 | void |

1698 | sort(); |

1699 | |

1700 | /** |

1701 | * @brief Sort the elements according to comparison function. |

1702 | * |

1703 | * Sorts the elements of this list in NlogN time. Equivalent |

1704 | * elements remain in list order. |

1705 | */ |

1706 | template<typename _StrictWeakOrdering> |

1707 | void |

1708 | sort(_StrictWeakOrdering); |

1709 | |

1710 | protected: |

1711 | // Internal constructor functions follow. |

1712 | |

1713 | // Called by the range constructor to implement [23.1.1]/9 |

1714 | |

1715 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

1716 | // 438. Ambiguity in the "do the right thing" clause |

1717 | template<typename _Integer> |

1718 | void |

1719 | _M_initialize_dispatch(_Integer __n, _Integer __x, __true_type) |

1720 | { _M_fill_initialize(static_cast<size_type>(__n), __x); } |

1721 | |

1722 | // Called by the range constructor to implement [23.1.1]/9 |

1723 | template<typename _InputIterator> |

1724 | void |

1725 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |

1726 | __false_type) |

1727 | { |

1728 | for (; __first != __last; ++__first) |

1729 | #if __cplusplus >= 201103L |

1730 | emplace_back(*__first); |

1731 | #else |

1732 | push_back(*__first); |

1733 | #endif |

1734 | } |

1735 | |

1736 | // Called by list(n,v,a), and the range constructor when it turns out |

1737 | // to be the same thing. |

1738 | void |

1739 | _M_fill_initialize(size_type __n, const value_type& __x) |

1740 | { |

1741 | for (; __n; --__n) |

1742 | push_back(__x); |

1743 | } |

1744 | |

1745 | #if __cplusplus >= 201103L |

1746 | // Called by list(n). |

1747 | void |

1748 | _M_default_initialize(size_type __n) |

1749 | { |

1750 | for (; __n; --__n) |

1751 | emplace_back(); |

1752 | } |

1753 | |

1754 | // Called by resize(sz). |

1755 | void |

1756 | _M_default_append(size_type __n); |

1757 | #endif |

1758 | |

1759 | // Internal assign functions follow. |

1760 | |

1761 | // Called by the range assign to implement [23.1.1]/9 |

1762 | |

1763 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

1764 | // 438. Ambiguity in the "do the right thing" clause |

1765 | template<typename _Integer> |

1766 | void |

1767 | _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) |

1768 | { _M_fill_assign(__n, __val); } |

1769 | |

1770 | // Called by the range assign to implement [23.1.1]/9 |

1771 | template<typename _InputIterator> |

1772 | void |

1773 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |

1774 | __false_type); |

1775 | |

1776 | // Called by assign(n,t), and the range assign when it turns out |

1777 | // to be the same thing. |

1778 | void |

1779 | _M_fill_assign(size_type __n, const value_type& __val); |

1780 | |

1781 | |

1782 | // Moves the elements from [first,last) before position. |

1783 | void |

1784 | _M_transfer(iterator __position, iterator __first, iterator __last) |

1785 | { __position._M_node->_M_transfer(__first._M_node, __last._M_node); } |

1786 | |

1787 | // Inserts new element at position given and with value given. |

1788 | #if __cplusplus < 201103L |

1789 | void |

1790 | _M_insert(iterator __position, const value_type& __x) |

1791 | { |

1792 | _Node* __tmp = _M_create_node(__x); |

1793 | __tmp->_M_hook(__position._M_node); |

1794 | this->_M_inc_size(1); |

1795 | } |

1796 | #else |

1797 | template<typename... _Args> |

1798 | void |

1799 | _M_insert(iterator __position, _Args&&... __args) |

1800 | { |

1801 | _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); |

1802 | __tmp->_M_hook(__position._M_node); |

1803 | this->_M_inc_size(1); |

1804 | } |

1805 | #endif |

1806 | |

1807 | // Erases element at position given. |

1808 | void |

1809 | _M_erase(iterator __position) _GLIBCXX_NOEXCEPT |

1810 | { |

1811 | this->_M_dec_size(1); |

1812 | __position._M_node->_M_unhook(); |

1813 | _Node* __n = static_cast<_Node*>(__position._M_node); |

1814 | #if __cplusplus >= 201103L |

1815 | _Node_alloc_traits::destroy(_M_get_Node_allocator(), __n->_M_valptr()); |

1816 | #else |

1817 | _Tp_alloc_type(_M_get_Node_allocator()).destroy(__n->_M_valptr()); |

1818 | #endif |

1819 | |

1820 | _M_put_node(__n); |

1821 | } |

1822 | |

1823 | // To implement the splice (and merge) bits of N1599. |

1824 | void |

1825 | _M_check_equal_allocators(list& __x) _GLIBCXX_NOEXCEPT |

1826 | { |

1827 | if (std::__alloc_neq<typename _Base::_Node_alloc_type>:: |

1828 | _S_do_it(_M_get_Node_allocator(), __x._M_get_Node_allocator())) |

1829 | __builtin_abort(); |

1830 | } |

1831 | |

1832 | // Used to implement resize. |

1833 | const_iterator |

1834 | _M_resize_pos(size_type& __new_size) const; |

1835 | |

1836 | #if __cplusplus >= 201103L |

1837 | void |

1838 | _M_move_assign(list&& __x, true_type) noexcept |

1839 | { |

1840 | this->_M_clear(); |

1841 | if (__x.empty()) |

1842 | this->_M_init(); |

1843 | else |

1844 | { |

1845 | this->_M_impl._M_node._M_next = __x._M_impl._M_node._M_next; |

1846 | this->_M_impl._M_node._M_next->_M_prev = &this->_M_impl._M_node; |

1847 | this->_M_impl._M_node._M_prev = __x._M_impl._M_node._M_prev; |

1848 | this->_M_impl._M_node._M_prev->_M_next = &this->_M_impl._M_node; |

1849 | this->_M_set_size(__x._M_get_size()); |

1850 | __x._M_init(); |

1851 | } |

1852 | std::__alloc_on_move(this->_M_get_Node_allocator(), |

1853 | __x._M_get_Node_allocator()); |

1854 | } |

1855 | |

1856 | void |

1857 | _M_move_assign(list&& __x, false_type) |

1858 | { |

1859 | if (__x._M_get_Node_allocator() == this->_M_get_Node_allocator()) |

1860 | _M_move_assign(std::move(__x), true_type{}); |

1861 | else |

1862 | // The rvalue's allocator cannot be moved, or is not equal, |

1863 | // so we need to individually move each element. |

1864 | _M_assign_dispatch(std::__make_move_if_noexcept_iterator(__x.begin()), |

1865 | std::__make_move_if_noexcept_iterator(__x.end()), |

1866 | __false_type{}); |

1867 | } |

1868 | #endif |

1869 | }; |

1870 | _GLIBCXX_END_NAMESPACE_CXX11 |

1871 | |

1872 | /** |

1873 | * @brief List equality comparison. |

1874 | * @param __x A %list. |

1875 | * @param __y A %list of the same type as @a __x. |

1876 | * @return True iff the size and elements of the lists are equal. |

1877 | * |

1878 | * This is an equivalence relation. It is linear in the size of |

1879 | * the lists. Lists are considered equivalent if their sizes are |

1880 | * equal, and if corresponding elements compare equal. |

1881 | */ |

1882 | template<typename _Tp, typename _Alloc> |

1883 | inline bool |

1884 | operator==(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1885 | { |

1886 | #if _GLIBCXX_USE_CXX11_ABI |

1887 | if (__x.size() != __y.size()) |

1888 | return false; |

1889 | #endif |

1890 | |

1891 | typedef typename list<_Tp, _Alloc>::const_iterator const_iterator; |

1892 | const_iterator __end1 = __x.end(); |

1893 | const_iterator __end2 = __y.end(); |

1894 | |

1895 | const_iterator __i1 = __x.begin(); |

1896 | const_iterator __i2 = __y.begin(); |

1897 | while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) |

1898 | { |

1899 | ++__i1; |

1900 | ++__i2; |

1901 | } |

1902 | return __i1 == __end1 && __i2 == __end2; |

1903 | } |

1904 | |

1905 | /** |

1906 | * @brief List ordering relation. |

1907 | * @param __x A %list. |

1908 | * @param __y A %list of the same type as @a __x. |

1909 | * @return True iff @a __x is lexicographically less than @a __y. |

1910 | * |

1911 | * This is a total ordering relation. It is linear in the size of the |

1912 | * lists. The elements must be comparable with @c <. |

1913 | * |

1914 | * See std::lexicographical_compare() for how the determination is made. |

1915 | */ |

1916 | template<typename _Tp, typename _Alloc> |

1917 | inline bool |

1918 | operator<(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1919 | { return std::lexicographical_compare(__x.begin(), __x.end(), |

1920 | __y.begin(), __y.end()); } |

1921 | |

1922 | /// Based on operator== |

1923 | template<typename _Tp, typename _Alloc> |

1924 | inline bool |

1925 | operator!=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1926 | { return !(__x == __y); } |

1927 | |

1928 | /// Based on operator< |

1929 | template<typename _Tp, typename _Alloc> |

1930 | inline bool |

1931 | operator>(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1932 | { return __y < __x; } |

1933 | |

1934 | /// Based on operator< |

1935 | template<typename _Tp, typename _Alloc> |

1936 | inline bool |

1937 | operator<=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1938 | { return !(__y < __x); } |

1939 | |

1940 | /// Based on operator< |

1941 | template<typename _Tp, typename _Alloc> |

1942 | inline bool |

1943 | operator>=(const list<_Tp, _Alloc>& __x, const list<_Tp, _Alloc>& __y) |

1944 | { return !(__x < __y); } |

1945 | |

1946 | /// See std::list::swap(). |

1947 | template<typename _Tp, typename _Alloc> |

1948 | inline void |

1949 | swap(list<_Tp, _Alloc>& __x, list<_Tp, _Alloc>& __y) |

1950 | _GLIBCXX_NOEXCEPT_IF(noexcept(__x.swap(__y))) |

1951 | { __x.swap(__y); } |

1952 | |

1953 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1954 | |

1955 | #if _GLIBCXX_USE_CXX11_ABI |

1956 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

1957 | |

1958 | // Detect when distance is used to compute the size of the whole list. |

1959 | template<typename _Tp> |

1960 | inline ptrdiff_t |

1961 | __distance(_GLIBCXX_STD_C::_List_iterator<_Tp> __first, |

1962 | _GLIBCXX_STD_C::_List_iterator<_Tp> __last, |

1963 | input_iterator_tag __tag) |

1964 | { |

1965 | typedef _GLIBCXX_STD_C::_List_const_iterator<_Tp> _CIter; |

1966 | return std::__distance(_CIter(__first), _CIter(__last), __tag); |

1967 | } |

1968 | |

1969 | template<typename _Tp> |

1970 | inline ptrdiff_t |

1971 | __distance(_GLIBCXX_STD_C::_List_const_iterator<_Tp> __first, |

1972 | _GLIBCXX_STD_C::_List_const_iterator<_Tp> __last, |

1973 | input_iterator_tag) |

1974 | { |

1975 | typedef _GLIBCXX_STD_C::_List_node<size_t> _Sentinel; |

1976 | _GLIBCXX_STD_C::_List_const_iterator<_Tp> __beyond = __last; |

1977 | ++__beyond; |

1978 | bool __whole = __first == __beyond; |

1979 | if (__builtin_constant_p (__whole) && __whole) |

1980 | return *static_cast<const _Sentinel*>(__last._M_node)->_M_valptr(); |

1981 | |

1982 | ptrdiff_t __n = 0; |

1983 | while (__first != __last) |

1984 | { |

1985 | ++__first; |

1986 | ++__n; |

1987 | } |

1988 | return __n; |

1989 | } |

1990 | |

1991 | _GLIBCXX_END_NAMESPACE_VERSION |

1992 | #endif |

1993 | } // namespace std |

1994 | |

1995 | #endif /* _STL_LIST_H */ |

1996 |