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
_GLIBCXX_VISIBILITY(default)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