2 //===-------------------------- iterator ----------------------------------===//
4 // The LLVM Compiler Infrastructure
6 // This file is dual licensed under the MIT and the University of Illinois Open
7 // Source Licenses. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 #ifndef _LIBCPP_ITERATOR
12 #define _LIBCPP_ITERATOR
20 template<class Iterator>
21 struct iterator_traits
23 typedef typename Iterator::difference_type difference_type;
24 typedef typename Iterator::value_type value_type;
25 typedef typename Iterator::pointer pointer;
26 typedef typename Iterator::reference reference;
27 typedef typename Iterator::iterator_category iterator_category;
31 struct iterator_traits<T*>
33 typedef ptrdiff_t difference_type;
37 typedef random_access_iterator_tag iterator_category;
41 struct iterator_traits<const T*>
43 typedef ptrdiff_t difference_type;
45 typedef const T* pointer;
46 typedef const T& reference;
47 typedef random_access_iterator_tag iterator_category;
50 template<class Category, class T, class Distance = ptrdiff_t,
51 class Pointer = T*, class Reference = T&>
55 typedef Distance difference_type;
56 typedef Pointer pointer;
57 typedef Reference reference;
58 typedef Category iterator_category;
61 struct input_iterator_tag {};
62 struct output_iterator_tag {};
63 struct forward_iterator_tag : public input_iterator_tag {};
64 struct bidirectional_iterator_tag : public forward_iterator_tag {};
65 struct random_access_iterator_tag : public bidirectional_iterator_tag {};
67 // extension: second argument not conforming to C++03
68 template <class InputIterator>
69 void advance(InputIterator& i,
70 typename iterator_traits<InputIterator>::difference_type n);
72 template <class InputIterator>
73 typename iterator_traits<InputIterator>::difference_type
74 distance(InputIterator first, InputIterator last);
76 template <class Iterator>
77 class reverse_iterator
78 : public iterator<typename iterator_traits<Iterator>::iterator_category,
79 typename iterator_traits<Iterator>::value_type,
80 typename iterator_traits<Iterator>::difference_type,
81 typename iterator_traits<Iterator>::pointer,
82 typename iterator_traits<Iterator>::reference>
87 typedef Iterator iterator_type;
88 typedef typename iterator_traits<Iterator>::difference_type difference_type;
89 typedef typename iterator_traits<Iterator>::reference reference;
90 typedef typename iterator_traits<Iterator>::pointer pointer;
93 explicit reverse_iterator(Iterator x);
94 template <class U> reverse_iterator(const reverse_iterator<U>& u);
95 Iterator base() const;
96 reference operator*() const;
97 pointer operator->() const;
98 reverse_iterator& operator++();
99 reverse_iterator operator++(int);
100 reverse_iterator& operator--();
101 reverse_iterator operator--(int);
102 reverse_iterator operator+ (difference_type n) const;
103 reverse_iterator& operator+=(difference_type n);
104 reverse_iterator operator- (difference_type n) const;
105 reverse_iterator& operator-=(difference_type n);
106 reference operator[](difference_type n) const;
109 template <class Iterator1, class Iterator2>
111 operator==(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
113 template <class Iterator1, class Iterator2>
115 operator<(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
117 template <class Iterator1, class Iterator2>
119 operator!=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
121 template <class Iterator1, class Iterator2>
123 operator>(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
125 template <class Iterator1, class Iterator2>
127 operator>=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
129 template <class Iterator1, class Iterator2>
131 operator<=(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
133 template <class Iterator1, class Iterator2>
134 typename reverse_iterator<Iterator1>::difference_type
135 operator-(const reverse_iterator<Iterator1>& x, const reverse_iterator<Iterator2>& y);
137 template <class Iterator>
138 reverse_iterator<Iterator>
139 operator+(typename reverse_iterator<Iterator>::difference_type n, const reverse_iterator<Iterator>& x);
141 template <class Container>
142 class back_insert_iterator
145 Container* container;
147 typedef Container container_type;
148 typedef void value_type;
149 typedef void difference_type;
150 typedef back_insert_iterator<Cont>& reference;
151 typedef void pointer;
153 explicit back_insert_iterator(Container& x);
154 back_insert_iterator& operator=(const typename Container::value_type& value);
155 back_insert_iterator& operator*();
156 back_insert_iterator& operator++();
157 back_insert_iterator operator++(int);
160 template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
162 template <class Container>
163 class front_insert_iterator
166 Container* container;
168 typedef Container container_type;
169 typedef void value_type;
170 typedef void difference_type;
171 typedef front_insert_iterator<Cont>& reference;
172 typedef void pointer;
174 explicit front_insert_iterator(Container& x);
175 front_insert_iterator& operator=(const typename Container::value_type& value);
176 front_insert_iterator& operator*();
177 front_insert_iterator& operator++();
178 front_insert_iterator operator++(int);
181 template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
183 template <class Container>
184 class insert_iterator
187 Container* container;
188 typename Container::iterator iter;
190 typedef Container container_type;
191 typedef void value_type;
192 typedef void difference_type;
193 typedef insert_iterator<Cont>& reference;
194 typedef void pointer;
196 insert_iterator(Container& x, typename Container::iterator i);
197 insert_iterator& operator=(const typename Container::value_type& value);
198 insert_iterator& operator*();
199 insert_iterator& operator++();
200 insert_iterator& operator++(int);
203 template <class Container, class Iterator>
204 insert_iterator<Container> inserter(Container& x, Iterator i);
206 template <class T, class charT = char, class traits = char_traits<charT>, class Distance = ptrdiff_t>
207 class istream_iterator
208 : public iterator<input_iterator_tag, T, Distance, const T*, const T&>
211 typedef charT char_type;
212 typedef traits traits_type;
213 typedef basic_istream<charT,traits> istream_type;
216 istream_iterator(istream_type& s);
217 istream_iterator(const istream_iterator& x);
220 const T& operator*() const;
221 const T* operator->() const;
222 istream_iterator& operator++();
223 istream_iterator operator++(int);
226 template <class T, class charT, class traits, class Distance>
227 bool operator==(const istream_iterator<T,charT,traits,Distance>& x,
228 const istream_iterator<T,charT,traits,Distance>& y);
229 template <class T, class charT, class traits, class Distance>
230 bool operator!=(const istream_iterator<T,charT,traits,Distance>& x,
231 const istream_iterator<T,charT,traits,Distance>& y);
233 template <class T, class charT = char, class traits = char_traits<charT> >
234 class ostream_iterator
235 : public iterator<output_iterator_tag, void, void, void ,void>
238 typedef charT char_type;
239 typedef traits traits_type;
240 typedef basic_ostream<charT,traits> ostream_type;
242 ostream_iterator(ostream_type& s);
243 ostream_iterator(ostream_type& s, const charT* delimiter);
244 ostream_iterator(const ostream_iterator& x);
246 ostream_iterator& operator=(const T& value);
248 ostream_iterator& operator*();
249 ostream_iterator& operator++();
250 ostream_iterator& operator++(int);
253 template<class charT, class traits = char_traits<charT> >
254 class istreambuf_iterator
255 : public iterator<input_iterator_tag, charT,
256 typename traits::off_type, unspecified,
260 typedef charT char_type;
261 typedef traits traits_type;
262 typedef typename traits::int_type int_type;
263 typedef basic_streambuf<charT,traits> streambuf_type;
264 typedef basic_istream<charT,traits> istream_type;
266 istreambuf_iterator() throw();
267 istreambuf_iterator(istream_type& s) throw();
268 istreambuf_iterator(streambuf_type* s) throw();
269 istreambuf_iterator(a-private-type) throw();
271 charT operator*() const;
272 pointer operator->() const;
273 istreambuf_iterator& operator++();
274 a-private-type operator++(int);
276 bool equal(const istreambuf_iterator& b) const;
279 template <class charT, class traits>
280 bool operator==(const istreambuf_iterator<charT,traits>& a,
281 const istreambuf_iterator<charT,traits>& b);
282 template <class charT, class traits>
283 bool operator!=(const istreambuf_iterator<charT,traits>& a,
284 const istreambuf_iterator<charT,traits>& b);
286 template <class charT, class traits = char_traits<charT> >
287 class ostreambuf_iterator
288 : public iterator<output_iterator_tag, void, void, void, void>
291 typedef charT char_type;
292 typedef traits traits_type;
293 typedef basic_streambuf<charT,traits> streambuf_type;
294 typedef basic_ostream<charT,traits> ostream_type;
296 ostreambuf_iterator(ostream_type& s) throw();
297 ostreambuf_iterator(streambuf_type* s) throw();
298 ostreambuf_iterator& operator=(charT c);
299 ostreambuf_iterator& operator*();
300 ostreambuf_iterator& operator++();
301 ostreambuf_iterator& operator++(int);
302 bool failed() const throw();
305 template <class C> auto begin(C& c) -> decltype(c.begin());
306 template <class C> auto begin(const C& c) -> decltype(c.begin());
307 template <class C> auto end(C& c) -> decltype(c.end());
308 template <class C> auto end(const C& c) -> decltype(c.end());
309 template <class T, size_t N> T* begin(T (&array)[N]);
310 template <class T, size_t N> T* end(T (&array)[N]);
317 #include <type_traits>
324 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
325 #pragma GCC system_header
328 _LIBCPP_BEGIN_NAMESPACE_STD
330 struct _LIBCPP_VISIBLE input_iterator_tag {};
331 struct _LIBCPP_VISIBLE output_iterator_tag {};
332 struct _LIBCPP_VISIBLE forward_iterator_tag : public input_iterator_tag {};
333 struct _LIBCPP_VISIBLE bidirectional_iterator_tag : public forward_iterator_tag {};
334 struct _LIBCPP_VISIBLE random_access_iterator_tag : public bidirectional_iterator_tag {};
337 struct __has_iterator_category
340 struct __two {char _; char __;};
341 template <class _Up> static __two __test(...);
342 template <class _Up> static char __test(typename _Up::iterator_category* = 0);
344 static const bool value = sizeof(__test<_Tp>(0)) == 1;
347 template <class _Iter, bool> struct ____iterator_traits {};
349 template <class _Iter>
350 struct ____iterator_traits<_Iter, true>
352 typedef typename _Iter::difference_type difference_type;
353 typedef typename _Iter::value_type value_type;
354 typedef typename _Iter::pointer pointer;
355 typedef typename _Iter::reference reference;
356 typedef typename _Iter::iterator_category iterator_category;
359 template <class _Iter, bool> struct __iterator_traits {};
361 template <class _Iter>
362 struct __iterator_traits<_Iter, true>
363 : ____iterator_traits
366 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
367 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
371 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
372 // exists. Else iterator_traits<Iterator> will be an empty class. This is a
373 // conforming extension which allows some programs to compile and behave as
374 // the client expects instead of failing at compile time.
376 template <class _Iter>
377 struct _LIBCPP_VISIBLE iterator_traits
378 : __iterator_traits<_Iter, __has_iterator_category<_Iter>::value> {};
381 struct _LIBCPP_VISIBLE iterator_traits<_Tp*>
383 typedef ptrdiff_t difference_type;
384 typedef typename remove_const<_Tp>::type value_type;
385 typedef _Tp* pointer;
386 typedef _Tp& reference;
387 typedef random_access_iterator_tag iterator_category;
390 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
391 struct __has_iterator_category_convertible_to
392 : public integral_constant<bool, is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
395 template <class _Tp, class _Up>
396 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : public false_type {};
399 struct __is_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
402 struct __is_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
405 struct __is_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
408 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
410 template<class _Category, class _Tp, class _Distance = ptrdiff_t,
411 class _Pointer = _Tp*, class _Reference = _Tp&>
412 struct _LIBCPP_VISIBLE iterator
414 typedef _Tp value_type;
415 typedef _Distance difference_type;
416 typedef _Pointer pointer;
417 typedef _Reference reference;
418 typedef _Category iterator_category;
421 template <class _InputIter>
422 inline _LIBCPP_INLINE_VISIBILITY
423 void __advance(_InputIter& __i,
424 typename iterator_traits<_InputIter>::difference_type __n, input_iterator_tag)
426 for (; __n > 0; --__n)
430 template <class _BiDirIter>
431 inline _LIBCPP_INLINE_VISIBILITY
432 void __advance(_BiDirIter& __i,
433 typename iterator_traits<_BiDirIter>::difference_type __n, bidirectional_iterator_tag)
436 for (; __n > 0; --__n)
439 for (; __n < 0; ++__n)
443 template <class _RandIter>
444 inline _LIBCPP_INLINE_VISIBILITY
445 void __advance(_RandIter& __i,
446 typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
451 template <class _InputIter>
452 inline _LIBCPP_INLINE_VISIBILITY
453 void advance(_InputIter& __i,
454 typename iterator_traits<_InputIter>::difference_type __n)
456 __advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());
459 template <class _InputIter>
460 inline _LIBCPP_INLINE_VISIBILITY
461 typename iterator_traits<_InputIter>::difference_type
462 __distance(_InputIter __first, _InputIter __last, input_iterator_tag)
464 typename iterator_traits<_InputIter>::difference_type __r(0);
465 for (; __first != __last; ++__first)
470 template <class _RandIter>
471 inline _LIBCPP_INLINE_VISIBILITY
472 typename iterator_traits<_RandIter>::difference_type
473 __distance(_RandIter __first, _RandIter __last, random_access_iterator_tag)
475 return __last - __first;
478 template <class _InputIter>
479 inline _LIBCPP_INLINE_VISIBILITY
480 typename iterator_traits<_InputIter>::difference_type
481 distance(_InputIter __first, _InputIter __last)
483 return __distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
486 template <class _ForwardIter>
487 inline _LIBCPP_INLINE_VISIBILITY
489 next(_ForwardIter __x,
490 typename iterator_traits<_ForwardIter>::difference_type __n = 1,
491 typename enable_if<__is_forward_iterator<_ForwardIter>::value>::type* = 0)
493 _VSTD::advance(__x, __n);
497 template <class _BidiretionalIter>
498 inline _LIBCPP_INLINE_VISIBILITY
500 prev(_BidiretionalIter __x,
501 typename iterator_traits<_BidiretionalIter>::difference_type __n = 1,
502 typename enable_if<__is_bidirectional_iterator<_BidiretionalIter>::value>::type* = 0)
504 _VSTD::advance(__x, -__n);
508 template <class _Iter>
509 class _LIBCPP_VISIBLE reverse_iterator
510 : public iterator<typename iterator_traits<_Iter>::iterator_category,
511 typename iterator_traits<_Iter>::value_type,
512 typename iterator_traits<_Iter>::difference_type,
513 typename iterator_traits<_Iter>::pointer,
514 typename iterator_traits<_Iter>::reference>
521 typedef _Iter iterator_type;
522 typedef typename iterator_traits<_Iter>::difference_type difference_type;
523 typedef typename iterator_traits<_Iter>::reference reference;
524 typedef typename iterator_traits<_Iter>::pointer pointer;
526 _LIBCPP_INLINE_VISIBILITY reverse_iterator() : current() {}
527 _LIBCPP_INLINE_VISIBILITY explicit reverse_iterator(_Iter __x) : __t(__x), current(__x) {}
528 template <class _Up> _LIBCPP_INLINE_VISIBILITY reverse_iterator(const reverse_iterator<_Up>& __u)
529 : __t(__u.base()), current(__u.base()) {}
530 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return current;}
531 _LIBCPP_INLINE_VISIBILITY reference operator*() const {__t = current; return *--__t;}
532 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &(operator*());}
533 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator++() {--current; return *this;}
534 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator++(int)
535 {reverse_iterator __tmp(*this); --current; return __tmp;}
536 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator--() {++current; return *this;}
537 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator--(int)
538 {reverse_iterator __tmp(*this); ++current; return __tmp;}
539 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator+ (difference_type __n) const
540 {return reverse_iterator(current - __n);}
541 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator+=(difference_type __n)
542 {current -= __n; return *this;}
543 _LIBCPP_INLINE_VISIBILITY reverse_iterator operator- (difference_type __n) const
544 {return reverse_iterator(current + __n);}
545 _LIBCPP_INLINE_VISIBILITY reverse_iterator& operator-=(difference_type __n)
546 {current += __n; return *this;}
547 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
548 {return current[-__n-1];}
551 template <class _Iter1, class _Iter2>
552 inline _LIBCPP_INLINE_VISIBILITY
554 operator==(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
556 return __x.base() == __y.base();
559 template <class _Iter1, class _Iter2>
560 inline _LIBCPP_INLINE_VISIBILITY
562 operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
564 return __x.base() > __y.base();
567 template <class _Iter1, class _Iter2>
568 inline _LIBCPP_INLINE_VISIBILITY
570 operator!=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
572 return __x.base() != __y.base();
575 template <class _Iter1, class _Iter2>
576 inline _LIBCPP_INLINE_VISIBILITY
578 operator>(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
580 return __x.base() < __y.base();
583 template <class _Iter1, class _Iter2>
584 inline _LIBCPP_INLINE_VISIBILITY
586 operator>=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
588 return __x.base() <= __y.base();
591 template <class _Iter1, class _Iter2>
592 inline _LIBCPP_INLINE_VISIBILITY
594 operator<=(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
596 return __x.base() >= __y.base();
599 template <class _Iter1, class _Iter2>
600 inline _LIBCPP_INLINE_VISIBILITY
601 typename reverse_iterator<_Iter1>::difference_type
602 operator-(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
604 return __y.base() - __x.base();
607 template <class _Iter>
608 inline _LIBCPP_INLINE_VISIBILITY
609 reverse_iterator<_Iter>
610 operator+(typename reverse_iterator<_Iter>::difference_type __n, const reverse_iterator<_Iter>& __x)
612 return reverse_iterator<_Iter>(__x.base() - __n);
615 template <class _Container>
616 class _LIBCPP_VISIBLE back_insert_iterator
617 : public iterator<output_iterator_tag,
621 back_insert_iterator<_Container>&>
624 _Container* container;
626 typedef _Container container_type;
628 _LIBCPP_INLINE_VISIBILITY explicit back_insert_iterator(_Container& __x) : container(&__x) {}
629 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(const typename _Container::value_type& __value_)
630 {container->push_back(__value_); return *this;}
631 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
632 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator=(typename _Container::value_type&& __value_)
633 {container->push_back(_VSTD::move(__value_)); return *this;}
634 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
635 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator*() {return *this;}
636 _LIBCPP_INLINE_VISIBILITY back_insert_iterator& operator++() {return *this;}
637 _LIBCPP_INLINE_VISIBILITY back_insert_iterator operator++(int) {return *this;}
640 template <class _Container>
641 inline _LIBCPP_INLINE_VISIBILITY
642 back_insert_iterator<_Container>
643 back_inserter(_Container& __x)
645 return back_insert_iterator<_Container>(__x);
648 template <class _Container>
649 class _LIBCPP_VISIBLE front_insert_iterator
650 : public iterator<output_iterator_tag,
654 front_insert_iterator<_Container>&>
657 _Container* container;
659 typedef _Container container_type;
661 _LIBCPP_INLINE_VISIBILITY explicit front_insert_iterator(_Container& __x) : container(&__x) {}
662 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(const typename _Container::value_type& __value_)
663 {container->push_front(__value_); return *this;}
664 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
665 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator=(typename _Container::value_type&& __value_)
666 {container->push_front(_VSTD::move(__value_)); return *this;}
667 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
668 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator*() {return *this;}
669 _LIBCPP_INLINE_VISIBILITY front_insert_iterator& operator++() {return *this;}
670 _LIBCPP_INLINE_VISIBILITY front_insert_iterator operator++(int) {return *this;}
673 template <class _Container>
674 inline _LIBCPP_INLINE_VISIBILITY
675 front_insert_iterator<_Container>
676 front_inserter(_Container& __x)
678 return front_insert_iterator<_Container>(__x);
681 template <class _Container>
682 class _LIBCPP_VISIBLE insert_iterator
683 : public iterator<output_iterator_tag,
687 insert_iterator<_Container>&>
690 _Container* container;
691 typename _Container::iterator iter;
693 typedef _Container container_type;
695 _LIBCPP_INLINE_VISIBILITY insert_iterator(_Container& __x, typename _Container::iterator __i)
696 : container(&__x), iter(__i) {}
697 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(const typename _Container::value_type& __value_)
698 {iter = container->insert(iter, __value_); ++iter; return *this;}
699 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
700 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator=(typename _Container::value_type&& __value_)
701 {iter = container->insert(iter, _VSTD::move(__value_)); ++iter; return *this;}
702 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
703 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator*() {return *this;}
704 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++() {return *this;}
705 _LIBCPP_INLINE_VISIBILITY insert_iterator& operator++(int) {return *this;}
708 template <class _Container>
709 inline _LIBCPP_INLINE_VISIBILITY
710 insert_iterator<_Container>
711 inserter(_Container& __x, typename _Container::iterator __i)
713 return insert_iterator<_Container>(__x, __i);
716 template <class _Tp, class _CharT = char,
717 class _Traits = char_traits<_CharT>, class _Distance = ptrdiff_t>
718 class _LIBCPP_VISIBLE istream_iterator
719 : public iterator<input_iterator_tag, _Tp, _Distance, const _Tp*, const _Tp&>
722 typedef _CharT char_type;
723 typedef _Traits traits_type;
724 typedef basic_istream<_CharT,_Traits> istream_type;
726 istream_type* __in_stream_;
729 _LIBCPP_INLINE_VISIBILITY istream_iterator() : __in_stream_(0) {}
730 _LIBCPP_INLINE_VISIBILITY istream_iterator(istream_type& __s) : __in_stream_(&__s)
732 if (!(*__in_stream_ >> __value_))
736 _LIBCPP_INLINE_VISIBILITY const _Tp& operator*() const {return __value_;}
737 _LIBCPP_INLINE_VISIBILITY const _Tp* operator->() const {return &(operator*());}
738 _LIBCPP_INLINE_VISIBILITY istream_iterator& operator++()
740 if (!(*__in_stream_ >> __value_))
744 _LIBCPP_INLINE_VISIBILITY istream_iterator operator++(int)
745 {istream_iterator __t(*this); ++(*this); return __t;}
747 friend _LIBCPP_INLINE_VISIBILITY
748 bool operator==(const istream_iterator& __x, const istream_iterator& __y)
749 {return __x.__in_stream_ == __y.__in_stream_;}
751 friend _LIBCPP_INLINE_VISIBILITY
752 bool operator!=(const istream_iterator& __x, const istream_iterator& __y)
753 {return !(__x == __y);}
756 template <class _Tp, class _CharT = char, class _Traits = char_traits<_CharT> >
757 class _LIBCPP_VISIBLE ostream_iterator
758 : public iterator<output_iterator_tag, void, void, void, void>
761 typedef _CharT char_type;
762 typedef _Traits traits_type;
763 typedef basic_ostream<_CharT,_Traits> ostream_type;
765 ostream_type* __out_stream_;
766 const char_type* __delim_;
768 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s)
769 : __out_stream_(&__s), __delim_(0) {}
770 _LIBCPP_INLINE_VISIBILITY ostream_iterator(ostream_type& __s, const _CharT* __delimiter)
771 : __out_stream_(&__s), __delim_(__delimiter) {}
772 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator=(const _Tp& __value_)
774 *__out_stream_ << __value_;
776 *__out_stream_ << __delim_;
780 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator*() {return *this;}
781 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++() {return *this;}
782 _LIBCPP_INLINE_VISIBILITY ostream_iterator& operator++(int) {return *this;}
785 template<class _CharT, class _Traits>
786 class _LIBCPP_VISIBLE istreambuf_iterator
787 : public iterator<input_iterator_tag, _CharT,
788 typename _Traits::off_type, _CharT*,
792 typedef _CharT char_type;
793 typedef _Traits traits_type;
794 typedef typename _Traits::int_type int_type;
795 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
796 typedef basic_istream<_CharT,_Traits> istream_type;
798 streambuf_type* __sbuf_;
803 streambuf_type* __sbuf_;
804 _LIBCPP_INLINE_VISIBILITY __proxy(char_type __c, streambuf_type* __s)
805 : __keep_(__c), __sbuf_(__s) {}
806 friend class istreambuf_iterator;
808 _LIBCPP_INLINE_VISIBILITY char_type operator*() const {return __keep_;}
811 _LIBCPP_INLINE_VISIBILITY
812 void __test_for_eof()
814 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sgetc(), traits_type::eof()))
818 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator() throw() : __sbuf_(0) {}
819 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(istream_type& __s) throw()
820 : __sbuf_(__s.rdbuf()) {__test_for_eof();}
821 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(streambuf_type* __s) throw()
822 : __sbuf_(__s) {__test_for_eof();}
823 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator(const __proxy& __p) throw()
824 : __sbuf_(__p.__sbuf_) {}
826 _LIBCPP_INLINE_VISIBILITY char_type operator*() const
827 {return static_cast<char_type>(__sbuf_->sgetc());}
828 _LIBCPP_INLINE_VISIBILITY char_type* operator->() const {return nullptr;}
829 _LIBCPP_INLINE_VISIBILITY istreambuf_iterator& operator++()
831 if (traits_type::eq_int_type(__sbuf_->snextc(), traits_type::eof()))
835 _LIBCPP_INLINE_VISIBILITY __proxy operator++(int)
837 char_type __c = __sbuf_->sgetc();
839 return __proxy(__c, __sbuf_);
842 _LIBCPP_INLINE_VISIBILITY bool equal(const istreambuf_iterator& __b) const
843 {return (__sbuf_ == 0) == (__b.__sbuf_ == 0);}
846 template <class _CharT, class _Traits>
847 inline _LIBCPP_INLINE_VISIBILITY
848 bool operator==(const istreambuf_iterator<_CharT,_Traits>& __a,
849 const istreambuf_iterator<_CharT,_Traits>& __b)
850 {return __a.equal(__b);}
852 template <class _CharT, class _Traits>
853 inline _LIBCPP_INLINE_VISIBILITY
854 bool operator!=(const istreambuf_iterator<_CharT,_Traits>& __a,
855 const istreambuf_iterator<_CharT,_Traits>& __b)
856 {return !__a.equal(__b);}
858 template <class _CharT, class _Traits>
859 class _LIBCPP_VISIBLE ostreambuf_iterator
860 : public iterator<output_iterator_tag, void, void, void, void>
863 typedef _CharT char_type;
864 typedef _Traits traits_type;
865 typedef basic_streambuf<_CharT,_Traits> streambuf_type;
866 typedef basic_ostream<_CharT,_Traits> ostream_type;
868 streambuf_type* __sbuf_;
870 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(ostream_type& __s) throw()
871 : __sbuf_(__s.rdbuf()) {}
872 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator(streambuf_type* __s) throw()
874 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator=(_CharT __c)
876 if (__sbuf_ && traits_type::eq_int_type(__sbuf_->sputc(__c), traits_type::eof()))
880 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator*() {return *this;}
881 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++() {return *this;}
882 _LIBCPP_INLINE_VISIBILITY ostreambuf_iterator& operator++(int) {return *this;}
883 _LIBCPP_INLINE_VISIBILITY bool failed() const throw() {return __sbuf_ == 0;}
886 template <class _Iter>
887 class _LIBCPP_VISIBLE move_iterator
892 typedef _Iter iterator_type;
893 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
894 typedef typename iterator_traits<iterator_type>::value_type value_type;
895 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
896 typedef typename iterator_traits<iterator_type>::pointer pointer;
897 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
898 typedef value_type&& reference;
900 typedef typename iterator_traits<iterator_type>::reference reference;
903 _LIBCPP_INLINE_VISIBILITY move_iterator() : __i() {}
904 _LIBCPP_INLINE_VISIBILITY explicit move_iterator(_Iter __x) : __i(__x) {}
905 template <class _Up> _LIBCPP_INLINE_VISIBILITY move_iterator(const move_iterator<_Up>& __u)
907 _LIBCPP_INLINE_VISIBILITY _Iter base() const {return __i;}
908 _LIBCPP_INLINE_VISIBILITY reference operator*() const {
909 return static_cast<reference>(*__i);
911 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {
912 typename iterator_traits<iterator_type>::reference __ref = *__i;
915 _LIBCPP_INLINE_VISIBILITY move_iterator& operator++() {++__i; return *this;}
916 _LIBCPP_INLINE_VISIBILITY move_iterator operator++(int)
917 {move_iterator __tmp(*this); ++__i; return __tmp;}
918 _LIBCPP_INLINE_VISIBILITY move_iterator& operator--() {--__i; return *this;}
919 _LIBCPP_INLINE_VISIBILITY move_iterator operator--(int)
920 {move_iterator __tmp(*this); --__i; return __tmp;}
921 _LIBCPP_INLINE_VISIBILITY move_iterator operator+ (difference_type __n) const
922 {return move_iterator(__i + __n);}
923 _LIBCPP_INLINE_VISIBILITY move_iterator& operator+=(difference_type __n)
924 {__i += __n; return *this;}
925 _LIBCPP_INLINE_VISIBILITY move_iterator operator- (difference_type __n) const
926 {return move_iterator(__i - __n);}
927 _LIBCPP_INLINE_VISIBILITY move_iterator& operator-=(difference_type __n)
928 {__i -= __n; return *this;}
929 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
931 return static_cast<reference>(__i[__n]);
935 template <class _Iter1, class _Iter2>
936 inline _LIBCPP_INLINE_VISIBILITY
938 operator==(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
940 return __x.base() == __y.base();
943 template <class _Iter1, class _Iter2>
944 inline _LIBCPP_INLINE_VISIBILITY
946 operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
948 return __x.base() < __y.base();
951 template <class _Iter1, class _Iter2>
952 inline _LIBCPP_INLINE_VISIBILITY
954 operator!=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
956 return __x.base() != __y.base();
959 template <class _Iter1, class _Iter2>
960 inline _LIBCPP_INLINE_VISIBILITY
962 operator>(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
964 return __x.base() > __y.base();
967 template <class _Iter1, class _Iter2>
968 inline _LIBCPP_INLINE_VISIBILITY
970 operator>=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
972 return __x.base() >= __y.base();
975 template <class _Iter1, class _Iter2>
976 inline _LIBCPP_INLINE_VISIBILITY
978 operator<=(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
980 return __x.base() <= __y.base();
983 template <class _Iter1, class _Iter2>
984 inline _LIBCPP_INLINE_VISIBILITY
985 typename move_iterator<_Iter1>::difference_type
986 operator-(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
988 return __x.base() - __y.base();
991 template <class _Iter>
992 inline _LIBCPP_INLINE_VISIBILITY
994 operator+(typename move_iterator<_Iter>::difference_type __n, const move_iterator<_Iter>& __x)
996 return move_iterator<_Iter>(__x.base() + __n);
999 template <class _Iter>
1000 inline _LIBCPP_INLINE_VISIBILITY
1001 move_iterator<_Iter>
1002 make_move_iterator(const _Iter& __i)
1004 return move_iterator<_Iter>(__i);
1009 template <class _Iter> class __wrap_iter;
1011 template <class _Iter1, class _Iter2>
1013 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1015 template <class _Iter1, class _Iter2>
1017 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1019 template <class _Iter1, class _Iter2>
1021 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1023 template <class _Iter1, class _Iter2>
1025 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1027 template <class _Iter1, class _Iter2>
1029 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1031 template <class _Iter1, class _Iter2>
1033 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1035 template <class _Iter1, class _Iter2>
1036 typename __wrap_iter<_Iter1>::difference_type
1037 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1039 template <class _Iter>
1041 operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT;
1043 template <class _Ip, class _Op> _Op copy(_Ip, _Ip, _Op);
1044 template <class _B1, class _B2> _B2 copy_backward(_B1, _B1, _B2);
1045 template <class _Ip, class _Op> _Op move(_Ip, _Ip, _Op);
1046 template <class _B1, class _B2> _B2 move_backward(_B1, _B1, _B2);
1048 template <class _Tp>
1051 is_trivially_copy_assignable<_Tp>::value,
1054 __unwrap_iter(__wrap_iter<_Tp*>);
1056 template <class _Iter>
1060 typedef _Iter iterator_type;
1061 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1062 typedef typename iterator_traits<iterator_type>::value_type value_type;
1063 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1064 typedef typename iterator_traits<iterator_type>::pointer pointer;
1065 typedef typename iterator_traits<iterator_type>::reference reference;
1069 _LIBCPP_INLINE_VISIBILITY __wrap_iter() _NOEXCEPT
1071 #if _LIBCPP_DEBUG_LEVEL >= 2
1072 __get_db()->__insert_i(this);
1075 template <class _Up> _LIBCPP_INLINE_VISIBILITY __wrap_iter(const __wrap_iter<_Up>& __u,
1076 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0) _NOEXCEPT
1079 #if _LIBCPP_DEBUG_LEVEL >= 2
1080 __get_db()->__iterator_copy(this, &__u);
1083 #if _LIBCPP_DEBUG_LEVEL >= 2
1084 _LIBCPP_INLINE_VISIBILITY
1085 __wrap_iter(const __wrap_iter& __x)
1088 __get_db()->__iterator_copy(this, &__x);
1090 _LIBCPP_INLINE_VISIBILITY
1091 __wrap_iter& operator=(const __wrap_iter& __x)
1095 __get_db()->__iterator_copy(this, &__x);
1100 _LIBCPP_INLINE_VISIBILITY
1103 __get_db()->__erase_i(this);
1106 _LIBCPP_INLINE_VISIBILITY reference operator*() const _NOEXCEPT
1108 #if _LIBCPP_DEBUG_LEVEL >= 2
1109 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1110 "Attempted to dereference a non-dereferenceable iterator");
1114 _LIBCPP_INLINE_VISIBILITY pointer operator->() const _NOEXCEPT {return &(operator*());}
1115 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator++() _NOEXCEPT
1117 #if _LIBCPP_DEBUG_LEVEL >= 2
1118 _LIBCPP_ASSERT(__get_const_db()->__dereferenceable(this),
1119 "Attempted to increment non-incrementable iterator");
1124 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator++(int) _NOEXCEPT
1125 {__wrap_iter __tmp(*this); ++(*this); return __tmp;}
1126 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator--() _NOEXCEPT
1128 #if _LIBCPP_DEBUG_LEVEL >= 2
1129 _LIBCPP_ASSERT(__get_const_db()->__decrementable(this),
1130 "Attempted to decrement non-decrementable iterator");
1135 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator--(int) _NOEXCEPT
1136 {__wrap_iter __tmp(*this); --(*this); return __tmp;}
1137 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator+ (difference_type __n) const _NOEXCEPT
1138 {__wrap_iter __w(*this); __w += __n; return __w;}
1139 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator+=(difference_type __n) _NOEXCEPT
1141 #if _LIBCPP_DEBUG_LEVEL >= 2
1142 _LIBCPP_ASSERT(__get_const_db()->__addable(this, __n),
1143 "Attempted to add/subtract iterator outside of valid range");
1148 _LIBCPP_INLINE_VISIBILITY __wrap_iter operator- (difference_type __n) const _NOEXCEPT
1149 {return *this + (-__n);}
1150 _LIBCPP_INLINE_VISIBILITY __wrap_iter& operator-=(difference_type __n) _NOEXCEPT
1151 {*this += -__n; return *this;}
1152 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const _NOEXCEPT
1154 #if _LIBCPP_DEBUG_LEVEL >= 2
1155 _LIBCPP_ASSERT(__get_const_db()->__subscriptable(this, __n),
1156 "Attempted to subscript iterator outside of valid range");
1161 _LIBCPP_INLINE_VISIBILITY iterator_type base() const _NOEXCEPT {return __i;}
1164 _LIBCPP_INLINE_VISIBILITY __wrap_iter(iterator_type __x) _NOEXCEPT : __i(__x) {}
1165 #if _LIBCPP_DEBUG_LEVEL >= 2
1166 _LIBCPP_INLINE_VISIBILITY __wrap_iter(const void* __p, iterator_type __x) : __i(__x)
1168 __get_db()->__insert_ic(this, __p);
1172 template <class _Up> friend class __wrap_iter;
1173 template <class _CharT, class _Traits, class _Alloc> friend class basic_string;
1174 template <class _Tp, class _Alloc> friend class vector;
1176 template <class _Iter1, class _Iter2>
1179 operator==(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1181 template <class _Iter1, class _Iter2>
1184 operator<(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1186 template <class _Iter1, class _Iter2>
1189 operator!=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1191 template <class _Iter1, class _Iter2>
1194 operator>(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1196 template <class _Iter1, class _Iter2>
1199 operator>=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1201 template <class _Iter1, class _Iter2>
1204 operator<=(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1206 template <class _Iter1, class _Iter2>
1208 typename __wrap_iter<_Iter1>::difference_type
1209 operator-(const __wrap_iter<_Iter1>&, const __wrap_iter<_Iter2>&) _NOEXCEPT;
1211 template <class _Iter1>
1214 operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT;
1216 template <class _Ip, class _Op> friend _Op copy(_Ip, _Ip, _Op);
1217 template <class _B1, class _B2> friend _B2 copy_backward(_B1, _B1, _B2);
1218 template <class _Ip, class _Op> friend _Op move(_Ip, _Ip, _Op);
1219 template <class _B1, class _B2> friend _B2 move_backward(_B1, _B1, _B2);
1221 template <class _Tp>
1225 is_trivially_copy_assignable<_Tp>::value,
1228 __unwrap_iter(__wrap_iter<_Tp*>);
1231 template <class _Iter1, class _Iter2>
1232 inline _LIBCPP_INLINE_VISIBILITY
1234 operator==(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1236 #if _LIBCPP_DEBUG_LEVEL >= 2
1237 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1238 "Attempted to compare incomparable iterators");
1240 return __x.base() == __y.base();
1243 template <class _Iter1, class _Iter2>
1244 inline _LIBCPP_INLINE_VISIBILITY
1246 operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1248 #if _LIBCPP_DEBUG_LEVEL >= 2
1249 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1250 "Attempted to compare incomparable iterators");
1252 return __x.base() < __y.base();
1255 template <class _Iter1, class _Iter2>
1256 inline _LIBCPP_INLINE_VISIBILITY
1258 operator!=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1260 return !(__x == __y);
1263 template <class _Iter1, class _Iter2>
1264 inline _LIBCPP_INLINE_VISIBILITY
1266 operator>(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1271 template <class _Iter1, class _Iter2>
1272 inline _LIBCPP_INLINE_VISIBILITY
1274 operator>=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1276 return !(__x < __y);
1279 template <class _Iter1, class _Iter2>
1280 inline _LIBCPP_INLINE_VISIBILITY
1282 operator<=(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1284 return !(__y < __x);
1287 template <class _Iter1, class _Iter2>
1288 inline _LIBCPP_INLINE_VISIBILITY
1289 typename __wrap_iter<_Iter1>::difference_type
1290 operator-(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
1292 #if _LIBCPP_DEBUG_LEVEL >= 2
1293 _LIBCPP_ASSERT(__get_const_db()->__comparable(&__x, &__y),
1294 "Attempted to subtract incompatible iterators");
1296 return __x.base() - __y.base();
1299 template <class _Iter>
1300 inline _LIBCPP_INLINE_VISIBILITY
1302 operator+(typename __wrap_iter<_Iter>::difference_type __n,
1303 __wrap_iter<_Iter> __x) _NOEXCEPT
1309 #ifdef _LIBCPP_DEBUG
1313 template <class _Container, class _Iter> class __debug_iter;
1315 template <class _Container, class _Iter1, class _Iter2>
1317 operator==(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1319 template <class _Container, class _Iter1, class _Iter2>
1321 operator<(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1323 template <class _Container, class _Iter1, class _Iter2>
1325 operator!=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1327 template <class _Container, class _Iter1, class _Iter2>
1329 operator>(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1331 template <class _Container, class _Iter1, class _Iter2>
1333 operator>=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1335 template <class _Container, class _Iter1, class _Iter2>
1337 operator<=(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1339 template <class _Container, class _Iter1, class _Iter2>
1340 typename __debug_iter<_Container, _Iter1>::difference_type
1341 operator-(const __debug_iter<_Container, _Iter1>&, const __debug_iter<_Container, _Iter2>&);
1343 template <class _Container, class _Iter>
1344 __debug_iter<_Container, _Iter>
1345 operator+(typename __debug_iter<_Container, _Iter>::difference_type, const __debug_iter<_Container, _Iter>&);
1347 template <class _Container, class _Iter>
1351 typedef _Iter iterator_type;
1352 typedef _Container __container_type;
1353 typedef typename iterator_traits<iterator_type>::iterator_category iterator_category;
1354 typedef typename iterator_traits<iterator_type>::value_type value_type;
1355 typedef typename iterator_traits<iterator_type>::difference_type difference_type;
1356 typedef typename iterator_traits<iterator_type>::pointer pointer;
1357 typedef typename iterator_traits<iterator_type>::reference reference;
1360 __debug_iter* __next;
1361 __container_type* __cont;
1364 _LIBCPP_INLINE_VISIBILITY __debug_iter() : __next(0), __cont(0) {}
1365 _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter& __x)
1366 : __i(__x.base()), __next(0), __cont(0) {__set_owner(__x.__cont);}
1367 __debug_iter& operator=(const __debug_iter& __x);
1368 template <class _Up> _LIBCPP_INLINE_VISIBILITY __debug_iter(const __debug_iter<_Container, _Up>& __u,
1369 typename enable_if<is_convertible<_Up, iterator_type>::value>::type* = 0)
1370 : __i(__u.base()), __next(0), __cont(0) {__set_owner(__u.__cont);}
1371 _LIBCPP_INLINE_VISIBILITY ~__debug_iter() {__remove_owner();}
1372 _LIBCPP_INLINE_VISIBILITY reference operator*() const {assert(__is_deref()); return *__i;}
1373 _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &(operator*());}
1374 _LIBCPP_INLINE_VISIBILITY __debug_iter& operator++() {assert(__can_increment()); ++__i; return *this;}
1375 _LIBCPP_INLINE_VISIBILITY __debug_iter operator++(int)
1376 {__debug_iter __tmp(*this); operator++(); return __tmp;}
1377 _LIBCPP_INLINE_VISIBILITY __debug_iter& operator--() {assert(__can_decrement()); --__i; return *this;}
1378 _LIBCPP_INLINE_VISIBILITY __debug_iter operator--(int)
1379 {__debug_iter __tmp(*this); operator--(); return __tmp;}
1380 _LIBCPP_INLINE_VISIBILITY __debug_iter operator+ (difference_type __n) const
1381 {__debug_iter __t(*this); __t += __n; return __t;}
1382 __debug_iter& operator+=(difference_type __n);
1383 _LIBCPP_INLINE_VISIBILITY __debug_iter operator- (difference_type __n) const
1384 {__debug_iter __t(*this); __t -= __n; return __t;}
1385 _LIBCPP_INLINE_VISIBILITY __debug_iter& operator-=(difference_type __n)
1386 {*this += -__n; return *this;}
1387 _LIBCPP_INLINE_VISIBILITY reference operator[](difference_type __n) const
1388 {return *(*this + __n);}
1391 _LIBCPP_INLINE_VISIBILITY __debug_iter(const __container_type* __c, iterator_type __x)
1392 : __i(__x), __next(0), __cont(0) {__set_owner(__c);}
1393 _LIBCPP_INLINE_VISIBILITY iterator_type base() const {return __i;}
1395 void __set_owner(const __container_type* __c);
1396 void __remove_owner();
1397 static void __remove_all(__container_type* __c);
1398 static void swap(__container_type* __x, __container_type* __y);
1400 _LIBCPP_INLINE_VISIBILITY bool __is_deref() const
1401 {return __is_deref(__is_random_access_iterator<iterator_type>());}
1402 bool __is_deref(false_type) const;
1403 bool __is_deref(true_type) const;
1404 _LIBCPP_INLINE_VISIBILITY bool __can_decrement() const
1405 {return __can_decrement(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1406 __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1407 bool __can_decrement(integral_constant<int, 0>) const;
1408 bool __can_decrement(integral_constant<int, 1>) const;
1409 bool __can_decrement(integral_constant<int, 2>) const;
1410 _LIBCPP_INLINE_VISIBILITY bool __can_increment() const
1411 {return __can_increment(integral_constant<int, is_pointer<iterator_type>::value ? 2:
1412 __is_random_access_iterator<iterator_type>::value ? 1 : 0>());}
1413 bool __can_increment(integral_constant<int, 0>) const;
1414 bool __can_increment(integral_constant<int, 1>) const;
1415 bool __can_increment(integral_constant<int, 2>) const;
1417 _LIBCPP_INLINE_VISIBILITY bool __can_add(difference_type __n) const
1418 {return __can_add(__n, is_pointer<iterator_type>());}
1419 bool __can_add(difference_type __n, false_type) const;
1420 bool __can_add(difference_type __n, true_type) const;
1422 template <class _Cp, class _Up> friend class __debug_iter;
1423 friend class _Container::__self;
1425 template <class _Cp, class _Iter1, class _Iter2>
1428 operator==(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1430 template <class _Cp, class _Iter1, class _Iter2>
1433 operator<(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1435 template <class _Cp, class _Iter1, class _Iter2>
1438 operator!=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1440 template <class _Cp, class _Iter1, class _Iter2>
1443 operator>(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1445 template <class _Cp, class _Iter1, class _Iter2>
1448 operator>=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1450 template <class _Cp, class _Iter1, class _Iter2>
1453 operator<=(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1455 template <class _Cp, class _Iter1, class _Iter2>
1457 typename __debug_iter<_Cp, _Iter1>::difference_type
1458 operator-(const __debug_iter<_Cp, _Iter1>&, const __debug_iter<_Cp, _Iter2>&);
1460 template <class _Cp, class _Iter1>
1462 __debug_iter<_Cp, _Iter1>
1463 operator+(typename __debug_iter<_Cp, _Iter1>::difference_type, const __debug_iter<_Cp, _Iter1>&);
1466 template <class _Container, class _Iter>
1467 __debug_iter<_Container, _Iter>&
1468 __debug_iter<_Container, _Iter>::operator=(const __debug_iter& __x)
1474 __set_owner(__x.__cont);
1479 template <class _Container, class _Iter>
1481 __debug_iter<_Container, _Iter>::__set_owner(const __container_type* __c)
1483 __cont = const_cast<__container_type*>(__c);
1484 __debug_iter*& __head = __cont->__get_iterator_list(this);
1489 template <class _Container, class _Iter>
1491 __debug_iter<_Container, _Iter>::__remove_owner()
1495 __debug_iter*& __head = __cont->__get_iterator_list(this);
1500 __debug_iter* __prev = __head;
1501 for (__debug_iter* __p = __head->__next; __p != this; __p = __p->__next)
1503 __prev->__next = __next;
1509 template <class _Container, class _Iter>
1511 __debug_iter<_Container, _Iter>::__remove_all(__container_type* __c)
1513 __debug_iter*& __head = __c->__get_iterator_list((__debug_iter*)0);
1514 __debug_iter* __p = __head;
1519 __debug_iter* __n = __p->__next;
1525 template <class _Container, class _Iter>
1527 __debug_iter<_Container, _Iter>::swap(__container_type* __x, __container_type* __y)
1529 __debug_iter*& __head_x = __x->__get_iterator_list((__debug_iter*)0);
1530 __debug_iter*& __head_y = __y->__get_iterator_list((__debug_iter*)0);
1531 __debug_iter* __p = __head_x;
1532 __head_x = __head_y;
1534 for (__p = __head_x; __p; __p = __p->__next)
1536 for (__p = __head_y; __p; __p = __p->__next)
1540 template <class _Container, class _Iter>
1542 __debug_iter<_Container, _Iter>::__is_deref(false_type) const
1546 return __i != __cont->end().base();
1549 template <class _Container, class _Iter>
1551 __debug_iter<_Container, _Iter>::__is_deref(true_type) const
1555 return __i < __cont->end().base();
1558 template <class _Container, class _Iter>
1560 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 0>) const
1564 return __i != __cont->begin().base();
1567 template <class _Container, class _Iter>
1569 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 1>) const
1573 iterator_type __b = __cont->begin().base();
1574 return __b < __i && __i <= __b + __cont->size();
1577 template <class _Container, class _Iter>
1579 __debug_iter<_Container, _Iter>::__can_decrement(integral_constant<int, 2>) const
1583 iterator_type __b = __cont->begin().base();
1584 return __b < __i && __i <= __b + __cont->size();
1587 template <class _Container, class _Iter>
1589 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 0>) const
1593 return __i != __cont->end().base();
1596 template <class _Container, class _Iter>
1598 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 1>) const
1602 iterator_type __b = __cont->begin().base();
1603 return __b <= __i && __i < __b + __cont->size();
1606 template <class _Container, class _Iter>
1608 __debug_iter<_Container, _Iter>::__can_increment(integral_constant<int, 2>) const
1612 iterator_type __b = __cont->begin().base();
1613 return __b <= __i && __i < __b + __cont->size();
1616 template <class _Container, class _Iter>
1618 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, false_type) const
1622 iterator_type __b = __cont->begin().base();
1623 iterator_type __j = __i + __n;
1624 return __b <= __j && __j <= __b + __cont->size();
1627 template <class _Container, class _Iter>
1629 __debug_iter<_Container, _Iter>::__can_add(difference_type __n, true_type) const
1633 iterator_type __b = __cont->begin().base();
1634 iterator_type __j = __i + __n;
1635 return __b <= __j && __j <= __b + __cont->size();
1638 template <class _Container, class _Iter>
1639 __debug_iter<_Container, _Iter>&
1640 __debug_iter<_Container, _Iter>::operator+=(difference_type __n)
1642 assert(__can_add(__n));
1647 template <class _Container, class _Iter1, class _Iter2>
1648 inline _LIBCPP_INLINE_VISIBILITY
1650 operator==(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1652 assert(__x.__cont && __x.__cont == __y.__cont);
1653 return __x.base() == __y.base();
1656 template <class _Container, class _Iter1, class _Iter2>
1657 inline _LIBCPP_INLINE_VISIBILITY
1659 operator!=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1661 return !(__x == __y);
1664 template <class _Container, class _Iter1, class _Iter2>
1665 inline _LIBCPP_INLINE_VISIBILITY
1667 operator<(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1669 assert(__x.__cont && __x.__cont == __y.__cont);
1670 return __x.base() < __y.base();
1673 template <class _Container, class _Iter1, class _Iter2>
1674 inline _LIBCPP_INLINE_VISIBILITY
1676 operator>(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1681 template <class _Container, class _Iter1, class _Iter2>
1682 inline _LIBCPP_INLINE_VISIBILITY
1684 operator>=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1686 return !(__x < __y);
1689 template <class _Container, class _Iter1, class _Iter2>
1690 inline _LIBCPP_INLINE_VISIBILITY
1692 operator<=(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1694 return !(__y < __x);
1697 template <class _Container, class _Iter1, class _Iter2>
1698 inline _LIBCPP_INLINE_VISIBILITY
1699 typename __debug_iter<_Container, _Iter1>::difference_type
1700 operator-(const __debug_iter<_Container, _Iter1>& __x, const __debug_iter<_Container, _Iter2>& __y)
1702 assert(__x.__cont && __x.__cont == __y.__cont);
1703 return __x.base() - __y.base();
1706 template <class _Container, class _Iter>
1707 inline _LIBCPP_INLINE_VISIBILITY
1708 __debug_iter<_Container, _Iter>
1709 operator+(typename __debug_iter<_Container, _Iter>::difference_type __n,
1710 const __debug_iter<_Container, _Iter>& __x)
1715 #endif // _LIBCPP_DEBUG
1717 #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1719 template <class _Cp>
1720 inline _LIBCPP_INLINE_VISIBILITY
1722 begin(_Cp& __c) -> decltype(__c.begin())
1727 template <class _Cp>
1728 inline _LIBCPP_INLINE_VISIBILITY
1730 begin(const _Cp& __c) -> decltype(__c.begin())
1735 template <class _Cp>
1736 inline _LIBCPP_INLINE_VISIBILITY
1738 end(_Cp& __c) -> decltype(__c.end())
1743 template <class _Cp>
1744 inline _LIBCPP_INLINE_VISIBILITY
1746 end(const _Cp& __c) -> decltype(__c.end())
1751 #else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1753 template <class _Cp>
1754 inline _LIBCPP_INLINE_VISIBILITY
1755 typename _Cp::iterator
1761 template <class _Cp>
1762 inline _LIBCPP_INLINE_VISIBILITY
1763 typename _Cp::const_iterator
1764 begin(const _Cp& __c)
1769 template <class _Cp>
1770 inline _LIBCPP_INLINE_VISIBILITY
1771 typename _Cp::iterator
1777 template <class _Cp>
1778 inline _LIBCPP_INLINE_VISIBILITY
1779 typename _Cp::const_iterator
1785 #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_TRAILING_RETURN)
1787 template <class _Tp, size_t _Np>
1788 inline _LIBCPP_INLINE_VISIBILITY
1790 begin(_Tp (&__array)[_Np])
1795 template <class _Tp, size_t _Np>
1796 inline _LIBCPP_INLINE_VISIBILITY
1798 end(_Tp (&__array)[_Np])
1800 return __array + _Np;
1803 _LIBCPP_END_NAMESPACE_STD
1805 #endif // _LIBCPP_ITERATOR