libstdc++-v3/include/bits/deque.tcc

   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       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(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       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         if (size() == max_size())
 490           __throw_length_error(
 491               __N("cannot create std::deque larger than max_size()"));
 492
 493         _M_reserve_map_at_back();
 494         *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node();
 495         __try
 496           {
 497 #if __cplusplus >= 201103L
 498             _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             this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node
 505                                                 + 1);
 506             this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first;
 507           }
 508         __catch(...)
 509           {
 510             _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1));
 511             __throw_exception_again;
 512           }
 513       }
 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     void deque<_Tp, _Alloc>::
 558     _M_pop_back_aux()
 559     {
 560       _M_deallocate_node(this->_M_impl._M_finish._M_first);
 561       this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1);
 562       this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1;
 563       _Alloc_traits::destroy(_M_get_Tp_allocator(),
 564                              this->_M_impl._M_finish._M_cur);
 565     }
 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      deque<_Tp, _Alloc>::
 857      _M_destroy_data_aux(iterator __first, iterator __last)
 858      {
 859        for (_Map_pointer __node = __first._M_node + 1;
 860             __node < __last._M_node; ++__node)
 861          std::_Destroy(*__node, *__node + _S_buffer_size(),
 862                        _M_get_Tp_allocator());
 863
 864        if (__first._M_node != __last._M_node)
 865          {
 866            std::_Destroy(__first._M_cur, __first._M_last,
 867                          _M_get_Tp_allocator());
 868            std::_Destroy(__last._M_first, __last._M_cur,
 869                          _M_get_Tp_allocator());
 870          }
 871        else
 872          std::_Destroy(__first._M_cur, __last._M_cur,
 873                        _M_get_Tp_allocator());
 874      }
 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     deque<_Tp, _Alloc>::
 929     _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front)
 930     {
 931       const size_type __old_num_nodes
 932         = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1;
 933       const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
 934
 935       _Map_pointer __new_nstart;
 936       if (this->_M_impl._M_map_size > 2 * __new_num_nodes)
 937         {
 938           __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size
 939                                          - __new_num_nodes) / 2
 940                          + (__add_at_front ? __nodes_to_add : 0);
 941           if (__new_nstart < this->_M_impl._M_start._M_node)
 942             std::copy(this->_M_impl._M_start._M_node,
 943                       this->_M_impl._M_finish._M_node + 1,
 944                       __new_nstart);
 945           else
 946             std::copy_backward(this->_M_impl._M_start._M_node,
 947                                this->_M_impl._M_finish._M_node + 1,
 948                                __new_nstart + __old_num_nodes);
 949         }
 950       else
 951         {
 952           size_type __new_map_size = this->_M_impl._M_map_size
 953                                      + std::max(this->_M_impl._M_map_size,
 954                                                 __nodes_to_add) + 2;
 955
 956           _Map_pointer __new_map = this->_M_allocate_map(__new_map_size);
 957           __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
 958                          + (__add_at_front ? __nodes_to_add : 0);
 959           std::copy(this->_M_impl._M_start._M_node,
 960                     this->_M_impl._M_finish._M_node + 1,
 961                     __new_nstart);
 962           _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size);
 963
 964           this->_M_impl._M_map = __new_map;
 965           this->_M_impl._M_map_size = __new_map_size;
 966         }
 967
 968       this->_M_impl._M_start._M_set_node(__new_nstart);
 969       this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
 970     }
 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, typename _CharT>
1069     typename __gnu_cxx::__enable_if<
1070       __is_char<_CharT>::__value,
1071       _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1072     __copy_move_a2(
1073         istreambuf_iterator<_CharT, char_traits<_CharT> > __first,
1074         istreambuf_iterator<_CharT, char_traits<_CharT> > __last,
1075         _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result)
1076     {
1077       if (__first == __last)
1078         return __result;
1079
1080       for (;;)
1081         {
1082           const std::ptrdiff_t __len = __result._M_last - __result._M_cur;
1083           const std::ptrdiff_t __nb
1084             = std::__copy_n_a(__first, __len, __result._M_cur, false)
1085             - __result._M_cur;
1086           __result += __nb;
1087
1088           if (__nb != __len)
1089             break;
1090         }
1091
1092       return __result;
1093     }
1094
1095   template<typename _CharT, typename _Size>
1096     typename __gnu_cxx::__enable_if<
1097       __is_char<_CharT>::__value,
1098       _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> >::__type
1099     __copy_n_a(
1100       istreambuf_iterator<_CharT, char_traits<_CharT> > __it, _Size __size,
1101       _GLIBCXX_STD_C::_Deque_iterator<_CharT, _CharT&, _CharT*> __result,
1102       bool __strict)
1103     {
1104       if (__size == 0)
1105         return __result;
1106
1107       do
1108         {
1109           const _Size __len
1110             = std::min<_Size>(__result._M_last - __result._M_cur, __size);
1111           std::__copy_n_a(__it, __len, __result._M_cur, __strict);
1112           __result += __len;
1113           __size -= __len;
1114         }
1115       while (__size != 0);
1116       return __result;
1117     }
1118
1119   template<bool _IsMove,
1120            typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1121     _OI
1122     __copy_move_backward_dit(
1123                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1124                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1125                 _OI __result)
1126     {
1127       typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1128       if (__first._M_node != __last._M_node)
1129         {
1130           __result = std::__copy_move_backward_a1<_IsMove>(
1131                 __last._M_first, __last._M_cur, __result);
1132
1133           for (typename _Iter::_Map_pointer __node = __last._M_node - 1;
1134                __node != __first._M_node; --__node)
1135             __result = std::__copy_move_backward_a1<_IsMove>(
1136                 *__node, *__node + _Iter::_S_buffer_size(), __result);
1137
1138           return std::__copy_move_backward_a1<_IsMove>(
1139                         __first._M_cur, __first._M_last, __result);
1140         }
1141
1142       return std::__copy_move_backward_a1<_IsMove>(
1143                 __first._M_cur, __last._M_cur, __result);
1144     }
1145
1146   template<bool _IsMove,
1147            typename _Tp, typename _Ref, typename _Ptr, typename _OI>
1148     _OI
1149     __copy_move_backward_a1(
1150                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first,
1151                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last,
1152                 _OI __result)
1153     { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1154
1155   template<bool _IsMove,
1156            typename _ITp, typename _IRef, typename _IPtr, typename _OTp>
1157     _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*>
1158     __copy_move_backward_a1(
1159                 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __first,
1160                 _GLIBCXX_STD_C::_Deque_iterator<_ITp, _IRef, _IPtr> __last,
1161                 _GLIBCXX_STD_C::_Deque_iterator<_OTp, _OTp&, _OTp*> __result)
1162     { return __copy_move_backward_dit<_IsMove>(__first, __last, __result); }
1163
1164   template<bool _IsMove, typename _II, typename _Tp>
1165     typename __gnu_cxx::__enable_if<
1166       __is_random_access_iter<_II>::__value,
1167       _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> >::__type
1168     __copy_move_backward_a1(_II __first, _II __last,
1169                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> __result)
1170     {
1171       typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Tp&, _Tp*> _Iter;
1172       typedef typename _Iter::difference_type difference_type;
1173
1174       difference_type __len = __last - __first;
1175       while (__len > 0)
1176         {
1177           difference_type __rlen = __result._M_cur - __result._M_first;
1178           _Tp* __rend = __result._M_cur;
1179           if (!__rlen)
1180             {
1181               __rlen = _Iter::_S_buffer_size();
1182               __rend = *(__result._M_node - 1) + __rlen;
1183             }
1184
1185           const difference_type __clen = std::min(__len, __rlen);
1186           std::__copy_move_backward_a1<_IsMove>(__last - __clen, __last, __rend);
1187
1188           __last -= __clen;
1189           __result -= __clen;
1190           __len -= __clen;
1191         }
1192
1193       return __result;
1194     }
1195
1196   template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1197     bool
1198     __equal_dit(
1199         const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __first1,
1200         const _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr>& __last1,
1201         _II __first2)
1202     {
1203       typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1204       if (__first1._M_node != __last1._M_node)
1205         {
1206           if (!std::__equal_aux1(__first1._M_cur, __first1._M_last, __first2))
1207             return false;
1208
1209           __first2 += __first1._M_last - __first1._M_cur;
1210           for (typename _Iter::_Map_pointer __node = __first1._M_node + 1;
1211                __node != __last1._M_node;
1212                __first2 += _Iter::_S_buffer_size(), ++__node)
1213             if (!std::__equal_aux1(*__node, *__node + _Iter::_S_buffer_size(),
1214                                   __first2))
1215               return false;
1216
1217           return std::__equal_aux1(__last1._M_first, __last1._M_cur, __first2);
1218         }
1219
1220       return std::__equal_aux1(__first1._M_cur, __last1._M_cur, __first2);
1221     }
1222
1223   template<typename _Tp, typename _Ref, typename _Ptr, typename _II>
1224     typename __gnu_cxx::__enable_if<
1225       __is_random_access_iter<_II>::__value, bool>::__type
1226     __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first1,
1227                  _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __last1,
1228                  _II __first2)
1229     { return std::__equal_dit(__first1, __last1, __first2); }
1230
1231   template<typename _Tp1, typename _Ref1, typename _Ptr1,
1232            typename _Tp2, typename _Ref2, typename _Ptr2>
1233     bool
1234     __equal_aux1(_GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __first1,
1235                  _GLIBCXX_STD_C::_Deque_iterator<_Tp1, _Ref1, _Ptr1> __last1,
1236                  _GLIBCXX_STD_C::_Deque_iterator<_Tp2, _Ref2, _Ptr2> __first2)
1237     { return std::__equal_dit(__first1, __last1, __first2); }
1238
1239   template<typename _II, typename _Tp, typename _Ref, typename _Ptr>
1240     typename __gnu_cxx::__enable_if<
1241       __is_random_access_iter<_II>::__value, bool>::__type
1242     __equal_aux1(_II __first1, _II __last1,
1243                 _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> __first2)
1244     {
1245       typedef _GLIBCXX_STD_C::_Deque_iterator<_Tp, _Ref, _Ptr> _Iter;
1246       typedef typename _Iter::difference_type difference_type;
1247
1248       difference_type __len = __last1 - __first1;
1249       while (__len > 0)
1250         {
1251           const difference_type __clen
1252             = std::min(__len, __first2._M_last - __first2._M_cur);
1253           if (!std::__equal_aux1(__first1, __first1 + __clen, __first2._M_cur))
1254             return false;
1255
1256           __first1 += __clen;
1257           __len -= __clen;
1258           __first2 += __clen;
1259         }
1260
1261       return true;
1262     }
1263
1264 _GLIBCXX_END_NAMESPACE_VERSION
1265 } // namespace std
1266
1267 #endif