1 | // Deque implementation (out of line) -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2019 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) 1997 |
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/deque.tcc |
52 | * This is an internal header file, included by other library headers. |
53 | * Do not attempt to use it directly. @headername{deque} |
54 | */ |
55 | |
56 | #ifndef _DEQUE_TCC |
57 | #define _DEQUE_TCC 1 |
58 | |
59 | namespace std _GLIBCXX_VISIBILITY(default) |
60 | { |
61 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
62 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
63 | |
64 | #if __cplusplus >= 201103L |
65 | template <typename _Tp, typename _Alloc> |
66 | void |
67 | deque<_Tp, _Alloc>:: |
68 | _M_default_initialize() |
69 | { |
70 | _Map_pointer __cur; |
71 | __try |
72 | { |
73 | for (__cur = this->_M_impl._M_start._M_node; |
74 | __cur < this->_M_impl._M_finish._M_node; |
75 | ++__cur) |
76 | std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), |
77 | _M_get_Tp_allocator()); |
78 | std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, |
79 | this->_M_impl._M_finish._M_cur, |
80 | _M_get_Tp_allocator()); |
81 | } |
82 | __catch(...) |
83 | { |
84 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
85 | _M_get_Tp_allocator()); |
86 | __throw_exception_again; |
87 | } |
88 | } |
89 | #endif |
90 | |
91 | template <typename _Tp, typename _Alloc> |
92 | deque<_Tp, _Alloc>& |
93 | deque<_Tp, _Alloc>:: |
94 | operator=(const deque& __x) |
95 | { |
96 | if (&__x != this) |
97 | { |
98 | #if __cplusplus >= 201103L |
99 | if (_Alloc_traits::_S_propagate_on_copy_assign()) |
100 | { |
101 | if (!_Alloc_traits::_S_always_equal() |
102 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) |
103 | { |
104 | // Replacement allocator cannot free existing storage, |
105 | // so deallocate everything and take copy of __x's data. |
106 | _M_replace_map(__x, __x.get_allocator()); |
107 | std::__alloc_on_copy(_M_get_Tp_allocator(), |
108 | __x._M_get_Tp_allocator()); |
109 | return *this; |
110 | } |
111 | std::__alloc_on_copy(_M_get_Tp_allocator(), |
112 | __x._M_get_Tp_allocator()); |
113 | } |
114 | #endif |
115 | const size_type __len = size(); |
116 | if (__len >= __x.size()) |
117 | _M_erase_at_end(std::copy(__x.begin(), __x.end(), |
118 | this->_M_impl._M_start)); |
119 | else |
120 | { |
121 | const_iterator __mid = __x.begin() + difference_type(__len); |
122 | std::copy(__x.begin(), __mid, this->_M_impl._M_start); |
123 | _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(), |
124 | std::random_access_iterator_tag()); |
125 | } |
126 | } |
127 | return *this; |
128 | } |
129 | |
130 | #if __cplusplus >= 201103L |
131 | template<typename _Tp, typename _Alloc> |
132 | template<typename... _Args> |
133 | #if __cplusplus > 201402L |
134 | typename deque<_Tp, _Alloc>::reference |
135 | #else |
136 | void |
137 | #endif |
138 | deque<_Tp, _Alloc>:: |
139 | emplace_front(_Args&&... __args) |
140 | { |
141 | if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) |
142 | { |
143 | _Alloc_traits::construct(this->_M_impl, |
144 | this->_M_impl._M_start._M_cur - 1, |
145 | std::forward<_Args>(__args)...); |
146 | --this->_M_impl._M_start._M_cur; |
147 | } |
148 | else |
149 | _M_push_front_aux(std::forward<_Args>(__args)...); |
150 | #if __cplusplus > 201402L |
151 | return front(); |
152 | #endif |
153 | } |
154 | |
155 | template<typename _Tp, typename _Alloc> |
156 | template<typename... _Args> |
157 | #if __cplusplus > 201402L |
158 | typename deque<_Tp, _Alloc>::reference |
159 | #else |
160 | void |
161 | #endif |
162 | deque<_Tp, _Alloc>:: |
163 | emplace_back(_Args&&... __args) |
164 | { |
165 | if (this->_M_impl._M_finish._M_cur |
166 | != this->_M_impl._M_finish._M_last - 1) |
167 | { |
168 | _Alloc_traits::construct(this->_M_impl, |
169 | this->_M_impl._M_finish._M_cur, |
170 | std::forward<_Args>(__args)...); |
171 | ++this->_M_impl._M_finish._M_cur; |
172 | } |
173 | else |
174 | _M_push_back_aux(std::forward<_Args>(__args)...); |
175 | #if __cplusplus > 201402L |
176 | return back(); |
177 | #endif |
178 | } |
179 | #endif |
180 | |
181 | #if __cplusplus >= 201103L |
182 | template<typename _Tp, typename _Alloc> |
183 | template<typename... _Args> |
184 | typename deque<_Tp, _Alloc>::iterator |
185 | deque<_Tp, _Alloc>:: |
186 | emplace(const_iterator __position, _Args&&... __args) |
187 | { |
188 | if (__position._M_cur == this->_M_impl._M_start._M_cur) |
189 | { |
190 | emplace_front(std::forward<_Args>(__args)...); |
191 | return this->_M_impl._M_start; |
192 | } |
193 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) |
194 | { |
195 | emplace_back(std::forward<_Args>(__args)...); |
196 | iterator __tmp = this->_M_impl._M_finish; |
197 | --__tmp; |
198 | return __tmp; |
199 | } |
200 | else |
201 | return _M_insert_aux(__position._M_const_cast(), |
202 | std::forward<_Args>(__args)...); |
203 | } |
204 | #endif |
205 | |
206 | template <typename _Tp, typename _Alloc> |
207 | typename deque<_Tp, _Alloc>::iterator |
208 | deque<_Tp, _Alloc>:: |
209 | #if __cplusplus >= 201103L |
210 | insert(const_iterator __position, const value_type& __x) |
211 | #else |
212 | insert(iterator __position, const value_type& __x) |
213 | #endif |
214 | { |
215 | if (__position._M_cur == this->_M_impl._M_start._M_cur) |
216 | { |
217 | push_front(__x); |
218 | return this->_M_impl._M_start; |
219 | } |
220 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) |
221 | { |
222 | push_back(__x); |
223 | iterator __tmp = this->_M_impl._M_finish; |
224 | --__tmp; |
225 | return __tmp; |
226 | } |
227 | else |
228 | return _M_insert_aux(__position._M_const_cast(), __x); |
229 | } |
230 | |
231 | template <typename _Tp, typename _Alloc> |
232 | typename deque<_Tp, _Alloc>::iterator |
233 | deque<_Tp, _Alloc>:: |
234 | _M_erase(iterator __position) |
235 | { |
236 | iterator __next = __position; |
237 | ++__next; |
238 | const difference_type __index = __position - begin(); |
239 | if (static_cast<size_type>(__index) < (size() >> 1)) |
240 | { |
241 | if (__position != begin()) |
242 | _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); |
243 | pop_front(); |
244 | } |
245 | else |
246 | { |
247 | if (__next != end()) |
248 | _GLIBCXX_MOVE3(__next, end(), __position); |
249 | pop_back(); |
250 | } |
251 | return begin() + __index; |
252 | } |
253 | |
254 | template <typename _Tp, typename _Alloc> |
255 | typename deque<_Tp, _Alloc>::iterator |
256 | deque<_Tp, _Alloc>:: |
257 | _M_erase(iterator __first, iterator __last) |
258 | { |
259 | if (__first == __last) |
260 | return __first; |
261 | else if (__first == begin() && __last == end()) |
262 | { |
263 | clear(); |
264 | return end(); |
265 | } |
266 | else |
267 | { |
268 | const difference_type __n = __last - __first; |
269 | const difference_type __elems_before = __first - begin(); |
270 | if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) |
271 | { |
272 | if (__first != begin()) |
273 | _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); |
274 | _M_erase_at_begin(begin() + __n); |
275 | } |
276 | else |
277 | { |
278 | if (__last != end()) |
279 | _GLIBCXX_MOVE3(__last, end(), __first); |
280 | _M_erase_at_end(end() - __n); |
281 | } |
282 | return begin() + __elems_before; |
283 | } |
284 | } |
285 | |
286 | template <typename _Tp, class _Alloc> |
287 | template <typename _InputIterator> |
288 | void |
289 | deque<_Tp, _Alloc>:: |
290 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |
291 | std::input_iterator_tag) |
292 | { |
293 | iterator __cur = begin(); |
294 | for (; __first != __last && __cur != end(); ++__cur, (void)++__first) |
295 | *__cur = *__first; |
296 | if (__first == __last) |
297 | _M_erase_at_end(__cur); |
298 | else |
299 | _M_range_insert_aux(end(), __first, __last, |
300 | std::__iterator_category(__first)); |
301 | } |
302 | |
303 | template <typename _Tp, typename _Alloc> |
304 | void |
305 | deque<_Tp, _Alloc>:: |
306 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
307 | { |
308 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
309 | { |
310 | iterator __new_start = _M_reserve_elements_at_front(__n); |
311 | __try |
312 | { |
313 | std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, |
314 | __x, _M_get_Tp_allocator()); |
315 | this->_M_impl._M_start = __new_start; |
316 | } |
317 | __catch(...) |
318 | { |
319 | _M_destroy_nodes(__new_start._M_node, |
320 | this->_M_impl._M_start._M_node); |
321 | __throw_exception_again; |
322 | } |
323 | } |
324 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
325 | { |
326 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
327 | __try |
328 | { |
329 | std::__uninitialized_fill_a(this->_M_impl._M_finish, |
330 | __new_finish, __x, |
331 | _M_get_Tp_allocator()); |
332 | this->_M_impl._M_finish = __new_finish; |
333 | } |
334 | __catch(...) |
335 | { |
336 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
337 | __new_finish._M_node + 1); |
338 | __throw_exception_again; |
339 | } |
340 | } |
341 | else |
342 | _M_insert_aux(__pos, __n, __x); |
343 | } |
344 | |
345 | #if __cplusplus >= 201103L |
346 | template <typename _Tp, typename _Alloc> |
347 | void |
348 | deque<_Tp, _Alloc>:: |
349 | _M_default_append(size_type __n) |
350 | { |
351 | if (__n) |
352 | { |
353 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
354 | __try |
355 | { |
356 | std::__uninitialized_default_a(this->_M_impl._M_finish, |
357 | __new_finish, |
358 | _M_get_Tp_allocator()); |
359 | this->_M_impl._M_finish = __new_finish; |
360 | } |
361 | __catch(...) |
362 | { |
363 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
364 | __new_finish._M_node + 1); |
365 | __throw_exception_again; |
366 | } |
367 | } |
368 | } |
369 | |
370 | template <typename _Tp, typename _Alloc> |
371 | bool |
372 | deque<_Tp, _Alloc>:: |
373 | _M_shrink_to_fit() |
374 | { |
375 | const difference_type __front_capacity |
376 | = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); |
377 | if (__front_capacity == 0) |
378 | return false; |
379 | |
380 | const difference_type __back_capacity |
381 | = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); |
382 | if (__front_capacity + __back_capacity < _S_buffer_size()) |
383 | return false; |
384 | |
385 | return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); |
386 | } |
387 | #endif |
388 | |
389 | template <typename _Tp, typename _Alloc> |
390 | void |
391 | deque<_Tp, _Alloc>:: |
392 | _M_fill_initialize(const value_type& __value) |
393 | { |
394 | _Map_pointer __cur; |
395 | __try |
396 | { |
397 | for (__cur = this->_M_impl._M_start._M_node; |
398 | __cur < this->_M_impl._M_finish._M_node; |
399 | ++__cur) |
400 | std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), |
401 | __value, _M_get_Tp_allocator()); |
402 | std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, |
403 | this->_M_impl._M_finish._M_cur, |
404 | __value, _M_get_Tp_allocator()); |
405 | } |
406 | __catch(...) |
407 | { |
408 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
409 | _M_get_Tp_allocator()); |
410 | __throw_exception_again; |
411 | } |
412 | } |
413 | |
414 | template <typename _Tp, typename _Alloc> |
415 | template <typename _InputIterator> |
416 | void |
417 | deque<_Tp, _Alloc>:: |
418 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
419 | std::input_iterator_tag) |
420 | { |
421 | this->_M_initialize_map(0); |
422 | __try |
423 | { |
424 | for (; __first != __last; ++__first) |
425 | #if __cplusplus >= 201103L |
426 | emplace_back(*__first); |
427 | #else |
428 | push_back(*__first); |
429 | #endif |
430 | } |
431 | __catch(...) |
432 | { |
433 | clear(); |
434 | __throw_exception_again; |
435 | } |
436 | } |
437 | |
438 | template <typename _Tp, typename _Alloc> |
439 | template <typename _ForwardIterator> |
440 | void |
441 | deque<_Tp, _Alloc>:: |
442 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
443 | std::forward_iterator_tag) |
444 | { |
445 | const size_type __n = std::distance(__first, __last); |
446 | this->_M_initialize_map(_S_check_init_len(__n, _M_get_Tp_allocator())); |
447 | |
448 | _Map_pointer __cur_node; |
449 | __try |
450 | { |
451 | for (__cur_node = this->_M_impl._M_start._M_node; |
452 | __cur_node < this->_M_impl._M_finish._M_node; |
453 | ++__cur_node) |
454 | { |
455 | _ForwardIterator __mid = __first; |
456 | std::advance(__mid, _S_buffer_size()); |
457 | std::__uninitialized_copy_a(__first, __mid, *__cur_node, |
458 | _M_get_Tp_allocator()); |
459 | __first = __mid; |
460 | } |
461 | std::__uninitialized_copy_a(__first, __last, |
462 | this->_M_impl._M_finish._M_first, |
463 | _M_get_Tp_allocator()); |
464 | } |
465 | __catch(...) |
466 | { |
467 | std::_Destroy(this->_M_impl._M_start, |
468 | iterator(*__cur_node, __cur_node), |
469 | _M_get_Tp_allocator()); |
470 | __throw_exception_again; |
471 | } |
472 | } |
473 | |
474 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
475 | template<typename _Tp, typename _Alloc> |
476 | #if __cplusplus >= 201103L |
477 | template<typename... _Args> |
478 | void |
479 | deque<_Tp, _Alloc>:: |
480 | _M_push_back_aux(_Args&&... __args) |
481 | #else |
482 | void |
483 | deque<_Tp, _Alloc>:: |
484 | _M_push_back_aux(const value_type& __t) |
485 | #endif |
486 | { |
487 | if (size() == max_size()) |
488 | __throw_length_error( |
489 | __N("cannot create std::deque larger than max_size()" )); |
490 | |
491 | _M_reserve_map_at_back(); |
492 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); |
493 | __try |
494 | { |
495 | #if __cplusplus >= 201103L |
496 | _Alloc_traits::construct(this->_M_impl, |
497 | this->_M_impl._M_finish._M_cur, |
498 | std::forward<_Args>(__args)...); |
499 | #else |
500 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); |
501 | #endif |
502 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
503 | + 1); |
504 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; |
505 | } |
506 | __catch(...) |
507 | { |
508 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); |
509 | __throw_exception_again; |
510 | } |
511 | } |
512 | |
513 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
514 | template<typename _Tp, typename _Alloc> |
515 | #if __cplusplus >= 201103L |
516 | template<typename... _Args> |
517 | void |
518 | deque<_Tp, _Alloc>:: |
519 | _M_push_front_aux(_Args&&... __args) |
520 | #else |
521 | void |
522 | deque<_Tp, _Alloc>:: |
523 | _M_push_front_aux(const value_type& __t) |
524 | #endif |
525 | { |
526 | if (size() == max_size()) |
527 | __throw_length_error( |
528 | __N("cannot create std::deque larger than max_size()" )); |
529 | |
530 | _M_reserve_map_at_front(); |
531 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); |
532 | __try |
533 | { |
534 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node |
535 | - 1); |
536 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; |
537 | #if __cplusplus >= 201103L |
538 | _Alloc_traits::construct(this->_M_impl, |
539 | this->_M_impl._M_start._M_cur, |
540 | std::forward<_Args>(__args)...); |
541 | #else |
542 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); |
543 | #endif |
544 | } |
545 | __catch(...) |
546 | { |
547 | ++this->_M_impl._M_start; |
548 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); |
549 | __throw_exception_again; |
550 | } |
551 | } |
552 | |
553 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
554 | template <typename _Tp, typename _Alloc> |
555 | void deque<_Tp, _Alloc>:: |
556 | _M_pop_back_aux() |
557 | { |
558 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
559 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); |
560 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; |
561 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
562 | this->_M_impl._M_finish._M_cur); |
563 | } |
564 | |
565 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
566 | // Note that if the deque has at least one element (a precondition for this |
567 | // member function), and if |
568 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, |
569 | // then the deque must have at least two nodes. |
570 | template <typename _Tp, typename _Alloc> |
571 | void deque<_Tp, _Alloc>:: |
572 | _M_pop_front_aux() |
573 | { |
574 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
575 | this->_M_impl._M_start._M_cur); |
576 | _M_deallocate_node(this->_M_impl._M_start._M_first); |
577 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); |
578 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; |
579 | } |
580 | |
581 | template <typename _Tp, typename _Alloc> |
582 | template <typename _InputIterator> |
583 | void |
584 | deque<_Tp, _Alloc>:: |
585 | _M_range_insert_aux(iterator __pos, |
586 | _InputIterator __first, _InputIterator __last, |
587 | std::input_iterator_tag) |
588 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
589 | |
590 | template <typename _Tp, typename _Alloc> |
591 | template <typename _ForwardIterator> |
592 | void |
593 | deque<_Tp, _Alloc>:: |
594 | _M_range_insert_aux(iterator __pos, |
595 | _ForwardIterator __first, _ForwardIterator __last, |
596 | std::forward_iterator_tag) |
597 | { |
598 | const size_type __n = std::distance(__first, __last); |
599 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
600 | { |
601 | iterator __new_start = _M_reserve_elements_at_front(__n); |
602 | __try |
603 | { |
604 | std::__uninitialized_copy_a(__first, __last, __new_start, |
605 | _M_get_Tp_allocator()); |
606 | this->_M_impl._M_start = __new_start; |
607 | } |
608 | __catch(...) |
609 | { |
610 | _M_destroy_nodes(__new_start._M_node, |
611 | this->_M_impl._M_start._M_node); |
612 | __throw_exception_again; |
613 | } |
614 | } |
615 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
616 | { |
617 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
618 | __try |
619 | { |
620 | std::__uninitialized_copy_a(__first, __last, |
621 | this->_M_impl._M_finish, |
622 | _M_get_Tp_allocator()); |
623 | this->_M_impl._M_finish = __new_finish; |
624 | } |
625 | __catch(...) |
626 | { |
627 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
628 | __new_finish._M_node + 1); |
629 | __throw_exception_again; |
630 | } |
631 | } |
632 | else |
633 | _M_insert_aux(__pos, __first, __last, __n); |
634 | } |
635 | |
636 | template<typename _Tp, typename _Alloc> |
637 | #if __cplusplus >= 201103L |
638 | template<typename... _Args> |
639 | typename deque<_Tp, _Alloc>::iterator |
640 | deque<_Tp, _Alloc>:: |
641 | _M_insert_aux(iterator __pos, _Args&&... __args) |
642 | { |
643 | value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy |
644 | #else |
645 | typename deque<_Tp, _Alloc>::iterator |
646 | deque<_Tp, _Alloc>:: |
647 | _M_insert_aux(iterator __pos, const value_type& __x) |
648 | { |
649 | value_type __x_copy = __x; // XXX copy |
650 | #endif |
651 | difference_type __index = __pos - this->_M_impl._M_start; |
652 | if (static_cast<size_type>(__index) < size() / 2) |
653 | { |
654 | push_front(_GLIBCXX_MOVE(front())); |
655 | iterator __front1 = this->_M_impl._M_start; |
656 | ++__front1; |
657 | iterator __front2 = __front1; |
658 | ++__front2; |
659 | __pos = this->_M_impl._M_start + __index; |
660 | iterator __pos1 = __pos; |
661 | ++__pos1; |
662 | _GLIBCXX_MOVE3(__front2, __pos1, __front1); |
663 | } |
664 | else |
665 | { |
666 | push_back(_GLIBCXX_MOVE(back())); |
667 | iterator __back1 = this->_M_impl._M_finish; |
668 | --__back1; |
669 | iterator __back2 = __back1; |
670 | --__back2; |
671 | __pos = this->_M_impl._M_start + __index; |
672 | _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); |
673 | } |
674 | *__pos = _GLIBCXX_MOVE(__x_copy); |
675 | return __pos; |
676 | } |
677 | |
678 | template <typename _Tp, typename _Alloc> |
679 | void |
680 | deque<_Tp, _Alloc>:: |
681 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
682 | { |
683 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
684 | const size_type __length = this->size(); |
685 | value_type __x_copy = __x; |
686 | if (__elems_before < difference_type(__length / 2)) |
687 | { |
688 | iterator __new_start = _M_reserve_elements_at_front(__n); |
689 | iterator __old_start = this->_M_impl._M_start; |
690 | __pos = this->_M_impl._M_start + __elems_before; |
691 | __try |
692 | { |
693 | if (__elems_before >= difference_type(__n)) |
694 | { |
695 | iterator __start_n = (this->_M_impl._M_start |
696 | + difference_type(__n)); |
697 | std::__uninitialized_move_a(this->_M_impl._M_start, |
698 | __start_n, __new_start, |
699 | _M_get_Tp_allocator()); |
700 | this->_M_impl._M_start = __new_start; |
701 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
702 | std::fill(__pos - difference_type(__n), __pos, __x_copy); |
703 | } |
704 | else |
705 | { |
706 | std::__uninitialized_move_fill(this->_M_impl._M_start, |
707 | __pos, __new_start, |
708 | this->_M_impl._M_start, |
709 | __x_copy, |
710 | _M_get_Tp_allocator()); |
711 | this->_M_impl._M_start = __new_start; |
712 | std::fill(__old_start, __pos, __x_copy); |
713 | } |
714 | } |
715 | __catch(...) |
716 | { |
717 | _M_destroy_nodes(__new_start._M_node, |
718 | this->_M_impl._M_start._M_node); |
719 | __throw_exception_again; |
720 | } |
721 | } |
722 | else |
723 | { |
724 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
725 | iterator __old_finish = this->_M_impl._M_finish; |
726 | const difference_type __elems_after = |
727 | difference_type(__length) - __elems_before; |
728 | __pos = this->_M_impl._M_finish - __elems_after; |
729 | __try |
730 | { |
731 | if (__elems_after > difference_type(__n)) |
732 | { |
733 | iterator __finish_n = (this->_M_impl._M_finish |
734 | - difference_type(__n)); |
735 | std::__uninitialized_move_a(__finish_n, |
736 | this->_M_impl._M_finish, |
737 | this->_M_impl._M_finish, |
738 | _M_get_Tp_allocator()); |
739 | this->_M_impl._M_finish = __new_finish; |
740 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
741 | std::fill(__pos, __pos + difference_type(__n), __x_copy); |
742 | } |
743 | else |
744 | { |
745 | std::__uninitialized_fill_move(this->_M_impl._M_finish, |
746 | __pos + difference_type(__n), |
747 | __x_copy, __pos, |
748 | this->_M_impl._M_finish, |
749 | _M_get_Tp_allocator()); |
750 | this->_M_impl._M_finish = __new_finish; |
751 | std::fill(__pos, __old_finish, __x_copy); |
752 | } |
753 | } |
754 | __catch(...) |
755 | { |
756 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
757 | __new_finish._M_node + 1); |
758 | __throw_exception_again; |
759 | } |
760 | } |
761 | } |
762 | |
763 | template <typename _Tp, typename _Alloc> |
764 | template <typename _ForwardIterator> |
765 | void |
766 | deque<_Tp, _Alloc>:: |
767 | _M_insert_aux(iterator __pos, |
768 | _ForwardIterator __first, _ForwardIterator __last, |
769 | size_type __n) |
770 | { |
771 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
772 | const size_type __length = size(); |
773 | if (static_cast<size_type>(__elemsbefore) < __length / 2) |
774 | { |
775 | iterator __new_start = _M_reserve_elements_at_front(__n); |
776 | iterator __old_start = this->_M_impl._M_start; |
777 | __pos = this->_M_impl._M_start + __elemsbefore; |
778 | __try |
779 | { |
780 | if (__elemsbefore >= difference_type(__n)) |
781 | { |
782 | iterator __start_n = (this->_M_impl._M_start |
783 | + difference_type(__n)); |
784 | std::__uninitialized_move_a(this->_M_impl._M_start, |
785 | __start_n, __new_start, |
786 | _M_get_Tp_allocator()); |
787 | this->_M_impl._M_start = __new_start; |
788 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
789 | std::copy(__first, __last, __pos - difference_type(__n)); |
790 | } |
791 | else |
792 | { |
793 | _ForwardIterator __mid = __first; |
794 | std::advance(__mid, difference_type(__n) - __elemsbefore); |
795 | std::__uninitialized_move_copy(this->_M_impl._M_start, |
796 | __pos, __first, __mid, |
797 | __new_start, |
798 | _M_get_Tp_allocator()); |
799 | this->_M_impl._M_start = __new_start; |
800 | std::copy(__mid, __last, __old_start); |
801 | } |
802 | } |
803 | __catch(...) |
804 | { |
805 | _M_destroy_nodes(__new_start._M_node, |
806 | this->_M_impl._M_start._M_node); |
807 | __throw_exception_again; |
808 | } |
809 | } |
810 | else |
811 | { |
812 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
813 | iterator __old_finish = this->_M_impl._M_finish; |
814 | const difference_type __elemsafter = |
815 | difference_type(__length) - __elemsbefore; |
816 | __pos = this->_M_impl._M_finish - __elemsafter; |
817 | __try |
818 | { |
819 | if (__elemsafter > difference_type(__n)) |
820 | { |
821 | iterator __finish_n = (this->_M_impl._M_finish |
822 | - difference_type(__n)); |
823 | std::__uninitialized_move_a(__finish_n, |
824 | this->_M_impl._M_finish, |
825 | this->_M_impl._M_finish, |
826 | _M_get_Tp_allocator()); |
827 | this->_M_impl._M_finish = __new_finish; |
828 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
829 | std::copy(__first, __last, __pos); |
830 | } |
831 | else |
832 | { |
833 | _ForwardIterator __mid = __first; |
834 | std::advance(__mid, __elemsafter); |
835 | std::__uninitialized_copy_move(__mid, __last, __pos, |
836 | this->_M_impl._M_finish, |
837 | this->_M_impl._M_finish, |
838 | _M_get_Tp_allocator()); |
839 | this->_M_impl._M_finish = __new_finish; |
840 | std::copy(__first, __mid, __pos); |
841 | } |
842 | } |
843 | __catch(...) |
844 | { |
845 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
846 | __new_finish._M_node + 1); |
847 | __throw_exception_again; |
848 | } |
849 | } |
850 | } |
851 | |
852 | template<typename _Tp, typename _Alloc> |
853 | void |
854 | deque<_Tp, _Alloc>:: |
855 | _M_destroy_data_aux(iterator __first, iterator __last) |
856 | { |
857 | for (_Map_pointer __node = __first._M_node + 1; |
858 | __node < __last._M_node; ++__node) |
859 | std::_Destroy(*__node, *__node + _S_buffer_size(), |
860 | _M_get_Tp_allocator()); |
861 | |
862 | if (__first._M_node != __last._M_node) |
863 | { |
864 | std::_Destroy(__first._M_cur, __first._M_last, |
865 | _M_get_Tp_allocator()); |
866 | std::_Destroy(__last._M_first, __last._M_cur, |
867 | _M_get_Tp_allocator()); |
868 | } |
869 | else |
870 | std::_Destroy(__first._M_cur, __last._M_cur, |
871 | _M_get_Tp_allocator()); |
872 | } |
873 | |
874 | template <typename _Tp, typename _Alloc> |
875 | void |
876 | deque<_Tp, _Alloc>:: |
877 | _M_new_elements_at_front(size_type __new_elems) |
878 | { |
879 | if (this->max_size() - this->size() < __new_elems) |
880 | __throw_length_error(__N("deque::_M_new_elements_at_front" )); |
881 | |
882 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) |
883 | / _S_buffer_size()); |
884 | _M_reserve_map_at_front(__new_nodes); |
885 | size_type __i; |
886 | __try |
887 | { |
888 | for (__i = 1; __i <= __new_nodes; ++__i) |
889 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); |
890 | } |
891 | __catch(...) |
892 | { |
893 | for (size_type __j = 1; __j < __i; ++__j) |
894 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); |
895 | __throw_exception_again; |
896 | } |
897 | } |
898 | |
899 | template <typename _Tp, typename _Alloc> |
900 | void |
901 | deque<_Tp, _Alloc>:: |
902 | _M_new_elements_at_back(size_type __new_elems) |
903 | { |
904 | if (this->max_size() - this->size() < __new_elems) |
905 | __throw_length_error(__N("deque::_M_new_elements_at_back" )); |
906 | |
907 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) |
908 | / _S_buffer_size()); |
909 | _M_reserve_map_at_back(__new_nodes); |
910 | size_type __i; |
911 | __try |
912 | { |
913 | for (__i = 1; __i <= __new_nodes; ++__i) |
914 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); |
915 | } |
916 | __catch(...) |
917 | { |
918 | for (size_type __j = 1; __j < __i; ++__j) |
919 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); |
920 | __throw_exception_again; |
921 | } |
922 | } |
923 | |
924 | template <typename _Tp, typename _Alloc> |
925 | void |
926 | deque<_Tp, _Alloc>:: |
927 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
928 | { |
929 | const size_type __old_num_nodes |
930 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
931 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
932 | |
933 | _Map_pointer __new_nstart; |
934 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
935 | { |
936 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
937 | - __new_num_nodes) / 2 |
938 | + (__add_at_front ? __nodes_to_add : 0); |
939 | if (__new_nstart < this->_M_impl._M_start._M_node) |
940 | std::copy(this->_M_impl._M_start._M_node, |
941 | this->_M_impl._M_finish._M_node + 1, |
942 | __new_nstart); |
943 | else |
944 | std::copy_backward(this->_M_impl._M_start._M_node, |
945 | this->_M_impl._M_finish._M_node + 1, |
946 | __new_nstart + __old_num_nodes); |
947 | } |
948 | else |
949 | { |
950 | size_type __new_map_size = this->_M_impl._M_map_size |
951 | + std::max(this->_M_impl._M_map_size, |
952 | __nodes_to_add) + 2; |
953 | |
954 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
955 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 |
956 | + (__add_at_front ? __nodes_to_add : 0); |
957 | std::copy(this->_M_impl._M_start._M_node, |
958 | this->_M_impl._M_finish._M_node + 1, |
959 | __new_nstart); |
960 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
961 | |
962 | this->_M_impl._M_map = __new_map; |
963 | this->_M_impl._M_map_size = __new_map_size; |
964 | } |
965 | |
966 | this->_M_impl._M_start._M_set_node(__new_nstart); |
967 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); |
968 | } |
969 | |
970 | // Overload for deque::iterators, exploiting the "segmented-iterator |
971 | // optimization". |
972 | template<typename _Tp> |
973 | void |
974 | fill(const _Deque_iterator<_Tp, _Tp&, _Tp*>& __first, |
975 | const _Deque_iterator<_Tp, _Tp&, _Tp*>& __last, const _Tp& __value) |
976 | { |
977 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; |
978 | |
979 | for (typename _Self::_Map_pointer __node = __first._M_node + 1; |
980 | __node < __last._M_node; ++__node) |
981 | std::fill(*__node, *__node + _Self::_S_buffer_size(), __value); |
982 | |
983 | if (__first._M_node != __last._M_node) |
984 | { |
985 | std::fill(__first._M_cur, __first._M_last, __value); |
986 | std::fill(__last._M_first, __last._M_cur, __value); |
987 | } |
988 | else |
989 | std::fill(__first._M_cur, __last._M_cur, __value); |
990 | } |
991 | |
992 | template<typename _Tp> |
993 | _Deque_iterator<_Tp, _Tp&, _Tp*> |
994 | copy(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, |
995 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, |
996 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
997 | { |
998 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; |
999 | typedef typename _Self::difference_type difference_type; |
1000 | |
1001 | difference_type __len = __last - __first; |
1002 | while (__len > 0) |
1003 | { |
1004 | const difference_type __clen |
1005 | = std::min(__len, std::min(__first._M_last - __first._M_cur, |
1006 | __result._M_last - __result._M_cur)); |
1007 | std::copy(__first._M_cur, __first._M_cur + __clen, __result._M_cur); |
1008 | __first += __clen; |
1009 | __result += __clen; |
1010 | __len -= __clen; |
1011 | } |
1012 | return __result; |
1013 | } |
1014 | |
1015 | template<typename _Tp> |
1016 | _Deque_iterator<_Tp, _Tp&, _Tp*> |
1017 | copy_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, |
1018 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, |
1019 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
1020 | { |
1021 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; |
1022 | typedef typename _Self::difference_type difference_type; |
1023 | |
1024 | difference_type __len = __last - __first; |
1025 | while (__len > 0) |
1026 | { |
1027 | difference_type __llen = __last._M_cur - __last._M_first; |
1028 | _Tp* __lend = __last._M_cur; |
1029 | |
1030 | difference_type __rlen = __result._M_cur - __result._M_first; |
1031 | _Tp* __rend = __result._M_cur; |
1032 | |
1033 | if (!__llen) |
1034 | { |
1035 | __llen = _Self::_S_buffer_size(); |
1036 | __lend = *(__last._M_node - 1) + __llen; |
1037 | } |
1038 | if (!__rlen) |
1039 | { |
1040 | __rlen = _Self::_S_buffer_size(); |
1041 | __rend = *(__result._M_node - 1) + __rlen; |
1042 | } |
1043 | |
1044 | const difference_type __clen = std::min(__len, |
1045 | std::min(__llen, __rlen)); |
1046 | std::copy_backward(__lend - __clen, __lend, __rend); |
1047 | __last -= __clen; |
1048 | __result -= __clen; |
1049 | __len -= __clen; |
1050 | } |
1051 | return __result; |
1052 | } |
1053 | |
1054 | #if __cplusplus >= 201103L |
1055 | template<typename _Tp> |
1056 | _Deque_iterator<_Tp, _Tp&, _Tp*> |
1057 | move(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, |
1058 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, |
1059 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
1060 | { |
1061 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; |
1062 | typedef typename _Self::difference_type difference_type; |
1063 | |
1064 | difference_type __len = __last - __first; |
1065 | while (__len > 0) |
1066 | { |
1067 | const difference_type __clen |
1068 | = std::min(__len, std::min(__first._M_last - __first._M_cur, |
1069 | __result._M_last - __result._M_cur)); |
1070 | std::move(__first._M_cur, __first._M_cur + __clen, __result._M_cur); |
1071 | __first += __clen; |
1072 | __result += __clen; |
1073 | __len -= __clen; |
1074 | } |
1075 | return __result; |
1076 | } |
1077 | |
1078 | template<typename _Tp> |
1079 | _Deque_iterator<_Tp, _Tp&, _Tp*> |
1080 | move_backward(_Deque_iterator<_Tp, const _Tp&, const _Tp*> __first, |
1081 | _Deque_iterator<_Tp, const _Tp&, const _Tp*> __last, |
1082 | _Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
1083 | { |
1084 | typedef typename _Deque_iterator<_Tp, _Tp&, _Tp*>::_Self _Self; |
1085 | typedef typename _Self::difference_type difference_type; |
1086 | |
1087 | difference_type __len = __last - __first; |
1088 | while (__len > 0) |
1089 | { |
1090 | difference_type __llen = __last._M_cur - __last._M_first; |
1091 | _Tp* __lend = __last._M_cur; |
1092 | |
1093 | difference_type __rlen = __result._M_cur - __result._M_first; |
1094 | _Tp* __rend = __result._M_cur; |
1095 | |
1096 | if (!__llen) |
1097 | { |
1098 | __llen = _Self::_S_buffer_size(); |
1099 | __lend = *(__last._M_node - 1) + __llen; |
1100 | } |
1101 | if (!__rlen) |
1102 | { |
1103 | __rlen = _Self::_S_buffer_size(); |
1104 | __rend = *(__result._M_node - 1) + __rlen; |
1105 | } |
1106 | |
1107 | const difference_type __clen = std::min(__len, |
1108 | std::min(__llen, __rlen)); |
1109 | std::move_backward(__lend - __clen, __lend, __rend); |
1110 | __last -= __clen; |
1111 | __result -= __clen; |
1112 | __len -= __clen; |
1113 | } |
1114 | return __result; |
1115 | } |
1116 | #endif |
1117 | |
1118 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1119 | _GLIBCXX_END_NAMESPACE_VERSION |
1120 | } // namespace std |
1121 | |
1122 | #endif |
1123 | |