Line data Source code
1 : // Deque implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2020 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 617822 : deque<_Tp, _Alloc>::
165 : emplace_back(_Args&&... __args)
166 : {
167 617822 : if (this->_M_impl._M_finish._M_cur
168 617822 : != this->_M_impl._M_finish._M_last - 1)
169 : {
170 617589 : _Alloc_traits::construct(this->_M_impl,
171 : this->_M_impl._M_finish._M_cur,
172 : std::forward<_Args>(__args)...);
173 617589 : ++this->_M_impl._M_finish._M_cur;
174 : }
175 : else
176 233 : _M_push_back_aux(std::forward<_Args>(__args)...);
177 : #if __cplusplus > 201402L
178 : return back();
179 : #endif
180 617822 : }
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 : _ForwardIterator __mid = __first;
458 : std::advance(__mid, _S_buffer_size());
459 : std::__uninitialized_copy_a(__first, __mid, *__cur_node,
460 : _M_get_Tp_allocator());
461 : __first = __mid;
462 : }
463 : std::__uninitialized_copy_a(__first, __last,
464 : this->_M_impl._M_finish._M_first,
465 : _M_get_Tp_allocator());
466 : }
467 : __catch(...)
468 : {
469 : std::_Destroy(this->_M_impl._M_start,
470 : iterator(*__cur_node, __cur_node),
471 : _M_get_Tp_allocator());
472 : __throw_exception_again;
473 : }
474 : }
475 :
476 : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1.
477 : template<typename _Tp, typename _Alloc>
478 : #if __cplusplus >= 201103L
479 : template<typename... _Args>
480 : void
481 233 : deque<_Tp, _Alloc>::
482 : _M_push_back_aux(_Args&&... __args)
483 : #else
484 : void
485 : deque<_Tp, _Alloc>::
486 : _M_push_back_aux(const value_type& __t)
487 : #endif
488 : {
489 233 : if (size() == max_size())
490 0 : __throw_length_error(
491 : __N("cannot create std::deque larger than max_size()"));
492 :
493 233 : _M_reserve_map_at_back();
494 233 : *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
495 : __try
496 : {
497 : #if __cplusplus >= 201103L
498 233 : _Alloc_traits::construct(this->_M_impl,
499 : this->_M_impl._M_finish._M_cur,
500 : std::forward<_Args>(__args)...);
501 : #else
502 : this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t);
503 : #endif
504 233 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
505 : + 1);
506 233 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
507 : }
508 0 : __catch(...)
509 : {
510 0 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
511 0 : __throw_exception_again;
512 : }
513 233 : }
514 :
515 : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first.
516 : template<typename _Tp, typename _Alloc>
517 : #if __cplusplus >= 201103L
518 : template<typename... _Args>
519 : void
520 : deque<_Tp, _Alloc>::
521 : _M_push_front_aux(_Args&&... __args)
522 : #else
523 : void
524 : deque<_Tp, _Alloc>::
525 : _M_push_front_aux(const value_type& __t)
526 : #endif
527 : {
528 : if (size() == max_size())
529 : __throw_length_error(
530 : __N("cannot create std::deque larger than max_size()"));
531 :
532 : _M_reserve_map_at_front();
533 : *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node();
534 : __try
535 : {
536 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node
537 : - 1);
538 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1;
539 : #if __cplusplus >= 201103L
540 : _Alloc_traits::construct(this->_M_impl,
541 : this->_M_impl._M_start._M_cur,
542 : std::forward<_Args>(__args)...);
543 : #else
544 : this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t);
545 : #endif
546 : }
547 : __catch(...)
548 : {
549 : ++this->_M_impl._M_start;
550 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1));
551 : __throw_exception_again;
552 : }
553 : }
554 :
555 : // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first.
556 : template <typename _Tp, typename _Alloc>
557 136 : void deque<_Tp, _Alloc>::
558 : _M_pop_back_aux()
559 : {
560 136 : _M_deallocate_node(this->_M_impl._M_finish._M_first);
561 136 : this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
562 136 : this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
563 136 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
564 : this->_M_impl._M_finish._M_cur);
565 136 : }
566 :
567 : // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1.
568 : // Note that if the deque has at least one element (a precondition for this
569 : // member function), and if
570 : // _M_impl._M_start._M_cur == _M_impl._M_start._M_last,
571 : // then the deque must have at least two nodes.
572 : template <typename _Tp, typename _Alloc>
573 : void deque<_Tp, _Alloc>::
574 : _M_pop_front_aux()
575 : {
576 : _Alloc_traits::destroy(_M_get_Tp_allocator(),
577 : this->_M_impl._M_start._M_cur);
578 : _M_deallocate_node(this->_M_impl._M_start._M_first);
579 : this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1);
580 : this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first;
581 : }
582 :
583 : template <typename _Tp, typename _Alloc>
584 : template <typename _InputIterator>
585 : void
586 : deque<_Tp, _Alloc>::
587 : _M_range_insert_aux(iterator __pos,
588 : _InputIterator __first, _InputIterator __last,
589 : std::input_iterator_tag)
590 : { std::copy(__first, __last, std::inserter(*this, __pos)); }
591 :
592 : template <typename _Tp, typename _Alloc>
593 : template <typename _ForwardIterator>
594 : void
595 : deque<_Tp, _Alloc>::
596 : _M_range_insert_aux(iterator __pos,
597 : _ForwardIterator __first, _ForwardIterator __last,
598 : std::forward_iterator_tag)
599 : {
600 : const size_type __n = std::distance(__first, __last);
601 : if (__pos._M_cur == this->_M_impl._M_start._M_cur)
602 : {
603 : iterator __new_start = _M_reserve_elements_at_front(__n);
604 : __try
605 : {
606 : std::__uninitialized_copy_a(__first, __last, __new_start,
607 : _M_get_Tp_allocator());
608 : this->_M_impl._M_start = __new_start;
609 : }
610 : __catch(...)
611 : {
612 : _M_destroy_nodes(__new_start._M_node,
613 : this->_M_impl._M_start._M_node);
614 : __throw_exception_again;
615 : }
616 : }
617 : else if (__pos._M_cur == this->_M_impl._M_finish._M_cur)
618 : {
619 : iterator __new_finish = _M_reserve_elements_at_back(__n);
620 : __try
621 : {
622 : std::__uninitialized_copy_a(__first, __last,
623 : this->_M_impl._M_finish,
624 : _M_get_Tp_allocator());
625 : this->_M_impl._M_finish = __new_finish;
626 : }
627 : __catch(...)
628 : {
629 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
630 : __new_finish._M_node + 1);
631 : __throw_exception_again;
632 : }
633 : }
634 : else
635 : _M_insert_aux(__pos, __first, __last, __n);
636 : }
637 :
638 : template<typename _Tp, typename _Alloc>
639 : #if __cplusplus >= 201103L
640 : template<typename... _Args>
641 : typename deque<_Tp, _Alloc>::iterator
642 : deque<_Tp, _Alloc>::
643 : _M_insert_aux(iterator __pos, _Args&&... __args)
644 : {
645 : value_type __x_copy(std::forward<_Args>(__args)...); // XXX copy
646 : #else
647 : typename deque<_Tp, _Alloc>::iterator
648 : deque<_Tp, _Alloc>::
649 : _M_insert_aux(iterator __pos, const value_type& __x)
650 : {
651 : value_type __x_copy = __x; // XXX copy
652 : #endif
653 : difference_type __index = __pos - this->_M_impl._M_start;
654 : if (static_cast<size_type>(__index) < size() / 2)
655 : {
656 : push_front(_GLIBCXX_MOVE(front()));
657 : iterator __front1 = this->_M_impl._M_start;
658 : ++__front1;
659 : iterator __front2 = __front1;
660 : ++__front2;
661 : __pos = this->_M_impl._M_start + __index;
662 : iterator __pos1 = __pos;
663 : ++__pos1;
664 : _GLIBCXX_MOVE3(__front2, __pos1, __front1);
665 : }
666 : else
667 : {
668 : push_back(_GLIBCXX_MOVE(back()));
669 : iterator __back1 = this->_M_impl._M_finish;
670 : --__back1;
671 : iterator __back2 = __back1;
672 : --__back2;
673 : __pos = this->_M_impl._M_start + __index;
674 : _GLIBCXX_MOVE_BACKWARD3(__pos, __back2, __back1);
675 : }
676 : *__pos = _GLIBCXX_MOVE(__x_copy);
677 : return __pos;
678 : }
679 :
680 : template <typename _Tp, typename _Alloc>
681 : void
682 : deque<_Tp, _Alloc>::
683 : _M_insert_aux(iterator __pos, size_type __n, const value_type& __x)
684 : {
685 : const difference_type __elems_before = __pos - this->_M_impl._M_start;
686 : const size_type __length = this->size();
687 : value_type __x_copy = __x;
688 : if (__elems_before < difference_type(__length / 2))
689 : {
690 : iterator __new_start = _M_reserve_elements_at_front(__n);
691 : iterator __old_start = this->_M_impl._M_start;
692 : __pos = this->_M_impl._M_start + __elems_before;
693 : __try
694 : {
695 : if (__elems_before >= difference_type(__n))
696 : {
697 : iterator __start_n = (this->_M_impl._M_start
698 : + difference_type(__n));
699 : std::__uninitialized_move_a(this->_M_impl._M_start,
700 : __start_n, __new_start,
701 : _M_get_Tp_allocator());
702 : this->_M_impl._M_start = __new_start;
703 : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
704 : std::fill(__pos - difference_type(__n), __pos, __x_copy);
705 : }
706 : else
707 : {
708 : std::__uninitialized_move_fill(this->_M_impl._M_start,
709 : __pos, __new_start,
710 : this->_M_impl._M_start,
711 : __x_copy,
712 : _M_get_Tp_allocator());
713 : this->_M_impl._M_start = __new_start;
714 : std::fill(__old_start, __pos, __x_copy);
715 : }
716 : }
717 : __catch(...)
718 : {
719 : _M_destroy_nodes(__new_start._M_node,
720 : this->_M_impl._M_start._M_node);
721 : __throw_exception_again;
722 : }
723 : }
724 : else
725 : {
726 : iterator __new_finish = _M_reserve_elements_at_back(__n);
727 : iterator __old_finish = this->_M_impl._M_finish;
728 : const difference_type __elems_after =
729 : difference_type(__length) - __elems_before;
730 : __pos = this->_M_impl._M_finish - __elems_after;
731 : __try
732 : {
733 : if (__elems_after > difference_type(__n))
734 : {
735 : iterator __finish_n = (this->_M_impl._M_finish
736 : - difference_type(__n));
737 : std::__uninitialized_move_a(__finish_n,
738 : this->_M_impl._M_finish,
739 : this->_M_impl._M_finish,
740 : _M_get_Tp_allocator());
741 : this->_M_impl._M_finish = __new_finish;
742 : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
743 : std::fill(__pos, __pos + difference_type(__n), __x_copy);
744 : }
745 : else
746 : {
747 : std::__uninitialized_fill_move(this->_M_impl._M_finish,
748 : __pos + difference_type(__n),
749 : __x_copy, __pos,
750 : this->_M_impl._M_finish,
751 : _M_get_Tp_allocator());
752 : this->_M_impl._M_finish = __new_finish;
753 : std::fill(__pos, __old_finish, __x_copy);
754 : }
755 : }
756 : __catch(...)
757 : {
758 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
759 : __new_finish._M_node + 1);
760 : __throw_exception_again;
761 : }
762 : }
763 : }
764 :
765 : template <typename _Tp, typename _Alloc>
766 : template <typename _ForwardIterator>
767 : void
768 : deque<_Tp, _Alloc>::
769 : _M_insert_aux(iterator __pos,
770 : _ForwardIterator __first, _ForwardIterator __last,
771 : size_type __n)
772 : {
773 : const difference_type __elemsbefore = __pos - this->_M_impl._M_start;
774 : const size_type __length = size();
775 : if (static_cast<size_type>(__elemsbefore) < __length / 2)
776 : {
777 : iterator __new_start = _M_reserve_elements_at_front(__n);
778 : iterator __old_start = this->_M_impl._M_start;
779 : __pos = this->_M_impl._M_start + __elemsbefore;
780 : __try
781 : {
782 : if (__elemsbefore >= difference_type(__n))
783 : {
784 : iterator __start_n = (this->_M_impl._M_start
785 : + difference_type(__n));
786 : std::__uninitialized_move_a(this->_M_impl._M_start,
787 : __start_n, __new_start,
788 : _M_get_Tp_allocator());
789 : this->_M_impl._M_start = __new_start;
790 : _GLIBCXX_MOVE3(__start_n, __pos, __old_start);
791 : std::copy(__first, __last, __pos - difference_type(__n));
792 : }
793 : else
794 : {
795 : _ForwardIterator __mid = __first;
796 : std::advance(__mid, difference_type(__n) - __elemsbefore);
797 : std::__uninitialized_move_copy(this->_M_impl._M_start,
798 : __pos, __first, __mid,
799 : __new_start,
800 : _M_get_Tp_allocator());
801 : this->_M_impl._M_start = __new_start;
802 : std::copy(__mid, __last, __old_start);
803 : }
804 : }
805 : __catch(...)
806 : {
807 : _M_destroy_nodes(__new_start._M_node,
808 : this->_M_impl._M_start._M_node);
809 : __throw_exception_again;
810 : }
811 : }
812 : else
813 : {
814 : iterator __new_finish = _M_reserve_elements_at_back(__n);
815 : iterator __old_finish = this->_M_impl._M_finish;
816 : const difference_type __elemsafter =
817 : difference_type(__length) - __elemsbefore;
818 : __pos = this->_M_impl._M_finish - __elemsafter;
819 : __try
820 : {
821 : if (__elemsafter > difference_type(__n))
822 : {
823 : iterator __finish_n = (this->_M_impl._M_finish
824 : - difference_type(__n));
825 : std::__uninitialized_move_a(__finish_n,
826 : this->_M_impl._M_finish,
827 : this->_M_impl._M_finish,
828 : _M_get_Tp_allocator());
829 : this->_M_impl._M_finish = __new_finish;
830 : _GLIBCXX_MOVE_BACKWARD3(__pos, __finish_n, __old_finish);
831 : std::copy(__first, __last, __pos);
832 : }
833 : else
834 : {
835 : _ForwardIterator __mid = __first;
836 : std::advance(__mid, __elemsafter);
837 : std::__uninitialized_copy_move(__mid, __last, __pos,
838 : this->_M_impl._M_finish,
839 : this->_M_impl._M_finish,
840 : _M_get_Tp_allocator());
841 : this->_M_impl._M_finish = __new_finish;
842 : std::copy(__first, __mid, __pos);
843 : }
844 : }
845 : __catch(...)
846 : {
847 : _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1,
848 : __new_finish._M_node + 1);
849 : __throw_exception_again;
850 : }
851 : }
852 : }
853 :
854 : template<typename _Tp, typename _Alloc>
855 : void
856 1278 : deque<_Tp, _Alloc>::
857 : _M_destroy_data_aux(iterator __first, iterator __last)
858 : {
859 1278 : for (_Map_pointer __node = __first._M_node + 1;
860 1278 : __node < __last._M_node; ++__node)
861 0 : std::_Destroy(*__node, *__node + _S_buffer_size(),
862 0 : _M_get_Tp_allocator());
863 :
864 1278 : if (__first._M_node != __last._M_node)
865 : {
866 0 : std::_Destroy(__first._M_cur, __first._M_last,
867 0 : _M_get_Tp_allocator());
868 0 : std::_Destroy(__last._M_first, __last._M_cur,
869 0 : _M_get_Tp_allocator());
870 : }
871 : else
872 1278 : std::_Destroy(__first._M_cur, __last._M_cur,
873 1278 : _M_get_Tp_allocator());
874 1278 : }
875 :
876 : template <typename _Tp, typename _Alloc>
877 : void
878 : deque<_Tp, _Alloc>::
879 : _M_new_elements_at_front(size_type __new_elems)
880 : {
881 : if (this->max_size() - this->size() < __new_elems)
882 : __throw_length_error(__N("deque::_M_new_elements_at_front"));
883 :
884 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
885 : / _S_buffer_size());
886 : _M_reserve_map_at_front(__new_nodes);
887 : size_type __i;
888 : __try
889 : {
890 : for (__i = 1; __i <= __new_nodes; ++__i)
891 : *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node();
892 : }
893 : __catch(...)
894 : {
895 : for (size_type __j = 1; __j < __i; ++__j)
896 : _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j));
897 : __throw_exception_again;
898 : }
899 : }
900 :
901 : template <typename _Tp, typename _Alloc>
902 : void
903 : deque<_Tp, _Alloc>::
904 : _M_new_elements_at_back(size_type __new_elems)
905 : {
906 : if (this->max_size() - this->size() < __new_elems)
907 : __throw_length_error(__N("deque::_M_new_elements_at_back"));
908 :
909 : const size_type __new_nodes = ((__new_elems + _S_buffer_size() - 1)
910 : / _S_buffer_size());
911 : _M_reserve_map_at_back(__new_nodes);
912 : size_type __i;
913 : __try
914 : {
915 : for (__i = 1; __i <= __new_nodes; ++__i)
916 : *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node();
917 : }
918 : __catch(...)
919 : {
920 : for (size_type __j = 1; __j < __i; ++__j)
921 : _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j));
922 : __throw_exception_again;
923 : }
924 : }
925 :
926 : template <typename _Tp, typename _Alloc>
927 : void
928 7 : deque<_Tp, _Alloc>::
929 : _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
930 : {
931 7 : const size_type __old_num_nodes
932 7 : = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
933 7 : const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
934 :
935 : _Map_pointer __new_nstart;
936 7 : if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
937 : {
938 0 : __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
939 0 : - __new_num_nodes) / 2
940 0 : + (__add_at_front ? __nodes_to_add : 0);
941 0 : if (__new_nstart < this->_M_impl._M_start._M_node)
942 0 : std::copy(this->_M_impl._M_start._M_node,
943 0 : this->_M_impl._M_finish._M_node + 1,
944 : __new_nstart);
945 : else
946 0 : std::copy_backward(this->_M_impl._M_start._M_node,
947 0 : this->_M_impl._M_finish._M_node + 1,
948 0 : __new_nstart + __old_num_nodes);
949 : }
950 : else
951 : {
952 14 : size_type __new_map_size = this->_M_impl._M_map_size
953 7 : + std::max(this->_M_impl._M_map_size,
954 : __nodes_to_add) + 2;
955 :
956 7 : _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
957 14 : __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
958 7 : + (__add_at_front ? __nodes_to_add : 0);
959 7 : std::copy(this->_M_impl._M_start._M_node,
960 7 : this->_M_impl._M_finish._M_node + 1,
961 : __new_nstart);
962 7 : _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
963 :
964 7 : this->_M_impl._M_map = __new_map;
965 7 : this->_M_impl._M_map_size = __new_map_size;
966 : }
967 :
968 7 : this->_M_impl._M_start._M_set_node(__new_nstart);
969 7 : this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
970 7 : }
971 :
972 : _GLIBCXX_END_NAMESPACE_CONTAINER
973 :
974 : // Overload for deque::iterators, exploiting the "segmented-iterator
975 : // optimization".
976 : template<typename _Tp, typename _VTp>
977 : void
978 : __fill_a1(const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __first,
979 : const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*>& __last,
980 : const _VTp& __value)
981 : {
982 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
983 : if (__first._M_node != __last._M_node)
984 : {
985 : std::__fill_a1(__first._M_cur, __first._M_last, __value);
986 :
987 : for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
988 : __node < __last._M_node; ++__node)
989 : std::__fill_a1(*__node, *__node + _Iter::_S_buffer_size(), __value);
990 :
991 : std::__fill_a1(__last._M_first, __last._M_cur, __value);
992 : }
993 : else
994 : std::__fill_a1(__first._M_cur, __last._M_cur, __value);
995 : }
996 :
997 : template<bool _IsMove,
998 : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
999 : _OI
1000 : __copy_move_dit(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1001 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1002 : _OI __result)
1003 : {
1004 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1005 : if (__first._M_node != __last._M_node)
1006 : {
1007 : __result
1008 : = std::__copy_move_a1<_IsMove>(__first._M_cur, __first._M_last,
1009 : __result);
1010 :
1011 : for (typename _Iter::_Map_pointer __node = __first._M_node + 1;
1012 : __node != __last._M_node; ++__node)
1013 : __result
1014 : = std::__copy_move_a1<_IsMove>(*__node,
1015 : *__node + _Iter::_S_buffer_size(),
1016 : __result);
1017 :
1018 : return std::__copy_move_a1<_IsMove>(__last._M_first, __last._M_cur,
1019 : __result);
1020 : }
1021 :
1022 : return std::__copy_move_a1<_IsMove>(__first._M_cur, __last._M_cur,
1023 : __result);
1024 : }
1025 :
1026 : template<bool _IsMove,
1027 : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1028 : _OI
1029 : __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1030 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1031 : _OI __result)
1032 : { return __copy_move_dit<_IsMove>(__first, __last, __result); }
1033 :
1034 : template<bool _IsMove,
1035 : typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
1036 : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1037 : __copy_move_a1(_GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1038 : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1039 : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1040 : { return __copy_move_dit<_IsMove>(__first, __last, __result); }
1041 :
1042 : template<bool _IsMove, typename _II, typename _Tp>
1043 : typename __gnu_cxx::__enable_if<
1044 : __is_random_access_iter<_II>::__value,
1045 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1046 : __copy_move_a1(_II __first, _II __last,
1047 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1048 : {
1049 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1050 : typedef typename _Iter::difference_type difference_type;
1051 :
1052 : difference_type __len = __last - __first;
1053 : while (__len > 0)
1054 : {
1055 : const difference_type __clen
1056 : = std::min(__len, __result._M_last - __result._M_cur);
1057 : std::__copy_move_a1<_IsMove>(__first, __first + __clen,
1058 : __result._M_cur);
1059 :
1060 : __first += __clen;
1061 : __result += __clen;
1062 : __len -= __clen;
1063 : }
1064 :
1065 : return __result;
1066 : }
1067 :
1068 : template<bool _IsMove,
1069 : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1070 : _OI
1071 : __copy_move_backward_dit(
1072 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1073 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1074 : _OI __result)
1075 : {
1076 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1077 : if (__first._M_node != __last._M_node)
1078 : {
1079 : __result = std::__copy_move_backward_a1<_IsMove>(
1080 : __last._M_first, __last._M_cur, __result);
1081 :
1082 : for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
1083 : __node != __first._M_node; --__node)
1084 : __result = std::__copy_move_backward_a1<_IsMove>(
1085 : *__node, *__node + _Iter::_S_buffer_size(), __result);
1086 :
1087 : return std::__copy_move_backward_a1<_IsMove>(
1088 : __first._M_cur, __first._M_last, __result);
1089 : }
1090 :
1091 : return std::__copy_move_backward_a1<_IsMove>(
1092 : __first._M_cur, __last._M_cur, __result);
1093 : }
1094 :
1095 : template<bool _IsMove,
1096 : typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1097 : _OI
1098 : __copy_move_backward_a1(
1099 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1100 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1101 : _OI __result)
1102 : { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1103 :
1104 : template<bool _IsMove,
1105 : typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
1106 : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1107 : __copy_move_backward_a1(
1108 : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1109 : _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1110 : _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1111 : { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1112 :
1113 : template<bool _IsMove, typename _II, typename _Tp>
1114 : typename __gnu_cxx::__enable_if<
1115 : __is_random_access_iter<_II>::__value,
1116 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1117 : __copy_move_backward_a1(_II __first, _II __last,
1118 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1119 : {
1120 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1121 : typedef typename _Iter::difference_type difference_type;
1122 :
1123 : difference_type __len = __last - __first;
1124 : while (__len > 0)
1125 : {
1126 : difference_type __rlen = __result._M_cur - __result._M_first;
1127 : _Tp* __rend = __result._M_cur;
1128 : if (!__rlen)
1129 : {
1130 : __rlen = _Iter::_S_buffer_size();
1131 : __rend = *(__result._M_node - 1) + __rlen;
1132 : }
1133 :
1134 : const difference_type __clen = std::min(__len, __rlen);
1135 : std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
1136 :
1137 : __last -= __clen;
1138 : __result -= __clen;
1139 : __len -= __clen;
1140 : }
1141 :
1142 : return __result;
1143 : }
1144 :
1145 : template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1146 : bool
1147 : __equal_dit(
1148 : const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
1149 : const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
1150 : _II __first2)
1151 : {
1152 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1153 : if (__first1._M_node != __last1._M_node)
1154 : {
1155 : if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
1156 : return false;
1157 :
1158 : __first2 += __first1._M_last - __first1._M_cur;
1159 : for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
1160 : __node != __last1._M_node;
1161 : __first2 += _Iter::_S_buffer_size(), ++__node)
1162 : if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
1163 : __first2))
1164 : return false;
1165 :
1166 : return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
1167 : }
1168 :
1169 : return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
1170 : }
1171 :
1172 : template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1173 : typename __gnu_cxx::__enable_if<
1174 : __is_random_access_iter<_II>::__value, bool>::__type
1175 : __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
1176 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
1177 : _II __first2)
1178 : { return std::__equal_dit(__first1, __last1, __first2); }
1179 :
1180 : template<typename _Tp1, typename _Ref1, typename _Ptr1,
1181 : typename _Tp2, typename _Ref2, typename _Ptr2>
1182 : bool
1183 : __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1184 : _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1185 : _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
1186 : { return std::__equal_dit(__first1, __last1, __first2); }
1187 :
1188 : template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1189 : typename __gnu_cxx::__enable_if<
1190 : __is_random_access_iter<_II>::__value, bool>::__type
1191 : __equal_aux1(_II __first1, _II __last1,
1192 : _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
1193 : {
1194 : typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1195 : typedef typename _Iter::difference_type difference_type;
1196 :
1197 : difference_type __len = __last1 - __first1;
1198 : while (__len > 0)
1199 : {
1200 : const difference_type __clen
1201 : = std::min(__len, __first2._M_last - __first2._M_cur);
1202 : if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
1203 : return false;
1204 :
1205 : __first1 += __clen;
1206 : __len -= __clen;
1207 : __first2 += __clen;
1208 : }
1209 :
1210 : return true;
1211 : }
1212 :
1213 : _GLIBCXX_END_NAMESPACE_VERSION
1214 : } // namespace std
1215 :
1216 : #endif
|
