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