]>
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 | { | |
bd8485dc JW |
97 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
98 | std::forward<_Args>(__args)...); | |
4dc3e453 PC |
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 | { | |
bd8485dc | 115 | _Alloc_traits::construct(this->_M_impl, 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; |
bd8485dc | 141 | _Alloc_traits::destroy(this->_M_impl, 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 | 162 | { |
bd8485dc JW |
163 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
164 | if (_Alloc_traits::_S_propagate_on_copy_assign()) | |
165 | { | |
166 | if (!_Alloc_traits::_S_always_equal() | |
167 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) | |
168 | { | |
169 | // replacement allocator cannot free existing storage | |
170 | this->clear(); | |
171 | _M_deallocate(this->_M_impl._M_start, | |
172 | this->_M_impl._M_end_of_storage | |
173 | - this->_M_impl._M_start); | |
174 | } | |
175 | std::__alloc_on_copy(_M_get_Tp_allocator(), | |
176 | __x._M_get_Tp_allocator()); | |
177 | } | |
178 | #endif | |
874e7baa PC |
179 | const size_type __xlen = __x.size(); |
180 | if (__xlen > capacity()) | |
181 | { | |
182 | pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), | |
183 | __x.end()); | |
1985f1cd | 184 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 185 | _M_get_Tp_allocator()); |
874e7baa PC |
186 | _M_deallocate(this->_M_impl._M_start, |
187 | this->_M_impl._M_end_of_storage | |
188 | - this->_M_impl._M_start); | |
189 | this->_M_impl._M_start = __tmp; | |
190 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; | |
191 | } | |
192 | else if (size() >= __xlen) | |
193 | { | |
bc9053ab PC |
194 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |
195 | end(), _M_get_Tp_allocator()); | |
874e7baa PC |
196 | } |
197 | else | |
198 | { | |
bc9053ab | 199 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |
874e7baa | 200 | this->_M_impl._M_start); |
bc9053ab PC |
201 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |
202 | __x._M_impl._M_finish, | |
203 | this->_M_impl._M_finish, | |
4fd20a8f | 204 | _M_get_Tp_allocator()); |
874e7baa PC |
205 | } |
206 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; | |
207 | } | |
3971a4d2 | 208 | return *this; |
83144cfc | 209 | } |
ed6814f7 | 210 | |
af5fb6ab | 211 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 212 | void |
874e7baa | 213 | vector<_Tp, _Alloc>:: |
3971a4d2 | 214 | _M_fill_assign(size_t __n, const value_type& __val) |
83144cfc | 215 | { |
3971a4d2 | 216 | if (__n > capacity()) |
874e7baa | 217 | { |
4fd20a8f | 218 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |
874e7baa PC |
219 | __tmp.swap(*this); |
220 | } | |
3971a4d2 | 221 | else if (__n > size()) |
874e7baa PC |
222 | { |
223 | std::fill(begin(), end(), __val); | |
1985f1cd MA |
224 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |
225 | __n - size(), __val, | |
4fd20a8f | 226 | _M_get_Tp_allocator()); |
368b7a30 | 227 | this->_M_impl._M_finish += __n - size(); |
874e7baa | 228 | } |
3971a4d2 | 229 | else |
bc9053ab | 230 | _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); |
83144cfc | 231 | } |
ed6814f7 | 232 | |
874e7baa PC |
233 | template<typename _Tp, typename _Alloc> |
234 | template<typename _InputIterator> | |
235 | void | |
236 | vector<_Tp, _Alloc>:: | |
237 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
6323b34e | 238 | std::input_iterator_tag) |
3971a4d2 | 239 | { |
bc9053ab PC |
240 | pointer __cur(this->_M_impl._M_start); |
241 | for (; __first != __last && __cur != this->_M_impl._M_finish; | |
242 | ++__cur, ++__first) | |
874e7baa PC |
243 | *__cur = *__first; |
244 | if (__first == __last) | |
bc9053ab | 245 | _M_erase_at_end(__cur); |
874e7baa PC |
246 | else |
247 | insert(end(), __first, __last); | |
3971a4d2 | 248 | } |
874e7baa PC |
249 | |
250 | template<typename _Tp, typename _Alloc> | |
251 | template<typename _ForwardIterator> | |
252 | void | |
43da93a7 | 253 | vector<_Tp, _Alloc>:: |
874e7baa | 254 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
6323b34e | 255 | std::forward_iterator_tag) |
3971a4d2 | 256 | { |
43da93a7 | 257 | const size_type __len = std::distance(__first, __last); |
874e7baa PC |
258 | |
259 | if (__len > capacity()) | |
260 | { | |
261 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); | |
1985f1cd | 262 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 263 | _M_get_Tp_allocator()); |
874e7baa PC |
264 | _M_deallocate(this->_M_impl._M_start, |
265 | this->_M_impl._M_end_of_storage | |
266 | - this->_M_impl._M_start); | |
267 | this->_M_impl._M_start = __tmp; | |
268 | this->_M_impl._M_finish = this->_M_impl._M_start + __len; | |
269 | this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; | |
270 | } | |
271 | else if (size() >= __len) | |
bc9053ab | 272 | _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); |
874e7baa PC |
273 | else |
274 | { | |
275 | _ForwardIterator __mid = __first; | |
276 | std::advance(__mid, size()); | |
277 | std::copy(__first, __mid, this->_M_impl._M_start); | |
1985f1cd MA |
278 | this->_M_impl._M_finish = |
279 | std::__uninitialized_copy_a(__mid, __last, | |
280 | this->_M_impl._M_finish, | |
4fd20a8f | 281 | _M_get_Tp_allocator()); |
874e7baa | 282 | } |
3971a4d2 | 283 | } |
ed6814f7 | 284 | |
6eef7402 CJ |
285 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
286 | template<typename _Tp, typename _Alloc> | |
287 | template<typename... _Args> | |
288 | typename vector<_Tp, _Alloc>::iterator | |
289 | vector<_Tp, _Alloc>:: | |
290 | emplace(iterator __position, _Args&&... __args) | |
291 | { | |
292 | const size_type __n = __position - begin(); | |
293 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage | |
294 | && __position == end()) | |
295 | { | |
bd8485dc JW |
296 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
297 | std::forward<_Args>(__args)...); | |
6eef7402 CJ |
298 | ++this->_M_impl._M_finish; |
299 | } | |
300 | else | |
301 | _M_insert_aux(__position, std::forward<_Args>(__args)...); | |
302 | return iterator(this->_M_impl._M_start + __n); | |
303 | } | |
304 | ||
305 | template<typename _Tp, typename _Alloc> | |
306 | template<typename... _Args> | |
307 | void | |
308 | vector<_Tp, _Alloc>:: | |
309 | _M_insert_aux(iterator __position, _Args&&... __args) | |
6eef7402 | 310 | #else |
af5fb6ab | 311 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 312 | void |
43da93a7 | 313 | vector<_Tp, _Alloc>:: |
3971a4d2 | 314 | _M_insert_aux(iterator __position, const _Tp& __x) |
6eef7402 | 315 | #endif |
812e8c79 | 316 | { |
03f9ea44 | 317 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
874e7baa | 318 | { |
bd8485dc JW |
319 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
320 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish | |
321 | - 1))); | |
874e7baa | 322 | ++this->_M_impl._M_finish; |
6eef7402 | 323 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
874e7baa | 324 | _Tp __x_copy = __x; |
6eef7402 CJ |
325 | #endif |
326 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), | |
327 | this->_M_impl._M_finish - 2, | |
328 | this->_M_impl._M_finish - 1); | |
812e8c79 PC |
329 | #ifndef __GXX_EXPERIMENTAL_CXX0X__ |
330 | *__position = __x_copy; | |
331 | #else | |
332 | *__position = _Tp(std::forward<_Args>(__args)...); | |
333 | #endif | |
874e7baa | 334 | } |
83144cfc | 335 | else |
874e7baa | 336 | { |
be1088fa ML |
337 | const size_type __len = |
338 | _M_check_len(size_type(1), "vector::_M_insert_aux"); | |
d2219f89 | 339 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
340 | pointer __new_start(this->_M_allocate(__len)); |
341 | pointer __new_finish(__new_start); | |
bc2631e0 | 342 | __try |
874e7baa | 343 | { |
d2219f89 PC |
344 | // The order of the three operations is dictated by the C++0x |
345 | // case, where the moves could alter a new element belonging | |
346 | // to the existing vector. This is an issue only for callers | |
347 | // taking the element by const lvalue ref (see 23.1/13). | |
bd8485dc JW |
348 | _Alloc_traits::construct(this->_M_impl, |
349 | __new_start + __elems_before, | |
812e8c79 | 350 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
bd8485dc | 351 | std::forward<_Args>(__args)...); |
d2219f89 | 352 | #else |
bd8485dc | 353 | __x); |
812e8c79 | 354 | #endif |
d2219f89 PC |
355 | __new_finish = 0; |
356 | ||
74a2a1b4 PC |
357 | __new_finish |
358 | = std::__uninitialized_move_if_noexcept_a | |
359 | (this->_M_impl._M_start, __position.base(), | |
360 | __new_start, _M_get_Tp_allocator()); | |
361 | ||
874e7baa | 362 | ++__new_finish; |
d2219f89 | 363 | |
74a2a1b4 PC |
364 | __new_finish |
365 | = std::__uninitialized_move_if_noexcept_a | |
366 | (__position.base(), this->_M_impl._M_finish, | |
367 | __new_finish, _M_get_Tp_allocator()); | |
996e5395 | 368 | } |
bc2631e0 | 369 | __catch(...) |
874e7baa | 370 | { |
d2219f89 | 371 | if (!__new_finish) |
bd8485dc JW |
372 | _Alloc_traits::destroy(this->_M_impl, |
373 | __new_start + __elems_before); | |
d2219f89 PC |
374 | else |
375 | std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator()); | |
bc9053ab | 376 | _M_deallocate(__new_start, __len); |
874e7baa PC |
377 | __throw_exception_again; |
378 | } | |
bc9053ab PC |
379 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
380 | _M_get_Tp_allocator()); | |
874e7baa PC |
381 | _M_deallocate(this->_M_impl._M_start, |
382 | this->_M_impl._M_end_of_storage | |
383 | - this->_M_impl._M_start); | |
bc9053ab PC |
384 | this->_M_impl._M_start = __new_start; |
385 | this->_M_impl._M_finish = __new_finish; | |
386 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa | 387 | } |
83144cfc | 388 | } |
64ebadac | 389 | |
af5fb6ab | 390 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 391 | void |
43da93a7 | 392 | vector<_Tp, _Alloc>:: |
3971a4d2 PE |
393 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |
394 | { | |
395 | if (__n != 0) | |
874e7baa PC |
396 | { |
397 | if (size_type(this->_M_impl._M_end_of_storage | |
398 | - this->_M_impl._M_finish) >= __n) | |
399 | { | |
400 | value_type __x_copy = __x; | |
401 | const size_type __elems_after = end() - __position; | |
bc9053ab | 402 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
403 | if (__elems_after > __n) |
404 | { | |
6eef7402 | 405 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
406 | this->_M_impl._M_finish, |
407 | this->_M_impl._M_finish, | |
4fd20a8f | 408 | _M_get_Tp_allocator()); |
874e7baa | 409 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
410 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
411 | __old_finish - __n, __old_finish); | |
bc9053ab PC |
412 | std::fill(__position.base(), __position.base() + __n, |
413 | __x_copy); | |
874e7baa PC |
414 | } |
415 | else | |
416 | { | |
1985f1cd MA |
417 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, |
418 | __n - __elems_after, | |
419 | __x_copy, | |
4fd20a8f | 420 | _M_get_Tp_allocator()); |
874e7baa | 421 | this->_M_impl._M_finish += __n - __elems_after; |
6eef7402 | 422 | std::__uninitialized_move_a(__position.base(), __old_finish, |
1985f1cd | 423 | this->_M_impl._M_finish, |
4fd20a8f | 424 | _M_get_Tp_allocator()); |
874e7baa | 425 | this->_M_impl._M_finish += __elems_after; |
bc9053ab | 426 | std::fill(__position.base(), __old_finish, __x_copy); |
874e7baa PC |
427 | } |
428 | } | |
429 | else | |
430 | { | |
be1088fa ML |
431 | const size_type __len = |
432 | _M_check_len(__n, "vector::_M_fill_insert"); | |
d2219f89 | 433 | const size_type __elems_before = __position - begin(); |
bc9053ab PC |
434 | pointer __new_start(this->_M_allocate(__len)); |
435 | pointer __new_finish(__new_start); | |
bc2631e0 | 436 | __try |
874e7baa | 437 | { |
d2219f89 PC |
438 | // See _M_insert_aux above. |
439 | std::__uninitialized_fill_n_a(__new_start + __elems_before, | |
440 | __n, __x, | |
441 | _M_get_Tp_allocator()); | |
442 | __new_finish = 0; | |
443 | ||
74a2a1b4 PC |
444 | __new_finish |
445 | = std::__uninitialized_move_if_noexcept_a | |
446 | (this->_M_impl._M_start, __position.base(), | |
447 | __new_start, _M_get_Tp_allocator()); | |
448 | ||
368b7a30 | 449 | __new_finish += __n; |
d2219f89 | 450 | |
74a2a1b4 PC |
451 | __new_finish |
452 | = std::__uninitialized_move_if_noexcept_a | |
453 | (__position.base(), this->_M_impl._M_finish, | |
454 | __new_finish, _M_get_Tp_allocator()); | |
874e7baa | 455 | } |
bc2631e0 | 456 | __catch(...) |
874e7baa | 457 | { |
d2219f89 PC |
458 | if (!__new_finish) |
459 | std::_Destroy(__new_start + __elems_before, | |
460 | __new_start + __elems_before + __n, | |
461 | _M_get_Tp_allocator()); | |
462 | else | |
463 | std::_Destroy(__new_start, __new_finish, | |
464 | _M_get_Tp_allocator()); | |
bc9053ab | 465 | _M_deallocate(__new_start, __len); |
874e7baa PC |
466 | __throw_exception_again; |
467 | } | |
1985f1cd | 468 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 469 | _M_get_Tp_allocator()); |
874e7baa PC |
470 | _M_deallocate(this->_M_impl._M_start, |
471 | this->_M_impl._M_end_of_storage | |
472 | - this->_M_impl._M_start); | |
bc9053ab PC |
473 | this->_M_impl._M_start = __new_start; |
474 | this->_M_impl._M_finish = __new_finish; | |
475 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
476 | } |
477 | } | |
3971a4d2 | 478 | } |
ed6814f7 | 479 | |
dc2cf706 PC |
480 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
481 | template<typename _Tp, typename _Alloc> | |
482 | void | |
483 | vector<_Tp, _Alloc>:: | |
484 | _M_default_append(size_type __n) | |
485 | { | |
486 | if (__n != 0) | |
487 | { | |
488 | if (size_type(this->_M_impl._M_end_of_storage | |
489 | - this->_M_impl._M_finish) >= __n) | |
490 | { | |
491 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, | |
492 | __n, _M_get_Tp_allocator()); | |
493 | this->_M_impl._M_finish += __n; | |
494 | } | |
495 | else | |
496 | { | |
497 | const size_type __len = | |
498 | _M_check_len(__n, "vector::_M_default_append"); | |
499 | const size_type __old_size = this->size(); | |
500 | pointer __new_start(this->_M_allocate(__len)); | |
501 | pointer __new_finish(__new_start); | |
502 | __try | |
503 | { | |
74a2a1b4 PC |
504 | __new_finish |
505 | = std::__uninitialized_move_if_noexcept_a | |
506 | (this->_M_impl._M_start, this->_M_impl._M_finish, | |
507 | __new_start, _M_get_Tp_allocator()); | |
dc2cf706 PC |
508 | std::__uninitialized_default_n_a(__new_finish, __n, |
509 | _M_get_Tp_allocator()); | |
510 | __new_finish += __n; | |
511 | } | |
512 | __catch(...) | |
513 | { | |
514 | std::_Destroy(__new_start, __new_finish, | |
515 | _M_get_Tp_allocator()); | |
516 | _M_deallocate(__new_start, __len); | |
517 | __throw_exception_again; | |
518 | } | |
519 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, | |
520 | _M_get_Tp_allocator()); | |
521 | _M_deallocate(this->_M_impl._M_start, | |
522 | this->_M_impl._M_end_of_storage | |
523 | - this->_M_impl._M_start); | |
524 | this->_M_impl._M_start = __new_start; | |
525 | this->_M_impl._M_finish = __new_finish; | |
526 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
527 | } | |
528 | } | |
529 | } | |
8a752dfe FD |
530 | |
531 | template<typename _Tp, typename _Alloc> | |
532 | bool | |
533 | vector<_Tp, _Alloc>:: | |
534 | _M_shrink_to_fit() | |
535 | { | |
536 | if (capacity() == size()) | |
537 | return false; | |
538 | return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); | |
539 | } | |
dc2cf706 PC |
540 | #endif |
541 | ||
232c4925 PC |
542 | template<typename _Tp, typename _Alloc> |
543 | template<typename _InputIterator> | |
544 | void | |
545 | vector<_Tp, _Alloc>:: | |
546 | _M_range_insert(iterator __pos, _InputIterator __first, | |
547 | _InputIterator __last, std::input_iterator_tag) | |
548 | { | |
549 | for (; __first != __last; ++__first) | |
550 | { | |
551 | __pos = insert(__pos, *__first); | |
552 | ++__pos; | |
553 | } | |
554 | } | |
ed6814f7 | 555 | |
874e7baa PC |
556 | template<typename _Tp, typename _Alloc> |
557 | template<typename _ForwardIterator> | |
558 | void | |
43da93a7 | 559 | vector<_Tp, _Alloc>:: |
996e5395 | 560 | _M_range_insert(iterator __position, _ForwardIterator __first, |
6323b34e | 561 | _ForwardIterator __last, std::forward_iterator_tag) |
3971a4d2 | 562 | { |
874e7baa PC |
563 | if (__first != __last) |
564 | { | |
43da93a7 | 565 | const size_type __n = std::distance(__first, __last); |
874e7baa PC |
566 | if (size_type(this->_M_impl._M_end_of_storage |
567 | - this->_M_impl._M_finish) >= __n) | |
568 | { | |
569 | const size_type __elems_after = end() - __position; | |
bc9053ab | 570 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
571 | if (__elems_after > __n) |
572 | { | |
6eef7402 | 573 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
574 | this->_M_impl._M_finish, |
575 | this->_M_impl._M_finish, | |
4fd20a8f | 576 | _M_get_Tp_allocator()); |
874e7baa | 577 | this->_M_impl._M_finish += __n; |
6eef7402 CJ |
578 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
579 | __old_finish - __n, __old_finish); | |
874e7baa PC |
580 | std::copy(__first, __last, __position); |
581 | } | |
582 | else | |
583 | { | |
584 | _ForwardIterator __mid = __first; | |
585 | std::advance(__mid, __elems_after); | |
1985f1cd MA |
586 | std::__uninitialized_copy_a(__mid, __last, |
587 | this->_M_impl._M_finish, | |
4fd20a8f | 588 | _M_get_Tp_allocator()); |
874e7baa | 589 | this->_M_impl._M_finish += __n - __elems_after; |
6eef7402 | 590 | std::__uninitialized_move_a(__position.base(), |
bc9053ab | 591 | __old_finish, |
1985f1cd | 592 | this->_M_impl._M_finish, |
4fd20a8f | 593 | _M_get_Tp_allocator()); |
874e7baa PC |
594 | this->_M_impl._M_finish += __elems_after; |
595 | std::copy(__first, __mid, __position); | |
596 | } | |
597 | } | |
598 | else | |
599 | { | |
be1088fa ML |
600 | const size_type __len = |
601 | _M_check_len(__n, "vector::_M_range_insert"); | |
bc9053ab PC |
602 | pointer __new_start(this->_M_allocate(__len)); |
603 | pointer __new_finish(__new_start); | |
bc2631e0 | 604 | __try |
874e7baa | 605 | { |
74a2a1b4 PC |
606 | __new_finish |
607 | = std::__uninitialized_move_if_noexcept_a | |
608 | (this->_M_impl._M_start, __position.base(), | |
609 | __new_start, _M_get_Tp_allocator()); | |
610 | __new_finish | |
611 | = std::__uninitialized_copy_a(__first, __last, | |
612 | __new_finish, | |
613 | _M_get_Tp_allocator()); | |
614 | __new_finish | |
615 | = std::__uninitialized_move_if_noexcept_a | |
616 | (__position.base(), this->_M_impl._M_finish, | |
617 | __new_finish, _M_get_Tp_allocator()); | |
874e7baa | 618 | } |
bc2631e0 | 619 | __catch(...) |
874e7baa | 620 | { |
bc9053ab | 621 | std::_Destroy(__new_start, __new_finish, |
4fd20a8f | 622 | _M_get_Tp_allocator()); |
bc9053ab | 623 | _M_deallocate(__new_start, __len); |
874e7baa PC |
624 | __throw_exception_again; |
625 | } | |
1985f1cd | 626 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 627 | _M_get_Tp_allocator()); |
874e7baa PC |
628 | _M_deallocate(this->_M_impl._M_start, |
629 | this->_M_impl._M_end_of_storage | |
630 | - this->_M_impl._M_start); | |
bc9053ab PC |
631 | this->_M_impl._M_start = __new_start; |
632 | this->_M_impl._M_finish = __new_finish; | |
633 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
634 | } |
635 | } | |
83144cfc | 636 | } |
3cbc7af0 | 637 | |
232c4925 PC |
638 | |
639 | // vector<bool> | |
c62df8fd PC |
640 | template<typename _Alloc> |
641 | void | |
642 | vector<bool, _Alloc>:: | |
8a752dfe | 643 | _M_reallocate(size_type __n) |
c62df8fd | 644 | { |
8a752dfe FD |
645 | _Bit_type* __q = this->_M_allocate(__n); |
646 | this->_M_impl._M_finish = _M_copy_aligned(begin(), end(), | |
647 | iterator(__q, 0)); | |
648 | this->_M_deallocate(); | |
649 | this->_M_impl._M_start = iterator(__q, 0); | |
650 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); | |
c62df8fd PC |
651 | } |
652 | ||
232c4925 PC |
653 | template<typename _Alloc> |
654 | void | |
655 | vector<bool, _Alloc>:: | |
656 | _M_fill_insert(iterator __position, size_type __n, bool __x) | |
657 | { | |
658 | if (__n == 0) | |
659 | return; | |
660 | if (capacity() - size() >= __n) | |
661 | { | |
662 | std::copy_backward(__position, end(), | |
663 | this->_M_impl._M_finish + difference_type(__n)); | |
664 | std::fill(__position, __position + difference_type(__n), __x); | |
665 | this->_M_impl._M_finish += difference_type(__n); | |
666 | } | |
667 | else | |
668 | { | |
be1088fa ML |
669 | const size_type __len = |
670 | _M_check_len(__n, "vector<bool>::_M_fill_insert"); | |
232c4925 PC |
671 | _Bit_type * __q = this->_M_allocate(__len); |
672 | iterator __i = _M_copy_aligned(begin(), __position, | |
673 | iterator(__q, 0)); | |
674 | std::fill(__i, __i + difference_type(__n), __x); | |
675 | this->_M_impl._M_finish = std::copy(__position, end(), | |
676 | __i + difference_type(__n)); | |
677 | this->_M_deallocate(); | |
8a752dfe | 678 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
232c4925 PC |
679 | this->_M_impl._M_start = iterator(__q, 0); |
680 | } | |
681 | } | |
682 | ||
683 | template<typename _Alloc> | |
684 | template<typename _ForwardIterator> | |
685 | void | |
686 | vector<bool, _Alloc>:: | |
687 | _M_insert_range(iterator __position, _ForwardIterator __first, | |
688 | _ForwardIterator __last, std::forward_iterator_tag) | |
689 | { | |
690 | if (__first != __last) | |
691 | { | |
692 | size_type __n = std::distance(__first, __last); | |
693 | if (capacity() - size() >= __n) | |
694 | { | |
695 | std::copy_backward(__position, end(), | |
696 | this->_M_impl._M_finish | |
697 | + difference_type(__n)); | |
698 | std::copy(__first, __last, __position); | |
699 | this->_M_impl._M_finish += difference_type(__n); | |
700 | } | |
701 | else | |
702 | { | |
be1088fa ML |
703 | const size_type __len = |
704 | _M_check_len(__n, "vector<bool>::_M_insert_range"); | |
232c4925 PC |
705 | _Bit_type * __q = this->_M_allocate(__len); |
706 | iterator __i = _M_copy_aligned(begin(), __position, | |
707 | iterator(__q, 0)); | |
708 | __i = std::copy(__first, __last, __i); | |
709 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
710 | this->_M_deallocate(); | |
8a752dfe | 711 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
232c4925 PC |
712 | this->_M_impl._M_start = iterator(__q, 0); |
713 | } | |
714 | } | |
715 | } | |
716 | ||
717 | template<typename _Alloc> | |
718 | void | |
719 | vector<bool, _Alloc>:: | |
720 | _M_insert_aux(iterator __position, bool __x) | |
721 | { | |
722 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_of_storage) | |
723 | { | |
724 | std::copy_backward(__position, this->_M_impl._M_finish, | |
725 | this->_M_impl._M_finish + 1); | |
726 | *__position = __x; | |
727 | ++this->_M_impl._M_finish; | |
728 | } | |
729 | else | |
730 | { | |
be1088fa ML |
731 | const size_type __len = |
732 | _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); | |
232c4925 PC |
733 | _Bit_type * __q = this->_M_allocate(__len); |
734 | iterator __i = _M_copy_aligned(begin(), __position, | |
735 | iterator(__q, 0)); | |
736 | *__i++ = __x; | |
737 | this->_M_impl._M_finish = std::copy(__position, end(), __i); | |
738 | this->_M_deallocate(); | |
8a752dfe | 739 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
232c4925 PC |
740 | this->_M_impl._M_start = iterator(__q, 0); |
741 | } | |
742 | } | |
743 | ||
8a752dfe FD |
744 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
745 | template<typename _Alloc> | |
746 | bool | |
747 | vector<bool, _Alloc>:: | |
748 | _M_shrink_to_fit() | |
749 | { | |
750 | if (capacity() - size() < int(_S_word_bit)) | |
751 | return false; | |
752 | __try | |
753 | { | |
754 | _M_reallocate(size()); | |
755 | return true; | |
756 | } | |
757 | __catch(...) | |
758 | { return false; } | |
759 | } | |
760 | #endif | |
761 | ||
12ffa228 BK |
762 | _GLIBCXX_END_NAMESPACE_CONTAINER |
763 | } // namespace std | |
83144cfc | 764 | |
f54e96d9 PC |
765 | #ifdef __GXX_EXPERIMENTAL_CXX0X__ |
766 | ||
12ffa228 BK |
767 | namespace std _GLIBCXX_VISIBILITY(default) |
768 | { | |
769 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
f54e96d9 PC |
770 | |
771 | template<typename _Alloc> | |
772 | size_t | |
12ffa228 BK |
773 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |
774 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const | |
f54e96d9 PC |
775 | { |
776 | size_t __hash = 0; | |
12ffa228 BK |
777 | using _GLIBCXX_STD_C::_S_word_bit; |
778 | using _GLIBCXX_STD_C::_Bit_type; | |
f54e96d9 PC |
779 | |
780 | const size_t __words = __b.size() / _S_word_bit; | |
781 | if (__words) | |
782 | { | |
055f6a47 | 783 | const size_t __clength = __words * sizeof(_Bit_type); |
e7f72940 | 784 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |
f54e96d9 PC |
785 | } |
786 | ||
787 | const size_t __extrabits = __b.size() % _S_word_bit; | |
788 | if (__extrabits) | |
789 | { | |
790 | _Bit_type __hiword = *__b._M_impl._M_finish._M_p; | |
791 | __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); | |
792 | ||
055f6a47 | 793 | const size_t __clength |
f54e96d9 PC |
794 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
795 | if (__words) | |
e7f72940 | 796 | __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); |
f54e96d9 | 797 | else |
e7f72940 | 798 | __hash = std::_Hash_impl::hash(&__hiword, __clength); |
f54e96d9 PC |
799 | } |
800 | ||
801 | return __hash; | |
802 | } | |
803 | ||
12ffa228 BK |
804 | _GLIBCXX_END_NAMESPACE_VERSION |
805 | } // namespace std | |
f54e96d9 PC |
806 | |
807 | #endif // __GXX_EXPERIMENTAL_CXX0X__ | |
808 | ||
3d7c150e | 809 | #endif /* _VECTOR_TCC */ |