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

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