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 #if __cplusplus < 201103L
 328     inline typename reverse_iterator<_Iterator>::difference_type
 329     operator-(const reverse_iterator<_Iterator>& __x,
 330               const reverse_iterator<_Iterator>& __y)
 331 #else
 332     inline auto
 333     operator-(const reverse_iterator<_Iterator>& __x,
 334               const reverse_iterator<_Iterator>& __y)
 335     -> decltype(__x.base() - __y.base())
 336 #endif
 337     { return __y.base() - __x.base(); }
 338
 339   template<typename _Iterator>
 340     inline reverse_iterator<_Iterator>
 341     operator+(typename reverse_iterator<_Iterator>::difference_type __n,
 342               const reverse_iterator<_Iterator>& __x)
 343     { return reverse_iterator<_Iterator>(__x.base() - __n); }
 344
 345   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 346   // DR 280. Comparison of reverse_iterator to const reverse_iterator.
 347   template<typename _IteratorL, typename _IteratorR>
 348     inline bool
 349     operator==(const reverse_iterator<_IteratorL>& __x,
 350                const reverse_iterator<_IteratorR>& __y)
 351     { return __x.base() == __y.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 __y.base() < __x.base(); }
 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 !(__x == __y); }
 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 !(__y < __x); }
 376
 377   template<typename _IteratorL, typename _IteratorR>
 378     inline bool
 379     operator>=(const reverse_iterator<_IteratorL>& __x,
 380                const reverse_iterator<_IteratorR>& __y)
 381     { return !(__x < __y); }
 382
 383   template<typename _IteratorL, typename _IteratorR>
 384 #if __cplusplus >= 201103L
 385     // DR 685.
 386     inline auto
 387     operator-(const reverse_iterator<_IteratorL>& __x,
 388               const reverse_iterator<_IteratorR>& __y)
 389     -> decltype(__y.base() - __x.base())
 390 #else
 391     inline typename reverse_iterator<_IteratorL>::difference_type
 392     operator-(const reverse_iterator<_IteratorL>& __x,
 393               const reverse_iterator<_IteratorR>& __y)
 394 #endif
 395     { return __y.base() - __x.base(); }
 396   //@}
 397
 398 #if __cplusplus > 201103L
 399 #define __cpp_lib_make_reverse_iterator 201402
 400
 401   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 402   // DR 2285. make_reverse_iterator
 403   /// Generator function for reverse_iterator.
 404   template<typename _Iterator>
 405     inline reverse_iterator<_Iterator>
 406     make_reverse_iterator(_Iterator __i)
 407     { return reverse_iterator<_Iterator>(__i); }
 408 #endif
 409
 410   // 24.4.2.2.1 back_insert_iterator
 411   /**
 412    *  @brief  Turns assignment into insertion.
 413    *
 414    *  These are output iterators, constructed from a container-of-T.
 415    *  Assigning a T to the iterator appends it to the container using
 416    *  push_back.
 417    *
 418    *  Tip:  Using the back_inserter function to create these iterators can
 419    *  save typing.
 420   */
 421   template<typename _Container>
 422     class back_insert_iterator
 423     : public iterator<output_iterator_tag, void, void, void, void>
 424     {
 425     protected:
 426       _Container* container;
 427
 428     public:
 429       /// A nested typedef for the type of whatever container you used.
 430       typedef _Container          container_type;
 431
 432       /// The only way to create this %iterator is with a container.
 433       explicit
 434       back_insert_iterator(_Container& __x) : container(&__x) { }
 435
 436       /**
 437        *  @param  __value  An instance of whatever type
 438        *                 container_type::const_reference is; presumably a
 439        *                 reference-to-const T for container<T>.
 440        *  @return  This %iterator, for chained operations.
 441        *
 442        *  This kind of %iterator doesn't really have a @a position in the
 443        *  container (you can think of the position as being permanently at
 444        *  the end, if you like).  Assigning a value to the %iterator will
 445        *  always append the value to the end of the container.
 446       */
 447 #if __cplusplus < 201103L
 448       back_insert_iterator&
 449       operator=(typename _Container::const_reference __value)
 450       {
 451         container->push_back(__value);
 452         return *this;
 453       }
 454 #else
 455       back_insert_iterator&
 456       operator=(const typename _Container::value_type& __value)
 457       {
 458         container->push_back(__value);
 459         return *this;
 460       }
 461
 462       back_insert_iterator&
 463       operator=(typename _Container::value_type&& __value)
 464       {
 465         container->push_back(std::move(__value));
 466         return *this;
 467       }
 468 #endif
 469
 470       /// Simply returns *this.
 471       back_insert_iterator&
 472       operator*()
 473       { return *this; }
 474
 475       /// Simply returns *this.  (This %iterator does not @a move.)
 476       back_insert_iterator&
 477       operator++()
 478       { return *this; }
 479
 480       /// Simply returns *this.  (This %iterator does not @a move.)
 481       back_insert_iterator
 482       operator++(int)
 483       { return *this; }
 484     };
 485
 486   /**
 487    *  @param  __x  A container of arbitrary type.
 488    *  @return  An instance of back_insert_iterator working on @p __x.
 489    *
 490    *  This wrapper function helps in creating back_insert_iterator instances.
 491    *  Typing the name of the %iterator requires knowing the precise full
 492    *  type of the container, which can be tedious and impedes generic
 493    *  programming.  Using this function lets you take advantage of automatic
 494    *  template parameter deduction, making the compiler match the correct
 495    *  types for you.
 496   */
 497   template<typename _Container>
 498     inline back_insert_iterator<_Container>
 499     back_inserter(_Container& __x)
 500     { return back_insert_iterator<_Container>(__x); }
 501
 502   /**
 503    *  @brief  Turns assignment into insertion.
 504    *
 505    *  These are output iterators, constructed from a container-of-T.
 506    *  Assigning a T to the iterator prepends it to the container using
 507    *  push_front.
 508    *
 509    *  Tip:  Using the front_inserter function to create these iterators can
 510    *  save typing.
 511   */
 512   template<typename _Container>
 513     class front_insert_iterator
 514     : public iterator<output_iterator_tag, void, void, void, void>
 515     {
 516     protected:
 517       _Container* container;
 518
 519     public:
 520       /// A nested typedef for the type of whatever container you used.
 521       typedef _Container          container_type;
 522
 523       /// The only way to create this %iterator is with a container.
 524       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 525
 526       /**
 527        *  @param  __value  An instance of whatever type
 528        *                 container_type::const_reference is; presumably a
 529        *                 reference-to-const T for container<T>.
 530        *  @return  This %iterator, for chained operations.
 531        *
 532        *  This kind of %iterator doesn't really have a @a position in the
 533        *  container (you can think of the position as being permanently at
 534        *  the front, if you like).  Assigning a value to the %iterator will
 535        *  always prepend the value to the front of the container.
 536       */
 537 #if __cplusplus < 201103L
 538       front_insert_iterator&
 539       operator=(typename _Container::const_reference __value)
 540       {
 541         container->push_front(__value);
 542         return *this;
 543       }
 544 #else
 545       front_insert_iterator&
 546       operator=(const typename _Container::value_type& __value)
 547       {
 548         container->push_front(__value);
 549         return *this;
 550       }
 551
 552       front_insert_iterator&
 553       operator=(typename _Container::value_type&& __value)
 554       {
 555         container->push_front(std::move(__value));
 556         return *this;
 557       }
 558 #endif
 559
 560       /// Simply returns *this.
 561       front_insert_iterator&
 562       operator*()
 563       { return *this; }
 564
 565       /// Simply returns *this.  (This %iterator does not @a move.)
 566       front_insert_iterator&
 567       operator++()
 568       { return *this; }
 569
 570       /// Simply returns *this.  (This %iterator does not @a move.)
 571       front_insert_iterator
 572       operator++(int)
 573       { return *this; }
 574     };
 575
 576   /**
 577    *  @param  __x  A container of arbitrary type.
 578    *  @return  An instance of front_insert_iterator working on @p x.
 579    *
 580    *  This wrapper function helps in creating front_insert_iterator instances.
 581    *  Typing the name of the %iterator requires knowing the precise full
 582    *  type of the container, which can be tedious and impedes generic
 583    *  programming.  Using this function lets you take advantage of automatic
 584    *  template parameter deduction, making the compiler match the correct
 585    *  types for you.
 586   */
 587   template<typename _Container>
 588     inline front_insert_iterator<_Container>
 589     front_inserter(_Container& __x)
 590     { return front_insert_iterator<_Container>(__x); }
 591
 592   /**
 593    *  @brief  Turns assignment into insertion.
 594    *
 595    *  These are output iterators, constructed from a container-of-T.
 596    *  Assigning a T to the iterator inserts it in the container at the
 597    *  %iterator's position, rather than overwriting the value at that
 598    *  position.
 599    *
 600    *  (Sequences will actually insert a @e copy of the value before the
 601    *  %iterator's position.)
 602    *
 603    *  Tip:  Using the inserter function to create these iterators can
 604    *  save typing.
 605   */
 606   template<typename _Container>
 607     class insert_iterator
 608     : public iterator<output_iterator_tag, void, void, void, void>
 609     {
 610     protected:
 611       _Container* container;
 612       typename _Container::iterator iter;
 613
 614     public:
 615       /// A nested typedef for the type of whatever container you used.
 616       typedef _Container          container_type;
 617
 618       /**
 619        *  The only way to create this %iterator is with a container and an
 620        *  initial position (a normal %iterator into the container).
 621       */
 622       insert_iterator(_Container& __x, typename _Container::iterator __i)
 623       : container(&__x), iter(__i) {}
 624
 625       /**
 626        *  @param  __value  An instance of whatever type
 627        *                 container_type::const_reference is; presumably a
 628        *                 reference-to-const T for container<T>.
 629        *  @return  This %iterator, for chained operations.
 630        *
 631        *  This kind of %iterator maintains its own position in the
 632        *  container.  Assigning a value to the %iterator will insert the
 633        *  value into the container at the place before the %iterator.
 634        *
 635        *  The position is maintained such that subsequent assignments will
 636        *  insert values immediately after one another.  For example,
 637        *  @code
 638        *     // vector v contains A and Z
 639        *
 640        *     insert_iterator i (v, ++v.begin());
 641        *     i = 1;
 642        *     i = 2;
 643        *     i = 3;
 644        *
 645        *     // vector v contains A, 1, 2, 3, and Z
 646        *  @endcode
 647       */
 648 #if __cplusplus < 201103L
 649       insert_iterator&
 650       operator=(typename _Container::const_reference __value)
 651       {
 652         iter = container->insert(iter, __value);
 653         ++iter;
 654         return *this;
 655       }
 656 #else
 657       insert_iterator&
 658       operator=(const typename _Container::value_type& __value)
 659       {
 660         iter = container->insert(iter, __value);
 661         ++iter;
 662         return *this;
 663       }
 664
 665       insert_iterator&
 666       operator=(typename _Container::value_type&& __value)
 667       {
 668         iter = container->insert(iter, std::move(__value));
 669         ++iter;
 670         return *this;
 671       }
 672 #endif
 673
 674       /// Simply returns *this.
 675       insert_iterator&
 676       operator*()
 677       { return *this; }
 678
 679       /// Simply returns *this.  (This %iterator does not @a move.)
 680       insert_iterator&
 681       operator++()
 682       { return *this; }
 683
 684       /// Simply returns *this.  (This %iterator does not @a move.)
 685       insert_iterator&
 686       operator++(int)
 687       { return *this; }
 688     };
 689
 690   /**
 691    *  @param __x  A container of arbitrary type.
 692    *  @return  An instance of insert_iterator working on @p __x.
 693    *
 694    *  This wrapper function helps in creating insert_iterator instances.
 695    *  Typing the name of the %iterator requires knowing the precise full
 696    *  type of the container, which can be tedious and impedes generic
 697    *  programming.  Using this function lets you take advantage of automatic
 698    *  template parameter deduction, making the compiler match the correct
 699    *  types for you.
 700   */
 701   template<typename _Container, typename _Iterator>
 702     inline insert_iterator<_Container>
 703     inserter(_Container& __x, _Iterator __i)
 704     {
 705       return insert_iterator<_Container>(__x,
 706                                          typename _Container::iterator(__i));
 707     }
 708
 709   // @} group iterators
 710
 711 _GLIBCXX_END_NAMESPACE_VERSION
 712 } // namespace
 713
 714 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
 715 {
 716 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 717
 718   // This iterator adapter is @a normal in the sense that it does not
 719   // change the semantics of any of the operators of its iterator
 720   // parameter.  Its primary purpose is to convert an iterator that is
 721   // not a class, e.g. a pointer, into an iterator that is a class.
 722   // The _Container parameter exists solely so that different containers
 723   // using this template can instantiate different types, even if the
 724   // _Iterator parameter is the same.
 725   using std::iterator_traits;
 726   using std::iterator;
 727   template<typename _Iterator, typename _Container>
 728     class __normal_iterator
 729     {
 730     protected:
 731       _Iterator _M_current;
 732
 733       typedef iterator_traits<_Iterator>                __traits_type;
 734
 735     public:
 736       typedef _Iterator                                 iterator_type;
 737       typedef typename __traits_type::iterator_category iterator_category;
 738       typedef typename __traits_type::value_type        value_type;
 739       typedef typename __traits_type::difference_type   difference_type;
 740       typedef typename __traits_type::reference         reference;
 741       typedef typename __traits_type::pointer           pointer;
 742
 743       _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
 744       : _M_current(_Iterator()) { }
 745
 746       explicit
 747       __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
 748       : _M_current(__i) { }
 749
 750       // Allow iterator to const_iterator conversion
 751       template<typename _Iter>
 752         __normal_iterator(const __normal_iterator<_Iter,
 753                           typename __enable_if<
 754                (std::__are_same<_Iter, typename _Container::pointer>::__value),
 755                       _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
 756         : _M_current(__i.base()) { }
 757
 758       // Forward iterator requirements
 759       reference
 760       operator*() const _GLIBCXX_NOEXCEPT
 761       { return *_M_current; }
 762
 763       pointer
 764       operator->() const _GLIBCXX_NOEXCEPT
 765       { return _M_current; }
 766
 767       __normal_iterator&
 768       operator++() _GLIBCXX_NOEXCEPT
 769       {
 770         ++_M_current;
 771         return *this;
 772       }
 773
 774       __normal_iterator
 775       operator++(int) _GLIBCXX_NOEXCEPT
 776       { return __normal_iterator(_M_current++); }
 777
 778       // Bidirectional iterator requirements
 779       __normal_iterator&
 780       operator--() _GLIBCXX_NOEXCEPT
 781       {
 782         --_M_current;
 783         return *this;
 784       }
 785
 786       __normal_iterator
 787       operator--(int) _GLIBCXX_NOEXCEPT
 788       { return __normal_iterator(_M_current--); }
 789
 790       // Random access iterator requirements
 791       reference
 792       operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
 793       { return _M_current[__n]; }
 794
 795       __normal_iterator&
 796       operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
 797       { _M_current += __n; return *this; }
 798
 799       __normal_iterator
 800       operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
 801       { return __normal_iterator(_M_current + __n); }
 802
 803       __normal_iterator&
 804       operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
 805       { _M_current -= __n; return *this; }
 806
 807       __normal_iterator
 808       operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
 809       { return __normal_iterator(_M_current - __n); }
 810
 811       const _Iterator&
 812       base() const _GLIBCXX_NOEXCEPT
 813       { return _M_current; }
 814     };
 815
 816   // Note: In what follows, the left- and right-hand-side iterators are
 817   // allowed to vary in types (conceptually in cv-qualification) so that
 818   // comparison between cv-qualified and non-cv-qualified iterators be
 819   // valid.  However, the greedy and unfriendly operators in std::rel_ops
 820   // will make overload resolution ambiguous (when in scope) if we don't
 821   // provide overloads whose operands are of the same type.  Can someone
 822   // remind me what generic programming is about? -- Gaby
 823
 824   // Forward iterator requirements
 825   template<typename _IteratorL, typename _IteratorR, typename _Container>
 826     inline bool
 827     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 828                const __normal_iterator<_IteratorR, _Container>& __rhs)
 829     _GLIBCXX_NOEXCEPT
 830     { return __lhs.base() == __rhs.base(); }
 831
 832   template<typename _Iterator, typename _Container>
 833     inline bool
 834     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
 835                const __normal_iterator<_Iterator, _Container>& __rhs)
 836     _GLIBCXX_NOEXCEPT
 837     { return __lhs.base() == __rhs.base(); }
 838
 839   template<typename _IteratorL, typename _IteratorR, typename _Container>
 840     inline bool
 841     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 842                const __normal_iterator<_IteratorR, _Container>& __rhs)
 843     _GLIBCXX_NOEXCEPT
 844     { return __lhs.base() != __rhs.base(); }
 845
 846   template<typename _Iterator, typename _Container>
 847     inline bool
 848     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
 849                const __normal_iterator<_Iterator, _Container>& __rhs)
 850     _GLIBCXX_NOEXCEPT
 851     { return __lhs.base() != __rhs.base(); }
 852
 853   // Random access iterator requirements
 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     _GLIBCXX_NOEXCEPT
 859     { return __lhs.base() < __rhs.base(); }
 860
 861   template<typename _Iterator, typename _Container>
 862     inline bool
 863     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
 864               const __normal_iterator<_Iterator, _Container>& __rhs)
 865     _GLIBCXX_NOEXCEPT
 866     { return __lhs.base() < __rhs.base(); }
 867
 868   template<typename _IteratorL, typename _IteratorR, typename _Container>
 869     inline bool
 870     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 871               const __normal_iterator<_IteratorR, _Container>& __rhs)
 872     _GLIBCXX_NOEXCEPT
 873     { return __lhs.base() > __rhs.base(); }
 874
 875   template<typename _Iterator, typename _Container>
 876     inline bool
 877     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
 878               const __normal_iterator<_Iterator, _Container>& __rhs)
 879     _GLIBCXX_NOEXCEPT
 880     { return __lhs.base() > __rhs.base(); }
 881
 882   template<typename _IteratorL, typename _IteratorR, typename _Container>
 883     inline bool
 884     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 885                const __normal_iterator<_IteratorR, _Container>& __rhs)
 886     _GLIBCXX_NOEXCEPT
 887     { return __lhs.base() <= __rhs.base(); }
 888
 889   template<typename _Iterator, typename _Container>
 890     inline bool
 891     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
 892                const __normal_iterator<_Iterator, _Container>& __rhs)
 893     _GLIBCXX_NOEXCEPT
 894     { return __lhs.base() <= __rhs.base(); }
 895
 896   template<typename _IteratorL, typename _IteratorR, typename _Container>
 897     inline bool
 898     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 899                const __normal_iterator<_IteratorR, _Container>& __rhs)
 900     _GLIBCXX_NOEXCEPT
 901     { return __lhs.base() >= __rhs.base(); }
 902
 903   template<typename _Iterator, typename _Container>
 904     inline bool
 905     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
 906                const __normal_iterator<_Iterator, _Container>& __rhs)
 907     _GLIBCXX_NOEXCEPT
 908     { return __lhs.base() >= __rhs.base(); }
 909
 910   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 911   // According to the resolution of DR179 not only the various comparison
 912   // operators but also operator- must accept mixed iterator/const_iterator
 913   // parameters.
 914   template<typename _IteratorL, typename _IteratorR, typename _Container>
 915 #if __cplusplus >= 201103L
 916     // DR 685.
 917     inline auto
 918     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 919               const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
 920     -> decltype(__lhs.base() - __rhs.base())
 921 #else
 922     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
 923     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 924               const __normal_iterator<_IteratorR, _Container>& __rhs)
 925 #endif
 926     { return __lhs.base() - __rhs.base(); }
 927
 928   template<typename _Iterator, typename _Container>
 929     inline typename __normal_iterator<_Iterator, _Container>::difference_type
 930     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
 931               const __normal_iterator<_Iterator, _Container>& __rhs)
 932     _GLIBCXX_NOEXCEPT
 933     { return __lhs.base() - __rhs.base(); }
 934
 935   template<typename _Iterator, typename _Container>
 936     inline __normal_iterator<_Iterator, _Container>
 937     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
 938               __n, const __normal_iterator<_Iterator, _Container>& __i)
 939     _GLIBCXX_NOEXCEPT
 940     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 941
 942 _GLIBCXX_END_NAMESPACE_VERSION
 943 } // namespace
 944
 945 #if __cplusplus >= 201103L
 946
 947 namespace std _GLIBCXX_VISIBILITY(default)
 948 {
 949 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 950
 951   /**
 952    * @addtogroup iterators
 953    * @{
 954    */
 955
 956   // 24.4.3  Move iterators
 957   /**
 958    *  Class template move_iterator is an iterator adapter with the same
 959    *  behavior as the underlying iterator except that its dereference
 960    *  operator implicitly converts the value returned by the underlying
 961    *  iterator's dereference operator to an rvalue reference.  Some
 962    *  generic algorithms can be called with move iterators to replace
 963    *  copying with moving.
 964    */
 965   template<typename _Iterator>
 966     class move_iterator
 967     {
 968     protected:
 969       _Iterator _M_current;
 970
 971       typedef iterator_traits<_Iterator>                __traits_type;
 972       typedef typename __traits_type::reference         __base_ref;
 973
 974     public:
 975       typedef _Iterator                                 iterator_type;
 976       typedef typename __traits_type::iterator_category iterator_category;
 977       typedef typename __traits_type::value_type        value_type;
 978       typedef typename __traits_type::difference_type   difference_type;
 979       // NB: DR 680.
 980       typedef _Iterator                                 pointer;
 981       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 982       // 2106. move_iterator wrapping iterators returning prvalues
 983       typedef typename conditional<is_reference<__base_ref>::value,
 984                          typename remove_reference<__base_ref>::type&&,
 985                          __base_ref>::type              reference;
 986
 987       move_iterator()
 988       : _M_current() { }
 989
 990       explicit
 991       move_iterator(iterator_type __i)
 992       : _M_current(__i) { }
 993
 994       template<typename _Iter>
 995         move_iterator(const move_iterator<_Iter>& __i)
 996         : _M_current(__i.base()) { }
 997
 998       iterator_type
 999       base() const
1000       { return _M_current; }
1001
1002       reference
1003       operator*() const
1004       { return static_cast<reference>(*_M_current); }
1005
1006       pointer
1007       operator->() const
1008       { return _M_current; }
1009
1010       move_iterator&
1011       operator++()
1012       {
1013         ++_M_current;
1014         return *this;
1015       }
1016
1017       move_iterator
1018       operator++(int)
1019       {
1020         move_iterator __tmp = *this;
1021         ++_M_current;
1022         return __tmp;
1023       }
1024
1025       move_iterator&
1026       operator--()
1027       {
1028         --_M_current;
1029         return *this;
1030       }
1031
1032       move_iterator
1033       operator--(int)
1034       {
1035         move_iterator __tmp = *this;
1036         --_M_current;
1037         return __tmp;
1038       }
1039
1040       move_iterator
1041       operator+(difference_type __n) const
1042       { return move_iterator(_M_current + __n); }
1043
1044       move_iterator&
1045       operator+=(difference_type __n)
1046       {
1047         _M_current += __n;
1048         return *this;
1049       }
1050
1051       move_iterator
1052       operator-(difference_type __n) const
1053       { return move_iterator(_M_current - __n); }
1054
1055       move_iterator&
1056       operator-=(difference_type __n)
1057       {
1058         _M_current -= __n;
1059         return *this;
1060       }
1061
1062       reference
1063       operator[](difference_type __n) const
1064       { return std::move(_M_current[__n]); }
1065     };
1066
1067   // Note: See __normal_iterator operators note from Gaby to understand
1068   // why there are always 2 versions for most of the move_iterator
1069   // operators.
1070   template<typename _IteratorL, typename _IteratorR>
1071     inline bool
1072     operator==(const move_iterator<_IteratorL>& __x,
1073                const move_iterator<_IteratorR>& __y)
1074     { return __x.base() == __y.base(); }
1075
1076   template<typename _Iterator>
1077     inline bool
1078     operator==(const move_iterator<_Iterator>& __x,
1079                const move_iterator<_Iterator>& __y)
1080     { return __x.base() == __y.base(); }
1081
1082   template<typename _IteratorL, typename _IteratorR>
1083     inline bool
1084     operator!=(const move_iterator<_IteratorL>& __x,
1085                const move_iterator<_IteratorR>& __y)
1086     { return !(__x == __y); }
1087
1088   template<typename _Iterator>
1089     inline bool
1090     operator!=(const move_iterator<_Iterator>& __x,
1091                const move_iterator<_Iterator>& __y)
1092     { return !(__x == __y); }
1093
1094   template<typename _IteratorL, typename _IteratorR>
1095     inline bool
1096     operator<(const move_iterator<_IteratorL>& __x,
1097               const move_iterator<_IteratorR>& __y)
1098     { return __x.base() < __y.base(); }
1099
1100   template<typename _Iterator>
1101     inline bool
1102     operator<(const move_iterator<_Iterator>& __x,
1103               const move_iterator<_Iterator>& __y)
1104     { return __x.base() < __y.base(); }
1105
1106   template<typename _IteratorL, typename _IteratorR>
1107     inline bool
1108     operator<=(const move_iterator<_IteratorL>& __x,
1109                const move_iterator<_IteratorR>& __y)
1110     { return !(__y < __x); }
1111
1112   template<typename _Iterator>
1113     inline bool
1114     operator<=(const move_iterator<_Iterator>& __x,
1115                const move_iterator<_Iterator>& __y)
1116     { return !(__y < __x); }
1117
1118   template<typename _IteratorL, typename _IteratorR>
1119     inline bool
1120     operator>(const move_iterator<_IteratorL>& __x,
1121               const move_iterator<_IteratorR>& __y)
1122     { return __y < __x; }
1123
1124   template<typename _Iterator>
1125     inline bool
1126     operator>(const move_iterator<_Iterator>& __x,
1127               const move_iterator<_Iterator>& __y)
1128     { return __y < __x; }
1129
1130   template<typename _IteratorL, typename _IteratorR>
1131     inline bool
1132     operator>=(const move_iterator<_IteratorL>& __x,
1133                const move_iterator<_IteratorR>& __y)
1134     { return !(__x < __y); }
1135
1136   template<typename _Iterator>
1137     inline bool
1138     operator>=(const move_iterator<_Iterator>& __x,
1139                const move_iterator<_Iterator>& __y)
1140     { return !(__x < __y); }
1141
1142   // DR 685.
1143   template<typename _IteratorL, typename _IteratorR>
1144     inline auto
1145     operator-(const move_iterator<_IteratorL>& __x,
1146               const move_iterator<_IteratorR>& __y)
1147     -> decltype(__x.base() - __y.base())
1148     { return __x.base() - __y.base(); }
1149
1150   template<typename _Iterator>
1151     inline auto
1152     operator-(const move_iterator<_Iterator>& __x,
1153               const move_iterator<_Iterator>& __y)
1154     -> decltype(__x.base() - __y.base())
1155     { return __x.base() - __y.base(); }
1156
1157   template<typename _Iterator>
1158     inline move_iterator<_Iterator>
1159     operator+(typename move_iterator<_Iterator>::difference_type __n,
1160               const move_iterator<_Iterator>& __x)
1161     { return __x + __n; }
1162
1163   template<typename _Iterator>
1164     inline move_iterator<_Iterator>
1165     make_move_iterator(_Iterator __i)
1166     { return move_iterator<_Iterator>(__i); }
1167
1168   template<typename _Iterator, typename _ReturnType
1169     = typename conditional<__move_if_noexcept_cond
1170       <typename iterator_traits<_Iterator>::value_type>::value,
1171                 _Iterator, move_iterator<_Iterator>>::type>
1172     inline _ReturnType
1173     __make_move_if_noexcept_iterator(_Iterator __i)
1174     { return _ReturnType(__i); }
1175
1176   // @} group iterators
1177
1178 _GLIBCXX_END_NAMESPACE_VERSION
1179 } // namespace
1180
1181 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1182 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1183   std::__make_move_if_noexcept_iterator(_Iter)
1184 #else
1185 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1186 #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1187 #endif // C++11
1188
1189 #endif