l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.8/include/bits/stl_iterator.h

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