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