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 
61namespace 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