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