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