Line data Source code
1 : // Vector implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2017 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 60 : vector<_Tp, _Alloc>::
66 : reserve(size_type __n)
67 : {
68 60 : if (__n > this->max_size())
69 0 : __throw_length_error(__N("vector::reserve"));
70 60 : if (this->capacity() < __n)
71 : {
72 60 : const size_type __old_size = size();
73 60 : pointer __tmp = _M_allocate_and_copy(__n,
74 : _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
75 : _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
76 60 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
77 60 : _M_get_Tp_allocator());
78 120 : _M_deallocate(this->_M_impl._M_start,
79 60 : this->_M_impl._M_end_of_storage
80 60 : - this->_M_impl._M_start);
81 60 : this->_M_impl._M_start = __tmp;
82 60 : this->_M_impl._M_finish = __tmp + __old_size;
83 60 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
84 : }
85 60 : }
86 :
87 : #if __cplusplus >= 201103L
88 : template<typename _Tp, typename _Alloc>
89 : template<typename... _Args>
90 : #if __cplusplus > 201402L
91 : typename vector<_Tp, _Alloc>::reference
92 : #else
93 : void
94 : #endif
95 178183 : vector<_Tp, _Alloc>::
96 : emplace_back(_Args&&... __args)
97 : {
98 178183 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
99 : {
100 178098 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
101 : std::forward<_Args>(__args)...);
102 178098 : ++this->_M_impl._M_finish;
103 : }
104 : else
105 85 : _M_realloc_insert(end(), std::forward<_Args>(__args)...);
106 : #if __cplusplus > 201402L
107 : return back();
108 : #endif
109 178183 : }
110 : #endif
111 :
112 : template<typename _Tp, typename _Alloc>
113 : typename vector<_Tp, _Alloc>::iterator
114 : vector<_Tp, _Alloc>::
115 : #if __cplusplus >= 201103L
116 : insert(const_iterator __position, const value_type& __x)
117 : #else
118 : insert(iterator __position, const value_type& __x)
119 : #endif
120 : {
121 : const size_type __n = __position - begin();
122 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
123 : if (__position == end())
124 : {
125 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
126 : __x);
127 : ++this->_M_impl._M_finish;
128 : }
129 : else
130 : {
131 : #if __cplusplus >= 201103L
132 : const auto __pos = begin() + (__position - cbegin());
133 : // __x could be an existing element of this vector, so make a
134 : // copy of it before _M_insert_aux moves elements around.
135 : _Temporary_value __x_copy(this, __x);
136 : _M_insert_aux(__pos, std::move(__x_copy._M_val()));
137 : #else
138 : _M_insert_aux(__position, __x);
139 : #endif
140 : }
141 : else
142 : #if __cplusplus >= 201103L
143 : _M_realloc_insert(begin() + (__position - cbegin()), __x);
144 : #else
145 : _M_realloc_insert(__position, __x);
146 : #endif
147 :
148 : return iterator(this->_M_impl._M_start + __n);
149 : }
150 :
151 : template<typename _Tp, typename _Alloc>
152 : typename vector<_Tp, _Alloc>::iterator
153 : vector<_Tp, _Alloc>::
154 : _M_erase(iterator __position)
155 : {
156 : if (__position + 1 != end())
157 : _GLIBCXX_MOVE3(__position + 1, end(), __position);
158 : --this->_M_impl._M_finish;
159 : _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
160 : return __position;
161 : }
162 :
163 : template<typename _Tp, typename _Alloc>
164 : typename vector<_Tp, _Alloc>::iterator
165 : vector<_Tp, _Alloc>::
166 : _M_erase(iterator __first, iterator __last)
167 : {
168 : if (__first != __last)
169 : {
170 : if (__last != end())
171 : _GLIBCXX_MOVE3(__last, end(), __first);
172 : _M_erase_at_end(__first.base() + (end() - __last));
173 : }
174 : return __first;
175 : }
176 :
177 : template<typename _Tp, typename _Alloc>
178 : vector<_Tp, _Alloc>&
179 : vector<_Tp, _Alloc>::
180 : operator=(const vector<_Tp, _Alloc>& __x)
181 : {
182 : if (&__x != this)
183 : {
184 : #if __cplusplus >= 201103L
185 : if (_Alloc_traits::_S_propagate_on_copy_assign())
186 : {
187 : if (!_Alloc_traits::_S_always_equal()
188 : && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
189 : {
190 : // replacement allocator cannot free existing storage
191 : this->clear();
192 : _M_deallocate(this->_M_impl._M_start,
193 : this->_M_impl._M_end_of_storage
194 : - this->_M_impl._M_start);
195 : this->_M_impl._M_start = nullptr;
196 : this->_M_impl._M_finish = nullptr;
197 : this->_M_impl._M_end_of_storage = nullptr;
198 : }
199 : std::__alloc_on_copy(_M_get_Tp_allocator(),
200 : __x._M_get_Tp_allocator());
201 : }
202 : #endif
203 : const size_type __xlen = __x.size();
204 : if (__xlen > capacity())
205 : {
206 : pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
207 : __x.end());
208 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
209 : _M_get_Tp_allocator());
210 : _M_deallocate(this->_M_impl._M_start,
211 : this->_M_impl._M_end_of_storage
212 : - this->_M_impl._M_start);
213 : this->_M_impl._M_start = __tmp;
214 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
215 : }
216 : else if (size() >= __xlen)
217 : {
218 : std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
219 : end(), _M_get_Tp_allocator());
220 : }
221 : else
222 : {
223 : std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
224 : this->_M_impl._M_start);
225 : std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
226 : __x._M_impl._M_finish,
227 : this->_M_impl._M_finish,
228 : _M_get_Tp_allocator());
229 : }
230 : this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
231 : }
232 : return *this;
233 : }
234 :
235 : template<typename _Tp, typename _Alloc>
236 : void
237 : vector<_Tp, _Alloc>::
238 : _M_fill_assign(size_t __n, const value_type& __val)
239 : {
240 : if (__n > capacity())
241 : {
242 : vector __tmp(__n, __val, _M_get_Tp_allocator());
243 : __tmp._M_impl._M_swap_data(this->_M_impl);
244 : }
245 : else if (__n > size())
246 : {
247 : std::fill(begin(), end(), __val);
248 : this->_M_impl._M_finish =
249 : std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
250 : __n - size(), __val,
251 : _M_get_Tp_allocator());
252 : }
253 : else
254 : _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
255 : }
256 :
257 : template<typename _Tp, typename _Alloc>
258 : template<typename _InputIterator>
259 : void
260 : vector<_Tp, _Alloc>::
261 : _M_assign_aux(_InputIterator __first, _InputIterator __last,
262 : std::input_iterator_tag)
263 : {
264 : pointer __cur(this->_M_impl._M_start);
265 : for (; __first != __last && __cur != this->_M_impl._M_finish;
266 : ++__cur, ++__first)
267 : *__cur = *__first;
268 : if (__first == __last)
269 : _M_erase_at_end(__cur);
270 : else
271 : _M_range_insert(end(), __first, __last,
272 : std::__iterator_category(__first));
273 : }
274 :
275 : template<typename _Tp, typename _Alloc>
276 : template<typename _ForwardIterator>
277 : void
278 : vector<_Tp, _Alloc>::
279 : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
280 : std::forward_iterator_tag)
281 : {
282 : const size_type __len = std::distance(__first, __last);
283 :
284 : if (__len > capacity())
285 : {
286 : pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
287 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
288 : _M_get_Tp_allocator());
289 : _M_deallocate(this->_M_impl._M_start,
290 : this->_M_impl._M_end_of_storage
291 : - this->_M_impl._M_start);
292 : this->_M_impl._M_start = __tmp;
293 : this->_M_impl._M_finish = this->_M_impl._M_start + __len;
294 : this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
295 : }
296 : else if (size() >= __len)
297 : _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
298 : else
299 : {
300 : _ForwardIterator __mid = __first;
301 : std::advance(__mid, size());
302 : std::copy(__first, __mid, this->_M_impl._M_start);
303 : this->_M_impl._M_finish =
304 : std::__uninitialized_copy_a(__mid, __last,
305 : this->_M_impl._M_finish,
306 : _M_get_Tp_allocator());
307 : }
308 : }
309 :
310 : #if __cplusplus >= 201103L
311 : template<typename _Tp, typename _Alloc>
312 : auto
313 : vector<_Tp, _Alloc>::
314 : _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
315 : {
316 : const auto __n = __position - cbegin();
317 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
318 : if (__position == cend())
319 : {
320 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
321 : std::move(__v));
322 : ++this->_M_impl._M_finish;
323 : }
324 : else
325 : _M_insert_aux(begin() + __n, std::move(__v));
326 : else
327 : _M_realloc_insert(begin() + __n, std::move(__v));
328 :
329 : return iterator(this->_M_impl._M_start + __n);
330 : }
331 :
332 : template<typename _Tp, typename _Alloc>
333 : template<typename... _Args>
334 : auto
335 : vector<_Tp, _Alloc>::
336 : _M_emplace_aux(const_iterator __position, _Args&&... __args)
337 : -> iterator
338 : {
339 : const auto __n = __position - cbegin();
340 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
341 : if (__position == cend())
342 : {
343 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
344 : std::forward<_Args>(__args)...);
345 : ++this->_M_impl._M_finish;
346 : }
347 : else
348 : {
349 : // We need to construct a temporary because something in __args...
350 : // could alias one of the elements of the container and so we
351 : // need to use it before _M_insert_aux moves elements around.
352 : _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
353 : _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
354 : }
355 : else
356 : _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
357 :
358 : return iterator(this->_M_impl._M_start + __n);
359 : }
360 :
361 : template<typename _Tp, typename _Alloc>
362 : template<typename _Arg>
363 : void
364 : vector<_Tp, _Alloc>::
365 : _M_insert_aux(iterator __position, _Arg&& __arg)
366 : #else
367 : template<typename _Tp, typename _Alloc>
368 : void
369 : vector<_Tp, _Alloc>::
370 : _M_insert_aux(iterator __position, const _Tp& __x)
371 : #endif
372 : {
373 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
374 : _GLIBCXX_MOVE(*(this->_M_impl._M_finish
375 : - 1)));
376 : ++this->_M_impl._M_finish;
377 : #if __cplusplus < 201103L
378 : _Tp __x_copy = __x;
379 : #endif
380 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
381 : this->_M_impl._M_finish - 2,
382 : this->_M_impl._M_finish - 1);
383 : #if __cplusplus < 201103L
384 : *__position = __x_copy;
385 : #else
386 : *__position = std::forward<_Arg>(__arg);
387 : #endif
388 : }
389 :
390 : #if __cplusplus >= 201103L
391 : template<typename _Tp, typename _Alloc>
392 : template<typename... _Args>
393 : void
394 291 : vector<_Tp, _Alloc>::
395 : _M_realloc_insert(iterator __position, _Args&&... __args)
396 : #else
397 : template<typename _Tp, typename _Alloc>
398 : void
399 : vector<_Tp, _Alloc>::
400 : _M_realloc_insert(iterator __position, const _Tp& __x)
401 : #endif
402 : {
403 291 : const size_type __len =
404 : _M_check_len(size_type(1), "vector::_M_realloc_insert");
405 291 : const size_type __elems_before = __position - begin();
406 291 : pointer __new_start(this->_M_allocate(__len));
407 291 : pointer __new_finish(__new_start);
408 : __try
409 : {
410 : // The order of the three operations is dictated by the C++11
411 : // case, where the moves could alter a new element belonging
412 : // to the existing vector. This is an issue only for callers
413 : // taking the element by lvalue ref (see last bullet of C++11
414 : // [res.on.arguments]).
415 582 : _Alloc_traits::construct(this->_M_impl,
416 291 : __new_start + __elems_before,
417 : #if __cplusplus >= 201103L
418 : std::forward<_Args>(__args)...);
419 : #else
420 : __x);
421 : #endif
422 291 : __new_finish = pointer();
423 :
424 291 : __new_finish
425 : = std::__uninitialized_move_if_noexcept_a
426 291 : (this->_M_impl._M_start, __position.base(),
427 291 : __new_start, _M_get_Tp_allocator());
428 :
429 291 : ++__new_finish;
430 :
431 291 : __new_finish
432 : = std::__uninitialized_move_if_noexcept_a
433 291 : (__position.base(), this->_M_impl._M_finish,
434 291 : __new_finish, _M_get_Tp_allocator());
435 : }
436 0 : __catch(...)
437 : {
438 0 : if (!__new_finish)
439 0 : _Alloc_traits::destroy(this->_M_impl,
440 0 : __new_start + __elems_before);
441 : else
442 0 : std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
443 0 : _M_deallocate(__new_start, __len);
444 0 : __throw_exception_again;
445 : }
446 291 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
447 291 : _M_get_Tp_allocator());
448 582 : _M_deallocate(this->_M_impl._M_start,
449 291 : this->_M_impl._M_end_of_storage
450 291 : - this->_M_impl._M_start);
451 291 : this->_M_impl._M_start = __new_start;
452 291 : this->_M_impl._M_finish = __new_finish;
453 291 : this->_M_impl._M_end_of_storage = __new_start + __len;
454 291 : }
455 :
456 : template<typename _Tp, typename _Alloc>
457 : void
458 : vector<_Tp, _Alloc>::
459 : _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
460 : {
461 : if (__n != 0)
462 : {
463 : if (size_type(this->_M_impl._M_end_of_storage
464 : - this->_M_impl._M_finish) >= __n)
465 : {
466 : #if __cplusplus < 201103L
467 : value_type __x_copy = __x;
468 : #else
469 : _Temporary_value __tmp(this, __x);
470 : value_type& __x_copy = __tmp._M_val();
471 : #endif
472 : const size_type __elems_after = end() - __position;
473 : pointer __old_finish(this->_M_impl._M_finish);
474 : if (__elems_after > __n)
475 : {
476 : std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
477 : this->_M_impl._M_finish,
478 : this->_M_impl._M_finish,
479 : _M_get_Tp_allocator());
480 : this->_M_impl._M_finish += __n;
481 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
482 : __old_finish - __n, __old_finish);
483 : std::fill(__position.base(), __position.base() + __n,
484 : __x_copy);
485 : }
486 : else
487 : {
488 : this->_M_impl._M_finish =
489 : std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
490 : __n - __elems_after,
491 : __x_copy,
492 : _M_get_Tp_allocator());
493 : std::__uninitialized_move_a(__position.base(), __old_finish,
494 : this->_M_impl._M_finish,
495 : _M_get_Tp_allocator());
496 : this->_M_impl._M_finish += __elems_after;
497 : std::fill(__position.base(), __old_finish, __x_copy);
498 : }
499 : }
500 : else
501 : {
502 : const size_type __len =
503 : _M_check_len(__n, "vector::_M_fill_insert");
504 : const size_type __elems_before = __position - begin();
505 : pointer __new_start(this->_M_allocate(__len));
506 : pointer __new_finish(__new_start);
507 : __try
508 : {
509 : // See _M_realloc_insert above.
510 : std::__uninitialized_fill_n_a(__new_start + __elems_before,
511 : __n, __x,
512 : _M_get_Tp_allocator());
513 : __new_finish = pointer();
514 :
515 : __new_finish
516 : = std::__uninitialized_move_if_noexcept_a
517 : (this->_M_impl._M_start, __position.base(),
518 : __new_start, _M_get_Tp_allocator());
519 :
520 : __new_finish += __n;
521 :
522 : __new_finish
523 : = std::__uninitialized_move_if_noexcept_a
524 : (__position.base(), this->_M_impl._M_finish,
525 : __new_finish, _M_get_Tp_allocator());
526 : }
527 : __catch(...)
528 : {
529 : if (!__new_finish)
530 : std::_Destroy(__new_start + __elems_before,
531 : __new_start + __elems_before + __n,
532 : _M_get_Tp_allocator());
533 : else
534 : std::_Destroy(__new_start, __new_finish,
535 : _M_get_Tp_allocator());
536 : _M_deallocate(__new_start, __len);
537 : __throw_exception_again;
538 : }
539 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
540 : _M_get_Tp_allocator());
541 : _M_deallocate(this->_M_impl._M_start,
542 : this->_M_impl._M_end_of_storage
543 : - this->_M_impl._M_start);
544 : this->_M_impl._M_start = __new_start;
545 : this->_M_impl._M_finish = __new_finish;
546 : this->_M_impl._M_end_of_storage = __new_start + __len;
547 : }
548 : }
549 : }
550 :
551 : #if __cplusplus >= 201103L
552 : template<typename _Tp, typename _Alloc>
553 : void
554 : vector<_Tp, _Alloc>::
555 : _M_default_append(size_type __n)
556 : {
557 : if (__n != 0)
558 : {
559 : if (size_type(this->_M_impl._M_end_of_storage
560 : - this->_M_impl._M_finish) >= __n)
561 : {
562 : this->_M_impl._M_finish =
563 : std::__uninitialized_default_n_a(this->_M_impl._M_finish,
564 : __n, _M_get_Tp_allocator());
565 : }
566 : else
567 : {
568 : const size_type __len =
569 : _M_check_len(__n, "vector::_M_default_append");
570 : const size_type __size = this->size();
571 : pointer __new_start(this->_M_allocate(__len));
572 : pointer __destroy_from = pointer();
573 : __try
574 : {
575 : std::__uninitialized_default_n_a(__new_start + __size,
576 : __n, _M_get_Tp_allocator());
577 : __destroy_from = __new_start + __size;
578 : std::__uninitialized_move_if_noexcept_a(
579 : this->_M_impl._M_start, this->_M_impl._M_finish,
580 : __new_start, _M_get_Tp_allocator());
581 : }
582 : __catch(...)
583 : {
584 : if (__destroy_from)
585 : std::_Destroy(__destroy_from, __destroy_from + __n,
586 : _M_get_Tp_allocator());
587 : _M_deallocate(__new_start, __len);
588 : __throw_exception_again;
589 : }
590 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
591 : _M_get_Tp_allocator());
592 : _M_deallocate(this->_M_impl._M_start,
593 : this->_M_impl._M_end_of_storage
594 : - this->_M_impl._M_start);
595 : this->_M_impl._M_start = __new_start;
596 : this->_M_impl._M_finish = __new_start + __size + __n;
597 : this->_M_impl._M_end_of_storage = __new_start + __len;
598 : }
599 : }
600 : }
601 :
602 : template<typename _Tp, typename _Alloc>
603 : bool
604 : vector<_Tp, _Alloc>::
605 : _M_shrink_to_fit()
606 : {
607 : if (capacity() == size())
608 : return false;
609 : return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
610 : }
611 : #endif
612 :
613 : template<typename _Tp, typename _Alloc>
614 : template<typename _InputIterator>
615 : void
616 : vector<_Tp, _Alloc>::
617 : _M_range_insert(iterator __pos, _InputIterator __first,
618 : _InputIterator __last, std::input_iterator_tag)
619 : {
620 : for (; __first != __last; ++__first)
621 : {
622 : __pos = insert(__pos, *__first);
623 : ++__pos;
624 : }
625 : }
626 :
627 : template<typename _Tp, typename _Alloc>
628 : template<typename _ForwardIterator>
629 : void
630 : vector<_Tp, _Alloc>::
631 : _M_range_insert(iterator __position, _ForwardIterator __first,
632 : _ForwardIterator __last, std::forward_iterator_tag)
633 : {
634 : if (__first != __last)
635 : {
636 : const size_type __n = std::distance(__first, __last);
637 : if (size_type(this->_M_impl._M_end_of_storage
638 : - this->_M_impl._M_finish) >= __n)
639 : {
640 : const size_type __elems_after = end() - __position;
641 : pointer __old_finish(this->_M_impl._M_finish);
642 : if (__elems_after > __n)
643 : {
644 : std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
645 : this->_M_impl._M_finish,
646 : this->_M_impl._M_finish,
647 : _M_get_Tp_allocator());
648 : this->_M_impl._M_finish += __n;
649 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
650 : __old_finish - __n, __old_finish);
651 : std::copy(__first, __last, __position);
652 : }
653 : else
654 : {
655 : _ForwardIterator __mid = __first;
656 : std::advance(__mid, __elems_after);
657 : std::__uninitialized_copy_a(__mid, __last,
658 : this->_M_impl._M_finish,
659 : _M_get_Tp_allocator());
660 : this->_M_impl._M_finish += __n - __elems_after;
661 : std::__uninitialized_move_a(__position.base(),
662 : __old_finish,
663 : this->_M_impl._M_finish,
664 : _M_get_Tp_allocator());
665 : this->_M_impl._M_finish += __elems_after;
666 : std::copy(__first, __mid, __position);
667 : }
668 : }
669 : else
670 : {
671 : const size_type __len =
672 : _M_check_len(__n, "vector::_M_range_insert");
673 : pointer __new_start(this->_M_allocate(__len));
674 : pointer __new_finish(__new_start);
675 : __try
676 : {
677 : __new_finish
678 : = std::__uninitialized_move_if_noexcept_a
679 : (this->_M_impl._M_start, __position.base(),
680 : __new_start, _M_get_Tp_allocator());
681 : __new_finish
682 : = std::__uninitialized_copy_a(__first, __last,
683 : __new_finish,
684 : _M_get_Tp_allocator());
685 : __new_finish
686 : = std::__uninitialized_move_if_noexcept_a
687 : (__position.base(), this->_M_impl._M_finish,
688 : __new_finish, _M_get_Tp_allocator());
689 : }
690 : __catch(...)
691 : {
692 : std::_Destroy(__new_start, __new_finish,
693 : _M_get_Tp_allocator());
694 : _M_deallocate(__new_start, __len);
695 : __throw_exception_again;
696 : }
697 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
698 : _M_get_Tp_allocator());
699 : _M_deallocate(this->_M_impl._M_start,
700 : this->_M_impl._M_end_of_storage
701 : - this->_M_impl._M_start);
702 : this->_M_impl._M_start = __new_start;
703 : this->_M_impl._M_finish = __new_finish;
704 : this->_M_impl._M_end_of_storage = __new_start + __len;
705 : }
706 : }
707 : }
708 :
709 :
710 : // vector<bool>
711 : template<typename _Alloc>
712 : void
713 : vector<bool, _Alloc>::
714 : _M_reallocate(size_type __n)
715 : {
716 : _Bit_pointer __q = this->_M_allocate(__n);
717 : iterator __start(std::__addressof(*__q), 0);
718 : iterator __finish(_M_copy_aligned(begin(), end(), __start));
719 : this->_M_deallocate();
720 : this->_M_impl._M_start = __start;
721 : this->_M_impl._M_finish = __finish;
722 : this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
723 : }
724 :
725 : template<typename _Alloc>
726 : void
727 : vector<bool, _Alloc>::
728 : _M_fill_insert(iterator __position, size_type __n, bool __x)
729 : {
730 : if (__n == 0)
731 : return;
732 : if (capacity() - size() >= __n)
733 : {
734 : std::copy_backward(__position, end(),
735 : this->_M_impl._M_finish + difference_type(__n));
736 : std::fill(__position, __position + difference_type(__n), __x);
737 : this->_M_impl._M_finish += difference_type(__n);
738 : }
739 : else
740 : {
741 : const size_type __len =
742 : _M_check_len(__n, "vector<bool>::_M_fill_insert");
743 : _Bit_pointer __q = this->_M_allocate(__len);
744 : iterator __start(std::__addressof(*__q), 0);
745 : iterator __i = _M_copy_aligned(begin(), __position, __start);
746 : std::fill(__i, __i + difference_type(__n), __x);
747 : iterator __finish = std::copy(__position, end(),
748 : __i + difference_type(__n));
749 : this->_M_deallocate();
750 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
751 : this->_M_impl._M_start = __start;
752 : this->_M_impl._M_finish = __finish;
753 : }
754 : }
755 :
756 : template<typename _Alloc>
757 : template<typename _ForwardIterator>
758 : void
759 : vector<bool, _Alloc>::
760 : _M_insert_range(iterator __position, _ForwardIterator __first,
761 : _ForwardIterator __last, std::forward_iterator_tag)
762 : {
763 : if (__first != __last)
764 : {
765 : size_type __n = std::distance(__first, __last);
766 : if (capacity() - size() >= __n)
767 : {
768 : std::copy_backward(__position, end(),
769 : this->_M_impl._M_finish
770 : + difference_type(__n));
771 : std::copy(__first, __last, __position);
772 : this->_M_impl._M_finish += difference_type(__n);
773 : }
774 : else
775 : {
776 : const size_type __len =
777 : _M_check_len(__n, "vector<bool>::_M_insert_range");
778 : _Bit_pointer __q = this->_M_allocate(__len);
779 : iterator __start(std::__addressof(*__q), 0);
780 : iterator __i = _M_copy_aligned(begin(), __position, __start);
781 : __i = std::copy(__first, __last, __i);
782 : iterator __finish = std::copy(__position, end(), __i);
783 : this->_M_deallocate();
784 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
785 : this->_M_impl._M_start = __start;
786 : this->_M_impl._M_finish = __finish;
787 : }
788 : }
789 : }
790 :
791 : template<typename _Alloc>
792 : void
793 : vector<bool, _Alloc>::
794 : _M_insert_aux(iterator __position, bool __x)
795 : {
796 : if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
797 : {
798 : std::copy_backward(__position, this->_M_impl._M_finish,
799 : this->_M_impl._M_finish + 1);
800 : *__position = __x;
801 : ++this->_M_impl._M_finish;
802 : }
803 : else
804 : {
805 : const size_type __len =
806 : _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
807 : _Bit_pointer __q = this->_M_allocate(__len);
808 : iterator __start(std::__addressof(*__q), 0);
809 : iterator __i = _M_copy_aligned(begin(), __position, __start);
810 : *__i++ = __x;
811 : iterator __finish = std::copy(__position, end(), __i);
812 : this->_M_deallocate();
813 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
814 : this->_M_impl._M_start = __start;
815 : this->_M_impl._M_finish = __finish;
816 : }
817 : }
818 :
819 : template<typename _Alloc>
820 : typename vector<bool, _Alloc>::iterator
821 : vector<bool, _Alloc>::
822 : _M_erase(iterator __position)
823 : {
824 : if (__position + 1 != end())
825 : std::copy(__position + 1, end(), __position);
826 : --this->_M_impl._M_finish;
827 : return __position;
828 : }
829 :
830 : template<typename _Alloc>
831 : typename vector<bool, _Alloc>::iterator
832 : vector<bool, _Alloc>::
833 : _M_erase(iterator __first, iterator __last)
834 : {
835 : if (__first != __last)
836 : _M_erase_at_end(std::copy(__last, end(), __first));
837 : return __first;
838 : }
839 :
840 : #if __cplusplus >= 201103L
841 : template<typename _Alloc>
842 : bool
843 : vector<bool, _Alloc>::
844 : _M_shrink_to_fit()
845 : {
846 : if (capacity() - size() < int(_S_word_bit))
847 : return false;
848 : __try
849 : {
850 : _M_reallocate(size());
851 : return true;
852 : }
853 : __catch(...)
854 : { return false; }
855 : }
856 : #endif
857 :
858 : _GLIBCXX_END_NAMESPACE_CONTAINER
859 : } // namespace std
860 :
861 : #if __cplusplus >= 201103L
862 :
863 : namespace std _GLIBCXX_VISIBILITY(default)
864 : {
865 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
866 :
867 : template<typename _Alloc>
868 : size_t
869 : hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
870 : operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
871 : {
872 : size_t __hash = 0;
873 : using _GLIBCXX_STD_C::_S_word_bit;
874 : using _GLIBCXX_STD_C::_Bit_type;
875 :
876 : const size_t __words = __b.size() / _S_word_bit;
877 : if (__words)
878 : {
879 : const size_t __clength = __words * sizeof(_Bit_type);
880 : __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
881 : }
882 :
883 : const size_t __extrabits = __b.size() % _S_word_bit;
884 : if (__extrabits)
885 : {
886 : _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
887 : __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
888 :
889 : const size_t __clength
890 : = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
891 : if (__words)
892 : __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
893 : else
894 : __hash = std::_Hash_impl::hash(&__hiword, __clength);
895 : }
896 :
897 : return __hash;
898 : }
899 :
900 : _GLIBCXX_END_NAMESPACE_VERSION
901 : } // namespace std
902 :
903 : #endif // C++11
904 :
905 : #endif /* _VECTOR_TCC */
|