]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Vector implementation (out of line) -*- C++ -*- |
2 | ||
818ab71a | 3 | // Copyright (C) 2001-2016 Free Software Foundation, Inc. |
83144cfc PE |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
83144cfc PE |
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 | ||
748086b7 JJ |
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. | |
83144cfc | 19 | |
748086b7 JJ |
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/>. | |
83144cfc PE |
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 | ||
f910786b | 51 | /** @file bits/vector.tcc |
83144cfc | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{vector} |
83144cfc PE |
54 | */ |
55 | ||
3d7c150e BK |
56 | #ifndef _VECTOR_TCC |
57 | #define _VECTOR_TCC 1 | |
83144cfc | 58 | |
12ffa228 BK |
59 | namespace std _GLIBCXX_VISIBILITY(default) |
60 | { | |
61 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER | |
3cbc7af0 | 62 | |
af5fb6ab | 63 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 64 | void |
874e7baa | 65 | vector<_Tp, _Alloc>:: |
3971a4d2 | 66 | reserve(size_type __n) |
83144cfc | 67 | { |
48d1c3c5 | 68 | if (__n > this->max_size()) |
ba9119ec | 69 | __throw_length_error(__N("vector::reserve")); |
48d1c3c5 BK |
70 | if (this->capacity() < __n) |
71 | { | |
72 | const size_type __old_size = size(); | |
245a5fe5 | 73 | pointer __tmp = _M_allocate_and_copy(__n, |
74a2a1b4 PC |
74 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), |
75 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); | |
1985f1cd | 76 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 77 | _M_get_Tp_allocator()); |
03f9ea44 | 78 | _M_deallocate(this->_M_impl._M_start, |
874e7baa PC |
79 | this->_M_impl._M_end_of_storage |
80 | - this->_M_impl._M_start); | |
03f9ea44 DM |
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; | |
48d1c3c5 | 84 | } |
3971a4d2 | 85 | } |
ed6814f7 | 86 | |
734f5023 | 87 | #if __cplusplus >= 201103L |
4dc3e453 PC |
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 | { | |
bd8485dc JW |
96 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
97 | std::forward<_Args>(__args)...); | |
4dc3e453 PC |
98 | ++this->_M_impl._M_finish; |
99 | } | |
100 | else | |
cc2ba8e3 | 101 | _M_emplace_back_aux(std::forward<_Args>(__args)...); |
4dc3e453 PC |
102 | } |
103 | #endif | |
104 | ||
af5fb6ab | 105 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
106 | typename vector<_Tp, _Alloc>::iterator |
107 | vector<_Tp, _Alloc>:: | |
7b61c5a9 PC |
108 | #if __cplusplus >= 201103L |
109 | insert(const_iterator __position, const value_type& __x) | |
110 | #else | |
3971a4d2 | 111 | insert(iterator __position, const value_type& __x) |
7b61c5a9 | 112 | #endif |
3971a4d2 | 113 | { |
43da93a7 | 114 | const size_type __n = __position - begin(); |
874e7baa PC |
115 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage |
116 | && __position == end()) | |
117 | { | |
bd8485dc | 118 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x); |
874e7baa PC |
119 | ++this->_M_impl._M_finish; |
120 | } | |
83144cfc | 121 | else |
812e8c79 | 122 | { |
734f5023 | 123 | #if __cplusplus >= 201103L |
bbf264c9 | 124 | const auto __pos = begin() + (__position - cbegin()); |
812e8c79 PC |
125 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
126 | { | |
127 | _Tp __x_copy = __x; | |
bbf264c9 | 128 | _M_insert_aux(__pos, std::move(__x_copy)); |
812e8c79 PC |
129 | } |
130 | else | |
bbf264c9 JW |
131 | _M_insert_aux(__pos, __x); |
132 | #else | |
133 | _M_insert_aux(__position, __x); | |
812e8c79 | 134 | #endif |
812e8c79 | 135 | } |
bc9053ab | 136 | return iterator(this->_M_impl._M_start + __n); |
83144cfc | 137 | } |
ed6814f7 | 138 | |
af5fb6ab | 139 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
140 | typename vector<_Tp, _Alloc>::iterator |
141 | vector<_Tp, _Alloc>:: | |
94938aec | 142 | _M_erase(iterator __position) |
83144cfc | 143 | { |
3971a4d2 | 144 | if (__position + 1 != end()) |
245a5fe5 | 145 | _GLIBCXX_MOVE3(__position + 1, end(), __position); |
03f9ea44 | 146 | --this->_M_impl._M_finish; |
bd8485dc | 147 | _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); |
3971a4d2 | 148 | return __position; |
83144cfc | 149 | } |
ed6814f7 | 150 | |
af5fb6ab | 151 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
152 | typename vector<_Tp, _Alloc>::iterator |
153 | vector<_Tp, _Alloc>:: | |
94938aec | 154 | _M_erase(iterator __first, iterator __last) |
83144cfc | 155 | { |
a7cee01d PC |
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 | } | |
3971a4d2 | 162 | return __first; |
83144cfc | 163 | } |
ed6814f7 | 164 | |
af5fb6ab | 165 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
166 | vector<_Tp, _Alloc>& |
167 | vector<_Tp, _Alloc>:: | |
168 | operator=(const vector<_Tp, _Alloc>& __x) | |
83144cfc | 169 | { |
3971a4d2 | 170 | if (&__x != this) |
874e7baa | 171 | { |
734f5023 | 172 | #if __cplusplus >= 201103L |
bd8485dc JW |
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); | |
68d047cb FD |
183 | this->_M_impl._M_start = nullptr; |
184 | this->_M_impl._M_finish = nullptr; | |
185 | this->_M_impl._M_end_of_storage = nullptr; | |
bd8485dc JW |
186 | } |
187 | std::__alloc_on_copy(_M_get_Tp_allocator(), | |
188 | __x._M_get_Tp_allocator()); | |
189 | } | |
190 | #endif | |
874e7baa PC |
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()); | |
1985f1cd | 196 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 197 | _M_get_Tp_allocator()); |
874e7baa PC |
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 | { | |
bc9053ab PC |
206 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |
207 | end(), _M_get_Tp_allocator()); | |
874e7baa PC |
208 | } |
209 | else | |
210 | { | |
bc9053ab | 211 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |
874e7baa | 212 | this->_M_impl._M_start); |
bc9053ab PC |
213 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |
214 | __x._M_impl._M_finish, | |
215 | this->_M_impl._M_finish, | |
4fd20a8f | 216 | _M_get_Tp_allocator()); |
874e7baa PC |
217 | } |
218 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; | |
219 | } | |
3971a4d2 | 220 | return *this; |
83144cfc | 221 | } |
ed6814f7 | 222 | |
af5fb6ab | 223 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 224 | void |
874e7baa | 225 | vector<_Tp, _Alloc>:: |
3971a4d2 | 226 | _M_fill_assign(size_t __n, const value_type& __val) |
83144cfc | 227 | { |
3971a4d2 | 228 | if (__n > capacity()) |
874e7baa | 229 | { |
4fd20a8f | 230 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |
c5b26147 | 231 | __tmp._M_impl._M_swap_data(this->_M_impl); |
874e7baa | 232 | } |
3971a4d2 | 233 | else if (__n > size()) |
874e7baa PC |
234 | { |
235 | std::fill(begin(), end(), __val); | |
e51cf2f5 JW |
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()); | |
874e7baa | 240 | } |
3971a4d2 | 241 | else |
bc9053ab | 242 | _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); |
83144cfc | 243 | } |
ed6814f7 | 244 | |
874e7baa PC |
245 | template<typename _Tp, typename _Alloc> |
246 | template<typename _InputIterator> | |
247 | void | |
248 | vector<_Tp, _Alloc>:: | |
249 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
6323b34e | 250 | std::input_iterator_tag) |
3971a4d2 | 251 | { |
bc9053ab PC |
252 | pointer __cur(this->_M_impl._M_start); |
253 | for (; __first != __last && __cur != this->_M_impl._M_finish; | |
254 | ++__cur, ++__first) | |
874e7baa PC |
255 | *__cur = *__first; |
256 | if (__first == __last) | |
bc9053ab | 257 | _M_erase_at_end(__cur); |
874e7baa PC |
258 | else |
259 | insert(end(), __first, __last); | |
3971a4d2 | 260 | } |
874e7baa PC |
261 | |
262 | template<typename _Tp, typename _Alloc> | |
263 | template<typename _ForwardIterator> | |
264 | void | |
43da93a7 | 265 | vector<_Tp, _Alloc>:: |
874e7baa | 266 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
6323b34e | 267 | std::forward_iterator_tag) |
3971a4d2 | 268 | { |
43da93a7 | 269 | const size_type __len = std::distance(__first, __last); |
874e7baa PC |
270 | |
271 | if (__len > capacity()) | |
272 | { | |
273 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); | |
1985f1cd | 274 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 275 | _M_get_Tp_allocator()); |
874e7baa PC |
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) | |
bc9053ab | 284 | _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); |
874e7baa PC |
285 | else |
286 | { | |
287 | _ForwardIterator __mid = __first; | |
288 | std::advance(__mid, size()); | |
289 | std::copy(__first, __mid, this->_M_impl._M_start); | |
1985f1cd MA |
290 | this->_M_impl._M_finish = |
291 | std::__uninitialized_copy_a(__mid, __last, | |
292 | this->_M_impl._M_finish, | |
4fd20a8f | 293 | _M_get_Tp_allocator()); |
874e7baa | 294 | } |
3971a4d2 | 295 | } |
ed6814f7 | 296 | |
734f5023 | 297 | #if __cplusplus >= 201103L |
6eef7402 CJ |
298 | template<typename _Tp, typename _Alloc> |
299 | template<typename... _Args> | |
300 | typename vector<_Tp, _Alloc>::iterator | |
301 | vector<_Tp, _Alloc>:: | |
7b61c5a9 | 302 | emplace(const_iterator __position, _Args&&... __args) |
6eef7402 CJ |
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 | { | |
bd8485dc JW |
308 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
309 | std::forward<_Args>(__args)...); | |
6eef7402 CJ |
310 | ++this->_M_impl._M_finish; |
311 | } | |
312 | else | |
bbf264c9 | 313 | _M_insert_aux(begin() + (__position - cbegin()), |
7b61c5a9 | 314 | std::forward<_Args>(__args)...); |
6eef7402 CJ |
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) | |
6eef7402 | 323 | #else |
af5fb6ab | 324 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 325 | void |
43da93a7 | 326 | vector<_Tp, _Alloc>:: |
3971a4d2 | 327 | _M_insert_aux(iterator __position, const _Tp& __x) |
6eef7402 | 328 | #endif |
812e8c79 | 329 | { |
03f9ea44 | 330 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
874e7baa | 331 | { |
bd8485dc JW |
332 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
333 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish | |
334 | - 1))); | |
874e7baa | 335 | ++this->_M_impl._M_finish; |
734f5023 | 336 | #if __cplusplus < 201103L |
874e7baa | 337 | _Tp __x_copy = __x; |
6eef7402 CJ |
338 | #endif |
339 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), | |
340 | this->_M_impl._M_finish - 2, | |
341 | this->_M_impl._M_finish - 1); | |
734f5023 | 342 | #if __cplusplus < 201103L |
812e8c79 PC |
343 | *__position = __x_copy; |
344 | #else | |
345 | *__position = _Tp(std::forward<_Args>(__args)...); | |
346 | #endif | |
874e7baa | 347 | } |
83144cfc | 348 | else |
874e7baa | 349 | { |
be1088fa ML |
350 | const size_type __len = |
351 | _M_check_len(size_type(1), "vector::_M_insert_aux"); | |
d2219f89 | 352 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
353 | pointer __new_start(this->_M_allocate(__len)); |
354 | pointer __new_finish(__new_start); | |
bc2631e0 | 355 | __try |
874e7baa | 356 | { |
d2219f89 PC |
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). | |
bd8485dc JW |
361 | _Alloc_traits::construct(this->_M_impl, |
362 | __new_start + __elems_before, | |
734f5023 | 363 | #if __cplusplus >= 201103L |
bd8485dc | 364 | std::forward<_Args>(__args)...); |
d2219f89 | 365 | #else |
bd8485dc | 366 | __x); |
812e8c79 | 367 | #endif |
5b99e0a0 | 368 | __new_finish = pointer(); |
d2219f89 | 369 | |
74a2a1b4 PC |
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 | ||
874e7baa | 375 | ++__new_finish; |
d2219f89 | 376 | |
74a2a1b4 PC |
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()); | |
996e5395 | 381 | } |
bc2631e0 | 382 | __catch(...) |
874e7baa | 383 | { |
d2219f89 | 384 | if (!__new_finish) |
bd8485dc JW |
385 | _Alloc_traits::destroy(this->_M_impl, |
386 | __new_start + __elems_before); | |
d2219f89 PC |
387 | else |
388 | std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); | |
bc9053ab | 389 | _M_deallocate(__new_start, __len); |
874e7baa PC |
390 | __throw_exception_again; |
391 | } | |
bc9053ab PC |
392 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
393 | _M_get_Tp_allocator()); | |
874e7baa PC |
394 | _M_deallocate(this->_M_impl._M_start, |
395 | this->_M_impl._M_end_of_storage | |
396 | - this->_M_impl._M_start); | |
bc9053ab PC |
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; | |
874e7baa | 400 | } |
83144cfc | 401 | } |
64ebadac | 402 | |
734f5023 | 403 | #if __cplusplus >= 201103L |
cc2ba8e3 PC |
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)...); | |
5b99e0a0 | 418 | __new_finish = pointer(); |
cc2ba8e3 PC |
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 | ||
af5fb6ab | 447 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 448 | void |
43da93a7 | 449 | vector<_Tp, _Alloc>:: |
3971a4d2 PE |
450 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |
451 | { | |
452 | if (__n != 0) | |
874e7baa PC |
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; | |
bc9053ab | 459 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
460 | if (__elems_after > __n) |
461 | { | |
6eef7402 | 462 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
463 | this->_M_impl._M_finish, |
464 | this->_M_impl._M_finish, | |
4fd20a8f | 465 | _M_get_Tp_allocator()); |
874e7baa | 466 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
467 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
468 | __old_finish - __n, __old_finish); | |
bc9053ab PC |
469 | std::fill(__position.base(), __position.base() + __n, |
470 | __x_copy); | |
874e7baa PC |
471 | } |
472 | else | |
473 | { | |
e51cf2f5 JW |
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()); | |
6eef7402 | 479 | std::__uninitialized_move_a(__position.base(), __old_finish, |
1985f1cd | 480 | this->_M_impl._M_finish, |
4fd20a8f | 481 | _M_get_Tp_allocator()); |
874e7baa | 482 | this->_M_impl._M_finish += __elems_after; |
bc9053ab | 483 | std::fill(__position.base(), __old_finish, __x_copy); |
874e7baa PC |
484 | } |
485 | } | |
486 | else | |
487 | { | |
be1088fa ML |
488 | const size_type __len = |
489 | _M_check_len(__n, "vector::_M_fill_insert"); | |
d2219f89 | 490 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
491 | pointer __new_start(this->_M_allocate(__len)); |
492 | pointer __new_finish(__new_start); | |
bc2631e0 | 493 | __try |
874e7baa | 494 | { |
d2219f89 PC |
495 | // See _M_insert_aux above. |
496 | std::__uninitialized_fill_n_a(__new_start + __elems_before, | |
497 | __n, __x, | |
498 | _M_get_Tp_allocator()); | |
5b99e0a0 | 499 | __new_finish = pointer(); |
d2219f89 | 500 | |
74a2a1b4 PC |
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 | ||
368b7a30 | 506 | __new_finish += __n; |
d2219f89 | 507 | |
74a2a1b4 PC |
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()); | |
874e7baa | 512 | } |
bc2631e0 | 513 | __catch(...) |
874e7baa | 514 | { |
d2219f89 PC |
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()); | |
bc9053ab | 522 | _M_deallocate(__new_start, __len); |
874e7baa PC |
523 | __throw_exception_again; |
524 | } | |
1985f1cd | 525 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 526 | _M_get_Tp_allocator()); |
874e7baa PC |
527 | _M_deallocate(this->_M_impl._M_start, |
528 | this->_M_impl._M_end_of_storage | |
529 | - this->_M_impl._M_start); | |
bc9053ab PC |
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; | |
874e7baa PC |
533 | } |
534 | } | |
3971a4d2 | 535 | } |
ed6814f7 | 536 | |
734f5023 | 537 | #if __cplusplus >= 201103L |
dc2cf706 PC |
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 | { | |
e51cf2f5 JW |
548 | this->_M_impl._M_finish = |
549 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, | |
550 | __n, _M_get_Tp_allocator()); | |
dc2cf706 PC |
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 | { | |
74a2a1b4 PC |
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()); | |
e51cf2f5 JW |
565 | __new_finish = |
566 | std::__uninitialized_default_n_a(__new_finish, __n, | |
567 | _M_get_Tp_allocator()); | |
dc2cf706 PC |
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 | } | |
8a752dfe FD |
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 | } | |
dc2cf706 PC |
597 | #endif |
598 | ||
232c4925 PC |
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 | } | |
ed6814f7 | 612 | |
874e7baa PC |
613 | template<typename _Tp, typename _Alloc> |
614 | template<typename _ForwardIterator> | |
615 | void | |
43da93a7 | 616 | vector<_Tp, _Alloc>:: |
996e5395 | 617 | _M_range_insert(iterator __position, _ForwardIterator __first, |
6323b34e | 618 | _ForwardIterator __last, std::forward_iterator_tag) |
3971a4d2 | 619 | { |
874e7baa PC |
620 | if (__first != __last) |
621 | { | |
43da93a7 | 622 | const size_type __n = std::distance(__first, __last); |
874e7baa PC |
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; | |
bc9053ab | 627 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
628 | if (__elems_after > __n) |
629 | { | |
6eef7402 | 630 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
631 | this->_M_impl._M_finish, |
632 | this->_M_impl._M_finish, | |
4fd20a8f | 633 | _M_get_Tp_allocator()); |
874e7baa | 634 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
635 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
636 | __old_finish - __n, __old_finish); | |
874e7baa PC |
637 | std::copy(__first, __last, __position); |
638 | } | |
639 | else | |
640 | { | |
641 | _ForwardIterator __mid = __first; | |
642 | std::advance(__mid, __elems_after); | |
1985f1cd MA |
643 | std::__uninitialized_copy_a(__mid, __last, |
644 | this->_M_impl._M_finish, | |
4fd20a8f | 645 | _M_get_Tp_allocator()); |
874e7baa | 646 | this->_M_impl._M_finish += __n - __elems_after; |
6eef7402 | 647 | std::__uninitialized_move_a(__position.base(), |
bc9053ab | 648 | __old_finish, |
1985f1cd | 649 | this->_M_impl._M_finish, |
4fd20a8f | 650 | _M_get_Tp_allocator()); |
874e7baa PC |
651 | this->_M_impl._M_finish += __elems_after; |
652 | std::copy(__first, __mid, __position); | |
653 | } | |
654 | } | |
655 | else | |
656 | { | |
be1088fa ML |
657 | const size_type __len = |
658 | _M_check_len(__n, "vector::_M_range_insert"); | |
bc9053ab PC |
659 | pointer __new_start(this->_M_allocate(__len)); |
660 | pointer __new_finish(__new_start); | |
bc2631e0 | 661 | __try |
874e7baa | 662 | { |
74a2a1b4 PC |
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()); | |
874e7baa | 675 | } |
bc2631e0 | 676 | __catch(...) |
874e7baa | 677 | { |
bc9053ab | 678 | std::_Destroy(__new_start, __new_finish, |
4fd20a8f | 679 | _M_get_Tp_allocator()); |
bc9053ab | 680 | _M_deallocate(__new_start, __len); |
874e7baa PC |
681 | __throw_exception_again; |
682 | } | |
1985f1cd | 683 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 684 | _M_get_Tp_allocator()); |
874e7baa PC |
685 | _M_deallocate(this->_M_impl._M_start, |
686 | this->_M_impl._M_end_of_storage | |
687 | - this->_M_impl._M_start); | |
bc9053ab PC |
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; | |
874e7baa PC |
691 | } |
692 | } | |
83144cfc | 693 | } |
3cbc7af0 | 694 | |
232c4925 PC |
695 | |
696 | // vector<bool> | |
c62df8fd PC |
697 | template<typename _Alloc> |
698 | void | |
699 | vector<bool, _Alloc>:: | |
8a752dfe | 700 | _M_reallocate(size_type __n) |
c62df8fd | 701 | { |
ccd615e3 JW |
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); | |
8a752dfe | 705 | this->_M_deallocate(); |
ccd615e3 | 706 | this->_M_impl._M_start = __start; |
8a752dfe | 707 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); |
c62df8fd PC |
708 | } |
709 | ||
232c4925 PC |
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 | { | |
be1088fa ML |
726 | const size_type __len = |
727 | _M_check_len(__n, "vector<bool>::_M_fill_insert"); | |
ccd615e3 JW |
728 | _Bit_pointer __q = this->_M_allocate(__len); |
729 | iterator __start(std::__addressof(*__q), 0); | |
730 | iterator __i = _M_copy_aligned(begin(), __position, __start); | |
232c4925 PC |
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(); | |
8a752dfe | 735 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 736 | this->_M_impl._M_start = __start; |
232c4925 PC |
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 | { | |
be1088fa ML |
760 | const size_type __len = |
761 | _M_check_len(__n, "vector<bool>::_M_insert_range"); | |
ccd615e3 JW |
762 | _Bit_pointer __q = this->_M_allocate(__len); |
763 | iterator __start(std::__addressof(*__q), 0); | |
764 | iterator __i = _M_copy_aligned(begin(), __position, __start); | |
232c4925 PC |
765 | __i = std::copy(__first, __last, __i); |
766 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
767 | this->_M_deallocate(); | |
8a752dfe | 768 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 769 | this->_M_impl._M_start = __start; |
232c4925 PC |
770 | } |
771 | } | |
772 | } | |
773 | ||
774 | template<typename _Alloc> | |
775 | void | |
776 | vector<bool, _Alloc>:: | |
777 | _M_insert_aux(iterator __position, bool __x) | |
778 | { | |
ccd615e3 | 779 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) |
232c4925 PC |
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 | { | |
be1088fa ML |
788 | const size_type __len = |
789 | _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); | |
ccd615e3 JW |
790 | _Bit_pointer __q = this->_M_allocate(__len); |
791 | iterator __start(std::__addressof(*__q), 0); | |
792 | iterator __i = _M_copy_aligned(begin(), __position, __start); | |
232c4925 PC |
793 | *__i++ = __x; |
794 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
795 | this->_M_deallocate(); | |
8a752dfe | 796 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 797 | this->_M_impl._M_start = __start; |
232c4925 PC |
798 | } |
799 | } | |
800 | ||
94938aec PC |
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 | ||
734f5023 | 822 | #if __cplusplus >= 201103L |
8a752dfe FD |
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 | ||
12ffa228 BK |
840 | _GLIBCXX_END_NAMESPACE_CONTAINER |
841 | } // namespace std | |
83144cfc | 842 | |
734f5023 | 843 | #if __cplusplus >= 201103L |
f54e96d9 | 844 | |
12ffa228 BK |
845 | namespace std _GLIBCXX_VISIBILITY(default) |
846 | { | |
847 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
f54e96d9 PC |
848 | |
849 | template<typename _Alloc> | |
850 | size_t | |
12ffa228 | 851 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |
72f1c34b | 852 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept |
f54e96d9 PC |
853 | { |
854 | size_t __hash = 0; | |
12ffa228 BK |
855 | using _GLIBCXX_STD_C::_S_word_bit; |
856 | using _GLIBCXX_STD_C::_Bit_type; | |
f54e96d9 PC |
857 | |
858 | const size_t __words = __b.size() / _S_word_bit; | |
859 | if (__words) | |
860 | { | |
055f6a47 | 861 | const size_t __clength = __words * sizeof(_Bit_type); |
e7f72940 | 862 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |
f54e96d9 PC |
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 | ||
055f6a47 | 871 | const size_t __clength |
f54e96d9 PC |
872 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
873 | if (__words) | |
e7f72940 | 874 | __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); |
f54e96d9 | 875 | else |
e7f72940 | 876 | __hash = std::_Hash_impl::hash(&__hiword, __clength); |
f54e96d9 PC |
877 | } |
878 | ||
879 | return __hash; | |
880 | } | |
881 | ||
12ffa228 BK |
882 | _GLIBCXX_END_NAMESPACE_VERSION |
883 | } // namespace std | |
f54e96d9 | 884 | |
734f5023 | 885 | #endif // C++11 |
f54e96d9 | 886 | |
3d7c150e | 887 | #endif /* _VECTOR_TCC */ |