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/stl_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     inline typename reverse_iterator<_IteratorL>::difference_type
 369     operator-(const reverse_iterator<_IteratorL>& __x,
 370               const reverse_iterator<_IteratorR>& __y)
 371     { return __y.base() - __x.base(); }
 372   //@}
 373
 374   // 24.4.2.2.1 back_insert_iterator
 375   /**
 376    *  @brief  Turns assignment into insertion.
 377    *
 378    *  These are output iterators, constructed from a container-of-T.
 379    *  Assigning a T to the iterator appends it to the container using
 380    *  push_back.
 381    *
 382    *  Tip:  Using the back_inserter function to create these iterators can
 383    *  save typing.
 384   */
 385   template<typename _Container>
 386     class back_insert_iterator
 387     : public iterator<output_iterator_tag, void, void, void, void>
 388     {
 389     protected:
 390       _Container* container;
 391
 392     public:
 393       /// A nested typedef for the type of whatever container you used.
 394       typedef _Container          container_type;
 395
 396       /// The only way to create this %iterator is with a container.
 397       explicit
 398       back_insert_iterator(_Container& __x) : container(&__x) { }
 399
 400       /**
 401        *  @param  value  An instance of whatever type
 402        *                 container_type::const_reference is; presumably a
 403        *                 reference-to-const T for container<T>.
 404        *  @return  This %iterator, for chained operations.
 405        *
 406        *  This kind of %iterator doesn't really have a "position" in the
 407        *  container (you can think of the position as being permanently at
 408        *  the end, if you like).  Assigning a value to the %iterator will
 409        *  always append the value to the end of the container.
 410       */
 411       back_insert_iterator&
 412       operator=(typename _Container::const_reference __value)
 413       {
 414         container->push_back(__value);
 415         return *this;
 416       }
 417
 418 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 419       back_insert_iterator&
 420       operator=(typename _Container::value_type&& __value)
 421       {
 422         container->push_back(std::move(__value));
 423         return *this;
 424       }
 425 #endif
 426
 427       /// Simply returns *this.
 428       back_insert_iterator&
 429       operator*()
 430       { return *this; }
 431
 432       /// Simply returns *this.  (This %iterator does not "move".)
 433       back_insert_iterator&
 434       operator++()
 435       { return *this; }
 436
 437       /// Simply returns *this.  (This %iterator does not "move".)
 438       back_insert_iterator
 439       operator++(int)
 440       { return *this; }
 441     };
 442
 443   /**
 444    *  @param  x  A container of arbitrary type.
 445    *  @return  An instance of back_insert_iterator working on @p x.
 446    *
 447    *  This wrapper function helps in creating back_insert_iterator instances.
 448    *  Typing the name of the %iterator requires knowing the precise full
 449    *  type of the container, which can be tedious and impedes generic
 450    *  programming.  Using this function lets you take advantage of automatic
 451    *  template parameter deduction, making the compiler match the correct
 452    *  types for you.
 453   */
 454   template<typename _Container>
 455     inline back_insert_iterator<_Container>
 456     back_inserter(_Container& __x)
 457     { return back_insert_iterator<_Container>(__x); }
 458
 459   /**
 460    *  @brief  Turns assignment into insertion.
 461    *
 462    *  These are output iterators, constructed from a container-of-T.
 463    *  Assigning a T to the iterator prepends it to the container using
 464    *  push_front.
 465    *
 466    *  Tip:  Using the front_inserter function to create these iterators can
 467    *  save typing.
 468   */
 469   template<typename _Container>
 470     class front_insert_iterator
 471     : public iterator<output_iterator_tag, void, void, void, void>
 472     {
 473     protected:
 474       _Container* container;
 475
 476     public:
 477       /// A nested typedef for the type of whatever container you used.
 478       typedef _Container          container_type;
 479
 480       /// The only way to create this %iterator is with a container.
 481       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 482
 483       /**
 484        *  @param  value  An instance of whatever type
 485        *                 container_type::const_reference is; presumably a
 486        *                 reference-to-const T for container<T>.
 487        *  @return  This %iterator, for chained operations.
 488        *
 489        *  This kind of %iterator doesn't really have a "position" in the
 490        *  container (you can think of the position as being permanently at
 491        *  the front, if you like).  Assigning a value to the %iterator will
 492        *  always prepend the value to the front of the container.
 493       */
 494       front_insert_iterator&
 495       operator=(typename _Container::const_reference __value)
 496       {
 497         container->push_front(__value);
 498         return *this;
 499       }
 500
 501 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 502       front_insert_iterator&
 503       operator=(typename _Container::value_type&& __value)
 504       {
 505         container->push_front(std::move(__value));
 506         return *this;
 507       }
 508 #endif
 509
 510       /// Simply returns *this.
 511       front_insert_iterator&
 512       operator*()
 513       { return *this; }
 514
 515       /// Simply returns *this.  (This %iterator does not "move".)
 516       front_insert_iterator&
 517       operator++()
 518       { return *this; }
 519
 520       /// Simply returns *this.  (This %iterator does not "move".)
 521       front_insert_iterator
 522       operator++(int)
 523       { return *this; }
 524     };
 525
 526   /**
 527    *  @param  x  A container of arbitrary type.
 528    *  @return  An instance of front_insert_iterator working on @p x.
 529    *
 530    *  This wrapper function helps in creating front_insert_iterator instances.
 531    *  Typing the name of the %iterator requires knowing the precise full
 532    *  type of the container, which can be tedious and impedes generic
 533    *  programming.  Using this function lets you take advantage of automatic
 534    *  template parameter deduction, making the compiler match the correct
 535    *  types for you.
 536   */
 537   template<typename _Container>
 538     inline front_insert_iterator<_Container>
 539     front_inserter(_Container& __x)
 540     { return front_insert_iterator<_Container>(__x); }
 541
 542   /**
 543    *  @brief  Turns assignment into insertion.
 544    *
 545    *  These are output iterators, constructed from a container-of-T.
 546    *  Assigning a T to the iterator inserts it in the container at the
 547    *  %iterator's position, rather than overwriting the value at that
 548    *  position.
 549    *
 550    *  (Sequences will actually insert a @e copy of the value before the
 551    *  %iterator's position.)
 552    *
 553    *  Tip:  Using the inserter function to create these iterators can
 554    *  save typing.
 555   */
 556   template<typename _Container>
 557     class insert_iterator
 558     : public iterator<output_iterator_tag, void, void, void, void>
 559     {
 560     protected:
 561       _Container* container;
 562       typename _Container::iterator iter;
 563
 564     public:
 565       /// A nested typedef for the type of whatever container you used.
 566       typedef _Container          container_type;
 567
 568       /**
 569        *  The only way to create this %iterator is with a container and an
 570        *  initial position (a normal %iterator into the container).
 571       */
 572       insert_iterator(_Container& __x, typename _Container::iterator __i)
 573       : container(&__x), iter(__i) {}
 574
 575       /**
 576        *  @param  value  An instance of whatever type
 577        *                 container_type::const_reference is; presumably a
 578        *                 reference-to-const T for container<T>.
 579        *  @return  This %iterator, for chained operations.
 580        *
 581        *  This kind of %iterator maintains its own position in the
 582        *  container.  Assigning a value to the %iterator will insert the
 583        *  value into the container at the place before the %iterator.
 584        *
 585        *  The position is maintained such that subsequent assignments will
 586        *  insert values immediately after one another.  For example,
 587        *  @code
 588        *     // vector v contains A and Z
 589        *
 590        *     insert_iterator i (v, ++v.begin());
 591        *     i = 1;
 592        *     i = 2;
 593        *     i = 3;
 594        *
 595        *     // vector v contains A, 1, 2, 3, and Z
 596        *  @endcode
 597       */
 598       insert_iterator&
 599       operator=(typename _Container::const_reference __value)
 600       {
 601         iter = container->insert(iter, __value);
 602         ++iter;
 603         return *this;
 604       }
 605
 606 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 607       insert_iterator&
 608       operator=(typename _Container::value_type&& __value)
 609       {
 610         iter = container->insert(iter, std::move(__value));
 611         ++iter;
 612         return *this;
 613       }
 614 #endif
 615
 616       /// Simply returns *this.
 617       insert_iterator&
 618       operator*()
 619       { return *this; }
 620
 621       /// Simply returns *this.  (This %iterator does not "move".)
 622       insert_iterator&
 623       operator++()
 624       { return *this; }
 625
 626       /// Simply returns *this.  (This %iterator does not "move".)
 627       insert_iterator&
 628       operator++(int)
 629       { return *this; }
 630     };
 631
 632   /**
 633    *  @param  x  A container of arbitrary type.
 634    *  @return  An instance of insert_iterator working on @p x.
 635    *
 636    *  This wrapper function helps in creating insert_iterator instances.
 637    *  Typing the name of the %iterator requires knowing the precise full
 638    *  type of the container, which can be tedious and impedes generic
 639    *  programming.  Using this function lets you take advantage of automatic
 640    *  template parameter deduction, making the compiler match the correct
 641    *  types for you.
 642   */
 643   template<typename _Container, typename _Iterator>
 644     inline insert_iterator<_Container>
 645     inserter(_Container& __x, _Iterator __i)
 646     {
 647       return insert_iterator<_Container>(__x,
 648                                          typename _Container::iterator(__i));
 649     }
 650
 651 _GLIBCXX_END_NAMESPACE
 652
 653 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
 654
 655   // This iterator adapter is 'normal' in the sense that it does not
 656   // change the semantics of any of the operators of its iterator
 657   // parameter.  Its primary purpose is to convert an iterator that is
 658   // not a class, e.g. a pointer, into an iterator that is a class.
 659   // The _Container parameter exists solely so that different containers
 660   // using this template can instantiate different types, even if the
 661   // _Iterator parameter is the same.
 662   using std::iterator_traits;
 663   using std::iterator;
 664   template<typename _Iterator, typename _Container>
 665     class __normal_iterator
 666     {
 667     protected:
 668       _Iterator _M_current;
 669
 670     public:
 671       typedef _Iterator                                      iterator_type;
 672       typedef typename iterator_traits<_Iterator>::iterator_category
 673                                                              iterator_category;
 674       typedef typename iterator_traits<_Iterator>::value_type  value_type;
 675       typedef typename iterator_traits<_Iterator>::difference_type
 676                                                              difference_type;
 677       typedef typename iterator_traits<_Iterator>::reference reference;
 678       typedef typename iterator_traits<_Iterator>::pointer   pointer;
 679
 680       __normal_iterator() : _M_current(_Iterator()) { }
 681
 682       explicit
 683       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 684
 685       // Allow iterator to const_iterator conversion
 686       template<typename _Iter>
 687         __normal_iterator(const __normal_iterator<_Iter,
 688                           typename __enable_if<
 689                (std::__are_same<_Iter, typename _Container::pointer>::__value),
 690                       _Container>::__type>& __i)
 691         : _M_current(__i.base()) { }
 692
 693       // Forward iterator requirements
 694       reference
 695       operator*() const
 696       { return *_M_current; }
 697
 698       pointer
 699       operator->() const
 700       { return _M_current; }
 701
 702       __normal_iterator&
 703       operator++()
 704       {
 705         ++_M_current;
 706         return *this;
 707       }
 708
 709       __normal_iterator
 710       operator++(int)
 711       { return __normal_iterator(_M_current++); }
 712
 713       // Bidirectional iterator requirements
 714       __normal_iterator&
 715       operator--()
 716       {
 717         --_M_current;
 718         return *this;
 719       }
 720
 721       __normal_iterator
 722       operator--(int)
 723       { return __normal_iterator(_M_current--); }
 724
 725       // Random access iterator requirements
 726       reference
 727       operator[](const difference_type& __n) const
 728       { return _M_current[__n]; }
 729
 730       __normal_iterator&
 731       operator+=(const difference_type& __n)
 732       { _M_current += __n; return *this; }
 733
 734       __normal_iterator
 735       operator+(const difference_type& __n) const
 736       { return __normal_iterator(_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       const _Iterator&
 747       base() const
 748       { return _M_current; }
 749     };
 750
 751   // Note: In what follows, the left- and right-hand-side iterators are
 752   // allowed to vary in types (conceptually in cv-qualification) so that
 753   // comparison between cv-qualified and non-cv-qualified iterators be
 754   // valid.  However, the greedy and unfriendly operators in std::rel_ops
 755   // will make overload resolution ambiguous (when in scope) if we don't
 756   // provide overloads whose operands are of the same type.  Can someone
 757   // remind me what generic programming is about? -- Gaby
 758
 759   // Forward iterator requirements
 760   template<typename _IteratorL, typename _IteratorR, typename _Container>
 761     inline bool
 762     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 763                const __normal_iterator<_IteratorR, _Container>& __rhs)
 764     { return __lhs.base() == __rhs.base(); }
 765
 766   template<typename _Iterator, typename _Container>
 767     inline bool
 768     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
 769                const __normal_iterator<_Iterator, _Container>& __rhs)
 770     { return __lhs.base() == __rhs.base(); }
 771
 772   template<typename _IteratorL, typename _IteratorR, typename _Container>
 773     inline bool
 774     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 775                const __normal_iterator<_IteratorR, _Container>& __rhs)
 776     { return __lhs.base() != __rhs.base(); }
 777
 778   template<typename _Iterator, typename _Container>
 779     inline bool
 780     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
 781                const __normal_iterator<_Iterator, _Container>& __rhs)
 782     { return __lhs.base() != __rhs.base(); }
 783
 784   // Random access iterator requirements
 785   template<typename _IteratorL, typename _IteratorR, typename _Container>
 786     inline bool
 787     operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
 788               const __normal_iterator<_IteratorR, _Container>& __rhs)
 789     { return __lhs.base() < __rhs.base(); }
 790
 791   template<typename _Iterator, typename _Container>
 792     inline bool
 793     operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
 794               const __normal_iterator<_Iterator, _Container>& __rhs)
 795     { return __lhs.base() < __rhs.base(); }
 796
 797   template<typename _IteratorL, typename _IteratorR, typename _Container>
 798     inline bool
 799     operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
 800               const __normal_iterator<_IteratorR, _Container>& __rhs)
 801     { return __lhs.base() > __rhs.base(); }
 802
 803   template<typename _Iterator, typename _Container>
 804     inline bool
 805     operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
 806               const __normal_iterator<_Iterator, _Container>& __rhs)
 807     { return __lhs.base() > __rhs.base(); }
 808
 809   template<typename _IteratorL, typename _IteratorR, typename _Container>
 810     inline bool
 811     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 812                const __normal_iterator<_IteratorR, _Container>& __rhs)
 813     { return __lhs.base() <= __rhs.base(); }
 814
 815   template<typename _Iterator, typename _Container>
 816     inline bool
 817     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
 818                const __normal_iterator<_Iterator, _Container>& __rhs)
 819     { return __lhs.base() <= __rhs.base(); }
 820
 821   template<typename _IteratorL, typename _IteratorR, typename _Container>
 822     inline bool
 823     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 824                const __normal_iterator<_IteratorR, _Container>& __rhs)
 825     { return __lhs.base() >= __rhs.base(); }
 826
 827   template<typename _Iterator, typename _Container>
 828     inline bool
 829     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
 830                const __normal_iterator<_Iterator, _Container>& __rhs)
 831     { return __lhs.base() >= __rhs.base(); }
 832
 833   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 834   // According to the resolution of DR179 not only the various comparison
 835   // operators but also operator- must accept mixed iterator/const_iterator
 836   // parameters.
 837   template<typename _IteratorL, typename _IteratorR, typename _Container>
 838     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
 839     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 840               const __normal_iterator<_IteratorR, _Container>& __rhs)
 841     { return __lhs.base() - __rhs.base(); }
 842
 843   template<typename _Iterator, typename _Container>
 844     inline typename __normal_iterator<_Iterator, _Container>::difference_type
 845     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
 846               const __normal_iterator<_Iterator, _Container>& __rhs)
 847     { return __lhs.base() - __rhs.base(); }
 848
 849   template<typename _Iterator, typename _Container>
 850     inline __normal_iterator<_Iterator, _Container>
 851     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
 852               __n, const __normal_iterator<_Iterator, _Container>& __i)
 853     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 854
 855 _GLIBCXX_END_NAMESPACE
 856
 857 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 858
 859 _GLIBCXX_BEGIN_NAMESPACE(std)
 860
 861   // 24.4.3  Move iterators
 862   /**
 863    *  Class template move_iterator is an iterator adapter with the same
 864    *  behavior as the underlying iterator except that its dereference
 865    *  operator implicitly converts the value returned by the underlying
 866    *  iterator's dereference operator to an rvalue reference.  Some
 867    *  generic algorithms can be called with move iterators to replace
 868    *  copying with moving.
 869    */
 870   template<typename _Iterator>
 871     class move_iterator
 872     {
 873     protected:
 874       _Iterator _M_current;
 875
 876     public:
 877       typedef _Iterator                                        iterator_type;
 878       typedef typename iterator_traits<_Iterator>::difference_type
 879                                                                difference_type;
 880       // NB: DR 680.
 881       typedef _Iterator                                        pointer;
 882       typedef typename iterator_traits<_Iterator>::value_type  value_type;
 883       typedef typename iterator_traits<_Iterator>::iterator_category
 884                                                                iterator_category;
 885       typedef value_type&&                                     reference;
 886
 887     public:
 888       move_iterator()
 889       : _M_current() { }
 890
 891       explicit
 892       move_iterator(iterator_type __i)
 893       : _M_current(__i) { }
 894
 895       template<typename _Iter>
 896         move_iterator(const move_iterator<_Iter>& __i)
 897         : _M_current(__i.base()) { }
 898
 899       iterator_type
 900       base() const
 901       { return _M_current; }
 902
 903       reference
 904       operator*() const
 905       { return *_M_current; }
 906
 907       pointer
 908       operator->() const
 909       { return _M_current; }
 910
 911       move_iterator&
 912       operator++()
 913       {
 914         ++_M_current;
 915         return *this;
 916       }
 917
 918       move_iterator
 919       operator++(int)
 920       {
 921         move_iterator __tmp = *this;
 922         ++_M_current;
 923         return __tmp;
 924       }
 925
 926       move_iterator&
 927       operator--()
 928       {
 929         --_M_current;
 930         return *this;
 931       }
 932
 933       move_iterator
 934       operator--(int)
 935       {
 936         move_iterator __tmp = *this;
 937         --_M_current;
 938         return __tmp;
 939       }
 940
 941       move_iterator
 942       operator+(difference_type __n) const
 943       { return move_iterator(_M_current + __n); }
 944
 945       move_iterator&
 946       operator+=(difference_type __n)
 947       {
 948         _M_current += __n;
 949         return *this;
 950       }
 951
 952       move_iterator
 953       operator-(difference_type __n) const
 954       { return move_iterator(_M_current - __n); }
 955
 956       move_iterator&
 957       operator-=(difference_type __n)
 958       {
 959         _M_current -= __n;
 960         return *this;
 961       }
 962
 963       reference
 964       operator[](difference_type __n) const
 965       { return _M_current[__n]; }
 966     };
 967
 968   template<typename _IteratorL, typename _IteratorR>
 969     inline bool
 970     operator==(const move_iterator<_IteratorL>& __x,
 971                const move_iterator<_IteratorR>& __y)
 972     { return __x.base() == __y.base(); }
 973
 974   template<typename _IteratorL, typename _IteratorR>
 975     inline bool
 976     operator!=(const move_iterator<_IteratorL>& __x,
 977                const move_iterator<_IteratorR>& __y)
 978     { return !(__x == __y); }
 979
 980   template<typename _IteratorL, typename _IteratorR>
 981     inline bool
 982     operator<(const move_iterator<_IteratorL>& __x,
 983               const move_iterator<_IteratorR>& __y)
 984     { return __x.base() < __y.base(); }
 985
 986   template<typename _IteratorL, typename _IteratorR>
 987     inline bool
 988     operator<=(const move_iterator<_IteratorL>& __x,
 989                const move_iterator<_IteratorR>& __y)
 990     { return !(__y < __x); }
 991
 992   template<typename _IteratorL, typename _IteratorR>
 993     inline bool
 994     operator>(const move_iterator<_IteratorL>& __x,
 995               const move_iterator<_IteratorR>& __y)
 996     { return __y < __x; }
 997
 998   template<typename _IteratorL, typename _IteratorR>
 999     inline bool
1000     operator>=(const move_iterator<_IteratorL>& __x,
1001                const move_iterator<_IteratorR>& __y)
1002     { return !(__x < __y); }
1003
1004   template<typename _IteratorL, typename _IteratorR>
1005     inline typename move_iterator<_IteratorL>::difference_type
1006     operator-(const move_iterator<_IteratorL>& __x,
1007               const move_iterator<_IteratorR>& __y)
1008     { return __x.base() - __y.base(); }
1009
1010   template<typename _Iterator>
1011     inline move_iterator<_Iterator>
1012     operator+(typename move_iterator<_Iterator>::difference_type __n,
1013               const move_iterator<_Iterator>& __x)
1014     { return __x + __n; }
1015
1016   template<typename _Iterator>
1017     inline move_iterator<_Iterator>
1018     make_move_iterator(const _Iterator& __i)
1019     { return move_iterator<_Iterator>(__i); }
1020
1021 _GLIBCXX_END_NAMESPACE
1022
1023 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1024 #else
1025 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1026 #endif // __GXX_EXPERIMENTAL_CXX0X__
1027
1028 #endif