1 | // Deque implementation (out of line) -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2021 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 | #include <bits/stl_algobase.h> |
60 | |
61 | namespace std _GLIBCXX_VISIBILITY(default) |
62 | { |
63 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
64 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
65 | |
66 | #if __cplusplus >= 201103L |
67 | template <typename _Tp, typename _Alloc> |
68 | void |
69 | deque<_Tp, _Alloc>:: |
70 | _M_default_initialize() |
71 | { |
72 | _Map_pointer __cur; |
73 | __try |
74 | { |
75 | for (__cur = this->_M_impl._M_start._M_node; |
76 | __cur < this->_M_impl._M_finish._M_node; |
77 | ++__cur) |
78 | std::__uninitialized_default_a(*__cur, *__cur + _S_buffer_size(), |
79 | _M_get_Tp_allocator()); |
80 | std::__uninitialized_default_a(this->_M_impl._M_finish._M_first, |
81 | this->_M_impl._M_finish._M_cur, |
82 | _M_get_Tp_allocator()); |
83 | } |
84 | __catch(...) |
85 | { |
86 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
87 | _M_get_Tp_allocator()); |
88 | __throw_exception_again; |
89 | } |
90 | } |
91 | #endif |
92 | |
93 | template <typename _Tp, typename _Alloc> |
94 | deque<_Tp, _Alloc>& |
95 | deque<_Tp, _Alloc>:: |
96 | operator=(const deque& __x) |
97 | { |
98 | if (&__x != this) |
99 | { |
100 | #if __cplusplus >= 201103L |
101 | if (_Alloc_traits::_S_propagate_on_copy_assign()) |
102 | { |
103 | if (!_Alloc_traits::_S_always_equal() |
104 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) |
105 | { |
106 | // Replacement allocator cannot free existing storage, |
107 | // so deallocate everything and take copy of __x's data. |
108 | _M_replace_map(__x, __x.get_allocator()); |
109 | std::__alloc_on_copy(_M_get_Tp_allocator(), |
110 | __x._M_get_Tp_allocator()); |
111 | return *this; |
112 | } |
113 | std::__alloc_on_copy(_M_get_Tp_allocator(), |
114 | __x._M_get_Tp_allocator()); |
115 | } |
116 | #endif |
117 | const size_type __len = size(); |
118 | if (__len >= __x.size()) |
119 | _M_erase_at_end(pos: std::copy(__x.begin(), __x.end(), |
120 | this->_M_impl._M_start)); |
121 | else |
122 | { |
123 | const_iterator __mid = __x.begin() + difference_type(__len); |
124 | std::copy(__x.begin(), __mid, this->_M_impl._M_start); |
125 | _M_range_insert_aux(this->_M_impl._M_finish, __mid, __x.end(), |
126 | std::random_access_iterator_tag()); |
127 | } |
128 | } |
129 | return *this; |
130 | } |
131 | |
132 | #if __cplusplus >= 201103L |
133 | template<typename _Tp, typename _Alloc> |
134 | template<typename... _Args> |
135 | #if __cplusplus > 201402L |
136 | typename deque<_Tp, _Alloc>::reference |
137 | #else |
138 | void |
139 | #endif |
140 | deque<_Tp, _Alloc>:: |
141 | emplace_front(_Args&&... __args) |
142 | { |
143 | if (this->_M_impl._M_start._M_cur != this->_M_impl._M_start._M_first) |
144 | { |
145 | _Alloc_traits::construct(this->_M_impl, |
146 | this->_M_impl._M_start._M_cur - 1, |
147 | std::forward<_Args>(__args)...); |
148 | --this->_M_impl._M_start._M_cur; |
149 | } |
150 | else |
151 | _M_push_front_aux(std::forward<_Args>(__args)...); |
152 | #if __cplusplus > 201402L |
153 | return front(); |
154 | #endif |
155 | } |
156 | |
157 | template<typename _Tp, typename _Alloc> |
158 | template<typename... _Args> |
159 | #if __cplusplus > 201402L |
160 | typename deque<_Tp, _Alloc>::reference |
161 | #else |
162 | void |
163 | #endif |
164 | deque<_Tp, _Alloc>:: |
165 | emplace_back(_Args&&... __args) |
166 | { |
167 | if (this->_M_impl._M_finish._M_cur |
168 | != this->_M_impl._M_finish._M_last - 1) |
169 | { |
170 | _Alloc_traits::construct(this->_M_impl, |
171 | this->_M_impl._M_finish._M_cur, |
172 | std::forward<_Args>(__args)...); |
173 | ++this->_M_impl._M_finish._M_cur; |
174 | } |
175 | else |
176 | _M_push_back_aux(std::forward<_Args>(__args)...); |
177 | #if __cplusplus > 201402L |
178 | return back(); |
179 | #endif |
180 | } |
181 | #endif |
182 | |
183 | #if __cplusplus >= 201103L |
184 | template<typename _Tp, typename _Alloc> |
185 | template<typename... _Args> |
186 | typename deque<_Tp, _Alloc>::iterator |
187 | deque<_Tp, _Alloc>:: |
188 | emplace(const_iterator __position, _Args&&... __args) |
189 | { |
190 | if (__position._M_cur == this->_M_impl._M_start._M_cur) |
191 | { |
192 | emplace_front(std::forward<_Args>(__args)...); |
193 | return this->_M_impl._M_start; |
194 | } |
195 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) |
196 | { |
197 | emplace_back(std::forward<_Args>(__args)...); |
198 | iterator __tmp = this->_M_impl._M_finish; |
199 | --__tmp; |
200 | return __tmp; |
201 | } |
202 | else |
203 | return _M_insert_aux(__position._M_const_cast(), |
204 | std::forward<_Args>(__args)...); |
205 | } |
206 | #endif |
207 | |
208 | template <typename _Tp, typename _Alloc> |
209 | typename deque<_Tp, _Alloc>::iterator |
210 | deque<_Tp, _Alloc>:: |
211 | #if __cplusplus >= 201103L |
212 | insert(const_iterator __position, const value_type& __x) |
213 | #else |
214 | insert(iterator __position, const value_type& __x) |
215 | #endif |
216 | { |
217 | if (__position._M_cur == this->_M_impl._M_start._M_cur) |
218 | { |
219 | push_front(__x); |
220 | return this->_M_impl._M_start; |
221 | } |
222 | else if (__position._M_cur == this->_M_impl._M_finish._M_cur) |
223 | { |
224 | push_back(__x); |
225 | iterator __tmp = this->_M_impl._M_finish; |
226 | --__tmp; |
227 | return __tmp; |
228 | } |
229 | else |
230 | return _M_insert_aux(__position._M_const_cast(), __x); |
231 | } |
232 | |
233 | template <typename _Tp, typename _Alloc> |
234 | typename deque<_Tp, _Alloc>::iterator |
235 | deque<_Tp, _Alloc>:: |
236 | _M_erase(iterator __position) |
237 | { |
238 | iterator __next = __position; |
239 | ++__next; |
240 | const difference_type __index = __position - begin(); |
241 | if (static_cast<size_type>(__index) < (size() >> 1)) |
242 | { |
243 | if (__position != begin()) |
244 | _GLIBCXX_MOVE_BACKWARD3(begin(), __position, __next); |
245 | pop_front(); |
246 | } |
247 | else |
248 | { |
249 | if (__next != end()) |
250 | _GLIBCXX_MOVE3(__next, end(), __position); |
251 | pop_back(); |
252 | } |
253 | return begin() + __index; |
254 | } |
255 | |
256 | template <typename _Tp, typename _Alloc> |
257 | typename deque<_Tp, _Alloc>::iterator |
258 | deque<_Tp, _Alloc>:: |
259 | _M_erase(iterator __first, iterator __last) |
260 | { |
261 | if (__first == __last) |
262 | return __first; |
263 | else if (__first == begin() && __last == end()) |
264 | { |
265 | clear(); |
266 | return end(); |
267 | } |
268 | else |
269 | { |
270 | const difference_type __n = __last - __first; |
271 | const difference_type __elems_before = __first - begin(); |
272 | if (static_cast<size_type>(__elems_before) <= (size() - __n) / 2) |
273 | { |
274 | if (__first != begin()) |
275 | _GLIBCXX_MOVE_BACKWARD3(begin(), __first, __last); |
276 | _M_erase_at_begin(pos: begin() + __n); |
277 | } |
278 | else |
279 | { |
280 | if (__last != end()) |
281 | _GLIBCXX_MOVE3(__last, end(), __first); |
282 | _M_erase_at_end(pos: end() - __n); |
283 | } |
284 | return begin() + __elems_before; |
285 | } |
286 | } |
287 | |
288 | template <typename _Tp, class _Alloc> |
289 | template <typename _InputIterator> |
290 | void |
291 | deque<_Tp, _Alloc>:: |
292 | _M_assign_aux(_InputIterator __first, _InputIterator __last, |
293 | std::input_iterator_tag) |
294 | { |
295 | iterator __cur = begin(); |
296 | for (; __first != __last && __cur != end(); ++__cur, (void)++__first) |
297 | *__cur = *__first; |
298 | if (__first == __last) |
299 | _M_erase_at_end(pos: __cur); |
300 | else |
301 | _M_range_insert_aux(end(), __first, __last, |
302 | std::__iterator_category(__first)); |
303 | } |
304 | |
305 | template <typename _Tp, typename _Alloc> |
306 | void |
307 | deque<_Tp, _Alloc>:: |
308 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
309 | { |
310 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
311 | { |
312 | iterator __new_start = _M_reserve_elements_at_front(__n); |
313 | __try |
314 | { |
315 | std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, |
316 | __x, _M_get_Tp_allocator()); |
317 | this->_M_impl._M_start = __new_start; |
318 | } |
319 | __catch(...) |
320 | { |
321 | _M_destroy_nodes(__new_start._M_node, |
322 | this->_M_impl._M_start._M_node); |
323 | __throw_exception_again; |
324 | } |
325 | } |
326 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
327 | { |
328 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
329 | __try |
330 | { |
331 | std::__uninitialized_fill_a(this->_M_impl._M_finish, |
332 | __new_finish, __x, |
333 | _M_get_Tp_allocator()); |
334 | this->_M_impl._M_finish = __new_finish; |
335 | } |
336 | __catch(...) |
337 | { |
338 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
339 | __new_finish._M_node + 1); |
340 | __throw_exception_again; |
341 | } |
342 | } |
343 | else |
344 | _M_insert_aux(__pos, __n, __x); |
345 | } |
346 | |
347 | #if __cplusplus >= 201103L |
348 | template <typename _Tp, typename _Alloc> |
349 | void |
350 | deque<_Tp, _Alloc>:: |
351 | _M_default_append(size_type __n) |
352 | { |
353 | if (__n) |
354 | { |
355 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
356 | __try |
357 | { |
358 | std::__uninitialized_default_a(this->_M_impl._M_finish, |
359 | __new_finish, |
360 | _M_get_Tp_allocator()); |
361 | this->_M_impl._M_finish = __new_finish; |
362 | } |
363 | __catch(...) |
364 | { |
365 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
366 | __new_finish._M_node + 1); |
367 | __throw_exception_again; |
368 | } |
369 | } |
370 | } |
371 | |
372 | template <typename _Tp, typename _Alloc> |
373 | bool |
374 | deque<_Tp, _Alloc>:: |
375 | _M_shrink_to_fit() |
376 | { |
377 | const difference_type __front_capacity |
378 | = (this->_M_impl._M_start._M_cur - this->_M_impl._M_start._M_first); |
379 | if (__front_capacity == 0) |
380 | return false; |
381 | |
382 | const difference_type __back_capacity |
383 | = (this->_M_impl._M_finish._M_last - this->_M_impl._M_finish._M_cur); |
384 | if (__front_capacity + __back_capacity < _S_buffer_size()) |
385 | return false; |
386 | |
387 | return std::__shrink_to_fit_aux<deque>::_S_do_it(*this); |
388 | } |
389 | #endif |
390 | |
391 | template <typename _Tp, typename _Alloc> |
392 | void |
393 | deque<_Tp, _Alloc>:: |
394 | _M_fill_initialize(const value_type& __value) |
395 | { |
396 | _Map_pointer __cur; |
397 | __try |
398 | { |
399 | for (__cur = this->_M_impl._M_start._M_node; |
400 | __cur < this->_M_impl._M_finish._M_node; |
401 | ++__cur) |
402 | std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), |
403 | __value, _M_get_Tp_allocator()); |
404 | std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, |
405 | this->_M_impl._M_finish._M_cur, |
406 | __value, _M_get_Tp_allocator()); |
407 | } |
408 | __catch(...) |
409 | { |
410 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
411 | _M_get_Tp_allocator()); |
412 | __throw_exception_again; |
413 | } |
414 | } |
415 | |
416 | template <typename _Tp, typename _Alloc> |
417 | template <typename _InputIterator> |
418 | void |
419 | deque<_Tp, _Alloc>:: |
420 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
421 | std::input_iterator_tag) |
422 | { |
423 | this->_M_initialize_map(0); |
424 | __try |
425 | { |
426 | for (; __first != __last; ++__first) |
427 | #if __cplusplus >= 201103L |
428 | emplace_back(*__first); |
429 | #else |
430 | push_back(*__first); |
431 | #endif |
432 | } |
433 | __catch(...) |
434 | { |
435 | clear(); |
436 | __throw_exception_again; |
437 | } |
438 | } |
439 | |
440 | template <typename _Tp, typename _Alloc> |
441 | template <typename _ForwardIterator> |
442 | void |
443 | deque<_Tp, _Alloc>:: |
444 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
445 | std::forward_iterator_tag) |
446 | { |
447 | const size_type __n = std::distance(__first, __last); |
448 | this->_M_initialize_map(_S_check_init_len(__n, a: _M_get_Tp_allocator())); |
449 | |
450 | _Map_pointer __cur_node; |
451 | __try |
452 | { |
453 | for (__cur_node = this->_M_impl._M_start._M_node; |
454 | __cur_node < this->_M_impl._M_finish._M_node; |
455 | ++__cur_node) |
456 | { |
457 | if (__n < _S_buffer_size()) |
458 | __builtin_unreachable(); // See PR 100516 |
459 | |
460 | _ForwardIterator __mid = __first; |
461 | std::advance(__mid, _S_buffer_size()); |
462 | std::__uninitialized_copy_a(__first, __mid, *__cur_node, |
463 | _M_get_Tp_allocator()); |
464 | __first = __mid; |
465 | } |
466 | std::__uninitialized_copy_a(__first, __last, |
467 | this->_M_impl._M_finish._M_first, |
468 | _M_get_Tp_allocator()); |
469 | } |
470 | __catch(...) |
471 | { |
472 | std::_Destroy(this->_M_impl._M_start, |
473 | iterator(*__cur_node, __cur_node), |
474 | _M_get_Tp_allocator()); |
475 | __throw_exception_again; |
476 | } |
477 | } |
478 | |
479 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
480 | template<typename _Tp, typename _Alloc> |
481 | #if __cplusplus >= 201103L |
482 | template<typename... _Args> |
483 | void |
484 | deque<_Tp, _Alloc>:: |
485 | _M_push_back_aux(_Args&&... __args) |
486 | #else |
487 | void |
488 | deque<_Tp, _Alloc>:: |
489 | _M_push_back_aux(const value_type& __t) |
490 | #endif |
491 | { |
492 | if (size() == max_size()) |
493 | __throw_length_error( |
494 | __N("cannot create std::deque larger than max_size()" )); |
495 | |
496 | _M_reserve_map_at_back(); |
497 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); |
498 | __try |
499 | { |
500 | #if __cplusplus >= 201103L |
501 | _Alloc_traits::construct(this->_M_impl, |
502 | this->_M_impl._M_finish._M_cur, |
503 | std::forward<_Args>(__args)...); |
504 | #else |
505 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t); |
506 | #endif |
507 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
508 | + 1); |
509 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; |
510 | } |
511 | __catch(...) |
512 | { |
513 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); |
514 | __throw_exception_again; |
515 | } |
516 | } |
517 | |
518 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
519 | template<typename _Tp, typename _Alloc> |
520 | #if __cplusplus >= 201103L |
521 | template<typename... _Args> |
522 | void |
523 | deque<_Tp, _Alloc>:: |
524 | _M_push_front_aux(_Args&&... __args) |
525 | #else |
526 | void |
527 | deque<_Tp, _Alloc>:: |
528 | _M_push_front_aux(const value_type& __t) |
529 | #endif |
530 | { |
531 | if (size() == max_size()) |
532 | __throw_length_error( |
533 | __N("cannot create std::deque larger than max_size()" )); |
534 | |
535 | _M_reserve_map_at_front(); |
536 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); |
537 | __try |
538 | { |
539 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node |
540 | - 1); |
541 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; |
542 | #if __cplusplus >= 201103L |
543 | _Alloc_traits::construct(this->_M_impl, |
544 | this->_M_impl._M_start._M_cur, |
545 | std::forward<_Args>(__args)...); |
546 | #else |
547 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t); |
548 | #endif |
549 | } |
550 | __catch(...) |
551 | { |
552 | ++this->_M_impl._M_start; |
553 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); |
554 | __throw_exception_again; |
555 | } |
556 | } |
557 | |
558 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
559 | template <typename _Tp, typename _Alloc> |
560 | void deque<_Tp, _Alloc>:: |
561 | _M_pop_back_aux() |
562 | { |
563 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
564 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); |
565 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; |
566 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
567 | this->_M_impl._M_finish._M_cur); |
568 | } |
569 | |
570 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
571 | // Note that if the deque has at least one element (a precondition for this |
572 | // member function), and if |
573 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, |
574 | // then the deque must have at least two nodes. |
575 | template <typename _Tp, typename _Alloc> |
576 | void deque<_Tp, _Alloc>:: |
577 | _M_pop_front_aux() |
578 | { |
579 | _Alloc_traits::destroy(_M_get_Tp_allocator(), |
580 | this->_M_impl._M_start._M_cur); |
581 | _M_deallocate_node(this->_M_impl._M_start._M_first); |
582 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); |
583 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; |
584 | } |
585 | |
586 | template <typename _Tp, typename _Alloc> |
587 | template <typename _InputIterator> |
588 | void |
589 | deque<_Tp, _Alloc>:: |
590 | _M_range_insert_aux(iterator __pos, |
591 | _InputIterator __first, _InputIterator __last, |
592 | std::input_iterator_tag) |
593 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
594 | |
595 | template <typename _Tp, typename _Alloc> |
596 | template <typename _ForwardIterator> |
597 | void |
598 | deque<_Tp, _Alloc>:: |
599 | _M_range_insert_aux(iterator __pos, |
600 | _ForwardIterator __first, _ForwardIterator __last, |
601 | std::forward_iterator_tag) |
602 | { |
603 | const size_type __n = std::distance(__first, __last); |
604 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
605 | { |
606 | iterator __new_start = _M_reserve_elements_at_front(__n); |
607 | __try |
608 | { |
609 | std::__uninitialized_copy_a(__first, __last, __new_start, |
610 | _M_get_Tp_allocator()); |
611 | this->_M_impl._M_start = __new_start; |
612 | } |
613 | __catch(...) |
614 | { |
615 | _M_destroy_nodes(__new_start._M_node, |
616 | this->_M_impl._M_start._M_node); |
617 | __throw_exception_again; |
618 | } |
619 | } |
620 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
621 | { |
622 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
623 | __try |
624 | { |
625 | std::__uninitialized_copy_a(__first, __last, |
626 | this->_M_impl._M_finish, |
627 | _M_get_Tp_allocator()); |
628 | this->_M_impl._M_finish = __new_finish; |
629 | } |
630 | __catch(...) |
631 | { |
632 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
633 | __new_finish._M_node + 1); |
634 | __throw_exception_again; |
635 | } |
636 | } |
637 | else |
638 | _M_insert_aux(__pos, __first, __last, __n); |
639 | } |
640 | |
641 | template<typename _Tp, typename _Alloc> |
642 | #if __cplusplus >= 201103L |
643 | template<typename... _Args> |
644 | typename deque<_Tp, _Alloc>::iterator |
645 | deque<_Tp, _Alloc>:: |
646 | _M_insert_aux(iterator __pos, _Args&&... __args) |
647 | { |
648 | value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy |
649 | #else |
650 | typename deque<_Tp, _Alloc>::iterator |
651 | deque<_Tp, _Alloc>:: |
652 | _M_insert_aux(iterator __pos, const value_type& __x) |
653 | { |
654 | value_type __x_copy = __x; // XXX copy |
655 | #endif |
656 | difference_type __index = __pos - this->_M_impl._M_start; |
657 | if (static_cast<size_type>(__index) < size() / 2) |
658 | { |
659 | push_front(_GLIBCXX_MOVE(front())); |
660 | iterator __front1 = this->_M_impl._M_start; |
661 | ++__front1; |
662 | iterator __front2 = __front1; |
663 | ++__front2; |
664 | __pos = this->_M_impl._M_start + __index; |
665 | iterator __pos1 = __pos; |
666 | ++__pos1; |
667 | _GLIBCXX_MOVE3(__front2, __pos1, __front1); |
668 | } |
669 | else |
670 | { |
671 | push_back(_GLIBCXX_MOVE(back())); |
672 | iterator __back1 = this->_M_impl._M_finish; |
673 | --__back1; |
674 | iterator __back2 = __back1; |
675 | --__back2; |
676 | __pos = this->_M_impl._M_start + __index; |
677 | _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1); |
678 | } |
679 | *__pos = _GLIBCXX_MOVE(__x_copy); |
680 | return __pos; |
681 | } |
682 | |
683 | template <typename _Tp, typename _Alloc> |
684 | void |
685 | deque<_Tp, _Alloc>:: |
686 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
687 | { |
688 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
689 | const size_type __length = this->size(); |
690 | value_type __x_copy = __x; |
691 | if (__elems_before < difference_type(__length / 2)) |
692 | { |
693 | iterator __new_start = _M_reserve_elements_at_front(__n); |
694 | iterator __old_start = this->_M_impl._M_start; |
695 | __pos = this->_M_impl._M_start + __elems_before; |
696 | __try |
697 | { |
698 | if (__elems_before >= difference_type(__n)) |
699 | { |
700 | iterator __start_n = (this->_M_impl._M_start |
701 | + difference_type(__n)); |
702 | std::__uninitialized_move_a(this->_M_impl._M_start, |
703 | __start_n, __new_start, |
704 | _M_get_Tp_allocator()); |
705 | this->_M_impl._M_start = __new_start; |
706 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
707 | std::fill(__pos - difference_type(__n), __pos, __x_copy); |
708 | } |
709 | else |
710 | { |
711 | std::__uninitialized_move_fill(this->_M_impl._M_start, |
712 | __pos, __new_start, |
713 | this->_M_impl._M_start, |
714 | __x_copy, |
715 | _M_get_Tp_allocator()); |
716 | this->_M_impl._M_start = __new_start; |
717 | std::fill(__old_start, __pos, __x_copy); |
718 | } |
719 | } |
720 | __catch(...) |
721 | { |
722 | _M_destroy_nodes(__new_start._M_node, |
723 | this->_M_impl._M_start._M_node); |
724 | __throw_exception_again; |
725 | } |
726 | } |
727 | else |
728 | { |
729 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
730 | iterator __old_finish = this->_M_impl._M_finish; |
731 | const difference_type __elems_after = |
732 | difference_type(__length) - __elems_before; |
733 | __pos = this->_M_impl._M_finish - __elems_after; |
734 | __try |
735 | { |
736 | if (__elems_after > difference_type(__n)) |
737 | { |
738 | iterator __finish_n = (this->_M_impl._M_finish |
739 | - difference_type(__n)); |
740 | std::__uninitialized_move_a(__finish_n, |
741 | this->_M_impl._M_finish, |
742 | this->_M_impl._M_finish, |
743 | _M_get_Tp_allocator()); |
744 | this->_M_impl._M_finish = __new_finish; |
745 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
746 | std::fill(__pos, __pos + difference_type(__n), __x_copy); |
747 | } |
748 | else |
749 | { |
750 | std::__uninitialized_fill_move(this->_M_impl._M_finish, |
751 | __pos + difference_type(__n), |
752 | __x_copy, __pos, |
753 | this->_M_impl._M_finish, |
754 | _M_get_Tp_allocator()); |
755 | this->_M_impl._M_finish = __new_finish; |
756 | std::fill(__pos, __old_finish, __x_copy); |
757 | } |
758 | } |
759 | __catch(...) |
760 | { |
761 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
762 | __new_finish._M_node + 1); |
763 | __throw_exception_again; |
764 | } |
765 | } |
766 | } |
767 | |
768 | template <typename _Tp, typename _Alloc> |
769 | template <typename _ForwardIterator> |
770 | void |
771 | deque<_Tp, _Alloc>:: |
772 | _M_insert_aux(iterator __pos, |
773 | _ForwardIterator __first, _ForwardIterator __last, |
774 | size_type __n) |
775 | { |
776 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
777 | const size_type __length = size(); |
778 | if (static_cast<size_type>(__elemsbefore) < __length / 2) |
779 | { |
780 | iterator __new_start = _M_reserve_elements_at_front(__n); |
781 | iterator __old_start = this->_M_impl._M_start; |
782 | __pos = this->_M_impl._M_start + __elemsbefore; |
783 | __try |
784 | { |
785 | if (__elemsbefore >= difference_type(__n)) |
786 | { |
787 | iterator __start_n = (this->_M_impl._M_start |
788 | + difference_type(__n)); |
789 | std::__uninitialized_move_a(this->_M_impl._M_start, |
790 | __start_n, __new_start, |
791 | _M_get_Tp_allocator()); |
792 | this->_M_impl._M_start = __new_start; |
793 | _GLIBCXX_MOVE3(__start_n, __pos, __old_start); |
794 | std::copy(__first, __last, __pos - difference_type(__n)); |
795 | } |
796 | else |
797 | { |
798 | _ForwardIterator __mid = __first; |
799 | std::advance(__mid, difference_type(__n) - __elemsbefore); |
800 | std::__uninitialized_move_copy(this->_M_impl._M_start, |
801 | __pos, __first, __mid, |
802 | __new_start, |
803 | _M_get_Tp_allocator()); |
804 | this->_M_impl._M_start = __new_start; |
805 | std::copy(__mid, __last, __old_start); |
806 | } |
807 | } |
808 | __catch(...) |
809 | { |
810 | _M_destroy_nodes(__new_start._M_node, |
811 | this->_M_impl._M_start._M_node); |
812 | __throw_exception_again; |
813 | } |
814 | } |
815 | else |
816 | { |
817 | iterator __new_finish = _M_reserve_elements_at_back(__n); |
818 | iterator __old_finish = this->_M_impl._M_finish; |
819 | const difference_type __elemsafter = |
820 | difference_type(__length) - __elemsbefore; |
821 | __pos = this->_M_impl._M_finish - __elemsafter; |
822 | __try |
823 | { |
824 | if (__elemsafter > difference_type(__n)) |
825 | { |
826 | iterator __finish_n = (this->_M_impl._M_finish |
827 | - difference_type(__n)); |
828 | std::__uninitialized_move_a(__finish_n, |
829 | this->_M_impl._M_finish, |
830 | this->_M_impl._M_finish, |
831 | _M_get_Tp_allocator()); |
832 | this->_M_impl._M_finish = __new_finish; |
833 | _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish); |
834 | std::copy(__first, __last, __pos); |
835 | } |
836 | else |
837 | { |
838 | _ForwardIterator __mid = __first; |
839 | std::advance(__mid, __elemsafter); |
840 | std::__uninitialized_copy_move(__mid, __last, __pos, |
841 | this->_M_impl._M_finish, |
842 | this->_M_impl._M_finish, |
843 | _M_get_Tp_allocator()); |
844 | this->_M_impl._M_finish = __new_finish; |
845 | std::copy(__first, __mid, __pos); |
846 | } |
847 | } |
848 | __catch(...) |
849 | { |
850 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
851 | __new_finish._M_node + 1); |
852 | __throw_exception_again; |
853 | } |
854 | } |
855 | } |
856 | |
857 | template<typename _Tp, typename _Alloc> |
858 | void |
859 | deque<_Tp, _Alloc>:: |
860 | _M_destroy_data_aux(iterator __first, iterator __last) |
861 | { |
862 | for (_Map_pointer __node = __first._M_node + 1; |
863 | __node < __last._M_node; ++__node) |
864 | std::_Destroy(*__node, *__node + _S_buffer_size(), |
865 | _M_get_Tp_allocator()); |
866 | |
867 | if (__first._M_node != __last._M_node) |
868 | { |
869 | std::_Destroy(__first._M_cur, __first._M_last, |
870 | _M_get_Tp_allocator()); |
871 | std::_Destroy(__last._M_first, __last._M_cur, |
872 | _M_get_Tp_allocator()); |
873 | } |
874 | else |
875 | std::_Destroy(__first._M_cur, __last._M_cur, |
876 | _M_get_Tp_allocator()); |
877 | } |
878 | |
879 | template <typename _Tp, typename _Alloc> |
880 | void |
881 | deque<_Tp, _Alloc>:: |
882 | _M_new_elements_at_front(size_type __new_elems) |
883 | { |
884 | if (this->max_size() - this->size() < __new_elems) |
885 | __throw_length_error(__N("deque::_M_new_elements_at_front" )); |
886 | |
887 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) |
888 | / _S_buffer_size()); |
889 | _M_reserve_map_at_front(nodes_to_add: __new_nodes); |
890 | size_type __i; |
891 | __try |
892 | { |
893 | for (__i = 1; __i <= __new_nodes; ++__i) |
894 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); |
895 | } |
896 | __catch(...) |
897 | { |
898 | for (size_type __j = 1; __j < __i; ++__j) |
899 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); |
900 | __throw_exception_again; |
901 | } |
902 | } |
903 | |
904 | template <typename _Tp, typename _Alloc> |
905 | void |
906 | deque<_Tp, _Alloc>:: |
907 | _M_new_elements_at_back(size_type __new_elems) |
908 | { |
909 | if (this->max_size() - this->size() < __new_elems) |
910 | __throw_length_error(__N("deque::_M_new_elements_at_back" )); |
911 | |
912 | const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1) |
913 | / _S_buffer_size()); |
914 | _M_reserve_map_at_back(nodes_to_add: __new_nodes); |
915 | size_type __i; |
916 | __try |
917 | { |
918 | for (__i = 1; __i <= __new_nodes; ++__i) |
919 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); |
920 | } |
921 | __catch(...) |
922 | { |
923 | for (size_type __j = 1; __j < __i; ++__j) |
924 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); |
925 | __throw_exception_again; |
926 | } |
927 | } |
928 | |
929 | template <typename _Tp, typename _Alloc> |
930 | void |
931 | deque<_Tp, _Alloc>:: |
932 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
933 | { |
934 | const size_type __old_num_nodes |
935 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
936 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
937 | |
938 | _Map_pointer __new_nstart; |
939 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
940 | { |
941 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
942 | - __new_num_nodes) / 2 |
943 | + (__add_at_front ? __nodes_to_add : 0); |
944 | if (__new_nstart < this->_M_impl._M_start._M_node) |
945 | std::copy(this->_M_impl._M_start._M_node, |
946 | this->_M_impl._M_finish._M_node + 1, |
947 | __new_nstart); |
948 | else |
949 | std::copy_backward(this->_M_impl._M_start._M_node, |
950 | this->_M_impl._M_finish._M_node + 1, |
951 | __new_nstart + __old_num_nodes); |
952 | } |
953 | else |
954 | { |
955 | size_type __new_map_size = this->_M_impl._M_map_size |
956 | + std::max(this->_M_impl._M_map_size, |
957 | __nodes_to_add) + 2; |
958 | |
959 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
960 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 |
961 | + (__add_at_front ? __nodes_to_add : 0); |
962 | std::copy(this->_M_impl._M_start._M_node, |
963 | this->_M_impl._M_finish._M_node + 1, |
964 | __new_nstart); |
965 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
966 | |
967 | this->_M_impl._M_map = __new_map; |
968 | this->_M_impl._M_map_size = __new_map_size; |
969 | } |
970 | |
971 | this->_M_impl._M_start._M_set_node(__new_nstart); |
972 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); |
973 | } |
974 | |
975 | _GLIBCXX_END_NAMESPACE_CONTAINER |
976 | |
977 | // Overload for deque::iterators, exploiting the "segmented-iterator |
978 | // optimization". |
979 | template<typename _Tp, typename _VTp> |
980 | void |
981 | __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first, |
982 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last, |
983 | const _VTp& __value) |
984 | { |
985 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
986 | if (__first._M_node != __last._M_node) |
987 | { |
988 | std::__fill_a1(__first._M_cur, __first._M_last, __value); |
989 | |
990 | for (typename _Iter::_Map_pointer __node = __first._M_node + 1; |
991 | __node < __last._M_node; ++__node) |
992 | std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value); |
993 | |
994 | std::__fill_a1(__last._M_first, __last._M_cur, __value); |
995 | } |
996 | else |
997 | std::__fill_a1(__first._M_cur, __last._M_cur, __value); |
998 | } |
999 | |
1000 | template<bool _IsMove, |
1001 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> |
1002 | _OI |
1003 | __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, |
1004 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, |
1005 | _OI __result) |
1006 | { |
1007 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1008 | if (__first._M_node != __last._M_node) |
1009 | { |
1010 | __result |
1011 | = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last, |
1012 | __result); |
1013 | |
1014 | for (typename _Iter::_Map_pointer __node = __first._M_node + 1; |
1015 | __node != __last._M_node; ++__node) |
1016 | __result |
1017 | = std::__copy_move_a1<_IsMove>(*__node, |
1018 | *__node + _Iter::_S_buffer_size(), |
1019 | __result); |
1020 | |
1021 | return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur, |
1022 | __result); |
1023 | } |
1024 | |
1025 | return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur, |
1026 | __result); |
1027 | } |
1028 | |
1029 | template<bool _IsMove, |
1030 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> |
1031 | _OI |
1032 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, |
1033 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, |
1034 | _OI __result) |
1035 | { return __copy_move_dit<_IsMove>(__first, __last, __result); } |
1036 | |
1037 | template<bool _IsMove, |
1038 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> |
1039 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> |
1040 | __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, |
1041 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, |
1042 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) |
1043 | { return __copy_move_dit<_IsMove>(__first, __last, __result); } |
1044 | |
1045 | template<bool _IsMove, typename _II, typename _Tp> |
1046 | typename __gnu_cxx::__enable_if< |
1047 | __is_random_access_iter<_II>::__value, |
1048 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type |
1049 | __copy_move_a1(_II __first, _II __last, |
1050 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
1051 | { |
1052 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
1053 | typedef typename _Iter::difference_type difference_type; |
1054 | |
1055 | difference_type __len = __last - __first; |
1056 | while (__len > 0) |
1057 | { |
1058 | const difference_type __clen |
1059 | = std::min(__len, __result._M_last - __result._M_cur); |
1060 | std::__copy_move_a1<_IsMove>(__first, __first + __clen, |
1061 | __result._M_cur); |
1062 | |
1063 | __first += __clen; |
1064 | __result += __clen; |
1065 | __len -= __clen; |
1066 | } |
1067 | |
1068 | return __result; |
1069 | } |
1070 | |
1071 | template<bool _IsMove, typename _CharT> |
1072 | typename __gnu_cxx::__enable_if< |
1073 | __is_char<_CharT>::__value, |
1074 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type |
1075 | __copy_move_a2( |
1076 | istreambuf_iterator<_CharT, char_traits<_CharT> > __first, |
1077 | istreambuf_iterator<_CharT, char_traits<_CharT> > __last, |
1078 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result) |
1079 | { |
1080 | if (__first == __last) |
1081 | return __result; |
1082 | |
1083 | for (;;) |
1084 | { |
1085 | const std::ptrdiff_t __len = __result._M_last - __result._M_cur; |
1086 | const std::ptrdiff_t __nb |
1087 | = std::__copy_n_a(__first, __len, __result._M_cur, false) |
1088 | - __result._M_cur; |
1089 | __result += __nb; |
1090 | |
1091 | if (__nb != __len) |
1092 | break; |
1093 | } |
1094 | |
1095 | return __result; |
1096 | } |
1097 | |
1098 | template<typename _CharT, typename _Size> |
1099 | typename __gnu_cxx::__enable_if< |
1100 | __is_char<_CharT>::__value, |
1101 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type |
1102 | __copy_n_a( |
1103 | istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size, |
1104 | _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result, |
1105 | bool __strict) |
1106 | { |
1107 | if (__size == 0) |
1108 | return __result; |
1109 | |
1110 | do |
1111 | { |
1112 | const _Size __len |
1113 | = std::min<_Size>(__result._M_last - __result._M_cur, __size); |
1114 | std::__copy_n_a(__it, __len, __result._M_cur, __strict); |
1115 | __result += __len; |
1116 | __size -= __len; |
1117 | } |
1118 | while (__size != 0); |
1119 | return __result; |
1120 | } |
1121 | |
1122 | template<bool _IsMove, |
1123 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> |
1124 | _OI |
1125 | __copy_move_backward_dit( |
1126 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, |
1127 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, |
1128 | _OI __result) |
1129 | { |
1130 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1131 | if (__first._M_node != __last._M_node) |
1132 | { |
1133 | __result = std::__copy_move_backward_a1<_IsMove>( |
1134 | __last._M_first, __last._M_cur, __result); |
1135 | |
1136 | for (typename _Iter::_Map_pointer __node = __last._M_node - 1; |
1137 | __node != __first._M_node; --__node) |
1138 | __result = std::__copy_move_backward_a1<_IsMove>( |
1139 | *__node, *__node + _Iter::_S_buffer_size(), __result); |
1140 | |
1141 | return std::__copy_move_backward_a1<_IsMove>( |
1142 | __first._M_cur, __first._M_last, __result); |
1143 | } |
1144 | |
1145 | return std::__copy_move_backward_a1<_IsMove>( |
1146 | __first._M_cur, __last._M_cur, __result); |
1147 | } |
1148 | |
1149 | template<bool _IsMove, |
1150 | typename _Tp, typename _Ref, typename _Ptr, typename _OI> |
1151 | _OI |
1152 | __copy_move_backward_a1( |
1153 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first, |
1154 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last, |
1155 | _OI __result) |
1156 | { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } |
1157 | |
1158 | template<bool _IsMove, |
1159 | typename _ITp, typename _IRef, typename _IPtr, typename _OTp> |
1160 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> |
1161 | __copy_move_backward_a1( |
1162 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first, |
1163 | _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last, |
1164 | _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result) |
1165 | { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); } |
1166 | |
1167 | template<bool _IsMove, typename _II, typename _Tp> |
1168 | typename __gnu_cxx::__enable_if< |
1169 | __is_random_access_iter<_II>::__value, |
1170 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type |
1171 | __copy_move_backward_a1(_II __first, _II __last, |
1172 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result) |
1173 | { |
1174 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter; |
1175 | typedef typename _Iter::difference_type difference_type; |
1176 | |
1177 | difference_type __len = __last - __first; |
1178 | while (__len > 0) |
1179 | { |
1180 | difference_type __rlen = __result._M_cur - __result._M_first; |
1181 | _Tp* __rend = __result._M_cur; |
1182 | if (!__rlen) |
1183 | { |
1184 | __rlen = _Iter::_S_buffer_size(); |
1185 | __rend = *(__result._M_node - 1) + __rlen; |
1186 | } |
1187 | |
1188 | const difference_type __clen = std::min(__len, __rlen); |
1189 | std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend); |
1190 | |
1191 | __last -= __clen; |
1192 | __result -= __clen; |
1193 | __len -= __clen; |
1194 | } |
1195 | |
1196 | return __result; |
1197 | } |
1198 | |
1199 | template<typename _Tp, typename _Ref, typename _Ptr, typename _II> |
1200 | bool |
1201 | __equal_dit( |
1202 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1, |
1203 | const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1, |
1204 | _II __first2) |
1205 | { |
1206 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1207 | if (__first1._M_node != __last1._M_node) |
1208 | { |
1209 | if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2)) |
1210 | return false; |
1211 | |
1212 | __first2 += __first1._M_last - __first1._M_cur; |
1213 | for (typename _Iter::_Map_pointer __node = __first1._M_node + 1; |
1214 | __node != __last1._M_node; |
1215 | __first2 += _Iter::_S_buffer_size(), ++__node) |
1216 | if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(), |
1217 | __first2)) |
1218 | return false; |
1219 | |
1220 | return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2); |
1221 | } |
1222 | |
1223 | return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2); |
1224 | } |
1225 | |
1226 | template<typename _Tp, typename _Ref, typename _Ptr, typename _II> |
1227 | typename __gnu_cxx::__enable_if< |
1228 | __is_random_access_iter<_II>::__value, bool>::__type |
1229 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1, |
1230 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1, |
1231 | _II __first2) |
1232 | { return std::__equal_dit(__first1, __last1, __first2); } |
1233 | |
1234 | template<typename _Tp1, typename _Ref1, typename _Ptr1, |
1235 | typename _Tp2, typename _Ref2, typename _Ptr2> |
1236 | bool |
1237 | __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, |
1238 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, |
1239 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2) |
1240 | { return std::__equal_dit(__first1, __last1, __first2); } |
1241 | |
1242 | template<typename _II, typename _Tp, typename _Ref, typename _Ptr> |
1243 | typename __gnu_cxx::__enable_if< |
1244 | __is_random_access_iter<_II>::__value, bool>::__type |
1245 | __equal_aux1(_II __first1, _II __last1, |
1246 | _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2) |
1247 | { |
1248 | typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter; |
1249 | typedef typename _Iter::difference_type difference_type; |
1250 | |
1251 | difference_type __len = __last1 - __first1; |
1252 | while (__len > 0) |
1253 | { |
1254 | const difference_type __clen |
1255 | = std::min(__len, __first2._M_last - __first2._M_cur); |
1256 | if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur)) |
1257 | return false; |
1258 | |
1259 | __first1 += __clen; |
1260 | __len -= __clen; |
1261 | __first2 += __clen; |
1262 | } |
1263 | |
1264 | return true; |
1265 | } |
1266 | |
1267 | template<typename _Tp1, typename _Ref, typename _Ptr, typename _Tp2> |
1268 | int |
1269 | __lex_cmp_dit( |
1270 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __first1, |
1271 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref, _Ptr> __last1, |
1272 | const _Tp2* __first2, const _Tp2* __last2) |
1273 | { |
1274 | const bool __simple = |
1275 | (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value |
1276 | && __is_pointer<_Ptr>::__value |
1277 | #if __cplusplus > 201703L && __cpp_lib_concepts |
1278 | // For C++20 iterator_traits<volatile T*>::value_type is non-volatile |
1279 | // so __is_byte<T> could be true, but we can't use memcmp with |
1280 | // volatile data. |
1281 | && !is_volatile_v<_Tp1> |
1282 | && !is_volatile_v<_Tp2> |
1283 | #endif |
1284 | ); |
1285 | typedef std::__lexicographical_compare<__simple> _Lc; |
1286 | |
1287 | while (__first1._M_node != __last1._M_node) |
1288 | { |
1289 | const ptrdiff_t __len1 = __first1._M_last - __first1._M_cur; |
1290 | const ptrdiff_t __len2 = __last2 - __first2; |
1291 | const ptrdiff_t __len = std::min(a: __len1, b: __len2); |
1292 | // if __len1 > __len2 this will return a positive value: |
1293 | if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_last, |
1294 | __first2, __first2 + __len)) |
1295 | return __ret; |
1296 | |
1297 | __first1 += __len; |
1298 | __first2 += __len; |
1299 | } |
1300 | return _Lc::__3way(__first1._M_cur, __last1._M_cur, |
1301 | __first2, __last2); |
1302 | } |
1303 | |
1304 | template<typename _Tp1, typename _Ref1, typename _Ptr1, |
1305 | typename _Tp2> |
1306 | inline bool |
1307 | __lexicographical_compare_aux1( |
1308 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, |
1309 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, |
1310 | _Tp2* __first2, _Tp2* __last2) |
1311 | { return std::__lex_cmp_dit(__first1, __last1, __first2, __last2) < 0; } |
1312 | |
1313 | template<typename _Tp1, |
1314 | typename _Tp2, typename _Ref2, typename _Ptr2> |
1315 | inline bool |
1316 | __lexicographical_compare_aux1(_Tp1* __first1, _Tp1* __last1, |
1317 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, |
1318 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) |
1319 | { return std::__lex_cmp_dit(__first2, __last2, __first1, __last1) > 0; } |
1320 | |
1321 | template<typename _Tp1, typename _Ref1, typename _Ptr1, |
1322 | typename _Tp2, typename _Ref2, typename _Ptr2> |
1323 | inline bool |
1324 | __lexicographical_compare_aux1( |
1325 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1, |
1326 | _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1, |
1327 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2, |
1328 | _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __last2) |
1329 | { |
1330 | const bool __simple = |
1331 | (__is_memcmp_ordered_with<_Tp1, _Tp2>::__value |
1332 | && __is_pointer<_Ptr1>::__value |
1333 | && __is_pointer<_Ptr2>::__value |
1334 | #if __cplusplus > 201703L && __cpp_lib_concepts |
1335 | // For C++20 iterator_traits<volatile T*>::value_type is non-volatile |
1336 | // so __is_byte<T> could be true, but we can't use memcmp with |
1337 | // volatile data. |
1338 | && !is_volatile_v<_Tp1> |
1339 | && !is_volatile_v<_Tp2> |
1340 | #endif |
1341 | ); |
1342 | typedef std::__lexicographical_compare<__simple> _Lc; |
1343 | |
1344 | while (__first1 != __last1) |
1345 | { |
1346 | const ptrdiff_t __len2 = __first2._M_node == __last2._M_node |
1347 | ? __last2._M_cur - __first2._M_cur |
1348 | : __first2._M_last - __first2._M_cur; |
1349 | if (__len2 == 0) |
1350 | return false; |
1351 | const ptrdiff_t __len1 = __first1._M_node == __last1._M_node |
1352 | ? __last1._M_cur - __first1._M_cur |
1353 | : __first1._M_last - __first1._M_cur; |
1354 | const ptrdiff_t __len = std::min(a: __len1, b: __len2); |
1355 | if (int __ret = _Lc::__3way(__first1._M_cur, __first1._M_cur + __len, |
1356 | __first2._M_cur, __first2._M_cur + __len)) |
1357 | return __ret < 0; |
1358 | |
1359 | __first1 += __len; |
1360 | __first2 += __len; |
1361 | } |
1362 | |
1363 | return __last2 != __first2; |
1364 | } |
1365 | |
1366 | _GLIBCXX_END_NAMESPACE_VERSION |
1367 | } // namespace std |
1368 | |
1369 | #endif |
1370 | |