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

2 | |

3 | // Copyright (C) 2001-2024 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 |

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

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

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

54 | */ |

55 | |

56 | #ifndef _STL_VECTOR_H |

57 | #define _STL_VECTOR_H 1 |

58 | |

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

60 | #include <bits/functexcept.h> |

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

62 | #if __cplusplus >= 201103L |

63 | #include <initializer_list> |

64 | #endif |

65 | #if __cplusplus >= 202002L |

66 | # include <compare> |

67 | #endif |

68 | |

69 | #include <debug/assertions.h> |

70 | |

71 | #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |

72 | extern "C" void |

73 | __sanitizer_annotate_contiguous_container(const void*, const void*, |

74 | const void*, const void*); |

75 | #endif |

76 | |

77 | namespace std _GLIBCXX_VISIBILITY(default) |

78 | { |

79 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

80 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

81 | |

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

83 | template<typename _Tp, typename _Alloc> |

84 | struct _Vector_base |

85 | { |

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

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

88 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type>::pointer |

89 | pointer; |

90 | |

91 | struct _Vector_impl_data |

92 | { |

93 | pointer _M_start; |

94 | pointer _M_finish; |

95 | pointer _M_end_of_storage; |

96 | |

97 | _GLIBCXX20_CONSTEXPR |

98 | _Vector_impl_data() _GLIBCXX_NOEXCEPT |

99 | : _M_start(), _M_finish(), _M_end_of_storage() |

100 | { } |

101 | |

102 | #if __cplusplus >= 201103L |

103 | _GLIBCXX20_CONSTEXPR |

104 | _Vector_impl_data(_Vector_impl_data&& __x) noexcept |

105 | : _M_start(__x._M_start), _M_finish(__x._M_finish), |

106 | _M_end_of_storage(__x._M_end_of_storage) |

107 | { __x._M_start = __x._M_finish = __x._M_end_of_storage = pointer(); } |

108 | #endif |

109 | |

110 | _GLIBCXX20_CONSTEXPR |

111 | void |

112 | _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT |

113 | { |

114 | _M_start = __x._M_start; |

115 | _M_finish = __x._M_finish; |

116 | _M_end_of_storage = __x._M_end_of_storage; |

117 | } |

118 | |

119 | _GLIBCXX20_CONSTEXPR |

120 | void |

121 | _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT |

122 | { |

123 | // Do not use std::swap(_M_start, __x._M_start), etc as it loses |

124 | // information used by TBAA. |

125 | _Vector_impl_data __tmp; |

126 | __tmp._M_copy_data(*this); |

127 | _M_copy_data(__x); |

128 | __x._M_copy_data(__tmp); |

129 | } |

130 | }; |

131 | |

132 | struct _Vector_impl |

133 | : public _Tp_alloc_type, public _Vector_impl_data |

134 | { |

135 | _GLIBCXX20_CONSTEXPR |

136 | _Vector_impl() _GLIBCXX_NOEXCEPT_IF( |

137 | is_nothrow_default_constructible<_Tp_alloc_type>::value) |

138 | #if __cpp_lib_concepts |

139 | requires is_default_constructible_v<_Tp_alloc_type> |

140 | #endif |

141 | : _Tp_alloc_type() |

142 | { } |

143 | |

144 | _GLIBCXX20_CONSTEXPR |

145 | _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT |

146 | : _Tp_alloc_type(__a) |

147 | { } |

148 | |

149 | #if __cplusplus >= 201103L |

150 | // Not defaulted, to enforce noexcept(true) even when |

151 | // !is_nothrow_move_constructible<_Tp_alloc_type>. |

152 | _GLIBCXX20_CONSTEXPR |

153 | _Vector_impl(_Vector_impl&& __x) noexcept |

154 | : _Tp_alloc_type(std::move(__x)), _Vector_impl_data(std::move(__x)) |

155 | { } |

156 | |

157 | _GLIBCXX20_CONSTEXPR |

158 | _Vector_impl(_Tp_alloc_type&& __a) noexcept |

159 | : _Tp_alloc_type(std::move(__a)) |

160 | { } |

161 | |

162 | _GLIBCXX20_CONSTEXPR |

163 | _Vector_impl(_Tp_alloc_type&& __a, _Vector_impl&& __rv) noexcept |

164 | : _Tp_alloc_type(std::move(__a)), _Vector_impl_data(std::move(__rv)) |

165 | { } |

166 | #endif |

167 | |

168 | #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |

169 | template<typename = _Tp_alloc_type> |

170 | struct _Asan |

171 | { |

172 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> |

173 | ::size_type size_type; |

174 | |

175 | static _GLIBCXX20_CONSTEXPR void |

176 | _S_shrink(_Vector_impl&, size_type) { } |

177 | static _GLIBCXX20_CONSTEXPR void |

178 | _S_on_dealloc(_Vector_impl&) { } |

179 | |

180 | typedef _Vector_impl& _Reinit; |

181 | |

182 | struct _Grow |

183 | { |

184 | _GLIBCXX20_CONSTEXPR _Grow(_Vector_impl&, size_type) { } |

185 | _GLIBCXX20_CONSTEXPR void _M_grew(size_type) { } |

186 | }; |

187 | }; |

188 | |

189 | // Enable ASan annotations for memory obtained from std::allocator. |

190 | template<typename _Up> |

191 | struct _Asan<allocator<_Up> > |

192 | { |

193 | typedef typename __gnu_cxx::__alloc_traits<_Tp_alloc_type> |

194 | ::size_type size_type; |

195 | |

196 | // Adjust ASan annotation for [_M_start, _M_end_of_storage) to |

197 | // mark end of valid region as __curr instead of __prev. |

198 | static _GLIBCXX20_CONSTEXPR void |

199 | _S_adjust(_Vector_impl& __impl, pointer __prev, pointer __curr) |

200 | { |

201 | #if __cpp_lib_is_constant_evaluated |

202 | if (std::is_constant_evaluated()) |

203 | return; |

204 | #endif |

205 | __sanitizer_annotate_contiguous_container(__impl._M_start, |

206 | __impl._M_end_of_storage, __prev, __curr); |

207 | } |

208 | |

209 | static _GLIBCXX20_CONSTEXPR void |

210 | _S_grow(_Vector_impl& __impl, size_type __n) |

211 | { _S_adjust(__impl, __impl._M_finish, __impl._M_finish + __n); } |

212 | |

213 | static _GLIBCXX20_CONSTEXPR void |

214 | _S_shrink(_Vector_impl& __impl, size_type __n) |

215 | { _S_adjust(__impl, __impl._M_finish + __n, __impl._M_finish); } |

216 | |

217 | static _GLIBCXX20_CONSTEXPR void |

218 | _S_on_dealloc(_Vector_impl& __impl) |

219 | { |

220 | if (__impl._M_start) |

221 | _S_adjust(__impl, __impl._M_finish, __impl._M_end_of_storage); |

222 | } |

223 | |

224 | // Used on reallocation to tell ASan unused capacity is invalid. |

225 | struct _Reinit |

226 | { |

227 | explicit _GLIBCXX20_CONSTEXPR |

228 | _Reinit(_Vector_impl& __impl) : _M_impl(__impl) |

229 | { |

230 | // Mark unused capacity as valid again before deallocating it. |

231 | _S_on_dealloc(_M_impl); |

232 | } |

233 | |

234 | _GLIBCXX20_CONSTEXPR |

235 | ~_Reinit() |

236 | { |

237 | // Mark unused capacity as invalid after reallocation. |

238 | if (_M_impl._M_start) |

239 | _S_adjust(_M_impl, _M_impl._M_end_of_storage, |

240 | _M_impl._M_finish); |

241 | } |

242 | |

243 | _Vector_impl& _M_impl; |

244 | |

245 | #if __cplusplus >= 201103L |

246 | _Reinit(const _Reinit&) = delete; |

247 | _Reinit& operator=(const _Reinit&) = delete; |

248 | #endif |

249 | }; |

250 | |

251 | // Tell ASan when unused capacity is initialized to be valid. |

252 | struct _Grow |

253 | { |

254 | _GLIBCXX20_CONSTEXPR |

255 | _Grow(_Vector_impl& __impl, size_type __n) |

256 | : _M_impl(__impl), _M_n(__n) |

257 | { _S_grow(_M_impl, __n); } |

258 | |

259 | _GLIBCXX20_CONSTEXPR |

260 | ~_Grow() { if (_M_n) _S_shrink(_M_impl, _M_n); } |

261 | |

262 | _GLIBCXX20_CONSTEXPR |

263 | void _M_grew(size_type __n) { _M_n -= __n; } |

264 | |

265 | #if __cplusplus >= 201103L |

266 | _Grow(const _Grow&) = delete; |

267 | _Grow& operator=(const _Grow&) = delete; |

268 | #endif |

269 | private: |

270 | _Vector_impl& _M_impl; |

271 | size_type _M_n; |

272 | }; |

273 | }; |

274 | |

275 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT \ |

276 | typename _Base::_Vector_impl::template _Asan<>::_Reinit const \ |

277 | __attribute__((__unused__)) __reinit_guard(this->_M_impl) |

278 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \ |

279 | typename _Base::_Vector_impl::template _Asan<>::_Grow \ |

280 | __attribute__((__unused__)) __grow_guard(this->_M_impl, (n)) |

281 | #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) __grow_guard._M_grew(n) |

282 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \ |

283 | _Base::_Vector_impl::template _Asan<>::_S_shrink(this->_M_impl, n) |

284 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \ |

285 | _Base::_Vector_impl::template _Asan<>::_S_on_dealloc(this->_M_impl) |

286 | #else // ! (_GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR) |

287 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT |

288 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) |

289 | #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) |

290 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) |

291 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC |

292 | #endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |

293 | }; |

294 | |

295 | public: |

296 | typedef _Alloc allocator_type; |

297 | |

298 | _GLIBCXX20_CONSTEXPR |

299 | _Tp_alloc_type& |

300 | _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT |

301 | { return this->_M_impl; } |

302 | |

303 | _GLIBCXX20_CONSTEXPR |

304 | const _Tp_alloc_type& |

305 | _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT |

306 | { return this->_M_impl; } |

307 | |

308 | _GLIBCXX20_CONSTEXPR |

309 | allocator_type |

310 | get_allocator() const _GLIBCXX_NOEXCEPT |

311 | { return allocator_type(_M_get_Tp_allocator()); } |

312 | |

313 | #if __cplusplus >= 201103L |

314 | _Vector_base() = default; |

315 | #else |

316 | _Vector_base() { } |

317 | #endif |

318 | |

319 | _GLIBCXX20_CONSTEXPR |

320 | _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT |

321 | : _M_impl(__a) { } |

322 | |

323 | // Kept for ABI compatibility. |

324 | #if !_GLIBCXX_INLINE_VERSION |

325 | _GLIBCXX20_CONSTEXPR |

326 | _Vector_base(size_t __n) |

327 | : _M_impl() |

328 | { _M_create_storage(__n); } |

329 | #endif |

330 | |

331 | _GLIBCXX20_CONSTEXPR |

332 | _Vector_base(size_t __n, const allocator_type& __a) |

333 | : _M_impl(__a) |

334 | { _M_create_storage(__n); } |

335 | |

336 | #if __cplusplus >= 201103L |

337 | _Vector_base(_Vector_base&&) = default; |

338 | |

339 | // Kept for ABI compatibility. |

340 | # if !_GLIBCXX_INLINE_VERSION |

341 | _GLIBCXX20_CONSTEXPR |

342 | _Vector_base(_Tp_alloc_type&& __a) noexcept |

343 | : _M_impl(std::move(__a)) { } |

344 | |

345 | _GLIBCXX20_CONSTEXPR |

346 | _Vector_base(_Vector_base&& __x, const allocator_type& __a) |

347 | : _M_impl(__a) |

348 | { |

349 | if (__x.get_allocator() == __a) |

350 | this->_M_impl._M_swap_data(__x._M_impl); |

351 | else |

352 | { |

353 | size_t __n = __x._M_impl._M_finish - __x._M_impl._M_start; |

354 | _M_create_storage(__n); |

355 | } |

356 | } |

357 | # endif |

358 | |

359 | _GLIBCXX20_CONSTEXPR |

360 | _Vector_base(const allocator_type& __a, _Vector_base&& __x) |

361 | : _M_impl(_Tp_alloc_type(__a), std::move(__x._M_impl)) |

362 | { } |

363 | #endif |

364 | |

365 | _GLIBCXX20_CONSTEXPR |

366 | ~_Vector_base() _GLIBCXX_NOEXCEPT |

367 | { |

368 | _M_deallocate(p: _M_impl._M_start, |

369 | n: _M_impl._M_end_of_storage - _M_impl._M_start); |

370 | } |

371 | |

372 | public: |

373 | _Vector_impl _M_impl; |

374 | |

375 | _GLIBCXX20_CONSTEXPR |

376 | pointer |

377 | _M_allocate(size_t __n) |

378 | { |

379 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; |

380 | return __n != 0 ? _Tr::allocate(_M_impl, __n) : pointer(); |

381 | } |

382 | |

383 | _GLIBCXX20_CONSTEXPR |

384 | void |

385 | _M_deallocate(pointer __p, size_t __n) |

386 | { |

387 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Tr; |

388 | if (__p) |

389 | _Tr::deallocate(_M_impl, __p, __n); |

390 | } |

391 | |

392 | protected: |

393 | |

394 | _GLIBCXX20_CONSTEXPR |

395 | void |

396 | _M_create_storage(size_t __n) |

397 | { |

398 | this->_M_impl._M_start = this->_M_allocate(__n); |

399 | this->_M_impl._M_finish = this->_M_impl._M_start; |

400 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; |

401 | } |

402 | }; |

403 | |

404 | /** |

405 | * @brief A standard container which offers fixed time access to |

406 | * individual elements in any order. |

407 | * |

408 | * @ingroup sequences |

409 | * @headerfile vector |

410 | * @since C++98 |

411 | * |

412 | * @tparam _Tp Type of element. |

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

414 | * |

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

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

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

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

419 | * %exception of @c push_front and @c pop_front. |

420 | * |

421 | * In some terminology a %vector can be described as a dynamic |

422 | * C-style array, it offers fast and efficient access to individual |

423 | * elements in any order and saves the user from worrying about |

424 | * memory and size allocation. Subscripting ( @c [] ) access is |

425 | * also provided as with C-style arrays. |

426 | */ |

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

428 | class vector : protected _Vector_base<_Tp, _Alloc> |

429 | { |

430 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

431 | // Concept requirements. |

432 | typedef typename _Alloc::value_type _Alloc_value_type; |

433 | # if __cplusplus < 201103L |

434 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

435 | # endif |

436 | __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) |

437 | #endif |

438 | |

439 | #if __cplusplus >= 201103L |

440 | static_assert(is_same<typename remove_cv<_Tp>::type, _Tp>::value, |

441 | "std::vector must have a non-const, non-volatile value_type"); |

442 | # if __cplusplus > 201703L || defined __STRICT_ANSI__ |

443 | static_assert(is_same<typename _Alloc::value_type, _Tp>::value, |

444 | "std::vector must have the same value_type as its allocator"); |

445 | # endif |

446 | #endif |

447 | |

448 | typedef _Vector_base<_Tp, _Alloc> _Base; |

449 | typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; |

450 | typedef __gnu_cxx::__alloc_traits<_Tp_alloc_type> _Alloc_traits; |

451 | |

452 | public: |

453 | typedef _Tp value_type; |

454 | typedef typename _Base::pointer pointer; |

455 | typedef typename _Alloc_traits::const_pointer const_pointer; |

456 | typedef typename _Alloc_traits::reference reference; |

457 | typedef typename _Alloc_traits::const_reference const_reference; |

458 | typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator; |

459 | typedef __gnu_cxx::__normal_iterator<const_pointer, vector> |

460 | const_iterator; |

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

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

463 | typedef size_t size_type; |

464 | typedef ptrdiff_t difference_type; |

465 | typedef _Alloc allocator_type; |

466 | |

467 | private: |

468 | #if __cplusplus >= 201103L |

469 | static constexpr bool |

470 | _S_nothrow_relocate(true_type) |

471 | { |

472 | return noexcept(std::__relocate_a(std::declval<pointer>(), |

473 | std::declval<pointer>(), |

474 | std::declval<pointer>(), |

475 | std::declval<_Tp_alloc_type&>())); |

476 | } |

477 | |

478 | static constexpr bool |

479 | _S_nothrow_relocate(false_type) |

480 | { return false; } |

481 | |

482 | static constexpr bool |

483 | _S_use_relocate() |

484 | { |

485 | // Instantiating std::__relocate_a might cause an error outside the |

486 | // immediate context (in __relocate_object_a's noexcept-specifier), |

487 | // so only do it if we know the type can be move-inserted into *this. |

488 | return _S_nothrow_relocate(__is_move_insertable<_Tp_alloc_type>{}); |

489 | } |

490 | |

491 | static pointer |

492 | _S_do_relocate(pointer __first, pointer __last, pointer __result, |

493 | _Tp_alloc_type& __alloc, true_type) noexcept |

494 | { |

495 | return std::__relocate_a(__first, __last, __result, __alloc); |

496 | } |

497 | |

498 | static pointer |

499 | _S_do_relocate(pointer, pointer, pointer __result, |

500 | _Tp_alloc_type&, false_type) noexcept |

501 | { return __result; } |

502 | |

503 | static _GLIBCXX20_CONSTEXPR pointer |

504 | _S_relocate(pointer __first, pointer __last, pointer __result, |

505 | _Tp_alloc_type& __alloc) noexcept |

506 | { |

507 | #if __cpp_if_constexpr |

508 | // All callers have already checked _S_use_relocate() so just do it. |

509 | return std::__relocate_a(__first, __last, __result, __alloc); |

510 | #else |

511 | using __do_it = __bool_constant<_S_use_relocate()>; |

512 | return _S_do_relocate(__first, __last, __result, __alloc, __do_it{}); |

513 | #endif |

514 | } |

515 | #endif // C++11 |

516 | |

517 | protected: |

518 | using _Base::_M_allocate; |

519 | using _Base::_M_deallocate; |

520 | using _Base::_M_impl; |

521 | using _Base::_M_get_Tp_allocator; |

522 | |

523 | public: |

524 | // [23.2.4.1] construct/copy/destroy |

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

526 | |

527 | /** |

528 | * @brief Creates a %vector with no elements. |

529 | */ |

530 | #if __cplusplus >= 201103L |

531 | vector() = default; |

532 | #else |

533 | vector() { } |

534 | #endif |

535 | |

536 | /** |

537 | * @brief Creates a %vector with no elements. |

538 | * @param __a An allocator object. |

539 | */ |

540 | explicit |

541 | _GLIBCXX20_CONSTEXPR |

542 | vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT |

543 | : _Base(__a) { } |

544 | |

545 | #if __cplusplus >= 201103L |

546 | /** |

547 | * @brief Creates a %vector with default constructed elements. |

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

549 | * @param __a An allocator. |

550 | * |

551 | * This constructor fills the %vector with @a __n default |

552 | * constructed elements. |

553 | */ |

554 | explicit |

555 | _GLIBCXX20_CONSTEXPR |

556 | vector(size_type __n, const allocator_type& __a = allocator_type()) |

557 | : _Base(_S_check_init_len(__n, __a), __a) |

558 | { _M_default_initialize(__n); } |

559 | |

560 | /** |

561 | * @brief Creates a %vector with copies of an exemplar element. |

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

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

564 | * @param __a An allocator. |

565 | * |

566 | * This constructor fills the %vector with @a __n copies of @a __value. |

567 | */ |

568 | _GLIBCXX20_CONSTEXPR |

569 | vector(size_type __n, const value_type& __value, |

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

571 | : _Base(_S_check_init_len(__n, __a), __a) |

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

573 | #else |

574 | /** |

575 | * @brief Creates a %vector with copies of an exemplar element. |

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

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

578 | * @param __a An allocator. |

579 | * |

580 | * This constructor fills the %vector with @a __n copies of @a __value. |

581 | */ |

582 | explicit |

583 | vector(size_type __n, const value_type& __value = value_type(), |

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

585 | : _Base(_S_check_init_len(__n, __a), __a) |

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

587 | #endif |

588 | |

589 | /** |

590 | * @brief %Vector copy constructor. |

591 | * @param __x A %vector of identical element and allocator types. |

592 | * |

593 | * All the elements of @a __x are copied, but any unused capacity in |

594 | * @a __x will not be copied |

595 | * (i.e. capacity() == size() in the new %vector). |

596 | * |

597 | * The newly-created %vector uses a copy of the allocator object used |

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

599 | */ |

600 | _GLIBCXX20_CONSTEXPR |

601 | vector(const vector& __x) |

602 | : _Base(__x.size(), |

603 | _Alloc_traits::_S_select_on_copy(__x._M_get_Tp_allocator())) |

604 | { |

605 | this->_M_impl._M_finish = |

606 | std::__uninitialized_copy_a(__x.begin(), __x.end(), |

607 | this->_M_impl._M_start, |

608 | _M_get_Tp_allocator()); |

609 | } |

610 | |

611 | #if __cplusplus >= 201103L |

612 | /** |

613 | * @brief %Vector move constructor. |

614 | * |

615 | * The newly-created %vector contains the exact contents of the |

616 | * moved instance. |

617 | * The contents of the moved instance are a valid, but unspecified |

618 | * %vector. |

619 | */ |

620 | vector(vector&&) noexcept = default; |

621 | |

622 | /// Copy constructor with alternative allocator |

623 | _GLIBCXX20_CONSTEXPR |

624 | vector(const vector& __x, const __type_identity_t<allocator_type>& __a) |

625 | : _Base(__x.size(), __a) |

626 | { |

627 | this->_M_impl._M_finish = |

628 | std::__uninitialized_copy_a(__x.begin(), __x.end(), |

629 | this->_M_impl._M_start, |

630 | _M_get_Tp_allocator()); |

631 | } |

632 | |

633 | private: |

634 | _GLIBCXX20_CONSTEXPR |

635 | vector(vector&& __rv, const allocator_type& __m, true_type) noexcept |

636 | : _Base(__m, std::move(__rv)) |

637 | { } |

638 | |

639 | _GLIBCXX20_CONSTEXPR |

640 | vector(vector&& __rv, const allocator_type& __m, false_type) |

641 | : _Base(__m) |

642 | { |

643 | if (__rv.get_allocator() == __m) |

644 | this->_M_impl._M_swap_data(__rv._M_impl); |

645 | else if (!__rv.empty()) |

646 | { |

647 | this->_M_create_storage(__rv.size()); |

648 | this->_M_impl._M_finish = |

649 | std::__uninitialized_move_a(__rv.begin(), __rv.end(), |

650 | this->_M_impl._M_start, |

651 | _M_get_Tp_allocator()); |

652 | __rv.clear(); |

653 | } |

654 | } |

655 | |

656 | public: |

657 | /// Move constructor with alternative allocator |

658 | _GLIBCXX20_CONSTEXPR |

659 | vector(vector&& __rv, const __type_identity_t<allocator_type>& __m) |

660 | noexcept( noexcept( |

661 | vector(std::declval<vector&&>(), std::declval<const allocator_type&>(), |

662 | std::declval<typename _Alloc_traits::is_always_equal>())) ) |

663 | : vector(std::move(__rv), __m, typename _Alloc_traits::is_always_equal{}) |

664 | { } |

665 | |

666 | /** |

667 | * @brief Builds a %vector from an initializer list. |

668 | * @param __l An initializer_list. |

669 | * @param __a An allocator. |

670 | * |

671 | * Create a %vector consisting of copies of the elements in the |

672 | * initializer_list @a __l. |

673 | * |

674 | * This will call the element type's copy constructor N times |

675 | * (where N is @a __l.size()) and do no memory reallocation. |

676 | */ |

677 | _GLIBCXX20_CONSTEXPR |

678 | vector(initializer_list<value_type> __l, |

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

680 | : _Base(__a) |

681 | { |

682 | _M_range_initialize(__l.begin(), __l.end(), |

683 | random_access_iterator_tag()); |

684 | } |

685 | #endif |

686 | |

687 | /** |

688 | * @brief Builds a %vector from a range. |

689 | * @param __first An input iterator. |

690 | * @param __last An input iterator. |

691 | * @param __a An allocator. |

692 | * |

693 | * Create a %vector consisting of copies of the elements from |

694 | * [first,last). |

695 | * |

696 | * If the iterators are forward, bidirectional, or |

697 | * random-access, then this will call the elements' copy |

698 | * constructor N times (where N is distance(first,last)) and do |

699 | * no memory reallocation. But if only input iterators are |

700 | * used, then this will do at most 2N calls to the copy |

701 | * constructor, and logN memory reallocations. |

702 | */ |

703 | #if __cplusplus >= 201103L |

704 | template<typename _InputIterator, |

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

706 | _GLIBCXX20_CONSTEXPR |

707 | vector(_InputIterator __first, _InputIterator __last, |

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

709 | : _Base(__a) |

710 | { |

711 | _M_range_initialize(__first, __last, |

712 | std::__iterator_category(__first)); |

713 | } |

714 | #else |

715 | template<typename _InputIterator> |

716 | vector(_InputIterator __first, _InputIterator __last, |

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

718 | : _Base(__a) |

719 | { |

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

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

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

723 | } |

724 | #endif |

725 | |

726 | /** |

727 | * The dtor only erases the elements, and note that if the |

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

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

730 | * responsibility. |

731 | */ |

732 | _GLIBCXX20_CONSTEXPR |

733 | ~vector() _GLIBCXX_NOEXCEPT |

734 | { |

735 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |

736 | _M_get_Tp_allocator()); |

737 | _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC; |

738 | } |

739 | |

740 | /** |

741 | * @brief %Vector assignment operator. |

742 | * @param __x A %vector of identical element and allocator types. |

743 | * |

744 | * All the elements of @a __x are copied, but any unused capacity in |

745 | * @a __x will not be copied. |

746 | * |

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

748 | */ |

749 | _GLIBCXX20_CONSTEXPR |

750 | vector& |

751 | operator=(const vector& __x); |

752 | |

753 | #if __cplusplus >= 201103L |

754 | /** |

755 | * @brief %Vector move assignment operator. |

756 | * @param __x A %vector of identical element and allocator types. |

757 | * |

758 | * The contents of @a __x are moved into this %vector (without copying, |

759 | * if the allocators permit it). |

760 | * Afterwards @a __x is a valid, but unspecified %vector. |

761 | * |

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

763 | */ |

764 | _GLIBCXX20_CONSTEXPR |

765 | vector& |

766 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move()) |

767 | { |

768 | constexpr bool __move_storage = |

769 | _Alloc_traits::_S_propagate_on_move_assign() |

770 | || _Alloc_traits::_S_always_equal(); |

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

772 | return *this; |

773 | } |

774 | |

775 | /** |

776 | * @brief %Vector list assignment operator. |

777 | * @param __l An initializer_list. |

778 | * |

779 | * This function fills a %vector with copies of the elements in the |

780 | * initializer list @a __l. |

781 | * |

782 | * Note that the assignment completely changes the %vector and |

783 | * that the resulting %vector's size is the same as the number |

784 | * of elements assigned. |

785 | */ |

786 | _GLIBCXX20_CONSTEXPR |

787 | vector& |

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

789 | { |

790 | this->_M_assign_aux(__l.begin(), __l.end(), |

791 | random_access_iterator_tag()); |

792 | return *this; |

793 | } |

794 | #endif |

795 | |

796 | /** |

797 | * @brief Assigns a given value to a %vector. |

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

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

800 | * |

801 | * This function fills a %vector with @a __n copies of the given |

802 | * value. Note that the assignment completely changes the |

803 | * %vector and that the resulting %vector's size is the same as |

804 | * the number of elements assigned. |

805 | */ |

806 | _GLIBCXX20_CONSTEXPR |

807 | void |

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

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

810 | |

811 | /** |

812 | * @brief Assigns a range to a %vector. |

813 | * @param __first An input iterator. |

814 | * @param __last An input iterator. |

815 | * |

816 | * This function fills a %vector with copies of the elements in the |

817 | * range [__first,__last). |

818 | * |

819 | * Note that the assignment completely changes the %vector and |

820 | * that the resulting %vector's size is the same as the number |

821 | * of elements assigned. |

822 | */ |

823 | #if __cplusplus >= 201103L |

824 | template<typename _InputIterator, |

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

826 | _GLIBCXX20_CONSTEXPR |

827 | void |

828 | assign(_InputIterator __first, _InputIterator __last) |

829 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } |

830 | #else |

831 | template<typename _InputIterator> |

832 | void |

833 | assign(_InputIterator __first, _InputIterator __last) |

834 | { |

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

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

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

838 | } |

839 | #endif |

840 | |

841 | #if __cplusplus >= 201103L |

842 | /** |

843 | * @brief Assigns an initializer list to a %vector. |

844 | * @param __l An initializer_list. |

845 | * |

846 | * This function fills a %vector with copies of the elements in the |

847 | * initializer list @a __l. |

848 | * |

849 | * Note that the assignment completely changes the %vector and |

850 | * that the resulting %vector's size is the same as the number |

851 | * of elements assigned. |

852 | */ |

853 | _GLIBCXX20_CONSTEXPR |

854 | void |

855 | assign(initializer_list<value_type> __l) |

856 | { |

857 | this->_M_assign_aux(__l.begin(), __l.end(), |

858 | random_access_iterator_tag()); |

859 | } |

860 | #endif |

861 | |

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

863 | using _Base::get_allocator; |

864 | |

865 | // iterators |

866 | /** |

867 | * Returns a read/write iterator that points to the first |

868 | * element in the %vector. Iteration is done in ordinary |

869 | * element order. |

870 | */ |

871 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

872 | iterator |

873 | begin() _GLIBCXX_NOEXCEPT |

874 | { return iterator(this->_M_impl._M_start); } |

875 | |

876 | /** |

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

878 | * first element in the %vector. Iteration is done in ordinary |

879 | * element order. |

880 | */ |

881 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

882 | const_iterator |

883 | begin() const _GLIBCXX_NOEXCEPT |

884 | { return const_iterator(this->_M_impl._M_start); } |

885 | |

886 | /** |

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

888 | * element in the %vector. Iteration is done in ordinary |

889 | * element order. |

890 | */ |

891 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

892 | iterator |

893 | end() _GLIBCXX_NOEXCEPT |

894 | { return iterator(this->_M_impl._M_finish); } |

895 | |

896 | /** |

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

898 | * the last element in the %vector. Iteration is done in |

899 | * ordinary element order. |

900 | */ |

901 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

902 | const_iterator |

903 | end() const _GLIBCXX_NOEXCEPT |

904 | { return const_iterator(this->_M_impl._M_finish); } |

905 | |

906 | /** |

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

908 | * last element in the %vector. Iteration is done in reverse |

909 | * element order. |

910 | */ |

911 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

912 | reverse_iterator |

913 | rbegin() _GLIBCXX_NOEXCEPT |

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

915 | |

916 | /** |

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

918 | * to the last element in the %vector. Iteration is done in |

919 | * reverse element order. |

920 | */ |

921 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

922 | const_reverse_iterator |

923 | rbegin() const _GLIBCXX_NOEXCEPT |

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

925 | |

926 | /** |

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

928 | * before the first element in the %vector. Iteration is done |

929 | * in reverse element order. |

930 | */ |

931 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

932 | reverse_iterator |

933 | rend() _GLIBCXX_NOEXCEPT |

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

935 | |

936 | /** |

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

938 | * to one before the first element in the %vector. Iteration |

939 | * is done in reverse element order. |

940 | */ |

941 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

942 | const_reverse_iterator |

943 | rend() const _GLIBCXX_NOEXCEPT |

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

945 | |

946 | #if __cplusplus >= 201103L |

947 | /** |

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

949 | * first element in the %vector. Iteration is done in ordinary |

950 | * element order. |

951 | */ |

952 | [[__nodiscard__]] _GLIBCXX20_CONSTEXPR |

953 | const_iterator |

954 | cbegin() const noexcept |

955 | { return const_iterator(this->_M_impl._M_start); } |

956 | |

957 | /** |

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

959 | * the last element in the %vector. Iteration is done in |

960 | * ordinary element order. |

961 | */ |

962 | [[__nodiscard__]] _GLIBCXX20_CONSTEXPR |

963 | const_iterator |

964 | cend() const noexcept |

965 | { return const_iterator(this->_M_impl._M_finish); } |

966 | |

967 | /** |

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

969 | * to the last element in the %vector. Iteration is done in |

970 | * reverse element order. |

971 | */ |

972 | [[__nodiscard__]] _GLIBCXX20_CONSTEXPR |

973 | const_reverse_iterator |

974 | crbegin() const noexcept |

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

976 | |

977 | /** |

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

979 | * to one before the first element in the %vector. Iteration |

980 | * is done in reverse element order. |

981 | */ |

982 | [[__nodiscard__]] _GLIBCXX20_CONSTEXPR |

983 | const_reverse_iterator |

984 | crend() const noexcept |

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

986 | #endif |

987 | |

988 | // [23.2.4.2] capacity |

989 | /** Returns the number of elements in the %vector. */ |

990 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

991 | size_type |

992 | size() const _GLIBCXX_NOEXCEPT |

993 | { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); } |

994 | |

995 | /** Returns the size() of the largest possible %vector. */ |

996 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

997 | size_type |

998 | max_size() const _GLIBCXX_NOEXCEPT |

999 | { return _S_max_size(a: _M_get_Tp_allocator()); } |

1000 | |

1001 | #if __cplusplus >= 201103L |

1002 | /** |

1003 | * @brief Resizes the %vector to the specified number of elements. |

1004 | * @param __new_size Number of elements the %vector should contain. |

1005 | * |

1006 | * This function will %resize the %vector to the specified |

1007 | * number of elements. If the number is smaller than the |

1008 | * %vector's current size the %vector is truncated, otherwise |

1009 | * default constructed elements are appended. |

1010 | */ |

1011 | _GLIBCXX20_CONSTEXPR |

1012 | void |

1013 | resize(size_type __new_size) |

1014 | { |

1015 | if (__new_size > size()) |

1016 | _M_default_append(n: __new_size - size()); |

1017 | else if (__new_size < size()) |

1018 | _M_erase_at_end(pos: this->_M_impl._M_start + __new_size); |

1019 | } |

1020 | |

1021 | /** |

1022 | * @brief Resizes the %vector to the specified number of elements. |

1023 | * @param __new_size Number of elements the %vector should contain. |

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

1025 | * |

1026 | * This function will %resize the %vector to the specified |

1027 | * number of elements. If the number is smaller than the |

1028 | * %vector's current size the %vector is truncated, otherwise |

1029 | * the %vector is extended and new elements are populated with |

1030 | * given data. |

1031 | */ |

1032 | _GLIBCXX20_CONSTEXPR |

1033 | void |

1034 | resize(size_type __new_size, const value_type& __x) |

1035 | { |

1036 | if (__new_size > size()) |

1037 | _M_fill_insert(pos: end(), n: __new_size - size(), __x); |

1038 | else if (__new_size < size()) |

1039 | _M_erase_at_end(pos: this->_M_impl._M_start + __new_size); |

1040 | } |

1041 | #else |

1042 | /** |

1043 | * @brief Resizes the %vector to the specified number of elements. |

1044 | * @param __new_size Number of elements the %vector should contain. |

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

1046 | * |

1047 | * This function will %resize the %vector to the specified |

1048 | * number of elements. If the number is smaller than the |

1049 | * %vector's current size the %vector is truncated, otherwise |

1050 | * the %vector is extended and new elements are populated with |

1051 | * given data. |

1052 | */ |

1053 | _GLIBCXX20_CONSTEXPR |

1054 | void |

1055 | resize(size_type __new_size, value_type __x = value_type()) |

1056 | { |

1057 | if (__new_size > size()) |

1058 | _M_fill_insert(end(), __new_size - size(), __x); |

1059 | else if (__new_size < size()) |

1060 | _M_erase_at_end(this->_M_impl._M_start + __new_size); |

1061 | } |

1062 | #endif |

1063 | |

1064 | #if __cplusplus >= 201103L |

1065 | /** A non-binding request to reduce capacity() to size(). */ |

1066 | _GLIBCXX20_CONSTEXPR |

1067 | void |

1068 | shrink_to_fit() |

1069 | { _M_shrink_to_fit(); } |

1070 | #endif |

1071 | |

1072 | /** |

1073 | * Returns the total number of elements that the %vector can |

1074 | * hold before needing to allocate more memory. |

1075 | */ |

1076 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1077 | size_type |

1078 | capacity() const _GLIBCXX_NOEXCEPT |

1079 | { |

1080 | return size_type(this->_M_impl._M_end_of_storage |

1081 | - this->_M_impl._M_start); |

1082 | } |

1083 | |

1084 | /** |

1085 | * Returns true if the %vector is empty. (Thus begin() would |

1086 | * equal end().) |

1087 | */ |

1088 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1089 | bool |

1090 | empty() const _GLIBCXX_NOEXCEPT |

1091 | { return begin() == end(); } |

1092 | |

1093 | /** |

1094 | * @brief Attempt to preallocate enough memory for specified number of |

1095 | * elements. |

1096 | * @param __n Number of elements required. |

1097 | * @throw std::length_error If @a n exceeds @c max_size(). |

1098 | * |

1099 | * This function attempts to reserve enough memory for the |

1100 | * %vector to hold the specified number of elements. If the |

1101 | * number requested is more than max_size(), length_error is |

1102 | * thrown. |

1103 | * |

1104 | * The advantage of this function is that if optimal code is a |

1105 | * necessity and the user can determine the number of elements |

1106 | * that will be required, the user can reserve the memory in |

1107 | * %advance, and thus prevent a possible reallocation of memory |

1108 | * and copying of %vector data. |

1109 | */ |

1110 | _GLIBCXX20_CONSTEXPR |

1111 | void |

1112 | reserve(size_type __n); |

1113 | |

1114 | // element access |

1115 | /** |

1116 | * @brief Subscript access to the data contained in the %vector. |

1117 | * @param __n The index of the element for which data should be |

1118 | * accessed. |

1119 | * @return Read/write reference to data. |

1120 | * |

1121 | * This operator allows for easy, array-style, data access. |

1122 | * Note that data access with this operator is unchecked and |

1123 | * out_of_range lookups are not defined. (For checked lookups |

1124 | * see at().) |

1125 | */ |

1126 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1127 | reference |

1128 | operator[](size_type __n) _GLIBCXX_NOEXCEPT |

1129 | { |

1130 | __glibcxx_requires_subscript(__n); |

1131 | return *(this->_M_impl._M_start + __n); |

1132 | } |

1133 | |

1134 | /** |

1135 | * @brief Subscript access to the data contained in the %vector. |

1136 | * @param __n The index of the element for which data should be |

1137 | * accessed. |

1138 | * @return Read-only (constant) reference to data. |

1139 | * |

1140 | * This operator allows for easy, array-style, data access. |

1141 | * Note that data access with this operator is unchecked and |

1142 | * out_of_range lookups are not defined. (For checked lookups |

1143 | * see at().) |

1144 | */ |

1145 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1146 | const_reference |

1147 | operator[](size_type __n) const _GLIBCXX_NOEXCEPT |

1148 | { |

1149 | __glibcxx_requires_subscript(__n); |

1150 | return *(this->_M_impl._M_start + __n); |

1151 | } |

1152 | |

1153 | protected: |

1154 | /// Safety check used only from at(). |

1155 | _GLIBCXX20_CONSTEXPR |

1156 | void |

1157 | _M_range_check(size_type __n) const |

1158 | { |

1159 | if (__n >= this->size()) |

1160 | __throw_out_of_range_fmt(__N("vector::_M_range_check: __n " |

1161 | "(which is %zu) >= this->size() " |

1162 | "(which is %zu)"), |

1163 | __n, this->size()); |

1164 | } |

1165 | |

1166 | public: |

1167 | /** |

1168 | * @brief Provides access to the data contained in the %vector. |

1169 | * @param __n The index of the element for which data should be |

1170 | * accessed. |

1171 | * @return Read/write reference to data. |

1172 | * @throw std::out_of_range If @a __n is an invalid index. |

1173 | * |

1174 | * This function provides for safer data access. The parameter |

1175 | * is first checked that it is in the range of the vector. The |

1176 | * function throws out_of_range if the check fails. |

1177 | */ |

1178 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1179 | reference |

1180 | at(size_type __n) |

1181 | { |

1182 | _M_range_check(__n); |

1183 | return (*this)[__n]; |

1184 | } |

1185 | |

1186 | /** |

1187 | * @brief Provides access to the data contained in the %vector. |

1188 | * @param __n The index of the element for which data should be |

1189 | * accessed. |

1190 | * @return Read-only (constant) reference to data. |

1191 | * @throw std::out_of_range If @a __n is an invalid index. |

1192 | * |

1193 | * This function provides for safer data access. The parameter |

1194 | * is first checked that it is in the range of the vector. The |

1195 | * function throws out_of_range if the check fails. |

1196 | */ |

1197 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1198 | const_reference |

1199 | at(size_type __n) const |

1200 | { |

1201 | _M_range_check(__n); |

1202 | return (*this)[__n]; |

1203 | } |

1204 | |

1205 | /** |

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

1207 | * element of the %vector. |

1208 | */ |

1209 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1210 | reference |

1211 | front() _GLIBCXX_NOEXCEPT |

1212 | { |

1213 | __glibcxx_requires_nonempty(); |

1214 | return *begin(); |

1215 | } |

1216 | |

1217 | /** |

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

1219 | * element of the %vector. |

1220 | */ |

1221 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1222 | const_reference |

1223 | front() const _GLIBCXX_NOEXCEPT |

1224 | { |

1225 | __glibcxx_requires_nonempty(); |

1226 | return *begin(); |

1227 | } |

1228 | |

1229 | /** |

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

1231 | * element of the %vector. |

1232 | */ |

1233 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1234 | reference |

1235 | back() _GLIBCXX_NOEXCEPT |

1236 | { |

1237 | __glibcxx_requires_nonempty(); |

1238 | return *(end() - 1); |

1239 | } |

1240 | |

1241 | /** |

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

1243 | * last element of the %vector. |

1244 | */ |

1245 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1246 | const_reference |

1247 | back() const _GLIBCXX_NOEXCEPT |

1248 | { |

1249 | __glibcxx_requires_nonempty(); |

1250 | return *(end() - 1); |

1251 | } |

1252 | |

1253 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

1254 | // DR 464. Suggestion for new member functions in standard containers. |

1255 | // data access |

1256 | /** |

1257 | * Returns a pointer such that [data(), data() + size()) is a valid |

1258 | * range. For a non-empty %vector, data() == &front(). |

1259 | */ |

1260 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1261 | _Tp* |

1262 | data() _GLIBCXX_NOEXCEPT |

1263 | { return _M_data_ptr(this->_M_impl._M_start); } |

1264 | |

1265 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

1266 | const _Tp* |

1267 | data() const _GLIBCXX_NOEXCEPT |

1268 | { return _M_data_ptr(this->_M_impl._M_start); } |

1269 | |

1270 | // [23.2.4.3] modifiers |

1271 | /** |

1272 | * @brief Add data to the end of the %vector. |

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

1274 | * |

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

1276 | * element at the end of the %vector and assigns the given data |

1277 | * to it. Due to the nature of a %vector this operation can be |

1278 | * done in constant time if the %vector has preallocated space |

1279 | * available. |

1280 | */ |

1281 | _GLIBCXX20_CONSTEXPR |

1282 | void |

1283 | push_back(const value_type& __x) |

1284 | { |

1285 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |

1286 | { |

1287 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |

1288 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |

1289 | __x); |

1290 | ++this->_M_impl._M_finish; |

1291 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |

1292 | } |

1293 | else |

1294 | _M_realloc_append(__x); |

1295 | } |

1296 | |

1297 | #if __cplusplus >= 201103L |

1298 | _GLIBCXX20_CONSTEXPR |

1299 | void |

1300 | push_back(value_type&& __x) |

1301 | { emplace_back(std::move(__x)); } |

1302 | |

1303 | template<typename... _Args> |

1304 | #if __cplusplus > 201402L |

1305 | _GLIBCXX20_CONSTEXPR |

1306 | reference |

1307 | #else |

1308 | void |

1309 | #endif |

1310 | emplace_back(_Args&&... __args); |

1311 | #endif |

1312 | |

1313 | /** |

1314 | * @brief Removes last element. |

1315 | * |

1316 | * This is a typical stack operation. It shrinks the %vector by one. |

1317 | * |

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

1319 | * data is needed, it should be retrieved before pop_back() is |

1320 | * called. |

1321 | */ |

1322 | _GLIBCXX20_CONSTEXPR |

1323 | void |

1324 | pop_back() _GLIBCXX_NOEXCEPT |

1325 | { |

1326 | __glibcxx_requires_nonempty(); |

1327 | --this->_M_impl._M_finish; |

1328 | _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); |

1329 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); |

1330 | } |

1331 | |

1332 | #if __cplusplus >= 201103L |

1333 | /** |

1334 | * @brief Inserts an object in %vector before specified iterator. |

1335 | * @param __position A const_iterator into the %vector. |

1336 | * @param __args Arguments. |

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

1338 | * |

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

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

1341 | * Note that this kind of operation could be expensive for a %vector |

1342 | * and if it is frequently used the user should consider using |

1343 | * std::list. |

1344 | */ |

1345 | template<typename... _Args> |

1346 | _GLIBCXX20_CONSTEXPR |

1347 | iterator |

1348 | emplace(const_iterator __position, _Args&&... __args) |

1349 | { return _M_emplace_aux(__position, std::forward<_Args>(__args)...); } |

1350 | |

1351 | /** |

1352 | * @brief Inserts given value into %vector before specified iterator. |

1353 | * @param __position A const_iterator into the %vector. |

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

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

1356 | * |

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

1358 | * the specified location. Note that this kind of operation |

1359 | * could be expensive for a %vector and if it is frequently |

1360 | * used the user should consider using std::list. |

1361 | */ |

1362 | _GLIBCXX20_CONSTEXPR |

1363 | iterator |

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

1365 | #else |

1366 | /** |

1367 | * @brief Inserts given value into %vector before specified iterator. |

1368 | * @param __position An iterator into the %vector. |

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

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

1371 | * |

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

1373 | * the specified location. Note that this kind of operation |

1374 | * could be expensive for a %vector and if it is frequently |

1375 | * used the user should consider using std::list. |

1376 | */ |

1377 | iterator |

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

1379 | #endif |

1380 | |

1381 | #if __cplusplus >= 201103L |

1382 | /** |

1383 | * @brief Inserts given rvalue into %vector before specified iterator. |

1384 | * @param __position A const_iterator into the %vector. |

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

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

1387 | * |

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

1389 | * the specified location. Note that this kind of operation |

1390 | * could be expensive for a %vector and if it is frequently |

1391 | * used the user should consider using std::list. |

1392 | */ |

1393 | _GLIBCXX20_CONSTEXPR |

1394 | iterator |

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

1396 | { return _M_insert_rval(__position, v: std::move(__x)); } |

1397 | |

1398 | /** |

1399 | * @brief Inserts an initializer_list into the %vector. |

1400 | * @param __position An iterator into the %vector. |

1401 | * @param __l An initializer_list. |

1402 | * |

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

1404 | * initializer_list @a l into the %vector before the location |

1405 | * specified by @a position. |

1406 | * |

1407 | * Note that this kind of operation could be expensive for a |

1408 | * %vector and if it is frequently used the user should |

1409 | * consider using std::list. |

1410 | */ |

1411 | _GLIBCXX20_CONSTEXPR |

1412 | iterator |

1413 | insert(const_iterator __position, initializer_list<value_type> __l) |

1414 | { |

1415 | auto __offset = __position - cbegin(); |

1416 | _M_range_insert(begin() + __offset, __l.begin(), __l.end(), |

1417 | std::random_access_iterator_tag()); |

1418 | return begin() + __offset; |

1419 | } |

1420 | #endif |

1421 | |

1422 | #if __cplusplus >= 201103L |

1423 | /** |

1424 | * @brief Inserts a number of copies of given data into the %vector. |

1425 | * @param __position A const_iterator into the %vector. |

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

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

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

1429 | * |

1430 | * This function will insert a specified number of copies of |

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

1432 | * |

1433 | * Note that this kind of operation could be expensive for a |

1434 | * %vector and if it is frequently used the user should |

1435 | * consider using std::list. |

1436 | */ |

1437 | _GLIBCXX20_CONSTEXPR |

1438 | iterator |

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

1440 | { |

1441 | difference_type __offset = __position - cbegin(); |

1442 | _M_fill_insert(pos: begin() + __offset, __n, __x); |

1443 | return begin() + __offset; |

1444 | } |

1445 | #else |

1446 | /** |

1447 | * @brief Inserts a number of copies of given data into the %vector. |

1448 | * @param __position An iterator into the %vector. |

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

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

1451 | * |

1452 | * This function will insert a specified number of copies of |

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

1454 | * |

1455 | * Note that this kind of operation could be expensive for a |

1456 | * %vector and if it is frequently used the user should |

1457 | * consider using std::list. |

1458 | */ |

1459 | void |

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

1461 | { _M_fill_insert(__position, __n, __x); } |

1462 | #endif |

1463 | |

1464 | #if __cplusplus >= 201103L |

1465 | /** |

1466 | * @brief Inserts a range into the %vector. |

1467 | * @param __position A const_iterator into the %vector. |

1468 | * @param __first An input iterator. |

1469 | * @param __last An input iterator. |

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

1471 | * |

1472 | * This function will insert copies of the data in the range |

1473 | * [__first,__last) into the %vector before the location specified |

1474 | * by @a pos. |

1475 | * |

1476 | * Note that this kind of operation could be expensive for a |

1477 | * %vector and if it is frequently used the user should |

1478 | * consider using std::list. |

1479 | */ |

1480 | template<typename _InputIterator, |

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

1482 | _GLIBCXX20_CONSTEXPR |

1483 | iterator |

1484 | insert(const_iterator __position, _InputIterator __first, |

1485 | _InputIterator __last) |

1486 | { |

1487 | difference_type __offset = __position - cbegin(); |

1488 | _M_range_insert(begin() + __offset, __first, __last, |

1489 | std::__iterator_category(__first)); |

1490 | return begin() + __offset; |

1491 | } |

1492 | #else |

1493 | /** |

1494 | * @brief Inserts a range into the %vector. |

1495 | * @param __position An iterator into the %vector. |

1496 | * @param __first An input iterator. |

1497 | * @param __last An input iterator. |

1498 | * |

1499 | * This function will insert copies of the data in the range |

1500 | * [__first,__last) into the %vector before the location specified |

1501 | * by @a pos. |

1502 | * |

1503 | * Note that this kind of operation could be expensive for a |

1504 | * %vector and if it is frequently used the user should |

1505 | * consider using std::list. |

1506 | */ |

1507 | template<typename _InputIterator> |

1508 | void |

1509 | insert(iterator __position, _InputIterator __first, |

1510 | _InputIterator __last) |

1511 | { |

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

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

1514 | _M_insert_dispatch(__position, __first, __last, _Integral()); |

1515 | } |

1516 | #endif |

1517 | |

1518 | /** |

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

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

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

1522 | * |

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

1524 | * shorten the %vector by one. |

1525 | * |

1526 | * Note This operation could be expensive and if it is |

1527 | * frequently used the user should consider using std::list. |

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

1529 | * the element, and that if the element is itself a pointer, |

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

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

1532 | */ |

1533 | _GLIBCXX20_CONSTEXPR |

1534 | iterator |

1535 | #if __cplusplus >= 201103L |

1536 | erase(const_iterator __position) |

1537 | { return _M_erase(begin() + (__position - cbegin())); } |

1538 | #else |

1539 | erase(iterator __position) |

1540 | { return _M_erase(__position); } |

1541 | #endif |

1542 | |

1543 | /** |

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

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

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

1547 | * erased. |

1548 | * @return An iterator pointing to the element pointed to by @a __last |

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

1550 | * |

1551 | * This function will erase the elements in the range |

1552 | * [__first,__last) and shorten the %vector accordingly. |

1553 | * |

1554 | * Note This operation could be expensive and if it is |

1555 | * frequently used the user should consider using std::list. |

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

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

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

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

1560 | */ |

1561 | _GLIBCXX20_CONSTEXPR |

1562 | iterator |

1563 | #if __cplusplus >= 201103L |

1564 | erase(const_iterator __first, const_iterator __last) |

1565 | { |

1566 | const auto __beg = begin(); |

1567 | const auto __cbeg = cbegin(); |

1568 | return _M_erase(__beg + (__first - __cbeg), __beg + (__last - __cbeg)); |

1569 | } |

1570 | #else |

1571 | erase(iterator __first, iterator __last) |

1572 | { return _M_erase(__first, __last); } |

1573 | #endif |

1574 | |

1575 | /** |

1576 | * @brief Swaps data with another %vector. |

1577 | * @param __x A %vector of the same element and allocator types. |

1578 | * |

1579 | * This exchanges the elements between two vectors in constant time. |

1580 | * (Three pointers, so it should be quite fast.) |

1581 | * Note that the global std::swap() function is specialized such that |

1582 | * std::swap(v1,v2) will feed to this function. |

1583 | * |

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

1585 | */ |

1586 | _GLIBCXX20_CONSTEXPR |

1587 | void |

1588 | swap(vector& __x) _GLIBCXX_NOEXCEPT |

1589 | { |

1590 | #if __cplusplus >= 201103L |

1591 | __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value |

1592 | || _M_get_Tp_allocator() == __x._M_get_Tp_allocator()); |

1593 | #endif |

1594 | this->_M_impl._M_swap_data(__x._M_impl); |

1595 | _Alloc_traits::_S_on_swap(_M_get_Tp_allocator(), |

1596 | __x._M_get_Tp_allocator()); |

1597 | } |

1598 | |

1599 | /** |

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

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

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

1603 | * the user's responsibility. |

1604 | */ |

1605 | _GLIBCXX20_CONSTEXPR |

1606 | void |

1607 | clear() _GLIBCXX_NOEXCEPT |

1608 | { _M_erase_at_end(pos: this->_M_impl._M_start); } |

1609 | |

1610 | protected: |

1611 | /** |

1612 | * Memory expansion handler. Uses the member allocation function to |

1613 | * obtain @a n bytes of memory, and then copies [first,last) into it. |

1614 | */ |

1615 | template<typename _ForwardIterator> |

1616 | _GLIBCXX20_CONSTEXPR |

1617 | pointer |

1618 | _M_allocate_and_copy(size_type __n, |

1619 | _ForwardIterator __first, _ForwardIterator __last) |

1620 | { |

1621 | pointer __result = this->_M_allocate(__n); |

1622 | __try |

1623 | { |

1624 | std::__uninitialized_copy_a(__first, __last, __result, |

1625 | _M_get_Tp_allocator()); |

1626 | return __result; |

1627 | } |

1628 | __catch(...) |

1629 | { |

1630 | _M_deallocate(__result, __n); |

1631 | __throw_exception_again; |

1632 | } |

1633 | } |

1634 | |

1635 | |

1636 | // Internal constructor functions follow. |

1637 | |

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

1639 | |

1640 | #if __cplusplus < 201103L |

1641 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1643 | template<typename _Integer> |

1644 | void |

1645 | _M_initialize_dispatch(_Integer __n, _Integer __value, __true_type) |

1646 | { |

1647 | this->_M_impl._M_start = _M_allocate(_S_check_init_len( |

1648 | static_cast<size_type>(__n), _M_get_Tp_allocator())); |

1649 | this->_M_impl._M_end_of_storage = |

1650 | this->_M_impl._M_start + static_cast<size_type>(__n); |

1651 | _M_fill_initialize(static_cast<size_type>(__n), __value); |

1652 | } |

1653 | |

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

1655 | template<typename _InputIterator> |

1656 | void |

1657 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |

1658 | __false_type) |

1659 | { |

1660 | _M_range_initialize(__first, __last, |

1661 | std::__iterator_category(__first)); |

1662 | } |

1663 | #endif |

1664 | |

1665 | // Called by the second initialize_dispatch above |

1666 | template<typename _InputIterator> |

1667 | _GLIBCXX20_CONSTEXPR |

1668 | void |

1669 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |

1670 | std::input_iterator_tag) |

1671 | { |

1672 | __try { |

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

1674 | #if __cplusplus >= 201103L |

1675 | emplace_back(*__first); |

1676 | #else |

1677 | push_back(*__first); |

1678 | #endif |

1679 | } __catch(...) { |

1680 | clear(); |

1681 | __throw_exception_again; |

1682 | } |

1683 | } |

1684 | |

1685 | // Called by the second initialize_dispatch above |

1686 | template<typename _ForwardIterator> |

1687 | _GLIBCXX20_CONSTEXPR |

1688 | void |

1689 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |

1690 | std::forward_iterator_tag) |

1691 | { |

1692 | const size_type __n = std::distance(__first, __last); |

1693 | this->_M_impl._M_start |

1694 | = this->_M_allocate(_S_check_init_len(__n, a: _M_get_Tp_allocator())); |

1695 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; |

1696 | this->_M_impl._M_finish = |

1697 | std::__uninitialized_copy_a(__first, __last, |

1698 | this->_M_impl._M_start, |

1699 | _M_get_Tp_allocator()); |

1700 | } |

1701 | |

1702 | // Called by the first initialize_dispatch above and by the |

1703 | // vector(n,value,a) constructor. |

1704 | _GLIBCXX20_CONSTEXPR |

1705 | void |

1706 | _M_fill_initialize(size_type __n, const value_type& __value) |

1707 | { |

1708 | this->_M_impl._M_finish = |

1709 | std::__uninitialized_fill_n_a(this->_M_impl._M_start, __n, __value, |

1710 | _M_get_Tp_allocator()); |

1711 | } |

1712 | |

1713 | #if __cplusplus >= 201103L |

1714 | // Called by the vector(n) constructor. |

1715 | _GLIBCXX20_CONSTEXPR |

1716 | void |

1717 | _M_default_initialize(size_type __n) |

1718 | { |

1719 | this->_M_impl._M_finish = |

1720 | std::__uninitialized_default_n_a(this->_M_impl._M_start, __n, |

1721 | _M_get_Tp_allocator()); |

1722 | } |

1723 | #endif |

1724 | |

1725 | // Internal assign functions follow. The *_aux functions do the actual |

1726 | // assignment work for the range versions. |

1727 | |

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

1729 | |

1730 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1732 | template<typename _Integer> |

1733 | _GLIBCXX20_CONSTEXPR |

1734 | void |

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

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

1737 | |

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

1739 | template<typename _InputIterator> |

1740 | _GLIBCXX20_CONSTEXPR |

1741 | void |

1742 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |

1743 | __false_type) |

1744 | { _M_assign_aux(__first, __last, std::__iterator_category(__first)); } |

1745 | |

1746 | // Called by the second assign_dispatch above |

1747 | template<typename _InputIterator> |

1748 | _GLIBCXX20_CONSTEXPR |

1749 | void |

1750 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |

1751 | std::input_iterator_tag); |

1752 | |

1753 | // Called by the second assign_dispatch above |

1754 | template<typename _ForwardIterator> |

1755 | _GLIBCXX20_CONSTEXPR |

1756 | void |

1757 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |

1758 | std::forward_iterator_tag); |

1759 | |

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

1761 | // to be the same thing. |

1762 | _GLIBCXX20_CONSTEXPR |

1763 | void |

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

1765 | |

1766 | // Internal insert functions follow. |

1767 | |

1768 | // Called by the range insert to implement [23.1.1]/9 |

1769 | |

1770 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1772 | template<typename _Integer> |

1773 | _GLIBCXX20_CONSTEXPR |

1774 | void |

1775 | _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __val, |

1776 | __true_type) |

1777 | { _M_fill_insert(__pos, __n, x: __val); } |

1778 | |

1779 | // Called by the range insert to implement [23.1.1]/9 |

1780 | template<typename _InputIterator> |

1781 | _GLIBCXX20_CONSTEXPR |

1782 | void |

1783 | _M_insert_dispatch(iterator __pos, _InputIterator __first, |

1784 | _InputIterator __last, __false_type) |

1785 | { |

1786 | _M_range_insert(__pos, __first, __last, |

1787 | std::__iterator_category(__first)); |

1788 | } |

1789 | |

1790 | // Called by the second insert_dispatch above |

1791 | template<typename _InputIterator> |

1792 | _GLIBCXX20_CONSTEXPR |

1793 | void |

1794 | _M_range_insert(iterator __pos, _InputIterator __first, |

1795 | _InputIterator __last, std::input_iterator_tag); |

1796 | |

1797 | // Called by the second insert_dispatch above |

1798 | template<typename _ForwardIterator> |

1799 | _GLIBCXX20_CONSTEXPR |

1800 | void |

1801 | _M_range_insert(iterator __pos, _ForwardIterator __first, |

1802 | _ForwardIterator __last, std::forward_iterator_tag); |

1803 | |

1804 | // Called by insert(p,n,x), and the range insert when it turns out to be |

1805 | // the same thing. |

1806 | _GLIBCXX20_CONSTEXPR |

1807 | void |

1808 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x); |

1809 | |

1810 | #if __cplusplus >= 201103L |

1811 | // Called by resize(n). |

1812 | _GLIBCXX20_CONSTEXPR |

1813 | void |

1814 | _M_default_append(size_type __n); |

1815 | |

1816 | _GLIBCXX20_CONSTEXPR |

1817 | bool |

1818 | _M_shrink_to_fit(); |

1819 | #endif |

1820 | |

1821 | #if __cplusplus < 201103L |

1822 | // Called by insert(p,x) |

1823 | void |

1824 | _M_insert_aux(iterator __position, const value_type& __x); |

1825 | |

1826 | void |

1827 | _M_realloc_insert(iterator __position, const value_type& __x); |

1828 | |

1829 | void |

1830 | _M_realloc_append(const value_type& __x); |

1831 | #else |

1832 | // A value_type object constructed with _Alloc_traits::construct() |

1833 | // and destroyed with _Alloc_traits::destroy(). |

1834 | struct _Temporary_value |

1835 | { |

1836 | template<typename... _Args> |

1837 | _GLIBCXX20_CONSTEXPR explicit |

1838 | _Temporary_value(vector* __vec, _Args&&... __args) : _M_this(__vec) |

1839 | { |

1840 | _Alloc_traits::construct(_M_this->_M_impl, _M_ptr(), |

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

1842 | } |

1843 | |

1844 | _GLIBCXX20_CONSTEXPR |

1845 | ~_Temporary_value() |

1846 | { _Alloc_traits::destroy(_M_this->_M_impl, _M_ptr()); } |

1847 | |

1848 | _GLIBCXX20_CONSTEXPR value_type& |

1849 | _M_val() noexcept { return _M_storage._M_val; } |

1850 | |

1851 | private: |

1852 | _GLIBCXX20_CONSTEXPR _Tp* |

1853 | _M_ptr() noexcept { return std::__addressof(_M_storage._M_val); } |

1854 | |

1855 | union _Storage |

1856 | { |

1857 | constexpr _Storage() : _M_byte() { } |

1858 | _GLIBCXX20_CONSTEXPR ~_Storage() { } |

1859 | _Storage& operator=(const _Storage&) = delete; |

1860 | unsigned char _M_byte; |

1861 | _Tp _M_val; |

1862 | }; |

1863 | |

1864 | vector* _M_this; |

1865 | _Storage _M_storage; |

1866 | }; |

1867 | |

1868 | // Called by insert(p,x) and other functions when insertion needs to |

1869 | // reallocate or move existing elements. _Arg is either _Tp& or _Tp. |

1870 | template<typename _Arg> |

1871 | _GLIBCXX20_CONSTEXPR |

1872 | void |

1873 | _M_insert_aux(iterator __position, _Arg&& __arg); |

1874 | |

1875 | template<typename... _Args> |

1876 | _GLIBCXX20_CONSTEXPR |

1877 | void |

1878 | _M_realloc_insert(iterator __position, _Args&&... __args); |

1879 | |

1880 | template<typename... _Args> |

1881 | _GLIBCXX20_CONSTEXPR |

1882 | void |

1883 | _M_realloc_append(_Args&&... __args); |

1884 | |

1885 | // Either move-construct at the end, or forward to _M_insert_aux. |

1886 | _GLIBCXX20_CONSTEXPR |

1887 | iterator |

1888 | _M_insert_rval(const_iterator __position, value_type&& __v); |

1889 | |

1890 | // Try to emplace at the end, otherwise forward to _M_insert_aux. |

1891 | template<typename... _Args> |

1892 | _GLIBCXX20_CONSTEXPR |

1893 | iterator |

1894 | _M_emplace_aux(const_iterator __position, _Args&&... __args); |

1895 | |

1896 | // Emplacing an rvalue of the correct type can use _M_insert_rval. |

1897 | _GLIBCXX20_CONSTEXPR |

1898 | iterator |

1899 | _M_emplace_aux(const_iterator __position, value_type&& __v) |

1900 | { return _M_insert_rval(__position, v: std::move(__v)); } |

1901 | #endif |

1902 | |

1903 | // Called by _M_fill_insert, _M_insert_aux etc. |

1904 | _GLIBCXX20_CONSTEXPR |

1905 | size_type |

1906 | _M_check_len(size_type __n, const char* __s) const |

1907 | { |

1908 | if (max_size() - size() < __n) |

1909 | __throw_length_error(__N(__s)); |

1910 | |

1911 | const size_type __len = size() + (std::max)(size(), __n); |

1912 | return (__len < size() || __len > max_size()) ? max_size() : __len; |

1913 | } |

1914 | |

1915 | // Called by constructors to check initial size. |

1916 | static _GLIBCXX20_CONSTEXPR size_type |

1917 | _S_check_init_len(size_type __n, const allocator_type& __a) |

1918 | { |

1919 | if (__n > _S_max_size(a: _Tp_alloc_type(__a))) |

1920 | __throw_length_error( |

1921 | __N("cannot create std::vector larger than max_size()")); |

1922 | return __n; |

1923 | } |

1924 | |

1925 | static _GLIBCXX20_CONSTEXPR size_type |

1926 | _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT |

1927 | { |

1928 | // std::distance(begin(), end()) cannot be greater than PTRDIFF_MAX, |

1929 | // and realistically we can't store more than PTRDIFF_MAX/sizeof(T) |

1930 | // (even if std::allocator_traits::max_size says we can). |

1931 | const size_t __diffmax |

1932 | = __gnu_cxx::__numeric_traits<ptrdiff_t>::__max / sizeof(_Tp); |

1933 | const size_t __allocmax = _Alloc_traits::max_size(__a); |

1934 | return (std::min)(a: __diffmax, b: __allocmax); |

1935 | } |

1936 | |

1937 | // Internal erase functions follow. |

1938 | |

1939 | // Called by erase(q1,q2), clear(), resize(), _M_fill_assign, |

1940 | // _M_assign_aux. |

1941 | _GLIBCXX20_CONSTEXPR |

1942 | void |

1943 | _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT |

1944 | { |

1945 | if (size_type __n = this->_M_impl._M_finish - __pos) |

1946 | { |

1947 | std::_Destroy(__pos, this->_M_impl._M_finish, |

1948 | _M_get_Tp_allocator()); |

1949 | this->_M_impl._M_finish = __pos; |

1950 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n); |

1951 | } |

1952 | } |

1953 | |

1954 | _GLIBCXX20_CONSTEXPR |

1955 | iterator |

1956 | _M_erase(iterator __position); |

1957 | |

1958 | _GLIBCXX20_CONSTEXPR |

1959 | iterator |

1960 | _M_erase(iterator __first, iterator __last); |

1961 | |

1962 | #if __cplusplus >= 201103L |

1963 | private: |

1964 | // Constant-time move assignment when source object's memory can be |

1965 | // moved, either because the source's allocator will move too |

1966 | // or because the allocators are equal. |

1967 | _GLIBCXX20_CONSTEXPR |

1968 | void |

1969 | _M_move_assign(vector&& __x, true_type) noexcept |

1970 | { |

1971 | vector __tmp(get_allocator()); |

1972 | this->_M_impl._M_swap_data(__x._M_impl); |

1973 | __tmp._M_impl._M_swap_data(__x._M_impl); |

1974 | std::__alloc_on_move(_M_get_Tp_allocator(), __x._M_get_Tp_allocator()); |

1975 | } |

1976 | |

1977 | // Do move assignment when it might not be possible to move source |

1978 | // object's memory, resulting in a linear-time operation. |

1979 | _GLIBCXX20_CONSTEXPR |

1980 | void |

1981 | _M_move_assign(vector&& __x, false_type) |

1982 | { |

1983 | if (__x._M_get_Tp_allocator() == this->_M_get_Tp_allocator()) |

1984 | _M_move_assign(std::move(__x), true_type()); |

1985 | else |

1986 | { |

1987 | // The rvalue's allocator cannot be moved and is not equal, |

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

1989 | this->_M_assign_aux(std::make_move_iterator(__x.begin()), |

1990 | std::make_move_iterator(__x.end()), |

1991 | std::random_access_iterator_tag()); |

1992 | __x.clear(); |

1993 | } |

1994 | } |

1995 | #endif |

1996 | |

1997 | template<typename _Up> |

1998 | _GLIBCXX20_CONSTEXPR |

1999 | _Up* |

2000 | _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT |

2001 | { return __ptr; } |

2002 | |

2003 | #if __cplusplus >= 201103L |

2004 | template<typename _Ptr> |

2005 | _GLIBCXX20_CONSTEXPR |

2006 | typename std::pointer_traits<_Ptr>::element_type* |

2007 | _M_data_ptr(_Ptr __ptr) const |

2008 | { return empty() ? nullptr : std::__to_address(__ptr); } |

2009 | #else |

2010 | template<typename _Up> |

2011 | _Up* |

2012 | _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT |

2013 | { return __ptr; } |

2014 | |

2015 | template<typename _Ptr> |

2016 | value_type* |

2017 | _M_data_ptr(_Ptr __ptr) |

2018 | { return empty() ? (value_type*)0 : __ptr.operator->(); } |

2019 | |

2020 | template<typename _Ptr> |

2021 | const value_type* |

2022 | _M_data_ptr(_Ptr __ptr) const |

2023 | { return empty() ? (const value_type*)0 : __ptr.operator->(); } |

2024 | #endif |

2025 | }; |

2026 | |

2027 | #if __cpp_deduction_guides >= 201606 |

2028 | template<typename _InputIterator, typename _ValT |

2029 | = typename iterator_traits<_InputIterator>::value_type, |

2030 | typename _Allocator = allocator<_ValT>, |

2031 | typename = _RequireInputIter<_InputIterator>, |

2032 | typename = _RequireAllocator<_Allocator>> |

2033 | vector(_InputIterator, _InputIterator, _Allocator = _Allocator()) |

2034 | -> vector<_ValT, _Allocator>; |

2035 | #endif |

2036 | |

2037 | /** |

2038 | * @brief Vector equality comparison. |

2039 | * @param __x A %vector. |

2040 | * @param __y A %vector of the same type as @a __x. |

2041 | * @return True iff the size and elements of the vectors are equal. |

2042 | * |

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

2044 | * vectors. Vectors are considered equivalent if their sizes are equal, |

2045 | * and if corresponding elements compare equal. |

2046 | */ |

2047 | template<typename _Tp, typename _Alloc> |

2048 | _GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR |

2049 | inline bool |

2050 | operator==(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

2051 | { return (__x.size() == __y.size() |

2052 | && std::equal(__x.begin(), __x.end(), __y.begin())); } |

2053 | |

2054 | #if __cpp_lib_three_way_comparison |

2055 | /** |

2056 | * @brief Vector ordering relation. |

2057 | * @param __x A `vector`. |

2058 | * @param __y A `vector` of the same type as `__x`. |

2059 | * @return A value indicating whether `__x` is less than, equal to, |

2060 | * greater than, or incomparable with `__y`. |

2061 | * |

2062 | * See `std::lexicographical_compare_three_way()` for how the determination |

2063 | * is made. This operator is used to synthesize relational operators like |

2064 | * `<` and `>=` etc. |

2065 | */ |

2066 | template<typename _Tp, typename _Alloc> |

2067 | [[nodiscard]] _GLIBCXX20_CONSTEXPR |

2068 | inline __detail::__synth3way_t<_Tp> |

2069 | operator<=>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

2070 | { |

2071 | return std::lexicographical_compare_three_way(__x.begin(), __x.end(), |

2072 | __y.begin(), __y.end(), |

2073 | __detail::__synth3way); |

2074 | } |

2075 | #else |

2076 | /** |

2077 | * @brief Vector ordering relation. |

2078 | * @param __x A %vector. |

2079 | * @param __y A %vector of the same type as @a __x. |

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

2081 | * |

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

2083 | * vectors. The elements must be comparable with @c <. |

2084 | * |

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

2086 | */ |

2087 | template<typename _Tp, typename _Alloc> |

2088 | _GLIBCXX_NODISCARD inline bool |

2089 | operator<(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

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

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

2092 | |

2093 | /// Based on operator== |

2094 | template<typename _Tp, typename _Alloc> |

2095 | _GLIBCXX_NODISCARD inline bool |

2096 | operator!=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

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

2098 | |

2099 | /// Based on operator< |

2100 | template<typename _Tp, typename _Alloc> |

2101 | _GLIBCXX_NODISCARD inline bool |

2102 | operator>(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

2103 | { return __y < __x; } |

2104 | |

2105 | /// Based on operator< |

2106 | template<typename _Tp, typename _Alloc> |

2107 | _GLIBCXX_NODISCARD inline bool |

2108 | operator<=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

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

2110 | |

2111 | /// Based on operator< |

2112 | template<typename _Tp, typename _Alloc> |

2113 | _GLIBCXX_NODISCARD inline bool |

2114 | operator>=(const vector<_Tp, _Alloc>& __x, const vector<_Tp, _Alloc>& __y) |

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

2116 | #endif // three-way comparison |

2117 | |

2118 | /// See std::vector::swap(). |

2119 | template<typename _Tp, typename _Alloc> |

2120 | _GLIBCXX20_CONSTEXPR |

2121 | inline void |

2122 | swap(vector<_Tp, _Alloc>& __x, vector<_Tp, _Alloc>& __y) |

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

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

2125 | |

2126 | _GLIBCXX_END_NAMESPACE_CONTAINER |

2127 | |

2128 | #if __cplusplus >= 201703L |

2129 | namespace __detail::__variant |

2130 | { |

2131 | template<typename> struct _Never_valueless_alt; // see <variant> |

2132 | |

2133 | // Provide the strong exception-safety guarantee when emplacing a |

2134 | // vector into a variant, but only if move assignment cannot throw. |

2135 | template<typename _Tp, typename _Alloc> |

2136 | struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> |

2137 | : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> |

2138 | { }; |

2139 | } // namespace __detail::__variant |

2140 | #endif // C++17 |

2141 | |

2142 | _GLIBCXX_END_NAMESPACE_VERSION |

2143 | } // namespace std |

2144 | |

2145 | #endif /* _STL_VECTOR_H */ |

2146 |