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