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

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