00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066 #ifndef _ITERATOR_H
00067 #define _ITERATOR_H 1
00068
00069 #include <bits/cpp_type_traits.h>
00070 #include <ext/type_traits.h>
00071
00072 _GLIBCXX_BEGIN_NAMESPACE(std)
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091
00092
00093 template<typename _Iterator>
00094 class reverse_iterator
00095 : public iterator<typename iterator_traits<_Iterator>::iterator_category,
00096 typename iterator_traits<_Iterator>::value_type,
00097 typename iterator_traits<_Iterator>::difference_type,
00098 typename iterator_traits<_Iterator>::pointer,
00099 typename iterator_traits<_Iterator>::reference>
00100 {
00101 protected:
00102 _Iterator current;
00103
00104 public:
00105 typedef _Iterator iterator_type;
00106 typedef typename iterator_traits<_Iterator>::difference_type
00107 difference_type;
00108 typedef typename iterator_traits<_Iterator>::reference reference;
00109 typedef typename iterator_traits<_Iterator>::pointer pointer;
00110
00111 public:
00112
00113
00114
00115
00116
00117
00118 reverse_iterator() : current() { }
00119
00120
00121
00122
00123 explicit
00124 reverse_iterator(iterator_type __x) : current(__x) { }
00125
00126
00127
00128
00129 reverse_iterator(const reverse_iterator& __x)
00130 : current(__x.current) { }
00131
00132
00133
00134
00135
00136 template<typename _Iter>
00137 reverse_iterator(const reverse_iterator<_Iter>& __x)
00138 : current(__x.base()) { }
00139
00140
00141
00142
00143 iterator_type
00144 base() const
00145 { return current; }
00146
00147
00148
00149
00150
00151
00152 reference
00153 operator*() const
00154 {
00155 _Iterator __tmp = current;
00156 return *--__tmp;
00157 }
00158
00159
00160
00161
00162
00163
00164 pointer
00165 operator->() const
00166 { return &(operator*()); }
00167
00168
00169
00170
00171
00172
00173 reverse_iterator&
00174 operator++()
00175 {
00176 --current;
00177 return *this;
00178 }
00179
00180
00181
00182
00183
00184
00185 reverse_iterator
00186 operator++(int)
00187 {
00188 reverse_iterator __tmp = *this;
00189 --current;
00190 return __tmp;
00191 }
00192
00193
00194
00195
00196
00197
00198 reverse_iterator&
00199 operator--()
00200 {
00201 ++current;
00202 return *this;
00203 }
00204
00205
00206
00207
00208
00209
00210 reverse_iterator
00211 operator--(int)
00212 {
00213 reverse_iterator __tmp = *this;
00214 ++current;
00215 return __tmp;
00216 }
00217
00218
00219
00220
00221
00222
00223 reverse_iterator
00224 operator+(difference_type __n) const
00225 { return reverse_iterator(current - __n); }
00226
00227
00228
00229
00230
00231
00232 reverse_iterator&
00233 operator+=(difference_type __n)
00234 {
00235 current -= __n;
00236 return *this;
00237 }
00238
00239
00240
00241
00242
00243
00244 reverse_iterator
00245 operator-(difference_type __n) const
00246 { return reverse_iterator(current + __n); }
00247
00248
00249
00250
00251
00252
00253 reverse_iterator&
00254 operator-=(difference_type __n)
00255 {
00256 current += __n;
00257 return *this;
00258 }
00259
00260
00261
00262
00263
00264
00265 reference
00266 operator[](difference_type __n) const
00267 { return *(*this + __n); }
00268 };
00269
00270
00271
00272
00273
00274
00275
00276
00277
00278
00279
00280 template<typename _Iterator>
00281 inline bool
00282 operator==(const reverse_iterator<_Iterator>& __x,
00283 const reverse_iterator<_Iterator>& __y)
00284 { return __x.base() == __y.base(); }
00285
00286 template<typename _Iterator>
00287 inline bool
00288 operator<(const reverse_iterator<_Iterator>& __x,
00289 const reverse_iterator<_Iterator>& __y)
00290 { return __y.base() < __x.base(); }
00291
00292 template<typename _Iterator>
00293 inline bool
00294 operator!=(const reverse_iterator<_Iterator>& __x,
00295 const reverse_iterator<_Iterator>& __y)
00296 { return !(__x == __y); }
00297
00298 template<typename _Iterator>
00299 inline bool
00300 operator>(const reverse_iterator<_Iterator>& __x,
00301 const reverse_iterator<_Iterator>& __y)
00302 { return __y < __x; }
00303
00304 template<typename _Iterator>
00305 inline bool
00306 operator<=(const reverse_iterator<_Iterator>& __x,
00307 const reverse_iterator<_Iterator>& __y)
00308 { return !(__y < __x); }
00309
00310 template<typename _Iterator>
00311 inline bool
00312 operator>=(const reverse_iterator<_Iterator>& __x,
00313 const reverse_iterator<_Iterator>& __y)
00314 { return !(__x < __y); }
00315
00316 template<typename _Iterator>
00317 inline typename reverse_iterator<_Iterator>::difference_type
00318 operator-(const reverse_iterator<_Iterator>& __x,
00319 const reverse_iterator<_Iterator>& __y)
00320 { return __y.base() - __x.base(); }
00321
00322 template<typename _Iterator>
00323 inline reverse_iterator<_Iterator>
00324 operator+(typename reverse_iterator<_Iterator>::difference_type __n,
00325 const reverse_iterator<_Iterator>& __x)
00326 { return reverse_iterator<_Iterator>(__x.base() - __n); }
00327
00328
00329
00330 template<typename _IteratorL, typename _IteratorR>
00331 inline bool
00332 operator==(const reverse_iterator<_IteratorL>& __x,
00333 const reverse_iterator<_IteratorR>& __y)
00334 { return __x.base() == __y.base(); }
00335
00336 template<typename _IteratorL, typename _IteratorR>
00337 inline bool
00338 operator<(const reverse_iterator<_IteratorL>& __x,
00339 const reverse_iterator<_IteratorR>& __y)
00340 { return __y.base() < __x.base(); }
00341
00342 template<typename _IteratorL, typename _IteratorR>
00343 inline bool
00344 operator!=(const reverse_iterator<_IteratorL>& __x,
00345 const reverse_iterator<_IteratorR>& __y)
00346 { return !(__x == __y); }
00347
00348 template<typename _IteratorL, typename _IteratorR>
00349 inline bool
00350 operator>(const reverse_iterator<_IteratorL>& __x,
00351 const reverse_iterator<_IteratorR>& __y)
00352 { return __y < __x; }
00353
00354 template<typename _IteratorL, typename _IteratorR>
00355 inline bool
00356 operator<=(const reverse_iterator<_IteratorL>& __x,
00357 const reverse_iterator<_IteratorR>& __y)
00358 { return !(__y < __x); }
00359
00360 template<typename _IteratorL, typename _IteratorR>
00361 inline bool
00362 operator>=(const reverse_iterator<_IteratorL>& __x,
00363 const reverse_iterator<_IteratorR>& __y)
00364 { return !(__x < __y); }
00365
00366 template<typename _IteratorL, typename _IteratorR>
00367 inline typename reverse_iterator<_IteratorL>::difference_type
00368 operator-(const reverse_iterator<_IteratorL>& __x,
00369 const reverse_iterator<_IteratorR>& __y)
00370 { return __y.base() - __x.base(); }
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384 template<typename _Container>
00385 class back_insert_iterator
00386 : public iterator<output_iterator_tag, void, void, void, void>
00387 {
00388 protected:
00389 _Container* container;
00390
00391 public:
00392
00393 typedef _Container container_type;
00394
00395
00396 explicit
00397 back_insert_iterator(_Container& __x) : container(&__x) { }
00398
00399
00400
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410 back_insert_iterator&
00411 operator=(typename _Container::const_reference __value)
00412 {
00413 container->push_back(__value);
00414 return *this;
00415 }
00416
00417
00418 back_insert_iterator&
00419 operator*()
00420 { return *this; }
00421
00422
00423 back_insert_iterator&
00424 operator++()
00425 { return *this; }
00426
00427
00428 back_insert_iterator
00429 operator++(int)
00430 { return *this; }
00431 };
00432
00433
00434
00435
00436
00437
00438
00439
00440
00441
00442
00443
00444 template<typename _Container>
00445 inline back_insert_iterator<_Container>
00446 back_inserter(_Container& __x)
00447 { return back_insert_iterator<_Container>(__x); }
00448
00449
00450
00451
00452
00453
00454
00455
00456
00457
00458
00459 template<typename _Container>
00460 class front_insert_iterator
00461 : public iterator<output_iterator_tag, void, void, void, void>
00462 {
00463 protected:
00464 _Container* container;
00465
00466 public:
00467
00468 typedef _Container container_type;
00469
00470
00471 explicit front_insert_iterator(_Container& __x) : container(&__x) { }
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482
00483
00484 front_insert_iterator&
00485 operator=(typename _Container::const_reference __value)
00486 {
00487 container->push_front(__value);
00488 return *this;
00489 }
00490
00491
00492 front_insert_iterator&
00493 operator*()
00494 { return *this; }
00495
00496
00497 front_insert_iterator&
00498 operator++()
00499 { return *this; }
00500
00501
00502 front_insert_iterator
00503 operator++(int)
00504 { return *this; }
00505 };
00506
00507
00508
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518 template<typename _Container>
00519 inline front_insert_iterator<_Container>
00520 front_inserter(_Container& __x)
00521 { return front_insert_iterator<_Container>(__x); }
00522
00523
00524
00525
00526
00527
00528
00529
00530
00531
00532
00533
00534
00535
00536
00537 template<typename _Container>
00538 class insert_iterator
00539 : public iterator<output_iterator_tag, void, void, void, void>
00540 {
00541 protected:
00542 _Container* container;
00543 typename _Container::iterator iter;
00544
00545 public:
00546
00547 typedef _Container container_type;
00548
00549
00550
00551
00552
00553 insert_iterator(_Container& __x, typename _Container::iterator __i)
00554 : container(&__x), iter(__i) {}
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567
00568
00569
00570
00571
00572
00573
00574
00575
00576
00577
00578
00579 insert_iterator&
00580 operator=(const typename _Container::const_reference __value)
00581 {
00582 iter = container->insert(iter, __value);
00583 ++iter;
00584 return *this;
00585 }
00586
00587
00588 insert_iterator&
00589 operator*()
00590 { return *this; }
00591
00592
00593 insert_iterator&
00594 operator++()
00595 { return *this; }
00596
00597
00598 insert_iterator&
00599 operator++(int)
00600 { return *this; }
00601 };
00602
00603
00604
00605
00606
00607
00608
00609
00610
00611
00612
00613
00614 template<typename _Container, typename _Iterator>
00615 inline insert_iterator<_Container>
00616 inserter(_Container& __x, _Iterator __i)
00617 {
00618 return insert_iterator<_Container>(__x,
00619 typename _Container::iterator(__i));
00620 }
00621
00622 _GLIBCXX_END_NAMESPACE
00623
00624 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00625
00626
00627
00628
00629
00630
00631
00632
00633 using std::iterator_traits;
00634 using std::iterator;
00635 template<typename _Iterator, typename _Container>
00636 class __normal_iterator
00637 {
00638 protected:
00639 _Iterator _M_current;
00640
00641 public:
00642 typedef typename iterator_traits<_Iterator>::iterator_category
00643 iterator_category;
00644 typedef typename iterator_traits<_Iterator>::value_type value_type;
00645 typedef typename iterator_traits<_Iterator>::difference_type
00646 difference_type;
00647 typedef typename iterator_traits<_Iterator>::reference reference;
00648 typedef typename iterator_traits<_Iterator>::pointer pointer;
00649
00650 __normal_iterator() : _M_current(_Iterator()) { }
00651
00652 explicit
00653 __normal_iterator(const _Iterator& __i) : _M_current(__i) { }
00654
00655
00656 template<typename _Iter>
00657 __normal_iterator(const __normal_iterator<_Iter,
00658 typename __enable_if<
00659 (std::__are_same<_Iter, typename _Container::pointer>::__value),
00660 _Container>::__type>& __i)
00661 : _M_current(__i.base()) { }
00662
00663
00664 reference
00665 operator*() const
00666 { return *_M_current; }
00667
00668 pointer
00669 operator->() const
00670 { return _M_current; }
00671
00672 __normal_iterator&
00673 operator++()
00674 {
00675 ++_M_current;
00676 return *this;
00677 }
00678
00679 __normal_iterator
00680 operator++(int)
00681 { return __normal_iterator(_M_current++); }
00682
00683
00684 __normal_iterator&
00685 operator--()
00686 {
00687 --_M_current;
00688 return *this;
00689 }
00690
00691 __normal_iterator
00692 operator--(int)
00693 { return __normal_iterator(_M_current--); }
00694
00695
00696 reference
00697 operator[](const difference_type& __n) const
00698 { return _M_current[__n]; }
00699
00700 __normal_iterator&
00701 operator+=(const difference_type& __n)
00702 { _M_current += __n; return *this; }
00703
00704 __normal_iterator
00705 operator+(const difference_type& __n) const
00706 { return __normal_iterator(_M_current + __n); }
00707
00708 __normal_iterator&
00709 operator-=(const difference_type& __n)
00710 { _M_current -= __n; return *this; }
00711
00712 __normal_iterator
00713 operator-(const difference_type& __n) const
00714 { return __normal_iterator(_M_current - __n); }
00715
00716 const _Iterator&
00717 base() const
00718 { return _M_current; }
00719 };
00720
00721
00722
00723
00724
00725
00726
00727
00728
00729
00730 template<typename _IteratorL, typename _IteratorR, typename _Container>
00731 inline bool
00732 operator==(const __normal_iterator<_IteratorL, _Container>& __lhs,
00733 const __normal_iterator<_IteratorR, _Container>& __rhs)
00734 { return __lhs.base() == __rhs.base(); }
00735
00736 template<typename _Iterator, typename _Container>
00737 inline bool
00738 operator==(const __normal_iterator<_Iterator, _Container>& __lhs,
00739 const __normal_iterator<_Iterator, _Container>& __rhs)
00740 { return __lhs.base() == __rhs.base(); }
00741
00742 template<typename _IteratorL, typename _IteratorR, typename _Container>
00743 inline bool
00744 operator!=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00745 const __normal_iterator<_IteratorR, _Container>& __rhs)
00746 { return __lhs.base() != __rhs.base(); }
00747
00748 template<typename _Iterator, typename _Container>
00749 inline bool
00750 operator!=(const __normal_iterator<_Iterator, _Container>& __lhs,
00751 const __normal_iterator<_Iterator, _Container>& __rhs)
00752 { return __lhs.base() != __rhs.base(); }
00753
00754
00755 template<typename _IteratorL, typename _IteratorR, typename _Container>
00756 inline bool
00757 operator<(const __normal_iterator<_IteratorL, _Container>& __lhs,
00758 const __normal_iterator<_IteratorR, _Container>& __rhs)
00759 { return __lhs.base() < __rhs.base(); }
00760
00761 template<typename _Iterator, typename _Container>
00762 inline bool
00763 operator<(const __normal_iterator<_Iterator, _Container>& __lhs,
00764 const __normal_iterator<_Iterator, _Container>& __rhs)
00765 { return __lhs.base() < __rhs.base(); }
00766
00767 template<typename _IteratorL, typename _IteratorR, typename _Container>
00768 inline bool
00769 operator>(const __normal_iterator<_IteratorL, _Container>& __lhs,
00770 const __normal_iterator<_IteratorR, _Container>& __rhs)
00771 { return __lhs.base() > __rhs.base(); }
00772
00773 template<typename _Iterator, typename _Container>
00774 inline bool
00775 operator>(const __normal_iterator<_Iterator, _Container>& __lhs,
00776 const __normal_iterator<_Iterator, _Container>& __rhs)
00777 { return __lhs.base() > __rhs.base(); }
00778
00779 template<typename _IteratorL, typename _IteratorR, typename _Container>
00780 inline bool
00781 operator<=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00782 const __normal_iterator<_IteratorR, _Container>& __rhs)
00783 { return __lhs.base() <= __rhs.base(); }
00784
00785 template<typename _Iterator, typename _Container>
00786 inline bool
00787 operator<=(const __normal_iterator<_Iterator, _Container>& __lhs,
00788 const __normal_iterator<_Iterator, _Container>& __rhs)
00789 { return __lhs.base() <= __rhs.base(); }
00790
00791 template<typename _IteratorL, typename _IteratorR, typename _Container>
00792 inline bool
00793 operator>=(const __normal_iterator<_IteratorL, _Container>& __lhs,
00794 const __normal_iterator<_IteratorR, _Container>& __rhs)
00795 { return __lhs.base() >= __rhs.base(); }
00796
00797 template<typename _Iterator, typename _Container>
00798 inline bool
00799 operator>=(const __normal_iterator<_Iterator, _Container>& __lhs,
00800 const __normal_iterator<_Iterator, _Container>& __rhs)
00801 { return __lhs.base() >= __rhs.base(); }
00802
00803
00804
00805
00806
00807 template<typename _IteratorL, typename _IteratorR, typename _Container>
00808 inline typename __normal_iterator<_IteratorL, _Container>::difference_type
00809 operator-(const __normal_iterator<_IteratorL, _Container>& __lhs,
00810 const __normal_iterator<_IteratorR, _Container>& __rhs)
00811 { return __lhs.base() - __rhs.base(); }
00812
00813 template<typename _Iterator, typename _Container>
00814 inline typename __normal_iterator<_Iterator, _Container>::difference_type
00815 operator-(const __normal_iterator<_Iterator, _Container>& __lhs,
00816 const __normal_iterator<_Iterator, _Container>& __rhs)
00817 { return __lhs.base() - __rhs.base(); }
00818
00819 template<typename _Iterator, typename _Container>
00820 inline __normal_iterator<_Iterator, _Container>
00821 operator+(typename __normal_iterator<_Iterator, _Container>::difference_type
00822 __n, const __normal_iterator<_Iterator, _Container>& __i)
00823 { return __normal_iterator<_Iterator, _Container>(__i.base() + __n); }
00824
00825 _GLIBCXX_END_NAMESPACE
00826
00827 #endif