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