contrib/gcc-5.0/libstdc++-v3/include/bits/stl_iterator.h

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