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