Bimap Reference - 1.68.0 - Boost C++ Libraries

Views are not isolated objects and so cannot be constructed on their own; rather they are an integral part of a bimap . The name of the view class ... Boost C++Libraries ...oneofthemosthighly regardedandexpertlydesignedC++libraryprojectsinthe world.—HerbSutterandAndrei Alexandrescu,C++ CodingStandards ThisisthedocumentationforanoldversionofBoost. Clickheretoviewthispageforthelatestversion. BimapReference View concepts Complexity signature Set typespecification Tags Header "boost/bimap/bimap.hpp"synopsis Class templatebimap Complexity Instantiation types Nested types Constructors, copyandassignment Projection operations Support foruserdefinednames Serialization View concepts bimapinstantiationscomprise twosideviewsandanviewoftherelationspecifiedatcompiletime.Each viewallowsread-writeaccesstotheelementscontainedinadefinitemanner, mathinganSTLcontainersignature. Viewsarenotisolatedobjectsandsocannotbeconstructedontheirown; rathertheyareanintegralpartofabimap. Thenameoftheviewclassimplementationproperisneverdirectlyexposed totheuser,whohasaccessonlytotheassociatedviewtypespecifier. Insertionanddeletionofelementsarealwaysperformedthroughtheappropriate interfaceofanyofthethreeviewsofthebimap; theseoperationsdo,however,haveanimpactonallotherviewsaswell: forinstance,insertionthroughagivenviewmayfailbecausethereexists anotherviewthatforbidstheoperationinordertopreserveitsinvariant (suchasuniquenessofelements).Theglobaloperationsperformedjointly intheanyviewcanbereducedtosixprimitives: copying insertionofanelement hintedinsertion,whereapre-existingelementissuggestedinorder toimprovetheefficiencyoftheoperation deletionofanelement replacementofthevalueofanelement,whichmaytriggertherearrangement ofthiselementinoneormoreviews,ormayforbidthereplacement modificationofanelement,anditssubsequentrearrangement/banning bythevariousviews Thelasttwoprimitivesdeservesomefurtherexplanation:inordertoguarantee theinvariantsassociatedtoeachview(e.g.somedefiniteordering)elements ofabimaparenotmutable. Toovercomethisrestriction,theviewsexposememberfunctionsforupdating andmodifying,whichallowsforthemutationofelementsinacontrolled fashion. Complexity signature Somememberfunctionsofaviewinterfaceareimplementedbyglobalprimitives fromtheabovelist.Thecomplexityoftheseoperationsthusdependson allviewsofagivenbimap, notjustthecurrentlyusedview. Inordertoestablishcomplexityestimates,aviewischaracterisedby itscomplexitysignature,consistingofthefollowingassociatedfunctions onthenumberofelements: c(n): copying i(n): insertion h(n): hintedinsertion d(n): deletion r(n): replacement m(n): modifying Ifthecollectiontypeoftherelationisleft_based orright_based,andwe useanlsubscripttodenote theleftviewandanr fortherightview,thentheinsertionofanelementinsuchacontainer isofcomplexityO(i_l(n)+i_r(n)), wherenisthenumberofelements.Ifthecollectiontypeofrelationis notside-based,thenthereisanadditionaltermtoaddthatiscontributed bythecollectiontypeofrelationview.Usinga todenotetheaboveview,thecomplexityofinsertionwillnowbeO(i_l(n)+i_r(n)+i_a(n)). Toabbreviatethenotation,weadoptthefollowingdefinitions: C(n)=c_l(n)+c_r(n)[+c_a(n)] I(n)=i_l(n)+i_r(n)[+i_a(n)] H(n)=h_l(n)+h_r(n)[+h_a(n)] D(n)=d_l(n)+d_r(n)[+d_a(n)] R(n)=r_l(n)+r_r(n)[+r_a(n)] M(n)=m_l(n)+m_r(n)[+m_a(n)] Set typespecification Settypespecifiersarepassedasinstantiationargumentstobimapandprovidetheinformationneeded toincorporatethecorrespondingviews.Currently,Boost.Bimapprovides thecollectiontypespecifiers.Thesidecollectiontype specifiersdefinetheconstraintsofthetwomapviewsofthebimap.The collectiontypeofrelationspecifierdefinesthe mainsetviewconstraints.Ifleft_based (thedefaultparameter)orright_based isused,thenthecollectiontypeofrelationwillbebasedontheleft orrightcollectiontypecorrespondingly. Sidecollectiontype Collectiontypeofrelation Include set_of set_of_relation boost/bimap/set_of.hpp multiset_of multiset_of_relation boost/bimap/multiset_of.hpp unordered_set_of unordered_set_of_relation boost/bimap/unordered_set_of.hpp unordered_multiset_of unordered_multiset_of_relation boost/bimap/unordered_multiset_of.hpp list_of list_of_relation boost/bimap/list_of.hpp vector_of vector_of_relation boost/bimap/vector_of.hpp unconstrained_set_of unconstrained_set_of_relation boost/bimap/unconstrained_set_of.hpp left_based boost/bimap/bimap.hpp right_based boost/bimap/bimap.hpp Tags Tagsarejustconventionaltypesusedasmnemonicsforthetypesstored inabimap.Boost.Bimap usesthetaggedidiomtolettheuserspecifythistags. Header "boost/bimap/bimap.hpp"synopsis namespaceboost{ namespacebimaps{ template structtagged; //bimaptemplateclass template < classLeftCollectionType,classRightCollectionType, classAdditionalParameter_1=detail::not_specified, classAdditionalParameter_2=detail::not_specified > classbimap-implementationdefined{:publicSetView}- { public: //Metadata typedef-unspecified-left_tag; typedef-unspecified-left_map; typedef-unspecified-right_tag; typedef-unspecified-right_map; //Shortcuts //typedef-side-_map::-type--side-_-type-; typedef-unspecified-info_type; //Mapviews left_mapleft; right_mapright; //Constructors bimap(); template bimap(InputIteratorfirst,InputIteratorlast); bimap(constbimap&); bimap&operator=(constbimap&b); //Projectionofiterators template left_iteratorproject_left(IteratorTypeiter); template left_const_iteratorproject_left(IteratorTypeiter)const; template right_iteratorproject_right(IteratorTypeiter); template right_const_iteratorproject_right(IteratorTypeiter)const; template iteratorproject_up(IteratorTypeiter); template const_iteratorproject_up(IteratorTypeiter)const; //Supportfortags template structmap_by; template map_by::typeby(); template constmap_by::type&by()const; template map_by::iteratorproject(IteratorTypeiter); template map_by::const_iteratorproject(IteratorTypeiter)const }; }//namespacebimap }//namespaceboost Class templatebimap Complexity Instantiation types Nested types Constructors, copyandassignment Projection operations Support foruserdefinednames Serialization ThisisthemaincomponentofBoost.Bimap. Complexity Inthedescriptionsoftheoperationsofbimap, weadopttheschemeoutlinedinthecomplexitysignaturesection. Instantiation types bimapisinstantiated withthefollowingtypes: LeftCollectionTypeandRightCollectionTypearecollectiontypespecifications optionallytagged,oranytypeoptionallytagged,inwhichcasethat sideactsasaset. AdditionalParameter_{1/2}canbeanyorderedsubsetof: CollectionTypeOfRelationspecification Allocator Nested types left_tag,right_tag Tagsforeachsideofthebimap.Iftheuserhasnotspecifiedany tagthetagsdefaulttomember_at::left andmember_at::right. left_key_type,right_key_type Keytypeofeachside.Inabimapleft_key_type isAandright_key_typeisB. Iftherearetags,itisbettertouse:Bimap::map_by::key_type. left_data_type,right_data_type Datatypeofeachside.Inabimapleft_key_typeisBand right_key_typeisA.Iftherearetags,itisbettertouse:Bimap::map_by::data_type. left_value_type,right_value_type Valuetypeusedfortheviews.Iftherearetags,itisbettertouse: Bimap::map_by::value_type. left_iterator,right_iterator left_const_iterator,right_const_iterator Iteratorsoftheviews.Iftherearetags,itisbettertouse:Bimap::map_by::iteratorandBimap::map_by::const_iterator left_map,right_map Mapviewtypeofeachside.Iftherearetags,itisbettertouse: Bimap::map_by::type. Constructors, copyandassignment bimap(); Effects:Constructsanemptybimap. Complexity:Constant. template bimap(InputIteratorfirst,InputIteratorlast); Requires:InputIterator isamodelofInputIteratoroverelementsoftyperelationoratypeconvertible torelation.last isreachablefromfirst. Effects:Constructsanemptybimapandfillsitwiththeelements intherange[first,last).Insertionofeachelementmayor maynotsucceeddependingonacceptancebythecollectiontypesof thebimap. Complexity: O(m*H(m)),wheremisthenumberofelementsin[first,last). bimap(constbimap&x); Effects:Constructsacopyofx, copyingitselementsaswellasitsinternalobjects(keyextractors, comparisonobjects,allocator.) Postconditions:*this== x.Theorderoftheviews ofthebimapispreserved aswell. Complexity:O(x.size()*log(x.size()) +C(x.size())) ~bimap() Effects:Destroysthebimapandalltheelementscontained. Theorderinwhichtheelementsaredestroyedisnotspecified. Complexity:O(n). bimap&operator=(constbimap&x); Effects:Replacestheelementsand internalobjectsofthebimap withcopiesfromx. Postconditions:*this==x.Theorderontheviewsofthe bimapispreserved aswell. Returns:*this. Complexity:O(n+x.size()*log(x.size()) +C(x.size())). Exceptionsafety:Strong,provided thecopyandassignmentoperationsofthetypesofctor_args_listdonotthrow. Projection operations Givenabimapwithviews v1andv2,wesaythananv1-iteratorit1andanv2-iteratorit2are equivalentif: it1== i1.end() ANDit2== i2.end(), ORit1andit2pointtothesameelement. template left_iteratorproject_left(IteratorTypeiter); template left_const_iteratorproject_left(IteratorTypeiter)const; Requires:IteratorType isabimapviewiterator.itisavaliditeratorofsomeviewof *this (i.e.doesnotrefertosomeotherbimap.) Effects:Returnsaleftmapview iteratorequivalenttoit. Complexity:Constant. Exceptionsafety:nothrow. template right_iteratorproject_right(IteratorTypeiter); template right_const_iteratorproject_right(IteratorTypeiter)const; Requires:IteratorType isabimapviewiterator.itisavaliditeratorofsomeviewof *this (i.e.doesnotrefertosomeotherbimap.) Effects:Returnsarightmapview iteratorequivalenttoit. Complexity:Constant. Exceptionsafety:nothrow. template iteratorproject_up(IteratorTypeiter); template const_iteratorproject_up(IteratorTypeiter)const; Requires:IteratorType isabimapviewiterator.itisavaliditeratorofsomeviewof *this (i.e.doesnotrefertosomeotherbimap.) Effects:Returnsacollectionof relationsviewiteratorequivalenttoit. Complexity:Constant. Exceptionsafety:nothrow. Support foruserdefinednames template structmap_by; map_by::typeyieldsthetypeofthemap viewtaggedwithTag. map_by::-type name-isthesameasmap_by::type::-typename-. Requires:Tag isavaliduserdefinednameofthebimap. template map_by::typeby(); template constmap_by::type&by()const; Requires:Tag isavaliduserdefinednameofthebimap. Effects:Returnsareferenceto themapviewtaggedwithTag heldby*this. Complexity:Constant. Exceptionsafety:nothrow. template map_by::iteratorproject(IteratorTypeiter); template map_by::const_iteratorproject(IteratorTypeiter)const Requires:Tag isavaliduserdefinednameofthebimap.IteratorType isabimapviewiterator.itisavaliditeratorofsomeviewof *this (i.e.doesnotrefertosomeotherbimap.) Effects:Returnsareferenceto themapviewtaggedwithTag heldby*this. Complexity:Constant. Exceptionsafety:nothrow. Serialization Abimapcanbearchived andretrievedbymeansofBoost.Serialization.Boost.Bimapdoes notexposeapublicserialisationinterface,asthisisprovidedbyBoost.Serialization itself.BothregularandXMLarchivesaresupported. Eachofthesetspecificationscomprisingagivenbimap contributesitsownpreconditionsaswellasguaranteesontheretrieved containers.Indescribingthese,thefollowingconceptsareused.Atype Tisserializable (resp.XML-serializable)ifanyobjectoftypeT canbesavedtoanoutputarchive(XMLarchive)andlaterretrievedfrom aninputarchive(XMLarchive)associatedtothesamestorage.Ifx'oftypeT isloadedfromtheserializationinformationsavedfromanotherobject x,wesaythatx'isarestoredcopyofx.Given aBinary PredicatePred over(T,T),andobjectsp andqoftypePred,wesaythatq isserialization-compatiblewithp if p(x,y)==q(x',y') foreveryxandyoftypeT andx'andy'beingrestoredcopiesofxandy, respectively. Operation:savingofabimapb toanoutputarchive(XMLarchive)ar. Requires:Valueisserializable (XML-serializable).Additionally,eachoftheviewsofbcanimpose otherrequirements. Exceptionsafety:Strongwithrespect tob.Ifanexception isthrown,armaybeleftinaninconsistentstate. Operation:loadingofabimapm'fromaninputarchive(XML archive)ar. Requires:Valueisserializable (XML-serializable).Additionally,eachoftheviewsofb'canimposeotherrequirements. Exceptionsafety:Basic.Ifanexception isthrown,armaybeleftinaninconsistentstate. Copyright©2006-2012MatiasCapeletto DistributedundertheBoostSoftwareLicense,Version1.0.(Seeaccompanying fileLICENSE_1_0.txtorcopyathttp://www.boost.org/LICENSE_1_0.txt)