Line data Source code
1 : // Iterators -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2016 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 : 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 : // Same as C++14 make_reverse_iterator but used in C++03 mode too.
400 : template<typename _Iterator>
401 : inline reverse_iterator<_Iterator>
402 : __make_reverse_iterator(_Iterator __i)
403 : { return reverse_iterator<_Iterator>(__i); }
404 :
405 : # if __cplusplus > 201103L
406 : # define __cpp_lib_make_reverse_iterator 201402
407 :
408 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
409 : // DR 2285. make_reverse_iterator
410 : /// Generator function for reverse_iterator.
411 : template<typename _Iterator>
412 : inline reverse_iterator<_Iterator>
413 : make_reverse_iterator(_Iterator __i)
414 : { return reverse_iterator<_Iterator>(__i); }
415 : # endif
416 : #endif
417 :
418 : #if __cplusplus >= 201103L
419 : template<typename _Iterator>
420 : auto
421 : __niter_base(reverse_iterator<_Iterator> __it)
422 : -> decltype(__make_reverse_iterator(__niter_base(__it.base())))
423 : { return __make_reverse_iterator(__niter_base(__it.base())); }
424 :
425 : template<typename _Iterator>
426 : struct __is_move_iterator<reverse_iterator<_Iterator> >
427 : : __is_move_iterator<_Iterator>
428 : { };
429 :
430 : template<typename _Iterator>
431 : auto
432 : __miter_base(reverse_iterator<_Iterator> __it)
433 : -> decltype(__make_reverse_iterator(__miter_base(__it.base())))
434 : { return __make_reverse_iterator(__miter_base(__it.base())); }
435 : #endif
436 :
437 : // 24.4.2.2.1 back_insert_iterator
438 : /**
439 : * @brief Turns assignment into insertion.
440 : *
441 : * These are output iterators, constructed from a container-of-T.
442 : * Assigning a T to the iterator appends it to the container using
443 : * push_back.
444 : *
445 : * Tip: Using the back_inserter function to create these iterators can
446 : * save typing.
447 : */
448 : template<typename _Container>
449 : class back_insert_iterator
450 : : public iterator<output_iterator_tag, void, void, void, void>
451 : {
452 : protected:
453 : _Container* container;
454 :
455 : public:
456 : /// A nested typedef for the type of whatever container you used.
457 : typedef _Container container_type;
458 :
459 : /// The only way to create this %iterator is with a container.
460 : explicit
461 0 : back_insert_iterator(_Container& __x)
462 0 : : container(std::__addressof(__x)) { }
463 :
464 : /**
465 : * @param __value An instance of whatever type
466 : * container_type::const_reference is; presumably a
467 : * reference-to-const T for container<T>.
468 : * @return This %iterator, for chained operations.
469 : *
470 : * This kind of %iterator doesn't really have a @a position in the
471 : * container (you can think of the position as being permanently at
472 : * the end, if you like). Assigning a value to the %iterator will
473 : * always append the value to the end of the container.
474 : */
475 : #if __cplusplus < 201103L
476 : back_insert_iterator&
477 : operator=(typename _Container::const_reference __value)
478 : {
479 : container->push_back(__value);
480 : return *this;
481 : }
482 : #else
483 : back_insert_iterator&
484 0 : operator=(const typename _Container::value_type& __value)
485 : {
486 0 : container->push_back(__value);
487 0 : return *this;
488 : }
489 :
490 : back_insert_iterator&
491 0 : operator=(typename _Container::value_type&& __value)
492 : {
493 0 : container->push_back(std::move(__value));
494 0 : return *this;
495 : }
496 : #endif
497 :
498 : /// Simply returns *this.
499 : back_insert_iterator&
500 0 : operator*()
501 0 : { return *this; }
502 :
503 : /// Simply returns *this. (This %iterator does not @a move.)
504 : back_insert_iterator&
505 0 : operator++()
506 0 : { return *this; }
507 :
508 : /// Simply returns *this. (This %iterator does not @a move.)
509 : back_insert_iterator
510 : operator++(int)
511 : { return *this; }
512 : };
513 :
514 : /**
515 : * @param __x A container of arbitrary type.
516 : * @return An instance of back_insert_iterator working on @p __x.
517 : *
518 : * This wrapper function helps in creating back_insert_iterator instances.
519 : * Typing the name of the %iterator requires knowing the precise full
520 : * type of the container, which can be tedious and impedes generic
521 : * programming. Using this function lets you take advantage of automatic
522 : * template parameter deduction, making the compiler match the correct
523 : * types for you.
524 : */
525 : template<typename _Container>
526 : inline back_insert_iterator<_Container>
527 0 : back_inserter(_Container& __x)
528 0 : { return back_insert_iterator<_Container>(__x); }
529 :
530 : /**
531 : * @brief Turns assignment into insertion.
532 : *
533 : * These are output iterators, constructed from a container-of-T.
534 : * Assigning a T to the iterator prepends it to the container using
535 : * push_front.
536 : *
537 : * Tip: Using the front_inserter function to create these iterators can
538 : * save typing.
539 : */
540 : template<typename _Container>
541 : class front_insert_iterator
542 : : public iterator<output_iterator_tag, void, void, void, void>
543 : {
544 : protected:
545 : _Container* container;
546 :
547 : public:
548 : /// A nested typedef for the type of whatever container you used.
549 : typedef _Container container_type;
550 :
551 : /// The only way to create this %iterator is with a container.
552 : explicit front_insert_iterator(_Container& __x)
553 : : container(std::__addressof(__x)) { }
554 :
555 : /**
556 : * @param __value An instance of whatever type
557 : * container_type::const_reference is; presumably a
558 : * reference-to-const T for container<T>.
559 : * @return This %iterator, for chained operations.
560 : *
561 : * This kind of %iterator doesn't really have a @a position in the
562 : * container (you can think of the position as being permanently at
563 : * the front, if you like). Assigning a value to the %iterator will
564 : * always prepend the value to the front of the container.
565 : */
566 : #if __cplusplus < 201103L
567 : front_insert_iterator&
568 : operator=(typename _Container::const_reference __value)
569 : {
570 : container->push_front(__value);
571 : return *this;
572 : }
573 : #else
574 : front_insert_iterator&
575 : operator=(const typename _Container::value_type& __value)
576 : {
577 : container->push_front(__value);
578 : return *this;
579 : }
580 :
581 : front_insert_iterator&
582 : operator=(typename _Container::value_type&& __value)
583 : {
584 : container->push_front(std::move(__value));
585 : return *this;
586 : }
587 : #endif
588 :
589 : /// Simply returns *this.
590 : front_insert_iterator&
591 : operator*()
592 : { return *this; }
593 :
594 : /// Simply returns *this. (This %iterator does not @a move.)
595 : front_insert_iterator&
596 : operator++()
597 : { return *this; }
598 :
599 : /// Simply returns *this. (This %iterator does not @a move.)
600 : front_insert_iterator
601 : operator++(int)
602 : { return *this; }
603 : };
604 :
605 : /**
606 : * @param __x A container of arbitrary type.
607 : * @return An instance of front_insert_iterator working on @p x.
608 : *
609 : * This wrapper function helps in creating front_insert_iterator instances.
610 : * Typing the name of the %iterator requires knowing the precise full
611 : * type of the container, which can be tedious and impedes generic
612 : * programming. Using this function lets you take advantage of automatic
613 : * template parameter deduction, making the compiler match the correct
614 : * types for you.
615 : */
616 : template<typename _Container>
617 : inline front_insert_iterator<_Container>
618 : front_inserter(_Container& __x)
619 : { return front_insert_iterator<_Container>(__x); }
620 :
621 : /**
622 : * @brief Turns assignment into insertion.
623 : *
624 : * These are output iterators, constructed from a container-of-T.
625 : * Assigning a T to the iterator inserts it in the container at the
626 : * %iterator's position, rather than overwriting the value at that
627 : * position.
628 : *
629 : * (Sequences will actually insert a @e copy of the value before the
630 : * %iterator's position.)
631 : *
632 : * Tip: Using the inserter function to create these iterators can
633 : * save typing.
634 : */
635 : template<typename _Container>
636 : class insert_iterator
637 : : public iterator<output_iterator_tag, void, void, void, void>
638 : {
639 : protected:
640 : _Container* container;
641 : typename _Container::iterator iter;
642 :
643 : public:
644 : /// A nested typedef for the type of whatever container you used.
645 : typedef _Container container_type;
646 :
647 : /**
648 : * The only way to create this %iterator is with a container and an
649 : * initial position (a normal %iterator into the container).
650 : */
651 : insert_iterator(_Container& __x, typename _Container::iterator __i)
652 : : container(std::__addressof(__x)), iter(__i) {}
653 :
654 : /**
655 : * @param __value An instance of whatever type
656 : * container_type::const_reference is; presumably a
657 : * reference-to-const T for container<T>.
658 : * @return This %iterator, for chained operations.
659 : *
660 : * This kind of %iterator maintains its own position in the
661 : * container. Assigning a value to the %iterator will insert the
662 : * value into the container at the place before the %iterator.
663 : *
664 : * The position is maintained such that subsequent assignments will
665 : * insert values immediately after one another. For example,
666 : * @code
667 : * // vector v contains A and Z
668 : *
669 : * insert_iterator i (v, ++v.begin());
670 : * i = 1;
671 : * i = 2;
672 : * i = 3;
673 : *
674 : * // vector v contains A, 1, 2, 3, and Z
675 : * @endcode
676 : */
677 : #if __cplusplus < 201103L
678 : insert_iterator&
679 : operator=(typename _Container::const_reference __value)
680 : {
681 : iter = container->insert(iter, __value);
682 : ++iter;
683 : return *this;
684 : }
685 : #else
686 : insert_iterator&
687 : operator=(const typename _Container::value_type& __value)
688 : {
689 : iter = container->insert(iter, __value);
690 : ++iter;
691 : return *this;
692 : }
693 :
694 : insert_iterator&
695 : operator=(typename _Container::value_type&& __value)
696 : {
697 : iter = container->insert(iter, std::move(__value));
698 : ++iter;
699 : return *this;
700 : }
701 : #endif
702 :
703 : /// Simply returns *this.
704 : insert_iterator&
705 : operator*()
706 : { return *this; }
707 :
708 : /// Simply returns *this. (This %iterator does not @a move.)
709 : insert_iterator&
710 : operator++()
711 : { return *this; }
712 :
713 : /// Simply returns *this. (This %iterator does not @a move.)
714 : insert_iterator&
715 : operator++(int)
716 : { return *this; }
717 : };
718 :
719 : /**
720 : * @param __x A container of arbitrary type.
721 : * @return An instance of insert_iterator working on @p __x.
722 : *
723 : * This wrapper function helps in creating insert_iterator instances.
724 : * Typing the name of the %iterator requires knowing the precise full
725 : * type of the container, which can be tedious and impedes generic
726 : * programming. Using this function lets you take advantage of automatic
727 : * template parameter deduction, making the compiler match the correct
728 : * types for you.
729 : */
730 : template<typename _Container, typename _Iterator>
731 : inline insert_iterator<_Container>
732 : inserter(_Container& __x, _Iterator __i)
733 : {
734 : return insert_iterator<_Container>(__x,
735 : typename _Container::iterator(__i));
736 : }
737 :
738 : // @} group iterators
739 :
740 : _GLIBCXX_END_NAMESPACE_VERSION
741 : } // namespace
742 :
743 : namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
744 : {
745 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
746 :
747 : // This iterator adapter is @a normal in the sense that it does not
748 : // change the semantics of any of the operators of its iterator
749 : // parameter. Its primary purpose is to convert an iterator that is
750 : // not a class, e.g. a pointer, into an iterator that is a class.
751 : // The _Container parameter exists solely so that different containers
752 : // using this template can instantiate different types, even if the
753 : // _Iterator parameter is the same.
754 : using std::iterator_traits;
755 : using std::iterator;
756 : template<typename _Iterator, typename _Container>
757 : class __normal_iterator
758 : {
759 : protected:
760 : _Iterator _M_current;
761 :
762 : typedef iterator_traits<_Iterator> __traits_type;
763 :
764 : public:
765 : typedef _Iterator iterator_type;
766 : typedef typename __traits_type::iterator_category iterator_category;
767 : typedef typename __traits_type::value_type value_type;
768 : typedef typename __traits_type::difference_type difference_type;
769 : typedef typename __traits_type::reference reference;
770 : typedef typename __traits_type::pointer pointer;
771 :
772 0 : _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT
773 0 : : _M_current(_Iterator()) { }
774 :
775 : explicit
776 7559 : __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT
777 7559 : : _M_current(__i) { }
778 :
779 : // Allow iterator to const_iterator conversion
780 : template<typename _Iter>
781 0 : __normal_iterator(const __normal_iterator<_Iter,
782 : typename __enable_if<
783 : (std::__are_same<_Iter, typename _Container::pointer>::__value),
784 : _Container>::__type>& __i) _GLIBCXX_NOEXCEPT
785 0 : : _M_current(__i.base()) { }
786 :
787 : // Forward iterator requirements
788 : reference
789 6498 : operator*() const _GLIBCXX_NOEXCEPT
790 6498 : { return *_M_current; }
791 :
792 : pointer
793 32 : operator->() const _GLIBCXX_NOEXCEPT
794 32 : { return _M_current; }
795 :
796 : __normal_iterator&
797 6311 : operator++() _GLIBCXX_NOEXCEPT
798 : {
799 6311 : ++_M_current;
800 6311 : return *this;
801 : }
802 :
803 : __normal_iterator
804 0 : operator++(int) _GLIBCXX_NOEXCEPT
805 0 : { return __normal_iterator(_M_current++); }
806 :
807 : // Bidirectional iterator requirements
808 : __normal_iterator&
809 0 : operator--() _GLIBCXX_NOEXCEPT
810 : {
811 0 : --_M_current;
812 0 : return *this;
813 : }
814 :
815 : __normal_iterator
816 : operator--(int) _GLIBCXX_NOEXCEPT
817 : { return __normal_iterator(_M_current--); }
818 :
819 : // Random access iterator requirements
820 : reference
821 : operator[](difference_type __n) const _GLIBCXX_NOEXCEPT
822 : { return _M_current[__n]; }
823 :
824 : __normal_iterator&
825 0 : operator+=(difference_type __n) _GLIBCXX_NOEXCEPT
826 0 : { _M_current += __n; return *this; }
827 :
828 : __normal_iterator
829 0 : operator+(difference_type __n) const _GLIBCXX_NOEXCEPT
830 0 : { return __normal_iterator(_M_current + __n); }
831 :
832 : __normal_iterator&
833 : operator-=(difference_type __n) _GLIBCXX_NOEXCEPT
834 : { _M_current -= __n; return *this; }
835 :
836 : __normal_iterator
837 138 : operator-(difference_type __n) const _GLIBCXX_NOEXCEPT
838 138 : { return __normal_iterator(_M_current - __n); }
839 :
840 : const _Iterator&
841 19861 : base() const _GLIBCXX_NOEXCEPT
842 19861 : { return _M_current; }
843 : };
844 :
845 : // Note: In what follows, the left- and right-hand-side iterators are
846 : // allowed to vary in types (conceptually in cv-qualification) so that
847 : // comparison between cv-qualified and non-cv-qualified iterators be
848 : // valid. However, the greedy and unfriendly operators in std::rel_ops
849 : // will make overload resolution ambiguous (when in scope) if we don't
850 : // provide overloads whose operands are of the same type. Can someone
851 : // remind me what generic programming is about? -- Gaby
852 :
853 : // Forward iterator requirements
854 : template<typename _IteratorL, typename _IteratorR, typename _Container>
855 : inline bool
856 0 : operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
857 : const __normal_iterator<_IteratorR, _Container>& __rhs)
858 : _GLIBCXX_NOEXCEPT
859 0 : { return __lhs.base() == __rhs.base(); }
860 :
861 : template<typename _Iterator, typename _Container>
862 : inline bool
863 13 : operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
864 : const __normal_iterator<_Iterator, _Container>& __rhs)
865 : _GLIBCXX_NOEXCEPT
866 13 : { return __lhs.base() == __rhs.base(); }
867 :
868 : template<typename _IteratorL, typename _IteratorR, typename _Container>
869 : inline bool
870 0 : operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
871 : const __normal_iterator<_IteratorR, _Container>& __rhs)
872 : _GLIBCXX_NOEXCEPT
873 0 : { return __lhs.base() != __rhs.base(); }
874 :
875 : template<typename _Iterator, typename _Container>
876 : inline bool
877 6805 : operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
878 : const __normal_iterator<_Iterator, _Container>& __rhs)
879 : _GLIBCXX_NOEXCEPT
880 6805 : { return __lhs.base() != __rhs.base(); }
881 :
882 : // Random access iterator requirements
883 : template<typename _IteratorL, typename _IteratorR, typename _Container>
884 : inline bool
885 : operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
886 : const __normal_iterator<_IteratorR, _Container>& __rhs)
887 : _GLIBCXX_NOEXCEPT
888 : { return __lhs.base() < __rhs.base(); }
889 :
890 : template<typename _Iterator, typename _Container>
891 : inline bool
892 0 : operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
893 : const __normal_iterator<_Iterator, _Container>& __rhs)
894 : _GLIBCXX_NOEXCEPT
895 0 : { return __lhs.base() < __rhs.base(); }
896 :
897 : template<typename _IteratorL, typename _IteratorR, typename _Container>
898 : inline bool
899 : operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
900 : const __normal_iterator<_IteratorR, _Container>& __rhs)
901 : _GLIBCXX_NOEXCEPT
902 : { return __lhs.base() > __rhs.base(); }
903 :
904 : template<typename _Iterator, typename _Container>
905 : inline bool
906 : operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
907 : const __normal_iterator<_Iterator, _Container>& __rhs)
908 : _GLIBCXX_NOEXCEPT
909 : { return __lhs.base() > __rhs.base(); }
910 :
911 : template<typename _IteratorL, typename _IteratorR, typename _Container>
912 : inline bool
913 : operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
914 : const __normal_iterator<_IteratorR, _Container>& __rhs)
915 : _GLIBCXX_NOEXCEPT
916 : { return __lhs.base() <= __rhs.base(); }
917 :
918 : template<typename _Iterator, typename _Container>
919 : inline bool
920 : operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
921 : const __normal_iterator<_Iterator, _Container>& __rhs)
922 : _GLIBCXX_NOEXCEPT
923 : { return __lhs.base() <= __rhs.base(); }
924 :
925 : template<typename _IteratorL, typename _IteratorR, typename _Container>
926 : inline bool
927 : operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
928 : const __normal_iterator<_IteratorR, _Container>& __rhs)
929 : _GLIBCXX_NOEXCEPT
930 : { return __lhs.base() >= __rhs.base(); }
931 :
932 : template<typename _Iterator, typename _Container>
933 : inline bool
934 : operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
935 : const __normal_iterator<_Iterator, _Container>& __rhs)
936 : _GLIBCXX_NOEXCEPT
937 : { return __lhs.base() >= __rhs.base(); }
938 :
939 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
940 : // According to the resolution of DR179 not only the various comparison
941 : // operators but also operator- must accept mixed iterator/const_iterator
942 : // parameters.
943 : template<typename _IteratorL, typename _IteratorR, typename _Container>
944 : #if __cplusplus >= 201103L
945 : // DR 685.
946 : inline auto
947 0 : operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
948 : const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept
949 : -> decltype(__lhs.base() - __rhs.base())
950 : #else
951 : inline typename __normal_iterator<_IteratorL, _Container>::difference_type
952 : operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
953 : const __normal_iterator<_IteratorR, _Container>& __rhs)
954 : #endif
955 0 : { return __lhs.base() - __rhs.base(); }
956 :
957 : template<typename _Iterator, typename _Container>
958 : inline typename __normal_iterator<_Iterator, _Container>::difference_type
959 0 : operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
960 : const __normal_iterator<_Iterator, _Container>& __rhs)
961 : _GLIBCXX_NOEXCEPT
962 0 : { return __lhs.base() - __rhs.base(); }
963 :
964 : template<typename _Iterator, typename _Container>
965 : inline __normal_iterator<_Iterator, _Container>
966 : operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
967 : __n, const __normal_iterator<_Iterator, _Container>& __i)
968 : _GLIBCXX_NOEXCEPT
969 : { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
970 :
971 : _GLIBCXX_END_NAMESPACE_VERSION
972 : } // namespace
973 :
974 : namespace std _GLIBCXX_VISIBILITY(default)
975 : {
976 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
977 :
978 : template<typename _Iterator, typename _Container>
979 : _Iterator
980 6225 : __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it)
981 6225 : { return __it.base(); }
982 :
983 : _GLIBCXX_END_NAMESPACE_VERSION
984 : } // namespace
985 :
986 : #if __cplusplus >= 201103L
987 :
988 : namespace std _GLIBCXX_VISIBILITY(default)
989 : {
990 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
991 :
992 : /**
993 : * @addtogroup iterators
994 : * @{
995 : */
996 :
997 : // 24.4.3 Move iterators
998 : /**
999 : * Class template move_iterator is an iterator adapter with the same
1000 : * behavior as the underlying iterator except that its dereference
1001 : * operator implicitly converts the value returned by the underlying
1002 : * iterator's dereference operator to an rvalue reference. Some
1003 : * generic algorithms can be called with move iterators to replace
1004 : * copying with moving.
1005 : */
1006 : template<typename _Iterator>
1007 : class move_iterator
1008 : {
1009 : protected:
1010 : _Iterator _M_current;
1011 :
1012 : typedef iterator_traits<_Iterator> __traits_type;
1013 : typedef typename __traits_type::reference __base_ref;
1014 :
1015 : public:
1016 : typedef _Iterator iterator_type;
1017 : typedef typename __traits_type::iterator_category iterator_category;
1018 : typedef typename __traits_type::value_type value_type;
1019 : typedef typename __traits_type::difference_type difference_type;
1020 : // NB: DR 680.
1021 : typedef _Iterator pointer;
1022 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
1023 : // 2106. move_iterator wrapping iterators returning prvalues
1024 : typedef typename conditional<is_reference<__base_ref>::value,
1025 : typename remove_reference<__base_ref>::type&&,
1026 : __base_ref>::type reference;
1027 :
1028 : move_iterator()
1029 : : _M_current() { }
1030 :
1031 : explicit
1032 8270 : move_iterator(iterator_type __i)
1033 8270 : : _M_current(__i) { }
1034 :
1035 : template<typename _Iter>
1036 : move_iterator(const move_iterator<_Iter>& __i)
1037 : : _M_current(__i.base()) { }
1038 :
1039 : iterator_type
1040 24358 : base() const
1041 24358 : { return _M_current; }
1042 :
1043 : reference
1044 8044 : operator*() const
1045 8044 : { return static_cast<reference>(*_M_current); }
1046 :
1047 : pointer
1048 : operator->() const
1049 : { return _M_current; }
1050 :
1051 : move_iterator&
1052 8044 : operator++()
1053 : {
1054 8044 : ++_M_current;
1055 8044 : return *this;
1056 : }
1057 :
1058 : move_iterator
1059 : operator++(int)
1060 : {
1061 : move_iterator __tmp = *this;
1062 : ++_M_current;
1063 : return __tmp;
1064 : }
1065 :
1066 : move_iterator&
1067 : operator--()
1068 : {
1069 : --_M_current;
1070 : return *this;
1071 : }
1072 :
1073 : move_iterator
1074 : operator--(int)
1075 : {
1076 : move_iterator __tmp = *this;
1077 : --_M_current;
1078 : return __tmp;
1079 : }
1080 :
1081 : move_iterator
1082 : operator+(difference_type __n) const
1083 : { return move_iterator(_M_current + __n); }
1084 :
1085 : move_iterator&
1086 : operator+=(difference_type __n)
1087 : {
1088 : _M_current += __n;
1089 : return *this;
1090 : }
1091 :
1092 : move_iterator
1093 : operator-(difference_type __n) const
1094 : { return move_iterator(_M_current - __n); }
1095 :
1096 : move_iterator&
1097 : operator-=(difference_type __n)
1098 : {
1099 : _M_current -= __n;
1100 : return *this;
1101 : }
1102 :
1103 : reference
1104 : operator[](difference_type __n) const
1105 : { return std::move(_M_current[__n]); }
1106 : };
1107 :
1108 : // Note: See __normal_iterator operators note from Gaby to understand
1109 : // why there are always 2 versions for most of the move_iterator
1110 : // operators.
1111 : template<typename _IteratorL, typename _IteratorR>
1112 : inline bool
1113 : operator==(const move_iterator<_IteratorL>& __x,
1114 : const move_iterator<_IteratorR>& __y)
1115 : { return __x.base() == __y.base(); }
1116 :
1117 : template<typename _Iterator>
1118 : inline bool
1119 9612 : operator==(const move_iterator<_Iterator>& __x,
1120 : const move_iterator<_Iterator>& __y)
1121 9612 : { return __x.base() == __y.base(); }
1122 :
1123 : template<typename _IteratorL, typename _IteratorR>
1124 : inline bool
1125 : operator!=(const move_iterator<_IteratorL>& __x,
1126 : const move_iterator<_IteratorR>& __y)
1127 : { return !(__x == __y); }
1128 :
1129 : template<typename _Iterator>
1130 : inline bool
1131 9612 : operator!=(const move_iterator<_Iterator>& __x,
1132 : const move_iterator<_Iterator>& __y)
1133 9612 : { return !(__x == __y); }
1134 :
1135 : template<typename _IteratorL, typename _IteratorR>
1136 : inline bool
1137 : operator<(const move_iterator<_IteratorL>& __x,
1138 : const move_iterator<_IteratorR>& __y)
1139 : { return __x.base() < __y.base(); }
1140 :
1141 : template<typename _Iterator>
1142 : inline bool
1143 : operator<(const move_iterator<_Iterator>& __x,
1144 : const move_iterator<_Iterator>& __y)
1145 : { return __x.base() < __y.base(); }
1146 :
1147 : template<typename _IteratorL, typename _IteratorR>
1148 : inline bool
1149 : operator<=(const move_iterator<_IteratorL>& __x,
1150 : const move_iterator<_IteratorR>& __y)
1151 : { return !(__y < __x); }
1152 :
1153 : template<typename _Iterator>
1154 : inline bool
1155 : operator<=(const move_iterator<_Iterator>& __x,
1156 : const move_iterator<_Iterator>& __y)
1157 : { return !(__y < __x); }
1158 :
1159 : template<typename _IteratorL, typename _IteratorR>
1160 : inline bool
1161 : operator>(const move_iterator<_IteratorL>& __x,
1162 : const move_iterator<_IteratorR>& __y)
1163 : { return __y < __x; }
1164 :
1165 : template<typename _Iterator>
1166 : inline bool
1167 : operator>(const move_iterator<_Iterator>& __x,
1168 : const move_iterator<_Iterator>& __y)
1169 : { return __y < __x; }
1170 :
1171 : template<typename _IteratorL, typename _IteratorR>
1172 : inline bool
1173 : operator>=(const move_iterator<_IteratorL>& __x,
1174 : const move_iterator<_IteratorR>& __y)
1175 : { return !(__x < __y); }
1176 :
1177 : template<typename _Iterator>
1178 : inline bool
1179 : operator>=(const move_iterator<_Iterator>& __x,
1180 : const move_iterator<_Iterator>& __y)
1181 : { return !(__x < __y); }
1182 :
1183 : // DR 685.
1184 : template<typename _IteratorL, typename _IteratorR>
1185 : inline auto
1186 : operator-(const move_iterator<_IteratorL>& __x,
1187 : const move_iterator<_IteratorR>& __y)
1188 : -> decltype(__x.base() - __y.base())
1189 : { return __x.base() - __y.base(); }
1190 :
1191 : template<typename _Iterator>
1192 : inline auto
1193 : operator-(const move_iterator<_Iterator>& __x,
1194 : const move_iterator<_Iterator>& __y)
1195 : -> decltype(__x.base() - __y.base())
1196 : { return __x.base() - __y.base(); }
1197 :
1198 : template<typename _Iterator>
1199 : inline move_iterator<_Iterator>
1200 : operator+(typename move_iterator<_Iterator>::difference_type __n,
1201 : const move_iterator<_Iterator>& __x)
1202 : { return __x + __n; }
1203 :
1204 : template<typename _Iterator>
1205 : inline move_iterator<_Iterator>
1206 : make_move_iterator(_Iterator __i)
1207 : { return move_iterator<_Iterator>(__i); }
1208 :
1209 : template<typename _Iterator, typename _ReturnType
1210 : = typename conditional<__move_if_noexcept_cond
1211 : <typename iterator_traits<_Iterator>::value_type>::value,
1212 : _Iterator, move_iterator<_Iterator>>::type>
1213 : inline _ReturnType
1214 : __make_move_if_noexcept_iterator(_Iterator __i)
1215 : { return _ReturnType(__i); }
1216 :
1217 : // Overload for pointers that matches std::move_if_noexcept more closely,
1218 : // returning a constant iterator when we don't want to move.
1219 : template<typename _Tp, typename _ReturnType
1220 : = typename conditional<__move_if_noexcept_cond<_Tp>::value,
1221 : const _Tp*, move_iterator<_Tp*>>::type>
1222 : inline _ReturnType
1223 8270 : __make_move_if_noexcept_iterator(_Tp* __i)
1224 8270 : { return _ReturnType(__i); }
1225 :
1226 : // @} group iterators
1227 :
1228 : template<typename _Iterator>
1229 : auto
1230 : __niter_base(move_iterator<_Iterator> __it)
1231 : -> decltype(make_move_iterator(__niter_base(__it.base())))
1232 : { return make_move_iterator(__niter_base(__it.base())); }
1233 :
1234 : template<typename _Iterator>
1235 : struct __is_move_iterator<move_iterator<_Iterator> >
1236 : {
1237 : enum { __value = 1 };
1238 : typedef __true_type __type;
1239 : };
1240 :
1241 : template<typename _Iterator>
1242 : auto
1243 5134 : __miter_base(move_iterator<_Iterator> __it)
1244 : -> decltype(__miter_base(__it.base()))
1245 5134 : { return __miter_base(__it.base()); }
1246 :
1247 : _GLIBCXX_END_NAMESPACE_VERSION
1248 : } // namespace
1249 :
1250 : #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter)
1251 : #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \
1252 : std::__make_move_if_noexcept_iterator(_Iter)
1253 : #else
1254 : #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter)
1255 : #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter)
1256 : #endif // C++11
1257 :
1258 : #ifdef _GLIBCXX_DEBUG
1259 : # include <debug/stl_iterator.h>
1260 : #endif
1261 :
1262 : #endif
|
