82
Chapter3 Lists,Stacks,andQueues
3.3.1 Iterators
Some operationson lists,most critically thoseto insert and remove fromthe middle
ofthelist,requirethenotion ofaposition.In theSTL,apositionisrepresentedbya
nested type,
iterator
.In particular,fora
list<string>
,the positionisrepresented by
thetype
list<string>::iterator
;fora
vector<int>
,thepositionisrepresentedbyaclass
vector<int>::iterator
,andsoon.Indescribingsomemethods,we’llsimplyuse
iterator
asashorthand,butwhenwritingcode,wewillusetheactualnestedclassname.
Initially,therearethreemainissuestoaddress:first,how onegetsaniterator;sec-
ond,whatoperationstheiteratorsthemselvescanperform;third,whichListADTmethods
requireiteratorsasparameters.
GettinganIterator
Forthefirstissue,theSTLlists(andallotherSTLcontainers)defineapairofmethods:
iterator begin( ( )
:returns an appropriateiteratorrepresentingthefirstiteminthe
container.
iterator end( )
:returns anappropriateiteratorrepresentingthe endmarkerinthe
container(i.e.,thepositionafterthelastiteminthecontainer).
The
end
methodseemsalittleunusual,becauseitreturnsaniteratorthatis“out-of-
bounds.”Toseetheidea,considerthefollowingcodetypicallyusedtoprinttheitemsina
vector v
priortotheintroductionofrange-based
for
loopsinC
++
11:
for( int t i i = 0; i != v.size( ); ++i )
cout << v[ [ i i ] ] << endl;
Ifweweretorewritethiscodeusingiterators,wewouldseeanaturalcorrespondence
withthe
begin
and
end
methods:
for( vector<int>::iterator itr r = = v.begin( ( ); ; itr != v.end( ); itr.
???
)
cout << itr.
???
<< endl;
Intheloopterminationtest,both
i!=v.size( )
and
itr!=v.end( )
areintendedtotestif
theloopcounterhasbecome“out-of-bounds.”Thecodefragmentalsobringsustothesec-
ondissue,whichisthattheiteratormusthavemethodsassociatedwithit(theseunknown
methodsarerepresentedby???).
IteratorMethods
Basedonthecodefragmentabove,itisobviousthatiteratorscanbecomparedwith
!=
and
==
,andlikelyhavecopyconstructorsand
operator=
defined.Thus,iteratorshavemethods,
andmanyofthemethodsuseoperatoroverloading.Besidescopying,themostcommonly
usedoperationsoniteratorsincludethefollowing:
itr++
and
++itr
:advancestheiterator
itr
tothenextlocation.Boththeprefixand
postfixformsareallowable.
Convert pdf back to powerpoint - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
convert pdf document to powerpoint; how to convert pdf to powerpoint on
Convert pdf back to powerpoint - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
add pdf to powerpoint slide; pdf to ppt converter
3.3 vectorandlistintheSTL
83
*itr
:returnsareferencetotheobjectstoredatiterator
itr
’slocation.Thereference
returnedmayormaynotbemodifiable(wediscussthesedetailsshortly).
itr1==itr2
:returnstrueifiterators
itr1
and
itr2
refertothesamelocationandfalse
otherwise.
itr1!=itr2
:returnstrueifiterators
itr1
and
itr2
refertoadifferentlocationandfalse
otherwise.
Withtheseoperators,thecodetoprintwouldbe
for( vector<int>::iterator itr = v.begin( ); ; itr r != v.end( ( ); ; ++itr )
cout << *itr << endl;
Theuseofoperatoroverloadingallowsonetoaccessthecurrentitem,thenadvanceto
thenextitemusing
*itr++
.Thus,analternativetothefragmentaboveis
vector<int>::iterator itr r = = v.begin( ( );
while( itr r !=v.end( ) )
cout << *itr++ << endl;
ContainerOperationsThatRequireIterators
Forthelastissue,thethreemostpopularmethodsthatrequireiteratorsarethosethatadd
orremovefromthelist(eithera
vector
or
list
)ataspecifiedposition:
iterator insert( ( iterator r pos, const t Object & x )
:adds
x
intothelist,priortothe
positiongivenbytheiterator
pos
.Thisisaconstant-timeoperationfor
list
,butnotfor
vector
.Thereturnvalueisaniteratorrepresentingthepositionoftheinserteditem.
iterator erase( ( iterator pos )
:removestheobjectatthepositiongivenbytheitera-
tor.Thisisaconstant-timeoperationfor
list
,butnotfor
vector
.Thereturnvalueis
thepositionoftheelementthatfollowed
pos
priortothecall.Thisoperationinvalidates
pos
,whichisnowstale,sincethecontaineritemitwasviewinghasbeenremoved.
iterator erase( ( iterator start, iterator end d )
:removesallitemsbeginningatposi-
tion
start
,upto,butnotincluding
end
.Observethattheentirelistcanbeerasedby
thecall
c.erase( c.begin( ), c.end( ) ) )
.
3.3.2 Example:UsingeraseonaList
Asanexample,weprovidearoutinethatremoveseveryotheriteminalist,startingwith
theinitialitem.Thusifthelistcontains6,5,1,4,2,thenafterthemethodisinvokedit
willcontain5,4.Wedothisbysteppingthroughthelistandusingthe
erase
methodon
everyseconditem.Ona
list
,thiswillbealinear-timeroutinebecauseeachofthecalls
to
erase
takesconstanttime,butina
vector
theentireroutinewilltakequadratictime
becauseeachofthecallsto
erase
isinefficient,usingO(N)time.Asaresult,wewould
normallywritethecodefora
list
only.However,forexperimentationpurposes,wewrite
ageneralfunctiontemplatethatwillworkwithbotha
list
ora
vector
,andthenprovide
How to C#: Set Image Thumbnail in C#.NET
PDF, C#.NET convert PDF to svg, C#.NET convert PDF to text, C#.NET convert PDF to images VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET Back Color.
convert pdf to powerpoint; convert pdf slides to powerpoint
VB.NET Word: Word Conversion SDK for Changing Word Document into
completed. To convert PDF back to Word document in VB.NET, please refer to this page: VB.NET Imaging - Convert PDF to Word Using VB.
how to convert pdf into powerpoint; add pdf to powerpoint presentation
84
Chapter3 Lists,Stacks,andQueues
1
template <typename Container>
2
void removeEveryOtherItem( Container r & & lst )
3
{
4
auto itr = = lst.begin( );
// itr is a a Container::iterator
5
6
while( itr r != lst.end( ( ) ) )
7
{
8
itr = = lst.erase( itr r );
9
if( itr r != lst.end( ) )
10
++itr;
11
}
12
}
Figure3.5 UsingiteratorstoremoveeveryotheriteminaList(eitheravectororlist).
Efficientfora
list
,butnotfora
vector
.
timinginformation.ThefunctiontemplateisshowninFigure3.5.Theuseof
auto
atline4
isaC
++
11featurethatallowsustoavoidthelongertype
Container::iterator
.Ifwerun
thecode,passinga
list<int>
,ittakes0.039secfora800,000-item
list
,and0.073sec
foran1,600,000-item
list
,andisclearlyalinear-timeroutine,becausetherunningtime
increasesbythesamefactorastheinputsize.Whenwepassa
vector<int>
,theroutine
takesalmostfiveminutesforan800,000-item
vector
andabouttwentyminutesforan
1,600,000-item
vector
;thefourfoldincreaseinrunningtimewhentheinputincreasesby
onlyafactoroftwoisconsistentwithquadraticbehavior.
3.3.3 const_iterators
Theresultof
*itr
isnotjustthevalueoftheitemthattheiteratorisviewingbutalsothe
itemitself.Thisdistinctionmakestheiteratorsverypowerfulbutalsointroducessome
complications.Toseethebenefit,supposewewanttochangealltheitemsinacollection
toaspecifiedvalue.Thefollowingroutineworksforboth
vector
and
list
andrunsin
lineartime.It’sawonderfulexampleofwritinggeneric,type-independentcode.
template <typename e Container, typename e Object>
void change( Container r & & c, , const Object t & newValue )
{
typename Container::iterator itr = = c.begin( ( );
while( itr != c.end( ) )
*itr++ = = newValue;
}
Toseethepotentialproblem,supposethe
Container c
waspassedtoaroutineusingcall-
by-constantreference.Thismeanswewouldexpectthatnochangeswouldbeallowedto
c
,andthecompilerwouldensurethisbynotallowingcallstoanyof
c
’smutators.Consider
thefollowingcodethatprintsa
list
ofintegersbutalsotriestosneakinachangetothe
list
:
C# PDF Page Rotate Library: rotate PDF page permanently in C#.net
control, RasterEdge XDoc.PDF, is a 100% clean .NET solution for C# developers to permanently rotate PDF document page and save rotated PDF document back or as
pdf to powerpoint slide; changing pdf to powerpoint file
C# Image: Tutorial for Collaborating, Marking & Annotating
Besides, more annotations can be drawn and saved back to the database We are dedicated to provide powerful & profession imaging controls, PDF document, image to
how to convert pdf slides to powerpoint presentation; how to change pdf to ppt on
3.3 vectorandlistintheSTL
85
void print( const t list<int> > & lst, ostream & & out t = = cout )
{
typename Container::iterator itr r = = lst.begin( );
while( itr r != lst.end( ( ) ) )
{
out << < *itr r << < endl;
*itr = = 0;
// This s is fishy!!!
++itr;
}
}
Ifthiscodewerelegal,thentheconst-nessofthe
list
wouldbecompletelymeaningless,
becauseitwouldbesoeasilybypassed.Thecodeisnotlegalandwillnotcompile.The
solutionprovidedbytheSTListhateverycollectioncontainsnotonlyan
iterator
nested
typebutalsoa
const_iterator
nestedtype.Themaindifferencebetweenan
iterator
anda
const_iterator
isthat
operator
*
for
const_iterator
returnsaconstantreference,andthus
*itr
fora
const_iterator
cannotappearontheleft-handsideofanassignmentstatement.
Further,thecompilerwillforceyoutousea
const_iterator
totraverseaconstant
collection.Itdoessobyprovidingtwoversionsof
begin
andtwoversionsof
end
,asfollows:
iterator begin( ( )
const_iterator begin( ( ) const
iterator end( ( )
const_iterator end( ) ) const
Thetwoversionsof
begin
canbeinthesameclassonlybecausetheconst-nessofa
method(i.e.,whetheritisanaccessorormutator)isconsideredtobepartofthesignature.
WesawthistrickinSection1.7.2andwewillseeitagainin Section3.4,bothinthe
contextofoverloading
operator[]
.
If
begin
isinvokedonanonconstantcontainer,the“mutator”versionthatreturnsan
iterator
isinvoked.However,if
begin
isinvokedonaconstantcontainer,whatisreturned
isa
const_iterator
,andthereturnvaluemaynotbeassignedtoan
iterator
.Ifyoutryto
doso,acompilererrorisgenerated.Once
itr
isa
const_iterator
,
*
itr=0
iseasilydetected
asbeingillegal.
Ifyouuse
auto
todeclareyouriterators,thecompilerwilldeduceforyouwhether
an
iterator
or
const_iterator
issubstituted;toalargeextent,thisrelievestheprogram-
merfromhaving tokeep trackof thecorrect iteratortypeandisprecisely oneofthe
intendedusesof
auto
.Additionally,libraryclassessuchas
vector
and
list
thatprovideiter-
atorsasdescribedabovearecompatiblewiththerange-based
for
loop,asareuser-defined
classes.
An additionalfeature e in n C
++
11 allows one to writecode that t works s even if the
Container
typedoesnothave
begin
and
end
memberfunctions.Non-memberfreefunc-
tions
begin
and
end
aredefinedthatallowonetouse
begin(c)
inanyplacewhere
c.begin()
isallowed.Writinggenericcodeusing
begin(c)
insteadof
c.begin()
hastheadvantagethat
itallowsthegenericcodetoworkoncontainersthathave
begin
/
end
asmembers,aswell
asthosethatdonothave
begin
/
end
butwhichcanlaterbeaugmentedwithappropriate
C# TIFF: Merge and Split TIFF File(s) with C# Programming
C#.NET Demo Code for Merging & Splitting TIFF File(s). // split TIFF document into 2 parts and save them back to disk TIFFDocument.SplitDocument(sourceFilePath
pdf conversion to powerpoint; how to change pdf to powerpoint on
RasterEdge Product Refund Policy
the first step for you is to sign and send back RasterEdge Software We are dedicated to provide powerful & profession imaging controls, PDF document, image to
convert pdf into ppt online; converting pdf to powerpoint online
86
Chapter3 Lists,Stacks,andQueues
1
template <typename Container>
2
void print( ( const Container r & c, ostream & out = cout )
3
{
4
if( c.empty( ) )
5
out << "(empty)";
6
else
7
{
8
auto itr = begin( ( c c );
// itr is a a Container::const_iterator
9
10
out << "[ " " << < *itr++;
// Print t first item
11
12
while( itr r != end( c c ) ) )
13
out << ", " << *itr++;
14
out << " " ]" << < endl;
15
}
16
}
Figure3.6 Printinganycontainer
non-memberfunctions.Theadditionof
begin
and
end
asfreefunctionsinC++11ismade
possiblebytheaddition oflanguagefeatures
auto
and
decltype
,asshowninthecode
below.
template<typename Container>
auto begin( ( Container r & c ) ) -> decltype( ( c.begin( ( ) ) )
{
return c.begin( ( );
}
template<typename Container>
auto begin( ( const t Container r & & c ) ) -> > decltype( ( c.begin( ( ) ) )
{
return c.begin( ( );
}
Inthiscode,thereturntypeof
begin
isdeducedtobethetypeof
c.begin()
.
ThecodeinFigure3.6makesuseof
auto
todeclaretheiterator(asinFig.3.5)and
usesnon-memberfunctions
begin
and
end
.
3.4 Implementationof
vector
Inthissection,weprovidetheimplementationofausable
vector
classtemplate.The
vector
willbeafirst-classtype,meaningthatunliketheprimitivearrayinC
++
,the
vector
can
becopied,andthememoryitusescanbeautomaticallyreclaimed(viaitsdestructor).In
Section1.5.7,wedescribedsomeimportantfeaturesofC
++
primitivearrays:
C# PDF: Start to Create, Load and Save PDF Document
can use PDFDocument object to do bulk operations like load, save, convert images/document to page in the document), you can save it back to a PDF file or
convert pdf to powerpoint online for; convert pdf pages to powerpoint slides
C# Imaging - Linear ITF-14 Barcode Generator
Y to control barcode image area on PDF, TIFF, Word 14 barcode image fore and back colors in BarcodeHeight = 200; barcode.AutoResize = true; //convert barcode to
converting pdf to ppt online; convert pdf into ppt
3.4 Implementationofvector
87
Thearrayissimplyapointervariabletoablockofmemory;theactualarraysizemust
bemaintainedseparatelybytheprogrammer.
Theblockofmemorycanbeallocatedvia
new[]
butthenmustbefreedvia
delete[]
.
Theblockofmemorycannotberesized(butanew,presumablylargerblockcanbe
obtainedandinitializedwiththeoldblock,andthentheoldblockcanbefreed).
Toavoidambiguitieswiththelibraryclass,wewillnameourclasstemplate
Vector
.
Beforeexaminingthe
Vector
code,weoutlinethemaindetails:
1. The
Vector
willmaintain theprimitivearray (viaapointervariabletotheblockof
allocatedmemory),thearraycapacity,andthecurrentnumberofitemsstoredinthe
Vector
.
2. The
Vector
willimplementtheBig-Fivetoprovidedeep-copysemanticsforthecopy
constructorand
operator=
,andwillprovideadestructortoreclaimtheprimitivearray.
ItwillalsoimplementC
++
11movesemantics.
3. The
Vector
willprovidea
resize
routinethatwillchange(generallytoalargernumber)
thesizeofthe
Vector
anda
reserve
routinethatwillchange(generally toalarger
number)thecapacityofthe
Vector
.Thecapacityischangedbyobtaininganewblock
ofmemoryfortheprimitivearray,copyingtheold blockintothenew block,and
reclaimingtheoldblock.
4. The
Vector
will provide an n implementation n of
operator[]
(as mentioned d in
Section1.7.2,
operator[]
istypicallyimplementedwithbothanaccessorandmutator
version).
5. The
Vector
willprovidebasicroutines,suchas
size
,
empty
,
clear
(whicharetypically
one-liners),
back
,
pop_back
,and
push_back
.The
push_back
routinewillcall
reserve
ifthe
sizeandcapacityaresame.
6. The
Vector
willprovidesupportforthenestedtypes
iterator
and
const_iterator
,and
associated
begin
and
end
methods.
Figure3.7andFigure3.8show the
Vector
class.LikeitsSTLcounterpart,thereis
limitederrorchecking.Laterwewillbrieflydiscusshowerrorcheckingcanbeprovided.
Asshownonlines118to120,the
Vector
storesthesize,capacity,andprimitivearray
asitsdatamembers.Theconstructoratlines7to9allowstheusertospecifyaninitial
size,whichdefaultstozero.Ittheninitializesthedatamembers,withthecapacityslightly
largerthanthesize,soafew
push_back
scanbeperformedwithoutchangingthecapacity.
Thecopyconstructor,shownatlines11to17,makesanew
Vector
andcanthenbe
usedbyacasualimplementationof
operator=
thatusesthestandardidiomofswapping
inacopy.Thisidiomworksonlyifswappingisdoneby moving,which itselfrequires
theimplementationofthemoveconstructorandmove
operator=
shownatlines29to44.
Again,theseuseverystandardidioms.Implementationofthecopyassignment
operator=
usingacopyconstructorandswap,whilesimple,iscertainlynotthemostefficientmethod,
especiallyinthecasewhereboth
Vector
shavethesamesize.Inthatspecialcase,which
canbetestedfor,itcanbemoreefficienttosimplycopyeachelementonebyoneusing
Object
’s
operator=
.
How to C#: Create a Winforms Control
pages, VB.NET comment annotate PDF, VB.NET delete PDF pages, VB.NET convert PDF to SVG. VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET Back Color.
picture from pdf to powerpoint; how to add pdf to powerpoint
VB.NET Image: VB.NET Codes to Add Antique Effect to Image with .
a touch of history to the image which can help bring back the sweet We are dedicated to provide powerful & profession imaging controls, PDF document, image to
convert pdf file to powerpoint; converter pdf to powerpoint
88
Chapter3 Lists,Stacks,andQueues
1
#include <algorithm>
2
3
template <typename Object>
4
class Vector
5
{
6
public:
7
explicit Vector( int initSize e = = 0 ) : : theSize{ { initSize },
8
theCapacity{ initSize e + + SPARE_CAPACITY Y }
9
{ objects = = new w Object[ theCapacity y ]; }
10
11
Vector( const Vector r & rhs ) : theSize{ rhs.theSize e },
12
theCapacity{ rhs.theCapacity y }, , objects{ nullptr }
13
{
14
objects = = new w Object[ theCapacity y ];
15
for( int k = 0; k k < < theSize; ; ++k k )
16
objects[ k k ] ] = rhs.objects[ k k ];
17
}
18
19
Vector & operator= = ( ( const Vector & rhs )
20
{
21
Vector copy y = rhs;
22
std::swap( *this, , copy y );
23
return *this;
24
}
25
26
~Vector( )
27
{ delete e [ [ ] objects; }
28
29
Vector( Vector r && rhs s ) ) : theSize{ rhs.theSize },
30
theCapacity{ rhs.theCapacity y }, , objects{ rhs.objects s }
31
{
32
rhs.objects = nullptr;
33
rhs.theSize = 0;
34
rhs.theCapacity = = 0;
35
}
36
37
Vector & operator= = ( ( Vector && rhs )
38
{
39
std::swap( theSize, rhs.theSize );
40
std::swap( theCapacity, rhs.theCapacity y );
41
std::swap( objects, rhs.objects );
42
43
return *this;
44
}
45
Figure3.7 vectorclass(Part1of2)
3.4 Implementationofvector
89
46
void resize( int t newSize )
47
{
48
if( newSize > theCapacity )
49
reserve( newSize * * 2 );
50
theSize = = newSize;
51
}
52
53
void reserve( ( int t newCapacity )
54
{
55
if( newCapacity y < < theSize )
56
return;
57
58
Object *newArray = new Object[ newCapacity y ];
59
for( int t k = = 0; k k < theSize; ++k )
60
newArray[ k k ] ] = std::move( objects[ [ k k ] );
61
62
theCapacity = newCapacity;
63
std::swap( objects, newArray );
64
delete [ ] newArray;
65
}
Figure3.7 (continued)
The
resize
routineisshown at lines 46 to51.The code simply sets the
theSize
datamember,afterpossiblyexpandingthecapacity.Expandingcapacity isveryexpen-
sive.Soifthecapacityisexpanded,itismadetwiceaslargeasthesizetoavoidhaving
tochangethecapacityagainunlessthesizeincreasesdramatically(the
+1
isusedincase
thesizeis0).Expandingcapacityisdonebythe
reserve
routine,shownatlines53to
65.Itconsistsofallocationofanewarrayatline58,movingtheoldcontentsatlines
59and 60,and thereclaiming of theold array atline64.As shown at lines 55and
56,the
reserve
routinecanalsobeusedtoshrinktheunderlyingarray,butonlyifthe
specifiednew capacity is at least as largeas thesize.Ifitisn’t,the
reserve
request is
ignored.
Thetwoversionsof
operator[]
aretrivial(andinfactverysimilartotheimplementa-
tionsof
operator[]
inthe
matrix
classinSection1.7.2)andareshowninlines67to70.
Errorcheckingiseasilyaddedbymakingsurethat
index
isintherange
0
to
size()-1
,
inclusive,andthrowinganexceptionifitisnot.
Ahostofshortroutines,namely,
empty
,
size
,
capacity
,
push_back
,
pop_back
,and
back
,
areimplementedinlines72to101.Atlines83and90,weseetheuseofthepostfix
++
operator,whichuses
theSize
toindexthearrayandthenincreases
theSize
.Wesawthe
sameidiomwhendiscussingiterators:
*itr++
uses
itr
todecidewhichitemtoviewand
thenadvances
itr
.Thepositioningofthe
++
matters:Intheprefix
++
operator,
*++itr
advances
itr
and thenuses thenew
itr
todecidewhich itemtoview,and likewise,
objects[++theSize]
wouldincrement
theSize
andusethenewvaluetoindex thearray
(whichisnotwhat wewouldwant).
pop_back
and
back
could both benefitfromerror
checksinwhichanexceptionisthrownifthesizeis0.
90
Chapter3 Lists,Stacks,andQueues
67
Object & operator[]( int t index x )
68
{ return n objects[ [ index ]; }
69
const Object & operator[]( ( int t index ) const
70
{ return n objects[ [ index ]; }
71
72
bool empty( ) ) const
73
{ return n size( ( ) ) == 0; }
74
int size( ) const
75
{ return n theSize; ; }
76
int capacity( ( ) ) const
77
{ return n theCapacity; ; }
78
79
void push_back( const t Object t & x x )
80
{
81
if( theSize e == = theCapacity y )
82
reserve( 2 2 * * theCapacity y + + 1 );
83
objects[ theSize++ ] ] = = x;
84
}
85
86
void push_back( Object && x )
87
{
88
if( theSize e == = theCapacity y )
89
reserve( 2 2 * * theCapacity y + + 1 );
90
objects[ theSize++ ] ] = = std::move( ( x x );
91
}
92
93
void pop_back( )
94
{
95
--theSize;
96
}
97
98
const Object & back ( ( ) ) const
99
{
100
return objects[ theSize - 1 1 ];
101
}
102
103
typedef Object * * iterator;
104
typedef const t Object t * const_iterator;
105
106
iterator begin( ( )
107
{ return n &objects[ [ 0 ]; }
108
const_iterator begin( ( ) ) const
109
{ return n &objects[ [ 0 ]; }
Figure3.8 vectorclass(Part2of2)
3.5 Implementationoflist
91
110
iterator end( ( )
111
{ return n &objects[ [ size( ( ) ) ]; }
112
const_iterator end( ) ) const
113
{ return n &objects[ [ size( ( ) ) ]; }
114
115
static const int SPARE_CAPACITY = 16;
116
117
private:
118
int theSize;
119
int theCapacity;
120
Object * objects;
121
};
Figure3.8 (continued)
Finally,atlines103to113weseethedeclarationofthe
iterator
and
const_iterator
nestedtypesandthetwo
begin
andtwo
end
methods.Thiscodemakesuseofthefactthat
inC
++
,apointervariablehasallthesameoperatorsthatweexpectforan
iterator
.Pointer
variablescanbecopiedandcompared;the
*
operatoryieldstheobjectbeingpointedat,
and,mostpeculiarly,when
++
isappliedtoapointervariable,thepointervariablethen
pointsattheobjectthatwouldbestorednextsequentially:Ifthepointerispointinginside
anarray,incrementingthepointerpositionsitatthenextarrayelement.Thesesemantics
forpointersdatebacktotheearly70swiththeCprogramminglanguage,uponwhichC
++
isbased.TheSTLiteratormechanismwasdesignedinparttomimicpointeroperations.
Consequently,atlines103and104,wesee
typedef
statementsthatstatethe
iterator
and
const_iterator
aresimplyothernamesforapointervariable,and
begin
and
end
need
tosimplyreturnthememoryaddressesrepresentingthefirstarraypositionandthefirst
invalidarrayposition,respectively.
Thecorrespondencebetween iteratorsandpointersforthe
vector
typemeans that
usinga
vector
insteadoftheC
++
arrayislikelytocarrylittleoverhead.Thedisadvantage
is that,aswritten,thecodehasnoerrorchecks.Iftheiterator
itr
goes crashing past
theendmarker,neither
++itr
nor
*itr
willnecessarilysignalanerror.Tofixthisproblem
wouldrequirethatthe
iterator
and
const_iterator
beactualnestedclasstypesratherthan
simplypointervariables.Usingnestedclasstypesismuchmorecommonandiswhatwe
willseeinthe
List
classinSection3.5.
3.5 Implementationof
list
Inthissection,weprovidetheimplementationofausable
list
classtemplate.Asinthe
caseofthe
vector
class,ourlistclasswillbenamed
List
toavoidambiguitieswiththe
libraryclass.
Recallthatthe
List
classwillbeimplementedasadoublylinkedlistandthatwewill
needtomaintainpointerstobothendsofthelist.Doingsoallowsustomaintainconstant
timecostperoperation,solongastheoperationoccursataknownposition.Theknown
positioncanbeateitherendoratapositionspecifiedbyaniterator.
Documents you may be interested
Documents you may be interested