Branch data 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 : 1244 : reverse_iterator() : current() { }
121 : :
122 : : /**
123 : : * This %iterator will move in the opposite direction that @p x does.
124 : : */
125 : : explicit
126 : 40718 : reverse_iterator(iterator_type __x) : current(__x) { }
127 : :
128 : : /**
129 : : * The copy constructor is normal.
130 : : */
131 : : reverse_iterator(const reverse_iterator& __x)
132 : : : 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 : 38282 : base() const
147 : 38282 : { 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 : 17923 : operator*() const
161 : : {
162 : 17923 : _Iterator __tmp = current;
163 : 17923 : 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 : 17923 : operator++()
182 : : {
183 : 17923 : --current;
184 : 17923 : return *this;
185 : : }
186 : :
187 : : /**
188 : : * @return The original value of @c *this
189 : : *
190 : : * Decrements the underlying iterator.
191 : : */
192 : : reverse_iterator
193 : : operator++(int)
194 : : {
195 : : reverse_iterator __tmp = *this;
196 : : --current;
197 : : 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 : 596 : operator==(const reverse_iterator<_Iterator>& __x,
292 : : const reverse_iterator<_Iterator>& __y)
293 : 596 : { return __x.base() == __y.base(); }
294 : :
295 : : template<typename _Iterator>
296 : : inline bool
297 : 18545 : operator<(const reverse_iterator<_Iterator>& __x,
298 : : const reverse_iterator<_Iterator>& __y)
299 [ + - ]: 18545 : { return __y.base() < __x.base(); }
300 : :
301 : : template<typename _Iterator>
302 : : inline bool
303 : 596 : operator!=(const reverse_iterator<_Iterator>& __x,
304 : : const reverse_iterator<_Iterator>& __y)
305 : 596 : { 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 : : { 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 : : 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 : : 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 : : { 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 : : operator=(typename _Container::const_reference __value)
631 : : {
632 : : iter = container->insert(iter, __value);
633 : : ++iter;
634 : : 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 : 1510 : _GLIBCXX_CONSTEXPR __normal_iterator() : _M_current(_Iterator()) { }
724 : :
725 : : explicit
726 : 4495589 : __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
727 : :
728 : : // Allow iterator to const_iterator conversion
729 : : template<typename _Iter>
730 : 1985 : __normal_iterator(const __normal_iterator<_Iter,
731 : : typename __enable_if<
732 : : (std::__are_same<_Iter, typename _Container::pointer>::__value),
733 : : _Container>::__type>& __i)
734 : 1985 : : _M_current(__i.base()) { }
735 : :
736 : : // Forward iterator requirements
737 : : reference
738 : 29178292 : operator*() const
739 : 29178292 : { return *_M_current; }
740 : :
741 : : pointer
742 : 0 : operator->() const
743 : 0 : { return _M_current; }
744 : :
745 : : __normal_iterator&
746 : 24505721 : operator++()
747 : : {
748 : 24505721 : ++_M_current;
749 : 24505721 : return *this;
750 : : }
751 : :
752 : : __normal_iterator
753 : : operator++(int)
754 : : { return __normal_iterator(_M_current++); }
755 : :
756 : : // Bidirectional iterator requirements
757 : : __normal_iterator&
758 : 2410396 : operator--()
759 : : {
760 : 2410396 : --_M_current;
761 : 2410396 : 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 : 192 : operator+=(const difference_type& __n)
775 : 192 : { _M_current += __n; return *this; }
776 : :
777 : : __normal_iterator
778 : 2060512 : operator+(const difference_type& __n) const
779 : 2060512 : { 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 : 108024 : operator-(const difference_type& __n) const
787 : 108024 : { return __normal_iterator(_M_current - __n); }
788 : :
789 : : const _Iterator&
790 : 56320048 : base() const
791 : 56320048 : { 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 : : operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
806 : : const __normal_iterator<_IteratorR, _Container>& __rhs)
807 : : { return __lhs.base() == __rhs.base(); }
808 : :
809 : : template<typename _Iterator, typename _Container>
810 : : inline bool
811 : 680 : operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
812 : : const __normal_iterator<_Iterator, _Container>& __rhs)
813 : 680 : { return __lhs.base() == __rhs.base(); }
814 : :
815 : : template<typename _IteratorL, typename _IteratorR, typename _Container>
816 : : inline bool
817 : 1985 : operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
818 : : const __normal_iterator<_IteratorR, _Container>& __rhs)
819 : 1985 : { return __lhs.base() != __rhs.base(); }
820 : :
821 : : template<typename _Iterator, typename _Container>
822 : : inline bool
823 : 27622678 : operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
824 : : const __normal_iterator<_Iterator, _Container>& __rhs)
825 : 27622678 : { 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 : 45599 : operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
837 : : const __normal_iterator<_Iterator, _Container>& __rhs)
838 : 45599 : { 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 : 892 : operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
873 : : const __normal_iterator<_Iterator, _Container>& __rhs)
874 : 892 : { 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 : 300874 : operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
897 : : const __normal_iterator<_Iterator, _Container>& __rhs)
898 : 300874 : { 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 : : move_iterator(iterator_type __i)
951 : : : _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 : : base() const
959 : : { return _M_current; }
960 : :
961 : : reference
962 : : operator*() const
963 : : { return std::move(*_M_current); }
964 : :
965 : : pointer
966 : : operator->() const
967 : : { return _M_current; }
968 : :
969 : : move_iterator&
970 : : operator++()
971 : : {
972 : : ++_M_current;
973 : : 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 : : operator==(const move_iterator<_Iterator>& __x,
1038 : : const move_iterator<_Iterator>& __y)
1039 : : { 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 : : operator!=(const move_iterator<_Iterator>& __x,
1050 : : const move_iterator<_Iterator>& __y)
1051 : : { 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 : : __make_move_if_noexcept_iterator(_Iterator __i)
1133 : : { 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
|