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