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