libstdc++-v3/include/bits/stl_iterator.h

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