libstdc++: list.tcc Source File (original) (raw)

56#ifndef _LIST_TCC

57#define _LIST_TCC 1

59namespace std _GLIBCXX_VISIBILITY(default)

60{

61_GLIBCXX_BEGIN_NAMESPACE_VERSION

62_GLIBCXX_BEGIN_NAMESPACE_CONTAINER

64 template<typename _Tp, typename _Alloc>

65 void

66 _List_base<_Tp, _Alloc>::

67 _M_clear() _GLIBCXX_NOEXCEPT

68 {

69 typedef _List_node<_Tp> _Node;

70 __detail::_List_node_base* __cur = _M_impl._M_node._M_next;

71 while (__cur != &_M_impl._M_node)

72 {

73 _Node* __tmp = static_cast<_Node*>(__cur);

74 __cur = __tmp->_M_next;

75 _Tp* __val = __tmp->_M_valptr();

76#if __cplusplus >= 201103L

77 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);

78#else

79 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);

80#endif

81 _M_put_node(__tmp);

82 }

83 }

85#if __cplusplus >= 201103L

86 template<typename _Tp, typename _Alloc>

87 template<typename... _Args>

88 typename list<_Tp, _Alloc>::iterator

91 {

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

93 __tmp->_M_hook(__position._M_const_cast()._M_node);

94 this->_M_inc_size(1);

96 }

97#endif

99 template<typename _Tp, typename _Alloc>

102#if __cplusplus >= 201103L

103 insert(const_iterator __position, const value_type& __x)

104#else

105 insert(iterator __position, const value_type& __x)

106#endif

107 {

108 _Node* __tmp = _M_create_node(__x);

109 __tmp->_M_hook(__position._M_const_cast()._M_node);

110 this->_M_inc_size(1);

112 }

113

114#if __cplusplus >= 201103L

115 template<typename _Tp, typename _Alloc>

119 {

120 if (__n)

121 {

122 list __tmp(__n, __x, get_allocator());

124 splice(__position, __tmp);

125 return __it;

126 }

127 return __position._M_const_cast();

128 }

129

130 template<typename _Tp, typename _Alloc>

131 template<typename _InputIterator, typename>

135 _InputIterator __last)

136 {

137 list __tmp(__first, __last, get_allocator());

138 if (!__tmp.empty())

139 {

141 splice(__position, __tmp);

142 return __it;

143 }

144 return __position._M_const_cast();

145 }

146#endif

147

148 template<typename _Tp, typename _Alloc>

151#if __cplusplus >= 201103L

153#else

155#endif

156 {

158 _M_erase(__position._M_const_cast());

159 return __ret;

160 }

161

162

163

164

165

166

167

168

169

170

171

172

173 template<typename _Tp, typename _Alloc>

177 {

178 const_iterator __i;

179#if _GLIBCXX_USE_CXX11_ABI

180 const size_type __len = size();

181 if (__new_size < __len)

182 {

183 if (__new_size <= __len / 2)

184 {

187 }

188 else

189 {

190 __i = end();

191 ptrdiff_t __num_erase = __len - __new_size;

193 }

194 __new_size = 0;

195 return __i;

196 }

197 else

198 __i = end();

199#else

200 size_type __len = 0;

201 for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)

202 ;

203#endif

204 __new_size -= __len;

205 return __i;

206 }

207

208#if __cplusplus >= 201103L

209 template<typename _Tp, typename _Alloc>

210 void

211 list<_Tp, _Alloc>::

212 _M_default_append(size_type __n)

213 {

214 size_type __i = 0;

215 __try

216 {

217 for (; __i < __n; ++__i)

218 emplace_back();

219 }

220 __catch(...)

221 {

222 for (; __i; --__i)

223 pop_back();

224 __throw_exception_again;

225 }

226 }

227

228 template<typename _Tp, typename _Alloc>

229 void

231 resize(size_type __new_size)

232 {

234 if (__new_size)

235 _M_default_append(__new_size);

236 else

237 erase(__i, end());

238 }

239

240 template<typename _Tp, typename _Alloc>

241 void

243 resize(size_type __new_size, const value_type& __x)

244 {

246 if (__new_size)

247 insert(end(), __new_size, __x);

248 else

249 erase(__i, end());

250 }

251#else

252 template<typename _Tp, typename _Alloc>

253 void

255 resize(size_type __new_size, value_type __x)

256 {

257 const_iterator __i = _M_resize_pos(__new_size);

258 if (__new_size)

259 insert(end(), __new_size, __x);

260 else

261 erase(__i._M_const_cast(), end());

262 }

263#endif

264

265 template<typename _Tp, typename _Alloc>

266 list<_Tp, _Alloc>&

269 {

271 {

272#if __cplusplus >= 201103L

273 if (_Node_alloc_traits::_S_propagate_on_copy_assign())

274 {

275 auto& __this_alloc = this->_M_get_Node_allocator();

276 auto& __that_alloc = __x._M_get_Node_allocator();

277 if (!_Node_alloc_traits::_S_always_equal()

278 && __this_alloc != __that_alloc)

279 {

280

281 clear();

282 }

283 std::__alloc_on_copy(__this_alloc, __that_alloc);

284 }

285#endif

286 _M_assign_dispatch(__x.begin(), __x.end(), __false_type());

287 }

288 return *this;

289 }

290

291 template<typename _Tp, typename _Alloc>

292 void

294 _M_fill_assign(size_type __n, const value_type& __val)

295 {

297 for (; __i != end() && __n > 0; ++__i, --__n)

298 *__i = __val;

299 if (__n > 0)

300 insert(end(), __n, __val);

301 else

302 erase(__i, end());

303 }

304

305 template<typename _Tp, typename _Alloc>

306 template <typename _InputIterator>

307 void

308 list<_Tp, _Alloc>::

309 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,

310 __false_type)

311 {

312 iterator __first1 = begin();

313 iterator __last1 = end();

314 for (; __first1 != __last1 && __first2 != __last2;

315 ++__first1, (void)++__first2)

316 *__first1 = *__first2;

317 if (__first2 == __last2)

318 erase(__first1, __last1);

319 else

320 insert(__last1, __first2, __last2);

321 }

322

323#if __cplusplus > 201703L

324# define _GLIBCXX20_ONLY(__expr) __expr

325#else

326# define _GLIBCXX20_ONLY(__expr)

327#endif

328

329 template<typename _Tp, typename _Alloc>

330 typename list<_Tp, _Alloc>::__remove_return_type

332 remove(const value_type& __value)

333 {

334#if !_GLIBCXX_USE_CXX11_ABI

335 size_type __removed __attribute__((__unused__)) = 0;

336#endif

337 list __to_destroy(get_allocator());

340 while (__first != __last)

341 {

343 ++__next;

344 if (*__first == __value)

345 {

346

347

348

349 __to_destroy.splice(__to_destroy.begin(), *this, __first);

350#if !_GLIBCXX_USE_CXX11_ABI

351 _GLIBCXX20_ONLY( __removed++ );

352#endif

353 }

354

355 __first = __next;

356 }

357

358#if !_GLIBCXX_USE_CXX11_ABI

359 return _GLIBCXX20_ONLY( __removed );

360#else

361 return _GLIBCXX20_ONLY( __to_destroy.size() );

362#endif

363 }

364

365 template<typename _Tp, typename _Alloc>

366 typename list<_Tp, _Alloc>::__remove_return_type

369 {

372 if (__first == __last)

373 return _GLIBCXX20_ONLY( 0 );

374#if !_GLIBCXX_USE_CXX11_ABI

375 size_type __removed __attribute__((__unused__)) = 0;

376#endif

377 list __to_destroy(get_allocator());

379 while (++__next != __last)

380 {

381 if (*__first == *__next)

382 {

383 __to_destroy.splice(__to_destroy.begin(), *this, __next);

384#if !_GLIBCXX_USE_CXX11_ABI

385 _GLIBCXX20_ONLY( __removed++ );

386#endif

387 }

388 else

389 __first = __next;

390 __next = __first;

391 }

392

393#if !_GLIBCXX_USE_CXX11_ABI

394 return _GLIBCXX20_ONLY( __removed );

395#else

396 return _GLIBCXX20_ONLY( __to_destroy.size() );

397#endif

398 }

399

400 template<typename _Tp, typename _Alloc>

401 void

403#if __cplusplus >= 201103L

404 merge(list&& __x)

405#else

406 merge(list& __x)

407#endif

408 {

409

410

412 {

413 _M_check_equal_allocators(__x);

414

419

420 const _Finalize_merge __fin(*this, __x, __first2);

421

422 while (__first1 != __last1 && __first2 != __last2)

423 if (*__first2 < *__first1)

424 {

426 _M_transfer(__first1, __first2, ++__next);

427 __first2 = __next;

428 }

429 else

430 ++__first1;

431 if (__first2 != __last2)

432 {

433 _M_transfer(__last1, __first2, __last2);

434 __first2 = __last2;

435 }

436 }

437 }

438

439 template<typename _Tp, typename _Alloc>

440 template <typename _StrictWeakOrdering>

441 void

443#if __cplusplus >= 201103L

444 merge(list&& __x, _StrictWeakOrdering __comp)

445#else

446 merge(list& __x, _StrictWeakOrdering __comp)

447#endif

448 {

449

450

452 {

453 _M_check_equal_allocators(__x);

454

459

460 const _Finalize_merge __fin(*this, __x, __first2);

461

462 while (__first1 != __last1 && __first2 != __last2)

463 if (__comp(*__first2, *__first1))

464 {

466 _M_transfer(__first1, __first2, ++__next);

467 __first2 = __next;

468 }

469 else

470 ++__first1;

471 if (__first2 != __last2)

472 {

473 _M_transfer(__last1, __first2, __last2);

474 __first2 = __last2;

475 }

476 }

477 }

478

479 template<typename _Tp, typename _Alloc>

480 void

483 {

484

485 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node

486 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)

487 {

488 using __detail::_Scratch_list;

489

490

491

492

493

494

495

496

497 _Scratch_list __carry;

498 _Scratch_list __tmp[64];

499 _Scratch_list* __fill = __tmp;

500 _Scratch_list* __counter;

501

502 _Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;

503

504 __try

505 {

506 do

507 {

508 __carry._M_take_one(begin()._M_node);

509

510 for(__counter = __tmp;

511 __counter != __fill && !__counter->empty();

512 ++__counter)

513 {

514

515 __counter->merge(__carry, __ptr_comp);

516 __carry.swap(*__counter);

517 }

518 __carry.swap(*__counter);

519 if (__counter == __fill)

520 ++__fill;

521 }

522 while ( empty () );

523

524 for (__counter = __tmp + 1; __counter != __fill; ++__counter)

525 __counter->merge(__counter[-1], __ptr_comp);

526 __fill[-1].swap(this->_M_impl._M_node);

527 }

528 __catch(...)

529 {

530

531 __carry._M_put_all(end()._M_node);

532 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)

533 __tmp[__i]._M_put_all(end()._M_node);

534 __throw_exception_again;

535 }

536 }

537 }

538

539 template<typename _Tp, typename _Alloc>

540 template <typename _Predicate>

541 typename list<_Tp, _Alloc>::__remove_return_type

544 {

545#if !_GLIBCXX_USE_CXX11_ABI

546 size_type __removed __attribute__((__unused__)) = 0;

547#endif

548 list __to_destroy(get_allocator());

551 while (__first != __last)

552 {

554 ++__next;

555 if (__pred(*__first))

556 {

557 __to_destroy.splice(__to_destroy.begin(), *this, __first);

558#if !_GLIBCXX_USE_CXX11_ABI

559 _GLIBCXX20_ONLY( __removed++ );

560#endif

561 }

562 __first = __next;

563 }

564

565#if !_GLIBCXX_USE_CXX11_ABI

566 return _GLIBCXX20_ONLY( __removed );

567#else

568 return _GLIBCXX20_ONLY( __to_destroy.size() );

569#endif

570 }

571

572 template<typename _Tp, typename _Alloc>

573 template <typename _BinaryPredicate>

574 typename list<_Tp, _Alloc>::__remove_return_type

576 unique(_BinaryPredicate __binary_pred)

577 {

580 if (__first == __last)

581 return _GLIBCXX20_ONLY(0);

582#if !_GLIBCXX_USE_CXX11_ABI

583 size_type __removed __attribute__((__unused__)) = 0;

584#endif

585 list __to_destroy(get_allocator());

587 while (++__next != __last)

588 {

589 if (__binary_pred(*__first, *__next))

590 {

591 __to_destroy.splice(__to_destroy.begin(), *this, __next);

592#if !_GLIBCXX_USE_CXX11_ABI

593 _GLIBCXX20_ONLY( __removed++ );

594#endif

595 }

596 else

597 __first = __next;

598 __next = __first;

599 }

600

601#if !_GLIBCXX_USE_CXX11_ABI

602 return _GLIBCXX20_ONLY( __removed );

603#else

604 return _GLIBCXX20_ONLY( __to_destroy.size() );

605#endif

606 }

607

608#undef _GLIBCXX20_ONLY

609

610 template<typename _Tp, typename _Alloc>

611 template <typename _StrictWeakOrdering>

612 void

614 sort(_StrictWeakOrdering __comp)

615 {

616

617 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node

618 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)

619 {

620 using __detail::_Scratch_list;

621 _Scratch_list __carry;

622 _Scratch_list __tmp[64];

623 _Scratch_list* __fill = __tmp;

624 _Scratch_list* __counter;

625

626 _Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp

627 = { __comp };

628

629 __try

630 {

631 do

632 {

633 __carry._M_take_one(begin()._M_node);

634

635 for(__counter = __tmp;

636 __counter != __fill && !__counter->empty();

637 ++__counter)

638 {

639

640 __counter->merge(__carry, __ptr_comp);

641 __carry.swap(*__counter);

642 }

643 __carry.swap(*__counter);

644 if (__counter == __fill)

645 ++__fill;

646 }

647 while ( empty () );

648

649 for (__counter = __tmp + 1; __counter != __fill; ++__counter)

650 __counter->merge(__counter[-1], __ptr_comp);

651 __fill[-1].swap(this->_M_impl._M_node);

652 }

653 __catch(...)

654 {

655

656 __carry._M_put_all(end()._M_node);

657 for (size_t __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)

658 __tmp[__i]._M_put_all(end()._M_node);

659 __throw_exception_again;

660 }

661 }

662 }

663

664_GLIBCXX_END_NAMESPACE_CONTAINER

665_GLIBCXX_END_NAMESPACE_VERSION

666}

667

668#endif

669

constexpr _Tp * __addressof(_Tp &__r) noexcept

Same as C++11 std::addressof.

_Tp * end(valarray< _Tp > &__va) noexcept

Return an iterator pointing to one past the last element of the valarray.

_Tp * begin(valarray< _Tp > &__va) noexcept

Return an iterator pointing to the first element of the valarray.

ISO C++ entities toplevel namespace is std.

constexpr auto empty(const _Container &__cont) noexcept(noexcept(__cont.empty())) -> decltype(__cont.empty())

Return whether a container is empty.

constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())

Return the size of a container.

constexpr void advance(_InputIterator &__i, _Distance __n)

A generalization of pointer arithmetic.

An actual node in the list.

A standard container with linear time access to elements, and fixed time insertion/deletion at any po...

void resize(size_type __new_size)

Resizes the list to the specified number of elements.

iterator insert(const_iterator __position, const value_type &__x)

Inserts given value into list before specified iterator.

void sort()

Sort the elements.

iterator begin() noexcept

iterator emplace(const_iterator __position, _Args &&... __args)

Constructs object in list before specified iterator.

list & operator=(const list &__x)

List assignment operator.

__remove_return_type unique()

Remove consecutive duplicate elements.

size_type size() const noexcept

__remove_return_type remove(const _Tp &__value)

Remove all elements equal to value.

__remove_return_type remove_if(_Predicate)

Remove all elements satisfying a predicate.

void splice(const_iterator __position, list &&__x) noexcept

Insert contents of another list.

bool empty() const noexcept