123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004200520062007200820092010201120122013201420152016201720182019202020212022202320242025202620272028202920302031203220332034203520362037203820392040204120422043204420452046204720482049205020512052205320542055205620572058205920602061206220632064206520662067206820692070207120722073207420752076207720782079208020812082208320842085208620872088208920902091209220932094209520962097209820992100210121022103210421052106210721082109211021112112211321142115211621172118211921202121212221232124212521262127212821292130213121322133213421352136213721382139214021412142214321442145214621472148214921502151215221532154215521562157215821592160216121622163216421652166216721682169217021712172217321742175217621772178217921802181218221832184218521862187218821892190219121922193219421952196219721982199220022012202220322042205220622072208220922102211221222132214221522162217221822192220222122222223222422252226222722282229223022312232223322342235223622372238223922402241224222432244224522462247224822492250225122522253225422552256225722582259226022612262226322642265226622672268226922702271227222732274227522762277227822792280228122822283228422852286228722882289229022912292229322942295229622972298229923002301230223032304230523062307230823092310231123122313231423152316231723182319232023212322232323242325232623272328232923302331233223332334233523362337233823392340234123422343234423452346234723482349235023512352235323542355235623572358235923602361236223632364236523662367236823692370237123722373237423752376237723782379238023812382238323842385238623872388238923902391239223932394239523962397239823992400240124022403240424052406240724082409241024112412241324142415241624172418241924202421242224232424242524262427242824292430243124322433243424352436243724382439244024412442244324442445244624472448244924502451245224532454245524562457245824592460246124622463246424652466246724682469247024712472247324742475247624772478247924802481248224832484248524862487248824892490249124922493249424952496249724982499250025012502250325042505250625072508250925102511251225132514251525162517251825192520252125222523252425252526252725282529253025312532253325342535253625372538253925402541254225432544254525462547254825492550255125522553255425552556255725582559256025612562256325642565256625672568256925702571257225732574257525762577257825792580258125822583258425852586258725882589259025912592259325942595259625972598259926002601260226032604260526062607260826092610261126122613261426152616261726182619262026212622262326242625262626272628262926302631263226332634263526362637263826392640264126422643264426452646264726482649265026512652265326542655265626572658265926602661266226632664266526662667266826692670267126722673267426752676267726782679268026812682268326842685268626872688268926902691269226932694269526962697269826992700270127022703270427052706270727082709271027112712271327142715271627172718271927202721272227232724272527262727272827292730273127322733273427352736273727382739274027412742274327442745274627472748274927502751275227532754275527562757275827592760276127622763276427652766276727682769277027712772277327742775277627772778277927802781278227832784278527862787278827892790279127922793279427952796279727982799280028012802280328042805280628072808280928102811281228132814281528162817281828192820282128222823282428252826282728282829283028312832283328342835283628372838283928402841284228432844284528462847284828492850285128522853285428552856285728582859286028612862286328642865286628672868286928702871287228732874287528762877287828792880288128822883288428852886288728882889289028912892289328942895289628972898289929002901290229032904290529062907290829092910291129122913291429152916291729182919292029212922292329242925292629272928292929302931293229332934293529362937293829392940294129422943294429452946294729482949295029512952295329542955295629572958295929602961296229632964296529662967296829692970297129722973297429752976297729782979298029812982298329842985298629872988298929902991299229932994299529962997299829993000300130023003300430053006300730083009301030113012301330143015301630173018301930203021302230233024302530263027302830293030303130323033303430353036303730383039304030413042304330443045304630473048304930503051305230533054305530563057305830593060306130623063306430653066306730683069307030713072307330743075307630773078307930803081308230833084308530863087308830893090309130923093309430953096309730983099310031013102310331043105310631073108310931103111311231133114311531163117311831193120312131223123312431253126312731283129313031313132313331343135313631373138313931403141314231433144314531463147314831493150315131523153315431553156315731583159316031613162316331643165316631673168316931703171317231733174317531763177317831793180318131823183318431853186318731883189319031913192319331943195319631973198319932003201320232033204320532063207320832093210321132123213321432153216321732183219322032213222322332243225322632273228322932303231323232333234323532363237323832393240324132423243324432453246324732483249325032513252325332543255325632573258325932603261326232633264326532663267326832693270327132723273327432753276327732783279328032813282328332843285328632873288328932903291329232933294329532963297329832993300330133023303330433053306330733083309331033113312331333143315331633173318331933203321332233233324332533263327332833293330333133323333333433353336333733383339334033413342334333443345334633473348334933503351335233533354335533563357335833593360336133623363336433653366336733683369337033713372337333743375337633773378337933803381338233833384338533863387338833893390339133923393339433953396339733983399340034013402340334043405340634073408340934103411341234133414341534163417341834193420342134223423342434253426342734283429343034313432343334343435343634373438343934403441344234433444344534463447344834493450345134523453345434553456345734583459346034613462346334643465346634673468346934703471347234733474347534763477347834793480348134823483348434853486348734883489349034913492349334943495349634973498349935003501350235033504350535063507350835093510351135123513351435153516351735183519352035213522352335243525352635273528352935303531353235333534353535363537353835393540354135423543354435453546354735483549355035513552355335543555355635573558355935603561356235633564356535663567356835693570357135723573357435753576357735783579358035813582358335843585358635873588358935903591359235933594359535963597359835993600360136023603360436053606360736083609361036113612361336143615361636173618361936203621362236233624362536263627362836293630363136323633363436353636363736383639364036413642364336443645364636473648364936503651365236533654365536563657365836593660366136623663366436653666366736683669367036713672367336743675367636773678367936803681368236833684368536863687368836893690369136923693369436953696369736983699370037013702370337043705370637073708370937103711371237133714371537163717371837193720372137223723372437253726372737283729373037313732373337343735373637373738373937403741374237433744374537463747374837493750375137523753375437553756375737583759376037613762376337643765376637673768376937703771377237733774377537763777377837793780378137823783378437853786378737883789379037913792379337943795379637973798379938003801380238033804380538063807380838093810381138123813381438153816381738183819382038213822382338243825382638273828382938303831383238333834383538363837383838393840384138423843384438453846384738483849385038513852385338543855385638573858385938603861386238633864386538663867386838693870387138723873387438753876387738783879388038813882388338843885388638873888388938903891389238933894389538963897389838993900390139023903390439053906390739083909391039113912391339143915391639173918391939203921392239233924392539263927392839293930393139323933393439353936393739383939394039413942394339443945394639473948394939503951395239533954395539563957395839593960396139623963396439653966396739683969397039713972397339743975397639773978397939803981398239833984398539863987398839893990399139923993399439953996399739983999400040014002400340044005400640074008400940104011401240134014401540164017401840194020402140224023402440254026402740284029403040314032403340344035403640374038403940404041404240434044404540464047404840494050405140524053405440554056405740584059406040614062406340644065406640674068406940704071407240734074407540764077407840794080408140824083408440854086408740884089409040914092409340944095409640974098409941004101410241034104410541064107410841094110411141124113411441154116411741184119412041214122412341244125412641274128412941304131413241334134413541364137413841394140414141424143414441454146414741484149415041514152415341544155415641574158415941604161416241634164416541664167416841694170417141724173417441754176417741784179418041814182418341844185418641874188418941904191419241934194419541964197419841994200420142024203420442054206420742084209421042114212421342144215421642174218421942204221422242234224422542264227422842294230423142324233423442354236423742384239424042414242424342444245424642474248424942504251425242534254425542564257 |
- [/
- / Copyright (c) 2006-2013 Ion Gaztanaga
- /
- / Distributed under the Boost Software License, Version 1.0. (See accompanying
- / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
- /]
- [library Boost.Intrusive
- [quickbook 1.6]
- [authors [Krzikalla, Olaf], [Gaztanaga, Ion]]
- [copyright 2005 Olaf Krzikalla, 2006-2015 Ion Gaztanaga]
- [id intrusive]
- [dirname intrusive]
- [purpose Intrusive containers]
- [license
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- [@http://www.boost.org/LICENSE_1_0.txt])
- ]
- ]
- [section:introduction Introduction]
- [section:introduction_presenting Presenting Boost.Intrusive]
- [*Boost.Intrusive] is a library presenting some intrusive containers to
- the world of C++. Intrusive containers are special containers
- that offer [link intrusive.performance better performance]
- and exception safety guarantees than non-intrusive containers (like STL containers).
- The performance benefits of intrusive containers makes them ideal as a building
- block to efficiently construct complex containers like multi-index containers or
- to design high performance code like memory allocation algorithms.
- While intrusive containers were and are widely used in C, they
- became more and more forgotten in C++ due to the presence of the standard
- containers which don't support intrusive techniques.[*Boost.Intrusive] wants to
- push intrusive containers usage encapsulating the implementation in
- STL-like interfaces. Hence anyone familiar with standard containers can easily use
- [*Boost.Intrusive].
- [endsect]
- [section:introduction_building_intrusive Building Boost.Intrusive]
- There is no need to compile anything to use [*Boost.Intrusive], since it's
- a header only library. Just include your Boost header directory in your
- compiler include path.
- [endsect]
- [section:tested_compilers Tested compilers]
- [*Boost.Intrusive] has been tested on the following compilers/platforms:
- * Visual C++ >= 7.1.
- * GCC >= 4.1.
- [warning GCC < 4.3 and MSVC < 9.0 are deprecated and will be removed in the next version.]
- [endsect]
- [endsect]
- [section:intrusive_vs_nontrusive Intrusive and non-intrusive containers]
- [section:differences_intrusive_vs_nontrusive Differences between intrusive and non-intrusive containers]
- The main difference between intrusive containers and non-intrusive containers is
- that in C++ non-intrusive containers store [*copies] of values passed by the user.
- Containers use the `Allocator` template parameter to allocate the stored values:
- [c++]
- #include <list>
- #include <assert.h>
- int main()
- {
- std::list<MyClass> myclass_list;
- MyClass myclass(...);
- myclass_list.push_back(myclass);
- //The stored object is different from the original object
- assert(&myclass != &myclass_list.front());
- return 0;
- }
- To store the newly allocated copy of `myclass`, the container needs additional
- data: `std::list` usually allocates nodes that contain pointers to the
- next and previous node and the value itself. Something similar to:
- [c++]
- //A possible implementation of a std::list<MyClass> node
- class list_node
- {
- list_node *next;
- list_node *previous;
- MyClass value;
- };
- On the other hand, an intrusive container does not store copies of passed objects,
- but it stores the objects themselves. The additional data needed to insert the object
- in the container must be provided by the object itself. For example, to insert `MyClass`
- in an intrusive container that implements a linked list, `MyClass` must contain the
- needed ['next] and ['previous] pointers:
- [c++]
- class MyClass
- {
- MyClass *next;
- MyClass *previous;
- //Other members...
- };
- int main()
- {
- acme_intrusive_list<MyClass> list;
- MyClass myclass;
- list.push_back(myclass);
- //"myclass" object is stored in the list
- assert(&myclass == &list.front());
- return 0;
- }
- As we can see, knowing which additional data the class should contain is not
- an easy task. [*Boost.Intrusive] offers several intrusive containers and an easy
- way to make user classes compatible with those containers.
- [endsect]
- [section:properties_of_intrusive Properties of Boost.Intrusive containers]
- Semantically, a [*Boost.Intrusive] container is similar to a STL container
- holding pointers to objects. That is, if you have an intrusive list holding
- objects of type `T`, then `std::list<T*>` would allow you to do quite the
- same operations (maintaining and navigating a set of objects of type T and
- types derived from it).
- A non-intrusive container has some limitations:
- * An object can only belong to one container: If you want to share an object
- between two containers, you either have to store multiple copies of those
- objects or you need to use containers of pointers: `std::list<Object*>`.
- * The use of dynamic allocation to create copies of passed values can be a performance
- and size bottleneck in some applications. Normally, dynamic allocation imposes
- a size overhead for each allocation to store bookkeeping information and a
- synchronization to protected concurrent allocation from different threads.
- * Before C++11, only copies of objects could be stored in non-intrusive containers. Still
- copy or move constructors and copy or move assignment operators are required
- and non-copyable and non-movable objects can't be stored in some containers. In any case,
- [*new] objects have to be created inside the container using constructors and the same
- object can't be shared between two containers.
- * It's not possible to store a derived object in a STL-container while
- retaining its original type.
- Intrusive containers have some important advantages:
- * Operating with intrusive containers doesn't invoke any memory management at all.
- The time and size overhead associated with dynamic memory can be minimized.
- * The same object can be inserted in more than one container at the same time with
- a tiny overhead in the object size.
- * Iterating an Intrusive container needs less memory accesses than the semantically
- equivalent container of pointers: iteration is faster.
- * Intrusive containers offer better exception guarantees than non-intrusive containers.
- In some situations intrusive containers offer a no-throw guarantee that can't be
- achieved with non-intrusive containers.
- * The computation of an iterator to an element from a pointer or reference to that element
- is a constant time operation (computing the position of `T*` in a `std::list<T*>` has
- linear complexity).
- * Intrusive containers offer predictability when inserting and erasing objects since no
- memory management is done with intrusive containers. Memory management usually is not a predictable
- operation so complexity guarantees from non-intrusive containers are looser than the guarantees
- offered by intrusive containers.
- Intrusive containers have also downsides:
- * Each type stored in an intrusive container needs additional memory holding the
- maintenance information needed by the container. Hence, whenever a certain type will
- be stored in an intrusive container [*you have to change the definition of that type]
- appropriately. Although this task is easy with [*Boost.Intrusive], touching the
- definition of a type is sometimes a crucial issue.
- * In intrusive containers you don't store a copy of an object, [*but rather the original object
- is linked with other objects in the container]. Objects don't need copy-constructors or assignment
- operators to be stored in intrusive containers. But you have to take care of possible side effects,
- whenever you change the contents of an object (this is especially important for
- associative containers).
- * The user [*has to manage the lifetime of inserted objects] independently from the
- containers.
- * Again you have to be [*careful]: in contrast to STL containers [*it's easy to render an
- iterator invalid] without touching the intrusive container directly, because the object
- can be disposed before is erased from the container.
- * [*Boost.Intrusive] containers are [*non-copyable and non-assignable]. Since intrusive
- containers don't have allocation capabilities, these operations make no sense. However,
- swapping can be used to implement move capabilities. To ease the implementation of
- copy constructors and assignment operators of classes storing [*Boost.Intrusive]
- containers, [*Boost.Intrusive] offers special cloning functions. See
- [link intrusive.clone_from Cloning Boost.Intrusive containers] section for more information.
- * Analyzing the thread safety of a program that uses containers is harder with intrusive containers, because
- the container might be modified indirectly without an explicit call to a container member.
- [table Summary of intrusive containers advantages and disadvantages
- [[Issue] [Intrusive] [Non-intrusive]]
- [[Memory management] [External] [Internal through allocator]]
- [[Insertion/Erasure time] [Faster] [Slower]]
- [[Memory locality] [Better] [Worse]]
- [[Can insert the same object in more than one container] [Yes] [No]]
- [[Exception guarantees] [Better] [Worse]]
- [[Computation of iterator from value] [Constant] [Non-constant]]
- [[Insertion/erasure predictability] [High] [Low]]
- [[Memory use] [Minimal] [More than minimal]]
- [[Insert objects by value retaining polymorphic behavior] [Yes] [No (slicing)]]
- [[User must modify the definition of the values to insert] [Yes] [No]]
- [[Containers are copyable] [No] [Yes]]
- [[Inserted object's lifetime managed by] [User (more complex)] [Container (less complex)]]
- [[Container invariants can be broken without using the container] [Easier] [Harder (only with containers of pointers)]]
- [[Thread-safety analysis] [Harder] [Easier]]
- ]
- For a performance comparison between Intrusive and Non-intrusive containers see
- [link intrusive.performance Performance] section.
- [endsect]
- [endsect]
- [section:usage How to use Boost.Intrusive]
- If you plan to insert a class in an intrusive container, you have to make some decisions
- influencing the class definition itself. Each class that will be used in an intrusive
- container needs some appropriate data members storing the information needed by the
- container. We will take a simple intrusive container, the intrusive list
- ([classref boost::intrusive::list boost::intrusive::list]), for the following
- examples, but all [*Boost.Intrusive] containers are very similar. To compile
- the example using [classref boost::intrusive::list boost::intrusive::list],
- just include:
- [c++]
- #include <boost/intrusive/list.hpp>
- Every class to be inserted in an intrusive container, needs to contain a hook that
- will offer the necessary data and resources to be insertable in the container.
- With [*Boost.Intrusive] you just choose the hook to be a public base class or
- a public member of the class to be inserted. [*Boost.Intrusive] also offers
- more flexible hooks for advanced users, as explained in the chapter
- [link intrusive.function_hooks Using function hooks], but usually base or member
- hooks are good enough for most users.
- [section:usage_base_hook Using base hooks]
- For [classref boost::intrusive::list list], you can publicly derive from
- [classref boost::intrusive::list_base_hook list_base_hook].
- [c++]
- template <class ...Options>
- class list_base_hook;
- The class can take several options. [*Boost.Intrusive] classes receive arguments in the
- form `option_name<option_value>`. You can specify the following options:
- * [*`tag<class Tag>`]: this argument serves as a tag, so you can derive from more than one
- [classref boost::intrusive::list_base_hook list_base_hook] and hence put an object in
- multiple intrusive lists at the same time. An incomplete type can serve as a tag.
- If you specify two base hooks, you [*must] specify a different
- tag for each one. Example: `list_base_hook< tag<tag1> >`. If no tag is specified
- a default one will be used (more on default tags later).
- * [*`link_mode<link_mode_type LinkMode>`]: The second template argument controls the
- linking policy. [*Boost.Intrusive] currently supports
- 3 modes: `normal_link`, `safe_link` and `auto_unlink`. By default, `safe_link`
- mode is used. More about these in sections
- [link intrusive.safe_hook Safe hooks] and [link intrusive.auto_unlink_hooks Auto-unlink hooks].
- Example: `list_base_hook< link_mode<auto_unlink> >`
- * [*`void_pointer<class VoidPointer>`]: this option is the pointer type to be used
- internally in the hook. The default value is `void *`, which means that raw pointers
- will be used in the hook. More about this in the section titled
- [link intrusive.using_smart_pointers Using smart pointers with Boost.Intrusive containers].
- Example: `list_base_hook< void_pointer< my_smart_ptr<void> >`
- For the following examples, let's forget the options and use the default values:
- [c++]
- #include <boost/intrusive/list.hpp>
- using namespace boost::intrusive;
- class Foo
- //Base hook with default tag, raw pointers and safe_link mode
- : public list_base_hook<>
- { /**/ };
- After that, we can define the intrusive list:
- [c++]
- template <class T, class ...Options>
- class list;
- `list` receives the type to be inserted in the container (`T`) as the first parameter
- and optionally, the user can specify options. We have 3 option types:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: All these options specify the relationship
- between the type `T` to be inserted in the list and the hook (since we can
- have several hooks in the same `T` type). `member_hook` will be explained
- a bit later and `value_traits` will be explained in the
- [link intrusive.value_traits Containers with custom ValueTraits] section.
- [*If no option is specified, the container will be configured to use the base
- hook with the default tag].
- Some options configured for the hook (the type of the pointers, link mode, etc.)
- will be propagated to the container.
- * [*`constant_time_size<bool Enabled>`]: Specifies if a constant time `size()`
- function is demanded for the container. This will instruct the intrusive
- container to store an additional member to keep track of the current size of the
- container. By default, constant-time size is activated.
- * [*`size_type<class SizeType>`]: Specifies an unsigned type that can hold
- the size of the container. This type will be the type returned by `list.size()`
- and the type stored in the intrusive container if `constant_time_size<true>`
- is requested.
- The user normally will not need to change this type, but some
- containers can have a `size_type` that might be different from `std::size_t`
- (for example, STL-like containers use the `size_type` defined by their allocator).
- [*Boost.Intrusive] can be used to implement such containers specifying the
- type of the size. By default the type is `std::size_t`.
- Example of a constant-time size intrusive list that will store Foo objects, using
- the base hook with the default tag:
- [c++]
- typedef list<Foo> FooList;
- Example of an intrusive list with non constant-time size that will store Foo objects:
- [c++]
- typedef list<Foo, constant_time_size<false> > FooList;
- Remember that the user must specify the base hook in the container declaration
- if the base hook has no default tag, because that usually means that the type
- has more than one base hook, and a container shall know which hook will be
- using:
- [c++]
- #include <boost/intrusive/list.hpp>
- using namespace boost::intrusive;
- struct my_tag1;
- struct my_tag2;
- typedef list_base_hook< tag<my_tag> > BaseHook;
- typedef list_base_hook< tag<my_tag2> > BaseHook2;
- class Foo : public BaseHook, public BaseHook2
- { /**/ };
- typedef list< Foo, base_hook<BaseHook> > FooList;
- typedef list< Foo, base_hook<BaseHook2> > FooList2;
- Once the list is defined, we can use it:
- [c++]
- //An object to be inserted in the list
- Foo foo_object;
- FooList list;
- list.push_back(object);
- assert(&list.front() == &foo_object);
- [endsect]
- [section:usage_member_hook Using member hooks]
- Sometimes an 'is-a' relationship between list hooks and the list value types
- is not desirable. In this case, using a member hook as a data member instead of
- 'disturbing' the hierarchy might be the right way: you can add a public data
- member `list_member_hook<...>` to your class.
- This class can be configured with the same options as `list_base_hook`
- except the option `tag`:
- [c++]
- template <class ...Options>
- class list_member_hook;
- Example:
- [c++]
- #include <boost/intrusive/list.hpp>
- class Foo
- {
- public:
- list_member_hook<> hook_;
- //...
- };
- When member hooks are used, the `member_hook` option is used to configure the
- list:
- [c++]
- //This option will configure "list" to use the member hook
- typedef member_hook<Foo, list_member_hook<>, &Foo::hook_> MemberHookOption;
- //This list will use the member hook
- typedef list<Foo, MemberHookOption> FooList;
- Now we can use the container:
- [c++]
- //An object to be inserted in the list
- Foo foo_object;
- FooList list;
- list.push_back(object);
- assert(&list.front() == &foo_object);
- [endsect]
- However, member hooks have some implementation limitations: If there is a virtual inheritance
- relationship between the parent and the member hook, then the distance between the parent
- and the hook is not a compile-time fixed value so obtaining the address of
- the parent from the member hook is not possible without reverse engineering compiler
- produced RTTI. Apart from this, the non-standard pointer to member implementation for classes
- with complex inheritance relationships in MSVC ABI compatible-compilers is not supported
- by member hooks since it also depends on compiler-produced RTTI information.
- [section:usage_both_hooks Using both hooks]
- You can insert the same object in several intrusive containers at the same time,
- using one hook per container. This is a full example using base and member hooks:
- [import ../example/doc_how_to_use.cpp]
- [doc_how_to_use_code]
- [endsect]
- [section:usage_lifetime Object lifetime]
- Even if the interface of [classref boost::intrusive::list list] is similar to
- `std::list`, its usage is a bit different: You always have to keep in mind that
- you directly store objects in intrusive containers, not copies. The lifetime of a
- stored object is not bound to or managed by the container:
- * When the container gets destroyed before the object, the object is not destroyed,
- so you have to be careful to avoid resource leaks.
- * When the object is destroyed before the container, your program is likely to crash,
- because the container contains a pointer to an non-existing object.
- [endsect]
- [endsect]
- [section:usage_when When to use?]
- Intrusive containers can be used for highly optimized algorithms, where speed is a crucial
- issue and:
- * additional memory management should be avoided.
- * the programmer needs to efficiently track the construction and destruction of objects.
- * exception safety, especially the no-throw guarantee, is needed.
- * the computation of an iterator to an element from a pointer or reference
- to that element should be a constant time operation.
- * it's important to achieve a well-known worst-time system response.
- * localization of data (e.g. for cache hit optimization) leads to measurable effects.
- The last point is important if you have a lot of containers over a set of elements. E.g. if
- you have a vector of objects (say, `std::vector<Object>`), and you also have a list
- storing a subset of those objects (`std::list<Object*>`), then operating on an Object
- from the list iterator (`std::list<Object*>::iterator`) requires two steps:
- * Access from the iterator (usually on the stack) to the list node storing a pointer to `Object`.
- * Access from the pointer to `Object` to the Object stored in the vector.
- While the objects themselves are tightly packed in the memory of the vector
- (a vector's memory is guaranteed to be contiguous), and form something
- like a data block, list nodes may be dispersed in the heap memory.
- Hence depending on your system you might get a lot of cache misses. The same doesn't hold
- for an intrusive list. Indeed, dereferencing an iterator from an intrusive list is performed in
- the same two steps as described above. But the list node is already embedded in the Object, so
- the memory is directly tracked from the iterator to the Object.
- It's also possible to use intrusive containers when the objects to be stored can
- have different or unknown size. This allows storing base and derived objects
- in the same container, as shown in the following example:
- [import ../example/doc_window.cpp]
- [doc_window_code]
- Due to certain properties of intrusive containers
- they are often more difficult to use than their STL-counterparts. That's why you
- should avoid them in public interfaces of libraries. Classes to be stored in intrusive
- containers must change their implementation to store the hook and this is not always
- possible or desirable.
- [endsect]
- [section:concepts_summary Concept summary]
- Here is a small summary of the basic concepts that will be used in the following
- chapters:
- [variablelist Brief Concepts Summary
- [[Node Algorithms][A class containing typedefs and static functions that define
- basic operations that can be applied to a group of `node`s. It's independent
- from the node definition and configured using a NodeTraits template
- parameter that describes the node.]]
- [[Node Traits][A class that stores basic information and operations to insert a node into a group of nodes.]]
- [[Hook][A class that a user must add as a base class or as a member to make the user class compatible with intrusive containers. A Hook encapsulates a `node`]]
- [[Intrusive Container][A class that stores user classes that have the needed hooks. It takes a ValueTraits template parameter as configuration information.]]
- [[Semi-Intrusive Container][Similar to an intrusive container but a semi-intrusive container needs additional memory (e.g. an auxiliary array) to work.]]
- [[Value Traits][A class containing typedefs and operations to obtain the node to be used by Node Algorithms from the user class and the inverse.]]
- ]
- [endsect]
- [section:presenting_containers Presenting Boost.Intrusive containers]
- [*Boost.Intrusive] offers a wide range of intrusive containers:
- * [*slist]: An intrusive singly linked list. The size overhead is very small
- for user classes (usually the size of one pointer) but many operations have linear
- time complexity, so the user must be careful if he wants to avoid performance problems.
- * [*list]: A `std::list` like intrusive linked list. The size overhead is quite
- small for user classes (usually the size of two pointers). Many operations have
- constant time complexity.
- * [*set/multiset/rbtree]: `std::set/std::multiset` like intrusive associative containers
- based on red-black trees.
- The size overhead is moderate for user classes (usually the size of three pointers).
- Many operations have logarithmic time complexity.
- * [*avl_set/avl_multiset/avltree]: A `std::set/std::multiset` like intrusive associative
- containers based on AVL trees.
- The size overhead is moderate for user classes (usually the size of three pointers).
- Many operations have logarithmic time complexity.
- * [*splay_set/splay_multiset/splaytree]: `std::set/std::multiset` like intrusive associative
- containers based on splay trees. Splay trees have no constant operations, but they
- have some interesting caching properties.
- The size overhead is moderate for user classes (usually the size of three pointers).
- Many operations have logarithmic time complexity.
- * [*sg_set/sg_multiset/sgtree]: A `std::set/std::multiset` like intrusive associative
- containers based on scapegoat trees. Scapegoat can be configured with the desired
- balance factor to achieve the desired rebalancing frequency/search time compromise.
- The size overhead is moderate for user classes (usually the size of three pointers).
- Many operations have logarithmic time complexity.
- [*Boost.Intrusive] also offers semi-intrusive containers:
- * [*unordered_set/unordered_multiset]: `std::tr1::unordered_set/std::tr1::unordered_multiset`
- like intrusive unordered associative containers.
- The size overhead is moderate for user classes (an average of two pointers per element).
- Many operations have amortized constant time complexity.
- Most of these intrusive containers can be configured with constant or linear time
- size:
- * [*Linear time size]: The intrusive container doesn't hold a size member that is
- updated with every insertion/erasure. This implies that the `size()` function doesn't have constant
- time complexity. On the other hand, the container is smaller, and some operations, like
- `splice()` taking a range of iterators in linked lists, have constant time complexity
- instead of linear complexity.
- * [*Constant time size]: The intrusive container holds a size member that is updated
- with every insertion/erasure. This implies that the `size()` function has constant time
- complexity. On the other hand, increases the size of the container, and some operations,
- like `splice()` taking a range of iterators, have linear time complexity in linked lists.
- To make user classes compatible with these intrusive containers [*Boost.Intrusive]
- offers two types of hooks for each container type:
- * [*Base hook]: The hook is stored as a public base class of the user class.
- * [*Member hook]: The hook is stored as a public member of the user class.
- Apart from that, [*Boost.Intrusive] offers additional features:
- * [*Safe mode hooks]: Hook constructor initializes the internal `node` to a well-known
- safe state and intrusive containers check that state before inserting a value in the
- container using that hook. When erasing an element from the container, the container
- puts the `node` of the hook in the safe state again. This allows a safer use mode and it can
- be used to detect programming errors. It implies a slight performance overhead in some
- operations and can convert some constant time operations to linear time operations.
- * [*Auto-unlink hooks]: The hook destructor removes the object from the container
- automatically and the user can safely unlink the object from the container without
- referring to the container.
- * [*Non-raw pointers]: If the user wants to use smart pointers instead of raw pointers,
- [*Boost.Intrusive] hooks can
- be configured to use any type of pointer. This configuration information is also
- transmitted to the containers, so all the internal pointers used by intrusive containers
- configured with these hooks will be smart pointers. As an example,
- [*Boost.Interprocess] defines a smart pointer compatible with shared memory,
- called `offset_ptr`. [*Boost.Intrusive] can be configured to use this smart pointer
- to allow shared memory intrusive containers.
- [endsect]
- [section:safe_hook Safe hooks]
- [section:features Features of the safe mode]
- [*Boost.Intrusive] hooks can be configured to operate in safe-link mode.
- The safe mode is activated by default, but it can be also explicitly activated:
- [c++]
- //Configuring the safe mode explicitly
- class Foo : public list_base_hook< link_mode<safe_link> >
- {};
- With the safe mode the user can detect if the object
- is actually inserted in a container without any external reference. Let's review the basic features of the safe mode:
- * Hook's constructor puts the hook in a well-known default state.
- * Hook's destructor checks if the hook is in the well-known default state. If not,
- an assertion is raised.
- * Every time an object is inserted in the intrusive container, the container
- checks if the hook is in the well-known default state. If not,
- an assertion is raised.
- * Every time an object is being erased from the intrusive container, the container
- puts the erased object in the well-known default state.
- With these features, without any external reference the user can know if the object
- has been inserted in a container by calling the `is_linked()` member function.
- If the object is not actually inserted
- in a container, the hook is in the default state, and if it is inserted in a container, the
- hook is not in the default state.
- [endsect]
- [section:configuring Configuring safe-mode assertions]
- By default, all safe-mode assertions raised by [*Boost-Intrusive] hooks
- and containers in are implemented using `BOOST_ASSERT`, which can be configured by
- the user. See [@http://www.boost.org/libs/utility/assert.html] for more
- information about `BOOST_ASSERT`.
- `BOOST_ASSERT` is globally configured, so the user might
- want to redefine intrusive safe-mode assertions without modifying the global
- `BOOST_ASSERT`. This can be achieved redefining the following macros:
- * `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT`: This assertion will be
- used in insertion functions of the intrusive containers to check that
- the hook of the value to be inserted is default constructed.
- * `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`: This assertion will be
- used in hooks' destructors to check that the hook is in a default state.
- If any of these macros is not redefined, the assertion will default to `BOOST_ASSERT`.
- If `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT` or `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`
- is defined and the programmer needs to include a file to configure that assertion, it can define
- `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE` or `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT_INCLUDE`
- with the name of the file to include:
- [c++]
- #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT MYASSERT
- #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE <myassert.h>
- [endsect]
- [endsect]
- [section:auto_unlink_hooks Auto-unlink hooks]
- [section:auto_unlink_hooks_what What's an auto-unlink hook?]
- [*Boost.Intrusive] offers additional hooks with unique features:
- * When the destructor of the hook is called, the hook checks if the node is inserted
- in a container. If so, the hook removes the node from the container.
- * The hook has a member function called `unlink()` that can be used to unlink the
- node from the container at any time, without having any reference to the container,
- if the user wants to do so.
- These hooks have exactly the same size overhead as their analog non auto-unlinking
- hooks, but they have a restriction: they can only be used with
- [link intrusive.presenting_containers non-constant time size containers].
- There is a reason for this:
- * Auto-unlink hooks don't store any reference to the container where they are inserted.
- * Only containers with non constant-time `size()` allow removing an object from the container
- without referring to the container.
- This auto-unlink feature is useful in certain applications
- but it must be used [*very carefully]:
- * If several threads are using the same container the destructor of the auto-unlink
- hook will be called without any thread synchronization so removing the object is
- thread-unsafe.
- * Container contents change silently without modifying the container directly.
- This can lead to surprising effects.
- These auto-unlink hooks have also safe-mode properties:
- * Hooks' constructors put the hook in a well-known default state.
- * Every time an object is inserted in the intrusive container, the container
- checks if the hook is in the well-known default state. If not,
- an assertion is raised.
- * Every time an object is erased from an intrusive container, the container
- puts the erased object in the well-known default state.
- [endsect]
- [section:auto_unlink_hooks_example Auto-unlink hook example]
- Let's see an example of an auto-unlink hook:
- [import ../example/doc_auto_unlink.cpp]
- [doc_auto_unlink_code]
- [endsect]
- [section:auto_unlink_and_constant_time Auto-unlink hooks and containers with constant-time `size()`]
- As explained, [*Boost.Intrusive] auto-unlink hooks are incompatible with containers
- that have constant-time `size()`, so if you try to define such container with an
- auto-unlink hook's value_traits, you will get a static assertion:
- [c++]
- #include <boost/intrusive/list.hpp>
- using boost::intrusive;
- struct MyTag;
- class MyClass : public list_base_hook< link_mode<auto_unlink> >
- {/**/};
- list <MyClass, constant_time_size<true> > bad_list;
- int main()
- {
- bad_list list;
- return 0;
- }
- leads to an error similar to:
- [pre
- error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>'
- ]
- Pointing to code like this:
- [c++]
- //Constant-time size is incompatible with auto-unlink hooks!
- BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));
- This way, there is no way to compile a program if you try to use auto-unlink hooks
- in constant-time size containers.
- [endsect]
- [endsect]
- [section:slist Intrusive singly linked list: slist]
- [classref boost::intrusive::slist slist] is the simplest intrusive container of
- [*Boost.Intrusive]: a singly linked list. The memory overhead
- it imposes is 1 pointer per node. The size of an empty, non constant-time size
- [classref boost::intrusive::slist slist] is the size of 1 pointer. This
- lightweight memory overhead comes with drawbacks, though: many operations have
- linear time complexity, even some that usually are constant time, like
- [classref boost::intrusive::slist::swap swap]. [classref boost::intrusive::slist slist]
- only provides forward iterators.
- For most cases, a doubly linked list is preferable because it offers more
- constant-time functions with a slightly bigger size overhead.
- However, for some applications like
- constructing more elaborate containers, singly linked lists are essential
- because of their low size overhead.
- [section:slist_hooks slist hooks]
- Like the rest of [*Boost.Intrusive] containers,
- [classref boost::intrusive::slist slist] has two hook types:
- [c++]
- template <class ...Options>
- class slist_base_hook;
- * [classref boost::intrusive::slist_base_hook slist_base_hook]:
- the user class derives publicly from
- [classref boost::intrusive::slist_base_hook slist_base_hook] to make
- it [classref boost::intrusive::slist slist]-compatible.
- [c++]
- template <class ...Options>
- class slist_member_hook;
- * [classref boost::intrusive::slist_member_hook slist_member_hook]:
- the user class contains a public
- [classref boost::intrusive::slist_member_hook slist_member_hook] to make
- it [classref boost::intrusive::slist slist]-compatible.
- [classref boost::intrusive::slist_base_hook slist_base_hook] and
- [classref boost::intrusive::slist_member_hook slist_member_hook]
- receive the same options explained in
- the section [link intrusive.usage How to use Boost.Intrusive]:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one slist hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- [endsect]
- [section:slist_container slist container]
- [c++]
- template <class T, class ...Options>
- class slist;
- [classref boost::intrusive::slist slist] receives the options explained in
- the section [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`.
- [classref boost::intrusive::slist slist] can receive additional options:
- * [*`linear<bool Enable>`]: the singly linked list is implemented as a
- null-terminated list instead of a circular list. This allows `O(1)` swap,
- but losses some operations like `container_from_end_iterator`.
- * [*`cache_last<bool Enable>`]: `slist` also stores a pointer to the
- last element of the singly linked list. This allows `O(1)` swap,
- `splice_after(iterator, slist &)` and makes the list offer new functions
- like `push_back(reference)` and `back()`. Logically, the size an empty list is
- increased in `sizeof(void_pointer)` and the cached last node pointer must
- be updated in every operation, and that might incur in a slight performance impact.
- `auto_unlink` hooks are not usable if `linear<true>` and/or `cache_last<true>` options are
- used. If `auto_unlink` hooks are used and those options are specified, a static
- assertion will be raised.
- [endsect]
- [section:slist_example Example]
- Now let's see a small example using both hooks:
- [import ../example/doc_slist.cpp]
- [doc_slist_code]
- [endsect]
- [endsect]
- [section:list Intrusive doubly linked list: list]
- [classref boost::intrusive::list list] is a doubly linked list. The memory overhead
- it imposes is 2 pointers per node. An empty, non constant-time size [classref boost::intrusive::list list]
- also has the size of 2 pointers. [classref boost::intrusive::list list]
- has many more constant-time operations than [classref boost::intrusive::slist slist]
- and provides a bidirectional iterator. It is recommended to use
- [classref boost::intrusive::list list] instead of
- [classref boost::intrusive::slist slist] if the size overhead is acceptable:
- [section:list_hooks list hooks]
- Like the rest of [*Boost.Intrusive] containers,
- [classref boost::intrusive::list list] has two hook types:
- [c++]
- template <class ...Options>
- class list_base_hook;
- * [classref boost::intrusive::list_base_hook list_base_hook]: the user class
- derives publicly from [classref boost::intrusive::list_base_hook list_base_hook]
- to make it [classref boost::intrusive::list list]-compatible.
- [c++]
- template <class ...Options>
- class list_member_hook;
- * [classref boost::intrusive::list_member_hook list_member_hook]:
- the user class contains a public
- [classref boost::intrusive::list_member_hook list_member_hook] to make
- it [classref boost::intrusive::list list]-compatible.
- [classref boost::intrusive::list_base_hook list_base_hook] and
- [classref boost::intrusive::list_member_hook list_member_hook] receive
- the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one list hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- [endsect]
- [section:list_container list container]
- [c++]
- template <class T, class ...Options>
- class list;
- [classref boost::intrusive::list list] receives the same options explained in
- the section [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- [endsect]
- [section:list_example Example]
- Now let's see a small example using both hooks:
- [import ../example/doc_list.cpp]
- [doc_list_code]
- [endsect]
- [endsect]
- [section:set_multiset Intrusive associative containers: set, multiset, rbtree]
- [*Boost.Intrusive] also offers associative containers that can be very useful
- when creating more complex associative containers, like containers maintaining
- one or more indices with different sorting semantics. Boost.Intrusive associative
- containers, like most STL associative container implementations are based on
- red-black trees.
- The memory overhead of these containers is usually 3 pointers and a bit (with
- alignment issues, this means 3 pointers and an integer).
- This size can be reduced to 3 pointers if pointers have even alignment
- (which is usually true in most systems).
- An empty, non constant-time size [classref boost::intrusive::set set],
- [classref boost::intrusive::multiset multiset] or
- [classref boost::intrusive::rbtree rbtree]
- has also the size of 3 pointers and an integer (3 pointers when optimized for size).
- These containers have logarithmic complexity in many
- operations like
- searches, insertions, erasures, etc. [classref boost::intrusive::set set] and
- [classref boost::intrusive::multiset multiset] are the
- intrusive equivalents of standard `std::set` and `std::multiset` containers.
- [classref boost::intrusive::rbtree rbtree] is a superset of
- [classref boost::intrusive::set set] and
- [classref boost::intrusive::multiset multiset] containers that offers
- functions to insert unique and multiple keys.
- [section:set_multiset_hooks set, multiset and rbtree hooks]
- [classref boost::intrusive::set set],
- [classref boost::intrusive::multiset multiset] and
- [classref boost::intrusive::rbtree rbtree] share the same hooks.
- This is an advantage, because the same
- user type can be inserted first in a [classref boost::intrusive::multiset multiset]
- and after that in [classref boost::intrusive::set set] without
- changing the definition of the user class.
- [c++]
- template <class ...Options>
- class set_base_hook;
- * [classref boost::intrusive::set_base_hook set_base_hook]:
- the user class derives publicly from
- [classref boost::intrusive::set_base_hook set_base_hook] to make
- it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
- [c++]
- template <class ...Options>
- class set_member_hook;
- * [classref boost::intrusive::set_member_hook set_member_hook]:
- the user class contains a public
- [classref boost::intrusive::set_member_hook set_member_hook] to make
- it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.
- [classref boost::intrusive::set_base_hook set_base_hook] and
- [classref boost::intrusive::set_member_hook set_member_hook] receive
- the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive] plus a size optimization option:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one base hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- * [*`optimize_size<bool Enable>`]: The hook will be optimized for size
- instead of speed. The hook will embed the color bit of the red-black
- tree node in the parent pointer if pointer alignment is even.
- In some platforms, optimizing the size might reduce speed performance a bit
- since masking operations will be needed to access parent pointer and color attributes,
- in other platforms this option improves performance due to improved memory locality.
- Default: `optimize_size<false>`.
- [endsect]
- [section:set_multiset_containers set, multiset and rbtree containers]
- [c++]
- template <class T, class ...Options>
- class set;
- template <class T, class ...Options>
- class multiset;
- template <class T, class ...Options>
- class rbtree;
- These containers receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive an additional option:
- * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `compare< std::less<key_type> >`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- [endsect]
- [section:set_multiset_example Example]
- Now let's see a small example using both hooks and both containers:
- [import ../example/doc_set.cpp]
- [doc_set_code]
- [endsect]
- [endsect]
- [section:unordered_set_unordered_multiset Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset]
- [*Boost.Intrusive] also offers hashed containers that can be very useful to implement
- fast-lookup containers. These containers
- ([classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset])
- are semi-intrusive containers: they need additional memory apart from the hook
- stored in the `value_type`. This additional
- memory must be passed in the constructor of the container.
- Unlike C++ TR1 unordered associative containers (which are also hashed containers),
- the contents of these semi-intrusive containers are not rehashed to maintain a
- load factor: that would require memory management and intrusive containers don't
- implement any memory management at all. However, the user can request an explicit
- rehashing passing a new bucket array.
- This also offers an additional guarantee over TR1 unordered associative containers:
- [*iterators are not invalidated when inserting an element] in the container.
- As with TR1 unordered associative containers, rehashing invalidates iterators,
- changes ordering between elements and changes which buckets elements appear in,
- but does not invalidate pointers or references to elements.
- Apart from expected hash and equality function objects, [*Boost.Intrusive] unordered
- associative containers' constructors take an argument specifying an auxiliary
- bucket vector to be used by the container.
- [section:unordered_set_unordered_multiset_performance unordered_set and unordered_multiset performance notes]
- The size overhead for a hashed container is moderate: 1 pointer per value plus
- a bucket array per container. The size of an element of the bucket array
- is usually one pointer. To obtain a good performance hashed container,
- the bucket length is usually the same as the number of elements that the
- container contains, so a well-balanced hashed container (`bucket_count()` is
- equal to `size()` ) will have an equivalent overhead of two pointers per element.
- An empty, non constant-time size [classref boost::intrusive::unordered_set unordered_set] or
- [classref boost::intrusive::unordered_multiset unordered_multiset]
- has also the size of `bucket_count()` pointers.
- Insertions, erasures, and searches, have amortized constant-time complexity in
- hashed containers. However, some worst-case guarantees are linear. See
- [classref boost::intrusive::unordered_set unordered_set] or
- [classref boost::intrusive::unordered_multiset unordered_multiset] for complexity guarantees
- of each operation.
- [*Be careful with non constant-time size hashed containers]: some operations, like
- `empty()`, have linear complexity, unlike other [*Boost.Intrusive] containers.
- [endsect]
- [section:unordered_set_unordered_multiset_hooks unordered_set and unordered_multiset hooks]
- [classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset] share the same hooks. This is an advantage, because the same
- user type can be inserted first in a [classref boost::intrusive::unordered_multiset unordered_multiset] and after that in [classref boost::intrusive::unordered_set unordered_set] without
- changing the definition of the user class.
- [c++]
- template <class ...Options>
- class unordered_set_base_hook;
- * [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook]:
- the user class derives publicly from
- [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] to make
- it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.
- [c++]
- template <class ...Options>
- class unordered_set_member_hook;
- * [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook]:
- the user class contains a public
- [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] to make
- it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.
- [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] and
- [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] receive
- the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one base hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- Apart from them, these hooks offer additional options:
- * [*`store_hash<bool Enabled>`]: This option reserves additional space in
- the hook to store the hash value of the object once it's introduced in the
- container. When this option is used, the unordered container will store
- the calculated hash value in the hook and rehashing operations won't need
- to recalculate the hash of the value.
- This option will improve the performance of unordered containers when
- rehashing is frequent or hashing the value is a slow operation.
- Default: `store_hash<false>`.
- * [*`optimize_multikey<bool Enabled>`]: This option reserves additional space in
- the hook that will be used to group equal elements in unordered multisets,
- improving significantly the performance when many equal values are inserted
- in these containers. Default: `optimize_multikey<false>`.
- [endsect]
- [section:unordered_set_unordered_multiset_containers unordered_set and unordered_multiset containers]
- [c++]
- template<class T, class ...Options>
- class unordered_set;
- template<class T, class ...Options>
- class unordered_multiset;
- As mentioned, unordered containers need an auxiliary array to work. [*Boost.Intrusive]
- unordered containers receive this auxiliary array packed in a type called `bucket_traits`
- (which can be also customized by a container option). All unordered containers receive
- a `bucket_traits` object in their constructors. The default `bucket_traits` class
- is initialized with a pointer to an array of buckets and its size:
- [c++]
- #include <boost/intrusive/unordered_set.hpp>
- using namespace boost::intrusive;
- struct MyClass : public unordered_set_base_hook<>
- {};
- typedef unordered_set<MyClass>::bucket_type bucket_type;
- typedef unordered_set<MyClass>::bucket_traits bucket_traits;
- int main()
- {
- bucket_type buckets[100];
- unordered_set<MyClass> uset(bucket_traits(buckets, 100));
- return 0;
- }
- Each hashed container needs [*its own bucket traits], that is, [*its own
- bucket vector]. Two hashed containers
- [*can't] share the same `bucket_type` elements. The bucket array [*must] be
- destroyed [*after] the container using it is destroyed, otherwise, the result
- is undefined.
- [classref boost::intrusive::unordered_set unordered_set] and
- [classref boost::intrusive::unordered_multiset unordered_multiset]
- receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive additional options:
- * [*`equal<class Equal>`]: Equality function for the objects to be inserted
- in containers. Default: `equal< std::equal_to<T> >`
- * [*`hash<class Hash>`]: Hash function to be used in the container.
- Default: `hash< boost::hash<T> >`
- * [*`bucket_traits<class BucketTraits>`]: A type that wraps the bucket vector to
- be used by the unordered container. Default: a type initialized by the address
- and size of a bucket array and stores both variables internally.
- * [*`power_2_buckets<bool Enabled>`]: The user guarantees that only bucket arrays
- with power of two length will be used. The container will then use masks instead of modulo
- operations to obtain the bucket number from the hash value. Masks are faster than
- modulo operations and for some applications modulo operations can impose
- a considerable overhead. In debug mode an assertion will be raised if the user
- provides a bucket length that is not power of two.
- Default: `power_2_buckets<false>`.
- * [*`cache_begin<bool Enabled>`]:
- [*Note: this option is not compatible with `auto_unlink` hooks].
- Due to its internal structure, finding the first
- element of an unordered container (`begin()` operation) is
- amortized constant-time. It's possible to speed up `begin()` and other operations
- related to it (like `clear()`) if the container caches internally the position
- of the first element. This imposes the overhead of one pointer to the size
- of the container. Default: `cache_begin<false>`.
- * [*`compare_hash<bool Enabled>`]:
- [*Note: this option requires `store_hash<true>` option in the hook].
- When the comparison function is expensive,
- (e.g. strings with a long common predicate) sometimes (specially when the
- load factor is high or we have many equivalent elements in an
- [classref boost::intrusive::unordered_multiset unordered_multiset] and
- no `optimize_multikey<>` is activated in the hook)
- the equality function is a performance problem. Two equal values must have
- equal hashes, so comparing the hash values of two elements before using the
- comparison functor can speed up some implementations.
- * [*`incremental<bool Enabled>`]: Activates incremental hashing (also known as Linear Hashing).
- This option implies `power_2_buckets<true>` and the container will require power of two buckets.
- For more information on incremental hashing, see
- [@http://en.wikipedia.org/wiki/Linear_hashing `Linear hash` on Wikipedia]
- Default: `incremental<false>`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- [endsect]
- [section:unordered_set_unordered_multiset_example Example]
- Now let's see a small example using both hooks and both containers:
- [import ../example/doc_unordered_set.cpp]
- [doc_unordered_set_code]
- [endsect]
- [section:custom_bucket_traits Custom bucket traits]
- Instead of using the default `bucket_traits` class to store the bucket array, a user
- can define his own class to store the bucket array using the [*['bucket_traits<>]]
- option. A user-defined bucket-traits must fulfill the following interface:
- [c++]
- class my_bucket_traits
- {
- bucket_ptr bucket_begin();
- const_bucket_ptr bucket_begin() const;
- std::size_t bucket_count() const;
- };
- The following bucket traits just stores a pointer to the bucket
- array but the size is a compile-time constant. Note the use of the auxiliary
- [classref boost::intrusive::unordered_bucket unordered_bucket] and
- [classref boost::intrusive::unordered_bucket_ptr unordered_bucket_ptr]
- utilities to obtain the type of the bucket and its pointer before defining
- the unordered container:
- [import ../example/doc_bucket_traits.cpp]
- [doc_bucket_traits]
- [endsect]
- [endsect]
- [section:map_multimap Map and multimap-like interface for associative containers]
- Implementing map-like intrusive containers is not a trivial task as
- STL's `std::map` and `std::multimap` containers store copies of a `value_type` which is defined
- as `std::pair<const key_type, mapped_type>`. In order to reproduce this interface in [*Boost.Intrusive]
- it shall require that objects stored in the intrusive containers contain that `std::pair` member with
- `pair.first` hardcoded as the key part and `pair.second` hardcoded as the `mapped_type`, which
- is limiting and also not very useful in practice. Any intrusive associative container can be used like
- a map using [link intrusive.advanced_lookups_insertions advanced lookup and insertions] and the user
- can change the key type in each lookup/insertion check call.
- On the other hand, in many cases containers are indexed by a well-known key type, and the user is forced
- to write some repetitive code using advanced lookup and insertions. [*Boost.Intrusive]
- associative containers offer an alternative to build a useful map-like lookup interfaces
- without forcing users to define `value_type`s containing `std::pair`-like classes.
- The option is called [classref boost::intrusive::key_of_value].
- If a user specifies that option when defining a `set/multiset` intrusive container, it specifies a function object
- that will tell the container which is the type of the ['key] that `value_type` holds and how to obtain it. This
- function object must be:
- * Lightweight to copy.
- * Default constructible (when the container constructor overload requires it).
- * It shall define:
- * A `type` member that defines the type of the key
- * A member function that returns the key derived a `value_type`, either by value or by const-reference.
- Let's see an example of how a set can be configured as a map indexed by an integer stored in the `value_type`:
-
- [import ../example/doc_map.cpp]
- [doc_map_code]
- [endsect]
- [section:avl_set_multiset Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree]
- Similar to red-black trees, AVL trees are balanced binary trees.
- AVL trees are often compared with red-black trees because they support the same set of operations
- and because both take O(log n) time for basic operations.
- AVL trees are more rigidly balanced than Red-Black trees, leading to slower insertion and
- removal but faster retrieval, so AVL trees perform better
- than red-black trees for lookup-intensive applications.
- [*Boost.Intrusive] offers 3 containers based on avl trees:
- [classref boost::intrusive::avl_set avl_set],
- [classref boost::intrusive::avl_multiset avl_multiset] and
- [classref boost::intrusive::avltree avltree]. The first two are similar to
- [classref boost::intrusive::set set] or
- [classref boost::intrusive::multiset multiset] and the latter is a generalization
- that offers functions both to insert unique and multiple keys.
- The memory overhead of these containers with Boost.Intrusive hooks is usually 3
- pointers and 2 bits (due to alignment, this usually means 3 pointers plus an integer).
- This size can be reduced to 3 pointers if pointers have 4 byte alignment
- (which is usually true in 32 bit systems).
- An empty, non constant-time size [classref boost::intrusive::avl_set avl_set],
- [classref boost::intrusive::avl_multiset avl_multiset] or
- [classref boost::intrusive::avltree avltree]
- also has a size of 3 pointers and an integer (3 pointers when optimized for size).
- [section:avl_set_multiset_hooks avl_set, avl_multiset and avltree hooks]
- [classref boost::intrusive::avl_set avl_set],
- [classref boost::intrusive::avl_multiset avl_multiset] and
- [classref boost::intrusive::avltree avltree]
- share the same hooks.
- [c++]
- template <class ...Options>
- class avl_set_base_hook;
- * [classref boost::intrusive::avl_set_base_hook avl_set_base_hook]:
- the user class derives publicly from this class to make
- it compatible with avl tree based containers.
- [c++]
- template <class ...Options>
- class avl_set_member_hook;
- * [classref boost::intrusive::set_member_hook set_member_hook]:
- the user class contains a public member of this class to make
- it compatible with avl tree based containers.
- [classref boost::intrusive::avl_set_base_hook avl_set_base_hook] and
- [classref boost::intrusive::avl_set_member_hook avl_set_member_hook] receive
- the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive] plus an option to optimize
- the size of the node:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one base hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- * [*`optimize_size<bool Enable>`]: The hook will be optimized for size
- instead of speed. The hook will embed the balance bits of the AVL
- tree node in the parent pointer if pointer alignment is multiple of 4.
- In some platforms, optimizing the size might reduce speed performance a bit
- since masking operations will be needed to access parent pointer and balance factor attributes,
- in other platforms this option improves performance due to improved memory locality.
- Default: `optimize_size<false>`.
- [endsect]
- [section:set_multiset_containers avl_set, avl_multiset and avltree containers]
- [c++]
- template <class T, class ...Options>
- class avl_set;
- template <class T, class ...Options>
- class avl_multiset;
- template <class T, class ...Options>
- class avltree;
- These containers receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive an additional option:
- * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `compare< std::less<key_type> >`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- [endsect]
- [section:avl_set_multiset_example Example]
- Now let's see a small example using both hooks and
- [classref boost::intrusive::avl_set avl_set]/
- [classref boost::intrusive::avl_multiset avl_multiset]
- containers:
- [import ../example/doc_avl_set.cpp]
- [doc_avl_set_code]
- [endsect]
- [endsect]
- [section:splay_set_multiset Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree]
- C++ associative containers are usually based on red-black tree implementations (e.g.: STL,
- Boost.Intrusive associative containers). However, there are other interesting data
- structures that offer some advantages (and also disadvantages).
- Splay trees are self-adjusting binary search trees used typically in caches, memory
- allocators and other applications, because splay trees have a "caching effect": recently
- accessed elements have better access times than elements accessed less frequently.
- For more information on splay trees see [@http://en.wikipedia.org/wiki/Splay_tree the corresponding Wikipedia entry].
- [*Boost.Intrusive] offers 3 containers based on splay trees:
- [classref boost::intrusive::splay_set splay_set],
- [classref boost::intrusive::splay_multiset splay_multiset] and
- [classref boost::intrusive::splaytree splaytree]. The first two are similar to
- [classref boost::intrusive::set set] or
- [classref boost::intrusive::multiset multiset] and the latter is a generalization
- that offers functions both to insert unique and multiple keys.
- The memory overhead of these containers with Boost.Intrusive hooks is usually 3 pointers.
- An empty, non constant-time size splay container has also a size of 3 pointers.
- [section:splay_set_multiset_disadvantages Advantages and disadvantages of splay tree based containers]
- Splay tree based intrusive containers have logarithmic complexity in many
- operations like searches, insertions, erasures, etc., but if some elements are
- more frequently accessed than others, splay trees perform faster searches than equivalent
- balanced binary trees (such as red-black trees).
- The caching effect offered by splay trees comes with a cost: the tree must be
- rebalanced when an element is searched. To maintain const-correctness and thread-safety
- guarantees, this caching effect is not updated when const versions of
- search functions like `find()`, `lower_bound()`, `upper_bound()`, `equal_range()`,
- `count()`... are called. This means that using splay-tree based associative containers as drop-in
- replacements of [classref boost::intrusive::set set]/
- [classref boost::intrusive::multiset multiset], specially for const search functions,
- might not result in desired performance improvements.
- If element searches are randomized, the tree will be continuously srebalanced
- without taking advantage of the cache effect, so splay trees can offer worse
- performance than other balanced trees for several search patterns.
- [*Boost.Intrusive] splay associative containers don't use their own hook types but plain Binary search tree hooks.
- See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
- information about these hooks.
- [endsect]
- [section:set_multiset_containers splay_set, splay_multiset and splaytree containers]
- [c++]
- template <class T, class ...Options>
- class splay_set;
- template <class T, class ...Options>
- class splay_multiset;
- template <class T, class ...Options>
- class splaytree;
- These containers receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive an additional option:
- * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `compare< std::less<key_type> >`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- [endsect]
- [section:splay_set_multiset_example Example]
- Now let's see a small example using
- [classref boost::intrusive::splay_set splay_set]/
- [classref boost::intrusive::splay_multiset splay_multiset]
- containers:
- [import ../example/doc_splay_set.cpp]
- [doc_splay_set_code]
- [endsect]
- [endsect]
- [section:sg_set_multiset Intrusive scapegoat tree based associative containers: sg_set, sg_multiset and sgtree]
- A scapegoat tree is a self-balancing binary search tree, that provides worst-case O(log n)
- lookup time, and O(log n) amortized insertion and deletion time.
- Unlike other self-balancing binary search trees that provide worst case O(log n) lookup
- time, scapegoat trees have no additional per-node overhead compared to a regular binary
- search tree.
- A binary search tree is said to be weight balanced if half the nodes are on the left
- of the root, and half on the right. An a-height-balanced tree is defined with defined
- with the following equation:
- [*['height(tree) <= log1/a(tree.size())]]
- * [*['a == 1]]: A tree forming a linked list is considered balanced.
- * [*['a == 0.5]]: Only a perfectly balanced binary is considered balanced.
- Scapegoat trees are loosely ['a-height-balanced] so:
- [*['height(tree) <= log1/a(tree.size()) + 1]]
- Scapegoat trees support any a between 0.5 and 1. If a is higher, the tree is rebalanced
- less often, obtaining quicker insertions but slower searches. Lower
- a values improve search times. Scapegoat-trees implemented in [*Boost.Intrusive] offer the possibility of
- [*changing a at run-time] taking advantage of the flexibility of scapegoat trees.
- For more information on scapegoat trees see [@http://en.wikipedia.org/wiki/Scapegoat_tree Wikipedia entry].
- Scapegoat trees also have downsides:
- * They need additional storage of data on the
- root (the size of the tree, for example) to achieve logarithmic complexity operations
- so it's not possible to offer `auto_unlink` hooks. The size of an empty scapegoat
- tree is also considerably increased.
- * The operations needed to determine if the tree is unbalanced require floating-point
- operations like ['log1/a]. If the system has no floating point operations (like some
- embedded systems), scapegoat tree operations might become slow.
- [*Boost.Intrusive] offers 3 containers based on scapegoat trees:
- [classref boost::intrusive::sg_set sg_set],
- [classref boost::intrusive::sg_multiset sg_multiset] and
- [classref boost::intrusive::sgtree sgtree]. The first two are similar to
- [classref boost::intrusive::set set] or
- [classref boost::intrusive::multiset multiset] and the latter is a generalization
- that offers functions both to insert unique and multiple keys.
- The memory overhead of these containers with Boost.Intrusive hooks is 3
- pointers.
- An empty, [classref boost::intrusive::sg_set sg_set],
- [classref boost::intrusive::sg_multiset sg_multiset] or
- [classref boost::intrusive::sgtree sgtree]
- has also the size of 3 pointers, two integers and two floating point values
- (equivalent to the size of 7 pointers on most systems).
- [*Boost.Intrusive] scapegoat associative containers don't use their own hook types but plain Binary search tree hooks.
- See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
- information about these hooks.
- [section:sg_set_multiset_containers sg_set, sg_multiset and sgtree containers]
- [c++]
- template <class T, class ...Options>
- class sg_set;
- template <class T, class ...Options>
- class sg_multiset;
- template <class T, class ...Options>
- class sgtree;
- These containers receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive additional options:
- * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `compare< std::less<key_type> >`
- * [*`floating_point<bool Enable>`]:
- When this option is deactivated, the scapegoat tree loses the ability to change
- the balance factor a at run-time, but the size of an empty container is reduced
- and no floating point operations are performed, normally increasing container
- performance. The fixed a factor that is used when this option is activated
- is ['1/sqrt(2) ~ 0,70711]. Default: `floating_point<true>`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- [endsect]
- [section:sg_set_multiset_example Example]
- Now let's see a small example using binary search tree hooks and
- [classref boost::intrusive::sg_set sg_set]/
- [classref boost::intrusive::sg_multiset sg_multiset]
- containers:
- [import ../example/doc_sg_set.cpp]
- [doc_sg_set_code]
- [endsect]
- [endsect]
- [section:treap_set_multiset Intrusive treap based associative containers: treap_set, treap_multiset and treap]
- The name ['treap] is a mixture of ['tree] and ['heap] indicating that Treaps exhibit the properties of both
- binary search trees and heaps. A treap is a binary search tree that orders the nodes
- by a key but also by a priority attribute. The nodes are ordered so that the keys form a binary search tree and
- the priorities obey the max heap order property.
- * If v is a left descendant of u, then key[v] < key[u];
- * If v is a right descendant of u, then key[v] > key[u];
- * If v is a child of u, then priority[v] <= priority[u];
- If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case
- behavior may be outweighed by better expected-case behavior, as the most important items will be near the root.
- This means most important objects will be retrieved faster than less important items and for items keys with equal keys
- most important objects will be found first. These properties are important for some applications.
- The priority comparison will be provided just like the key comparison, via a function object that will be
- stored in the intrusive container. This means that the priority can be stored in the value to be introduced
- in the treap or computed on flight (via hashing or similar).
- [*Boost.Intrusive] offers 3 containers based on treaps:
- [classref boost::intrusive::treap_set treap_set],
- [classref boost::intrusive::treap_multiset treap_multiset] and
- [classref boost::intrusive::treap treap]. The first two are similar to
- [classref boost::intrusive::set set] or
- [classref boost::intrusive::multiset multiset] and the latter is a generalization
- that offers functions both to insert unique and multiple keys.
- The memory overhead of these containers with Boost.Intrusive hooks is 3
- pointers.
- An empty, [classref boost::intrusive::treap_set treap_set],
- [classref boost::intrusive::treap_multiset treap_multiset] or
- [classref boost::intrusive::treap treap]
- has also the size of 3 pointers and an integer (supposing empty function objects for key and priority
- comparison and constant-time size).
- [*Boost.Intrusive] treap associative containers don't use their own hook types but plain Binary search tree hooks.
- See [link intrusive.bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook] section for more
- information about these hooks.
- [section:treap_set_multiset_containers treap_set, treap_multiset and treap containers]
- [c++]
- template <class T, class ...Options>
- class treap_set;
- template <class T, class ...Options>
- class treap_multiset;
- template <class T, class ...Options>
- class treap;
- These containers receive the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
- [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
- to configure the container. (To learn about value traits go to the section
- [link intrusive.value_traits Containers with custom ValueTraits].)
- * [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
- Default: `constant_time_size<true>`
- * [*`size_type<typename SizeType>`]: To specify the type that will be used to store the size
- of the container. Default: `size_type<std::size_t>`
- And they also can receive additional options:
- * [*`compare<class Compare>`]: Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `compare< std::less<key_type> >`
- * [*`priority_of_value<class PriorityOfValue>`]: A function object
- that specifies the type of the priority (`priority_type`) of a treap
- container and an operator to obtain it from a value type.
- Default: `priority_type` is equal to `value_type` (set-like interface).
- * [*`priority<class PriorityCompare>`]: Priority Comparison function for the objects to be inserted
- in containers. The comparison functor must induce a strict weak ordering.
- Default: `priority< priority_compare<priority_type> >`
- * [*`key_of_value<class KeyOfValueFunctionObject>`]: A function object that will
- define the `key_type` of the value type to be stored. This type will allow a map-like interface. See
- [link intrusive.map_multimap Map and multimap-like interface with set and multiset]
- for details. Default: `key_type` is equal to `value_type` (set-like interface).
- The default `priority_compare<T>` object function will call an unqualified function `priority_order`
- passing two constant `T` references as arguments and should return true if the first argument has
- higher priority (it will be searched faster), inducing strict weak ordering.
- The function will be found using ADL lookup so that
- the user just needs to define a `priority_order` function in the same namespace as the class:
- [c++]
- struct MyType
- {
- friend bool priority_order(const MyType &a, const MyType &b)
- {...}
- };
- or
- namespace mytype {
- struct MyType{ ... };
- bool priority_order(const MyType &a, const MyType &b)
- {...}
- } //namespace mytype {
- [endsect]
- [section:treap_set_exceptions Exception safety of treap-based intrusive containers]
- In general, intrusive containers offer strong safety guarantees, but treap containers must deal
- with two possibly throwing functors (one for value ordering, another for priority ordering).
- Moreover, treap erasure operations require rotations based on the priority order function and
- this issue degrades usual `erase(const_iterator)` no-throw guarantee. However, intrusive offers
- the strongest possible behaviour in these situations. In summary:
- * If the priority order functor does not throw, treap-based containers, offer exactly the same
- guarantees as other tree-based containers.
- * If the priority order functor throws, treap-based containers offer strong guarantee.
- [endsect]
- [section:treap_set_multiset_example Example]
- Now let's see a small example using binary search tree hooks and
- [classref boost::intrusive::treap_set treap_set]/
- [classref boost::intrusive::treap_multiset treap_multiset]
- containers:
- [import ../example/doc_treap_set.cpp]
- [doc_treap_set_code]
- [endsect]
- [endsect]
- [section:bst_hooks Binary search tree hooks: bs_set_base_hook and bs_set_member_hook]
- Binary search tree hooks can be used with several tree-like containers that don't
- need any additional metadata for rebalancing operations. This has many advantages
- since binary search tree hooks can also be used to insert values in
- plain binary search tree, splay tree, scapegoat tree, and treap containers.
- [c++]
- template <class ...Options>
- class bs_set_base_hook;
- * [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]:
- the user class derives publicly from this class to make
- it compatible with the mentioned tree based containers.
- [c++]
- template <class ...Options>
- class bs_set_member_hook;
- * [classref boost::intrusive::bs_set_member_hook bs_set_member_hook]:
- the user class contains a public member of this class to make
- it compatible with the mentioned tree based containers.
- [classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
- [classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
- the same options explained in the section
- [link intrusive.usage How to use Boost.Intrusive]:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one base hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- [endsect]
- [section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
- [section:advanced_lookups Advanced lookups]
- [*Boost.Intrusive] associative containers offer an interface similar to STL associative
- containers. However, STL's ordered and unordered simple associative containers
- (`std::set`, `std::multiset`, `std::unordered_set` and `std::unordered_multiset`)
- have some inefficiencies caused by the interface in several search, insertion or erasure functions
- (`equal_range`, `lower_bound`, `upper_bound`, `find`, `insert`, `erase`...): the user can only operate
- with `value_type` objects or (starting from C++11),
- [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3657.htm heterogeneous comparison lookups]
- which are not flexible enough as `key_compare` shall support the comparison between the provided
- key and `value_type`, which precludes the use of user-defined comparison objects that can partition the
- search in a compatible but advanced way.
- To solve these problems, [*Boost.Intrusive] containers offers functions where a key type different
- from `key_type` and a comparison object are provided by the user. This applies to:
- * equal_range
- * lower_bound
- * upper_bound
- * count
- * find
- * erase
- Requirements for such functions are:
- * For unordered container the provided comparison and hashing
- function with the given key shall induce the same hash and equivalence as `key_compare` and `hasher`.
- * For ordered associative containers, lookup and erasure functions, the container to be searched shall
- be partitioned in regards to the supplied comparison object and key.
- For more details, see [*Requires] clauses of such functions in the reference.
- [section:advanced_lookups_example Example]
- Imagine that the object to be searched is quite expensive to construct (called `Expensive` in the example):
- [import ../example/doc_assoc_optimized_code.cpp]
- [doc_assoc_optimized_code_normal_find]
- If "key" c-string is quite long
- `Expensive` has to construct a `std::string` using heap memory. Like
- `Expensive`, many times the only member taking part in ordering issues is just
- a small part of the class. E.g.: with `Expensive`, only the internal
- `std::string` is needed to compare the object.
- In both containers, if we call `get_from_set/get_from_unordered_set` in a loop, we might get a performance penalty,
- because we are forced to create a whole `Expensive` object to be able to find an
- equivalent one.
- Sometimes the problem is not only performance-related, as
- we [*might not have enough information to construct the object] but we might
- [*have enough information to find the object]. In this case, a name is enough
- to search `Expensive` objects in the container but constructing an `Expensive`
- object might require more information that the searcher might not have.
- To solve this, we can use the functions that take any type comparable with the value and a
- the 'compatible' comparison object (and hash, when the associative container is unordered)
- Let's see optimized search function:
- [doc_assoc_optimized_code_optimized_find]
- [endsect]
- [endsect]
- [section:advanced_insertions Advanced insertions]
- A similar issue happens with insertions in simple ordered and unordered associative
- containers with unique keys (`std::set` and `std::unordered_set`). In these containers,
- if a value is already present, the value to be inserted is discarded. With expensive
- values, if the value is already present, we can suffer efficiency problems.
- [classref boost::intrusive::set set] and [classref boost::intrusive::unordered_set unordered_set]-like
- containers have insertion functions (`insert_check`, `insert_unique_check`,...) to check efficiently, without
- constructing the value, if a value is present or not and if it's not present, a
- function to insert it immediately (`insert_commit`) without any further lookup. Requirements for functions
- that check the existence of such value are:
- * For unordered container the provided comparison and hashing
- function with the given key shall induce the same hash and equivalence as `key_compare` and `hasher`.
- * For ordered associative containers, the provided comparison function with the given key, shall induce the same
- strict weak order as `key_compare`.
- To sum up, `insert_check` is similar to a normal `insert` but:
- * `insert_check` can be used with arbitrary keys
- * if the insertion is possible (there is no equivalent value) `insert_check` collects all the needed information
- in an `insert_commit_data` structure, so that `insert_commit`:
- * [*does not execute] further comparisons
- * can be executed with [*constant-time complexity]
- * has [*no-throw guarantee].
- These functions must be used with care,
- no other insertion or erasure must be executed between an `insert_check` and an `insert_commit`
- pair. Otherwise, the behaviour is undefined.
- See [classref boost::intrusive::set set]
- and [classref boost::intrusive::unordered_set unordered_set]-like containers' reference
- for more information about `insert_check` and `insert_commit`.
- With multiple ordered and unordered associative containers
- ([classref boost::intrusive::multiset multiset] and
- [classref boost::intrusive::unordered_multiset unordered_multiset]) there is
- no need for these advanced insertion functions, since insertions are always successful.
- [section:advanced_insertions_example Example]
- For example, using the same `Expensive` class,
- this function can be inefficient:
- [doc_assoc_optimized_code_normal_insert]
- If the object is already present, we are constructing an `Expensive` that
- will be discarded, and this is a waste of resources. Instead of that, let's use
- `insert_check` and `insert_commit` functions:
- [doc_assoc_optimized_code_optimized_insert]
- [endsect]
- [endsect]
- [section:positional_insertions Positional insertions]
- Some ordered associative containers offer low-level functions to bypass ordering
- checks and insert nodes directly in desired tree positions. These functions are
- provided for performance reasons when values to be inserted in the container are
- known to fulfill order (sets and multisets) and uniqueness (sets) invariants. A
- typical usage of these functions is when intrusive associative containers are used
- to build non-intrusive containers and the programmer wants to speed up assignments
- from other associative containers: if the ordering and uniqueness properties are the same,
- there is no need to waste time checking the position of each source value, because values
- are already ordered: back insertions will be much more efficient.
- [*Note:] These functions [*don't check preconditions] so they must used with care. They
- are low-level operations that [*will break container invariants if
- ordering and uniqueness preconditions are not assured by the caller.]
- Let's see an example:
- [import ../example/doc_positional_insertion.cpp]
- [doc_positional_insertion]
- [endsect]
- For more information about advanced lookup and insertion functions see
- associative containers' documentation (e.g.
- [classref boost::intrusive::set set],
- [classref boost::intrusive::multiset multiset],
- [classref boost::intrusive::unordered_set unordered_set] and
- [classref boost::intrusive::unordered_multiset unordered_multiset] references).
- [endsect]
- [section:erasing_and_disposing Erasing and disposing values from Boost.Intrusive containers]
- One of the most tedious tasks when using intrusive containers is the management of the erased elements.
- When using STL containers, the container itself unlinks and destroys the contained elements, but with
- intrusive containers, the user must explicitly destroy the object after erasing an element from the container.
- This makes STL-like functions erasing multiple objects unhelpful: the user can't destroy every erased element.
- For example, let's take the function `remove_if` from [classref boost::intrusive::list list]:
- [c++]
- template<class Pred>
- void remove_if(Pred pred);
- How can the user destroy the elements (say, using `operator delete`) that will be erased according
- to the predicate? [*Boost.Intrusive] containers offer additional functions that take a function
- object that will be called after the element has been erased from the container. For example,
- [classref boost::intrusive::list list] offers:
- [c++]
- template<class Pred, class Disposer>
- void remove_and_dispose_if(Pred pred, Disposer disposer)
- With this function the user can efficiently remove and destroy elements if the disposer
- function destroys an object: `remove_and_dispose_if`
- will call the "disposer" function object for every removed element. [classref boost::intrusive::list list] offers
- more functions taking a disposer function object as argument, like `erase_and_dispose`, `clear_and_dispose`,
- `remove_and_dispose`, etc.
- Note that the disposing function does not need to just destroy the object. It can
- implement any other operation like inserting the remove object in another container.
- Let's see a small example:
- [import ../example/doc_erasing_and_disposing.cpp]
- [doc_erasing_and_disposing]
- All [*Boost.Intrusive] containers offer these "erase + dispose" additional members for all functions
- that erase an element from the container.
- [endsect]
- [section:clone_from Cloning Boost.Intrusive containers]
- As previously mentioned, [*Boost.Intrusive] containers are [*non-copyable and non-assignable], because
- intrusive containers don't allocate memory at all. To implement a copy-constructor or assignment operator,
- the user must clone one by one all the elements of the container and insert them in another intrusive container.
- However, cloning by hand is usually more inefficient than a member cloning function and a specialized cloning
- function can offer more guarantees than the manual cloning (better exception safety guarantees, for example).
- To ease the implementation of copy constructors and assignment operators of classes containing [*Boost.Intrusive]
- containers, all [*Boost.Intrusive] containers offer a special cloning function called `clone_from`.
- Apart from the container to be cloned, `clone_from` takes two function objects as arguments. For example, consider the
- `clone_from` member function of [classref boost::intrusive::list list]:
- [c++]
- template <class Cloner, class Disposer>
- void clone_from(const list &src, Cloner cloner, Disposer disposer);
- This function will make `*this` a clone of `src`. Let's explain the arguments:
- * The first parameter is the list to be cloned.
- * The second parameter is a function object that will clone `value_type` objects and
- return a pointer to the clone. It must implement the following function:
- `pointer operator()(const value_type &)`.
- * The second parameter is a function object that will dispose `value_type` objects. It's used first
- to empty the container before cloning and to dispose the elements if an exception is thrown.
- The cloning function works as follows:
- * First it clears and disposes all the elements from *this using the disposer function object.
- * After that it starts cloning all the elements of the source container using the cloner function object.
- * If any operation in the cloning function (for example, the cloner function object) throws,
- all the constructed elements are disposed using the disposer function object.
- Here is an example of `clone_from`:
- [import ../example/doc_clone_from.cpp]
- [doc_clone_from]
- [endsect]
- [section:function_hooks Using function hooks]
- A programmer might find that base or member hooks are not flexible enough in some situations.
- In some applications it would be optimal to put a hook deep inside a member of a class or just outside the class.
- [*Boost.Intrusive] has an easy option to allow such cases: [classref boost::intrusive::function_hook function_hook].
- This option is similar to [classref boost::intrusive::member_hook member_hook] or
- [classref boost::intrusive::base_hook base_hook], but the programmer can specify a function
- object that tells the container how to obtain a hook from a value and vice versa.
- The programmer just needs to define the following function object:
- [c++]
- //This functor converts between value_type and a hook_type
- struct Functor
- {
- //Required types
- typedef /*impl-defined*/ hook_type;
- typedef /*impl-defined*/ hook_ptr;
- typedef /*impl-defined*/ const_hook_ptr;
- typedef /*impl-defined*/ value_type;
- typedef /*impl-defined*/ pointer;
- typedef /*impl-defined*/ const_pointer;
- //Required static functions
- static hook_ptr to_hook_ptr (value_type &value);
- static const_hook_ptr to_hook_ptr(const value_type &value);
- static pointer to_value_ptr(hook_ptr n);
- static const_pointer to_value_ptr(const_hook_ptr n);
- };
- Converting from values to hooks is generally easy, since most hooks are
- in practice members or base classes of class data members. The inverse operation
- is a bit more complicated, but [*Boost.Intrusive] offers a bit of help with the function
- [funcref boost::intrusive::get_parent_from_member get_parent_from_member],
- which allows easy conversions from the address of a data member to the address of
- the parent holding that member. Let's see a little example of
- [classref boost::intrusive::function_hook function_hook]:
- [import ../example/doc_function_hooks.cpp]
- [doc_function_hooks]
- [endsect]
- [section:recursive Recursive Boost.Intrusive containers]
- [*Boost.Intrusive] containers can be used to define recursive structures very easily,
- allowing complex data structures with very low overhead. Let's see an example:
- [import ../example/doc_recursive.cpp]
- [doc_recursive]
- Recursive data structures using [*Boost.Intrusive] containers must avoid using hook deduction to avoid early type
- instantiation:
- [c++]
- //This leads to compilation error (Recursive is instantiated by
- //'list' to deduce hook properties (pointer type, tag, safe-mode...)
- class Recursive
- { //...
- list< Recursive > l;
- //...
- };
- //Ok, programmer must specify the hook type to avoid early Recursive instantiation
- class Recursive
- { //...
- list< Recursive, base_hook<BaseHook> > l;
- //...
- };
- Member hooks are not suitable for recursive structures:
- [c++]
- class Recursive
- {
- private:
- Recursive(const Recursive&);
- Recursive & operator=(const Recursive&);
- public:
- list_member_hook<> memhook;
- list< Recursive, member_hook<Recursive, list_member_hook<>, &Recursive::memhook> > children;
- };
- Specifying `&Recursive::memhook` (that is, the offset between memhook and Recursive) provokes an early
- instantiation of `Recursive`. To define recursive structures using member hooks, a programmer should use
- [classref ::boost::interprocess::function_hook function_hook]:
- [import ../example/doc_recursive_member.cpp]
- [doc_recursive_member]
- [endsect]
- [section:using_smart_pointers Using smart pointers with Boost.Intrusive containers]
- [*Boost.Intrusive] hooks can be configured to use other pointers than raw pointers.
- When a [*Boost.Intrusive] hook is configured with a smart pointer as an argument,
- this pointer configuration is passed to the containers. For example, if the following
- hook is configured with a smart pointer (for example, an offset pointer from
- [*Boost.Interprocess]):
- [import ../example/doc_offset_ptr.cpp]
- [doc_offset_ptr_0]
- Any intrusive list constructed using this hook will be ready for shared memory,
- because the intrusive list will also use offset pointers internally. For example,
- we can create an intrusive list in shared memory combining [*Boost.Interprocess]
- and [*Boost.Intrusive]:
- [doc_offset_ptr_1]
- [section:smart_pointers_requirements Requirements for smart pointers compatible with Boost.Intrusive]
- Not every smart pointer is compatible with [*Boost.Intrusive]:
- * It must be compatible with C++11 [@http://en.cppreference.com/w/cpp/memory/pointer_traits `std::pointer_traits`]
- requirements. [*Boost.Intrusive] uses its own [classref boost::intrusive::pointer_traits pointer_traits]
- class to implement those features in both C++11 and C++03 compilers.
- * It must have the same ownership semantics as a raw pointer. This means that
- resource management smart pointers (like `boost::shared_ptr`) can't be used.
- The conversion from the smart pointer to a raw pointer will be implemented as a recursive call to
- `operator->()` until the function returns a raw pointer.
- [endsect]
- [endsect]
- [section:obtaining_iterators_from_values Obtaining iterators from values]
- [*Boost.Intrusive] offers another useful feature that's not present in STL
- containers: it's possible to obtain an iterator to a value from the value itself.
- This feature is implemented in [*Boost.Intrusive] containers by a
- function called `iterator_to`:
- [c++]
- iterator iterator_to(reference value);
- const_iterator iterator_to(const_reference value);
- For [*Boost.Intrusive] containers that have local iterators, like unordered
- associative containers, we can also obtain local iterators:
- [c++]
- local_iterator local_iterator_to(reference value);
- const_local_iterator local_iterator_to(const_reference value) const;
- For most [*Boost.Intrusive] containers
- ([classref boost::intrusive::list list],
- [classref boost::intrusive::slist slist],
- [classref boost::intrusive::set set],
- [classref boost::intrusive::multiset multiset]) we have an alternative
- static `s_iterator_to` function.
- For unordered associative containers
- ([classref boost::intrusive::unordered_set unordered_set],
- [classref boost::intrusive::multiset multiset]),
- `iterator_to` has no static alternative function.
- On the other hand, `local_iterator_to` functions
- have their `s_local_iterator_to` static alternatives.
- Alternative static functions are available under certain circumstances
- explained in the [link intrusive.value_traits.stateful_value_traits Stateful value traits] section;
- if the programmer uses hooks provided by [*Boost.Intrusive], those functions
- will be available.
- Let's see a small function that shows the use of `iterator_to` and
- `local_iterator_to`:
- [import ../example/doc_iterator_from_value.cpp]
- [doc_iterator_from_value]
- [endsect]
- [section:any_hooks Any Hooks: A single hook for any Intrusive container]
- Sometimes, a class programmer wants to place a class in several intrusive
- containers but no at the same time. In this case, the programmer might
- decide to insert two hooks in the same class.
- [c++]
- class MyClass
- : public list_base_hook<>, public slist_base_hook<> //...
- {};
- However, there is a more size-efficient alternative in [*Boost.Intrusive]: "any" hooks
- ([classref boost::intrusive::any_base_hook any_base_hook] and
- [classref boost::intrusive::any_member_hook any_member_hook]).
- These hooks can be used to store a type in several containers
- offered by [*Boost.Intrusive] minimizing the size of the class.
- These hooks support these options:
- * [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
- so you can derive from more than one slist hook.
- Default: `tag<default_tag>`.
- * [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
- `link_mode<auto_unlink>` is [*not] supported and `link_mode<safe_mode>`
- might offer weaker error detection in any hooks than in other hooks.
- Default: `link_mode<safe_link>`.
- * [*`void_pointer<class VoidPointer>`]: The pointer type to be used
- internally in the hook and propagated to the container.
- Default: `void_pointer<void*>`.
- `auto_unlink` can't be supported because the hook does not know in which type of
- container might be currently inserted. Additionally, these hooks don't support `unlink()` and
- `swap_nodes()` operations for the same reason.
- Here is an example that creates a class with two any hooks, and uses one to insert the
- class in a [classref slist] and the other one in a [classref list].
- [import ../example/doc_any_hook.cpp]
- [doc_any_hook]
- [endsect]
- [section:concepts Concepts explained]
- This section will expand the explanation of previously presented basic concepts
- before explaining the customization options of [*Boost.Intrusive].
- * [*Node Algorithms]: A set of static functions that implement basic operations
- on a group of nodes: initialize a node, link a node to a group of nodes,
- unlink a node from another group of nodes, etc. For example, a circular
- singly linked list is a group of nodes, where each node has a pointer to the
- next node. [*Node Algorithms] just require a [*NodeTraits]
- template parameter and they can work with any [*NodeTraits] class that fulfills
- the needed interface. As an example, here is a class that implements operations
- to manage a group of nodes forming a circular singly linked list:
- [c++]
- template<class NodeTraits>
- struct my_slist_algorithms
- {
- typedef typename NodeTraits::node_ptr node_ptr;
- typedef typename NodeTraits::const_node_ptr const_node_ptr;
- //Get the previous node of "this_node"
- static node_ptr get_prev_node(node_ptr this_node)
- {
- node_ptr p = this_node;
- while (this_node != NodeTraits::get_next(p))
- p = NodeTraits::get_next(p);
- return p;
- }
- // number of elements in the group of nodes containing "this_node"
- static std::size_t count(const_node_ptr this_node)
- {
- std::size_t result = 0;
- const_node_ptr p = this_node;
- do{
- p = NodeTraits::get_next(p);
- ++result;
- } while (p != this_node);
- return result;
- }
- // More operations
- // ...
- };
- * [*Node Traits]: A class that encapsulates the basic information and
- operations on a node within a group of nodes:
- the type of the node, a function to obtain the pointer to the next node, etc.
- [*Node Traits] specify the configuration information [*Node Algorithms]
- need. Each type of [*Node Algorithm] expects an interface that compatible
- [*Node Traits] classes must implement.
- As an example, this is the definition of a [*Node Traits] class that
- is compatible with the previously presented `my_slist_algorithms`:
- [c++]
- struct my_slist_node_traits
- {
- //The type of the node
- struct node
- {
- node *next_;
- };
- typedef node * node_ptr;
- typedef const node * const_node_ptr;
- //A function to obtain a pointer to the next node
- static node_ptr get_next(const_node_ptr n)
- { return n->next_; }
- //A function to set the pointer to the next node
- static void set_next(node_ptr n, node_ptr next)
- { n->next_ = next; }
- };
- * [*Hook]: A class that the user must add as a base class or as a member to his own
- class to make that class insertable in an intrusive container. Usually the hook
- contains a node object that will be used to form the group of nodes:
- For example, the following class is a [*Hook] that the user can add as a base class,
- to make the user class compatible with a singly linked list container:
- [c++]
- class my_slist_base_hook
- //This hook contains a node, that will be used
- //to link the user object in the group of nodes
- : private my_slist_node_traits::node
- {
- typedef my_slist_node_traits::node_ptr node_ptr;
- typedef my_slist_node_traits::const_node_ptr const_node_ptr;
- //Converts the generic node to the hook
- static my_slist_base_hook *to_hook_ptr(node_ptr p)
- { return static_cast<my_slist_base_hook*>(p); }
- //Returns the generic node stored by this hook
- node_ptr to_node_ptr()
- { return static_cast<node *const>(this); }
- // More operations
- // ...
- };
- //To make MyClass compatible with an intrusive singly linked list
- //derive our class from the hook.
- class MyClass
- : public my_slist_base_hook
- {
- void set(int value);
- int get() const;
- private:
- int value_;
- };
- * [*Intrusive Container]: A container that offers a STL-like interface to store
- user objects. An intrusive container can be templatized to store different
- value types that use different hooks. An intrusive container is also more elaborate
- than a group of nodes: it can store the number of elements to achieve constant-time
- size information, it can offer debugging facilities, etc.
- For example, an [classref boost::intrusive::slist slist] container
- (intrusive singly linked list) should
- be able to hold `MyClass` objects that might have decided to store the hook
- as a base class or as a member. Internally, the container will use [*Node Algorithms]
- to implement its operations, and an intrusive container is configured using
- a template parameter called [*ValueTraits]. [*ValueTraits] will contain
- the information to convert user classes in nodes compatible with [*Node Algorithms].
- For example, this a possible [classref boost::intrusive::slist slist] implementation:
- [c++]
- template<class ValueTraits, ...>
- class slist
- {
- public:
- typedef typename ValueTraits::value_type value_type;
- //More typedefs and functions
- // ...
- //Insert the value as the first element of the list
- void push_front (reference value)
- {
- node_ptr to_insert(ValueTraits::to_node_ptr(value));
- circular_list_algorithms::link_after(to_insert, get_root_node());
- }
- // More operations
- // ...
- };
- * [*Semi-Intrusive Container]: A semi-intrusive container is similar to an
- intrusive container, but apart from the values to be inserted in the container,
- it needs additional memory (for example, auxiliary arrays or indexes).
- * [*Value Traits]: As we can see, to make our classes intrusive-friendly we add
- a simple hook as a member or base class. The hook contains a generic node
- that will be inserted in a group of nodes. [*Node Algorithms] just work
- with nodes and don't know anything about user classes. On the other
- hand, an intrusive container needs to know how to obtain a node from a user class,
- and also the inverse operation.
- So we can define [*ValueTraits] as the glue between user classes and nodes
- required by [*Node Algorithms].
- Let's see a possible implementation of a value traits class that glues MyClass
- and the node stored in the hook:
- [c++]
- struct my_slist_derivation_value_traits
- {
- public:
- typedef slist_node_traits node_traits;
- typedef MyClass value_type;
- typedef node_traits::node_ptr node_ptr;
- typedef value_type* pointer;
- //...
- //Converts user's value to a generic node
- static node_ptr to_node_ptr(reference value)
- { return static_cast<slist_base_hook &>(value).to_node_ptr(); }
- //Converts a generic node into user's value
- static value_type *to_value_ptr(node_traits::node *n)
- { static_cast<value_type*>(slist_base_hook::to_hook_ptr(n)); }
- // More operations
- // ...
- };
- [endsect]
- [section:node_algorithms Node algorithms with custom NodeTraits]
- As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
- containers are implemented using node algorithms that work on generic nodes.
- Sometimes, the use of intrusive containers is expensive for some environments
- and the programmer might want to avoid all the template instantiations
- related to [*Boost.Intrusive] containers. However, the user can still benefit
- from [*Boost.Intrusive] using the node algorithms, because some of those algorithms,
- like red-black tree algorithms, are not trivial to write.
- All node algorithm classes are
- templatized by a `NodeTraits` class. This class encapsulates the needed internal
- type declarations and operations to make a node compatible with node algorithms.
- Each type of node algorithms has its own requirements:
- [section:circular_slist_algorithms Intrusive singly linked list algorithms]
- These algorithms are static
- members of the [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms] class:
- [c++]
- template<class NodeTraits>
- struct circular_slist_algorithms;
- An empty list is formed by a node whose pointer to the next node points
- to itself. [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular list
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- [*Static functions]:
- * `static node_ptr get_next(const_node_ptr n);`:
- Returns a pointer to the next node stored in "n".
- * `static void set_next(node_ptr n, node_ptr next);`:
- Sets the pointer to the next node stored in "n" to "next".
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_slist_algorithms.cpp]
- [doc_slist_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms reference].
- [endsect]
- [section:circular_list_algorithms Intrusive doubly linked list algorithms]
- These algorithms are static
- members of the [classref boost::intrusive::circular_list_algorithms circular_list_algorithms] class:
- [c++]
- template<class NodeTraits>
- struct circular_list_algorithms;
- An empty list is formed by a node whose pointer to the next node points
- to itself. [classref boost::intrusive::circular_list_algorithms circular_list_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular list
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- [*Static functions]:
- * `static node_ptr get_next(const_node_ptr n);`:
- Returns a pointer to the next node stored in "n".
- * `static void set_next(node_ptr n, node_ptr next);`:
- Sets the pointer to the next node stored in "n" to "next".
- * `static node_ptr get_previous(const_node_ptr n);`:
- Returns a pointer to the previous node stored in "n".
- * `static void set_previous(node_ptr n, node_ptr prev);`:
- Sets the pointer to the previous node stored in "n" to "prev".
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_list_algorithms.cpp]
- [doc_list_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::circular_list_algorithms circular_list_algorithms reference].
- [endsect]
- [section:rbtree_algorithms Intrusive red-black tree algorithms]
- These algorithms are static
- members of the [classref boost::intrusive::rbtree_algorithms rbtree_algorithms] class:
- [c++]
- template<class NodeTraits>
- struct rbtree_algorithms;
- An empty tree is formed by a node whose pointer to the parent node is null,
- the left and right node pointers point to itself, and whose color is red.
- [classref boost::intrusive::rbtree_algorithms rbtree_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular rbtree
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- * `color`: The type that can store the color of a node
- [*Static functions]:
- * `static node_ptr get_parent(const_node_ptr n);`:
- Returns a pointer to the parent node stored in "n".
- * `static void set_parent(node_ptr n, node_ptr p);`:
- Sets the pointer to the parent node stored in "n" to "p".
- * `static node_ptr get_left(const_node_ptr n);`:
- Returns a pointer to the left node stored in "n".
- * `static void set_left(node_ptr n, node_ptr l);`:
- Sets the pointer to the left node stored in "n" to "l".
- * `static node_ptr get_right(const_node_ptr n);`:
- Returns a pointer to the right node stored in "n".
- * `static void set_right(node_ptr n, node_ptr r);`:
- Sets the pointer to the right node stored in "n" to "r".
- * `static color get_color(const_node_ptr n);`:
- Returns the color stored in "n".
- * `static void set_color(node_ptr n, color c);`:
- Sets the color stored in "n" to "c".
- * `static color black();`:
- Returns a value representing the black color.
- * `static color red();`:
- Returns a value representing the red color.
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_rbtree_algorithms.cpp]
- [doc_rbtree_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::rbtree_algorithms rbtree_algorithms reference].
- [endsect]
- [section:splaytree_algorithms Intrusive splay tree algorithms]
- These algorithms are static
- members of the [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] class:
- [c++]
- template<class NodeTraits>
- struct splaytree_algorithms;
- An empty tree is formed by a node whose pointer to the parent node is null,
- and whose left and right nodes pointers point to itself.
- [classref boost::intrusive::splaytree_algorithms splaytree_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular splaytree
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- [*Static functions]:
- * `static node_ptr get_parent(const_node_ptr n);`:
- Returns a pointer to the parent node stored in "n".
- * `static void set_parent(node_ptr n, node_ptr p);`:
- Sets the pointer to the parent node stored in "n" to "p".
- * `static node_ptr get_left(const_node_ptr n);`:
- Returns a pointer to the left node stored in "n".
- * `static void set_left(node_ptr n, node_ptr l);`:
- Sets the pointer to the left node stored in "n" to "l".
- * `static node_ptr get_right(const_node_ptr n);`:
- Returns a pointer to the right node stored in "n".
- * `static void set_right(node_ptr n, node_ptr r);`:
- Sets the pointer to the right node stored in "n" to "r".
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_splaytree_algorithms.cpp]
- [doc_splaytree_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference].
- [endsect]
- [section:avltree_algorithms Intrusive avl tree algorithms]
- [classref boost::intrusive::avltree_algorithms avltree_algorithms] have the same
- interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
- [c++]
- template<class NodeTraits>
- struct avltree_algorithms;
- [classref boost::intrusive::avltree_algorithms avltree_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular avltree
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- * `balance`: A type that can represent 3 balance types (usually an integer)
- [*Static functions]:
- * `static node_ptr get_parent(const_node_ptr n);`:
- Returns a pointer to the parent node stored in "n".
- * `static void set_parent(node_ptr n, node_ptr p);`:
- Sets the pointer to the parent node stored in "n" to "p".
- * `static node_ptr get_left(const_node_ptr n);`:
- Returns a pointer to the left node stored in "n".
- * `static void set_left(node_ptr n, node_ptr l);`:
- Sets the pointer to the left node stored in "n" to "l".
- * `static node_ptr get_right(const_node_ptr n);`:
- Returns a pointer to the right node stored in "n".
- * `static void set_right(node_ptr n, node_ptr r);`:
- Sets the pointer to the right node stored in "n" to "r".
- * `static balance get_balance(const_node_ptr n);`:
- Returns the balance factor stored in "n".
- * `static void set_balance(node_ptr n, balance b);`:
- Sets the balance factor stored in "n" to "b".
- * `static balance negative();`:
- Returns a value representing a negative balance factor.
- * `static balance zero();`:
- Returns a value representing a zero balance factor.
- * `static balance positive();`:
- Returns a value representing a positive balance factor.
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_avltree_algorithms.cpp]
- [doc_avltree_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::avltree_algorithms avltree_algorithms reference].
- [endsect]
- [section:treap_algorithms Intrusive treap algorithms]
- [classref boost::intrusive::treap_algorithms treap_algorithms] have the same
- interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
- [c++]
- template<class NodeTraits>
- struct treap_algorithms;
- [classref boost::intrusive::treap_algorithms treap_algorithms]
- is configured with a NodeTraits class, which encapsulates
- the information about the node to be manipulated. NodeTraits must support the
- following interface:
- [*Typedefs]:
- * `node`: The type of the node that forms the circular treap
- * `node_ptr`: The type of a pointer to a node (usually node*)
- * `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- [*Static functions]:
- * `static node_ptr get_parent(const_node_ptr n);`:
- Returns a pointer to the parent node stored in "n".
- * `static void set_parent(node_ptr n, node_ptr p);`:
- Sets the pointer to the parent node stored in "n" to "p".
- * `static node_ptr get_left(const_node_ptr n);`:
- Returns a pointer to the left node stored in "n".
- * `static void set_left(node_ptr n, node_ptr l);`:
- Sets the pointer to the left node stored in "n" to "l".
- * `static node_ptr get_right(const_node_ptr n);`:
- Returns a pointer to the right node stored in "n".
- * `static void set_right(node_ptr n, node_ptr r);`:
- Sets the pointer to the right node stored in "n" to "r".
- Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- with our nodes:
- [import ../example/doc_treap_algorithms.cpp]
- [doc_treap_algorithms_code]
- For a complete list of functions see
- [classref boost::intrusive::treap_algorithms treap_algorithms reference].
- [endsect]
- [/
- /
- /[section:sgtree_algorithms Intrusive sg tree algorithms]
- /
- /
- /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms] have the same
- /interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
- /
- /[c++]
- /
- / template<class NodeTraits>
- / struct sgtree_algorithms;
- /
- /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms]
- /is configured with a NodeTraits class, which encapsulates
- /the information about the node to be manipulated. NodeTraits must support the
- /following interface:
- /
- /[*Typedefs]:
- /
- /* `node`: The type of the node that forms the circular sgtree
- /
- /* `node_ptr`: The type of a pointer to a node (usually node*)
- /
- /* `const_node_ptr`: The type of a pointer to a const node (usually const node*)
- /
- /[*Static functions]:
- /
- /* `static node_ptr get_parent(const_node_ptr n);`:
- / Returns a pointer to the parent node stored in "n".
- /
- /* `static void set_parent(node_ptr n, node_ptr p);`:
- / Sets the pointer to the parent node stored in "n" to "p".
- /
- /* `static node_ptr get_left(const_node_ptr n);`:
- / Returns a pointer to the left node stored in "n".
- /
- /* `static void set_left(node_ptr n, node_ptr l);`:
- / Sets the pointer to the left node stored in "n" to "l".
- /
- /* `static node_ptr get_right(const_node_ptr n);`:
- / Returns a pointer to the right node stored in "n".
- /
- /* `static void set_right(node_ptr n, node_ptr r);`:
- / Sets the pointer to the right node stored in "n" to "r".
- /
- /Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
- /with our nodes:
- /
- /[import ../example/doc_sgtree_algorithms.cpp]
- /[doc_sgtree_algorithms_code]
- /
- /For a complete list of functions see
- /[classref boost::intrusive::sgtree_algorithms sgtree_algorithms reference].
- /
- /[endsect]
- /]
- [endsect]
- [section:value_traits Containers with custom ValueTraits]
- As explained in the [link intrusive.concepts Concepts] section, [*Boost.Intrusive]
- containers need a `ValueTraits` class to perform transformations between nodes and
- user values. `ValueTraits` can be explicitly configured (using the `value_traits<>` option)
- or implicitly configured (using hooks and their `base_hook<>`/`member_hook<>` options).
- `ValueTraits` contains
- all the information to glue the `value_type` of the containers and the node to be
- used in node algorithms, since these types can be different. Apart from this,
- `ValueTraits` also stores information about the link policy of the values to be inserted.
- Instead of using [*Boost.Intrusive] predefined hooks
- a user might want to develop customized containers, for example, using nodes that are
- optimized for a specific
- application or that are compatible with a legacy ABI. A user might want
- to have only two additional pointers in his class and insert the class in a doubly
- linked list sometimes and in a singly linked list in other situations. You can't
- achieve this using [*Boost.Intrusive] predefined hooks. Now, instead of using
- `base_hook<...>` or `member_hook<...>` options the user will specify the
- `value_traits<...>` options. Let's see how we can do this:
- [section:value_traits_interface ValueTraits interface]
- `ValueTraits` has the following interface:
- [c++]
- #include <boost/intrusive/pointer_traits.hpp>
- #include <boost/intrusive/link_mode.hpp>
- struct my_value_traits
- {
- typedef implementation_defined node_traits;
- typedef implementation_defined value_type;
- typedef node_traits::node_ptr node_ptr;
- typedef node_traits::const_node_ptr const_node_ptr;
- typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
- <value_type>::type::pointer pointer;
- typedef boost::intrusive::pointer_traits<node_ptr>::rebind_traits
- <const value_type>::type::pointer const_pointer;
- static const link_mode_type link_mode = some_linking_policy;
- static node_ptr to_node_ptr (value_type &value);
- static const_node_ptr to_node_ptr (const value_type &value);
- static pointer to_value_ptr (node_ptr n);
- static const_pointer to_value_ptr (const_node_ptr n);
- };
- Let's explain each type and function:
- * [*['node_traits]]: The node configuration that is needed by node algorithms.
- These node traits and algorithms are
- described in the previous chapter: [link intrusive.node_algorithms Node Algorithms].
- * If my_value_traits is meant to be used with [classref boost::intrusive::slist slist],
- `node_traits` should follow
- the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms].
- * If my_value_traits is meant to be used with [classref boost::intrusive::list list],
- `node_traits` should follow
- the interface needed by [classref boost::intrusive::circular_list_algorithms circular_list_algorithms].
- * If my_value_traits is meant to be used with [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset],
- `node_traits` should follow
- the interface needed by [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
- * If my_value_traits is meant to be used with [classref boost::intrusive::unordered_set unordered_set]/
- [classref boost::intrusive::unordered_multiset unordered_multiset], `node_traits`
- should follow the interface needed by [classref boost::intrusive::circular_slist_algorithms circular_slist_algorithms].
- * [*['node_ptr]]: A typedef for `node_traits::node_ptr`.
- * [*['const_node_ptr]]: A typedef for `node_traits::const_node_ptr`.
- * [*['value_type]]: The type that the user wants to insert in the container. This type can be
- the same as `node_traits::node` but it can be different (for example, `node_traits::node`
- can be a member type of `value_type`). If `value_type` and `node_traits::node` are the
- same type, the `to_node_ptr` and `to_value_ptr` functions are trivial.
- * [*['pointer]]: The type of a pointer to a `value_type`. It must be the same pointer type
- as `node_ptr`: If `node_ptr` is `node*`, `pointer` must be `value_type*`. If
- `node_ptr` is `smart_ptr<node_traits::node>`, `pointer` must be `smart_ptr<value_type>`.
- This can be generically achieved using `boost::intrusive::pointer_traits` (portable implementation of C++11
- `std::pointer_traits`).
- * [*['const_pointer]]: The type of a pointer to a `const value_type`. It must be the same pointer type
- as `node_ptr`: If `node_ptr` is `node*`, `const_pointer` must be `const value_type*`. If
- `node_ptr` is `smart_ptr<node_traits::node>`, `const_pointer` must be `smart_ptr<const value_type>`.
- * [*['link_mode]]: Indicates that `value_traits` needs some additional work or checks from the
- container. The types are enumerations defined in the `link_mode.hpp` header.
- These are the possible types:
- * [*`normal_link`]: If this linking policy is specified in a `ValueTraits` class
- as the link mode, containers
- configured with such `ValueTraits` won't set the hooks
- of the erased values to a default state. Containers also won't
- check that the hooks of the new values are default initialized.
- * [*`safe_link`]: If this linking policy is specified as the link mode
- in a `ValueTraits` class, containers
- configured with this `ValueTraits` will set the hooks
- of the erased values to a default state. Containers also will
- check that the hooks of the new values are default initialized.
- * [*`auto_unlink`]: Same as "safe_link" but containers with
- constant-time size features won't be
- compatible with `ValueTraits` configured with this policy.
- Containers also know that a value can be silently erased from
- the container without using any function provided by the containers.
- * [*['static node_ptr to_node_ptr (value_type &value)]] and
- [*['static const_node_ptr to_node_ptr (const value_type &value)]]:
- These functions take a reference to a value_type and return a pointer to the node
- to be used with node algorithms.
- * [*['static pointer to_value_ptr (node_ptr n)]] and
- [*['static const_pointer to_value_ptr (const_node_ptr n)]]:
- These functions take a pointer to a node and return a pointer to the value
- that contains the node.
- [endsect]
- [section:value_traits_example Custom ValueTraits example]
- Let's define our own `value_traits` class to be able to use [*Boost.Intrusive]
- containers with an old C structure whose definition can't be changed.
- That legacy type has two pointers that can be used to build singly and doubly linked
- lists: in singly linked lists we only need a pointer, whereas in doubly
- linked lists, we need two pointers. Since we only have two pointers, we can't insert
- the object in both a singly and a doubly linked list at the same time.
- This is the definition of the old node:
- [import ../example/doc_value_traits.cpp]
- [doc_value_traits_code_legacy]
- Now we have to define a NodeTraits class that will implement the functions/typedefs
- that will make the legacy node compatible with [*Boost.Intrusive] algorithms. After that,
- we'll define a ValueTraits class that will configure [*Boost.Intrusive] containers:
- [doc_value_traits_value_traits]
- Defining a value traits class that simply defines `value_type` as
- `legacy_node_traits::node` is a common approach when defining customized
- intrusive containers, so [*Boost.Intrusive] offers a templatized
- [classref boost::intrusive::trivial_value_traits trivial_value_traits] class
- that does exactly what we want:
- [doc_value_traits_trivial]
- Now we can just define the containers that will store the legacy abi objects and write
- a little test:
- [doc_value_traits_test]
- As seen, several key elements of [*Boost.Intrusive] can be reused with custom user types,
- if the user does not want to use the provided [*Boost.Intrusive] facilities.
- [endsect]
- [section:reusing_node_algorithms Reusing node algorithms for different values]
- In the previous example, `legacy_node_traits::node` type and
- `legacy_value_traits::value_type` are the same type, but this is not necessary. It's possible
- to have several `ValueTraits` defining the same `node_traits` type (and thus, the same `node_traits::node`).
- This reduces the number of node algorithm instantiations, but
- now `ValueTraits::to_node_ptr` and `ValueTraits::to_value_ptr` functions need to offer
- conversions between both types. Let's see a small example:
- First, we'll define the node to be used in the algorithms. For a linked list,
- we just need a node that stores two pointers:
- [import ../example/doc_advanced_value_traits.cpp]
- [doc_advanced_value_traits_code]
- Now we'll define two different types that will be inserted in intrusive lists and
- a templatized `ValueTraits` that will work for both types:
- [doc_advanced_value_traits_value_traits]
- Now define two containers. Both containers will instantiate the same list algorithms
- (`circular_list_algorithms<simple_node_traits>`),
- due to the fact that the value traits used to define the containers provide the same `node_traits` type:
- [doc_advanced_value_traits_containers]
- All [*Boost.Intrusive] containers using predefined hooks use this technique to minimize code size:
- all possible [classref boost::intrusive::list list] containers
- created with predefined hooks that define the same `VoidPointer` type
- share the same list algorithms.
- [endsect]
- [section:simplifying_value_traits Simplifying value traits definition]
- The previous example can be further simplified using the
- [classref boost::intrusive::derivation_value_traits derivation_value_traits]
- class to define a value traits class with a value that stores the
- `simple_node` as a base class:
- [import ../example/doc_derivation_value_traits.cpp]
- [doc_derivation_value_traits_value_traits]
- We can even choose to store `simple_node` as a member of `value_1` and `value_2`
- classes and use [classref boost::intrusive::member_value_traits member_value_traits]
- to define the needed value traits classes:
- [import ../example/doc_member_value_traits.cpp]
- [doc_member_value_traits_value_traits]
- [endsect]
- [section:stateful_value_traits Stateful value traits]
- Until now all shown custom value traits are stateless, that is, [*the transformation between nodes
- and values is implemented in terms of static functions]. It's possible to use [*stateful] value traits
- so that we can separate nodes and values and [*avoid modifying types to insert nodes].
- [*Boost.Intrusive] differentiates between stateful and stateless value traits by checking if all
- Node <-> Value transformation functions are static or not (except for Visual 7.1, since overloaded
- static function detection is not possible, in this case the implementation checks if the class is empty):
- * If all Node <-> Value transformation functions are static , a [*stateless]
- value traits is assumed. transformations must be static functions.
- * Otherwise a [*stateful] value traits is assumed.
- Using stateful value traits it's possible to create containers of non-copyable/movable objects [*without modifying]
- the definition of the class to be inserted. This interesting property is achieved without using global variables
- (stateless value traits could use global variables to achieve the same goal), so:
- * [*Thread-safety guarantees]: Better thread-safety guarantees can be achieved with stateful
- value traits, since accessing global resources might require synchronization primitives that
- can be avoided when using internal state.
- * [*Flexibility]: A stateful value traits type can be configured at run-time.
- * [*Run-time polymorphism]: A value traits might implement node <-> value
- transformations as virtual functions. A single container type could be
- configured at run-time to use different node <-> value relationships.
- Stateful value traits have many advantages but also some downsides:
- * [*Performance]: Value traits operations should be very efficient since they are basic operations used by containers.
- [*A heavy node <-> value transformation will hurt intrusive containers' performance].
- * [*Exception guarantees]: The stateful ValueTraits must maintain no-throw guarantees, otherwise, the
- container invariants won't be preserved.
- * [*Static functions]: Some static functions offered by intrusive containers are not
- available because node <-> value transformations are not static.
- * [*Bigger iterators]: The size of some iterators is increased because the iterator
- needs to store a pointer to the stateful value traits to implement node to value
- transformations (e.g. `operator*()` and `operator->()`).
- An easy and useful example of stateful value traits is when an array of values can be indirectly introduced
- in a list guaranteeing no additional allocation apart from the initial resource reservation:
- [import ../example/doc_stateful_value_traits.cpp]
- [doc_stateful_value_traits]
- [endsect]
- [endsect]
- [section:thread_safety Thread safety guarantees]
- Intrusive containers have thread safety guarantees similar to STL containers.
- * Several threads having read or write access to different instances is safe as long as inserted
- objects are different.
- * Concurrent read-only access to the same container is safe.
- Some Intrusive hooks (auto-unlink hooks, for example) modify containers without
- having a reference to them: this is considered a write access to the container.
- Other functions, like checking if an object is already inserted in a container using the `is_linked()`
- member of safe hooks, constitute read access on the container without having a reference to it, so no other
- thread should have write access (direct or indirect) to that container.
- Since the same object can be inserted in several containers at the same time using different hooks,
- the thread safety of [*Boost.Intrusive] is related to the containers and also to the object whose lifetime
- is manually managed by the user.
- As we can see, the analysis of the thread-safety of a program using [*Boost.Intrusive] is harder
- than with non-intrusive containers.
- To analyze the thread safety, consider the following points:
- * The auto-unlink hook's destructor and `unlink()` functions modify the container indirectly.
- * The safe mode and auto-unlink hooks' `is_linked()` functions are a read access to the container.
- * Inserting an object in containers that will be modified by different threads has no thread safety
- guarantee, although in most platforms it will be thread-safe without locking.
- [endsect]
- [section:boost_intrusive_iterators Boost.Intrusive Iterator features]
- [section:null_forward_iterators Null forward iterators]
- [*Boost.Intrusive] implements
- [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf C++14 Null Forward Iterators],
- a feature that was introduced with C++14. This means that equality and inequality comparison are defined
- over all iterators for the same underlying sequence and the value initialized-iterators.
- Value initialized iterators behave as if they refer past the end of the same empty sequence:
- [c++]
- list<MyType> l = { ... };
- auto ni = list<MyType>::iterator();
- auto nd = list<MyType2>::iterator();
- ni == ni; // True.
- nd != nd; // False.
- ni == nd; // Won't compile.
- [endsect]
- [section:scary_iterators Scary Iterators]
- The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf,
- SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
- iterator types have no dependency on any type argument apart from the container's `value_type`,
- `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
- the types of a standard container's iterators should not depend on the container's `key_compare`,
- `hasher`, `key_equal`, or `allocator` types.
- That paper demonstrated that SCARY operations were crucial to the performant implementation of common
- design patterns using STL components. It showed that implementations that support SCARY operations reduce
- object code bloat by eliminating redundant specializations of iterator and algorithm templates.
- [*Boost.Intrusive] containers are a bit different from standard containers. In particular, they have no
- allocator parameter and they can be configured with additional options not present in STL-like containers.
- Thus [*Boost.Intrusive] offers its own `SCARY iterator` implementation, where iterator types don't
- change when the container is configured with an option that does not alter the value <-> node transformation.
- More concretely, the following options and conditions guarantee that iterator types are unchanged:
- * [*All containers]: `size_type<>`, `constant_time_size<>`,
- * [*`slist`]: `cache_last<>`, `linear<>`,
- * [*`unordered_[multi]set`]: `hash<>`, `equal<>`, `power_2_buckets<>`, `cache_begin<>`.
- * [*All tree-like containers] (`[multi]set`, `avl_[multi]set`, `sg_[multi]set`, `bs_[multi]set`,
- `splay_[multi]set`, `treap_[multi]set`): `compare<>`.
- * [*`treap_[multi]set`]: `priority<>`
- * [*`bs_[multi]set`, `sg_[multi]set`, `treap_[multi]set`, `splay_[multi]set`]:
- They share the same iterator type when configured with the same options.
- [endsect]
- [endsect]
- [section:equal_range_stability Stability and insertion with hint in ordered associative containers with equivalent keys]
- [*Boost.Intrusive] ordered associative containers with equivalent keys offer stability guarantees, following
- [@http://open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 C++ standard library's defect #233 resolution],
- explained in document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html Comments on LWG issue 233: Insertion hints in associative containers].
- This means that:
- * A ['Insert without hint] member function always insert at the upper bound of an equal range.
- * A ['Insert with hint] member function inserts the new value [*before the hint] if hint's and new node's keys are equivalent.
- * Implements Andrew Koenig ['as close as possible to hint] proposal. A new element is always be inserted as close to the hint as possible.
- So, for example, if there is a subsequence of equivalent values, `a.begin()` as the hint means that the new element should be inserted
- before the subsequence even if `a.begin()` is far away. This allows code to always append (or prepend) an equal range with something
- as simple as: `m.insert(m.end(), new_node);` or `m.insert(m.begin(), new_node);`
- [endsect]
- [section:obtaining_same_type_reducing_space Obtaining the same types and reducing symbol length]
- The flexible option specification mechanism used by [*Boost.Intrusive] for hooks and containers
- has a couple of downsides:
- * If a user specifies the same options in different order or specifies some options and leaves the
- rest as defaults, the type of the created container/hook will be different. Sometimes
- this is annoying, because two programmers specifying the same options might end up with incompatible
- types. For example, the following two lists, although using the same options, do not have
- the same type:
- [c++]
- #include <boost/intrusive/list.hpp>
- using namespace boost::intrusive;
- //Explicitly specify constant-time size and size type
- typedef list<T, constant_time_size<true>, size_type<std::size_t> List1;
- //Implicitly specify constant-time size and size type
- typedef list<T> List2;
- * Option specifiers lead to long template symbols for classes and functions. Option specifiers themselves
- are verbose and without variadic templates, several default template parameters are assigned for
- non-specified options. Object and debugging information files can grow and compilation times
- may suffer if long names are produced.
- To solve these issues [*Boost.Intrusive] offers some helper metafunctions that reduce symbol lengths
- and create the same type if the same options (either explicitly or implicitly) are used. These also
- improve compilation times. All containers and hooks have their respective `make_xxx` versions.
- The previously shown example can be rewritten like this to obtain the same list type:
- [c++]
- #include <boost/intrusive/list.hpp>
- using namespace boost::intrusive;
- #include <boost/intrusive/list.hpp>
- using namespace boost::intrusive;
- //Explicitly specify constant-time size and size type
- typedef make_list<T, constant_time_size<true>, size_type<std::size_t>::type List1;
- //Implicitly specify constant-time size and size type
- typedef make_list<T>::type List2;
- Produced symbol lengths and compilation times will usually be shorter and object/debug files smaller.
- If you are concerned with file sizes and compilation times, this option is your best choice.
- [endsect]
- [section:design_notes Design Notes]
- When designing [*Boost.Intrusive] the following guidelines have been taken into account:
- [section:performance_sensitive Boost.Intrusive in performance sensitive environments]
- [*Boost.Intrusive] should be a valuable tool in performance sensitive environments,
- and following this guideline, [*Boost.Intrusive] has been designed to offer well
- known complexity guarantees. Apart from that, some options, like optional
- constant-time, have been designed to offer faster complexity guarantees in some
- functions, like `slist::splice`.
- The advanced lookup and insertion functions for associative containers, taking
- an arbitrary key type and predicates, were designed to avoid unnecessary object
- constructions.
- [endsect]
- [section:space_constrained Boost.Intrusive in space constrained environments]
- [*Boost.Intrusive] should be useful in space constrained environments,
- and following this guideline [*Boost.Intrusive] separates node algorithms
- and intrusive containers to avoid instantiating node algorithms for each
- user type. For example, a single class of red-black algorithms will be instantiated
- to implement all set and multiset containers using raw pointers. This way,
- [*Boost.Intrusive] seeks to avoid any code size overhead associated with templates.
- Apart from that, [*Boost.Intrusive] implements some size improvements: for example,
- red-black trees embed the color bit in the parent pointer lower bit, if nodes
- are two-byte aligned. The option to forgo constant-time size operations can
- reduce container size, and this extra size optimization is noticeable
- when the container is empty or contains few values.
- [endsect]
- [section:basic_building_block Boost.Intrusive as a basic building block]
- [*Boost.Intrusive] can be a basic building block to build more complex containers
- and this potential has motivated many design decisions. For example, the ability
- to have more than one hook per user type opens the opportunity to implement multi-index
- containers on top of [*Boost.Intrusive].
- [*Boost.Intrusive] containers implement advanced functions taking function objects
- as arguments (`clone_from`, `erase_and_dispose`, `insert_check`, etc.). These
- functions come in handy when implementing non-intrusive containers
- (for example, STL-like containers) on top of intrusive containers.
- [endsect]
- [section:extending_intrusive Extending Boost.Intrusive]
- [*Boost.Intrusive] offers a wide range of containers but also allows the
- construction of custom containers reusing [*Boost.Intrusive] elements.
- The programmer might want to use node algorithms directly or
- build special hooks that take advantage of an application environment.
- For example, the programmer can customize parts of [*Boost.Intrusive]
- to manage old data structures whose definition can't be changed.
- [endsect]
- [endsect]
- [section:performance Performance]
- [*Boost.Intrusive] containers offer speed improvements compared to non-intrusive containers
- primarily because:
- * They minimize memory allocation/deallocation calls.
- * They obtain better memory locality.
- This section will show performance tests comparing some operations on
- `boost::intrusive::list` and `std::list`:
- * Insertions using `push_back` and container destruction will show the
- overhead associated with memory allocation/deallocation.
- * The `reverse` member function will show the advantages of the compact
- memory representation that can be achieved with intrusive containers.
- * The `sort` and `write access` tests will show the advantage of intrusive containers
- minimizing memory accesses compared to containers of pointers.
- Given an object of type `T`, [classref boost::intrusive::list boost::intrusive::list<T>]
- can replace `std::list<T>` to avoid memory allocation overhead,
- or it can replace `std::list<T*>` when the user wants containers with
- polymorphic values or wants to share values between several containers.
- Because of this versatility, the performance tests will be executed for 6 different
- list types:
- * 3 intrusive lists holding a class named `itest_class`,
- each one with a different linking policy (`normal_link`, `safe_link`, `auto_unlink`).
- The `itest_class` objects will be tightly packed in a `std::vector<itest_class>` object.
- * `std::list<test_class>`, where `test_class` is exactly the same as `itest_class`,
- but without the intrusive hook.
- * `std::list<test_class*>`. The list will contain pointers to `test_class` objects
- tightly packed in a `std::vector<test_class>` object. We'll call this configuration ['compact pointer list]
- * `std::list<test_class*>`. The list will contain pointers to `test_class` objects owned by a
- `std::list<test_class>` object. We'll call this configuration ['disperse pointer list].
- Both `test_class` and `itest_class` are templatized classes that can be configured with
- a boolean to increase the size of the object. This way, the tests can be executed with
- small and big objects. Here is the first part of the testing code, which shows
- the definitions of `test_class` and `itest_class` classes, and some other
- utilities:
- [import ../perf/perf_list.cpp]
- [perf_list_value_type]
- As we can see, `test_class` is a very simple class holding an `int`. `itest_class`
- is just a class that has a base hook ([classref boost::intrusive::list_base_hook list_base_hook])
- and also derives from `test_class`.
- `func_ptr_adaptor` is just a functor adaptor to convert function objects taking
- `test_list` objects to function objects taking pointers to them.
- You can find the full test code in the
- [@../../libs/intrusive/perf/perf_list.cpp perf_list.cpp] source file.
- [section:performance_results_push_back Back insertion and destruction]
- The first test will measure the benefits we can obtain with intrusive containers
- avoiding memory allocations and deallocations. All the objects to be
- inserted in intrusive containers are allocated in a single allocation call,
- whereas `std::list` will need to allocate memory for each object and deallocate it
- for every erasure (or container destruction).
- Let's compare the code to be executed for each container type for different insertion tests:
- [perf_list_push_back_intrusive]
- For intrusive containers, all the values are created in a vector and after that
- inserted in the intrusive list.
- [perf_list_push_back_stdlist]
- For a standard list, elements are pushed back using push_back().
- [perf_list_push_back_stdptrlist]
- For a standard compact pointer list, elements are created in a vector and pushed back
- in the pointer list using push_back().
- [perf_list_push_back_disperse_stdptrlist]
- For a ['disperse pointer list], elements are created in a list and pushed back
- in the pointer list using push_back().
- These are the times in microseconds for each case, and the normalized time:
- [table Back insertion + destruction times for Visual C++ 7.1 / Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [5000 / 22500] [1 / 1]]
- [[`safe_link` intrusive list] [7812 / 32187] [1.56 / 1.43]]
- [[`auto_unlink` intrusive list] [10156 / 41562] [2.03 / 1.84]]
- [[Standard list] [26875 / 97500] [5.37 / 4.33]]
- [[Standard compact pointer list] [76406 / 86718] [15.28 / 3.85]]
- [[Standard disperse pointer list] [146562 / 175625] [29.31 / 7.80]]
- ]
- [table Back insertion + destruction times for GCC 4.1.1 / MinGW over Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [4375 / 22187] [1 / 1]]
- [[`safe_link` intrusive list] [7812 / 32812] [1.78 / 1.47]]
- [[`auto_unlink` intrusive list] [10468 / 42031] [2.39 / 1.89]]
- [[Standard list] [81250 / 98125] [18.57 / 4.42]]
- [[Standard compact pointer list] [83750 / 94218] [19.14 / 4.24]]
- [[Standard disperse pointer list] [155625 / 175625] [35.57 / 7.91]]
- ]
- [table Back insertion + destruction times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [4792 / 20495] [1 / 1]]
- [[`safe_link` intrusive list] [7709 / 30803] [1.60 / 1.5]]
- [[`auto_unlink` intrusive list] [10180 / 41183] [2.12 / 2.0]]
- [[Standard list] [17031 / 32586] [3.55 / 1.58]]
- [[Standard compact pointer list] [27221 / 34823] [5.68 / 1.69]]
- [[Standard disperse pointer list] [102272 / 60056] [21.34 / 2.93]]
- ]
- The results are logical: intrusive lists just need one allocation. The destruction
- time of the `normal_link` intrusive container is trivial (complexity: `O(1)`),
- whereas `safe_link` and `auto_unlink` intrusive containers need to put the hooks of
- erased values in the default state (complexity: `O(NumElements)`). That's why
- `normal_link` intrusive list shines in this test.
- Non-intrusive containers need to make many more allocations and that's why they
- lag behind. The `disperse pointer list` needs to make `NumElements*2` allocations,
- so the result is not surprising.
- The Linux test shows that standard containers perform very well against intrusive containers
- with big objects. Nearly the same GCC version in MinGW performs worse, so maybe
- a good memory allocator is the reason for these excellent results.
- [endsect]
- [section:performance_results_reversing Reversing]
- The next test measures the time needed to complete calls to the member function `reverse()`.
- Values (`test_class` and `itest_class`) and lists are created as explained in the
- previous section.
- Note that for pointer lists, `reverse` [*does not need to access `test_class` values
- stored in another list or vector],
- since this function just needs to adjust internal pointers, so in theory all tested
- lists need to perform the same operations.
- These are the results:
- [table Reverse times for Visual C++ 7.1 / Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2656 / 10625] [1 / 1.83]]
- [[`safe_link` intrusive list] [2812 / 10937] [1.05 / 1.89]]
- [[`auto_unlink` intrusive list] [2710 / 10781] [1.02 / 1.86]]
- [[Standard list] [5781 / 14531] [2.17 / 2.51]]
- [[Standard compact pointer list] [5781 / 5781] [2.17 / 1]]
- [[Standard disperse pointer list] [10781 / 15781] [4.05 / 2.72]]
- ]
- [table Reverse times for GCC 4.1.1 / MinGW over Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2656 / 10781] [1 / 2.22]]
- [[`safe_link` intrusive list] [2656 / 10781] [1 / 2.22]]
- [[`auto_unlink` intrusive list] [2812 / 10781] [1.02 / 2.22]]
- [[Standard list] [4843 / 12500] [1.82 / 2.58]]
- [[Standard compact pointer list] [4843 / 4843] [1.82 / 1]]
- [[Standard disperse pointer list] [9218 / 12968] [3.47 / 2.67]]
- ]
- [table Reverse times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2742 / 10847] [1 / 3.41]]
- [[`safe_link` intrusive list] [2742 / 10847] [1 / 3.41]]
- [[`auto_unlink` intrusive list] [2742 / 11027] [1 / 3.47]]
- [[Standard list] [3184 / 10942] [1.16 / 3.44]]
- [[Standard compact pointer list] [3207 / 3176] [1.16 / 1]]
- [[Standard disperse pointer list] [5814 / 13381] [2.12 / 4.21]]
- ]
- For small objects the results show that the compact storage of values in intrusive
- containers improve locality and reversing is faster than with standard containers,
- whose values might be dispersed in memory because each value is independently
- allocated. Note that the dispersed pointer list (a list of pointers to values
- allocated in another list) suffers more because nodes of the pointer list
- might be more dispersed, since allocations from both lists are interleaved
- in the code:
- [c++]
- //Object list (holding `test_class`)
- stdlist objects;
- //Pointer list (holding `test_class` pointers)
- stdptrlist l;
- for(int i = 0; i < NumElements; ++i){
- //Allocation from the object list
- objects.push_back(stdlist::value_type(i));
- //Allocation from the pointer list
- l.push_back(&objects.back());
- }
- For big objects the compact pointer list wins because the reversal test doesn't need access
- to values stored in another container. Since all the allocations for nodes of
- this pointer list are likely to be close (since there is no other allocation in the
- process until the pointer list is created) locality is better than with intrusive
- containers. The dispersed pointer list, as with small values, has poor locality.
- [endsect]
- [section:performance_results_sorting Sorting]
- The next test measures the time needed to complete calls to the member function
- `sort(Pred pred)`. Values (`test_class` and `itest_class`) and lists are created as explained in the
- first section. The values will be sorted in ascending and descending order each
- iteration. For example, if ['l] is a list:
- [c++]
- for(int i = 0; i < NumIter; ++i){
- if(!(i % 2))
- l.sort(std::greater<stdlist::value_type>());
- else
- l.sort(std::less<stdlist::value_type>());
- }
- For a pointer list, the function object will be adapted using `func_ptr_adaptor`:
- [c++]
- for(int i = 0; i < NumIter; ++i){
- if(!(i % 2))
- l.sort(func_ptr_adaptor<std::greater<stdlist::value_type> >());
- else
- l.sort(func_ptr_adaptor<std::less<stdlist::value_type> >());
- }
- Note that for pointer lists, `sort` will take a function object that [*will access
- `test_class` values stored in another list or vector], so pointer lists will suffer
- an extra indirection: they will need to access the `test_class` values stored in
- another container to compare two elements.
- These are the results:
- [table Sort times for Visual C++ 7.1 / Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [16093 / 38906] [1 / 1]]
- [[`safe_link` intrusive list] [16093 / 39062] [1 / 1]]
- [[`auto_unlink` intrusive list] [16093 / 38906] [1 / 1]]
- [[Standard list] [32343 / 56406] [2.0 / 1.44]]
- [[Standard compact pointer list] [33593 / 46093] [2.08 / 1.18]]
- [[Standard disperse pointer list] [46875 / 68593] [2.91 / 1.76]]
- ]
- [table Sort times for GCC 4.1.1 / MinGW over Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [15000 / 39218] [1 / 1]]
- [[`safe_link` intrusive list] [15156 / 39531] [1.01 / 1.01]]
- [[`auto_unlink` intrusive list] [15156 / 39531] [1.01 / 1.01]]
- [[Standard list] [34218 / 56875] [2.28 / 1.45]]
- [[Standard compact pointer list] [35468 / 49218] [2.36 / 1.25]]
- [[Standard disperse pointer list] [47656 / 70156] [3.17 / 1.78]]
- ]
- [table Sort times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [18003 / 40795] [1 / 1]]
- [[`safe_link` intrusive list] [18003 / 41017] [1 / 1]]
- [[`auto_unlink` intrusive list] [18230 / 40941] [1.01 / 1]]
- [[Standard list] [26273 / 49643] [1.45 / 1.21]]
- [[Standard compact pointer list] [28540 / 43172] [1.58 / 1.05]]
- [[Standard disperse pointer list] [35077 / 57638] [1.94 / 1.41]]
- ]
- The results show that intrusive containers are faster than standard
- containers. We can see that the pointer
- list holding pointers to values stored in a vector is quite fast, so the extra
- indirection that is needed to access the value is minimized because all the values
- are tightly stored, improving caching. The disperse list, on the other hand, is
- slower because the indirection to access values stored in the object list is
- more expensive than accessing values stored in a vector.
- [endsect]
- [section:performance_results_write_access Write access]
- The next test measures the time needed to iterate through all the elements of a list, and
- increment the value of the internal `i_` member:
- [c++]
- stdlist::iterator it(l.begin()), end(l.end());
- for(; it != end; ++it)
- ++(it->i_);
- Values (`test_class` and `itest_class`) and lists are created as explained in
- the first section. Note that for pointer lists, the iteration will suffer
- an extra indirection: they will need to access the `test_class` values stored in
- another container:
- [c++]
- stdptrlist::iterator it(l.begin()), end(l.end());
- for(; it != end; ++it)
- ++((*it)->i_);
- These are the results:
- [table Write access times for Visual C++ 7.1 / Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2031 / 8125] [1 / 1]]
- [[`safe_link` intrusive list] [2031 / 8281] [1 / 1.01]]
- [[`auto_unlink` intrusive list] [2031 / 8281] [1 / 1.01]]
- [[Standard list] [4218 / 10000] [2.07 / 1.23]]
- [[Standard compact pointer list] [4062 / 8437] [2.0 / 1.03]]
- [[Standard disperse pointer list] [8593 / 13125] [4.23 / 1.61]]
- ]
- [table Write access times for GCC 4.1.1 / MinGW over Windows XP
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2343 / 8281] [1 / 1]]
- [[`safe_link` intrusive list] [2500 / 8281] [1.06 / 1]]
- [[`auto_unlink` intrusive list] [2500 / 8281] [1.06 / 1]]
- [[Standard list] [4218 / 10781] [1.8 / 1.3]]
- [[Standard compact pointer list] [3906 / 8281] [1.66 / 1]]
- [[Standard disperse pointer list] [8281 / 13750] [3.53 / 1.66]]
- ]
- [table Write access times for GCC 4.1.2 / Linux Kernel 2.6.18 (OpenSuse 10.2)
- [[Container] [Time in us/iteration (small object / big object)] [Normalized time (small object / big object)]]
- [[`normal_link` intrusive list] [2286 / 8468] [1 / 1.1]]
- [[`safe_link` intrusive list] [2381 / 8412] [1.04 / 1.09]]
- [[`auto_unlink` intrusive list] [2301 / 8437] [1.01 / 1.1]]
- [[Standard list] [3044 / 9061] [1.33 / 1.18]]
- [[Standard compact pointer list] [2755 / 7660] [1.20 / 1]]
- [[Standard disperse pointer list] [6118 / 12453] [2.67 / 1.62]]
- ]
- As with the read access test, the results show that intrusive containers outperform
- all other containers if the values are tightly packed in a vector.
- The disperse list is again the slowest.
- [endsect]
- [section:performance_results_conclusions Conclusions]
- Intrusive containers can offer performance benefits that cannot be achieved with
- equivalent non-intrusive containers. Memory locality improvements are noticeable
- when the objects to be inserted are small. Minimizing memory allocation/deallocation calls is also
- an important factor and intrusive containers make this simple if all objects
- to be inserted in intrusive containers are allocated using `std::vector` or `std::deque`.
- [endsect]
- [endsect]
- [section:release_notes Release Notes]
- [section:release_notes_boost_1_71_00 Boost 1.71 Release]
- * Fixed bugs:
- * [@https://github.com/boostorg/intrusive/pull/42 GitHub #42: ['Documentation does not describe treap priority_of_value changes]]
- * [@https://github.com/boostorg/intrusive/pull/43 GitHub #43: ['Fix tests with BOOST_INTRUSIVE_VARIADIC_TEMPLATES enabled]]
- * [@https://github.com/boostorg/intrusive/pull/45 GitHub #45: ['Disable variadic templates for MSVC-12 to avoid ICEs]]
-
- [endsect]
- [section:release_notes_boost_1_70_00 Boost 1.70 Release]
- * Fixed bugs:
- * [@https://github.com/boostorg/intrusive/pull/33 GitHub Pull #33: ['Fix compilation in case if key is void*, again]]
- * [@https://github.com/boostorg/intrusive/issues/34 GitHub Issue #34: ['-Wdeprecated-copy on gcc9]]
- * [@https://github.com/boostorg/intrusive/issues/35 GitHub Issue #35: ['key_of_value on treap_set seems to be broken in 1.69]]
- * [@https://github.com/boostorg/intrusive/issues/38 GitHub Issue #38: ['treap: Same type for priority and key comparison leads to ambiguous base class error]]
- * [@https://github.com/boostorg/intrusive/pull/39 GitHub Pull #39: ['Fix -Wextra-semi clang warnings]]
- [endsect]
- [section:release_notes_boost_1_67_00 Boost 1.67 Release]
- * Fixed bugs:
- * [@https://github.com/boostorg/intrusive/issues/29 GitHub Issues #29: ['Uninitialized variable warning pointer_plus_bits.hpp]]
- [endsect]
- [section:release_notes_boost_1_65_00 Boost 1.65 Release]
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/12894 Boost Trac #12894: ['Allow non std::size_t size_type]]
- * [@https://svn.boost.org/trac/boost/ticket/12698 Boost Trac #12698: ['base64 iterators can't be used with iterator_advance]]
- * [@https://github.com/boostorg/intrusive/pull/23 GitHub Pull #23: ['Conditionally replace deprecated/removed C++98 std::random_shuffle by...]]
- * [@https://github.com/boostorg/intrusive/pull/24 GitHub Pull #24: ['Adds support for MSVC ARM64 target]]
- [endsect]
- [section:release_notes_boost_1_64_00 Boost 1.64 Release]
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/12745 Boost Trac #12745: ['key_nodeptr_comp broken if the key type is void*]]
- * [@https://svn.boost.org/trac/boost/ticket/12761 Boost Trac #12761: ['intrusive::set::swap doesn't swap the comparison function*]]
- [endsect]
- [section:release_notes_boost_1_63_00 Boost 1.63 Release]
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/12556 Boost Trac #12556: ['member_value_traits.hpp has a missing #include]]
- [endsect]
- [section:release_notes_boost_1_62_00 Boost 1.62 Release]
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/11476 Boost Trac #11476: ['has_member_function_callable_with.hpp is massively broken with BOOST_NO_CXX11_DECLTYPE]]
- * [@https://svn.boost.org/trac/boost/ticket/11994 Boost Trac #11994: ['Support intrusive container key extractors that return the key by value]]
- * [@https://svn.boost.org/trac/boost/ticket/12184 Boost Trac #12184: ['clang -Wdocumentation warning]]
- * [@https://svn.boost.org/trac/boost/ticket/12190 Boost Trac #12190: ['Intrusive List + Flat Map combination crashes]]
- * [@https://svn.boost.org/trac/boost/ticket/12229 Boost Trac #12229: ['intrusive::unordered_set<T>::rehash() broken]]
- * [@https://svn.boost.org/trac/boost/ticket/12245 Boost Trac #12245: ['bstree uses a shared static size_traits for constant_time_size<false>]]
- * [@https://svn.boost.org/trac/boost/ticket/12432 Boost Trac #12432: ['Forced KeyOfValue creation when using custom compare on insert_check]]
- * Implemented `merge` functions in ordered associative containers.
- * Officially documented `root()` function for tree-based containers.
- [endsect]
- [section:release_notes_boost_1_61_00 Boost 1.61 Release]
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/11832 Boost Trac #11832: ['clang-cl + boost intrusive = miscompile]]
- * [@https://svn.boost.org/trac/boost/ticket/11865 Boost Trac #11865: ['Intrusive list explicit ctor error with Clang 3.6 (C++11/14)]]
- * [@https://svn.boost.org/trac/boost/ticket/11992 Boost Trac #11992: ['Add an overload of insert_check taking a key_type]]
- * [@https://github.com/boostorg/intrusive/pull/19 GitHub Pull #19: ['ebo_functor_holder: compile fix for copy constructor]]
- [endsect]
- [section:release_notes_boost_1_60_00 Boost 1.60 Release]
- * [link intrusive.advanced_lookups_insertions Advanced lookup and insertions] in ordered associative containers
- now support comparison functions that are not required to offer the same strict weak ordering as `key_compare`,
- the container must be partitioned in regards to the passed comparison object.
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/11701 Boost Trac #11701: ['Regression in boost::intrusive::set::equal_range]]
- * [@https://svn.boost.org/trac/boost/ticket/11765 Boost Trac #11765: ['sgtree.hpp:830: bad if test ?]]
- [endsect]
- [section:release_notes_boost_1_59_00 Boost 1.59 Release]
- * Implemented [link intrusive.map_multimap map and multimap-like interfaces].
- * Refactored hashtable containers to reduce template instantiations.
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/11222 Boost Trac #11222: ['intrusive/pointer_traits.hpp fails to compile with C++98]]
- [endsect]
- [section:release_notes_boost_1_58_00 Boost 1.58 Release]
- * Reduced compile-time dependencies, headers, and the use of Boost.Preprocessor, specially for hooks and iterators.
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/6720 Boost Trac #6720: ['intrusive::unordered_set::clear_and_dispose does not compile on VC11 Beta when passed a stateless lambda]]
- * [@https://svn.boost.org/trac/boost/ticket/10771 Boost Trac #10771: ['remove_if is broken for slist]]
- * [@https://svn.boost.org/trac/boost/ticket/10853 Boost Trac #10853: ['problem with detection of const_cast_from]]
- * [@https://svn.boost.org/trac/boost/ticket/10987 Boost Trac #10987: ['bug in any_xxx_node_traits, returning by reference]]
- [endsect]
- [section:release_notes_boost_1_57_00 Boost 1.57 Release]
- * Experimental version of node checkers, contributed by Matei David. Many thanks!
- * Implemented [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf N3644: Null Forward Iterators] from C++14.
- * Fixed bugs:
- * [@https://github.com/boostorg/intrusive/pull/12 GitHub Pull #12: ['Fix MSVC14 warning C4456: declaration of 'x_parent_right' hides previous local declaration]]
- * [@https://svn.boost.org/trac/boost/ticket/10520 Boost Trac #10520: ['Conversion warning in intrusive/detail/utilities.hpp]]
- * [@https://svn.boost.org/trac/boost/ticket/10469 Boost Trac #10469: ['Erasing from intrusive unordered_multiset with optimize_multikey goes into an infinite loop]]
- [endsect]
- [section:release_notes_boost_1_56_00 Boost 1.56 Release]
- * Improved Doxygen generated reference and updated and fixed forward-declaration header.
- * [*ABI breaking]: Fixed ABI regression introduced in Boost 1.55 version, mainly noticeable on MSVC compilers.
- * [*Source breaking]: Removed previously deprecated `xxx_dont_splay` functions from splay containers,
- `splay_set_base_hook` and `splay_set_member_hook`from splay containers and `bool splay = true`
- extra parameter in `splaytree_algorithms` functions.
- * Fixed bugs:
- * [@https://svn.boost.org/trac/boost/ticket/8468 #8468: Compile error on visual studio 2010/2012 using vector with custom allocator and aligned types]
- * [@https://svn.boost.org/trac/boost/ticket/9332 #9332: ['"has_member_function_callable_with.hpp compile error on msvc-12.0"]].
- * [@https://svn.boost.org/trac/boost/ticket/9650 #9650: ['"intrusive list with stateful value traits"]].
- * [@https://svn.boost.org/trac/boost/ticket/9746 #9746: Modern Sun CC compiler detects error in intrusive library header]
- * [@https://svn.boost.org/trac/boost/ticket/9940 #9940: bad bug in intrusive list with safe_link (or auto_unlink) hooks]
- * [@https://svn.boost.org/trac/boost/ticket/9948 #9948: remove use of const_cast in intrusive containers]
- * [@https://svn.boost.org/trac/boost/ticket/9949 #9949: clear header node hooks upon intrusive container destruction]
- * [@https://svn.boost.org/trac/boost/ticket/9961 #9961: tests for hooks not derived frorm generic_hook]
- * Optimized tree rebalancing code to avoid redundant assignments.
- * Added 64 bit prime values for `suggested_upper_bucket_count`/`suggested_lower_bucket_count` in 64 bit platforms.
- * Deleted workarounds for old SUN_CC compilers, those are now unsupported as modern SunPro compilers are standard-corforming enough.
- [endsect]
- [section:release_notes_boost_1_55_00 Boost 1.55 Release]
- * [*Source breaking]: Deprecated `xxx_dont_splay` functions from splay containers.
- Deprecated `splay_set_base_hook` and `splay_set_member_hook`from splay containers, use
- `bs_set_base_hook` or `bs_set_member_hook` instead.
- Both will be removed in Boost 1.56.
- * [*ABI breaking]: Hash containers' end iterator was implemented pointing to one-past the end of the bucket array
- (see [@https://svn.boost.org/trac/boost/ticket/8698 #8698]) causing severe bugs when values to be inserted
- where allocated next to the bucket array. End iterator implementation was changed to point to the beginning
- of the bucket array.
- * Big refactoring in order to reduce template and debug symbol bloat. Test object files have been slashed
- to half in MSVC compilers in Debug mode. Toolchains without Identical COMDAT Folding (ICF) should notice size improvements.
- * Implemented [link intrusive.scary_iterators SCARY iterators].
- [endsect]
- [section:release_notes_boost_1_54_00 Boost 1.54 Release]
- * Added `BOOST_NO_EXCEPTIONS` support (bug [@https://svn.boost.org/trac/boost/ticket/7849 #7849]).
- [endsect]
- [section:release_notes_boost_1_53_00 Boost 1.53 Release]
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/7174 #7174],
- [@https://svn.boost.org/trac/boost/ticket/7529 #7529],
- [@https://svn.boost.org/trac/boost/ticket/7815 #7815].
- * Fixed GCC -Wshadow warnings.
- * Added missing `explicit` keyword in several intrusive container constructors.
- * Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros.
- * Small documentation fixes.
- [endsect]
- [section:release_notes_boost_1_51_00 Boost 1.51 Release]
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/6841 #6841],
- [@https://svn.boost.org/trac/boost/ticket/6907 #6907],
- [@https://svn.boost.org/trac/boost/ticket/6922 #6922],
- [@https://svn.boost.org/trac/boost/ticket/7033 #7033],
- * Added `bounded_range` function to trees.
- [endsect]
- [section:release_notes_boost_1_49_00 Boost 1.49 Release]
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/6347 #6347],
- [@https://svn.boost.org/trac/boost/ticket/6223 #6223],
- [@https://svn.boost.org/trac/boost/ticket/6153 #6153].
- [endsect]
- [section:release_notes_boost_1_48_00 Boost 1.48 Release]
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/4797 #4797],
- [@https://svn.boost.org/trac/boost/ticket/5165 #5165],
- [@https://svn.boost.org/trac/boost/ticket/5183 #5183],
- [@https://svn.boost.org/trac/boost/ticket/5191 #5191].
- [endsect]
- [section:release_notes_boost_1_46_00 Boost 1.46 Release]
- * Fixed bug
- [@https://svn.boost.org/trac/boost/ticket/4980 #4980],
- [endsect]
- [section:release_notes_boost_1_45_00 Boost 1.45 Release]
- * Added `function_hook` option.
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/2611 #2611],
- [@https://svn.boost.org/trac/boost/ticket/3288 #3288],
- [@https://svn.boost.org/trac/boost/ticket/3304 #3304],
- [@https://svn.boost.org/trac/boost/ticket/3489 #3489],
- [@https://svn.boost.org/trac/boost/ticket/3668 #3668],
- [@https://svn.boost.org/trac/boost/ticket/3339 #3688],
- [@https://svn.boost.org/trac/boost/ticket/3698 #3698],
- [@https://svn.boost.org/trac/boost/ticket/3706 #3706],
- [@https://svn.boost.org/trac/boost/ticket/3721 #3721].
- [@https://svn.boost.org/trac/boost/ticket/3729 #3729],
- [@https://svn.boost.org/trac/boost/ticket/3746 #3746],
- [@https://svn.boost.org/trac/boost/ticket/3781 #3781],
- [@https://svn.boost.org/trac/boost/ticket/3840 #3840],
- [@https://svn.boost.org/trac/boost/ticket/3849 #3849],
- [@https://svn.boost.org/trac/boost/ticket/3339 #3339],
- [@https://svn.boost.org/trac/boost/ticket/3419 #3419],
- [@https://svn.boost.org/trac/boost/ticket/3431 #3431],
- [@https://svn.boost.org/trac/boost/ticket/4021 #4021].
- [endsect]
- [section:release_notes_boost_1_40_00 Boost 1.40 Release]
- * Code cleanup in bstree_algorithms.hpp and avl_tree_algorithms.hpp
- * Fixed bug
- [@https://svn.boost.org/trac/boost/ticket/3164 #3164].
- [endsect]
- [section:release_notes_boost_1_39_00 Boost 1.39 Release]
- * Optimized `list::merge` and `slist::merge`
- * `list::sort` and `slist::sort` are now stable.
- * Fixed bugs
- [@https://svn.boost.org/trac/boost/ticket/2689 #2689],
- [@https://svn.boost.org/trac/boost/ticket/2755 #2755],
- [@https://svn.boost.org/trac/boost/ticket/2786 #2786],
- [@https://svn.boost.org/trac/boost/ticket/2807 #2807],
- [@https://svn.boost.org/trac/boost/ticket/2810 #2810],
- [@https://svn.boost.org/trac/boost/ticket/2862 #2862].
- [endsect]
- [section:release_notes_boost_1_38_00 Boost 1.38 Release]
- * New treap-based containers: treap, treap_set, treap_multiset.
- * Corrected compilation bug for Windows-based 64 bit compilers.
- * Corrected exception-safety bugs in container constructors.
- * Updated documentation to show rvalue-references functions instead of emulation functions.
- [endsect]
- [section:release_notes_boost_1_37_00 Boost 1.37 Release]
- * Intrusive now takes advantage of compilers with variadic templates.
- * `clone_from` functions now copy predicates and hash functions of associative containers.
- * Added incremental hashing to unordered containers via `incremental<>` option.
- * Update some function parameters from `iterator` to `const_iterator` in containers
- to keep up with the draft of the next standard.
- * Added an option to specify include files for intrusive configurable assertion macros.
- [endsect]
- [section:release_notes_boost_1_36_00 Boost 1.36 Release]
- * Added `linear<>` and `cache_last<>` options to singly linked lists.
- * Added `optimize_multikey<>` option to unordered container hooks.
- * Optimized unordered containers when `store_hash` option is used in the hook.
- * Implementation changed to be exception agnostic so that it can be used
- in environments without exceptions.
- * Added `container_from_iterator` function to tree-based containers.
- [endsect]
- [endsect]
- [section:references References]
- * SGI's [@http://www.sgi.com/tech/stl/ STL Programmer's Guide].
- [*Boost.Intrusive] is based on STL concepts and interfaces.
- * Dr. Dobb's, September 1, 2005: [@http://www.ddj.com/architect/184402007 ['Implementing Splay Trees in C++] ].
- [*Boost.Intrusive] splay containers code is based on this article.
- * Olaf's original intrusive container library: [@http://freenet-homepage.de/turtle++/intrusive.html ['STL-like intrusive containers] ].
- [endsect]
- [section:acknowledgements Acknowledgements]
- [*Olaf Krzikalla] would like to thank:
- * [*Markus Schaaf] for pointing out the possibility and the advantages of the derivation
- approach.
- * [*Udo Steinbach] for encouragements to present this work for boost, a lot of fixes and
- helpful discussions.
- * [*Jaap Suter] for the initial hint, which eventually lead to the member value_traits.
- [*Ion Gaztanaga] would like to thank:
- * [*Olaf Krzikalla] for the permission to continue his great work.
- * [*Joaquin M. Lopez Munoz] for his thorough review, help, and ideas.
- * [*Cory Nelson], [*Daniel James], [*Dave Harris], [*Guillaume Melquiond],
- [*Henri Bavestrello], [*Hervé Bronnimann], [*Kai Bruning], [*Kevin Sopp],
- [*Paul Rose], [*Pavel Vozelinek], [*Howard Hinnant], [*Olaf Krzikalla],
- [*Samuel Debionne], [*Stjepan Rajko], [*Thorsten Ottosen], [*Tobias Schwinger],
- [*Tom Brinkman] and [*Steven Watanabe]
- for their comments and reviews in the Boost.Intrusive formal review.
- * Thanks to [*Julienne Walker] and [*The EC Team] ([@http://eternallyconfuzzled.com])
- for their great algorithms.
- * Thanks to [*Daniel K. O.] for his AVL tree rebalancing code.
- * Thanks to [*Ralf Mattethat] for his splay tree article and code.
- * Special thanks to [*Steven Watanabe] and [*Tobias Schwinger] for their
- invaluable suggestions and improvements.
- [endsect]
- [include auto_index_helpers.qbk]
- [section:index Indexes]
- [named_index class_name Class Index]
- [named_index typedef_name Typedef Index]
- [named_index function_name Function Index]
- [named_index macro_name Macro Index]
- [/index]
- [endsect]
- [xinclude autodoc.xml]
|