pinoc_gcc/lib/include/c++/4.5-GNUH8_v10.03/bits/stl_iterator.h

   1 // Iterators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 3, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  *
  40  * Copyright (c) 1996-1998
  41  * Silicon Graphics Computer Systems, Inc.
  42  *
  43  * Permission to use, copy, modify, distribute and sell this software
  44  * and its documentation for any purpose is hereby granted without fee,
  45  * provided that the above copyright notice appear in all copies and
  46  * that both that copyright notice and this permission notice appear
  47  * in supporting documentation.  Silicon Graphics makes no
  48  * representations about the suitability of this software for any
  49  * purpose.  It is provided "as is" without express or implied warranty.
  50  */
  51
  52 /** @file stl_iterator.h
  53  *  This is an internal header file, included by other library headers.
  54  *  You should not attempt to use it directly.
  55  *
  56  *  This file implements reverse_iterator, back_insert_iterator,
  57  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
  58  *  supporting functions and overloaded operators.
  59  */
  60
  61 #ifndef _STL_ITERATOR_H
  62 #define _STL_ITERATOR_H 1
  63
  64 #include <bits/cpp_type_traits.h>
  65 #include <ext/type_traits.h>
  66 #include <bits/move.h>
  67
  68 _GLIBCXX_BEGIN_NAMESPACE(std)
  69
  70   /**
  71    * @addtogroup iterators
  72    * @{
  73    */
  74
  75   // 24.4.1 Reverse iterators
  76   /**
  77    *  Bidirectional and random access iterators have corresponding reverse
  78    *  %iterator adaptors that iterate through the data structure in the
  79    *  opposite direction.  They have the same signatures as the corresponding
  80    *  iterators.  The fundamental relation between a reverse %iterator and its
  81    *  corresponding %iterator @c i is established by the identity:
  82    *  @code
  83    *      &*(reverse_iterator(i)) == &*(i - 1)
  84    *  @endcode
  85    *
  86    *  <em>This mapping is dictated by the fact that while there is always a
  87    *  pointer past the end of an array, there might not be a valid pointer
  88    *  before the beginning of an array.</em> [24.4.1]/1,2
  89    *
  90    *  Reverse iterators can be tricky and surprising at first.  Their
  91    *  semantics make sense, however, and the trickiness is a side effect of
  92    *  the requirement that the iterators must be safe.
  93   */
  94   template<typename _Iterator>
  95     class reverse_iterator
  96     : public iterator<typename iterator_traits<_Iterator>::iterator_category,
  97                       typename iterator_traits<_Iterator>::value_type,
  98                       typename iterator_traits<_Iterator>::difference_type,
  99                       typename iterator_traits<_Iterator>::pointer,
 100                       typename iterator_traits<_Iterator>::reference>
 101     {
 102     protected:
 103       _Iterator current;
 104
 105       typedef iterator_traits<_Iterator>                __traits_type;
 106
 107     public:
 108       typedef _Iterator                                 iterator_type;
 109       typedef typename __traits_type::difference_type   difference_type;
 110       typedef typename __traits_type::pointer           pointer;
 111       typedef typename __traits_type::reference         reference;
 112
 113       /**
 114        *  The default constructor default-initializes member @p current.
 115        *  If it is a pointer, that means it is zero-initialized.
 116       */
 117       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 118       // 235 No specification of default ctor for reverse_iterator
 119       reverse_iterator() : current() { }
 120
 121       /**
 122        *  This %iterator will move in the opposite direction that @p x does.
 123       */
 124       explicit
 125       reverse_iterator(iterator_type __x) : current(__x) { }
 126
 127       /**
 128        *  The copy constructor is normal.
 129       */
 130       reverse_iterator(const reverse_iterator& __x)
 131       : current(__x.current) { }
 132
 133       /**
 134        *  A reverse_iterator across other types can be copied in the normal
 135        *  fashion.
 136       */
 137       template<typename _Iter>
 138         reverse_iterator(const reverse_iterator<_Iter>& __x)
 139         : current(__x.base()) { }
 140
 141       /**
 142        *  @return  @c current, the %iterator used for underlying work.
 143       */
 144       iterator_type
 145       base() const
 146       { return current; }
 147
 148       /**
 149        *  @return  TODO
 150        *
 151        *  @doctodo
 152       */
 153       reference
 154       operator*() const
 155       {
 156         _Iterator __tmp = current;
 157         return *--__tmp;
 158       }
 159
 160       /**
 161        *  @return  TODO
 162        *
 163        *  @doctodo
 164       */
 165       pointer
 166       operator->() const
 167       { return &(operator*()); }
 168
 169       /**
 170        *  @return  TODO
 171        *
 172        *  @doctodo
 173       */
 174       reverse_iterator&
 175       operator++()
 176       {
 177         --current;
 178         return *this;
 179       }
 180
 181       /**
 182        *  @return  TODO
 183        *
 184        *  @doctodo
 185       */
 186       reverse_iterator
 187       operator++(int)
 188       {
 189         reverse_iterator __tmp = *this;
 190         --current;
 191         return __tmp;
 192       }
 193
 194       /**
 195        *  @return  TODO
 196        *
 197        *  @doctodo
 198       */
 199       reverse_iterator&
 200       operator--()
 201       {
 202         ++current;
 203         return *this;
 204       }
 205
 206       /**
 207        *  @return  TODO
 208        *
 209        *  @doctodo
 210       */
 211       reverse_iterator
 212       operator--(int)
 213       {
 214         reverse_iterator __tmp = *this;
 215         ++current;
 216         return __tmp;
 217       }
 218
 219       /**
 220        *  @return  TODO
 221        *
 222        *  @doctodo
 223       */
 224       reverse_iterator
 225       operator+(difference_type __n) const
 226       { return reverse_iterator(current - __n); }
 227
 228       /**
 229        *  @return  TODO
 230        *
 231        *  @doctodo
 232       */
 233       reverse_iterator&
 234       operator+=(difference_type __n)
 235       {
 236         current -= __n;
 237         return *this;
 238       }
 239
 240       /**
 241        *  @return  TODO
 242        *
 243        *  @doctodo
 244       */
 245       reverse_iterator
 246       operator-(difference_type __n) const
 247       { return reverse_iterator(current + __n); }
 248
 249       /**
 250        *  @return  TODO
 251        *
 252        *  @doctodo
 253       */
 254       reverse_iterator&
 255       operator-=(difference_type __n)
 256       {
 257         current += __n;
 258         return *this;
 259       }
 260
 261       /**
 262        *  @return  TODO
 263        *
 264        *  @doctodo
 265       */
 266       reference
 267       operator[](difference_type __n) const
 268       { return *(*this + __n); }
 269     };
 270
 271   //@{
 272   /**
 273    *  @param  x  A %reverse_iterator.
 274    *  @param  y  A %reverse_iterator.
 275    *  @return  A simple bool.
 276    *
 277    *  Reverse iterators forward many operations to their underlying base()
 278    *  iterators.  Others are implemented in terms of one another.
 279    *
 280   */
 281   template<typename _Iterator>
 282     inline bool
 283     operator==(const reverse_iterator<_Iterator>& __x,
 284                const reverse_iterator<_Iterator>& __y)
 285     { return __x.base() == __y.base(); }
 286
 287   template<typename _Iterator>
 288     inline bool
 289     operator<(const reverse_iterator<_Iterator>& __x,
 290               const reverse_iterator<_Iterator>& __y)
 291     { return __y.base() < __x.base(); }
 292
 293   template<typename _Iterator>
 294     inline bool
 295     operator!=(const reverse_iterator<_Iterator>& __x,
 296                const reverse_iterator<_Iterator>& __y)
 297     { return !(__x == __y); }
 298
 299   template<typename _Iterator>
 300     inline bool
 301     operator>(const reverse_iterator<_Iterator>& __x,
 302               const reverse_iterator<_Iterator>& __y)
 303     { return __y < __x; }
 304
 305   template<typename _Iterator>
 306     inline bool
 307     operator<=(const reverse_iterator<_Iterator>& __x,
 308                const reverse_iterator<_Iterator>& __y)
 309     { return !(__y < __x); }
 310
 311   template<typename _Iterator>
 312     inline bool
 313     operator>=(const reverse_iterator<_Iterator>& __x,
 314                const reverse_iterator<_Iterator>& __y)
 315     { return !(__x < __y); }
 316
 317   template<typename _Iterator>
 318     inline typename reverse_iterator<_Iterator>::difference_type
 319     operator-(const reverse_iterator<_Iterator>& __x,
 320               const reverse_iterator<_Iterator>& __y)
 321     { return __y.base() - __x.base(); }
 322
 323   template<typename _Iterator>
 324     inline reverse_iterator<_Iterator>
 325     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 326               const reverse_iterator<_Iterator>& __x)
 327     { return reverse_iterator<_Iterator>(__x.base() - __n); }
 328
 329   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 330   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
 331   template<typename _IteratorL, typename _IteratorR>
 332     inline bool
 333     operator==(const reverse_iterator<_IteratorL>& __x,
 334                const reverse_iterator<_IteratorR>& __y)
 335     { return __x.base() == __y.base(); }
 336
 337   template<typename _IteratorL, typename _IteratorR>
 338     inline bool
 339     operator<(const reverse_iterator<_IteratorL>& __x,
 340               const reverse_iterator<_IteratorR>& __y)
 341     { return __y.base() < __x.base(); }
 342
 343   template<typename _IteratorL, typename _IteratorR>
 344     inline bool
 345     operator!=(const reverse_iterator<_IteratorL>& __x,
 346                const reverse_iterator<_IteratorR>& __y)
 347     { return !(__x == __y); }
 348
 349   template<typename _IteratorL, typename _IteratorR>
 350     inline bool
 351     operator>(const reverse_iterator<_IteratorL>& __x,
 352               const reverse_iterator<_IteratorR>& __y)
 353     { return __y < __x; }
 354
 355   template<typename _IteratorL, typename _IteratorR>
 356     inline bool
 357     operator<=(const reverse_iterator<_IteratorL>& __x,
 358                const reverse_iterator<_IteratorR>& __y)
 359     { return !(__y < __x); }
 360
 361   template<typename _IteratorL, typename _IteratorR>
 362     inline bool
 363     operator>=(const reverse_iterator<_IteratorL>& __x,
 364                const reverse_iterator<_IteratorR>& __y)
 365     { return !(__x < __y); }
 366
 367   template<typename _IteratorL, typename _IteratorR>
 368 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 369     // DR 685.
 370     inline auto
 371     operator-(const reverse_iterator<_IteratorL>& __x,
 372               const reverse_iterator<_IteratorR>& __y)
 373     -> decltype(__y.base() - __x.base())
 374 #else
 375     inline typename reverse_iterator<_IteratorL>::difference_type
 376     operator-(const reverse_iterator<_IteratorL>& __x,
 377               const reverse_iterator<_IteratorR>& __y)
 378 #endif
 379     { return __y.base() - __x.base(); }
 380   //@}
 381
 382   // 24.4.2.2.1 back_insert_iterator
 383   /**
 384    *  @brief  Turns assignment into insertion.
 385    *
 386    *  These are output iterators, constructed from a container-of-T.
 387    *  Assigning a T to the iterator appends it to the container using
 388    *  push_back.
 389    *
 390    *  Tip:  Using the back_inserter function to create these iterators can
 391    *  save typing.
 392   */
 393   template<typename _Container>
 394     class back_insert_iterator
 395     : public iterator<output_iterator_tag, void, void, void, void>
 396     {
 397     protected:
 398       _Container* container;
 399
 400     public:
 401       /// A nested typedef for the type of whatever container you used.
 402       typedef _Container          container_type;
 403
 404       /// The only way to create this %iterator is with a container.
 405       explicit
 406       back_insert_iterator(_Container& __x) : container(&__x) { }
 407
 408       /**
 409        *  @param  value  An instance of whatever type
 410        *                 container_type::const_reference is; presumably a
 411        *                 reference-to-const T for container<T>.
 412        *  @return  This %iterator, for chained operations.
 413        *
 414        *  This kind of %iterator doesn't really have a @a position in the
 415        *  container (you can think of the position as being permanently at
 416        *  the end, if you like).  Assigning a value to the %iterator will
 417        *  always append the value to the end of the container.
 418       */
 419       back_insert_iterator&
 420       operator=(typename _Container::const_reference __value)
 421       {
 422         container->push_back(__value);
 423         return *this;
 424       }
 425
 426 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 427       back_insert_iterator&
 428       operator=(typename _Container::value_type&& __value)
 429       {
 430         container->push_back(std::move(__value));
 431         return *this;
 432       }
 433 #endif
 434
 435       /// Simply returns *this.
 436       back_insert_iterator&
 437       operator*()
 438       { return *this; }
 439
 440       /// Simply returns *this.  (This %iterator does not @a move.)
 441       back_insert_iterator&
 442       operator++()
 443       { return *this; }
 444
 445       /// Simply returns *this.  (This %iterator does not @a move.)
 446       back_insert_iterator
 447       operator++(int)
 448       { return *this; }
 449     };
 450
 451   /**
 452    *  @param  x  A container of arbitrary type.
 453    *  @return  An instance of back_insert_iterator working on @p x.
 454    *
 455    *  This wrapper function helps in creating back_insert_iterator instances.
 456    *  Typing the name of the %iterator requires knowing the precise full
 457    *  type of the container, which can be tedious and impedes generic
 458    *  programming.  Using this function lets you take advantage of automatic
 459    *  template parameter deduction, making the compiler match the correct
 460    *  types for you.
 461   */
 462   template<typename _Container>
 463     inline back_insert_iterator<_Container>
 464     back_inserter(_Container& __x)
 465     { return back_insert_iterator<_Container>(__x); }
 466
 467   /**
 468    *  @brief  Turns assignment into insertion.
 469    *
 470    *  These are output iterators, constructed from a container-of-T.
 471    *  Assigning a T to the iterator prepends it to the container using
 472    *  push_front.
 473    *
 474    *  Tip:  Using the front_inserter function to create these iterators can
 475    *  save typing.
 476   */
 477   template<typename _Container>
 478     class front_insert_iterator
 479     : public iterator<output_iterator_tag, void, void, void, void>
 480     {
 481     protected:
 482       _Container* container;
 483
 484     public:
 485       /// A nested typedef for the type of whatever container you used.
 486       typedef _Container          container_type;
 487
 488       /// The only way to create this %iterator is with a container.
 489       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 490
 491       /**
 492        *  @param  value  An instance of whatever type
 493        *                 container_type::const_reference is; presumably a
 494        *                 reference-to-const T for container<T>.
 495        *  @return  This %iterator, for chained operations.
 496        *
 497        *  This kind of %iterator doesn't really have a @a position in the
 498        *  container (you can think of the position as being permanently at
 499        *  the front, if you like).  Assigning a value to the %iterator will
 500        *  always prepend the value to the front of the container.
 501       */
 502       front_insert_iterator&
 503       operator=(typename _Container::const_reference __value)
 504       {
 505         container->push_front(__value);
 506         return *this;
 507       }
 508
 509 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 510       front_insert_iterator&
 511       operator=(typename _Container::value_type&& __value)
 512       {
 513         container->push_front(std::move(__value));
 514         return *this;
 515       }
 516 #endif
 517
 518       /// Simply returns *this.
 519       front_insert_iterator&
 520       operator*()
 521       { return *this; }
 522
 523       /// Simply returns *this.  (This %iterator does not @a move.)
 524       front_insert_iterator&
 525       operator++()
 526       { return *this; }
 527
 528       /// Simply returns *this.  (This %iterator does not @a move.)
 529       front_insert_iterator
 530       operator++(int)
 531       { return *this; }
 532     };
 533
 534   /**
 535    *  @param  x  A container of arbitrary type.
 536    *  @return  An instance of front_insert_iterator working on @p x.
 537    *
 538    *  This wrapper function helps in creating front_insert_iterator instances.
 539    *  Typing the name of the %iterator requires knowing the precise full
 540    *  type of the container, which can be tedious and impedes generic
 541    *  programming.  Using this function lets you take advantage of automatic
 542    *  template parameter deduction, making the compiler match the correct
 543    *  types for you.
 544   */
 545   template<typename _Container>
 546     inline front_insert_iterator<_Container>
 547     front_inserter(_Container& __x)
 548     { return front_insert_iterator<_Container>(__x); }
 549
 550   /**
 551    *  @brief  Turns assignment into insertion.
 552    *
 553    *  These are output iterators, constructed from a container-of-T.
 554    *  Assigning a T to the iterator inserts it in the container at the
 555    *  %iterator's position, rather than overwriting the value at that
 556    *  position.
 557    *
 558    *  (Sequences will actually insert a @e copy of the value before the
 559    *  %iterator's position.)
 560    *
 561    *  Tip:  Using the inserter function to create these iterators can
 562    *  save typing.
 563   */
 564   template<typename _Container>
 565     class insert_iterator
 566     : public iterator<output_iterator_tag, void, void, void, void>
 567     {
 568     protected:
 569       _Container* container;
 570       typename _Container::iterator iter;
 571
 572     public:
 573       /// A nested typedef for the type of whatever container you used.
 574       typedef _Container          container_type;
 575
 576       /**
 577        *  The only way to create this %iterator is with a container and an
 578        *  initial position (a normal %iterator into the container).
 579       */
 580       insert_iterator(_Container& __x, typename _Container::iterator __i)
 581       : container(&__x), iter(__i) {}
 582
 583       /**
 584        *  @param  value  An instance of whatever type
 585        *                 container_type::const_reference is; presumably a
 586        *                 reference-to-const T for container<T>.
 587        *  @return  This %iterator, for chained operations.
 588        *
 589        *  This kind of %iterator maintains its own position in the
 590        *  container.  Assigning a value to the %iterator will insert the
 591        *  value into the container at the place before the %iterator.
 592        *
 593        *  The position is maintained such that subsequent assignments will
 594        *  insert values immediately after one another.  For example,
 595        *  @code
 596        *     // vector v contains A and Z
 597        *
 598        *     insert_iterator i (v, ++v.begin());
 599        *     i = 1;
 600        *     i = 2;
 601        *     i = 3;
 602        *
 603        *     // vector v contains A, 1, 2, 3, and Z
 604        *  @endcode
 605       */
 606       insert_iterator&
 607       operator=(typename _Container::const_reference __value)
 608       {
 609         iter = container->insert(iter, __value);
 610         ++iter;
 611         return *this;
 612       }
 613
 614 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 615       insert_iterator&
 616       operator=(typename _Container::value_type&& __value)
 617       {
 618         iter = container->insert(iter, std::move(__value));
 619         ++iter;
 620         return *this;
 621       }
 622 #endif
 623
 624       /// Simply returns *this.
 625       insert_iterator&
 626       operator*()
 627       { return *this; }
 628
 629       /// Simply returns *this.  (This %iterator does not @a move.)
 630       insert_iterator&
 631       operator++()
 632       { return *this; }
 633
 634       /// Simply returns *this.  (This %iterator does not @a move.)
 635       insert_iterator&
 636       operator++(int)
 637       { return *this; }
 638     };
 639
 640   /**
 641    *  @param  x  A container of arbitrary type.
 642    *  @return  An instance of insert_iterator working on @p x.
 643    *
 644    *  This wrapper function helps in creating insert_iterator instances.
 645    *  Typing the name of the %iterator requires knowing the precise full
 646    *  type of the container, which can be tedious and impedes generic
 647    *  programming.  Using this function lets you take advantage of automatic
 648    *  template parameter deduction, making the compiler match the correct
 649    *  types for you.
 650   */
 651   template<typename _Container, typename _Iterator>
 652     inline insert_iterator<_Container>
 653     inserter(_Container& __x, _Iterator __i)
 654     {
 655       return insert_iterator<_Container>(__x,
 656                                          typename _Container::iterator(__i));
 657     }
 658
 659   // @} group iterators
 660
 661 _GLIBCXX_END_NAMESPACE
 662
 663 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
 664
 665   // This iterator adapter is @a normal in the sense that it does not
 666   // change the semantics of any of the operators of its iterator
 667   // parameter.  Its primary purpose is to convert an iterator that is
 668   // not a class, e.g. a pointer, into an iterator that is a class.
 669   // The _Container parameter exists solely so that different containers
 670   // using this template can instantiate different types, even if the
 671   // _Iterator parameter is the same.
 672   using std::iterator_traits;
 673   using std::iterator;
 674   template<typename _Iterator, typename _Container>
 675     class __normal_iterator
 676     {
 677     protected:
 678       _Iterator _M_current;
 679
 680       typedef iterator_traits<_Iterator>                __traits_type;
 681
 682     public:
 683       typedef _Iterator                                 iterator_type;
 684       typedef typename __traits_type::iterator_category iterator_category;
 685       typedef typename __traits_type::value_type        value_type;
 686       typedef typename __traits_type::difference_type   difference_type;
 687       typedef typename __traits_type::reference         reference;
 688       typedef typename __traits_type::pointer           pointer;
 689
 690       __normal_iterator() : _M_current(_Iterator()) { }
 691
 692       explicit
 693       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 694
 695       // Allow iterator to const_iterator conversion
 696       template<typename _Iter>
 697         __normal_iterator(const __normal_iterator<_Iter,
 698                           typename __enable_if<
 699                (std::__are_same<_Iter, typename _Container::pointer>::__value),
 700                       _Container>::__type>& __i)
 701         : _M_current(__i.base()) { }
 702
 703       // Forward iterator requirements
 704       reference
 705       operator*() const
 706       { return *_M_current; }
 707
 708       pointer
 709       operator->() const
 710       { return _M_current; }
 711
 712       __normal_iterator&
 713       operator++()
 714       {
 715         ++_M_current;
 716         return *this;
 717       }
 718
 719       __normal_iterator
 720       operator++(int)
 721       { return __normal_iterator(_M_current++); }
 722
 723       // Bidirectional iterator requirements
 724       __normal_iterator&
 725       operator--()
 726       {
 727         --_M_current;
 728         return *this;
 729       }
 730
 731       __normal_iterator
 732       operator--(int)
 733       { return __normal_iterator(_M_current--); }
 734
 735       // Random access iterator requirements
 736       reference
 737       operator[](const difference_type& __n) const
 738       { return _M_current[__n]; }
 739
 740       __normal_iterator&
 741       operator+=(const difference_type& __n)
 742       { _M_current += __n; return *this; }
 743
 744       __normal_iterator
 745       operator+(const difference_type& __n) const
 746       { return __normal_iterator(_M_current + __n); }
 747
 748       __normal_iterator&
 749       operator-=(const difference_type& __n)
 750       { _M_current -= __n; return *this; }
 751
 752       __normal_iterator
 753       operator-(const difference_type& __n) const
 754       { return __normal_iterator(_M_current - __n); }
 755
 756       const _Iterator&
 757       base() const
 758       { return _M_current; }
 759     };
 760
 761   // Note: In what follows, the left- and right-hand-side iterators are
 762   // allowed to vary in types (conceptually in cv-qualification) so that
 763   // comparison between cv-qualified and non-cv-qualified iterators be
 764   // valid.  However, the greedy and unfriendly operators in std::rel_ops
 765   // will make overload resolution ambiguous (when in scope) if we don't
 766   // provide overloads whose operands are of the same type.  Can someone
 767   // remind me what generic programming is about? -- Gaby
 768
 769   // Forward iterator requirements
 770   template<typename _IteratorL, typename _IteratorR, typename _Container>
 771     inline bool
 772     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 773                const __normal_iterator<_IteratorR, _Container>& __rhs)
 774     { return __lhs.base() == __rhs.base(); }
 775
 776   template<typename _Iterator, typename _Container>
 777     inline bool
 778     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
 779                const __normal_iterator<_Iterator, _Container>& __rhs)
 780     { return __lhs.base() == __rhs.base(); }
 781
 782   template<typename _IteratorL, typename _IteratorR, typename _Container>
 783     inline bool
 784     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 785                const __normal_iterator<_IteratorR, _Container>& __rhs)
 786     { return __lhs.base() != __rhs.base(); }
 787
 788   template<typename _Iterator, typename _Container>
 789     inline bool
 790     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
 791                const __normal_iterator<_Iterator, _Container>& __rhs)
 792     { return __lhs.base() != __rhs.base(); }
 793
 794   // Random access iterator requirements
 795   template<typename _IteratorL, typename _IteratorR, typename _Container>
 796     inline bool
 797     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
 798               const __normal_iterator<_IteratorR, _Container>& __rhs)
 799     { return __lhs.base() < __rhs.base(); }
 800
 801   template<typename _Iterator, typename _Container>
 802     inline bool
 803     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
 804               const __normal_iterator<_Iterator, _Container>& __rhs)
 805     { return __lhs.base() < __rhs.base(); }
 806
 807   template<typename _IteratorL, typename _IteratorR, typename _Container>
 808     inline bool
 809     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 810               const __normal_iterator<_IteratorR, _Container>& __rhs)
 811     { return __lhs.base() > __rhs.base(); }
 812
 813   template<typename _Iterator, typename _Container>
 814     inline bool
 815     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
 816               const __normal_iterator<_Iterator, _Container>& __rhs)
 817     { return __lhs.base() > __rhs.base(); }
 818
 819   template<typename _IteratorL, typename _IteratorR, typename _Container>
 820     inline bool
 821     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 822                const __normal_iterator<_IteratorR, _Container>& __rhs)
 823     { return __lhs.base() <= __rhs.base(); }
 824
 825   template<typename _Iterator, typename _Container>
 826     inline bool
 827     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
 828                const __normal_iterator<_Iterator, _Container>& __rhs)
 829     { return __lhs.base() <= __rhs.base(); }
 830
 831   template<typename _IteratorL, typename _IteratorR, typename _Container>
 832     inline bool
 833     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 834                const __normal_iterator<_IteratorR, _Container>& __rhs)
 835     { return __lhs.base() >= __rhs.base(); }
 836
 837   template<typename _Iterator, typename _Container>
 838     inline bool
 839     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
 840                const __normal_iterator<_Iterator, _Container>& __rhs)
 841     { return __lhs.base() >= __rhs.base(); }
 842
 843   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 844   // According to the resolution of DR179 not only the various comparison
 845   // operators but also operator- must accept mixed iterator/const_iterator
 846   // parameters.
 847   template<typename _IteratorL, typename _IteratorR, typename _Container>
 848 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 849     // DR 685.
 850     inline auto
 851     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 852               const __normal_iterator<_IteratorR, _Container>& __rhs)
 853     -> decltype(__lhs.base() - __rhs.base())
 854 #else
 855     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
 856     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 857               const __normal_iterator<_IteratorR, _Container>& __rhs)
 858 #endif
 859     { return __lhs.base() - __rhs.base(); }
 860
 861   template<typename _Iterator, typename _Container>
 862     inline typename __normal_iterator<_Iterator, _Container>::difference_type
 863     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
 864               const __normal_iterator<_Iterator, _Container>& __rhs)
 865     { return __lhs.base() - __rhs.base(); }
 866
 867   template<typename _Iterator, typename _Container>
 868     inline __normal_iterator<_Iterator, _Container>
 869     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
 870               __n, const __normal_iterator<_Iterator, _Container>& __i)
 871     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 872
 873 _GLIBCXX_END_NAMESPACE
 874
 875 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 876
 877 _GLIBCXX_BEGIN_NAMESPACE(std)
 878
 879   /**
 880    * @addtogroup iterators
 881    * @{
 882    */
 883
 884   // 24.4.3  Move iterators
 885   /**
 886    *  Class template move_iterator is an iterator adapter with the same
 887    *  behavior as the underlying iterator except that its dereference
 888    *  operator implicitly converts the value returned by the underlying
 889    *  iterator's dereference operator to an rvalue reference.  Some
 890    *  generic algorithms can be called with move iterators to replace
 891    *  copying with moving.
 892    */
 893   template<typename _Iterator>
 894     class move_iterator
 895     {
 896     protected:
 897       _Iterator _M_current;
 898
 899       typedef iterator_traits<_Iterator>                __traits_type;
 900
 901     public:
 902       typedef _Iterator                                 iterator_type;
 903       typedef typename __traits_type::iterator_category iterator_category;
 904       typedef typename __traits_type::value_type        value_type;
 905       typedef typename __traits_type::difference_type   difference_type;
 906       // NB: DR 680.
 907       typedef _Iterator                                 pointer;
 908       typedef value_type&&                              reference;
 909
 910       move_iterator()
 911       : _M_current() { }
 912
 913       explicit
 914       move_iterator(iterator_type __i)
 915       : _M_current(__i) { }
 916
 917       template<typename _Iter>
 918         move_iterator(const move_iterator<_Iter>& __i)
 919         : _M_current(__i.base()) { }
 920
 921       iterator_type
 922       base() const
 923       { return _M_current; }
 924
 925       reference
 926       operator*() const
 927       { return std::move(*_M_current); }
 928
 929       pointer
 930       operator->() const
 931       { return _M_current; }
 932
 933       move_iterator&
 934       operator++()
 935       {
 936         ++_M_current;
 937         return *this;
 938       }
 939
 940       move_iterator
 941       operator++(int)
 942       {
 943         move_iterator __tmp = *this;
 944         ++_M_current;
 945         return __tmp;
 946       }
 947
 948       move_iterator&
 949       operator--()
 950       {
 951         --_M_current;
 952         return *this;
 953       }
 954
 955       move_iterator
 956       operator--(int)
 957       {
 958         move_iterator __tmp = *this;
 959         --_M_current;
 960         return __tmp;
 961       }
 962
 963       move_iterator
 964       operator+(difference_type __n) const
 965       { return move_iterator(_M_current + __n); }
 966
 967       move_iterator&
 968       operator+=(difference_type __n)
 969       {
 970         _M_current += __n;
 971         return *this;
 972       }
 973
 974       move_iterator
 975       operator-(difference_type __n) const
 976       { return move_iterator(_M_current - __n); }
 977
 978       move_iterator&
 979       operator-=(difference_type __n)
 980       {
 981         _M_current -= __n;
 982         return *this;
 983       }
 984
 985       reference
 986       operator[](difference_type __n) const
 987       { return std::move(_M_current[__n]); }
 988     };
 989
 990   template<typename _IteratorL, typename _IteratorR>
 991     inline bool
 992     operator==(const move_iterator<_IteratorL>& __x,
 993                const move_iterator<_IteratorR>& __y)
 994     { return __x.base() == __y.base(); }
 995
 996   template<typename _IteratorL, typename _IteratorR>
 997     inline bool
 998     operator!=(const move_iterator<_IteratorL>& __x,
 999                const move_iterator<_IteratorR>& __y)
1000     { return !(__x == __y); }
1001
1002   template<typename _IteratorL, typename _IteratorR>
1003     inline bool
1004     operator<(const move_iterator<_IteratorL>& __x,
1005               const move_iterator<_IteratorR>& __y)
1006     { return __x.base() < __y.base(); }
1007
1008   template<typename _IteratorL, typename _IteratorR>
1009     inline bool
1010     operator<=(const move_iterator<_IteratorL>& __x,
1011                const move_iterator<_IteratorR>& __y)
1012     { return !(__y < __x); }
1013
1014   template<typename _IteratorL, typename _IteratorR>
1015     inline bool
1016     operator>(const move_iterator<_IteratorL>& __x,
1017               const move_iterator<_IteratorR>& __y)
1018     { return __y < __x; }
1019
1020   template<typename _IteratorL, typename _IteratorR>
1021     inline bool
1022     operator>=(const move_iterator<_IteratorL>& __x,
1023                const move_iterator<_IteratorR>& __y)
1024     { return !(__x < __y); }
1025
1026   // DR 685.
1027   template<typename _IteratorL, typename _IteratorR>
1028     inline auto
1029     operator-(const move_iterator<_IteratorL>& __x,
1030               const move_iterator<_IteratorR>& __y)
1031     -> decltype(__x.base() - __y.base())
1032     { return __x.base() - __y.base(); }
1033
1034   template<typename _Iterator>
1035     inline move_iterator<_Iterator>
1036     operator+(typename move_iterator<_Iterator>::difference_type __n,
1037               const move_iterator<_Iterator>& __x)
1038     { return __x + __n; }
1039
1040   template<typename _Iterator>
1041     inline move_iterator<_Iterator>
1042     make_move_iterator(const _Iterator& __i)
1043     { return move_iterator<_Iterator>(__i); }
1044
1045   // @} group iterators
1046
1047 _GLIBCXX_END_NAMESPACE
1048
1049 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1050 #else
1051 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1052 #endif // __GXX_EXPERIMENTAL_CXX0X__
1053
1054 #endif