1 | // Iterators -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2016 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /* |
26 | * |
27 | * Copyright (c) 1994 |
28 | * Hewlett-Packard Company |
29 | * |
30 | * Permission to use, copy, modify, distribute and sell this software |
31 | * and its documentation for any purpose is hereby granted without fee, |
32 | * provided that the above copyright notice appear in all copies and |
33 | * that both that copyright notice and this permission notice appear |
34 | * in supporting documentation. Hewlett-Packard Company makes no |
35 | * representations about the suitability of this software for any |
36 | * purpose. It is provided "as is" without express or implied warranty. |
37 | * |
38 | * |
39 | * Copyright (c) 1996-1998 |
40 | * Silicon Graphics Computer Systems, Inc. |
41 | * |
42 | * Permission to use, copy, modify, distribute and sell this software |
43 | * and its documentation for any purpose is hereby granted without fee, |
44 | * provided that the above copyright notice appear in all copies and |
45 | * that both that copyright notice and this permission notice appear |
46 | * in supporting documentation. Silicon Graphics makes no |
47 | * representations about the suitability of this software for any |
48 | * purpose. It is provided "as is" without express or implied warranty. |
49 | */ |
50 | |
51 | /** @file bits/stl_iterator.h |
52 | * This is an internal header file, included by other library headers. |
53 | * Do not attempt to use it directly. @headername{iterator} |
54 | * |
55 | * This file implements reverse_iterator, back_insert_iterator, |
56 | * front_insert_iterator, insert_iterator, __normal_iterator, and their |
57 | * supporting functions and overloaded operators. |
58 | */ |
59 | |
60 | #ifndef _STL_ITERATOR_H |
61 | #define _STL_ITERATOR_H 1 |
62 | |
63 | #include <bits/cpp_type_traits.h> |
64 | #include <ext/type_traits.h> |
65 | #include <bits/move.h> |
66 | #include <bits/ptr_traits.h> |
67 | |
68 | namespace std _GLIBCXX_VISIBILITY(default) |
69 | { |
70 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
71 | |
72 | /** |
73 | * @addtogroup iterators |
74 | * @{ |
75 | */ |
76 | |
77 | // 24.4.1 Reverse iterators |
78 | /** |
79 | * Bidirectional and random access iterators have corresponding reverse |
80 | * %iterator adaptors that iterate through the data structure in the |
81 | * opposite direction. They have the same signatures as the corresponding |
82 | * iterators. The fundamental relation between a reverse %iterator and its |
83 | * corresponding %iterator @c i is established by the identity: |
84 | * @code |
85 | * &*(reverse_iterator(i)) == &*(i - 1) |
86 | * @endcode |
87 | * |
88 | * <em>This mapping is dictated by the fact that while there is always a |
89 | * pointer past the end of an array, there might not be a valid pointer |
90 | * before the beginning of an array.</em> [24.4.1]/1,2 |
91 | * |
92 | * Reverse iterators can be tricky and surprising at first. Their |
93 | * semantics make sense, however, and the trickiness is a side effect of |
94 | * the requirement that the iterators must be safe. |
95 | */ |
96 | template<typename _Iterator> |
97 | class reverse_iterator |
98 | : public iterator<typename iterator_traits<_Iterator>::iterator_category, |
99 | typename iterator_traits<_Iterator>::value_type, |
100 | typename iterator_traits<_Iterator>::difference_type, |
101 | typename iterator_traits<_Iterator>::pointer, |
102 | typename iterator_traits<_Iterator>::reference> |
103 | { |
104 | protected: |
105 | _Iterator current; |
106 | |
107 | typedef iterator_traits<_Iterator> __traits_type; |
108 | |
109 | public: |
110 | typedef _Iterator iterator_type; |
111 | typedef typename __traits_type::difference_type difference_type; |
112 | typedef typename __traits_type::pointer pointer; |
113 | typedef typename __traits_type::reference reference; |
114 | |
115 | /** |
116 | * The default constructor value-initializes member @p current. |
117 | * If it is a pointer, that means it is zero-initialized. |
118 | */ |
119 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
120 | // 235 No specification of default ctor for reverse_iterator |
121 | reverse_iterator() : current() { } |
122 | |
123 | /** |
124 | * This %iterator will move in the opposite direction that @p x does. |
125 | */ |
126 | explicit |
127 | reverse_iterator(iterator_type __x) : current(__x) { } |
128 | |
129 | /** |
130 | * The copy constructor is normal. |
131 | */ |
132 | reverse_iterator(const reverse_iterator& __x) |
133 | : current(__x.current) { } |
134 | |
135 | /** |
136 | * A %reverse_iterator across other types can be copied if the |
137 | * underlying %iterator can be converted to the type of @c current. |
138 | */ |
139 | template<typename _Iter> |
140 | reverse_iterator(const reverse_iterator<_Iter>& __x) |
141 | : current(__x.base()) { } |
142 | |
143 | /** |
144 | * @return @c current, the %iterator used for underlying work. |
145 | */ |
146 | iterator_type |
147 | base() const |
148 | { return current; } |
149 | |
150 | /** |
151 | * @return A reference to the value at @c --current |
152 | * |
153 | * This requires that @c --current is dereferenceable. |
154 | * |
155 | * @warning This implementation requires that for an iterator of the |
156 | * underlying iterator type, @c x, a reference obtained by |
157 | * @c *x remains valid after @c x has been modified or |
158 | * destroyed. This is a bug: http://gcc.gnu.org/PR51823 |
159 | */ |
160 | reference |
161 | operator*() const |
162 | { |
163 | _Iterator __tmp = current; |
164 | return *--__tmp; |
165 | } |
166 | |
167 | /** |
168 | * @return A pointer to the value at @c --current |
169 | * |
170 | * This requires that @c --current is dereferenceable. |
171 | */ |
172 | pointer |
173 | operator->() const |
174 | { return &(operator*()); } |
175 | |
176 | /** |
177 | * @return @c *this |
178 | * |
179 | * Decrements the underlying iterator. |
180 | */ |
181 | reverse_iterator& |
182 | operator++() |
183 | { |
184 | --current; |
185 | return *this; |
186 | } |
187 | |
188 | /** |
189 | * @return The original value of @c *this |
190 | * |
191 | * Decrements the underlying iterator. |
192 | */ |
193 | reverse_iterator |
194 | operator++(int) |
195 | { |
196 | reverse_iterator __tmp = *this; |
197 | --current; |
198 | return __tmp; |
199 | } |
200 | |
201 | /** |
202 | * @return @c *this |
203 | * |
204 | * Increments the underlying iterator. |
205 | */ |
206 | reverse_iterator& |
207 | operator--() |
208 | { |
209 | ++current; |
210 | return *this; |
211 | } |
212 | |
213 | /** |
214 | * @return A reverse_iterator with the previous value of @c *this |
215 | * |
216 | * Increments the underlying iterator. |
217 | */ |
218 | reverse_iterator |
219 | operator--(int) |
220 | { |
221 | reverse_iterator __tmp = *this; |
222 | ++current; |
223 | return __tmp; |
224 | } |
225 | |
226 | /** |
227 | * @return A reverse_iterator that refers to @c current - @a __n |
228 | * |
229 | * The underlying iterator must be a Random Access Iterator. |
230 | */ |
231 | reverse_iterator |
232 | operator+(difference_type __n) const |
233 | { return reverse_iterator(current - __n); } |
234 | |
235 | /** |
236 | * @return *this |
237 | * |
238 | * Moves the underlying iterator backwards @a __n steps. |
239 | * The underlying iterator must be a Random Access Iterator. |
240 | */ |
241 | reverse_iterator& |
242 | operator+=(difference_type __n) |
243 | { |
244 | current -= __n; |
245 | return *this; |
246 | } |
247 | |
248 | /** |
249 | * @return A reverse_iterator that refers to @c current - @a __n |
250 | * |
251 | * The underlying iterator must be a Random Access Iterator. |
252 | */ |
253 | reverse_iterator |
254 | operator-(difference_type __n) const |
255 | { return reverse_iterator(current + __n); } |
256 | |
257 | /** |
258 | * @return *this |
259 | * |
260 | * Moves the underlying iterator forwards @a __n steps. |
261 | * The underlying iterator must be a Random Access Iterator. |
262 | */ |
263 | reverse_iterator& |
264 | operator-=(difference_type __n) |
265 | { |
266 | current += __n; |
267 | return *this; |
268 | } |
269 | |
270 | /** |
271 | * @return The value at @c current - @a __n - 1 |
272 | * |
273 | * The underlying iterator must be a Random Access Iterator. |
274 | */ |
275 | reference |
276 | operator[](difference_type __n) const |
277 | { return *(*this + __n); } |
278 | }; |
279 | |
280 | //@{ |
281 | /** |
282 | * @param __x A %reverse_iterator. |
283 | * @param __y A %reverse_iterator. |
284 | * @return A simple bool. |
285 | * |
286 | * Reverse iterators forward many operations to their underlying base() |
287 | * iterators. Others are implemented in terms of one another. |
288 | * |
289 | */ |
290 | template<typename _Iterator> |
291 | inline bool |
292 | operator==(const reverse_iterator<_Iterator>& __x, |
293 | const reverse_iterator<_Iterator>& __y) |
294 | { return __x.base() == __y.base(); } |
295 | |
296 | template<typename _Iterator> |
297 | inline bool |
298 | operator<(const reverse_iterator<_Iterator>& __x, |
299 | const reverse_iterator<_Iterator>& __y) |
300 | { return __y.base() < __x.base(); } |
301 | |
302 | template<typename _Iterator> |
303 | inline bool |
304 | operator!=(const reverse_iterator<_Iterator>& __x, |
305 | const reverse_iterator<_Iterator>& __y) |
306 | { return !(__x == __y); } |
307 | |
308 | template<typename _Iterator> |
309 | inline bool |
310 | operator>(const reverse_iterator<_Iterator>& __x, |
311 | const reverse_iterator<_Iterator>& __y) |
312 | { return __y < __x; } |
313 | |
314 | template<typename _Iterator> |
315 | inline bool |
316 | operator<=(const reverse_iterator<_Iterator>& __x, |
317 | const reverse_iterator<_Iterator>& __y) |
318 | { return !(__y < __x); } |
319 | |
320 | template<typename _Iterator> |
321 | inline bool |
322 | operator>=(const reverse_iterator<_Iterator>& __x, |
323 | const reverse_iterator<_Iterator>& __y) |
324 | { return !(__x < __y); } |
325 | |
326 | template<typename _Iterator> |
327 | 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 | #if __cplusplus >= 201103L |
392 | // Same as C++14 make_reverse_iterator but used in C++03 mode too. |
393 | template<typename _Iterator> |
394 | inline reverse_iterator<_Iterator> |
395 | __make_reverse_iterator(_Iterator __i) |
396 | { return reverse_iterator<_Iterator>(__i); } |
397 | |
398 | # if __cplusplus > 201103L |
399 | # define __cpp_lib_make_reverse_iterator 201402 |
400 | |
401 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
402 | // DR 2285. make_reverse_iterator |
403 | /// Generator function for reverse_iterator. |
404 | template<typename _Iterator> |
405 | inline reverse_iterator<_Iterator> |
406 | make_reverse_iterator(_Iterator __i) |
407 | { return reverse_iterator<_Iterator>(__i); } |
408 | # endif |
409 | #endif |
410 | |
411 | #if __cplusplus >= 201103L |
412 | template<typename _Iterator> |
413 | auto |
414 | __niter_base(reverse_iterator<_Iterator> __it) |
415 | -> decltype(__make_reverse_iterator(__niter_base(__it.base()))) |
416 | { return __make_reverse_iterator(__niter_base(__it.base())); } |
417 | |
418 | template<typename _Iterator> |
419 | struct __is_move_iterator<reverse_iterator<_Iterator> > |
420 | : __is_move_iterator<_Iterator> |
421 | { }; |
422 | |
423 | template<typename _Iterator> |
424 | auto |
425 | __miter_base(reverse_iterator<_Iterator> __it) |
426 | -> decltype(__make_reverse_iterator(__miter_base(__it.base()))) |
427 | { return __make_reverse_iterator(__miter_base(__it.base())); } |
428 | #endif |
429 | |
430 | // 24.4.2.2.1 back_insert_iterator |
431 | /** |
432 | * @brief Turns assignment into insertion. |
433 | * |
434 | * These are output iterators, constructed from a container-of-T. |
435 | * Assigning a T to the iterator appends it to the container using |
436 | * push_back. |
437 | * |
438 | * Tip: Using the back_inserter function to create these iterators can |
439 | * save typing. |
440 | */ |
441 | template<typename _Container> |
442 | class back_insert_iterator |
443 | : public iterator<output_iterator_tag, void, void, void, void> |
444 | { |
445 | protected: |
446 | _Container* container; |
447 | |
448 | public: |
449 | /// A nested typedef for the type of whatever container you used. |
450 | typedef _Container container_type; |
451 | |
452 | /// The only way to create this %iterator is with a container. |
453 | explicit |
454 | back_insert_iterator(_Container& __x) |
455 | : container(std::__addressof(__x)) { } |
456 | |
457 | /** |
458 | * @param __value An instance of whatever type |
459 | * container_type::const_reference is; presumably a |
460 | * reference-to-const T for container<T>. |
461 | * @return This %iterator, for chained operations. |
462 | * |
463 | * This kind of %iterator doesn't really have a @a position in the |
464 | * container (you can think of the position as being permanently at |
465 | * the end, if you like). Assigning a value to the %iterator will |
466 | * always append the value to the end of the container. |
467 | */ |
468 | #if __cplusplus < 201103L |
469 | back_insert_iterator& |
470 | operator=(typename _Container::const_reference __value) |
471 | { |
472 | container->push_back(__value); |
473 | return *this; |
474 | } |
475 | #else |
476 | back_insert_iterator& |
477 | operator=(const typename _Container::value_type& __value) |
478 | { |
479 | container->push_back(__value); |
480 | return *this; |
481 | } |
482 | |
483 | back_insert_iterator& |
484 | operator=(typename _Container::value_type&& __value) |
485 | { |
486 | container->push_back(std::move(__value)); |
487 | return *this; |
488 | } |
489 | #endif |
490 | |
491 | /// Simply returns *this. |
492 | back_insert_iterator& |
493 | operator*() |
494 | { return *this; } |
495 | |
496 | /// Simply returns *this. (This %iterator does not @a move.) |
497 | back_insert_iterator& |
498 | operator++() |
499 | { return *this; } |
500 | |
501 | /// Simply returns *this. (This %iterator does not @a move.) |
502 | back_insert_iterator |
503 | operator++(int) |
504 | { return *this; } |
505 | }; |
506 | |
507 | /** |
508 | * @param __x A container of arbitrary type. |
509 | * @return An instance of back_insert_iterator working on @p __x. |
510 | * |
511 | * This wrapper function helps in creating back_insert_iterator instances. |
512 | * Typing the name of the %iterator requires knowing the precise full |
513 | * type of the container, which can be tedious and impedes generic |
514 | * programming. Using this function lets you take advantage of automatic |
515 | * template parameter deduction, making the compiler match the correct |
516 | * types for you. |
517 | */ |
518 | template<typename _Container> |
519 | inline back_insert_iterator<_Container> |
520 | back_inserter(_Container& __x) |
521 | { return back_insert_iterator<_Container>(__x); } |
522 | |
523 | /** |
524 | * @brief Turns assignment into insertion. |
525 | * |
526 | * These are output iterators, constructed from a container-of-T. |
527 | * Assigning a T to the iterator prepends it to the container using |
528 | * push_front. |
529 | * |
530 | * Tip: Using the front_inserter function to create these iterators can |
531 | * save typing. |
532 | */ |
533 | template<typename _Container> |
534 | class front_insert_iterator |
535 | : public iterator<output_iterator_tag, void, void, void, void> |
536 | { |
537 | protected: |
538 | _Container* container; |
539 | |
540 | public: |
541 | /// A nested typedef for the type of whatever container you used. |
542 | typedef _Container container_type; |
543 | |
544 | /// The only way to create this %iterator is with a container. |
545 | explicit front_insert_iterator(_Container& __x) |
546 | : container(std::__addressof(__x)) { } |
547 | |
548 | /** |
549 | * @param __value An instance of whatever type |
550 | * container_type::const_reference is; presumably a |
551 | * reference-to-const T for container<T>. |
552 | * @return This %iterator, for chained operations. |
553 | * |
554 | * This kind of %iterator doesn't really have a @a position in the |
555 | * container (you can think of the position as being permanently at |
556 | * the front, if you like). Assigning a value to the %iterator will |
557 | * always prepend the value to the front of the container. |
558 | */ |
559 | #if __cplusplus < 201103L |
560 | front_insert_iterator& |
561 | operator=(typename _Container::const_reference __value) |
562 | { |
563 | container->push_front(__value); |
564 | return *this; |
565 | } |
566 | #else |
567 | front_insert_iterator& |
568 | operator=(const typename _Container::value_type& __value) |
569 | { |
570 | container->push_front(__value); |
571 | return *this; |
572 | } |
573 | |
574 | front_insert_iterator& |
575 | operator=(typename _Container::value_type&& __value) |
576 | { |
577 | container->push_front(std::move(__value)); |
578 | return *this; |
579 | } |
580 | #endif |
581 | |
582 | /// Simply returns *this. |
583 | front_insert_iterator& |
584 | operator*() |
585 | { return *this; } |
586 | |
587 | /// Simply returns *this. (This %iterator does not @a move.) |
588 | front_insert_iterator& |
589 | operator++() |
590 | { return *this; } |
591 | |
592 | /// Simply returns *this. (This %iterator does not @a move.) |
593 | front_insert_iterator |
594 | operator++(int) |
595 | { return *this; } |
596 | }; |
597 | |
598 | /** |
599 | * @param __x A container of arbitrary type. |
600 | * @return An instance of front_insert_iterator working on @p x. |
601 | * |
602 | * This wrapper function helps in creating front_insert_iterator instances. |
603 | * Typing the name of the %iterator requires knowing the precise full |
604 | * type of the container, which can be tedious and impedes generic |
605 | * programming. Using this function lets you take advantage of automatic |
606 | * template parameter deduction, making the compiler match the correct |
607 | * types for you. |
608 | */ |
609 | template<typename _Container> |
610 | inline front_insert_iterator<_Container> |
611 | front_inserter(_Container& __x) |
612 | { return front_insert_iterator<_Container>(__x); } |
613 | |
614 | /** |
615 | * @brief Turns assignment into insertion. |
616 | * |
617 | * These are output iterators, constructed from a container-of-T. |
618 | * Assigning a T to the iterator inserts it in the container at the |
619 | * %iterator's position, rather than overwriting the value at that |
620 | * position. |
621 | * |
622 | * (Sequences will actually insert a @e copy of the value before the |
623 | * %iterator's position.) |
624 | * |
625 | * Tip: Using the inserter function to create these iterators can |
626 | * save typing. |
627 | */ |
628 | template<typename _Container> |
629 | class insert_iterator |
630 | : public iterator<output_iterator_tag, void, void, void, void> |
631 | { |
632 | protected: |
633 | _Container* container; |
634 | typename _Container::iterator iter; |
635 | |
636 | public: |
637 | /// A nested typedef for the type of whatever container you used. |
638 | typedef _Container container_type; |
639 | |
640 | /** |
641 | * The only way to create this %iterator is with a container and an |
642 | * initial position (a normal %iterator into the container). |
643 | */ |
644 | insert_iterator(_Container& __x, typename _Container::iterator __i) |
645 | : container(std::__addressof(__x)), iter(__i) {} |
646 | |
647 | /** |
648 | * @param __value An instance of whatever type |
649 | * container_type::const_reference is; presumably a |
650 | * reference-to-const T for container<T>. |
651 | * @return This %iterator, for chained operations. |
652 | * |
653 | * This kind of %iterator maintains its own position in the |
654 | * container. Assigning a value to the %iterator will insert the |
655 | * value into the container at the place before the %iterator. |
656 | * |
657 | * The position is maintained such that subsequent assignments will |
658 | * insert values immediately after one another. For example, |
659 | * @code |
660 | * // vector v contains A and Z |
661 | * |
662 | * insert_iterator i (v, ++v.begin()); |
663 | * i = 1; |
664 | * i = 2; |
665 | * i = 3; |
666 | * |
667 | * // vector v contains A, 1, 2, 3, and Z |
668 | * @endcode |
669 | */ |
670 | #if __cplusplus < 201103L |
671 | insert_iterator& |
672 | operator=(typename _Container::const_reference __value) |
673 | { |
674 | iter = container->insert(iter, __value); |
675 | ++iter; |
676 | return *this; |
677 | } |
678 | #else |
679 | insert_iterator& |
680 | operator=(const typename _Container::value_type& __value) |
681 | { |
682 | iter = container->insert(iter, __value); |
683 | ++iter; |
684 | return *this; |
685 | } |
686 | |
687 | insert_iterator& |
688 | operator=(typename _Container::value_type&& __value) |
689 | { |
690 | iter = container->insert(iter, std::move(__value)); |
691 | ++iter; |
692 | return *this; |
693 | } |
694 | #endif |
695 | |
696 | /// Simply returns *this. |
697 | insert_iterator& |
698 | operator*() |
699 | { return *this; } |
700 | |
701 | /// Simply returns *this. (This %iterator does not @a move.) |
702 | insert_iterator& |
703 | operator++() |
704 | { return *this; } |
705 | |
706 | /// Simply returns *this. (This %iterator does not @a move.) |
707 | insert_iterator& |
708 | operator++(int) |
709 | { return *this; } |
710 | }; |
711 | |
712 | /** |
713 | * @param __x A container of arbitrary type. |
714 | * @return An instance of insert_iterator working on @p __x. |
715 | * |
716 | * This wrapper function helps in creating insert_iterator instances. |
717 | * Typing the name of the %iterator requires knowing the precise full |
718 | * type of the container, which can be tedious and impedes generic |
719 | * programming. Using this function lets you take advantage of automatic |
720 | * template parameter deduction, making the compiler match the correct |
721 | * types for you. |
722 | */ |
723 | template<typename _Container, typename _Iterator> |
724 | inline insert_iterator<_Container> |
725 | inserter(_Container& __x, _Iterator __i) |
726 | { |
727 | return insert_iterator<_Container>(__x, |
728 | typename _Container::iterator(__i)); |
729 | } |
730 | |
731 | // @} group iterators |
732 | |
733 | _GLIBCXX_END_NAMESPACE_VERSION |
734 | } // namespace |
735 | |
736 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
737 | { |
738 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
739 | |
740 | // This iterator adapter is @a normal in the sense that it does not |
741 | // change the semantics of any of the operators of its iterator |
742 | // parameter. Its primary purpose is to convert an iterator that is |
743 | // not a class, e.g. a pointer, into an iterator that is a class. |
744 | // The _Container parameter exists solely so that different containers |
745 | // using this template can instantiate different types, even if the |
746 | // _Iterator parameter is the same. |
747 | using std::iterator_traits; |
748 | using std::iterator; |
749 | template<typename _Iterator, typename _Container> |
750 | class __normal_iterator |
751 | { |
752 | protected: |
753 | _Iterator _M_current; |
754 | |
755 | typedef iterator_traits<_Iterator> __traits_type; |
756 | |
757 | public: |
758 | typedef _Iterator iterator_type; |
759 | typedef typename __traits_type::iterator_category iterator_category; |
760 | typedef typename __traits_type::value_type value_type; |
761 | typedef typename __traits_type::difference_type difference_type; |
762 | typedef typename __traits_type::reference reference; |
763 | typedef typename __traits_type::pointer pointer; |
764 | |
765 | _GLIBCXX_CONSTEXPR __normal_iterator() _GLIBCXX_NOEXCEPT |
766 | : _M_current(_Iterator()) { } |
767 | |
768 | explicit |
769 | __normal_iterator(const _Iterator& __i) _GLIBCXX_NOEXCEPT |
770 | : _M_current(__i) { } |
771 | |
772 | // Allow iterator to const_iterator conversion |
773 | template<typename _Iter> |
774 | __normal_iterator(const __normal_iterator<_Iter, |
775 | typename __enable_if< |
776 | (std::__are_same<_Iter, typename _Container::pointer>::__value), |
777 | _Container>::__type>& __i) _GLIBCXX_NOEXCEPT |
778 | : _M_current(__i.base()) { } |
779 | |
780 | // Forward iterator requirements |
781 | reference |
782 | operator*() const _GLIBCXX_NOEXCEPT |
783 | { return *_M_current; } |
784 | |
785 | pointer |
786 | operator->() const _GLIBCXX_NOEXCEPT |
787 | { return _M_current; } |
788 | |
789 | __normal_iterator& |
790 | operator++() _GLIBCXX_NOEXCEPT |
791 | { |
792 | ++_M_current; |
793 | return *this; |
794 | } |
795 | |
796 | __normal_iterator |
797 | operator++(int) _GLIBCXX_NOEXCEPT |
798 | { return __normal_iterator(_M_current++); } |
799 | |
800 | // Bidirectional iterator requirements |
801 | __normal_iterator& |
802 | operator--() _GLIBCXX_NOEXCEPT |
803 | { |
804 | --_M_current; |
805 | return *this; |
806 | } |
807 | |
808 | __normal_iterator |
809 | operator--(int) _GLIBCXX_NOEXCEPT |
810 | { return __normal_iterator(_M_current--); } |
811 | |
812 | // Random access iterator requirements |
813 | reference |
814 | operator[](difference_type __n) const _GLIBCXX_NOEXCEPT |
815 | { return _M_current[__n]; } |
816 | |
817 | __normal_iterator& |
818 | operator+=(difference_type __n) _GLIBCXX_NOEXCEPT |
819 | { _M_current += __n; return *this; } |
820 | |
821 | __normal_iterator |
822 | operator+(difference_type __n) const _GLIBCXX_NOEXCEPT |
823 | { return __normal_iterator(_M_current + __n); } |
824 | |
825 | __normal_iterator& |
826 | operator-=(difference_type __n) _GLIBCXX_NOEXCEPT |
827 | { _M_current -= __n; return *this; } |
828 | |
829 | __normal_iterator |
830 | operator-(difference_type __n) const _GLIBCXX_NOEXCEPT |
831 | { return __normal_iterator(_M_current - __n); } |
832 | |
833 | const _Iterator& |
834 | base() const _GLIBCXX_NOEXCEPT |
835 | { return _M_current; } |
836 | }; |
837 | |
838 | // Note: In what follows, the left- and right-hand-side iterators are |
839 | // allowed to vary in types (conceptually in cv-qualification) so that |
840 | // comparison between cv-qualified and non-cv-qualified iterators be |
841 | // valid. However, the greedy and unfriendly operators in std::rel_ops |
842 | // will make overload resolution ambiguous (when in scope) if we don't |
843 | // provide overloads whose operands are of the same type. Can someone |
844 | // remind me what generic programming is about? -- Gaby |
845 | |
846 | // Forward iterator requirements |
847 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
848 | inline bool |
849 | operator==(const __normal_iterator<_IteratorL, _Container>& __lhs, |
850 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
851 | _GLIBCXX_NOEXCEPT |
852 | { return __lhs.base() == __rhs.base(); } |
853 | |
854 | template<typename _Iterator, typename _Container> |
855 | inline bool |
856 | operator==(const __normal_iterator<_Iterator, _Container>& __lhs, |
857 | const __normal_iterator<_Iterator, _Container>& __rhs) |
858 | _GLIBCXX_NOEXCEPT |
859 | { return __lhs.base() == __rhs.base(); } |
860 | |
861 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
862 | inline bool |
863 | operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs, |
864 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
865 | _GLIBCXX_NOEXCEPT |
866 | { return __lhs.base() != __rhs.base(); } |
867 | |
868 | template<typename _Iterator, typename _Container> |
869 | inline bool |
870 | operator!=(const __normal_iterator<_Iterator, _Container>& __lhs, |
871 | const __normal_iterator<_Iterator, _Container>& __rhs) |
872 | _GLIBCXX_NOEXCEPT |
873 | { return __lhs.base() != __rhs.base(); } |
874 | |
875 | // Random access iterator requirements |
876 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
877 | inline bool |
878 | operator<(const __normal_iterator<_IteratorL, _Container>& __lhs, |
879 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
880 | _GLIBCXX_NOEXCEPT |
881 | { return __lhs.base() < __rhs.base(); } |
882 | |
883 | template<typename _Iterator, typename _Container> |
884 | inline bool |
885 | operator<(const __normal_iterator<_Iterator, _Container>& __lhs, |
886 | const __normal_iterator<_Iterator, _Container>& __rhs) |
887 | _GLIBCXX_NOEXCEPT |
888 | { return __lhs.base() < __rhs.base(); } |
889 | |
890 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
891 | inline bool |
892 | operator>(const __normal_iterator<_IteratorL, _Container>& __lhs, |
893 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
894 | _GLIBCXX_NOEXCEPT |
895 | { return __lhs.base() > __rhs.base(); } |
896 | |
897 | template<typename _Iterator, typename _Container> |
898 | inline bool |
899 | operator>(const __normal_iterator<_Iterator, _Container>& __lhs, |
900 | const __normal_iterator<_Iterator, _Container>& __rhs) |
901 | _GLIBCXX_NOEXCEPT |
902 | { return __lhs.base() > __rhs.base(); } |
903 | |
904 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
905 | inline bool |
906 | operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs, |
907 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
908 | _GLIBCXX_NOEXCEPT |
909 | { return __lhs.base() <= __rhs.base(); } |
910 | |
911 | template<typename _Iterator, typename _Container> |
912 | inline bool |
913 | operator<=(const __normal_iterator<_Iterator, _Container>& __lhs, |
914 | const __normal_iterator<_Iterator, _Container>& __rhs) |
915 | _GLIBCXX_NOEXCEPT |
916 | { return __lhs.base() <= __rhs.base(); } |
917 | |
918 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
919 | inline bool |
920 | operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs, |
921 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
922 | _GLIBCXX_NOEXCEPT |
923 | { return __lhs.base() >= __rhs.base(); } |
924 | |
925 | template<typename _Iterator, typename _Container> |
926 | inline bool |
927 | operator>=(const __normal_iterator<_Iterator, _Container>& __lhs, |
928 | const __normal_iterator<_Iterator, _Container>& __rhs) |
929 | _GLIBCXX_NOEXCEPT |
930 | { return __lhs.base() >= __rhs.base(); } |
931 | |
932 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
933 | // According to the resolution of DR179 not only the various comparison |
934 | // operators but also operator- must accept mixed iterator/const_iterator |
935 | // parameters. |
936 | template<typename _IteratorL, typename _IteratorR, typename _Container> |
937 | #if __cplusplus >= 201103L |
938 | // DR 685. |
939 | inline auto |
940 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, |
941 | const __normal_iterator<_IteratorR, _Container>& __rhs) noexcept |
942 | -> decltype(__lhs.base() - __rhs.base()) |
943 | #else |
944 | inline typename __normal_iterator<_IteratorL, _Container>::difference_type |
945 | operator-(const __normal_iterator<_IteratorL, _Container>& __lhs, |
946 | const __normal_iterator<_IteratorR, _Container>& __rhs) |
947 | #endif |
948 | { return __lhs.base() - __rhs.base(); } |
949 | |
950 | template<typename _Iterator, typename _Container> |
951 | inline typename __normal_iterator<_Iterator, _Container>::difference_type |
952 | operator-(const __normal_iterator<_Iterator, _Container>& __lhs, |
953 | const __normal_iterator<_Iterator, _Container>& __rhs) |
954 | _GLIBCXX_NOEXCEPT |
955 | { return __lhs.base() - __rhs.base(); } |
956 | |
957 | template<typename _Iterator, typename _Container> |
958 | inline __normal_iterator<_Iterator, _Container> |
959 | operator+(typename __normal_iterator<_Iterator, _Container>::difference_type |
960 | __n, const __normal_iterator<_Iterator, _Container>& __i) |
961 | _GLIBCXX_NOEXCEPT |
962 | { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); } |
963 | |
964 | _GLIBCXX_END_NAMESPACE_VERSION |
965 | } // namespace |
966 | |
967 | namespace std _GLIBCXX_VISIBILITY(default) |
968 | { |
969 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
970 | |
971 | template<typename _Iterator, typename _Container> |
972 | _Iterator |
973 | __niter_base(__gnu_cxx::__normal_iterator<_Iterator, _Container> __it) |
974 | { return __it.base(); } |
975 | |
976 | _GLIBCXX_END_NAMESPACE_VERSION |
977 | } // namespace |
978 | |
979 | #if __cplusplus >= 201103L |
980 | |
981 | namespace std _GLIBCXX_VISIBILITY(default) |
982 | { |
983 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
984 | |
985 | /** |
986 | * @addtogroup iterators |
987 | * @{ |
988 | */ |
989 | |
990 | // 24.4.3 Move iterators |
991 | /** |
992 | * Class template move_iterator is an iterator adapter with the same |
993 | * behavior as the underlying iterator except that its dereference |
994 | * operator implicitly converts the value returned by the underlying |
995 | * iterator's dereference operator to an rvalue reference. Some |
996 | * generic algorithms can be called with move iterators to replace |
997 | * copying with moving. |
998 | */ |
999 | template<typename _Iterator> |
1000 | class move_iterator |
1001 | { |
1002 | protected: |
1003 | _Iterator _M_current; |
1004 | |
1005 | typedef iterator_traits<_Iterator> __traits_type; |
1006 | typedef typename __traits_type::reference __base_ref; |
1007 | |
1008 | public: |
1009 | typedef _Iterator iterator_type; |
1010 | typedef typename __traits_type::iterator_category iterator_category; |
1011 | typedef typename __traits_type::value_type value_type; |
1012 | typedef typename __traits_type::difference_type difference_type; |
1013 | // NB: DR 680. |
1014 | typedef _Iterator pointer; |
1015 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1016 | // 2106. move_iterator wrapping iterators returning prvalues |
1017 | typedef typename conditional<is_reference<__base_ref>::value, |
1018 | typename remove_reference<__base_ref>::type&&, |
1019 | __base_ref>::type reference; |
1020 | |
1021 | move_iterator() |
1022 | : _M_current() { } |
1023 | |
1024 | explicit |
1025 | move_iterator(iterator_type __i) |
1026 | : _M_current(__i) { } |
1027 | |
1028 | template<typename _Iter> |
1029 | move_iterator(const move_iterator<_Iter>& __i) |
1030 | : _M_current(__i.base()) { } |
1031 | |
1032 | iterator_type |
1033 | base() const |
1034 | { return _M_current; } |
1035 | |
1036 | reference |
1037 | operator*() const |
1038 | { return static_cast<reference>(*_M_current); } |
1039 | |
1040 | pointer |
1041 | operator->() const |
1042 | { return _M_current; } |
1043 | |
1044 | move_iterator& |
1045 | operator++() |
1046 | { |
1047 | ++_M_current; |
1048 | return *this; |
1049 | } |
1050 | |
1051 | move_iterator |
1052 | operator++(int) |
1053 | { |
1054 | move_iterator __tmp = *this; |
1055 | ++_M_current; |
1056 | return __tmp; |
1057 | } |
1058 | |
1059 | move_iterator& |
1060 | operator--() |
1061 | { |
1062 | --_M_current; |
1063 | return *this; |
1064 | } |
1065 | |
1066 | move_iterator |
1067 | operator--(int) |
1068 | { |
1069 | move_iterator __tmp = *this; |
1070 | --_M_current; |
1071 | return __tmp; |
1072 | } |
1073 | |
1074 | move_iterator |
1075 | operator+(difference_type __n) const |
1076 | { return move_iterator(_M_current + __n); } |
1077 | |
1078 | move_iterator& |
1079 | operator+=(difference_type __n) |
1080 | { |
1081 | _M_current += __n; |
1082 | return *this; |
1083 | } |
1084 | |
1085 | move_iterator |
1086 | operator-(difference_type __n) const |
1087 | { return move_iterator(_M_current - __n); } |
1088 | |
1089 | move_iterator& |
1090 | operator-=(difference_type __n) |
1091 | { |
1092 | _M_current -= __n; |
1093 | return *this; |
1094 | } |
1095 | |
1096 | reference |
1097 | operator[](difference_type __n) const |
1098 | { return std::move(_M_current[__n]); } |
1099 | }; |
1100 | |
1101 | // Note: See __normal_iterator operators note from Gaby to understand |
1102 | // why there are always 2 versions for most of the move_iterator |
1103 | // operators. |
1104 | template<typename _IteratorL, typename _IteratorR> |
1105 | inline bool |
1106 | operator==(const move_iterator<_IteratorL>& __x, |
1107 | const move_iterator<_IteratorR>& __y) |
1108 | { return __x.base() == __y.base(); } |
1109 | |
1110 | template<typename _Iterator> |
1111 | inline bool |
1112 | operator==(const move_iterator<_Iterator>& __x, |
1113 | const move_iterator<_Iterator>& __y) |
1114 | { return __x.base() == __y.base(); } |
1115 | |
1116 | template<typename _IteratorL, typename _IteratorR> |
1117 | inline bool |
1118 | operator!=(const move_iterator<_IteratorL>& __x, |
1119 | const move_iterator<_IteratorR>& __y) |
1120 | { return !(__x == __y); } |
1121 | |
1122 | template<typename _Iterator> |
1123 | inline bool |
1124 | operator!=(const move_iterator<_Iterator>& __x, |
1125 | const move_iterator<_Iterator>& __y) |
1126 | { return !(__x == __y); } |
1127 | |
1128 | template<typename _IteratorL, typename _IteratorR> |
1129 | inline bool |
1130 | operator<(const move_iterator<_IteratorL>& __x, |
1131 | const move_iterator<_IteratorR>& __y) |
1132 | { return __x.base() < __y.base(); } |
1133 | |
1134 | template<typename _Iterator> |
1135 | inline bool |
1136 | operator<(const move_iterator<_Iterator>& __x, |
1137 | const move_iterator<_Iterator>& __y) |
1138 | { return __x.base() < __y.base(); } |
1139 | |
1140 | template<typename _IteratorL, typename _IteratorR> |
1141 | inline bool |
1142 | operator<=(const move_iterator<_IteratorL>& __x, |
1143 | const move_iterator<_IteratorR>& __y) |
1144 | { return !(__y < __x); } |
1145 | |
1146 | template<typename _Iterator> |
1147 | inline bool |
1148 | operator<=(const move_iterator<_Iterator>& __x, |
1149 | const move_iterator<_Iterator>& __y) |
1150 | { return !(__y < __x); } |
1151 | |
1152 | template<typename _IteratorL, typename _IteratorR> |
1153 | inline bool |
1154 | operator>(const move_iterator<_IteratorL>& __x, |
1155 | const move_iterator<_IteratorR>& __y) |
1156 | { return __y < __x; } |
1157 | |
1158 | template<typename _Iterator> |
1159 | inline bool |
1160 | operator>(const move_iterator<_Iterator>& __x, |
1161 | const move_iterator<_Iterator>& __y) |
1162 | { return __y < __x; } |
1163 | |
1164 | template<typename _IteratorL, typename _IteratorR> |
1165 | inline bool |
1166 | operator>=(const move_iterator<_IteratorL>& __x, |
1167 | const move_iterator<_IteratorR>& __y) |
1168 | { return !(__x < __y); } |
1169 | |
1170 | template<typename _Iterator> |
1171 | inline bool |
1172 | operator>=(const move_iterator<_Iterator>& __x, |
1173 | const move_iterator<_Iterator>& __y) |
1174 | { return !(__x < __y); } |
1175 | |
1176 | // DR 685. |
1177 | template<typename _IteratorL, typename _IteratorR> |
1178 | inline auto |
1179 | operator-(const move_iterator<_IteratorL>& __x, |
1180 | const move_iterator<_IteratorR>& __y) |
1181 | -> decltype(__x.base() - __y.base()) |
1182 | { return __x.base() - __y.base(); } |
1183 | |
1184 | template<typename _Iterator> |
1185 | inline auto |
1186 | operator-(const move_iterator<_Iterator>& __x, |
1187 | const move_iterator<_Iterator>& __y) |
1188 | -> decltype(__x.base() - __y.base()) |
1189 | { return __x.base() - __y.base(); } |
1190 | |
1191 | template<typename _Iterator> |
1192 | inline move_iterator<_Iterator> |
1193 | operator+(typename move_iterator<_Iterator>::difference_type __n, |
1194 | const move_iterator<_Iterator>& __x) |
1195 | { return __x + __n; } |
1196 | |
1197 | template<typename _Iterator> |
1198 | inline move_iterator<_Iterator> |
1199 | make_move_iterator(_Iterator __i) |
1200 | { return move_iterator<_Iterator>(__i); } |
1201 | |
1202 | template<typename _Iterator, typename _ReturnType |
1203 | = typename conditional<__move_if_noexcept_cond |
1204 | <typename iterator_traits<_Iterator>::value_type>::value, |
1205 | _Iterator, move_iterator<_Iterator>>::type> |
1206 | inline _ReturnType |
1207 | __make_move_if_noexcept_iterator(_Iterator __i) |
1208 | { return _ReturnType(__i); } |
1209 | |
1210 | // Overload for pointers that matches std::move_if_noexcept more closely, |
1211 | // returning a constant iterator when we don't want to move. |
1212 | template<typename _Tp, typename _ReturnType |
1213 | = typename conditional<__move_if_noexcept_cond<_Tp>::value, |
1214 | const _Tp*, move_iterator<_Tp*>>::type> |
1215 | inline _ReturnType |
1216 | __make_move_if_noexcept_iterator(_Tp* __i) |
1217 | { return _ReturnType(__i); } |
1218 | |
1219 | // @} group iterators |
1220 | |
1221 | template<typename _Iterator> |
1222 | auto |
1223 | __niter_base(move_iterator<_Iterator> __it) |
1224 | -> decltype(make_move_iterator(__niter_base(__it.base()))) |
1225 | { return make_move_iterator(__niter_base(__it.base())); } |
1226 | |
1227 | template<typename _Iterator> |
1228 | struct __is_move_iterator<move_iterator<_Iterator> > |
1229 | { |
1230 | enum { __value = 1 }; |
1231 | typedef __true_type __type; |
1232 | }; |
1233 | |
1234 | template<typename _Iterator> |
1235 | auto |
1236 | __miter_base(move_iterator<_Iterator> __it) |
1237 | -> decltype(__miter_base(__it.base())) |
1238 | { return __miter_base(__it.base()); } |
1239 | |
1240 | _GLIBCXX_END_NAMESPACE_VERSION |
1241 | } // namespace |
1242 | |
1243 | #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) std::make_move_iterator(_Iter) |
1244 | #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) \ |
1245 | std::__make_move_if_noexcept_iterator(_Iter) |
1246 | #else |
1247 | #define _GLIBCXX_MAKE_MOVE_ITERATOR(_Iter) (_Iter) |
1248 | #define _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(_Iter) (_Iter) |
1249 | #endif // C++11 |
1250 | |
1251 | #ifdef _GLIBCXX_DEBUG |
1252 | # include <debug/stl_iterator.h> |
1253 | #endif |
1254 | |
1255 | #endif |
1256 | |