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

   1 // Iterators -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
   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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  18 // permissions described in the GCC Runtime Library Exception, version
  19 // 3.1, as published by the Free Software Foundation.
  20
  21 // You should have received a copy of the GNU General Public License and
  22 // a copy of the GCC Runtime Library Exception along with this program;
  23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  24 // <http://www.gnu.org/licenses/>.
  25
  26 /*
  27  *
  28  * Copyright (c) 1994
  29  * Hewlett-Packard Company
  30  *
  31  * Permission to use, copy, modify, distribute and sell this software
  32  * and its documentation for any purpose is hereby granted without fee,
  33  * provided that the above copyright notice appear in all copies and
  34  * that both that copyright notice and this permission notice appear
  35  * in supporting documentation.  Hewlett-Packard Company makes no
  36  * representations about the suitability of this software for any
  37  * purpose.  It is provided "as is" without express or implied warranty.
  38  *
  39  *
  40  * Copyright (c) 1996-1998
  41  * Silicon Graphics Computer Systems, Inc.
  42  *
  43  * Permission to use, copy, modify, distribute and sell this software
  44  * and its documentation for any purpose is hereby granted without fee,
  45  * provided that the above copyright notice appear in all copies and
  46  * that both that copyright notice and this permission notice appear
  47  * in supporting documentation.  Silicon Graphics makes no
  48  * representations about the suitability of this software for any
  49  * purpose.  It is provided "as is" without express or implied warranty.
  50  */
  51
  52 /** @file stl_iterator.h
  53  *  This is an internal header file, included by other library headers.
  54  *  You should not attempt to use it directly.
  55  *
  56  *  This file implements reverse_iterator, back_insert_iterator,
  57  *  front_insert_iterator, insert_iterator, __normal_iterator, and their
  58  *  supporting functions and overloaded operators.
  59  */
  60
  61 #ifndef _STL_ITERATOR_H
  62 #define _STL_ITERATOR_H 1
  63
  64 #include <bits/cpp_type_traits.h>
  65 #include <ext/type_traits.h>
  66 #include <bits/move.h>
  67
  68 _GLIBCXX_BEGIN_NAMESPACE(std)
  69
  70   /**
  71    * @addtogroup iterators
  72    * @{
  73    */
  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    *  <em>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.</em> [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       typedef iterator_traits<_Iterator>                __traits_type;
 106
 107     public:
 108       typedef _Iterator                                 iterator_type;
 109       typedef typename __traits_type::difference_type   difference_type;
 110       typedef typename __traits_type::pointer           pointer;
 111       typedef typename __traits_type::reference         reference;
 112
 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 @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 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 420       back_insert_iterator&
 421       operator=(typename _Container::const_reference __value)
 422       {
 423         container->push_back(__value);
 424         return *this;
 425       }
 426 #else
 427       back_insert_iterator&
 428       operator=(const typename _Container::value_type& __value)
 429       {
 430         container->push_back(__value);
 431         return *this;
 432       }
 433
 434       back_insert_iterator&
 435       operator=(typename _Container::value_type&& __value)
 436       {
 437         container->push_back(std::move(__value));
 438         return *this;
 439       }
 440 #endif
 441
 442       /// Simply returns *this.
 443       back_insert_iterator&
 444       operator*()
 445       { return *this; }
 446
 447       /// Simply returns *this.  (This %iterator does not @a move.)
 448       back_insert_iterator&
 449       operator++()
 450       { return *this; }
 451
 452       /// Simply returns *this.  (This %iterator does not @a move.)
 453       back_insert_iterator
 454       operator++(int)
 455       { return *this; }
 456     };
 457
 458   /**
 459    *  @param  x  A container of arbitrary type.
 460    *  @return  An instance of back_insert_iterator working on @p x.
 461    *
 462    *  This wrapper function helps in creating back_insert_iterator instances.
 463    *  Typing the name of the %iterator requires knowing the precise full
 464    *  type of the container, which can be tedious and impedes generic
 465    *  programming.  Using this function lets you take advantage of automatic
 466    *  template parameter deduction, making the compiler match the correct
 467    *  types for you.
 468   */
 469   template<typename _Container>
 470     inline back_insert_iterator<_Container>
 471     back_inserter(_Container& __x)
 472     { return back_insert_iterator<_Container>(__x); }
 473
 474   /**
 475    *  @brief  Turns assignment into insertion.
 476    *
 477    *  These are output iterators, constructed from a container-of-T.
 478    *  Assigning a T to the iterator prepends it to the container using
 479    *  push_front.
 480    *
 481    *  Tip:  Using the front_inserter function to create these iterators can
 482    *  save typing.
 483   */
 484   template<typename _Container>
 485     class front_insert_iterator
 486     : public iterator<output_iterator_tag, void, void, void, void>
 487     {
 488     protected:
 489       _Container* container;
 490
 491     public:
 492       /// A nested typedef for the type of whatever container you used.
 493       typedef _Container          container_type;
 494
 495       /// The only way to create this %iterator is with a container.
 496       explicit front_insert_iterator(_Container& __x) : container(&__x) { }
 497
 498       /**
 499        *  @param  value  An instance of whatever type
 500        *                 container_type::const_reference is; presumably a
 501        *                 reference-to-const T for container<T>.
 502        *  @return  This %iterator, for chained operations.
 503        *
 504        *  This kind of %iterator doesn't really have a @a position in the
 505        *  container (you can think of the position as being permanently at
 506        *  the front, if you like).  Assigning a value to the %iterator will
 507        *  always prepend the value to the front of the container.
 508       */
 509 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 510       front_insert_iterator&
 511       operator=(typename _Container::const_reference __value)
 512       {
 513         container->push_front(__value);
 514         return *this;
 515       }
 516 #else
 517       front_insert_iterator&
 518       operator=(const typename _Container::value_type& __value)
 519       {
 520         container->push_front(__value);
 521         return *this;
 522       }
 523
 524       front_insert_iterator&
 525       operator=(typename _Container::value_type&& __value)
 526       {
 527         container->push_front(std::move(__value));
 528         return *this;
 529       }
 530 #endif
 531
 532       /// Simply returns *this.
 533       front_insert_iterator&
 534       operator*()
 535       { return *this; }
 536
 537       /// Simply returns *this.  (This %iterator does not @a move.)
 538       front_insert_iterator&
 539       operator++()
 540       { return *this; }
 541
 542       /// Simply returns *this.  (This %iterator does not @a move.)
 543       front_insert_iterator
 544       operator++(int)
 545       { return *this; }
 546     };
 547
 548   /**
 549    *  @param  x  A container of arbitrary type.
 550    *  @return  An instance of front_insert_iterator working on @p x.
 551    *
 552    *  This wrapper function helps in creating front_insert_iterator instances.
 553    *  Typing the name of the %iterator requires knowing the precise full
 554    *  type of the container, which can be tedious and impedes generic
 555    *  programming.  Using this function lets you take advantage of automatic
 556    *  template parameter deduction, making the compiler match the correct
 557    *  types for you.
 558   */
 559   template<typename _Container>
 560     inline front_insert_iterator<_Container>
 561     front_inserter(_Container& __x)
 562     { return front_insert_iterator<_Container>(__x); }
 563
 564   /**
 565    *  @brief  Turns assignment into insertion.
 566    *
 567    *  These are output iterators, constructed from a container-of-T.
 568    *  Assigning a T to the iterator inserts it in the container at the
 569    *  %iterator's position, rather than overwriting the value at that
 570    *  position.
 571    *
 572    *  (Sequences will actually insert a @e copy of the value before the
 573    *  %iterator's position.)
 574    *
 575    *  Tip:  Using the inserter function to create these iterators can
 576    *  save typing.
 577   */
 578   template<typename _Container>
 579     class insert_iterator
 580     : public iterator<output_iterator_tag, void, void, void, void>
 581     {
 582     protected:
 583       _Container* container;
 584       typename _Container::iterator iter;
 585
 586     public:
 587       /// A nested typedef for the type of whatever container you used.
 588       typedef _Container          container_type;
 589
 590       /**
 591        *  The only way to create this %iterator is with a container and an
 592        *  initial position (a normal %iterator into the container).
 593       */
 594       insert_iterator(_Container& __x, typename _Container::iterator __i)
 595       : container(&__x), iter(__i) {}
 596
 597       /**
 598        *  @param  value  An instance of whatever type
 599        *                 container_type::const_reference is; presumably a
 600        *                 reference-to-const T for container<T>.
 601        *  @return  This %iterator, for chained operations.
 602        *
 603        *  This kind of %iterator maintains its own position in the
 604        *  container.  Assigning a value to the %iterator will insert the
 605        *  value into the container at the place before the %iterator.
 606        *
 607        *  The position is maintained such that subsequent assignments will
 608        *  insert values immediately after one another.  For example,
 609        *  @code
 610        *     // vector v contains A and Z
 611        *
 612        *     insert_iterator i (v, ++v.begin());
 613        *     i = 1;
 614        *     i = 2;
 615        *     i = 3;
 616        *
 617        *     // vector v contains A, 1, 2, 3, and Z
 618        *  @endcode
 619       */
 620 #ifndef __GXX_EXPERIMENTAL_CXX0X__
 621       insert_iterator&
 622       operator=(typename _Container::const_reference __value)
 623       {
 624         iter = container->insert(iter, __value);
 625         ++iter;
 626         return *this;
 627       }
 628 #else
 629       insert_iterator&
 630       operator=(const typename _Container::value_type& __value)
 631       {
 632         iter = container->insert(iter, __value);
 633         ++iter;
 634         return *this;
 635       }
 636
 637       insert_iterator&
 638       operator=(typename _Container::value_type&& __value)
 639       {
 640         iter = container->insert(iter, std::move(__value));
 641         ++iter;
 642         return *this;
 643       }
 644 #endif
 645
 646       /// Simply returns *this.
 647       insert_iterator&
 648       operator*()
 649       { return *this; }
 650
 651       /// Simply returns *this.  (This %iterator does not @a move.)
 652       insert_iterator&
 653       operator++()
 654       { return *this; }
 655
 656       /// Simply returns *this.  (This %iterator does not @a move.)
 657       insert_iterator&
 658       operator++(int)
 659       { return *this; }
 660     };
 661
 662   /**
 663    *  @param  x  A container of arbitrary type.
 664    *  @return  An instance of insert_iterator working on @p x.
 665    *
 666    *  This wrapper function helps in creating insert_iterator instances.
 667    *  Typing the name of the %iterator requires knowing the precise full
 668    *  type of the container, which can be tedious and impedes generic
 669    *  programming.  Using this function lets you take advantage of automatic
 670    *  template parameter deduction, making the compiler match the correct
 671    *  types for you.
 672   */
 673   template<typename _Container, typename _Iterator>
 674     inline insert_iterator<_Container>
 675     inserter(_Container& __x, _Iterator __i)
 676     {
 677       return insert_iterator<_Container>(__x,
 678                                          typename _Container::iterator(__i));
 679     }
 680
 681   // @} group iterators
 682
 683 _GLIBCXX_END_NAMESPACE
 684
 685 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
 686
 687   // This iterator adapter is @a normal in the sense that it does not
 688   // change the semantics of any of the operators of its iterator
 689   // parameter.  Its primary purpose is to convert an iterator that is
 690   // not a class, e.g. a pointer, into an iterator that is a class.
 691   // The _Container parameter exists solely so that different containers
 692   // using this template can instantiate different types, even if the
 693   // _Iterator parameter is the same.
 694   using std::iterator_traits;
 695   using std::iterator;
 696   template<typename _Iterator, typename _Container>
 697     class __normal_iterator
 698     {
 699     protected:
 700       _Iterator _M_current;
 701
 702       typedef iterator_traits<_Iterator>                __traits_type;
 703
 704     public:
 705       typedef _Iterator                                 iterator_type;
 706       typedef typename __traits_type::iterator_category iterator_category;
 707       typedef typename __traits_type::value_type        value_type;
 708       typedef typename __traits_type::difference_type   difference_type;
 709       typedef typename __traits_type::reference         reference;
 710       typedef typename __traits_type::pointer           pointer;
 711
 712       __normal_iterator() : _M_current(_Iterator()) { }
 713
 714       explicit
 715       __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
 716
 717       // Allow iterator to const_iterator conversion
 718       template<typename _Iter>
 719         __normal_iterator(const __normal_iterator<_Iter,
 720                           typename __enable_if<
 721                (std::__are_same<_Iter, typename _Container::pointer>::__value),
 722                       _Container>::__type>& __i)
 723         : _M_current(__i.base()) { }
 724
 725       // Forward iterator requirements
 726       reference
 727       operator*() const
 728       { return *_M_current; }
 729
 730       pointer
 731       operator->() const
 732       { return _M_current; }
 733
 734       __normal_iterator&
 735       operator++()
 736       {
 737         ++_M_current;
 738         return *this;
 739       }
 740
 741       __normal_iterator
 742       operator++(int)
 743       { return __normal_iterator(_M_current++); }
 744
 745       // Bidirectional iterator requirements
 746       __normal_iterator&
 747       operator--()
 748       {
 749         --_M_current;
 750         return *this;
 751       }
 752
 753       __normal_iterator
 754       operator--(int)
 755       { return __normal_iterator(_M_current--); }
 756
 757       // Random access iterator requirements
 758       reference
 759       operator[](const difference_type& __n) const
 760       { return _M_current[__n]; }
 761
 762       __normal_iterator&
 763       operator+=(const difference_type& __n)
 764       { _M_current += __n; return *this; }
 765
 766       __normal_iterator
 767       operator+(const difference_type& __n) const
 768       { return __normal_iterator(_M_current + __n); }
 769
 770       __normal_iterator&
 771       operator-=(const difference_type& __n)
 772       { _M_current -= __n; return *this; }
 773
 774       __normal_iterator
 775       operator-(const difference_type& __n) const
 776       { return __normal_iterator(_M_current - __n); }
 777
 778       const _Iterator&
 779       base() const
 780       { return _M_current; }
 781     };
 782
 783   // Note: In what follows, the left- and right-hand-side iterators are
 784   // allowed to vary in types (conceptually in cv-qualification) so that
 785   // comparison between cv-qualified and non-cv-qualified iterators be
 786   // valid.  However, the greedy and unfriendly operators in std::rel_ops
 787   // will make overload resolution ambiguous (when in scope) if we don't
 788   // provide overloads whose operands are of the same type.  Can someone
 789   // remind me what generic programming is about? -- Gaby
 790
 791   // Forward iterator requirements
 792   template<typename _IteratorL, typename _IteratorR, typename _Container>
 793     inline bool
 794     operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
 795                const __normal_iterator<_IteratorR, _Container>& __rhs)
 796     { return __lhs.base() == __rhs.base(); }
 797
 798   template<typename _Iterator, typename _Container>
 799     inline bool
 800     operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
 801                const __normal_iterator<_Iterator, _Container>& __rhs)
 802     { return __lhs.base() == __rhs.base(); }
 803
 804   template<typename _IteratorL, typename _IteratorR, typename _Container>
 805     inline bool
 806     operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 807                const __normal_iterator<_IteratorR, _Container>& __rhs)
 808     { return __lhs.base() != __rhs.base(); }
 809
 810   template<typename _Iterator, typename _Container>
 811     inline bool
 812     operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
 813                const __normal_iterator<_Iterator, _Container>& __rhs)
 814     { return __lhs.base() != __rhs.base(); }
 815
 816   // Random access iterator requirements
 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   template<typename _IteratorL, typename _IteratorR, typename _Container>
 842     inline bool
 843     operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 844                const __normal_iterator<_IteratorR, _Container>& __rhs)
 845     { return __lhs.base() <= __rhs.base(); }
 846
 847   template<typename _Iterator, typename _Container>
 848     inline bool
 849     operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
 850                const __normal_iterator<_Iterator, _Container>& __rhs)
 851     { return __lhs.base() <= __rhs.base(); }
 852
 853   template<typename _IteratorL, typename _IteratorR, typename _Container>
 854     inline bool
 855     operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
 856                const __normal_iterator<_IteratorR, _Container>& __rhs)
 857     { return __lhs.base() >= __rhs.base(); }
 858
 859   template<typename _Iterator, typename _Container>
 860     inline bool
 861     operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
 862                const __normal_iterator<_Iterator, _Container>& __rhs)
 863     { return __lhs.base() >= __rhs.base(); }
 864
 865   // _GLIBCXX_RESOLVE_LIB_DEFECTS
 866   // According to the resolution of DR179 not only the various comparison
 867   // operators but also operator- must accept mixed iterator/const_iterator
 868   // parameters.
 869   template<typename _IteratorL, typename _IteratorR, typename _Container>
 870 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 871     // DR 685.
 872     inline auto
 873     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 874               const __normal_iterator<_IteratorR, _Container>& __rhs)
 875     -> decltype(__lhs.base() - __rhs.base())
 876 #else
 877     inline typename __normal_iterator<_IteratorL, _Container>::difference_type
 878     operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
 879               const __normal_iterator<_IteratorR, _Container>& __rhs)
 880 #endif
 881     { return __lhs.base() - __rhs.base(); }
 882
 883   template<typename _Iterator, typename _Container>
 884     inline typename __normal_iterator<_Iterator, _Container>::difference_type
 885     operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
 886               const __normal_iterator<_Iterator, _Container>& __rhs)
 887     { return __lhs.base() - __rhs.base(); }
 888
 889   template<typename _Iterator, typename _Container>
 890     inline __normal_iterator<_Iterator, _Container>
 891     operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
 892               __n, const __normal_iterator<_Iterator, _Container>& __i)
 893     { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
 894
 895 _GLIBCXX_END_NAMESPACE
 896
 897 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 898
 899 _GLIBCXX_BEGIN_NAMESPACE(std)
 900
 901   /**
 902    * @addtogroup iterators
 903    * @{
 904    */
 905
 906   // 24.4.3  Move iterators
 907   /**
 908    *  Class template move_iterator is an iterator adapter with the same
 909    *  behavior as the underlying iterator except that its dereference
 910    *  operator implicitly converts the value returned by the underlying
 911    *  iterator's dereference operator to an rvalue reference.  Some
 912    *  generic algorithms can be called with move iterators to replace
 913    *  copying with moving.
 914    */
 915   template<typename _Iterator>
 916     class move_iterator
 917     {
 918     protected:
 919       _Iterator _M_current;
 920
 921       typedef iterator_traits<_Iterator>                __traits_type;
 922
 923     public:
 924       typedef _Iterator                                 iterator_type;
 925       typedef typename __traits_type::iterator_category iterator_category;
 926       typedef typename __traits_type::value_type        value_type;
 927       typedef typename __traits_type::difference_type   difference_type;
 928       // NB: DR 680.
 929       typedef _Iterator                                 pointer;
 930       typedef value_type&&                              reference;
 931
 932       move_iterator()
 933       : _M_current() { }
 934
 935       explicit
 936       move_iterator(iterator_type __i)
 937       : _M_current(__i) { }
 938
 939       template<typename _Iter>
 940         move_iterator(const move_iterator<_Iter>& __i)
 941         : _M_current(__i.base()) { }
 942
 943       iterator_type
 944       base() const
 945       { return _M_current; }
 946
 947       reference
 948       operator*() const
 949       { return std::move(*_M_current); }
 950
 951       pointer
 952       operator->() const
 953       { return _M_current; }
 954
 955       move_iterator&
 956       operator++()
 957       {
 958         ++_M_current;
 959         return *this;
 960       }
 961
 962       move_iterator
 963       operator++(int)
 964       {
 965         move_iterator __tmp = *this;
 966         ++_M_current;
 967         return __tmp;
 968       }
 969
 970       move_iterator&
 971       operator--()
 972       {
 973         --_M_current;
 974         return *this;
 975       }
 976
 977       move_iterator
 978       operator--(int)
 979       {
 980         move_iterator __tmp = *this;
 981         --_M_current;
 982         return __tmp;
 983       }
 984
 985       move_iterator
 986       operator+(difference_type __n) const
 987       { return move_iterator(_M_current + __n); }
 988
 989       move_iterator&
 990       operator+=(difference_type __n)
 991       {
 992         _M_current += __n;
 993         return *this;
 994       }
 995
 996       move_iterator
 997       operator-(difference_type __n) const
 998       { return move_iterator(_M_current - __n); }
 999
1000       move_iterator&
1001       operator-=(difference_type __n)
1002       {
1003         _M_current -= __n;
1004         return *this;
1005       }
1006
1007       reference
1008       operator[](difference_type __n) const
1009       { return std::move(_M_current[__n]); }
1010     };
1011
1012   template<typename _IteratorL, typename _IteratorR>
1013     inline bool
1014     operator==(const move_iterator<_IteratorL>& __x,
1015                const move_iterator<_IteratorR>& __y)
1016     { return __x.base() == __y.base(); }
1017
1018   template<typename _IteratorL, typename _IteratorR>
1019     inline bool
1020     operator!=(const move_iterator<_IteratorL>& __x,
1021                const move_iterator<_IteratorR>& __y)
1022     { return !(__x == __y); }
1023
1024   template<typename _IteratorL, typename _IteratorR>
1025     inline bool
1026     operator<(const move_iterator<_IteratorL>& __x,
1027               const move_iterator<_IteratorR>& __y)
1028     { return __x.base() < __y.base(); }
1029
1030   template<typename _IteratorL, typename _IteratorR>
1031     inline bool
1032     operator<=(const move_iterator<_IteratorL>& __x,
1033                const move_iterator<_IteratorR>& __y)
1034     { return !(__y < __x); }
1035
1036   template<typename _IteratorL, typename _IteratorR>
1037     inline bool
1038     operator>(const move_iterator<_IteratorL>& __x,
1039               const move_iterator<_IteratorR>& __y)
1040     { return __y < __x; }
1041
1042   template<typename _IteratorL, typename _IteratorR>
1043     inline bool
1044     operator>=(const move_iterator<_IteratorL>& __x,
1045                const move_iterator<_IteratorR>& __y)
1046     { return !(__x < __y); }
1047
1048   // DR 685.
1049   template<typename _IteratorL, typename _IteratorR>
1050     inline auto
1051     operator-(const move_iterator<_IteratorL>& __x,
1052               const move_iterator<_IteratorR>& __y)
1053     -> decltype(__x.base() - __y.base())
1054     { return __x.base() - __y.base(); }
1055
1056   template<typename _Iterator>
1057     inline move_iterator<_Iterator>
1058     operator+(typename move_iterator<_Iterator>::difference_type __n,
1059               const move_iterator<_Iterator>& __x)
1060     { return __x + __n; }
1061
1062   template<typename _Iterator>
1063     inline move_iterator<_Iterator>
1064     make_move_iterator(const _Iterator& __i)
1065     { return move_iterator<_Iterator>(__i); }
1066
1067   // @} group iterators
1068
1069 _GLIBCXX_END_NAMESPACE
1070
1071 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1072 #else
1073 #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1074 #endif // __GXX_EXPERIMENTAL_CXX0X__
1075
1076 #endif