CSTL深入理解关联容器multimap和map及其查找操作

　　关联容器map和multimap为了实现接近于logn的查找（二分查找）效率，将一维的数据组织成二维的树型逻辑结构（红黑树做为底层逻辑结构）。由此，为了维护其元素有序结构，其增加元素的成员函数是insert（），而不是序列容器的pushback（）或list、deque容器的pushfront（）。
　　关联容器multimap是一个key与多个value的映射关系。
　　关联容器map是一个key与一个value的映射关系。
　　因为map一一映射的特性，所以有额外的成员函数at（）和重载操作符operator〔〕。
　　classification
　　functionname
　　map
　　multimap
　　constructor
　　map：：map
　　multimap：：multimap
　　destructor
　　map：：map
　　multimap：：multimap
　　memberfunctions
　　at
　　NA
　　begin
　　cbegin
　　cend
　　clear
　　count
　　crbegin
　　crend
　　emplace
　　emplacehint
　　empty
　　end
　　equalrange
　　erase
　　find
　　getallocator
　　insert
　　keycomp
　　lowerbound
　　maxsize
　　operator
　　operator〔〕
　　NA
　　rbegin
　　rend
　　size
　　swap
　　upperbound
　　valuecomp
　　nonmemberoverloads
　　relationaloperators
　　swap
　　1multimap的单值查找查找iteratorfind（constkeytypek）；constiteratorfind（constkeytypek）const；
　　demo：includeiostreamincludemapintmain（）｛std：：multimapchar，intmymm；mymm。insert（std：：makepair（x，10））；mymm。insert（std：：makepair（y，20））；mymm。insert（std：：makepair（z，30））；mymm。insert（std：：makepair（z，40））；std：：multimapchar，int：：iteratoritmymm。find（x）；mymm。erase（it）；mymm。erase（mymm。find（z））；printcontent：std：：coutelementsinmymm：；std：：coutymymm。find（y）second；std：：coutzmymm。find（z）second；return0；｝Output：elementsinmymm：y20z402multimap的多值查找
　　2。1使用成员函数lowerbound（）和upperbound（）iteratorlowerbound（constkeytypek）；constiteratorlowerbound（constkeytypek）const；iteratorupperbound（constkeytypek）；constiteratorupperbound（constkeytypek）const；
　　demo：includeiostreamincludemapintmain（）｛std：：multimapchar，intmymultimap；std：：multimapchar，int：：iteratorit，itlow，itup；mymultimap。insert（std：：makepair（a，10））；mymultimap。insert（std：：makepair（b，121））；mymultimap。insert（std：：makepair（c，1001））；mymultimap。insert（std：：makepair（c，2002））；mymultimap。insert（std：：makepair（d，11011））；mymultimap。insert（std：：makepair（e，44））；itlowmymultimap。lowerbound（c）；itlowpointstobitupmymultimap。upperbound（c）；ituppointstoe（notd）printrange〔itlow，itup）：for（ititlow；it！itup；it）std：：cout（it）。first（it）。second；getchar（）；return0；｝output：c1001c2002
　　2。2使用成员函数equalrange（）templateclassForwardIterator，classTpairForwardIterator，ForwardIteratorequalrange（ForwardIteratorfirst，ForwardIteratorlast，constTval）｛ForwardIteratoritstd：：lowerbound（first，last，val）；returnstd：：makepair（it，std：：upperbound（it，last，val））；｝
　　equalrange（）返回一对起始位置和终点位置的迭代器（pair类型），可以使用一个迭代器指向返回的pair的first和second。Associativecontainerfunctionequalrange（）returnsapaircontainingtheresultsalowerboundandanupperboundoperation。includeiostreamincludemapintmain（）｛std：：multimapchar，intmymm；mymm。insert（std：：makepair（x，50））；mymm。insert（std：：makepair（y，100））；mymm。insert（std：：makepair（y，150））；mymm。insert（std：：makepair（y，200））；mymm。insert（std：：makepair（z，250））；mymm。insert（std：：makepair（z，300））；for（charcx；cz；c）｛std：：coutTherearemymm。count（c）elementswithkeyc：；std：：multimapchar，int：：iteratorit；for（itmymm。equalrange（c）。first；it！mymm。equalrange（c）。second；it）std：：cout（it）。second；std：：cout；｝getchar（）；return0；｝Output：Thereare1elementswithkeyx：50Thereare3elementswithkeyy：100150200Thereare2elementswithkeyz：250300
　　另一种写法：includeiostreamincludemapintmain（）｛std：：multimapchar，intmymm；mymm。insert（std：：pairchar，int（a，10））；mymm。insert（std：：pairchar，int（b，20））；mymm。insert（std：：pairchar，int（b，30））；mymm。insert（std：：pairchar，int（b，40））；mymm。insert（std：：pairchar，int（c，50））；mymm。insert（std：：pairchar，int（c，60））；mymm。insert（std：：pairchar，int（d，60））；std：：coutmymmcontains：；for（charcha；chd；ch）｛std：：pairstd：：multimapchar，int：：iterator，std：：multimapchar，int：：iteratorret；retmymm。equalrange（ch）；std：：coutch；for（std：：multimapchar，int：：iteratoritret。first；it！ret。second；it）std：：coutitsecond；std：：cout；｝getchar（）；return0；｝output：mymmcontains：a10b203040c5060d603std：：map：：findcountiteratorfind（constkeytypek）；constiteratorfind（constkeytypek）const；sizetypecount（constkeytypek）const；
　　demo：includeiostreamincludemapintmain（）｛std：：mapchar，intmymap；std：：mapchar，int：：iteratorit；mymap〔a〕50；mymap〔b〕100；mymap〔c〕150；mymap〔d〕200；itmymap。find（b）；if（it！mymap。end（））mymap。erase（it）；printcontent：std：：coutelementsinmymap：；std：：coutamymap。find（a）second；std：：coutcmymap。find（c）second；std：：coutdmymap。find（d）second；if（mymap。count（e）0）std：：coutemymap。find（e）second；elsestd：：coutenotexist！；getchar（）；return0；｝output：elementsinmymap：a50c150d200enotexist！4std：：map：：equalrangepairconstiterator，constiteratorequalrange（constkeytypek）const；pairiterator，iteratorequalrange（constkeytypek）；
　　demo：includeiostreamincludemapintmain（）｛std：：mapchar，intmymap；mymap〔a〕10；mymap〔b〕20；mymap〔c〕30；std：：pairstd：：mapchar，int：：iterator，std：：mapchar，int：：iteratorret；retmymap。equalrange（b）；std：：coutlowerboundpointsto：；std：：coutret。firstfirstret。firstsecond；std：：coutupperboundpointsto：；std：：coutret。secondfirstret。secondsecond；return0；｝output：lowerboundpointsto：b20upperboundpointsto：c305std：：map：：lowerboundupperbounditeratorlowerbound（constkeytypek）；constiteratorlowerbound（constkeytypek）const；iteratorupperbound（constkeytypek）；constiteratorupperbound（constkeytypek）const；
　　demo：includeiostreamincludemapintmain（）｛std：：mapchar，intmymap；std：：mapchar，int：：iteratoritlow，itup；mymap〔a〕20；mymap〔b〕40；mymap〔c〕60；mymap〔d〕80；mymap〔e〕100；itlowmymap。lowerbound（b）；itlowpointstobitupmymap。upperbound（d）；ituppointstoe（notd！）mymap。erase（itlow，itup）；erases〔itlow，itup）printcontent：for（std：：mapchar，int：：iteratoritmymap。begin（）；it！mymap。end（）；it）std：：coutitfirstitsecond；return0；｝output：a20e1006std：：map：：at（C11）
　　成员函数at有边界检查，当然也有性能损耗。mappedtypeat（constkeytypek）；constmappedtypeat（constkeytypek）const；
　　demo：includeiostreamincludestringincludemapintmain（）｛std：：mapstd：：string，intmymap｛｛alpha，0｝，｛beta，0｝，｛gamma，0｝｝；mymap。at（alpha）10；mymap。at（beta）20；mymap。at（gamma）30；for（autox：mymap）｛std：：coutx。first：x。second；｝std：：coutmymap。at（alpha）；std：：coutmymap。at（empty）；std：：coutmymap。at（alpha）；return0；｝output：alpha：10beta：20gamma：3010terminatecalledafterthrowinganinstanceofstd：：outofrangewhat（）：map：：at7std：：map：：operator〔〕
　　重载操作符operator〔〕没有边界检查，当然也就避免了性能损耗。mappedtypeoperator〔〕（constkeytypek）；
　　demo：includeiostreamincludestringincludemapintmain（）｛std：：mapstd：：string，intmymap｛｛alpha，0｝，｛beta，0｝，｛gamma，0｝｝；mymap〔alpha〕10；mymap〔beta〕20；mymap〔gamma〕30；for（autox：mymap）｛std：：coutx。first：x。second；｝std：：coutmymap〔alpha〕；std：：coutmymap〔empty〕；0return0；｝output：alpha：10beta：20gamma：30100
　　ref
　　http：www。cplusplus。comreferencemapmultimapcount
　　http：www。cplusplus。comreferencemapmultimapequalrange