Clang Project

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