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

2 | |

3 | // Copyright (C) 2001-2021 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 > 201703L |

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 | _Vector_impl_data() _GLIBCXX_NOEXCEPT |

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

99 | { } |

100 | |

101 | #if __cplusplus >= 201103L |

102 | _Vector_impl_data(_Vector_impl_data&& __x) noexcept |

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

104 | _M_end_of_storage(__x._M_end_of_storage) |

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

106 | #endif |

107 | |

108 | void |

109 | _M_copy_data(_Vector_impl_data const& __x) _GLIBCXX_NOEXCEPT |

110 | { |

111 | _M_start = __x._M_start; |

112 | _M_finish = __x._M_finish; |

113 | _M_end_of_storage = __x._M_end_of_storage; |

114 | } |

115 | |

116 | void |

117 | _M_swap_data(_Vector_impl_data& __x) _GLIBCXX_NOEXCEPT |

118 | { |

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

120 | // information used by TBAA. |

121 | _Vector_impl_data __tmp; |

122 | __tmp._M_copy_data(*this); |

123 | _M_copy_data(__x); |

124 | __x._M_copy_data(__tmp); |

125 | } |

126 | }; |

127 | |

128 | struct _Vector_impl |

129 | : public _Tp_alloc_type, public _Vector_impl_data |

130 | { |

131 | _Vector_impl() _GLIBCXX_NOEXCEPT_IF( |

132 | is_nothrow_default_constructible<_Tp_alloc_type>::value) |

133 | : _Tp_alloc_type() |

134 | { } |

135 | |

136 | _Vector_impl(_Tp_alloc_type const& __a) _GLIBCXX_NOEXCEPT |

137 | : _Tp_alloc_type(__a) |

138 | { } |

139 | |

140 | #if __cplusplus >= 201103L |

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

142 | // !is_nothrow_move_constructible<_Tp_alloc_type>. |

143 | _Vector_impl(_Vector_impl&& __x) noexcept |

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

145 | { } |

146 | |

147 | _Vector_impl(_Tp_alloc_type&& __a) noexcept |

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

149 | { } |

150 | |

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

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

153 | { } |

154 | #endif |

155 | |

156 | #if _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |

157 | template<typename = _Tp_alloc_type> |

158 | struct _Asan |

159 | { |

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

161 | ::size_type size_type; |

162 | |

163 | static void _S_shrink(_Vector_impl&, size_type) { } |

164 | static void _S_on_dealloc(_Vector_impl&) { } |

165 | |

166 | typedef _Vector_impl& _Reinit; |

167 | |

168 | struct _Grow |

169 | { |

170 | _Grow(_Vector_impl&, size_type) { } |

171 | void _M_grew(size_type) { } |

172 | }; |

173 | }; |

174 | |

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

176 | template<typename _Up> |

177 | struct _Asan<allocator<_Up> > |

178 | { |

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

180 | ::size_type size_type; |

181 | |

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

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

184 | static void |

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

186 | { |

187 | __sanitizer_annotate_contiguous_container(__impl._M_start, |

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

189 | } |

190 | |

191 | static void |

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

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

194 | |

195 | static void |

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

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

198 | |

199 | static void |

200 | _S_on_dealloc(_Vector_impl& __impl) |

201 | { |

202 | if (__impl._M_start) |

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

204 | } |

205 | |

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

207 | struct _Reinit |

208 | { |

209 | explicit _Reinit(_Vector_impl& __impl) : _M_impl(__impl) |

210 | { |

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

212 | _S_on_dealloc(_M_impl); |

213 | } |

214 | |

215 | ~_Reinit() |

216 | { |

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

218 | if (_M_impl._M_start) |

219 | _S_adjust(_M_impl, _M_impl._M_end_of_storage, |

220 | _M_impl._M_finish); |

221 | } |

222 | |

223 | _Vector_impl& _M_impl; |

224 | |

225 | #if __cplusplus >= 201103L |

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

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

228 | #endif |

229 | }; |

230 | |

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

232 | struct _Grow |

233 | { |

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

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

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

237 | |

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

239 | |

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

241 | |

242 | #if __cplusplus >= 201103L |

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

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

245 | #endif |

246 | private: |

247 | _Vector_impl& _M_impl; |

248 | size_type _M_n; |

249 | }; |

250 | }; |

251 | |

252 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT \ |

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

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

255 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) \ |

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

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

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

259 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) \ |

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

261 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC \ |

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

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

264 | #define _GLIBCXX_ASAN_ANNOTATE_REINIT |

265 | #define _GLIBCXX_ASAN_ANNOTATE_GROW(n) |

266 | #define _GLIBCXX_ASAN_ANNOTATE_GREW(n) |

267 | #define _GLIBCXX_ASAN_ANNOTATE_SHRINK(n) |

268 | #define _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC |

269 | #endif // _GLIBCXX_SANITIZE_STD_ALLOCATOR && _GLIBCXX_SANITIZE_VECTOR |

270 | }; |

271 | |

272 | public: |

273 | typedef _Alloc allocator_type; |

274 | |

275 | _Tp_alloc_type& |

276 | _M_get_Tp_allocator() _GLIBCXX_NOEXCEPT |

277 | { return this->_M_impl; } |

278 | |

279 | const _Tp_alloc_type& |

280 | _M_get_Tp_allocator() const _GLIBCXX_NOEXCEPT |

281 | { return this->_M_impl; } |

282 | |

283 | allocator_type |

284 | get_allocator() const _GLIBCXX_NOEXCEPT |

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

286 | |

287 | #if __cplusplus >= 201103L |

288 | _Vector_base() = default; |

289 | #else |

290 | _Vector_base() { } |

291 | #endif |

292 | |

293 | _Vector_base(const allocator_type& __a) _GLIBCXX_NOEXCEPT |

294 | : _M_impl(__a) { } |

295 | |

296 | // Kept for ABI compatibility. |

297 | #if !_GLIBCXX_INLINE_VERSION |

298 | _Vector_base(size_t __n) |

299 | : _M_impl() |

300 | { _M_create_storage(__n); } |

301 | #endif |

302 | |

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

304 | : _M_impl(__a) |

305 | { _M_create_storage(__n); } |

306 | |

307 | #if __cplusplus >= 201103L |

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

309 | |

310 | // Kept for ABI compatibility. |

311 | # if !_GLIBCXX_INLINE_VERSION |

312 | _Vector_base(_Tp_alloc_type&& __a) noexcept |

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

314 | |

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

316 | : _M_impl(__a) |

317 | { |

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

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

320 | else |

321 | { |

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

323 | _M_create_storage(__n); |

324 | } |

325 | } |

326 | # endif |

327 | |

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

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

330 | { } |

331 | #endif |

332 | |

333 | ~_Vector_base() _GLIBCXX_NOEXCEPT |

334 | { |

335 | _M_deallocate(p: _M_impl._M_start, |

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

337 | } |

338 | |

339 | public: |

340 | _Vector_impl _M_impl; |

341 | |

342 | pointer |

343 | _M_allocate(size_t __n) |

344 | { |

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

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

347 | } |

348 | |

349 | void |

350 | _M_deallocate(pointer __p, size_t __n) |

351 | { |

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

353 | if (__p) |

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

355 | } |

356 | |

357 | protected: |

358 | void |

359 | _M_create_storage(size_t __n) |

360 | { |

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

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

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

364 | } |

365 | }; |

366 | |

367 | /** |

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

369 | * individual elements in any order. |

370 | * |

371 | * @ingroup sequences |

372 | * |

373 | * @tparam _Tp Type of element. |

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

375 | * |

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

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

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

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

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

381 | * |

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

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

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

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

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

387 | */ |

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

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

390 | { |

391 | #ifdef _GLIBCXX_CONCEPT_CHECKS |

392 | // Concept requirements. |

393 | typedef typename _Alloc::value_type _Alloc_value_type; |

394 | # if __cplusplus < 201103L |

395 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) |

396 | # endif |

397 | __glibcxx_class_requires2(_Tp, _Alloc_value_type, _SameTypeConcept) |

398 | #endif |

399 | |

400 | #if __cplusplus >= 201103L |

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

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

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

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

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

406 | # endif |

407 | #endif |

408 | |

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

410 | typedef typename _Base::_Tp_alloc_type _Tp_alloc_type; |

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

412 | |

413 | public: |

414 | typedef _Tp value_type; |

415 | typedef typename _Base::pointer pointer; |

416 | typedef typename _Alloc_traits::const_pointer const_pointer; |

417 | typedef typename _Alloc_traits::reference reference; |

418 | typedef typename _Alloc_traits::const_reference const_reference; |

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

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

421 | const_iterator; |

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

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

424 | typedef size_t size_type; |

425 | typedef ptrdiff_t difference_type; |

426 | typedef _Alloc allocator_type; |

427 | |

428 | private: |

429 | #if __cplusplus >= 201103L |

430 | static constexpr bool |

431 | _S_nothrow_relocate(true_type) |

432 | { |

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

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

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

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

437 | } |

438 | |

439 | static constexpr bool |

440 | _S_nothrow_relocate(false_type) |

441 | { return false; } |

442 | |

443 | static constexpr bool |

444 | _S_use_relocate() |

445 | { |

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

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

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

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

450 | } |

451 | |

452 | static pointer |

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

454 | _Tp_alloc_type& __alloc, true_type) noexcept |

455 | { |

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

457 | } |

458 | |

459 | static pointer |

460 | _S_do_relocate(pointer, pointer, pointer __result, |

461 | _Tp_alloc_type&, false_type) noexcept |

462 | { return __result; } |

463 | |

464 | static pointer |

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

466 | _Tp_alloc_type& __alloc) noexcept |

467 | { |

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

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

470 | } |

471 | #endif // C++11 |

472 | |

473 | protected: |

474 | using _Base::_M_allocate; |

475 | using _Base::_M_deallocate; |

476 | using _Base::_M_impl; |

477 | using _Base::_M_get_Tp_allocator; |

478 | |

479 | public: |

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

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

482 | |

483 | /** |

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

485 | */ |

486 | #if __cplusplus >= 201103L |

487 | vector() = default; |

488 | #else |

489 | vector() { } |

490 | #endif |

491 | |

492 | /** |

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

494 | * @param __a An allocator object. |

495 | */ |

496 | explicit |

497 | vector(const allocator_type& __a) _GLIBCXX_NOEXCEPT |

498 | : _Base(__a) { } |

499 | |

500 | #if __cplusplus >= 201103L |

501 | /** |

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

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

504 | * @param __a An allocator. |

505 | * |

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

507 | * constructed elements. |

508 | */ |

509 | explicit |

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

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

512 | { _M_default_initialize(__n); } |

513 | |

514 | /** |

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

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

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

518 | * @param __a An allocator. |

519 | * |

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

521 | */ |

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

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

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

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

526 | #else |

527 | /** |

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

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

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

531 | * @param __a An allocator. |

532 | * |

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

534 | */ |

535 | explicit |

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

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

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

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

540 | #endif |

541 | |

542 | /** |

543 | * @brief %Vector copy constructor. |

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

545 | * |

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

547 | * @a __x will not be copied |

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

549 | * |

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

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

552 | */ |

553 | vector(const vector& __x) |

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

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

556 | { |

557 | this->_M_impl._M_finish = |

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

559 | this->_M_impl._M_start, |

560 | _M_get_Tp_allocator()); |

561 | } |

562 | |

563 | #if __cplusplus >= 201103L |

564 | /** |

565 | * @brief %Vector move constructor. |

566 | * |

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

568 | * moved instance. |

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

570 | * %vector. |

571 | */ |

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

573 | |

574 | /// Copy constructor with alternative allocator |

575 | vector(const vector& __x, const allocator_type& __a) |

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

577 | { |

578 | this->_M_impl._M_finish = |

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

580 | this->_M_impl._M_start, |

581 | _M_get_Tp_allocator()); |

582 | } |

583 | |

584 | private: |

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

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

587 | { } |

588 | |

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

590 | : _Base(__m) |

591 | { |

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

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

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

595 | { |

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

597 | this->_M_impl._M_finish = |

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

599 | this->_M_impl._M_start, |

600 | _M_get_Tp_allocator()); |

601 | __rv.clear(); |

602 | } |

603 | } |

604 | |

605 | public: |

606 | /// Move constructor with alternative allocator |

607 | vector(vector&& __rv, const allocator_type& __m) |

608 | noexcept( noexcept( |

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

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

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

612 | { } |

613 | |

614 | /** |

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

616 | * @param __l An initializer_list. |

617 | * @param __a An allocator. |

618 | * |

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

620 | * initializer_list @a __l. |

621 | * |

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

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

624 | */ |

625 | vector(initializer_list<value_type> __l, |

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

627 | : _Base(__a) |

628 | { |

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

630 | random_access_iterator_tag()); |

631 | } |

632 | #endif |

633 | |

634 | /** |

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

636 | * @param __first An input iterator. |

637 | * @param __last An input iterator. |

638 | * @param __a An allocator. |

639 | * |

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

641 | * [first,last). |

642 | * |

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

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

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

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

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

648 | * constructor, and logN memory reallocations. |

649 | */ |

650 | #if __cplusplus >= 201103L |

651 | template<typename _InputIterator, |

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

653 | vector(_InputIterator __first, _InputIterator __last, |

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

655 | : _Base(__a) |

656 | { |

657 | _M_range_initialize(__first, __last, |

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

659 | } |

660 | #else |

661 | template<typename _InputIterator> |

662 | vector(_InputIterator __first, _InputIterator __last, |

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

664 | : _Base(__a) |

665 | { |

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

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

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

669 | } |

670 | #endif |

671 | |

672 | /** |

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

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

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

676 | * responsibility. |

677 | */ |

678 | ~vector() _GLIBCXX_NOEXCEPT |

679 | { |

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

681 | _M_get_Tp_allocator()); |

682 | _GLIBCXX_ASAN_ANNOTATE_BEFORE_DEALLOC; |

683 | } |

684 | |

685 | /** |

686 | * @brief %Vector assignment operator. |

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

688 | * |

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

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

691 | * |

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

693 | */ |

694 | vector& |

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

696 | |

697 | #if __cplusplus >= 201103L |

698 | /** |

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

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

701 | * |

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

703 | * if the allocators permit it). |

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

705 | * |

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

707 | */ |

708 | vector& |

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

710 | { |

711 | constexpr bool __move_storage = |

712 | _Alloc_traits::_S_propagate_on_move_assign() |

713 | || _Alloc_traits::_S_always_equal(); |

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

715 | return *this; |

716 | } |

717 | |

718 | /** |

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

720 | * @param __l An initializer_list. |

721 | * |

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

723 | * initializer list @a __l. |

724 | * |

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

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

727 | * of elements assigned. |

728 | */ |

729 | vector& |

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

731 | { |

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

733 | random_access_iterator_tag()); |

734 | return *this; |

735 | } |

736 | #endif |

737 | |

738 | /** |

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

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

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

742 | * |

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

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

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

746 | * the number of elements assigned. |

747 | */ |

748 | void |

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

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

751 | |

752 | /** |

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

754 | * @param __first An input iterator. |

755 | * @param __last An input iterator. |

756 | * |

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

758 | * range [__first,__last). |

759 | * |

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

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

762 | * of elements assigned. |

763 | */ |

764 | #if __cplusplus >= 201103L |

765 | template<typename _InputIterator, |

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

767 | void |

768 | assign(_InputIterator __first, _InputIterator __last) |

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

770 | #else |

771 | template<typename _InputIterator> |

772 | void |

773 | assign(_InputIterator __first, _InputIterator __last) |

774 | { |

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

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

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

778 | } |

779 | #endif |

780 | |

781 | #if __cplusplus >= 201103L |

782 | /** |

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

784 | * @param __l An initializer_list. |

785 | * |

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

787 | * initializer list @a __l. |

788 | * |

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

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

791 | * of elements assigned. |

792 | */ |

793 | void |

794 | assign(initializer_list<value_type> __l) |

795 | { |

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

797 | random_access_iterator_tag()); |

798 | } |

799 | #endif |

800 | |

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

802 | using _Base::get_allocator; |

803 | |

804 | // iterators |

805 | /** |

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

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

808 | * element order. |

809 | */ |

810 | iterator |

811 | begin() _GLIBCXX_NOEXCEPT |

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

813 | |

814 | /** |

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

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

817 | * element order. |

818 | */ |

819 | const_iterator |

820 | begin() const _GLIBCXX_NOEXCEPT |

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

822 | |

823 | /** |

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

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

826 | * element order. |

827 | */ |

828 | iterator |

829 | end() _GLIBCXX_NOEXCEPT |

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

831 | |

832 | /** |

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

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

835 | * ordinary element order. |

836 | */ |

837 | const_iterator |

838 | end() const _GLIBCXX_NOEXCEPT |

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

840 | |

841 | /** |

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

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

844 | * element order. |

845 | */ |

846 | reverse_iterator |

847 | rbegin() _GLIBCXX_NOEXCEPT |

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

849 | |

850 | /** |

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

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

853 | * reverse element order. |

854 | */ |

855 | const_reverse_iterator |

856 | rbegin() const _GLIBCXX_NOEXCEPT |

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

858 | |

859 | /** |

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

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

862 | * in reverse element order. |

863 | */ |

864 | reverse_iterator |

865 | rend() _GLIBCXX_NOEXCEPT |

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

867 | |

868 | /** |

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

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

871 | * is done in reverse element order. |

872 | */ |

873 | const_reverse_iterator |

874 | rend() const _GLIBCXX_NOEXCEPT |

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

876 | |

877 | #if __cplusplus >= 201103L |

878 | /** |

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

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

881 | * element order. |

882 | */ |

883 | const_iterator |

884 | cbegin() const noexcept |

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

886 | |

887 | /** |

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

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

890 | * ordinary element order. |

891 | */ |

892 | const_iterator |

893 | cend() const noexcept |

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

895 | |

896 | /** |

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

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

899 | * reverse element order. |

900 | */ |

901 | const_reverse_iterator |

902 | crbegin() const noexcept |

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

904 | |

905 | /** |

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

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

908 | * is done in reverse element order. |

909 | */ |

910 | const_reverse_iterator |

911 | crend() const noexcept |

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

913 | #endif |

914 | |

915 | // [23.2.4.2] capacity |

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

917 | size_type |

918 | size() const _GLIBCXX_NOEXCEPT |

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

920 | |

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

922 | size_type |

923 | max_size() const _GLIBCXX_NOEXCEPT |

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

925 | |

926 | #if __cplusplus >= 201103L |

927 | /** |

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

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

930 | * |

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

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

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

934 | * default constructed elements are appended. |

935 | */ |

936 | void |

937 | resize(size_type __new_size) |

938 | { |

939 | if (__new_size > size()) |

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

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

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

943 | } |

944 | |

945 | /** |

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

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

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

949 | * |

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

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

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

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

954 | * given data. |

955 | */ |

956 | void |

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

958 | { |

959 | if (__new_size > size()) |

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

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

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

963 | } |

964 | #else |

965 | /** |

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

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

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

969 | * |

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

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

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

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

974 | * given data. |

975 | */ |

976 | void |

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

978 | { |

979 | if (__new_size > size()) |

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

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

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

983 | } |

984 | #endif |

985 | |

986 | #if __cplusplus >= 201103L |

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

988 | void |

989 | shrink_to_fit() |

990 | { _M_shrink_to_fit(); } |

991 | #endif |

992 | |

993 | /** |

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

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

996 | */ |

997 | size_type |

998 | capacity() const _GLIBCXX_NOEXCEPT |

999 | { return size_type(this->_M_impl._M_end_of_storage |

1000 | - this->_M_impl._M_start); } |

1001 | |

1002 | /** |

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

1004 | * equal end().) |

1005 | */ |

1006 | _GLIBCXX_NODISCARD bool |

1007 | empty() const _GLIBCXX_NOEXCEPT |

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

1009 | |

1010 | /** |

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

1012 | * elements. |

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

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

1015 | * |

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

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

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

1019 | * thrown. |

1020 | * |

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

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

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

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

1025 | * and copying of %vector data. |

1026 | */ |

1027 | void |

1028 | reserve(size_type __n); |

1029 | |

1030 | // element access |

1031 | /** |

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

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

1034 | * accessed. |

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

1036 | * |

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

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

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

1040 | * see at().) |

1041 | */ |

1042 | reference |

1043 | operator[](size_type __n) _GLIBCXX_NOEXCEPT |

1044 | { |

1045 | __glibcxx_requires_subscript(__n); |

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

1047 | } |

1048 | |

1049 | /** |

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

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

1052 | * accessed. |

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

1054 | * |

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

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

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

1058 | * see at().) |

1059 | */ |

1060 | const_reference |

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

1062 | { |

1063 | __glibcxx_requires_subscript(__n); |

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

1065 | } |

1066 | |

1067 | protected: |

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

1069 | void |

1070 | _M_range_check(size_type __n) const |

1071 | { |

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

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

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

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

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

1077 | } |

1078 | |

1079 | public: |

1080 | /** |

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

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

1083 | * accessed. |

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

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

1086 | * |

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

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

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

1090 | */ |

1091 | reference |

1092 | at(size_type __n) |

1093 | { |

1094 | _M_range_check(__n); |

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

1096 | } |

1097 | |

1098 | /** |

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

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

1101 | * accessed. |

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

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

1104 | * |

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

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

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

1108 | */ |

1109 | const_reference |

1110 | at(size_type __n) const |

1111 | { |

1112 | _M_range_check(__n); |

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

1114 | } |

1115 | |

1116 | /** |

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

1118 | * element of the %vector. |

1119 | */ |

1120 | reference |

1121 | front() _GLIBCXX_NOEXCEPT |

1122 | { |

1123 | __glibcxx_requires_nonempty(); |

1124 | return *begin(); |

1125 | } |

1126 | |

1127 | /** |

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

1129 | * element of the %vector. |

1130 | */ |

1131 | const_reference |

1132 | front() const _GLIBCXX_NOEXCEPT |

1133 | { |

1134 | __glibcxx_requires_nonempty(); |

1135 | return *begin(); |

1136 | } |

1137 | |

1138 | /** |

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

1140 | * element of the %vector. |

1141 | */ |

1142 | reference |

1143 | back() _GLIBCXX_NOEXCEPT |

1144 | { |

1145 | __glibcxx_requires_nonempty(); |

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

1147 | } |

1148 | |

1149 | /** |

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

1151 | * last element of the %vector. |

1152 | */ |

1153 | const_reference |

1154 | back() const _GLIBCXX_NOEXCEPT |

1155 | { |

1156 | __glibcxx_requires_nonempty(); |

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

1158 | } |

1159 | |

1160 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1162 | // data access |

1163 | /** |

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

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

1166 | */ |

1167 | _Tp* |

1168 | data() _GLIBCXX_NOEXCEPT |

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

1170 | |

1171 | const _Tp* |

1172 | data() const _GLIBCXX_NOEXCEPT |

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

1174 | |

1175 | // [23.2.4.3] modifiers |

1176 | /** |

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

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

1179 | * |

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

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

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

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

1184 | * available. |

1185 | */ |

1186 | void |

1187 | push_back(const value_type& __x) |

1188 | { |

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

1190 | { |

1191 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |

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

1193 | __x); |

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

1195 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |

1196 | } |

1197 | else |

1198 | _M_realloc_insert(end(), __x); |

1199 | } |

1200 | |

1201 | #if __cplusplus >= 201103L |

1202 | void |

1203 | push_back(value_type&& __x) |

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

1205 | |

1206 | template<typename... _Args> |

1207 | #if __cplusplus > 201402L |

1208 | reference |

1209 | #else |

1210 | void |

1211 | #endif |

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

1213 | #endif |

1214 | |

1215 | /** |

1216 | * @brief Removes last element. |

1217 | * |

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

1219 | * |

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

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

1222 | * called. |

1223 | */ |

1224 | void |

1225 | pop_back() _GLIBCXX_NOEXCEPT |

1226 | { |

1227 | __glibcxx_requires_nonempty(); |

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

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

1230 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); |

1231 | } |

1232 | |

1233 | #if __cplusplus >= 201103L |

1234 | /** |

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

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

1237 | * @param __args Arguments. |

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

1239 | * |

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

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

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

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

1244 | * std::list. |

1245 | */ |

1246 | template<typename... _Args> |

1247 | iterator |

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

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

1250 | |

1251 | /** |

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

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

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

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

1256 | * |

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

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

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

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

1261 | */ |

1262 | iterator |

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

1264 | #else |

1265 | /** |

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

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

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

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

1270 | * |

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

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

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

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

1275 | */ |

1276 | iterator |

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

1278 | #endif |

1279 | |

1280 | #if __cplusplus >= 201103L |

1281 | /** |

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

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

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

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

1286 | * |

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

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

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

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

1291 | */ |

1292 | iterator |

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

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

1295 | |

1296 | /** |

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

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

1299 | * @param __l An initializer_list. |

1300 | * |

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

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

1303 | * specified by @a position. |

1304 | * |

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

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

1307 | * consider using std::list. |

1308 | */ |

1309 | iterator |

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

1311 | { |

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

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

1314 | std::random_access_iterator_tag()); |

1315 | return begin() + __offset; |

1316 | } |

1317 | #endif |

1318 | |

1319 | #if __cplusplus >= 201103L |

1320 | /** |

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

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

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

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

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

1326 | * |

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

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

1329 | * |

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

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

1332 | * consider using std::list. |

1333 | */ |

1334 | iterator |

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

1336 | { |

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

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

1339 | return begin() + __offset; |

1340 | } |

1341 | #else |

1342 | /** |

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

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

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

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

1347 | * |

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

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

1350 | * |

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

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

1353 | * consider using std::list. |

1354 | */ |

1355 | void |

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

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

1358 | #endif |

1359 | |

1360 | #if __cplusplus >= 201103L |

1361 | /** |

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

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

1364 | * @param __first An input iterator. |

1365 | * @param __last An input iterator. |

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

1367 | * |

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

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

1370 | * by @a pos. |

1371 | * |

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

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

1374 | * consider using std::list. |

1375 | */ |

1376 | template<typename _InputIterator, |

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

1378 | iterator |

1379 | insert(const_iterator __position, _InputIterator __first, |

1380 | _InputIterator __last) |

1381 | { |

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

1383 | _M_insert_dispatch(begin() + __offset, |

1384 | __first, __last, __false_type()); |

1385 | return begin() + __offset; |

1386 | } |

1387 | #else |

1388 | /** |

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

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

1391 | * @param __first An input iterator. |

1392 | * @param __last An input iterator. |

1393 | * |

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

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

1396 | * by @a pos. |

1397 | * |

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

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

1400 | * consider using std::list. |

1401 | */ |

1402 | template<typename _InputIterator> |

1403 | void |

1404 | insert(iterator __position, _InputIterator __first, |

1405 | _InputIterator __last) |

1406 | { |

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

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

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

1410 | } |

1411 | #endif |

1412 | |

1413 | /** |

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

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

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

1417 | * |

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

1419 | * shorten the %vector by one. |

1420 | * |

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

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

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

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

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

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

1427 | */ |

1428 | iterator |

1429 | #if __cplusplus >= 201103L |

1430 | erase(const_iterator __position) |

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

1432 | #else |

1433 | erase(iterator __position) |

1434 | { return _M_erase(__position); } |

1435 | #endif |

1436 | |

1437 | /** |

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

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

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

1441 | * erased. |

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

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

1444 | * |

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

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

1447 | * |

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

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

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

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

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

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

1454 | */ |

1455 | iterator |

1456 | #if __cplusplus >= 201103L |

1457 | erase(const_iterator __first, const_iterator __last) |

1458 | { |

1459 | const auto __beg = begin(); |

1460 | const auto __cbeg = cbegin(); |

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

1462 | } |

1463 | #else |

1464 | erase(iterator __first, iterator __last) |

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

1466 | #endif |

1467 | |

1468 | /** |

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

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

1471 | * |

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

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

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

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

1476 | * |

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

1478 | */ |

1479 | void |

1480 | swap(vector& __x) _GLIBCXX_NOEXCEPT |

1481 | { |

1482 | #if __cplusplus >= 201103L |

1483 | __glibcxx_assert(_Alloc_traits::propagate_on_container_swap::value |

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

1485 | #endif |

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

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

1488 | __x._M_get_Tp_allocator()); |

1489 | } |

1490 | |

1491 | /** |

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

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

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

1495 | * the user's responsibility. |

1496 | */ |

1497 | void |

1498 | clear() _GLIBCXX_NOEXCEPT |

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

1500 | |

1501 | protected: |

1502 | /** |

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

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

1505 | */ |

1506 | template<typename _ForwardIterator> |

1507 | pointer |

1508 | _M_allocate_and_copy(size_type __n, |

1509 | _ForwardIterator __first, _ForwardIterator __last) |

1510 | { |

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

1512 | __try |

1513 | { |

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

1515 | _M_get_Tp_allocator()); |

1516 | return __result; |

1517 | } |

1518 | __catch(...) |

1519 | { |

1520 | _M_deallocate(__result, __n); |

1521 | __throw_exception_again; |

1522 | } |

1523 | } |

1524 | |

1525 | |

1526 | // Internal constructor functions follow. |

1527 | |

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

1529 | |

1530 | #if __cplusplus < 201103L |

1531 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1533 | template<typename _Integer> |

1534 | void |

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

1536 | { |

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

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

1539 | this->_M_impl._M_end_of_storage = |

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

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

1542 | } |

1543 | |

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

1545 | template<typename _InputIterator> |

1546 | void |

1547 | _M_initialize_dispatch(_InputIterator __first, _InputIterator __last, |

1548 | __false_type) |

1549 | { |

1550 | _M_range_initialize(__first, __last, |

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

1552 | } |

1553 | #endif |

1554 | |

1555 | // Called by the second initialize_dispatch above |

1556 | template<typename _InputIterator> |

1557 | void |

1558 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |

1559 | std::input_iterator_tag) |

1560 | { |

1561 | __try { |

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

1563 | #if __cplusplus >= 201103L |

1564 | emplace_back(*__first); |

1565 | #else |

1566 | push_back(*__first); |

1567 | #endif |

1568 | } __catch(...) { |

1569 | clear(); |

1570 | __throw_exception_again; |

1571 | } |

1572 | } |

1573 | |

1574 | // Called by the second initialize_dispatch above |

1575 | template<typename _ForwardIterator> |

1576 | void |

1577 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |

1578 | std::forward_iterator_tag) |

1579 | { |

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

1581 | this->_M_impl._M_start |

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

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

1584 | this->_M_impl._M_finish = |

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

1586 | this->_M_impl._M_start, |

1587 | _M_get_Tp_allocator()); |

1588 | } |

1589 | |

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

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

1592 | void |

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

1594 | { |

1595 | this->_M_impl._M_finish = |

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

1597 | _M_get_Tp_allocator()); |

1598 | } |

1599 | |

1600 | #if __cplusplus >= 201103L |

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

1602 | void |

1603 | _M_default_initialize(size_type __n) |

1604 | { |

1605 | this->_M_impl._M_finish = |

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

1607 | _M_get_Tp_allocator()); |

1608 | } |

1609 | #endif |

1610 | |

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

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

1613 | |

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

1615 | |

1616 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1618 | template<typename _Integer> |

1619 | void |

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

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

1622 | |

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

1624 | template<typename _InputIterator> |

1625 | void |

1626 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, |

1627 | __false_type) |

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

1629 | |

1630 | // Called by the second assign_dispatch above |

1631 | template<typename _InputIterator> |

1632 | void |

1633 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |

1634 | std::input_iterator_tag); |

1635 | |

1636 | // Called by the second assign_dispatch above |

1637 | template<typename _ForwardIterator> |

1638 | void |

1639 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |

1640 | std::forward_iterator_tag); |

1641 | |

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

1643 | // to be the same thing. |

1644 | void |

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

1646 | |

1647 | // Internal insert functions follow. |

1648 | |

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

1650 | |

1651 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |

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

1653 | template<typename _Integer> |

1654 | void |

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

1656 | __true_type) |

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

1658 | |

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

1660 | template<typename _InputIterator> |

1661 | void |

1662 | _M_insert_dispatch(iterator __pos, _InputIterator __first, |

1663 | _InputIterator __last, __false_type) |

1664 | { |

1665 | _M_range_insert(__pos, __first, __last, |

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

1667 | } |

1668 | |

1669 | // Called by the second insert_dispatch above |

1670 | template<typename _InputIterator> |

1671 | void |

1672 | _M_range_insert(iterator __pos, _InputIterator __first, |

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

1674 | |

1675 | // Called by the second insert_dispatch above |

1676 | template<typename _ForwardIterator> |

1677 | void |

1678 | _M_range_insert(iterator __pos, _ForwardIterator __first, |

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

1680 | |

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

1682 | // the same thing. |

1683 | void |

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

1685 | |

1686 | #if __cplusplus >= 201103L |

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

1688 | void |

1689 | _M_default_append(size_type __n); |

1690 | |

1691 | bool |

1692 | _M_shrink_to_fit(); |

1693 | #endif |

1694 | |

1695 | #if __cplusplus < 201103L |

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

1697 | void |

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

1699 | |

1700 | void |

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

1702 | #else |

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

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

1705 | struct _Temporary_value |

1706 | { |

1707 | template<typename... _Args> |

1708 | explicit |

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

1710 | { |

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

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

1713 | } |

1714 | |

1715 | ~_Temporary_value() |

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

1717 | |

1718 | value_type& |

1719 | _M_val() { return *_M_ptr(); } |

1720 | |

1721 | private: |

1722 | _Tp* |

1723 | _M_ptr() { return reinterpret_cast<_Tp*>(&__buf); } |

1724 | |

1725 | vector* _M_this; |

1726 | typename aligned_storage<sizeof(_Tp), alignof(_Tp)>::type __buf; |

1727 | }; |

1728 | |

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

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

1731 | template<typename _Arg> |

1732 | void |

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

1734 | |

1735 | template<typename... _Args> |

1736 | void |

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

1738 | |

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

1740 | iterator |

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

1742 | |

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

1744 | template<typename... _Args> |

1745 | iterator |

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

1747 | |

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

1749 | iterator |

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

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

1752 | #endif |

1753 | |

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

1755 | size_type |

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

1757 | { |

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

1759 | __throw_length_error(__N(__s)); |

1760 | |

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

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

1763 | } |

1764 | |

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

1766 | static size_type |

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

1768 | { |

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

1770 | __throw_length_error( |

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

1772 | return __n; |

1773 | } |

1774 | |

1775 | static size_type |

1776 | _S_max_size(const _Tp_alloc_type& __a) _GLIBCXX_NOEXCEPT |

1777 | { |

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

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

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

1781 | const size_t __diffmax |

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

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

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

1785 | } |

1786 | |

1787 | // Internal erase functions follow. |

1788 | |

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

1790 | // _M_assign_aux. |

1791 | void |

1792 | _M_erase_at_end(pointer __pos) _GLIBCXX_NOEXCEPT |

1793 | { |

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

1795 | { |

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

1797 | _M_get_Tp_allocator()); |

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

1799 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(__n); |

1800 | } |

1801 | } |

1802 | |

1803 | iterator |

1804 | _M_erase(iterator __position); |

1805 | |

1806 | iterator |

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

1808 | |

1809 | #if __cplusplus >= 201103L |

1810 | private: |

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

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

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

1814 | void |

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

1816 | { |

1817 | vector __tmp(get_allocator()); |

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

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

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

1821 | } |

1822 | |

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

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

1825 | void |

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

1827 | { |

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

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

1830 | else |

1831 | { |

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

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

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

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

1836 | std::random_access_iterator_tag()); |

1837 | __x.clear(); |

1838 | } |

1839 | } |

1840 | #endif |

1841 | |

1842 | template<typename _Up> |

1843 | _Up* |

1844 | _M_data_ptr(_Up* __ptr) const _GLIBCXX_NOEXCEPT |

1845 | { return __ptr; } |

1846 | |

1847 | #if __cplusplus >= 201103L |

1848 | template<typename _Ptr> |

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

1850 | _M_data_ptr(_Ptr __ptr) const |

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

1852 | #else |

1853 | template<typename _Up> |

1854 | _Up* |

1855 | _M_data_ptr(_Up* __ptr) _GLIBCXX_NOEXCEPT |

1856 | { return __ptr; } |

1857 | |

1858 | template<typename _Ptr> |

1859 | value_type* |

1860 | _M_data_ptr(_Ptr __ptr) |

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

1862 | |

1863 | template<typename _Ptr> |

1864 | const value_type* |

1865 | _M_data_ptr(_Ptr __ptr) const |

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

1867 | #endif |

1868 | }; |

1869 | |

1870 | #if __cpp_deduction_guides >= 201606 |

1871 | template<typename _InputIterator, typename _ValT |

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

1873 | typename _Allocator = allocator<_ValT>, |

1874 | typename = _RequireInputIter<_InputIterator>, |

1875 | typename = _RequireAllocator<_Allocator>> |

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

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

1878 | #endif |

1879 | |

1880 | /** |

1881 | * @brief Vector equality comparison. |

1882 | * @param __x A %vector. |

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

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

1885 | * |

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

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

1888 | * and if corresponding elements compare equal. |

1889 | */ |

1890 | template<typename _Tp, typename _Alloc> |

1891 | inline bool |

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

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

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

1895 | |

1896 | #if __cpp_lib_three_way_comparison |

1897 | /** |

1898 | * @brief Vector ordering relation. |

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

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

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

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

1903 | * |

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

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

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

1907 | */ |

1908 | template<typename _Tp, typename _Alloc> |

1909 | inline __detail::__synth3way_t<_Tp> |

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

1911 | { |

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

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

1914 | __detail::__synth3way); |

1915 | } |

1916 | #else |

1917 | /** |

1918 | * @brief Vector ordering relation. |

1919 | * @param __x A %vector. |

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

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

1922 | * |

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

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

1925 | * |

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

1927 | */ |

1928 | template<typename _Tp, typename _Alloc> |

1929 | inline bool |

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

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

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

1933 | |

1934 | /// Based on operator== |

1935 | template<typename _Tp, typename _Alloc> |

1936 | inline bool |

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

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

1939 | |

1940 | /// Based on operator< |

1941 | template<typename _Tp, typename _Alloc> |

1942 | inline bool |

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

1944 | { return __y < __x; } |

1945 | |

1946 | /// Based on operator< |

1947 | template<typename _Tp, typename _Alloc> |

1948 | inline bool |

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

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

1951 | |

1952 | /// Based on operator< |

1953 | template<typename _Tp, typename _Alloc> |

1954 | inline bool |

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

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

1957 | #endif // three-way comparison |

1958 | |

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

1960 | template<typename _Tp, typename _Alloc> |

1961 | inline void |

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

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

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

1965 | |

1966 | _GLIBCXX_END_NAMESPACE_CONTAINER |

1967 | |

1968 | #if __cplusplus >= 201703L |

1969 | namespace __detail::__variant |

1970 | { |

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

1972 | |

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

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

1975 | template<typename _Tp, typename _Alloc> |

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

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

1978 | { }; |

1979 | } // namespace __detail::__variant |

1980 | #endif // C++17 |

1981 | |

1982 | _GLIBCXX_END_NAMESPACE_VERSION |

1983 | } // namespace std |

1984 | |

1985 | #endif /* _STL_VECTOR_H */ |

1986 |