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   	
72   	namespace 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  	
749  	namespace __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  	
980  	namespace 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  	
994  	namespace 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