Line data Source code
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 :
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 7150 : __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
783 7150 : : _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 64895 : operator*() const _GLIBCXX_NOEXCEPT
796 64895 : { return *_M_current; }
797 :
798 : pointer
799 : operator->() const _GLIBCXX_NOEXCEPT
800 : { return _M_current; }
801 :
802 : __normal_iterator&
803 62103 : operator++() _GLIBCXX_NOEXCEPT
804 : {
805 62103 : ++_M_current;
806 62103 : return *this;
807 : }
808 :
809 : __normal_iterator
810 0 : operator++(int) _GLIBCXX_NOEXCEPT
811 0 : { 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 2388 : operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
844 2388 : { return __normal_iterator(_M_current - __n); }
845 :
846 : const _Iterator&
847 117262 : base() const _GLIBCXX_NOEXCEPT
848 117262 : { 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 57272 : operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
884 : const __normal_iterator<_Iterator, _Container>& __rhs)
885 : _GLIBCXX_NOEXCEPT
886 57272 : { 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 1053 : operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
966 : const __normal_iterator<_Iterator, _Container>& __rhs)
967 : _GLIBCXX_NOEXCEPT
968 1053 : { 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 10 : __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
987 10 : { 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 1280 : move_iterator(iterator_type __i)
1040 1280 : : _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 656768 : base() const
1049 656768 : { return _M_current; }
1050 :
1051 : _GLIBCXX17_CONSTEXPR reference
1052 327744 : operator*() const
1053 327744 : { 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 327744 : operator++()
1061 : {
1062 327744 : ++_M_current;
1063 327744 : 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 328378 : operator==(const move_iterator<_Iterator>& __x,
1128 : const move_iterator<_Iterator>& __y)
1129 328378 : { 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 328378 : operator!=(const move_iterator<_Iterator>& __x,
1140 : const move_iterator<_Iterator>& __y)
1141 328378 : { 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 1284 : __make_move_if_noexcept_iterator(_Tp* __i)
1225 1284 : { 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 12 : __miter_base(move_iterator<_Iterator> __it)
1245 : -> decltype(__miter_base(__it.base()))
1246 12 : { 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
|