Line data Source code
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(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 9653 : deque<_Tp, _Alloc>::
165 : emplace_back(_Args&&... __args)
166 : {
167 9653 : if (this->_M_impl._M_finish._M_cur
168 9653 : != this->_M_impl._M_finish._M_last - 1)
169 : {
170 9593 : _Alloc_traits::construct(this->_M_impl,
171 : this->_M_impl._M_finish._M_cur,
172 : std::forward<_Args>(__args)...);
173 9593 : ++this->_M_impl._M_finish._M_cur;
174 : }
175 : else
176 60 : _M_push_back_aux(std::forward<_Args>(__args)...);
177 : #if __cplusplus > 201402L
178 9653 : 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(begin() + __n);
277 : }
278 : else
279 : {
280 : if (__last != end())
281 : _GLIBCXX_MOVE3(__last, end(), __first);
282 : _M_erase_at_end(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(__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, _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 60 : 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 60 : if (size() == max_size())
493 0 : __throw_length_error(
494 : __N("cannot create std::deque larger than max_size()"));
495 :
496 60 : _M_reserve_map_at_back();
497 60 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
498 : __try
499 : {
500 : #if __cplusplus >= 201103L
501 60 : _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 60 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
508 : + 1);
509 60 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
510 : }
511 0 : __catch(...)
512 : {
513 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
514 0 : __throw_exception_again;
515 : }
516 60 : }
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 0 : void deque<_Tp, _Alloc>::
561 : _M_pop_back_aux()
562 : {
563 0 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
564 0 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
565 0 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
566 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
567 : this->_M_impl._M_finish._M_cur);
568 0 : }
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 0 : void deque<_Tp, _Alloc>::
577 : _M_pop_front_aux()
578 : {
579 0 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
580 : this->_M_impl._M_start._M_cur);
581 0 : _M_deallocate_node(this->_M_impl._M_start._M_first);
582 0 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
583 0 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
584 0 : }
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 5437 : deque<_Tp, _Alloc>::
860 : _M_destroy_data_aux(iterator __first, iterator __last)
861 : {
862 5487 : for (_Map_pointer __node = __first._M_node + 1;
863 5487 : __node < __last._M_node; ++__node)
864 50 : std::_Destroy(*__node, *__node + _S_buffer_size(),
865 50 : _M_get_Tp_allocator());
866 :
867 5437 : if (__first._M_node != __last._M_node)
868 : {
869 10 : std::_Destroy(__first._M_cur, __first._M_last,
870 10 : _M_get_Tp_allocator());
871 10 : std::_Destroy(__last._M_first, __last._M_cur,
872 10 : _M_get_Tp_allocator());
873 : }
874 : else
875 5427 : std::_Destroy(__first._M_cur, __last._M_cur,
876 5427 : _M_get_Tp_allocator());
877 5437 : }
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(__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(__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 5 : deque<_Tp, _Alloc>::
932 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
933 : {
934 5 : const size_type __old_num_nodes
935 5 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
936 5 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
937 :
938 : _Map_pointer __new_nstart;
939 5 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
940 : {
941 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
942 0 : - __new_num_nodes) / 2
943 0 : + (__add_at_front ? __nodes_to_add : 0);
944 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
945 0 : std::copy(this->_M_impl._M_start._M_node,
946 0 : this->_M_impl._M_finish._M_node + 1,
947 : __new_nstart);
948 : else
949 0 : std::copy_backward(this->_M_impl._M_start._M_node,
950 0 : this->_M_impl._M_finish._M_node + 1,
951 0 : __new_nstart + __old_num_nodes);
952 : }
953 : else
954 : {
955 10 : size_type __new_map_size = this->_M_impl._M_map_size
956 5 : + std::max(this->_M_impl._M_map_size,
957 : __nodes_to_add) + 2;
958 :
959 5 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
960 10 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
961 5 : + (__add_at_front ? __nodes_to_add : 0);
962 5 : std::copy(this->_M_impl._M_start._M_node,
963 5 : this->_M_impl._M_finish._M_node + 1,
964 : __new_nstart);
965 5 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
966 :
967 5 : this->_M_impl._M_map = __new_map;
968 5 : this->_M_impl._M_map_size = __new_map_size;
969 : }
970 :
971 5 : this->_M_impl._M_start._M_set_node(__new_nstart);
972 5 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
973 5 : }
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(__len1, __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(__len1, __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
|
