1 | // Vector implementation (out of line) -*- C++ -*- |
---|---|

2 | |

3 | // Copyright (C) 2001-2015 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/vector.tcc |

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

57 | #define _VECTOR_TCC 1 |

58 | |

59 | namespace std _GLIBCXX_VISIBILITY(default) |

60 | { |

61 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |

62 | |

63 | template<typename _Tp, typename _Alloc> |

64 | void |

65 | vector<_Tp, _Alloc>:: |

66 | reserve(size_type __n) |

67 | { |

68 | if (__n > this->max_size()) |

69 | __throw_length_error(__N("vector::reserve")); |

70 | if (this->capacity() < __n) |

71 | { |

72 | const size_type __old_size = size(); |

73 | pointer __tmp = _M_allocate_and_copy(__n, |

74 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), |

75 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); |

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

77 | _M_get_Tp_allocator()); |

78 | _M_deallocate(this->_M_impl._M_start, |

79 | this->_M_impl._M_end_of_storage |

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

81 | this->_M_impl._M_start = __tmp; |

82 | this->_M_impl._M_finish = __tmp + __old_size; |

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

84 | } |

85 | } |

86 | |

87 | #if __cplusplus >= 201103L |

88 | template<typename _Tp, typename _Alloc> |

89 | template<typename... _Args> |

90 | void |

91 | vector<_Tp, _Alloc>:: |

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

93 | { |

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

95 | { |

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

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

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

99 | } |

100 | else |

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

102 | } |

103 | #endif |

104 | |

105 | template<typename _Tp, typename _Alloc> |

106 | typename vector<_Tp, _Alloc>::iterator |

107 | vector<_Tp, _Alloc>:: |

108 | #if __cplusplus >= 201103L |

109 | insert(const_iterator __position, const value_type& __x) |

110 | #else |

111 | insert(iterator __position, const value_type& __x) |

112 | #endif |

113 | { |

114 | const size_type __n = __position - begin(); |

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

116 | && __position == end()) |

117 | { |

118 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x); |

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

120 | } |

121 | else |

122 | { |

123 | #if __cplusplus >= 201103L |

124 | const auto __pos = begin() + (__position - cbegin()); |

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

126 | { |

127 | _Tp __x_copy = __x; |

128 | _M_insert_aux(__pos, std::move(__x_copy)); |

129 | } |

130 | else |

131 | _M_insert_aux(__pos, __x); |

132 | #else |

133 | _M_insert_aux(__position, __x); |

134 | #endif |

135 | } |

136 | return iterator(this->_M_impl._M_start + __n); |

137 | } |

138 | |

139 | template<typename _Tp, typename _Alloc> |

140 | typename vector<_Tp, _Alloc>::iterator |

141 | vector<_Tp, _Alloc>:: |

142 | _M_erase(iterator __position) |

143 | { |

144 | if (__position + 1 != end()) |

145 | _GLIBCXX_MOVE3(__position + 1, end(), __position); |

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

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

148 | return __position; |

149 | } |

150 | |

151 | template<typename _Tp, typename _Alloc> |

152 | typename vector<_Tp, _Alloc>::iterator |

153 | vector<_Tp, _Alloc>:: |

154 | _M_erase(iterator __first, iterator __last) |

155 | { |

156 | if (__first != __last) |

157 | { |

158 | if (__last != end()) |

159 | _GLIBCXX_MOVE3(__last, end(), __first); |

160 | _M_erase_at_end(__first.base() + (end() - __last)); |

161 | } |

162 | return __first; |

163 | } |

164 | |

165 | template<typename _Tp, typename _Alloc> |

166 | vector<_Tp, _Alloc>& |

167 | vector<_Tp, _Alloc>:: |

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

169 | { |

170 | if (&__x != this) |

171 | { |

172 | #if __cplusplus >= 201103L |

173 | if (_Alloc_traits::_S_propagate_on_copy_assign()) |

174 | { |

175 | if (!_Alloc_traits::_S_always_equal() |

176 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) |

177 | { |

178 | // replacement allocator cannot free existing storage |

179 | this->clear(); |

180 | _M_deallocate(this->_M_impl._M_start, |

181 | this->_M_impl._M_end_of_storage |

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

183 | this->_M_impl._M_start = nullptr; |

184 | this->_M_impl._M_finish = nullptr; |

185 | this->_M_impl._M_end_of_storage = nullptr; |

186 | } |

187 | std::__alloc_on_copy(_M_get_Tp_allocator(), |

188 | __x._M_get_Tp_allocator()); |

189 | } |

190 | #endif |

191 | const size_type __xlen = __x.size(); |

192 | if (__xlen > capacity()) |

193 | { |

194 | pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), |

195 | __x.end()); |

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

197 | _M_get_Tp_allocator()); |

198 | _M_deallocate(this->_M_impl._M_start, |

199 | this->_M_impl._M_end_of_storage |

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

201 | this->_M_impl._M_start = __tmp; |

202 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; |

203 | } |

204 | else if (size() >= __xlen) |

205 | { |

206 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |

207 | end(), _M_get_Tp_allocator()); |

208 | } |

209 | else |

210 | { |

211 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |

212 | this->_M_impl._M_start); |

213 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |

214 | __x._M_impl._M_finish, |

215 | this->_M_impl._M_finish, |

216 | _M_get_Tp_allocator()); |

217 | } |

218 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; |

219 | } |

220 | return *this; |

221 | } |

222 | |

223 | template<typename _Tp, typename _Alloc> |

224 | void |

225 | vector<_Tp, _Alloc>:: |

226 | _M_fill_assign(size_t __n, const value_type& __val) |

227 | { |

228 | if (__n > capacity()) |

229 | { |

230 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |

231 | __tmp._M_impl._M_swap_data(this->_M_impl); |

232 | } |

233 | else if (__n > size()) |

234 | { |

235 | std::fill(begin(), end(), __val); |

236 | this->_M_impl._M_finish = |

237 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |

238 | __n - size(), __val, |

239 | _M_get_Tp_allocator()); |

240 | } |

241 | else |

242 | _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); |

243 | } |

244 | |

245 | template<typename _Tp, typename _Alloc> |

246 | template<typename _InputIterator> |

247 | void |

248 | vector<_Tp, _Alloc>:: |

249 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |

250 | std::input_iterator_tag) |

251 | { |

252 | pointer __cur(this->_M_impl._M_start); |

253 | for (; __first != __last && __cur != this->_M_impl._M_finish; |

254 | ++__cur, ++__first) |

255 | *__cur = *__first; |

256 | if (__first == __last) |

257 | _M_erase_at_end(__cur); |

258 | else |

259 | insert(end(), __first, __last); |

260 | } |

261 | |

262 | template<typename _Tp, typename _Alloc> |

263 | template<typename _ForwardIterator> |

264 | void |

265 | vector<_Tp, _Alloc>:: |

266 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |

267 | std::forward_iterator_tag) |

268 | { |

269 | const size_type __len = std::distance(__first, __last); |

270 | |

271 | if (__len > capacity()) |

272 | { |

273 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); |

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

275 | _M_get_Tp_allocator()); |

276 | _M_deallocate(this->_M_impl._M_start, |

277 | this->_M_impl._M_end_of_storage |

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

279 | this->_M_impl._M_start = __tmp; |

280 | this->_M_impl._M_finish = this->_M_impl._M_start + __len; |

281 | this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; |

282 | } |

283 | else if (size() >= __len) |

284 | _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); |

285 | else |

286 | { |

287 | _ForwardIterator __mid = __first; |

288 | std::advance(__mid, size()); |

289 | std::copy(__first, __mid, this->_M_impl._M_start); |

290 | this->_M_impl._M_finish = |

291 | std::__uninitialized_copy_a(__mid, __last, |

292 | this->_M_impl._M_finish, |

293 | _M_get_Tp_allocator()); |

294 | } |

295 | } |

296 | |

297 | #if __cplusplus >= 201103L |

298 | template<typename _Tp, typename _Alloc> |

299 | template<typename... _Args> |

300 | typename vector<_Tp, _Alloc>::iterator |

301 | vector<_Tp, _Alloc>:: |

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

303 | { |

304 | const size_type __n = __position - begin(); |

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

306 | && __position == end()) |

307 | { |

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

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

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

311 | } |

312 | else |

313 | _M_insert_aux(begin() + (__position - cbegin()), |

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

315 | return iterator(this->_M_impl._M_start + __n); |

316 | } |

317 | |

318 | template<typename _Tp, typename _Alloc> |

319 | template<typename... _Args> |

320 | void |

321 | vector<_Tp, _Alloc>:: |

322 | _M_insert_aux(iterator __position, _Args&&... __args) |

323 | #else |

324 | template<typename _Tp, typename _Alloc> |

325 | void |

326 | vector<_Tp, _Alloc>:: |

327 | _M_insert_aux(iterator __position, const _Tp& __x) |

328 | #endif |

329 | { |

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

331 | { |

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

333 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish |

334 | - 1))); |

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

336 | #if __cplusplus < 201103L |

337 | _Tp __x_copy = __x; |

338 | #endif |

339 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |

340 | this->_M_impl._M_finish - 2, |

341 | this->_M_impl._M_finish - 1); |

342 | #if __cplusplus < 201103L |

343 | *__position = __x_copy; |

344 | #else |

345 | *__position = _Tp(std::forward<_Args>(__args)...); |

346 | #endif |

347 | } |

348 | else |

349 | { |

350 | const size_type __len = |

351 | _M_check_len(size_type(1), "vector::_M_insert_aux"); |

352 | const size_type __elems_before = __position - begin(); |

353 | pointer __new_start(this->_M_allocate(__len)); |

354 | pointer __new_finish(__new_start); |

355 | __try |

356 | { |

357 | // The order of the three operations is dictated by the C++0x |

358 | // case, where the moves could alter a new element belonging |

359 | // to the existing vector. This is an issue only for callers |

360 | // taking the element by const lvalue ref (see 23.1/13). |

361 | _Alloc_traits::construct(this->_M_impl, |

362 | __new_start + __elems_before, |

363 | #if __cplusplus >= 201103L |

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

365 | #else |

366 | __x); |

367 | #endif |

368 | __new_finish = pointer(); |

369 | |

370 | __new_finish |

371 | = std::__uninitialized_move_if_noexcept_a |

372 | (this->_M_impl._M_start, __position.base(), |

373 | __new_start, _M_get_Tp_allocator()); |

374 | |

375 | ++__new_finish; |

376 | |

377 | __new_finish |

378 | = std::__uninitialized_move_if_noexcept_a |

379 | (__position.base(), this->_M_impl._M_finish, |

380 | __new_finish, _M_get_Tp_allocator()); |

381 | } |

382 | __catch(...) |

383 | { |

384 | if (!__new_finish) |

385 | _Alloc_traits::destroy(this->_M_impl, |

386 | __new_start + __elems_before); |

387 | else |

388 | std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); |

389 | _M_deallocate(__new_start, __len); |

390 | __throw_exception_again; |

391 | } |

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

393 | _M_get_Tp_allocator()); |

394 | _M_deallocate(this->_M_impl._M_start, |

395 | this->_M_impl._M_end_of_storage |

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

397 | this->_M_impl._M_start = __new_start; |

398 | this->_M_impl._M_finish = __new_finish; |

399 | this->_M_impl._M_end_of_storage = __new_start + __len; |

400 | } |

401 | } |

402 | |

403 | #if __cplusplus >= 201103L |

404 | template<typename _Tp, typename _Alloc> |

405 | template<typename... _Args> |

406 | void |

407 | vector<_Tp, _Alloc>:: |

408 | _M_emplace_back_aux(_Args&&... __args) |

409 | { |

410 | const size_type __len = |

411 | _M_check_len(size_type(1), "vector::_M_emplace_back_aux"); |

412 | pointer __new_start(this->_M_allocate(__len)); |

413 | pointer __new_finish(__new_start); |

414 | __try |

415 | { |

416 | _Alloc_traits::construct(this->_M_impl, __new_start + size(), |

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

418 | __new_finish = pointer(); |

419 | |

420 | __new_finish |

421 | = std::__uninitialized_move_if_noexcept_a |

422 | (this->_M_impl._M_start, this->_M_impl._M_finish, |

423 | __new_start, _M_get_Tp_allocator()); |

424 | |

425 | ++__new_finish; |

426 | } |

427 | __catch(...) |

428 | { |

429 | if (!__new_finish) |

430 | _Alloc_traits::destroy(this->_M_impl, __new_start + size()); |

431 | else |

432 | std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); |

433 | _M_deallocate(__new_start, __len); |

434 | __throw_exception_again; |

435 | } |

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

437 | _M_get_Tp_allocator()); |

438 | _M_deallocate(this->_M_impl._M_start, |

439 | this->_M_impl._M_end_of_storage |

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

441 | this->_M_impl._M_start = __new_start; |

442 | this->_M_impl._M_finish = __new_finish; |

443 | this->_M_impl._M_end_of_storage = __new_start + __len; |

444 | } |

445 | #endif |

446 | |

447 | template<typename _Tp, typename _Alloc> |

448 | void |

449 | vector<_Tp, _Alloc>:: |

450 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |

451 | { |

452 | if (__n != 0) |

453 | { |

454 | if (size_type(this->_M_impl._M_end_of_storage |

455 | - this->_M_impl._M_finish) >= __n) |

456 | { |

457 | value_type __x_copy = __x; |

458 | const size_type __elems_after = end() - __position; |

459 | pointer __old_finish(this->_M_impl._M_finish); |

460 | if (__elems_after > __n) |

461 | { |

462 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |

463 | this->_M_impl._M_finish, |

464 | this->_M_impl._M_finish, |

465 | _M_get_Tp_allocator()); |

466 | this->_M_impl._M_finish += __n; |

467 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |

468 | __old_finish - __n, __old_finish); |

469 | std::fill(__position.base(), __position.base() + __n, |

470 | __x_copy); |

471 | } |

472 | else |

473 | { |

474 | this->_M_impl._M_finish = |

475 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |

476 | __n - __elems_after, |

477 | __x_copy, |

478 | _M_get_Tp_allocator()); |

479 | std::__uninitialized_move_a(__position.base(), __old_finish, |

480 | this->_M_impl._M_finish, |

481 | _M_get_Tp_allocator()); |

482 | this->_M_impl._M_finish += __elems_after; |

483 | std::fill(__position.base(), __old_finish, __x_copy); |

484 | } |

485 | } |

486 | else |

487 | { |

488 | const size_type __len = |

489 | _M_check_len(__n, "vector::_M_fill_insert"); |

490 | const size_type __elems_before = __position - begin(); |

491 | pointer __new_start(this->_M_allocate(__len)); |

492 | pointer __new_finish(__new_start); |

493 | __try |

494 | { |

495 | // See _M_insert_aux above. |

496 | std::__uninitialized_fill_n_a(__new_start + __elems_before, |

497 | __n, __x, |

498 | _M_get_Tp_allocator()); |

499 | __new_finish = pointer(); |

500 | |

501 | __new_finish |

502 | = std::__uninitialized_move_if_noexcept_a |

503 | (this->_M_impl._M_start, __position.base(), |

504 | __new_start, _M_get_Tp_allocator()); |

505 | |

506 | __new_finish += __n; |

507 | |

508 | __new_finish |

509 | = std::__uninitialized_move_if_noexcept_a |

510 | (__position.base(), this->_M_impl._M_finish, |

511 | __new_finish, _M_get_Tp_allocator()); |

512 | } |

513 | __catch(...) |

514 | { |

515 | if (!__new_finish) |

516 | std::_Destroy(__new_start + __elems_before, |

517 | __new_start + __elems_before + __n, |

518 | _M_get_Tp_allocator()); |

519 | else |

520 | std::_Destroy(__new_start, __new_finish, |

521 | _M_get_Tp_allocator()); |

522 | _M_deallocate(__new_start, __len); |

523 | __throw_exception_again; |

524 | } |

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

526 | _M_get_Tp_allocator()); |

527 | _M_deallocate(this->_M_impl._M_start, |

528 | this->_M_impl._M_end_of_storage |

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

530 | this->_M_impl._M_start = __new_start; |

531 | this->_M_impl._M_finish = __new_finish; |

532 | this->_M_impl._M_end_of_storage = __new_start + __len; |

533 | } |

534 | } |

535 | } |

536 | |

537 | #if __cplusplus >= 201103L |

538 | template<typename _Tp, typename _Alloc> |

539 | void |

540 | vector<_Tp, _Alloc>:: |

541 | _M_default_append(size_type __n) |

542 | { |

543 | if (__n != 0) |

544 | { |

545 | if (size_type(this->_M_impl._M_end_of_storage |

546 | - this->_M_impl._M_finish) >= __n) |

547 | { |

548 | this->_M_impl._M_finish = |

549 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, |

550 | __n, _M_get_Tp_allocator()); |

551 | } |

552 | else |

553 | { |

554 | const size_type __len = |

555 | _M_check_len(__n, "vector::_M_default_append"); |

556 | const size_type __old_size = this->size(); |

557 | pointer __new_start(this->_M_allocate(__len)); |

558 | pointer __new_finish(__new_start); |

559 | __try |

560 | { |

561 | __new_finish |

562 | = std::__uninitialized_move_if_noexcept_a |

563 | (this->_M_impl._M_start, this->_M_impl._M_finish, |

564 | __new_start, _M_get_Tp_allocator()); |

565 | __new_finish = |

566 | std::__uninitialized_default_n_a(__new_finish, __n, |

567 | _M_get_Tp_allocator()); |

568 | } |

569 | __catch(...) |

570 | { |

571 | std::_Destroy(__new_start, __new_finish, |

572 | _M_get_Tp_allocator()); |

573 | _M_deallocate(__new_start, __len); |

574 | __throw_exception_again; |

575 | } |

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

577 | _M_get_Tp_allocator()); |

578 | _M_deallocate(this->_M_impl._M_start, |

579 | this->_M_impl._M_end_of_storage |

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

581 | this->_M_impl._M_start = __new_start; |

582 | this->_M_impl._M_finish = __new_finish; |

583 | this->_M_impl._M_end_of_storage = __new_start + __len; |

584 | } |

585 | } |

586 | } |

587 | |

588 | template<typename _Tp, typename _Alloc> |

589 | bool |

590 | vector<_Tp, _Alloc>:: |

591 | _M_shrink_to_fit() |

592 | { |

593 | if (capacity() == size()) |

594 | return false; |

595 | return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); |

596 | } |

597 | #endif |

598 | |

599 | template<typename _Tp, typename _Alloc> |

600 | template<typename _InputIterator> |

601 | void |

602 | vector<_Tp, _Alloc>:: |

603 | _M_range_insert(iterator __pos, _InputIterator __first, |

604 | _InputIterator __last, std::input_iterator_tag) |

605 | { |

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

607 | { |

608 | __pos = insert(__pos, *__first); |

609 | ++__pos; |

610 | } |

611 | } |

612 | |

613 | template<typename _Tp, typename _Alloc> |

614 | template<typename _ForwardIterator> |

615 | void |

616 | vector<_Tp, _Alloc>:: |

617 | _M_range_insert(iterator __position, _ForwardIterator __first, |

618 | _ForwardIterator __last, std::forward_iterator_tag) |

619 | { |

620 | if (__first != __last) |

621 | { |

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

623 | if (size_type(this->_M_impl._M_end_of_storage |

624 | - this->_M_impl._M_finish) >= __n) |

625 | { |

626 | const size_type __elems_after = end() - __position; |

627 | pointer __old_finish(this->_M_impl._M_finish); |

628 | if (__elems_after > __n) |

629 | { |

630 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |

631 | this->_M_impl._M_finish, |

632 | this->_M_impl._M_finish, |

633 | _M_get_Tp_allocator()); |

634 | this->_M_impl._M_finish += __n; |

635 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |

636 | __old_finish - __n, __old_finish); |

637 | std::copy(__first, __last, __position); |

638 | } |

639 | else |

640 | { |

641 | _ForwardIterator __mid = __first; |

642 | std::advance(__mid, __elems_after); |

643 | std::__uninitialized_copy_a(__mid, __last, |

644 | this->_M_impl._M_finish, |

645 | _M_get_Tp_allocator()); |

646 | this->_M_impl._M_finish += __n - __elems_after; |

647 | std::__uninitialized_move_a(__position.base(), |

648 | __old_finish, |

649 | this->_M_impl._M_finish, |

650 | _M_get_Tp_allocator()); |

651 | this->_M_impl._M_finish += __elems_after; |

652 | std::copy(__first, __mid, __position); |

653 | } |

654 | } |

655 | else |

656 | { |

657 | const size_type __len = |

658 | _M_check_len(__n, "vector::_M_range_insert"); |

659 | pointer __new_start(this->_M_allocate(__len)); |

660 | pointer __new_finish(__new_start); |

661 | __try |

662 | { |

663 | __new_finish |

664 | = std::__uninitialized_move_if_noexcept_a |

665 | (this->_M_impl._M_start, __position.base(), |

666 | __new_start, _M_get_Tp_allocator()); |

667 | __new_finish |

668 | = std::__uninitialized_copy_a(__first, __last, |

669 | __new_finish, |

670 | _M_get_Tp_allocator()); |

671 | __new_finish |

672 | = std::__uninitialized_move_if_noexcept_a |

673 | (__position.base(), this->_M_impl._M_finish, |

674 | __new_finish, _M_get_Tp_allocator()); |

675 | } |

676 | __catch(...) |

677 | { |

678 | std::_Destroy(__new_start, __new_finish, |

679 | _M_get_Tp_allocator()); |

680 | _M_deallocate(__new_start, __len); |

681 | __throw_exception_again; |

682 | } |

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

684 | _M_get_Tp_allocator()); |

685 | _M_deallocate(this->_M_impl._M_start, |

686 | this->_M_impl._M_end_of_storage |

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

688 | this->_M_impl._M_start = __new_start; |

689 | this->_M_impl._M_finish = __new_finish; |

690 | this->_M_impl._M_end_of_storage = __new_start + __len; |

691 | } |

692 | } |

693 | } |

694 | |

695 | |

696 | // vector<bool> |

697 | template<typename _Alloc> |

698 | void |

699 | vector<bool, _Alloc>:: |

700 | _M_reallocate(size_type __n) |

701 | { |

702 | _Bit_pointer __q = this->_M_allocate(__n); |

703 | iterator __start(std::__addressof(*__q), 0); |

704 | this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), __start); |

705 | this->_M_deallocate(); |

706 | this->_M_impl._M_start = __start; |

707 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); |

708 | } |

709 | |

710 | template<typename _Alloc> |

711 | void |

712 | vector<bool, _Alloc>:: |

713 | _M_fill_insert(iterator __position, size_type __n, bool __x) |

714 | { |

715 | if (__n == 0) |

716 | return; |

717 | if (capacity() - size() >= __n) |

718 | { |

719 | std::copy_backward(__position, end(), |

720 | this->_M_impl._M_finish + difference_type(__n)); |

721 | std::fill(__position, __position + difference_type(__n), __x); |

722 | this->_M_impl._M_finish += difference_type(__n); |

723 | } |

724 | else |

725 | { |

726 | const size_type __len = |

727 | _M_check_len(__n, "vector<bool>::_M_fill_insert"); |

728 | _Bit_pointer __q = this->_M_allocate(__len); |

729 | iterator __start(std::__addressof(*__q), 0); |

730 | iterator __i = _M_copy_aligned(begin(), __position, __start); |

731 | std::fill(__i, __i + difference_type(__n), __x); |

732 | this->_M_impl._M_finish = std::copy(__position, end(), |

733 | __i + difference_type(__n)); |

734 | this->_M_deallocate(); |

735 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |

736 | this->_M_impl._M_start = __start; |

737 | } |

738 | } |

739 | |

740 | template<typename _Alloc> |

741 | template<typename _ForwardIterator> |

742 | void |

743 | vector<bool, _Alloc>:: |

744 | _M_insert_range(iterator __position, _ForwardIterator __first, |

745 | _ForwardIterator __last, std::forward_iterator_tag) |

746 | { |

747 | if (__first != __last) |

748 | { |

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

750 | if (capacity() - size() >= __n) |

751 | { |

752 | std::copy_backward(__position, end(), |

753 | this->_M_impl._M_finish |

754 | + difference_type(__n)); |

755 | std::copy(__first, __last, __position); |

756 | this->_M_impl._M_finish += difference_type(__n); |

757 | } |

758 | else |

759 | { |

760 | const size_type __len = |

761 | _M_check_len(__n, "vector<bool>::_M_insert_range"); |

762 | _Bit_pointer __q = this->_M_allocate(__len); |

763 | iterator __start(std::__addressof(*__q), 0); |

764 | iterator __i = _M_copy_aligned(begin(), __position, __start); |

765 | __i = std::copy(__first, __last, __i); |

766 | this->_M_impl._M_finish = std::copy(__position, end(), __i); |

767 | this->_M_deallocate(); |

768 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |

769 | this->_M_impl._M_start = __start; |

770 | } |

771 | } |

772 | } |

773 | |

774 | template<typename _Alloc> |

775 | void |

776 | vector<bool, _Alloc>:: |

777 | _M_insert_aux(iterator __position, bool __x) |

778 | { |

779 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) |

780 | { |

781 | std::copy_backward(__position, this->_M_impl._M_finish, |

782 | this->_M_impl._M_finish + 1); |

783 | *__position = __x; |

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

785 | } |

786 | else |

787 | { |

788 | const size_type __len = |

789 | _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); |

790 | _Bit_pointer __q = this->_M_allocate(__len); |

791 | iterator __start(std::__addressof(*__q), 0); |

792 | iterator __i = _M_copy_aligned(begin(), __position, __start); |

793 | *__i++ = __x; |

794 | this->_M_impl._M_finish = std::copy(__position, end(), __i); |

795 | this->_M_deallocate(); |

796 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |

797 | this->_M_impl._M_start = __start; |

798 | } |

799 | } |

800 | |

801 | template<typename _Alloc> |

802 | typename vector<bool, _Alloc>::iterator |

803 | vector<bool, _Alloc>:: |

804 | _M_erase(iterator __position) |

805 | { |

806 | if (__position + 1 != end()) |

807 | std::copy(__position + 1, end(), __position); |

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

809 | return __position; |

810 | } |

811 | |

812 | template<typename _Alloc> |

813 | typename vector<bool, _Alloc>::iterator |

814 | vector<bool, _Alloc>:: |

815 | _M_erase(iterator __first, iterator __last) |

816 | { |

817 | if (__first != __last) |

818 | _M_erase_at_end(std::copy(__last, end(), __first)); |

819 | return __first; |

820 | } |

821 | |

822 | #if __cplusplus >= 201103L |

823 | template<typename _Alloc> |

824 | bool |

825 | vector<bool, _Alloc>:: |

826 | _M_shrink_to_fit() |

827 | { |

828 | if (capacity() - size() < int(_S_word_bit)) |

829 | return false; |

830 | __try |

831 | { |

832 | _M_reallocate(size()); |

833 | return true; |

834 | } |

835 | __catch(...) |

836 | { return false; } |

837 | } |

838 | #endif |

839 | |

840 | _GLIBCXX_END_NAMESPACE_CONTAINER |

841 | } // namespace std |

842 | |

843 | #if __cplusplus >= 201103L |

844 | |

845 | namespace std _GLIBCXX_VISIBILITY(default) |

846 | { |

847 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |

848 | |

849 | template<typename _Alloc> |

850 | size_t |

851 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |

852 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept |

853 | { |

854 | size_t __hash = 0; |

855 | using _GLIBCXX_STD_C::_S_word_bit; |

856 | using _GLIBCXX_STD_C::_Bit_type; |

857 | |

858 | const size_t __words = __b.size() / _S_word_bit; |

859 | if (__words) |

860 | { |

861 | const size_t __clength = __words * sizeof(_Bit_type); |

862 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |

863 | } |

864 | |

865 | const size_t __extrabits = __b.size() % _S_word_bit; |

866 | if (__extrabits) |

867 | { |

868 | _Bit_type __hiword = *__b._M_impl._M_finish._M_p; |

869 | __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); |

870 | |

871 | const size_t __clength |

872 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |

873 | if (__words) |

874 | __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); |

875 | else |

876 | __hash = std::_Hash_impl::hash(&__hiword, __clength); |

877 | } |

878 | |

879 | return __hash; |

880 | } |

881 | |

882 | _GLIBCXX_END_NAMESPACE_VERSION |

883 | } // namespace std |

884 | |

885 | #endif // C++11 |

886 | |

887 | #endif /* _VECTOR_TCC */ |

888 |