]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Vector implementation (out of line) -*- C++ -*- |
2 | ||
12ffa228 BK |
3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, |
4 | // 2011 Free Software Foundation, Inc. | |
83144cfc PE |
5 | // |
6 | // This file is part of the GNU ISO C++ Library. This library is free | |
7 | // software; you can redistribute it and/or modify it under the | |
8 | // terms of the GNU General Public License as published by the | |
748086b7 | 9 | // Free Software Foundation; either version 3, or (at your option) |
83144cfc PE |
10 | // any later version. |
11 | ||
12 | // This library is distributed in the hope that it will be useful, | |
13 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
15 | // GNU General Public License for more details. | |
16 | ||
748086b7 JJ |
17 | // Under Section 7 of GPL version 3, you are granted additional |
18 | // permissions described in the GCC Runtime Library Exception, version | |
19 | // 3.1, as published by the Free Software Foundation. | |
83144cfc | 20 | |
748086b7 JJ |
21 | // You should have received a copy of the GNU General Public License and |
22 | // a copy of the GCC Runtime Library Exception along with this program; | |
23 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see | |
24 | // <http://www.gnu.org/licenses/>. | |
83144cfc PE |
25 | |
26 | /* | |
27 | * | |
28 | * Copyright (c) 1994 | |
29 | * Hewlett-Packard Company | |
30 | * | |
31 | * Permission to use, copy, modify, distribute and sell this software | |
32 | * and its documentation for any purpose is hereby granted without fee, | |
33 | * provided that the above copyright notice appear in all copies and | |
34 | * that both that copyright notice and this permission notice appear | |
35 | * in supporting documentation. Hewlett-Packard Company makes no | |
36 | * representations about the suitability of this software for any | |
37 | * purpose. It is provided "as is" without express or implied warranty. | |
38 | * | |
39 | * | |
40 | * Copyright (c) 1996 | |
41 | * Silicon Graphics Computer Systems, Inc. | |
42 | * | |
43 | * Permission to use, copy, modify, distribute and sell this software | |
44 | * and its documentation for any purpose is hereby granted without fee, | |
45 | * provided that the above copyright notice appear in all copies and | |
46 | * that both that copyright notice and this permission notice appear | |
47 | * in supporting documentation. Silicon Graphics makes no | |
48 | * representations about the suitability of this software for any | |
49 | * purpose. It is provided "as is" without express or implied warranty. | |
50 | */ | |
51 | ||
f910786b | 52 | /** @file bits/vector.tcc |
83144cfc | 53 | * This is an internal header file, included by other library headers. |
f910786b | 54 | * Do not attempt to use it directly. @headername{vector} |
83144cfc PE |
55 | */ |
56 | ||
3d7c150e BK |
57 | #ifndef _VECTOR_TCC |
58 | #define _VECTOR_TCC 1 | |
83144cfc | 59 | |
12ffa228 BK |
60 | namespace std _GLIBCXX_VISIBILITY(default) |
61 | { | |
62 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER | |
3cbc7af0 | 63 | |
af5fb6ab | 64 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 65 | void |
874e7baa | 66 | vector<_Tp, _Alloc>:: |
3971a4d2 | 67 | reserve(size_type __n) |
83144cfc | 68 | { |
48d1c3c5 | 69 | if (__n > this->max_size()) |
ba9119ec | 70 | __throw_length_error(__N("vector::reserve")); |
48d1c3c5 BK |
71 | if (this->capacity() < __n) |
72 | { | |
73 | const size_type __old_size = size(); | |
245a5fe5 | 74 | pointer __tmp = _M_allocate_and_copy(__n, |
74a2a1b4 PC |
75 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), |
76 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); | |
1985f1cd | 77 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 78 | _M_get_Tp_allocator()); |
03f9ea44 | 79 | _M_deallocate(this->_M_impl._M_start, |
874e7baa PC |
80 | this->_M_impl._M_end_of_storage |
81 | - this->_M_impl._M_start); | |
03f9ea44 DM |
82 | this->_M_impl._M_start = __tmp; |
83 | this->_M_impl._M_finish = __tmp + __old_size; | |
84 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; | |
48d1c3c5 | 85 | } |
3971a4d2 | 86 | } |
ed6814f7 | 87 | |
4dc3e453 PC |
88 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
89 | template<typename _Tp, typename _Alloc> | |
90 | template<typename... _Args> | |
91 | void | |
92 | vector<_Tp, _Alloc>:: | |
93 | emplace_back(_Args&&... __args) | |
94 | { | |
95 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) | |
96 | { | |
97 | this->_M_impl.construct(this->_M_impl._M_finish, | |
98 | std::forward<_Args>(__args)...); | |
99 | ++this->_M_impl._M_finish; | |
100 | } | |
101 | else | |
102 | _M_insert_aux(end(), std::forward<_Args>(__args)...); | |
103 | } | |
104 | #endif | |
105 | ||
af5fb6ab | 106 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
107 | typename vector<_Tp, _Alloc>::iterator |
108 | vector<_Tp, _Alloc>:: | |
3971a4d2 PE |
109 | insert(iterator __position, const value_type& __x) |
110 | { | |
43da93a7 | 111 | const size_type __n = __position - begin(); |
874e7baa PC |
112 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage |
113 | && __position == end()) | |
114 | { | |
1985f1cd | 115 | this->_M_impl.construct(this->_M_impl._M_finish, __x); |
874e7baa PC |
116 | ++this->_M_impl._M_finish; |
117 | } | |
83144cfc | 118 | else |
812e8c79 PC |
119 | { |
120 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ | |
121 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) | |
122 | { | |
123 | _Tp __x_copy = __x; | |
124 | _M_insert_aux(__position, std::move(__x_copy)); | |
125 | } | |
126 | else | |
127 | #endif | |
128 | _M_insert_aux(__position, __x); | |
129 | } | |
bc9053ab | 130 | return iterator(this->_M_impl._M_start + __n); |
83144cfc | 131 | } |
ed6814f7 | 132 | |
af5fb6ab | 133 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
134 | typename vector<_Tp, _Alloc>::iterator |
135 | vector<_Tp, _Alloc>:: | |
3971a4d2 | 136 | erase(iterator __position) |
83144cfc | 137 | { |
3971a4d2 | 138 | if (__position + 1 != end()) |
245a5fe5 | 139 | _GLIBCXX_MOVE3(__position + 1, end(), __position); |
03f9ea44 | 140 | --this->_M_impl._M_finish; |
1985f1cd | 141 | this->_M_impl.destroy(this->_M_impl._M_finish); |
3971a4d2 | 142 | return __position; |
83144cfc | 143 | } |
ed6814f7 | 144 | |
af5fb6ab | 145 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
146 | typename vector<_Tp, _Alloc>::iterator |
147 | vector<_Tp, _Alloc>:: | |
3971a4d2 | 148 | erase(iterator __first, iterator __last) |
83144cfc | 149 | { |
bc9053ab | 150 | if (__last != end()) |
245a5fe5 | 151 | _GLIBCXX_MOVE3(__last, end(), __first); |
bc9053ab | 152 | _M_erase_at_end(__first.base() + (end() - __last)); |
3971a4d2 | 153 | return __first; |
83144cfc | 154 | } |
ed6814f7 | 155 | |
af5fb6ab | 156 | template<typename _Tp, typename _Alloc> |
874e7baa PC |
157 | vector<_Tp, _Alloc>& |
158 | vector<_Tp, _Alloc>:: | |
159 | operator=(const vector<_Tp, _Alloc>& __x) | |
83144cfc | 160 | { |
3971a4d2 | 161 | if (&__x != this) |
874e7baa PC |
162 | { |
163 | const size_type __xlen = __x.size(); | |
164 | if (__xlen > capacity()) | |
165 | { | |
166 | pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), | |
167 | __x.end()); | |
1985f1cd | 168 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 169 | _M_get_Tp_allocator()); |
874e7baa PC |
170 | _M_deallocate(this->_M_impl._M_start, |
171 | this->_M_impl._M_end_of_storage | |
172 | - this->_M_impl._M_start); | |
173 | this->_M_impl._M_start = __tmp; | |
174 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; | |
175 | } | |
176 | else if (size() >= __xlen) | |
177 | { | |
bc9053ab PC |
178 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |
179 | end(), _M_get_Tp_allocator()); | |
874e7baa PC |
180 | } |
181 | else | |
182 | { | |
bc9053ab | 183 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |
874e7baa | 184 | this->_M_impl._M_start); |
bc9053ab PC |
185 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |
186 | __x._M_impl._M_finish, | |
187 | this->_M_impl._M_finish, | |
4fd20a8f | 188 | _M_get_Tp_allocator()); |
874e7baa PC |
189 | } |
190 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; | |
191 | } | |
3971a4d2 | 192 | return *this; |
83144cfc | 193 | } |
ed6814f7 | 194 | |
af5fb6ab | 195 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 196 | void |
874e7baa | 197 | vector<_Tp, _Alloc>:: |
3971a4d2 | 198 | _M_fill_assign(size_t __n, const value_type& __val) |
83144cfc | 199 | { |
3971a4d2 | 200 | if (__n > capacity()) |
874e7baa | 201 | { |
4fd20a8f | 202 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |
874e7baa PC |
203 | __tmp.swap(*this); |
204 | } | |
3971a4d2 | 205 | else if (__n > size()) |
874e7baa PC |
206 | { |
207 | std::fill(begin(), end(), __val); | |
1985f1cd MA |
208 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |
209 | __n - size(), __val, | |
4fd20a8f | 210 | _M_get_Tp_allocator()); |
368b7a30 | 211 | this->_M_impl._M_finish += __n - size(); |
874e7baa | 212 | } |
3971a4d2 | 213 | else |
bc9053ab | 214 | _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); |
83144cfc | 215 | } |
ed6814f7 | 216 | |
874e7baa PC |
217 | template<typename _Tp, typename _Alloc> |
218 | template<typename _InputIterator> | |
219 | void | |
220 | vector<_Tp, _Alloc>:: | |
221 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
6323b34e | 222 | std::input_iterator_tag) |
3971a4d2 | 223 | { |
bc9053ab PC |
224 | pointer __cur(this->_M_impl._M_start); |
225 | for (; __first != __last && __cur != this->_M_impl._M_finish; | |
226 | ++__cur, ++__first) | |
874e7baa PC |
227 | *__cur = *__first; |
228 | if (__first == __last) | |
bc9053ab | 229 | _M_erase_at_end(__cur); |
874e7baa PC |
230 | else |
231 | insert(end(), __first, __last); | |
3971a4d2 | 232 | } |
874e7baa PC |
233 | |
234 | template<typename _Tp, typename _Alloc> | |
235 | template<typename _ForwardIterator> | |
236 | void | |
43da93a7 | 237 | vector<_Tp, _Alloc>:: |
874e7baa | 238 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
6323b34e | 239 | std::forward_iterator_tag) |
3971a4d2 | 240 | { |
43da93a7 | 241 | const size_type __len = std::distance(__first, __last); |
874e7baa PC |
242 | |
243 | if (__len > capacity()) | |
244 | { | |
245 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); | |
1985f1cd | 246 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 247 | _M_get_Tp_allocator()); |
874e7baa PC |
248 | _M_deallocate(this->_M_impl._M_start, |
249 | this->_M_impl._M_end_of_storage | |
250 | - this->_M_impl._M_start); | |
251 | this->_M_impl._M_start = __tmp; | |
252 | this->_M_impl._M_finish = this->_M_impl._M_start + __len; | |
253 | this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; | |
254 | } | |
255 | else if (size() >= __len) | |
bc9053ab | 256 | _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); |
874e7baa PC |
257 | else |
258 | { | |
259 | _ForwardIterator __mid = __first; | |
260 | std::advance(__mid, size()); | |
261 | std::copy(__first, __mid, this->_M_impl._M_start); | |
1985f1cd MA |
262 | this->_M_impl._M_finish = |
263 | std::__uninitialized_copy_a(__mid, __last, | |
264 | this->_M_impl._M_finish, | |
4fd20a8f | 265 | _M_get_Tp_allocator()); |
874e7baa | 266 | } |
3971a4d2 | 267 | } |
ed6814f7 | 268 | |
6eef7402 CJ |
269 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
270 | template<typename _Tp, typename _Alloc> | |
271 | template<typename... _Args> | |
272 | typename vector<_Tp, _Alloc>::iterator | |
273 | vector<_Tp, _Alloc>:: | |
274 | emplace(iterator __position, _Args&&... __args) | |
275 | { | |
276 | const size_type __n = __position - begin(); | |
277 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage | |
278 | && __position == end()) | |
279 | { | |
280 | this->_M_impl.construct(this->_M_impl._M_finish, | |
281 | std::forward<_Args>(__args)...); | |
282 | ++this->_M_impl._M_finish; | |
283 | } | |
284 | else | |
285 | _M_insert_aux(__position, std::forward<_Args>(__args)...); | |
286 | return iterator(this->_M_impl._M_start + __n); | |
287 | } | |
288 | ||
289 | template<typename _Tp, typename _Alloc> | |
290 | template<typename... _Args> | |
291 | void | |
292 | vector<_Tp, _Alloc>:: | |
293 | _M_insert_aux(iterator __position, _Args&&... __args) | |
6eef7402 | 294 | #else |
af5fb6ab | 295 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 296 | void |
43da93a7 | 297 | vector<_Tp, _Alloc>:: |
3971a4d2 | 298 | _M_insert_aux(iterator __position, const _Tp& __x) |
6eef7402 | 299 | #endif |
812e8c79 | 300 | { |
03f9ea44 | 301 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
874e7baa | 302 | { |
1985f1cd | 303 | this->_M_impl.construct(this->_M_impl._M_finish, |
6eef7402 CJ |
304 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish |
305 | - 1))); | |
874e7baa | 306 | ++this->_M_impl._M_finish; |
6eef7402 | 307 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
874e7baa | 308 | _Tp __x_copy = __x; |
6eef7402 CJ |
309 | #endif |
310 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), | |
311 | this->_M_impl._M_finish - 2, | |
312 | this->_M_impl._M_finish - 1); | |
812e8c79 PC |
313 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
314 | *__position = __x_copy; | |
315 | #else | |
316 | *__position = _Tp(std::forward<_Args>(__args)...); | |
317 | #endif | |
874e7baa | 318 | } |
83144cfc | 319 | else |
874e7baa | 320 | { |
be1088fa ML |
321 | const size_type __len = |
322 | _M_check_len(size_type(1), "vector::_M_insert_aux"); | |
d2219f89 | 323 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
324 | pointer __new_start(this->_M_allocate(__len)); |
325 | pointer __new_finish(__new_start); | |
bc2631e0 | 326 | __try |
874e7baa | 327 | { |
d2219f89 PC |
328 | // The order of the three operations is dictated by the C++0x |
329 | // case, where the moves could alter a new element belonging | |
330 | // to the existing vector. This is an issue only for callers | |
331 | // taking the element by const lvalue ref (see 23.1/13). | |
332 | this->_M_impl.construct(__new_start + __elems_before, | |
812e8c79 | 333 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
812e8c79 | 334 | std::forward<_Args>(__args)...); |
d2219f89 PC |
335 | #else |
336 | __x); | |
812e8c79 | 337 | #endif |
d2219f89 PC |
338 | __new_finish = 0; |
339 | ||
74a2a1b4 PC |
340 | __new_finish |
341 | = std::__uninitialized_move_if_noexcept_a | |
342 | (this->_M_impl._M_start, __position.base(), | |
343 | __new_start, _M_get_Tp_allocator()); | |
344 | ||
874e7baa | 345 | ++__new_finish; |
d2219f89 | 346 | |
74a2a1b4 PC |
347 | __new_finish |
348 | = std::__uninitialized_move_if_noexcept_a | |
349 | (__position.base(), this->_M_impl._M_finish, | |
350 | __new_finish, _M_get_Tp_allocator()); | |
996e5395 | 351 | } |
bc2631e0 | 352 | __catch(...) |
874e7baa | 353 | { |
d2219f89 PC |
354 | if (!__new_finish) |
355 | this->_M_impl.destroy(__new_start + __elems_before); | |
356 | else | |
357 | std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); | |
bc9053ab | 358 | _M_deallocate(__new_start, __len); |
874e7baa PC |
359 | __throw_exception_again; |
360 | } | |
bc9053ab PC |
361 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
362 | _M_get_Tp_allocator()); | |
874e7baa PC |
363 | _M_deallocate(this->_M_impl._M_start, |
364 | this->_M_impl._M_end_of_storage | |
365 | - this->_M_impl._M_start); | |
bc9053ab PC |
366 | this->_M_impl._M_start = __new_start; |
367 | this->_M_impl._M_finish = __new_finish; | |
368 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa | 369 | } |
83144cfc | 370 | } |
64ebadac | 371 | |
af5fb6ab | 372 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 373 | void |
43da93a7 | 374 | vector<_Tp, _Alloc>:: |
3971a4d2 PE |
375 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |
376 | { | |
377 | if (__n != 0) | |
874e7baa PC |
378 | { |
379 | if (size_type(this->_M_impl._M_end_of_storage | |
380 | - this->_M_impl._M_finish) >= __n) | |
381 | { | |
382 | value_type __x_copy = __x; | |
383 | const size_type __elems_after = end() - __position; | |
bc9053ab | 384 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
385 | if (__elems_after > __n) |
386 | { | |
6eef7402 | 387 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
388 | this->_M_impl._M_finish, |
389 | this->_M_impl._M_finish, | |
4fd20a8f | 390 | _M_get_Tp_allocator()); |
874e7baa | 391 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
392 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
393 | __old_finish - __n, __old_finish); | |
bc9053ab PC |
394 | std::fill(__position.base(), __position.base() + __n, |
395 | __x_copy); | |
874e7baa PC |
396 | } |
397 | else | |
398 | { | |
1985f1cd MA |
399 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |
400 | __n - __elems_after, | |
401 | __x_copy, | |
4fd20a8f | 402 | _M_get_Tp_allocator()); |
874e7baa | 403 | this->_M_impl._M_finish += __n - __elems_after; |
6eef7402 | 404 | std::__uninitialized_move_a(__position.base(), __old_finish, |
1985f1cd | 405 | this->_M_impl._M_finish, |
4fd20a8f | 406 | _M_get_Tp_allocator()); |
874e7baa | 407 | this->_M_impl._M_finish += __elems_after; |
bc9053ab | 408 | std::fill(__position.base(), __old_finish, __x_copy); |
874e7baa PC |
409 | } |
410 | } | |
411 | else | |
412 | { | |
be1088fa ML |
413 | const size_type __len = |
414 | _M_check_len(__n, "vector::_M_fill_insert"); | |
d2219f89 | 415 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
416 | pointer __new_start(this->_M_allocate(__len)); |
417 | pointer __new_finish(__new_start); | |
bc2631e0 | 418 | __try |
874e7baa | 419 | { |
d2219f89 PC |
420 | // See _M_insert_aux above. |
421 | std::__uninitialized_fill_n_a(__new_start + __elems_before, | |
422 | __n, __x, | |
423 | _M_get_Tp_allocator()); | |
424 | __new_finish = 0; | |
425 | ||
74a2a1b4 PC |
426 | __new_finish |
427 | = std::__uninitialized_move_if_noexcept_a | |
428 | (this->_M_impl._M_start, __position.base(), | |
429 | __new_start, _M_get_Tp_allocator()); | |
430 | ||
368b7a30 | 431 | __new_finish += __n; |
d2219f89 | 432 | |
74a2a1b4 PC |
433 | __new_finish |
434 | = std::__uninitialized_move_if_noexcept_a | |
435 | (__position.base(), this->_M_impl._M_finish, | |
436 | __new_finish, _M_get_Tp_allocator()); | |
874e7baa | 437 | } |
bc2631e0 | 438 | __catch(...) |
874e7baa | 439 | { |
d2219f89 PC |
440 | if (!__new_finish) |
441 | std::_Destroy(__new_start + __elems_before, | |
442 | __new_start + __elems_before + __n, | |
443 | _M_get_Tp_allocator()); | |
444 | else | |
445 | std::_Destroy(__new_start, __new_finish, | |
446 | _M_get_Tp_allocator()); | |
bc9053ab | 447 | _M_deallocate(__new_start, __len); |
874e7baa PC |
448 | __throw_exception_again; |
449 | } | |
1985f1cd | 450 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 451 | _M_get_Tp_allocator()); |
874e7baa PC |
452 | _M_deallocate(this->_M_impl._M_start, |
453 | this->_M_impl._M_end_of_storage | |
454 | - this->_M_impl._M_start); | |
bc9053ab PC |
455 | this->_M_impl._M_start = __new_start; |
456 | this->_M_impl._M_finish = __new_finish; | |
457 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
458 | } |
459 | } | |
3971a4d2 | 460 | } |
ed6814f7 | 461 | |
dc2cf706 PC |
462 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
463 | template<typename _Tp, typename _Alloc> | |
464 | void | |
465 | vector<_Tp, _Alloc>:: | |
466 | _M_default_append(size_type __n) | |
467 | { | |
468 | if (__n != 0) | |
469 | { | |
470 | if (size_type(this->_M_impl._M_end_of_storage | |
471 | - this->_M_impl._M_finish) >= __n) | |
472 | { | |
473 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, | |
474 | __n, _M_get_Tp_allocator()); | |
475 | this->_M_impl._M_finish += __n; | |
476 | } | |
477 | else | |
478 | { | |
479 | const size_type __len = | |
480 | _M_check_len(__n, "vector::_M_default_append"); | |
481 | const size_type __old_size = this->size(); | |
482 | pointer __new_start(this->_M_allocate(__len)); | |
483 | pointer __new_finish(__new_start); | |
484 | __try | |
485 | { | |
74a2a1b4 PC |
486 | __new_finish |
487 | = std::__uninitialized_move_if_noexcept_a | |
488 | (this->_M_impl._M_start, this->_M_impl._M_finish, | |
489 | __new_start, _M_get_Tp_allocator()); | |
dc2cf706 PC |
490 | std::__uninitialized_default_n_a(__new_finish, __n, |
491 | _M_get_Tp_allocator()); | |
492 | __new_finish += __n; | |
493 | } | |
494 | __catch(...) | |
495 | { | |
496 | std::_Destroy(__new_start, __new_finish, | |
497 | _M_get_Tp_allocator()); | |
498 | _M_deallocate(__new_start, __len); | |
499 | __throw_exception_again; | |
500 | } | |
501 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, | |
502 | _M_get_Tp_allocator()); | |
503 | _M_deallocate(this->_M_impl._M_start, | |
504 | this->_M_impl._M_end_of_storage | |
505 | - this->_M_impl._M_start); | |
506 | this->_M_impl._M_start = __new_start; | |
507 | this->_M_impl._M_finish = __new_finish; | |
508 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
509 | } | |
510 | } | |
511 | } | |
512 | #endif | |
513 | ||
232c4925 PC |
514 | template<typename _Tp, typename _Alloc> |
515 | template<typename _InputIterator> | |
516 | void | |
517 | vector<_Tp, _Alloc>:: | |
518 | _M_range_insert(iterator __pos, _InputIterator __first, | |
519 | _InputIterator __last, std::input_iterator_tag) | |
520 | { | |
521 | for (; __first != __last; ++__first) | |
522 | { | |
523 | __pos = insert(__pos, *__first); | |
524 | ++__pos; | |
525 | } | |
526 | } | |
ed6814f7 | 527 | |
874e7baa PC |
528 | template<typename _Tp, typename _Alloc> |
529 | template<typename _ForwardIterator> | |
530 | void | |
43da93a7 | 531 | vector<_Tp, _Alloc>:: |
996e5395 | 532 | _M_range_insert(iterator __position, _ForwardIterator __first, |
6323b34e | 533 | _ForwardIterator __last, std::forward_iterator_tag) |
3971a4d2 | 534 | { |
874e7baa PC |
535 | if (__first != __last) |
536 | { | |
43da93a7 | 537 | const size_type __n = std::distance(__first, __last); |
874e7baa PC |
538 | if (size_type(this->_M_impl._M_end_of_storage |
539 | - this->_M_impl._M_finish) >= __n) | |
540 | { | |
541 | const size_type __elems_after = end() - __position; | |
bc9053ab | 542 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
543 | if (__elems_after > __n) |
544 | { | |
6eef7402 | 545 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
546 | this->_M_impl._M_finish, |
547 | this->_M_impl._M_finish, | |
4fd20a8f | 548 | _M_get_Tp_allocator()); |
874e7baa | 549 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
550 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
551 | __old_finish - __n, __old_finish); | |
874e7baa PC |
552 | std::copy(__first, __last, __position); |
553 | } | |
554 | else | |
555 | { | |
556 | _ForwardIterator __mid = __first; | |
557 | std::advance(__mid, __elems_after); | |
1985f1cd MA |
558 | std::__uninitialized_copy_a(__mid, __last, |
559 | this->_M_impl._M_finish, | |
4fd20a8f | 560 | _M_get_Tp_allocator()); |
874e7baa | 561 | this->_M_impl._M_finish += __n - __elems_after; |
6eef7402 | 562 | std::__uninitialized_move_a(__position.base(), |
bc9053ab | 563 | __old_finish, |
1985f1cd | 564 | this->_M_impl._M_finish, |
4fd20a8f | 565 | _M_get_Tp_allocator()); |
874e7baa PC |
566 | this->_M_impl._M_finish += __elems_after; |
567 | std::copy(__first, __mid, __position); | |
568 | } | |
569 | } | |
570 | else | |
571 | { | |
be1088fa ML |
572 | const size_type __len = |
573 | _M_check_len(__n, "vector::_M_range_insert"); | |
bc9053ab PC |
574 | pointer __new_start(this->_M_allocate(__len)); |
575 | pointer __new_finish(__new_start); | |
bc2631e0 | 576 | __try |
874e7baa | 577 | { |
74a2a1b4 PC |
578 | __new_finish |
579 | = std::__uninitialized_move_if_noexcept_a | |
580 | (this->_M_impl._M_start, __position.base(), | |
581 | __new_start, _M_get_Tp_allocator()); | |
582 | __new_finish | |
583 | = std::__uninitialized_copy_a(__first, __last, | |
584 | __new_finish, | |
585 | _M_get_Tp_allocator()); | |
586 | __new_finish | |
587 | = std::__uninitialized_move_if_noexcept_a | |
588 | (__position.base(), this->_M_impl._M_finish, | |
589 | __new_finish, _M_get_Tp_allocator()); | |
874e7baa | 590 | } |
bc2631e0 | 591 | __catch(...) |
874e7baa | 592 | { |
bc9053ab | 593 | std::_Destroy(__new_start, __new_finish, |
4fd20a8f | 594 | _M_get_Tp_allocator()); |
bc9053ab | 595 | _M_deallocate(__new_start, __len); |
874e7baa PC |
596 | __throw_exception_again; |
597 | } | |
1985f1cd | 598 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 599 | _M_get_Tp_allocator()); |
874e7baa PC |
600 | _M_deallocate(this->_M_impl._M_start, |
601 | this->_M_impl._M_end_of_storage | |
602 | - this->_M_impl._M_start); | |
bc9053ab PC |
603 | this->_M_impl._M_start = __new_start; |
604 | this->_M_impl._M_finish = __new_finish; | |
605 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
606 | } |
607 | } | |
83144cfc | 608 | } |
3cbc7af0 | 609 | |
232c4925 PC |
610 | |
611 | // vector<bool> | |
612 | ||
c62df8fd PC |
613 | template<typename _Alloc> |
614 | void | |
615 | vector<bool, _Alloc>:: | |
616 | reserve(size_type __n) | |
617 | { | |
618 | if (__n > this->max_size()) | |
619 | __throw_length_error(__N("vector::reserve")); | |
620 | if (this->capacity() < __n) | |
621 | { | |
622 | _Bit_type* __q = this->_M_allocate(__n); | |
623 | this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), | |
624 | iterator(__q, 0)); | |
625 | this->_M_deallocate(); | |
626 | this->_M_impl._M_start = iterator(__q, 0); | |
627 | this->_M_impl._M_end_of_storage = (__q + (__n + int(_S_word_bit) - 1) | |
628 | / int(_S_word_bit)); | |
629 | } | |
630 | } | |
631 | ||
232c4925 PC |
632 | template<typename _Alloc> |
633 | void | |
634 | vector<bool, _Alloc>:: | |
635 | _M_fill_insert(iterator __position, size_type __n, bool __x) | |
636 | { | |
637 | if (__n == 0) | |
638 | return; | |
639 | if (capacity() - size() >= __n) | |
640 | { | |
641 | std::copy_backward(__position, end(), | |
642 | this->_M_impl._M_finish + difference_type(__n)); | |
643 | std::fill(__position, __position + difference_type(__n), __x); | |
644 | this->_M_impl._M_finish += difference_type(__n); | |
645 | } | |
646 | else | |
647 | { | |
be1088fa ML |
648 | const size_type __len = |
649 | _M_check_len(__n, "vector<bool>::_M_fill_insert"); | |
232c4925 PC |
650 | _Bit_type * __q = this->_M_allocate(__len); |
651 | iterator __i = _M_copy_aligned(begin(), __position, | |
652 | iterator(__q, 0)); | |
653 | std::fill(__i, __i + difference_type(__n), __x); | |
654 | this->_M_impl._M_finish = std::copy(__position, end(), | |
655 | __i + difference_type(__n)); | |
656 | this->_M_deallocate(); | |
657 | this->_M_impl._M_end_of_storage = (__q + ((__len | |
658 | + int(_S_word_bit) - 1) | |
659 | / int(_S_word_bit))); | |
660 | this->_M_impl._M_start = iterator(__q, 0); | |
661 | } | |
662 | } | |
663 | ||
664 | template<typename _Alloc> | |
665 | template<typename _ForwardIterator> | |
666 | void | |
667 | vector<bool, _Alloc>:: | |
668 | _M_insert_range(iterator __position, _ForwardIterator __first, | |
669 | _ForwardIterator __last, std::forward_iterator_tag) | |
670 | { | |
671 | if (__first != __last) | |
672 | { | |
673 | size_type __n = std::distance(__first, __last); | |
674 | if (capacity() - size() >= __n) | |
675 | { | |
676 | std::copy_backward(__position, end(), | |
677 | this->_M_impl._M_finish | |
678 | + difference_type(__n)); | |
679 | std::copy(__first, __last, __position); | |
680 | this->_M_impl._M_finish += difference_type(__n); | |
681 | } | |
682 | else | |
683 | { | |
be1088fa ML |
684 | const size_type __len = |
685 | _M_check_len(__n, "vector<bool>::_M_insert_range"); | |
232c4925 PC |
686 | _Bit_type * __q = this->_M_allocate(__len); |
687 | iterator __i = _M_copy_aligned(begin(), __position, | |
688 | iterator(__q, 0)); | |
689 | __i = std::copy(__first, __last, __i); | |
690 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
691 | this->_M_deallocate(); | |
692 | this->_M_impl._M_end_of_storage = (__q | |
693 | + ((__len | |
694 | + int(_S_word_bit) - 1) | |
695 | / int(_S_word_bit))); | |
696 | this->_M_impl._M_start = iterator(__q, 0); | |
697 | } | |
698 | } | |
699 | } | |
700 | ||
701 | template<typename _Alloc> | |
702 | void | |
703 | vector<bool, _Alloc>:: | |
704 | _M_insert_aux(iterator __position, bool __x) | |
705 | { | |
706 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) | |
707 | { | |
708 | std::copy_backward(__position, this->_M_impl._M_finish, | |
709 | this->_M_impl._M_finish + 1); | |
710 | *__position = __x; | |
711 | ++this->_M_impl._M_finish; | |
712 | } | |
713 | else | |
714 | { | |
be1088fa ML |
715 | const size_type __len = |
716 | _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); | |
232c4925 PC |
717 | _Bit_type * __q = this->_M_allocate(__len); |
718 | iterator __i = _M_copy_aligned(begin(), __position, | |
719 | iterator(__q, 0)); | |
720 | *__i++ = __x; | |
721 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
722 | this->_M_deallocate(); | |
723 | this->_M_impl._M_end_of_storage = (__q + ((__len | |
724 | + int(_S_word_bit) - 1) | |
725 | / int(_S_word_bit))); | |
726 | this->_M_impl._M_start = iterator(__q, 0); | |
727 | } | |
728 | } | |
729 | ||
12ffa228 BK |
730 | _GLIBCXX_END_NAMESPACE_CONTAINER |
731 | } // namespace std | |
83144cfc | 732 | |
f54e96d9 PC |
733 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
734 | ||
12ffa228 BK |
735 | namespace std _GLIBCXX_VISIBILITY(default) |
736 | { | |
737 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
f54e96d9 PC |
738 | |
739 | template<typename _Alloc> | |
740 | size_t | |
12ffa228 BK |
741 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |
742 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const | |
f54e96d9 PC |
743 | { |
744 | size_t __hash = 0; | |
12ffa228 BK |
745 | using _GLIBCXX_STD_C::_S_word_bit; |
746 | using _GLIBCXX_STD_C::_Bit_type; | |
f54e96d9 PC |
747 | |
748 | const size_t __words = __b.size() / _S_word_bit; | |
749 | if (__words) | |
750 | { | |
055f6a47 | 751 | const size_t __clength = __words * sizeof(_Bit_type); |
e7f72940 | 752 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |
f54e96d9 PC |
753 | } |
754 | ||
755 | const size_t __extrabits = __b.size() % _S_word_bit; | |
756 | if (__extrabits) | |
757 | { | |
758 | _Bit_type __hiword = *__b._M_impl._M_finish._M_p; | |
759 | __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); | |
760 | ||
055f6a47 | 761 | const size_t __clength |
f54e96d9 PC |
762 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
763 | if (__words) | |
e7f72940 | 764 | __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); |
f54e96d9 | 765 | else |
e7f72940 | 766 | __hash = std::_Hash_impl::hash(&__hiword, __clength); |
f54e96d9 PC |
767 | } |
768 | ||
769 | return __hash; | |
770 | } | |
771 | ||
12ffa228 BK |
772 | _GLIBCXX_END_NAMESPACE_VERSION |
773 | } // namespace std | |
f54e96d9 PC |
774 | |
775 | #endif // __GXX_EXPERIMENTAL_CXX0X__ | |
776 | ||
3d7c150e | 777 | #endif /* _VECTOR_TCC */ |