资源描述：
《Intrusive Data Structures》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、IntrusiveDataStructuresJiriSoukup,CodeFarmsInc.7214JockTrail,Richmond,Ont.,Canada,KOA2ZO613-838-4829,fax613-838-3316,jiri@codefarms.comABSTRACTThisarticlecomparestwostylesofbuildingdatastructuresanddatastructurelibrariesinC++:(a)Intrusivedatastructuresformedbypointer
2、sstoredinsidetheapplicationobjects,(b)Containerswhereauxiliaryobjectsformtherequireddatastructure,andonlypointtotheapplicationobjectswithoutaddinganypointersorotherdatatothem.Eachstyleworksbetterindifferentsituations,andthefirsthalfofthearticlediscussestheimpactofthi
3、schoiceonprogramperformance,codemaintainability,easeofuseanddataintegrity.Whenworkingwithtemplates,containersareeasiertoimplement,whichmaybethereasonwhymostclasslibrariesarebasedoncontainers.Theonlyexistinglibrarywhichisconsistentlyintrusive(CodeFarms)usesacodegenera
4、tor.Ifintrusivedatastructurescouldnotbeimplementedwithtemplates,theirapplicabilitywouldbeseverelylimited.Thesecondhalfofthearticledealswiththispivotalquestion,showsanelegantwayofbuildinganintrusivedatastructurelibrarywithtemplates,explainswhyitsinterfaceissimilarto-b
5、utcannotbeidenticalwithSTL,discussestheimpactofthenewarchitectureonclassdependency,andcomparesthenewapproachwithexistinglibraries.AprototypeofthenewlibraryisnowavailableunderthenamePatternTemplateLibrary-see[15].Chapter1:IntroductionOpenanybookondatastructures,andsom
6、ewherenearthebeginningyouwillfindalinkedlistsimilartoFig.1a.Thisisthetypeoflistyouwouldprobablyuseinyourprogramifyouwerenotusinganyclasslibrary.Fig.1a:Differentimplementationsoftheabstractlist:intrusivelinkedlist.Fig.1b:Differentimplementationsoftheabstractlist:non-i
7、ntrusivelinkedlist.Fig.1c:Differentimplementationsoftheabstractlist:array-basednon-intrusivelist.Forexample,ifeachDepartmenthasEmployees,andeachEmployeebelongstoexactlyoneDepartment,youwouldwriteitlikethis:classEmployee{Employee*next;...};classDepartment{Employee*lis
8、tHead;...};Thistypeoflistiscalledan"intrusivelist",becausethepointersthatconnectitareembeddedintheparticipatingobjects.[Accordingto
