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