Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
206 kB · 5905 lines
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157415841594160416141624163416441654166416741684169417041714172417341744175417641774178417941804181418241834184418541864187418841894190419141924193419441954196419741984199420042014202420342044205420642074208420942104211421242134214421542164217421842194220422142224223422442254226422742284229423042314232423342344235423642374238423942404241424242434244424542464247424842494250425142524253425442554256425742584259426042614262426342644265426642674268426942704271427242734274427542764277427842794280428142824283428442854286428742884289429042914292429342944295429642974298429943004301430243034304430543064307430843094310431143124313431443154316431743184319432043214322432343244325432643274328432943304331433243334334433543364337433843394340434143424343434443454346434743484349435043514352435343544355435643574358435943604361436243634364436543664367436843694370437143724373437443754376437743784379438043814382438343844385438643874388438943904391439243934394439543964397439843994400440144024403440444054406440744084409441044114412441344144415441644174418441944204421442244234424442544264427442844294430443144324433443444354436443744384439444044414442444344444445444644474448444944504451445244534454445544564457445844594460446144624463446444654466446744684469447044714472447344744475447644774478447944804481448244834484448544864487448844894490449144924493449444954496449744984499450045014502450345044505450645074508450945104511451245134514451545164517451845194520452145224523452445254526452745284529453045314532453345344535453645374538453945404541454245434544454545464547454845494550455145524553455445554556455745584559456045614562456345644565456645674568456945704571457245734574457545764577457845794580458145824583458445854586458745884589459045914592459345944595459645974598459946004601460246034604460546064607460846094610461146124613461446154616461746184619462046214622462346244625462646274628462946304631463246334634463546364637463846394640464146424643464446454646464746484649465046514652465346544655465646574658465946604661466246634664466546664667466846694670467146724673467446754676467746784679468046814682468346844685468646874688468946904691469246934694469546964697469846994700470147024703470447054706470747084709471047114712471347144715471647174718471947204721472247234724472547264727472847294730473147324733473447354736473747384739474047414742474347444745474647474748474947504751475247534754475547564757475847594760476147624763476447654766476747684769477047714772477347744775477647774778477947804781478247834784478547864787478847894790479147924793479447954796479747984799480048014802480348044805480648074808480948104811481248134814481548164817481848194820482148224823482448254826482748284829483048314832483348344835483648374838483948404841484248434844484548464847484848494850485148524853485448554856485748584859486048614862486348644865486648674868486948704871487248734874487548764877487848794880488148824883488448854886488748884889489048914892489348944895489648974898489949004901490249034904490549064907490849094910491149124913491449154916491749184919492049214922492349244925492649274928492949304931493249334934493549364937493849394940494149424943494449454946494749484949495049514952495349544955495649574958495949604961496249634964496549664967496849694970497149724973497449754976497749784979498049814982498349844985498649874988498949904991499249934994499549964997499849995000500150025003500450055006500750085009501050115012501350145015501650175018501950205021502250235024502550265027502850295030503150325033503450355036503750385039504050415042504350445045504650475048504950505051505250535054505550565057505850595060506150625063506450655066506750685069507050715072507350745075507650775078507950805081508250835084508550865087508850895090509150925093509450955096509750985099510051015102510351045105510651075108510951105111511251135114511551165117511851195120512151225123512451255126512751285129513051315132513351345135513651375138513951405141514251435144514551465147514851495150515151525153515451555156515751585159516051615162516351645165516651675168516951705171517251735174517551765177517851795180518151825183518451855186518751885189519051915192519351945195519651975198519952005201520252035204520552065207520852095210521152125213521452155216521752185219522052215222522352245225522652275228522952305231523252335234523552365237523852395240524152425243524452455246524752485249525052515252525352545255525652575258525952605261526252635264526552665267526852695270527152725273527452755276527752785279528052815282528352845285528652875288528952905291529252935294529552965297529852995300530153025303530453055306530753085309531053115312531353145315531653175318531953205321532253235324532553265327532853295330533153325333533453355336533753385339534053415342534353445345534653475348534953505351535253535354535553565357535853595360536153625363536453655366536753685369537053715372537353745375537653775378537953805381538253835384538553865387538853895390539153925393539453955396539753985399540054015402540354045405540654075408540954105411541254135414541554165417541854195420542154225423542454255426542754285429543054315432543354345435543654375438543954405441544254435444544554465447544854495450545154525453545454555456545754585459546054615462546354645465546654675468546954705471547254735474547554765477547854795480548154825483548454855486548754885489549054915492549354945495549654975498549955005501550255035504550555065507550855095510551155125513551455155516551755185519552055215522552355245525552655275528552955305531553255335534553555365537553855395540554155425543554455455546554755485549555055515552555355545555555655575558555955605561556255635564556555665567556855695570557155725573557455755576557755785579558055815582558355845585558655875588558955905591559255935594559555965597559855995600560156025603560456055606560756085609561056115612561356145615561656175618561956205621562256235624562556265627562856295630563156325633563456355636563756385639564056415642564356445645564656475648564956505651565256535654565556565657565856595660566156625663566456655666566756685669567056715672567356745675567656775678567956805681568256835684568556865687568856895690569156925693569456955696569756985699570057015702570357045705570657075708570957105711571257135714571557165717571857195720572157225723572457255726572757285729573057315732573357345735573657375738573957405741574257435744574557465747574857495750575157525753575457555756575757585759576057615762576357645765576657675768576957705771577257735774577557765777577857795780578157825783578457855786578757885789579057915792579357945795579657975798579958005801580258035804580558065807580858095810581158125813581458155816581758185819582058215822582358245825582658275828582958305831583258335834583558365837583858395840584158425843584458455846584758485849585058515852585358545855585658575858585958605861586258635864586558665867586858695870587158725873587458755876587758785879588058815882588358845885588658875888588958905891589258935894589558965897589858995900590159025903590459055906// -*- C++ -*-//===-------------------------- algorithm ---------------------------------===////// The LLVM Compiler Infrastructure//// This file is dual licensed under the MIT and the University of Illinois Open// Source Licenses. See LICENSE.TXT for details.////===----------------------------------------------------------------------===//#ifndef _LIBCPP_ALGORITHM#define _LIBCPP_ALGORITHM/* algorithm synopsis#include <initializer_list>namespace std{template <class InputIterator, class Predicate> bool all_of(InputIterator first, InputIterator last, Predicate pred);template <class InputIterator, class Predicate> bool any_of(InputIterator first, InputIterator last, Predicate pred);template <class InputIterator, class Predicate> bool none_of(InputIterator first, InputIterator last, Predicate pred);template <class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f);template<class InputIterator, class Size, class Function> InputIterator for_each_n(InputIterator first, Size n, Function f); // C++17template <class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value);template <class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred);template<class InputIterator, class Predicate> InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred);template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);template <class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value);template <class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred);template <class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);template <class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); // **C++14**template <class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);template <class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); // **C++14**template <class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2);template <class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); // **C++14**template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); // **C++14**template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); // **C++14**template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred);template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); // **C++14**template <class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2);template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred);template <class ForwardIterator, class Size, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value);template <class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred);template <class InputIterator, class OutputIterator> OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result);template<class InputIterator, class OutputIterator, class Predicate> OutputIterator copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);template<class InputIterator, class Size, class OutputIterator> OutputIterator copy_n(InputIterator first, Size n, OutputIterator result);template <class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result);template <class ForwardIterator1, class ForwardIterator2> ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2);template <class ForwardIterator1, class ForwardIterator2> void iter_swap(ForwardIterator1 a, ForwardIterator2 b);template <class InputIterator, class OutputIterator, class UnaryOperation> OutputIterator transform(InputIterator first, InputIterator last, OutputIterator result, UnaryOperation op);template <class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation> OutputIterator transform(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryOperation binary_op);template <class ForwardIterator, class T> void replace(ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);template <class ForwardIterator, class Predicate, class T> void replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value);template <class InputIterator, class OutputIterator, class T> OutputIterator replace_copy(InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value);template <class InputIterator, class OutputIterator, class Predicate, class T> OutputIterator replace_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value);template <class ForwardIterator, class T> void fill(ForwardIterator first, ForwardIterator last, const T& value);template <class OutputIterator, class Size, class T> OutputIterator fill_n(OutputIterator first, Size n, const T& value);template <class ForwardIterator, class Generator> void generate(ForwardIterator first, ForwardIterator last, Generator gen);template <class OutputIterator, class Size, class Generator> OutputIterator generate_n(OutputIterator first, Size n, Generator gen);template <class ForwardIterator, class T> ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class Predicate> ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);template <class InputIterator, class OutputIterator, class T> OutputIterator remove_copy(InputIterator first, InputIterator last, OutputIterator result, const T& value);template <class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);template <class ForwardIterator> ForwardIterator unique(ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate pred);template <class InputIterator, class OutputIterator> OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result);template <class InputIterator, class OutputIterator, class BinaryPredicate> OutputIterator unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate pred);template <class BidirectionalIterator> void reverse(BidirectionalIterator first, BidirectionalIterator last);template <class BidirectionalIterator, class OutputIterator> OutputIterator reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);template <class ForwardIterator> ForwardIterator rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);template <class ForwardIterator, class OutputIterator> OutputIterator rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);template <class RandomAccessIterator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last); // deprecated in C++14, removed in C++17template <class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand); // deprecated in C++14, removed in C++17template<class PopulationIterator, class SampleIterator, class Distance, class UniformRandomBitGenerator> SampleIterator sample(PopulationIterator first, PopulationIterator last, SampleIterator out, Distance n, UniformRandomBitGenerator&& g); // C++17template<class RandomAccessIterator, class UniformRandomNumberGenerator> void shuffle(RandomAccessIterator first, RandomAccessIterator last, UniformRandomNumberGenerator&& g);template <class InputIterator, class Predicate> bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);template <class ForwardIterator, class Predicate> ForwardIterator partition(ForwardIterator first, ForwardIterator last, Predicate pred);template <class InputIterator, class OutputIterator1, class OutputIterator2, class Predicate> pair<OutputIterator1, OutputIterator2> partition_copy(InputIterator first, InputIterator last, OutputIterator1 out_true, OutputIterator2 out_false, Predicate pred);template <class ForwardIterator, class Predicate> ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);template<class ForwardIterator, class Predicate> ForwardIterator partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);template <class ForwardIterator> bool is_sorted(ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);template<class ForwardIterator> ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);template <class ForwardIterator, class Compare> ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp);template <class RandomAccessIterator> void sort(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> void stable_sort(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);template <class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last);template <class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, Compare comp);template <class RandomAccessIterator> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);template <class ForwardIterator, class T> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);template <class ForwardIterator, class T> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare> ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);template <class ForwardIterator, class T> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare> pair<ForwardIterator, ForwardIterator> equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);template <class ForwardIterator, class T> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value);template <class ForwardIterator, class T, class Compare> bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);template <class BidirectionalIterator> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);template <class BidirectionalIterator, class Compare> void inplace_merge(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);template <class InputIterator1, class InputIterator2> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);template <class InputIterator1, class InputIterator2, class Compare> bool includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_union(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_intersection(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);template <class InputIterator1, class InputIterator2, class OutputIterator> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);template <class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator set_symmetric_difference(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp);template <class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> void pop_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first, RandomAccessIterator last);template <class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);template <class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessiterator last);template <class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessiterator last, Compare comp);template <class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessiterator last);template <class RandomAccessIterator, class Compare> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessiterator last, Compare comp);template <class ForwardIterator> ForwardIterator min_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14template <class ForwardIterator, class Compare> ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14template <class T> const T& min(const T& a, const T& b); // constexpr in C++14template <class T, class Compare> const T& min(const T& a, const T& b, Compare comp); // constexpr in C++14template<class T> T min(initializer_list<T> t); // constexpr in C++14template<class T, class Compare> T min(initializer_list<T> t, Compare comp); // constexpr in C++14template<class T> constexpr const T& clamp( const T& v, const T& lo, const T& hi ); // C++17template<class T, class Compare> constexpr const T& clamp( const T& v, const T& lo, const T& hi, Compare comp ); // C++17template <class ForwardIterator> ForwardIterator max_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14template <class ForwardIterator, class Compare> ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14template <class T> const T& max(const T& a, const T& b); // constexpr in C++14template <class T, class Compare> const T& max(const T& a, const T& b, Compare comp); // constexpr in C++14template<class T> T max(initializer_list<T> t); // constexpr in C++14template<class T, class Compare> T max(initializer_list<T> t, Compare comp); // constexpr in C++14template<class ForwardIterator> pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last); // constexpr in C++14template<class ForwardIterator, class Compare> pair<ForwardIterator, ForwardIterator> minmax_element(ForwardIterator first, ForwardIterator last, Compare comp); // constexpr in C++14template<class T> pair<const T&, const T&> minmax(const T& a, const T& b); // constexpr in C++14template<class T, class Compare> pair<const T&, const T&> minmax(const T& a, const T& b, Compare comp); // constexpr in C++14template<class T> pair<T, T> minmax(initializer_list<T> t); // constexpr in C++14template<class T, class Compare> pair<T, T> minmax(initializer_list<T> t, Compare comp); // constexpr in C++14template <class InputIterator1, class InputIterator2> bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2);template <class InputIterator1, class InputIterator2, class Compare> bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, Compare comp);template <class BidirectionalIterator> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);template <class BidirectionalIterator, class Compare> bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);template <class BidirectionalIterator> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);template <class BidirectionalIterator, class Compare> bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);} // std*/#include <__config>#include <initializer_list>#include <type_traits>#include <cstring>#include <utility> // needed to provide swap_ranges.#include <memory>#include <iterator>#include <cstddef>#if defined(__IBMCPP__)#include "support/ibm/support.h"#endif#if defined(_LIBCPP_COMPILER_MSVC)#include <intrin.h>#endif#include <__debug>#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)#pragma GCC system_header#endif_LIBCPP_PUSH_MACROS#include <__undef_macros>_LIBCPP_BEGIN_NAMESPACE_STD// I'd like to replace these with _VSTD::equal_to<void>, but can't because:// * That only works with C++14 and later, and// * We haven't included <functional> here.template <class _T1, class _T2 = _T1>struct __equal_to{ _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;} _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) const {return __x == __y;} _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T1& __y) const {return __x == __y;} _LIBCPP_INLINE_VISIBILITY bool operator()(const _T2& __x, const _T2& __y) const {return __x == __y;}};template <class _T1>struct __equal_to<_T1, _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}};template <class _T1>struct __equal_to<const _T1, _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}};template <class _T1>struct __equal_to<_T1, const _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x == __y;}};template <class _T1, class _T2 = _T1>struct __less{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T2& __y) const {return __x < __y;} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T1& __y) const {return __x < __y;} _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T2& __x, const _T2& __y) const {return __x < __y;}};template <class _T1>struct __less<_T1, _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}};template <class _T1>struct __less<const _T1, _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}};template <class _T1>struct __less<_T1, const _T1>{ _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11 bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}};template <class _Predicate>class __negate{private: _Predicate __p_;public: _LIBCPP_INLINE_VISIBILITY __negate() {} _LIBCPP_INLINE_VISIBILITY explicit __negate(_Predicate __p) : __p_(__p) {} template <class _T1> _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x) {return !__p_(__x);} template <class _T1, class _T2> _LIBCPP_INLINE_VISIBILITY bool operator()(const _T1& __x, const _T2& __y) {return !__p_(__x, __y);}};#ifdef _LIBCPP_DEBUGtemplate <class _Compare>struct __debug_less{ _Compare __comp_; __debug_less(_Compare& __c) : __comp_(__c) {} template <class _Tp, class _Up> bool operator()(const _Tp& __x, const _Up& __y) { bool __r = __comp_(__x, __y); if (__r) __do_compare_assert(0, __y, __x); return __r; } template <class _LHS, class _RHS> inline _LIBCPP_INLINE_VISIBILITY decltype((void)_VSTD::declval<_Compare&>()( _VSTD::declval<_LHS const&>(), _VSTD::declval<_RHS const&>())) __do_compare_assert(int, _LHS const& __l, _RHS const& __r) { _LIBCPP_ASSERT(!__comp_(__l, __r), "Comparator does not induce a strict weak ordering"); } template <class _LHS, class _RHS> inline _LIBCPP_INLINE_VISIBILITY void __do_compare_assert(long, _LHS const&, _RHS const&) {}};#endif // _LIBCPP_DEBUG// Precondition: __x != 0inline _LIBCPP_INLINE_VISIBILITYunsigned __ctz(unsigned __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned>(__builtin_ctz(__x));#else static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); static_assert(sizeof(unsigned long) == 4, ""); unsigned long where; // Search from LSB to MSB for first set bit. // Returns zero if no set bit is found. if (_BitScanForward(&where, mask)) return where; return 32;#endif}inline _LIBCPP_INLINE_VISIBILITYunsigned long __ctz(unsigned long __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned long>(__builtin_ctzl(__x));#else static_assert(sizeof(unsigned long) == sizeof(unsigned), ""); return __ctz(static_cast<unsigned>(__x));#endif}inline _LIBCPP_INLINE_VISIBILITYunsigned long long __ctz(unsigned long long __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned long long>(__builtin_ctzll(__x));#else unsigned long where;// Search from LSB to MSB for first set bit.// Returns zero if no set bit is found.#if defined(_LIBCPP_HAS_BITSCAN64) (defined(_M_AMD64) || defined(__x86_64__)) if (_BitScanForward64(&where, mask)) return static_cast<int>(where);#else // Win32 doesn't have _BitScanForward64 so emulate it with two 32 bit calls. // Scan the Low Word. if (_BitScanForward(&where, static_cast<unsigned long>(mask))) return where; // Scan the High Word. if (_BitScanForward(&where, static_cast<unsigned long>(mask >> 32))) return where + 32; // Create a bit offset from the LSB.#endif return 64;#endif // _LIBCPP_COMPILER_MSVC}// Precondition: __x != 0inline _LIBCPP_INLINE_VISIBILITYunsigned __clz(unsigned __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned>(__builtin_clz(__x));#else static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); static_assert(sizeof(unsigned long) == 4, ""); unsigned long where; // Search from LSB to MSB for first set bit. // Returns zero if no set bit is found. if (_BitScanReverse(&where, mask)) return 31 - where; return 32; // Undefined Behavior.#endif}inline _LIBCPP_INLINE_VISIBILITYunsigned long __clz(unsigned long __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned long>(__builtin_clzl (__x));#else static_assert(sizeof(unsigned) == sizeof(unsigned long), ""); return __clz(static_cast<unsigned>(__x));#endif}inline _LIBCPP_INLINE_VISIBILITYunsigned long long __clz(unsigned long long __x) {#ifndef _LIBCPP_COMPILER_MSVC return static_cast<unsigned long long>(__builtin_clzll(__x));#else unsigned long where;// BitScanReverse scans from MSB to LSB for first set bit.// Returns 0 if no set bit is found.#if defined(_LIBCPP_HAS_BITSCAN64) if (_BitScanReverse64(&where, mask)) return static_cast<int>(63 - where);#else // Scan the high 32 bits. if (_BitScanReverse(&where, static_cast<unsigned long>(mask >> 32))) return 63 - (where + 32); // Create a bit offset from the MSB. // Scan the low 32 bits. if (_BitScanReverse(&where, static_cast<unsigned long>(mask))) return 63 - where;#endif return 64; // Undefined Behavior.#endif // _LIBCPP_COMPILER_MSVC}inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned __x) {#ifndef _LIBCPP_COMPILER_MSVC return __builtin_popcount (__x);#else static_assert(sizeof(unsigned) == 4, ""); return __popcnt(__x);#endif}inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long __x) {#ifndef _LIBCPP_COMPILER_MSVC return __builtin_popcountl (__x);#else static_assert(sizeof(unsigned long) == 4, ""); return __popcnt(__x);#endif}inline _LIBCPP_INLINE_VISIBILITY int __pop_count(unsigned long long __x) {#ifndef _LIBCPP_COMPILER_MSVC return __builtin_popcountll(__x);#else static_assert(sizeof(unsigned long long) == 8, ""); return __popcnt64(__x);#endif}// all_oftemplate <class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITYboolall_of(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (!__pred(*__first)) return false; return true;}// any_oftemplate <class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITYboolany_of(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (__pred(*__first)) return true; return false;}// none_oftemplate <class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITYboolnone_of(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (__pred(*__first)) return false; return true;}// for_eachtemplate <class _InputIterator, class _Function>inline _LIBCPP_INLINE_VISIBILITY_Functionfor_each(_InputIterator __first, _InputIterator __last, _Function __f){ for (; __first != __last; ++__first) __f(*__first); return __f;}#if _LIBCPP_STD_VER > 14// for_each_ntemplate <class _InputIterator, class _Size, class _Function>inline _LIBCPP_INLINE_VISIBILITY_InputIteratorfor_each_n(_InputIterator __first, _Size __orig_n, _Function __f){ typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; while (__n > 0) { __f(*__first); ++__first; --__n; } return __first;}#endif// findtemplate <class _InputIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_InputIteratorfind(_InputIterator __first, _InputIterator __last, const _Tp& __value_){ for (; __first != __last; ++__first) if (*__first == __value_) break; return __first;}// find_iftemplate <class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_InputIteratorfind_if(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (__pred(*__first)) break; return __first;}// find_if_nottemplate<class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_InputIteratorfind_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (!__pred(*__first)) break; return __first;}// find_endtemplate <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>_ForwardIterator1__find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag){ // modeled after search algorithm _ForwardIterator1 __r = __last1; // __last1 is the "default" answer if (__first2 == __last2) return __r; while (true) { while (true) { if (__first1 == __last1) // if source exhausted return last correct answer return __r; // (or __last1 if never found) if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here _ForwardIterator1 __m1 = __first1; _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) { // Pattern exhaused, record answer and search for another one __r = __first1; ++__first1; break; } if (++__m1 == __last1) // Source exhausted, return last answer return __r; if (!__pred(*__m1, *__m2)) // mismatch, restart with a new __first { ++__first1; break; } // else there is a match, check next elements } }}template <class _BinaryPredicate, class _BidirectionalIterator1, class _BidirectionalIterator2>_BidirectionalIterator1__find_end(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BinaryPredicate __pred, bidirectional_iterator_tag, bidirectional_iterator_tag){ // modeled after search algorithm (in reverse) if (__first2 == __last2) return __last1; // Everything matches an empty sequence _BidirectionalIterator1 __l1 = __last1; _BidirectionalIterator2 __l2 = __last2; --__l2; while (true) { // Find last element in sequence 1 that matchs *(__last2-1), with a mininum of loop checks while (true) { if (__first1 == __l1) // return __last1 if no element matches *__first2 return __last1; if (__pred(*--__l1, *__l2)) break; } // *__l1 matches *__l2, now match elements before here _BidirectionalIterator1 __m1 = __l1; _BidirectionalIterator2 __m2 = __l2; while (true) { if (__m2 == __first2) // If pattern exhausted, __m1 is the answer (works for 1 element pattern) return __m1; if (__m1 == __first1) // Otherwise if source exhaused, pattern not found return __last1; if (!__pred(*--__m1, *--__m2)) // if there is a mismatch, restart with a new __l1 { break; } // else there is a match, check next elements } }}template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>_LIBCPP_CONSTEXPR_AFTER_CXX11 _RandomAccessIterator1__find_end(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag){ // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern typename iterator_traits<_RandomAccessIterator2>::difference_type __len2 = __last2 - __first2; if (__len2 == 0) return __last1; typename iterator_traits<_RandomAccessIterator1>::difference_type __len1 = __last1 - __first1; if (__len1 < __len2) return __last1; const _RandomAccessIterator1 __s = __first1 + (__len2 - 1); // End of pattern match can't go before here _RandomAccessIterator1 __l1 = __last1; _RandomAccessIterator2 __l2 = __last2; --__l2; while (true) { while (true) { if (__s == __l1) return __last1; if (__pred(*--__l1, *__l2)) break; } _RandomAccessIterator1 __m1 = __l1; _RandomAccessIterator2 __m2 = __l2; while (true) { if (__m2 == __first2) return __m1; // no need to check range on __m1 because __s guarantees we have enough source if (!__pred(*--__m1, *--__m2)) { break; } } }}template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred){ return _VSTD::__find_end<typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category());}template <class _ForwardIterator1, class _ForwardIterator2>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2){ typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::find_end(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());}// find_first_oftemplate <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>_LIBCPP_CONSTEXPR_AFTER_CXX11 _ForwardIterator1__find_first_of_ce(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred){ for (; __first1 != __last1; ++__first1) for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) if (__pred(*__first1, *__j)) return __first1; return __last1;}template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred){ return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __pred);}template <class _ForwardIterator1, class _ForwardIterator2>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1find_first_of(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2){ typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::__find_first_of_ce(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());}// adjacent_findtemplate <class _ForwardIterator, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratoradjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred){ if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { if (__pred(*__first, *__i)) return __first; __first = __i; } } return __last;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratoradjacent_find(_ForwardIterator __first, _ForwardIterator __last){ typedef typename iterator_traits<_ForwardIterator>::value_type __v; return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());}// counttemplate <class _InputIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYtypename iterator_traits<_InputIterator>::difference_typecount(_InputIterator __first, _InputIterator __last, const _Tp& __value_){ typename iterator_traits<_InputIterator>::difference_type __r(0); for (; __first != __last; ++__first) if (*__first == __value_) ++__r; return __r;}// count_iftemplate <class _InputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITYtypename iterator_traits<_InputIterator>::difference_typecount_if(_InputIterator __first, _InputIterator __last, _Predicate __pred){ typename iterator_traits<_InputIterator>::difference_type __r(0); for (; __first != __last; ++__first) if (__pred(*__first)) ++__r; return __r;}// mismatchtemplate <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITYpair<_InputIterator1, _InputIterator2>mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred){ for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2);}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYpair<_InputIterator1, _InputIterator2>mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2){ typedef typename iterator_traits<_InputIterator1>::value_type __v1; typedef typename iterator_traits<_InputIterator2>::value_type __v2; return _VSTD::mismatch(__first1, __last1, __first2, __equal_to<__v1, __v2>());}#if _LIBCPP_STD_VER > 11template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITYpair<_InputIterator1, _InputIterator2>mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred){ for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) break; return pair<_InputIterator1, _InputIterator2>(__first1, __first2);}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYpair<_InputIterator1, _InputIterator2>mismatch(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2){ typedef typename iterator_traits<_InputIterator1>::value_type __v1; typedef typename iterator_traits<_InputIterator2>::value_type __v2; return _VSTD::mismatch(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());}#endif// equaltemplate <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITYboolequal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _BinaryPredicate __pred){ for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return true;}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYboolequal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2){ typedef typename iterator_traits<_InputIterator1>::value_type __v1; typedef typename iterator_traits<_InputIterator2>::value_type __v2; return _VSTD::equal(__first1, __last1, __first2, __equal_to<__v1, __v2>());}#if _LIBCPP_STD_VER > 11template <class _BinaryPredicate, class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYbool__equal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred, input_iterator_tag, input_iterator_tag ){ for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) return false; return __first1 == __last1 && __first2 == __last2;}template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>inline _LIBCPP_INLINE_VISIBILITYbool__equal(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag ){ if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; return _VSTD::equal<_RandomAccessIterator1, _RandomAccessIterator2, typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __pred );}template <class _InputIterator1, class _InputIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITYboolequal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _BinaryPredicate __pred ){ return _VSTD::__equal<typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __last2, __pred, typename iterator_traits<_InputIterator1>::iterator_category(), typename iterator_traits<_InputIterator2>::iterator_category());}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYboolequal(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2){ typedef typename iterator_traits<_InputIterator1>::value_type __v1; typedef typename iterator_traits<_InputIterator2>::value_type __v2; return _VSTD::__equal(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), typename iterator_traits<_InputIterator1>::iterator_category(), typename iterator_traits<_InputIterator2>::iterator_category());}#endif// is_permutationtemplate<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>boolis_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _BinaryPredicate __pred){ // shorten sequences as much as possible by lopping of any equal parts for (; __first1 != __last1; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return true;__not_done: // __first1 != __last1 && *__first1 != *__first2 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; _D1 __l1 = _VSTD::distance(__first1, __last1); if (__l1 == _D1(1)) return false; _ForwardIterator2 __last2 = _VSTD::next(__first2, __l1); // For each element in [f1, l1) see if there are the same number of // equal elements in [f2, l2) for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? for (_ForwardIterator1 __j = __first1; __j != __i; ++__j) if (__pred(*__j, *__i)) goto __next_iter; { // Count number of *__i in [f2, l2) _D1 __c2 = 0; for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) if (__pred(*__i, *__j)) ++__c2; if (__c2 == 0) return false; // Count number of *__i in [__i, l1) (we can start with 1) _D1 __c1 = 1; for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) if (__pred(*__i, *__j)) ++__c1; if (__c1 != __c2) return false; }__next_iter:; } return true;}template<class _ForwardIterator1, class _ForwardIterator2>inline _LIBCPP_INLINE_VISIBILITYboolis_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2){ typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::is_permutation(__first1, __last1, __first2, __equal_to<__v1, __v2>());}#if _LIBCPP_STD_VER > 11template<class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>bool__is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag ){ // shorten sequences as much as possible by lopping of any equal parts for (; __first1 != __last1 && __first2 != __last2; ++__first1, (void) ++__first2) if (!__pred(*__first1, *__first2)) goto __not_done; return __first1 == __last1 && __first2 == __last2;__not_done: // __first1 != __last1 && __first2 != __last2 && *__first1 != *__first2 typedef typename iterator_traits<_ForwardIterator1>::difference_type _D1; _D1 __l1 = _VSTD::distance(__first1, __last1); typedef typename iterator_traits<_ForwardIterator2>::difference_type _D2; _D2 __l2 = _VSTD::distance(__first2, __last2); if (__l1 != __l2) return false; // For each element in [f1, l1) see if there are the same number of // equal elements in [f2, l2) for (_ForwardIterator1 __i = __first1; __i != __last1; ++__i) { // Have we already counted the number of *__i in [f1, l1)? for (_ForwardIterator1 __j = __first1; __j != __i; ++__j) if (__pred(*__j, *__i)) goto __next_iter; { // Count number of *__i in [f2, l2) _D1 __c2 = 0; for (_ForwardIterator2 __j = __first2; __j != __last2; ++__j) if (__pred(*__i, *__j)) ++__c2; if (__c2 == 0) return false; // Count number of *__i in [__i, l1) (we can start with 1) _D1 __c1 = 1; for (_ForwardIterator1 __j = _VSTD::next(__i); __j != __last1; ++__j) if (__pred(*__i, *__j)) ++__c1; if (__c1 != __c2) return false; }__next_iter:; } return true;}template<class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>bool__is_permutation(_RandomAccessIterator1 __first1, _RandomAccessIterator2 __last1, _RandomAccessIterator1 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag ){ if ( _VSTD::distance(__first1, __last1) != _VSTD::distance(__first2, __last2)) return false; return _VSTD::is_permutation<_RandomAccessIterator1, _RandomAccessIterator2, typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __pred );}template<class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITYboolis_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred ){ return _VSTD::__is_permutation<typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category());}template<class _ForwardIterator1, class _ForwardIterator2>inline _LIBCPP_INLINE_VISIBILITYboolis_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2){ typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::__is_permutation(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>(), typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category());}#endif// searchtemplate <class _BinaryPredicate, class _ForwardIterator1, class _ForwardIterator2>pair<_ForwardIterator1, _ForwardIterator1>__search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred, forward_iterator_tag, forward_iterator_tag){ if (__first2 == __last2) return make_pair(__first1, __first1); // Everything matches an empty sequence while (true) { // Find first element in sequence 1 that matchs *__first2, with a mininum of loop checks while (true) { if (__first1 == __last1) // return __last1 if no element matches *__first2 return make_pair(__last1, __last1); if (__pred(*__first1, *__first2)) break; ++__first1; } // *__first1 matches *__first2, now match elements after here _ForwardIterator1 __m1 = __first1; _ForwardIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) // If pattern exhausted, __first1 is the answer (works for 1 element pattern) return make_pair(__first1, __m1); if (++__m1 == __last1) // Otherwise if source exhaused, pattern not found return make_pair(__last1, __last1); if (!__pred(*__m1, *__m2)) // if there is a mismatch, restart with a new __first1 { ++__first1; break; } // else there is a match, check next elements } }}template <class _BinaryPredicate, class _RandomAccessIterator1, class _RandomAccessIterator2>_LIBCPP_CONSTEXPR_AFTER_CXX11pair<_RandomAccessIterator1, _RandomAccessIterator1>__search(_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1, _RandomAccessIterator2 __first2, _RandomAccessIterator2 __last2, _BinaryPredicate __pred, random_access_iterator_tag, random_access_iterator_tag){ typedef typename iterator_traits<_RandomAccessIterator1>::difference_type _D1; typedef typename iterator_traits<_RandomAccessIterator2>::difference_type _D2; // Take advantage of knowing source and pattern lengths. Stop short when source is smaller than pattern const _D2 __len2 = __last2 - __first2; if (__len2 == 0) return make_pair(__first1, __first1); const _D1 __len1 = __last1 - __first1; if (__len1 < __len2) return make_pair(__last1, __last1); const _RandomAccessIterator1 __s = __last1 - (__len2 - 1); // Start of pattern match can't go beyond here while (true) { while (true) { if (__first1 == __s) return make_pair(__last1, __last1); if (__pred(*__first1, *__first2)) break; ++__first1; } _RandomAccessIterator1 __m1 = __first1; _RandomAccessIterator2 __m2 = __first2; while (true) { if (++__m2 == __last2) return make_pair(__first1, __first1 + __len2); ++__m1; // no need to check range on __m1 because __s guarantees we have enough source if (!__pred(*__m1, *__m2)) { ++__first1; break; } } }}template <class _ForwardIterator1, class _ForwardIterator2, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2, _BinaryPredicate __pred){ return _VSTD::__search<typename add_lvalue_reference<_BinaryPredicate>::type> (__first1, __last1, __first2, __last2, __pred, typename iterator_traits<_ForwardIterator1>::iterator_category(), typename iterator_traits<_ForwardIterator2>::iterator_category()) .first;}template <class _ForwardIterator1, class _ForwardIterator2>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator1search(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2, _ForwardIterator2 __last2){ typedef typename iterator_traits<_ForwardIterator1>::value_type __v1; typedef typename iterator_traits<_ForwardIterator2>::value_type __v2; return _VSTD::search(__first1, __last1, __first2, __last2, __equal_to<__v1, __v2>());}// search_ntemplate <class _BinaryPredicate, class _ForwardIterator, class _Size, class _Tp>_ForwardIterator__search_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred, forward_iterator_tag){ if (__count <= 0) return __first; while (true) { // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { if (__first == __last) // return __last if no element matches __value_ return __last; if (__pred(*__first, __value_)) break; ++__first; } // *__first matches __value_, now match elements after here _ForwardIterator __m = __first; _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) return __first; if (++__m == __last) // Otherwise if source exhaused, pattern not found return __last; if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; break; } // else there is a match, check next elements } }}template <class _BinaryPredicate, class _RandomAccessIterator, class _Size, class _Tp>_RandomAccessIterator__search_n(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred, random_access_iterator_tag){ if (__count <= 0) return __first; _Size __len = static_cast<_Size>(__last - __first); if (__len < __count) return __last; const _RandomAccessIterator __s = __last - (__count - 1); // Start of pattern match can't go beyond here while (true) { // Find first element in sequence that matchs __value_, with a mininum of loop checks while (true) { if (__first >= __s) // return __last if no element matches __value_ return __last; if (__pred(*__first, __value_)) break; ++__first; } // *__first matches __value_, now match elements after here _RandomAccessIterator __m = __first; _Size __c(0); while (true) { if (++__c == __count) // If pattern exhausted, __first is the answer (works for 1 element pattern) return __first; ++__m; // no need to check range on __m because __s guarantees we have enough source if (!__pred(*__m, __value_)) // if there is a mismatch, restart with a new __first { __first = __m; ++__first; break; } // else there is a match, check next elements } }}template <class _ForwardIterator, class _Size, class _Tp, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorsearch_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_, _BinaryPredicate __pred){ return _VSTD::__search_n<typename add_lvalue_reference<_BinaryPredicate>::type> (__first, __last, __convert_to_integral(__count), __value_, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());}template <class _ForwardIterator, class _Size, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorsearch_n(_ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value_){ typedef typename iterator_traits<_ForwardIterator>::value_type __v; return _VSTD::search_n(__first, __last, __convert_to_integral(__count), __value_, __equal_to<__v, _Tp>());}// copytemplate <class _Iter>inline _LIBCPP_INLINE_VISIBILITY_Iter__unwrap_iter(_Iter __i){ return __i;}template <class _Tp>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_trivially_copy_assignable<_Tp>::value, _Tp*>::type__unwrap_iter(move_iterator<_Tp*> __i){ return __i.base();}#if _LIBCPP_DEBUG_LEVEL < 2template <class _Tp>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_trivially_copy_assignable<_Tp>::value, _Tp*>::type__unwrap_iter(__wrap_iter<_Tp*> __i){ return __i.base();}#elsetemplate <class _Tp>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_trivially_copy_assignable<_Tp>::value, __wrap_iter<_Tp*>>::type__unwrap_iter(__wrap_iter<_Tp*> __i){ return __i;}#endif // _LIBCPP_DEBUG_LEVEL < 2template <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIterator__copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ for (; __first != __last; ++__first, (void) ++__result) *__result = *__first; return __result;}template <class _Tp, class _Up>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_same<typename remove_const<_Tp>::type, _Up>::value && is_trivially_copy_assignable<_Up>::value, _Up*>::type__copy(_Tp* __first, _Tp* __last, _Up* __result){ const size_t __n = static_cast<size_t>(__last - __first); if (__n > 0) _VSTD::memmove(__result, __first, __n * sizeof(_Up)); return __result + __n;}template <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorcopy(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ return _VSTD::__copy(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));}// copy_backwardtemplate <class _BidirectionalIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIterator__copy_backward(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result){ while (__first != __last) *--__result = *--__last; return __result;}template <class _Tp, class _Up>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_same<typename remove_const<_Tp>::type, _Up>::value && is_trivially_copy_assignable<_Up>::value, _Up*>::type__copy_backward(_Tp* __first, _Tp* __last, _Up* __result){ const size_t __n = static_cast<size_t>(__last - __first); if (__n > 0) { __result -= __n; _VSTD::memmove(__result, __first, __n * sizeof(_Up)); } return __result;}template <class _BidirectionalIterator1, class _BidirectionalIterator2>inline _LIBCPP_INLINE_VISIBILITY_BidirectionalIterator2copy_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result){ return _VSTD::__copy_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));}// copy_iftemplate<class _InputIterator, class _OutputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorcopy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred){ for (; __first != __last; ++__first) { if (__pred(*__first)) { *__result = *__first; ++__result; } } return __result;}// copy_ntemplate<class _InputIterator, class _Size, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< __is_input_iterator<_InputIterator>::value && !__is_random_access_iterator<_InputIterator>::value, _OutputIterator>::typecopy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result){ typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; if (__n > 0) { *__result = *__first; ++__result; for (--__n; __n > 0; --__n) { ++__first; *__result = *__first; ++__result; } } return __result;}template<class _InputIterator, class _Size, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< __is_random_access_iterator<_InputIterator>::value, _OutputIterator>::typecopy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result){ typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; return _VSTD::copy(__first, __first + __n, __result);}// movetemplate <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIterator__move(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ for (; __first != __last; ++__first, (void) ++__result) *__result = _VSTD::move(*__first); return __result;}template <class _Tp, class _Up>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_same<typename remove_const<_Tp>::type, _Up>::value && is_trivially_copy_assignable<_Up>::value, _Up*>::type__move(_Tp* __first, _Tp* __last, _Up* __result){ const size_t __n = static_cast<size_t>(__last - __first); if (__n > 0) _VSTD::memmove(__result, __first, __n * sizeof(_Up)); return __result + __n;}template <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratormove(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ return _VSTD::__move(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));}// move_backwardtemplate <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIterator__move_backward(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ while (__first != __last) *--__result = _VSTD::move(*--__last); return __result;}template <class _Tp, class _Up>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_same<typename remove_const<_Tp>::type, _Up>::value && is_trivially_copy_assignable<_Up>::value, _Up*>::type__move_backward(_Tp* __first, _Tp* __last, _Up* __result){ const size_t __n = static_cast<size_t>(__last - __first); if (__n > 0) { __result -= __n; _VSTD::memmove(__result, __first, __n * sizeof(_Up)); } return __result;}template <class _BidirectionalIterator1, class _BidirectionalIterator2>inline _LIBCPP_INLINE_VISIBILITY_BidirectionalIterator2move_backward(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last, _BidirectionalIterator2 __result){ return _VSTD::__move_backward(__unwrap_iter(__first), __unwrap_iter(__last), __unwrap_iter(__result));}// iter_swap// moved to <type_traits> for better swap / noexcept support// transformtemplate <class _InputIterator, class _OutputIterator, class _UnaryOperation>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratortransform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op){ for (; __first != __last; ++__first, (void) ++__result) *__result = __op(*__first); return __result;}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _BinaryOperation>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratortransform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _OutputIterator __result, _BinaryOperation __binary_op){ for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result) *__result = __binary_op(*__first1, *__first2); return __result;}// replacetemplate <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoidreplace(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __old_value, const _Tp& __new_value){ for (; __first != __last; ++__first) if (*__first == __old_value) *__first = __new_value;}// replace_iftemplate <class _ForwardIterator, class _Predicate, class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoidreplace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value){ for (; __first != __last; ++__first) if (__pred(*__first)) *__first = __new_value;}// replace_copytemplate <class _InputIterator, class _OutputIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorreplace_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __old_value, const _Tp& __new_value){ for (; __first != __last; ++__first, (void) ++__result) if (*__first == __old_value) *__result = __new_value; else *__result = *__first; return __result;}// replace_copy_iftemplate <class _InputIterator, class _OutputIterator, class _Predicate, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorreplace_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred, const _Tp& __new_value){ for (; __first != __last; ++__first, (void) ++__result) if (__pred(*__first)) *__result = __new_value; else *__result = *__first; return __result;}// fill_ntemplate <class _OutputIterator, class _Size, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_OutputIterator__fill_n(_OutputIterator __first, _Size __n, const _Tp& __value_){ for (; __n > 0; ++__first, (void) --__n) *__first = __value_; return __first;}template <class _Tp, class _Size, class _Up>inline _LIBCPP_INLINE_VISIBILITYtypename enable_if< is_integral<_Tp>::value && sizeof(_Tp) == 1 && !is_same<_Tp, bool>::value && is_integral<_Up>::value && sizeof(_Up) == 1, _Tp*>::type__fill_n(_Tp* __first, _Size __n,_Up __value_){ if (__n > 0) _VSTD::memset(__first, (unsigned char)__value_, (size_t)(__n)); return __first + __n;}template <class _OutputIterator, class _Size, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorfill_n(_OutputIterator __first, _Size __n, const _Tp& __value_){ return _VSTD::__fill_n(__first, __convert_to_integral(__n), __value_);}// filltemplate <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoid__fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, forward_iterator_tag){ for (; __first != __last; ++__first) *__first = __value_;}template <class _RandomAccessIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoid__fill(_RandomAccessIterator __first, _RandomAccessIterator __last, const _Tp& __value_, random_access_iterator_tag){ _VSTD::fill_n(__first, __last - __first, __value_);}template <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoidfill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ _VSTD::__fill(__first, __last, __value_, typename iterator_traits<_ForwardIterator>::iterator_category());}// generatetemplate <class _ForwardIterator, class _Generator>inline _LIBCPP_INLINE_VISIBILITYvoidgenerate(_ForwardIterator __first, _ForwardIterator __last, _Generator __gen){ for (; __first != __last; ++__first) *__first = __gen();}// generate_ntemplate <class _OutputIterator, class _Size, class _Generator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorgenerate_n(_OutputIterator __first, _Size __orig_n, _Generator __gen){ typedef decltype(__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; for (; __n > 0; ++__first, (void) --__n) *__first = __gen(); return __first;}// removetemplate <class _ForwardIterator, class _Tp>_ForwardIteratorremove(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ __first = _VSTD::find(__first, __last, __value_); if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { if (!(*__i == __value_)) { *__first = _VSTD::move(*__i); ++__first; } } } return __first;}// remove_iftemplate <class _ForwardIterator, class _Predicate>_ForwardIteratorremove_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred){ __first = _VSTD::find_if<_ForwardIterator, typename add_lvalue_reference<_Predicate>::type> (__first, __last, __pred); if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { if (!__pred(*__i)) { *__first = _VSTD::move(*__i); ++__first; } } } return __first;}// remove_copytemplate <class _InputIterator, class _OutputIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorremove_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, const _Tp& __value_){ for (; __first != __last; ++__first) { if (!(*__first == __value_)) { *__result = *__first; ++__result; } } return __result;}// remove_copy_iftemplate <class _InputIterator, class _OutputIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorremove_copy_if(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _Predicate __pred){ for (; __first != __last; ++__first) { if (!__pred(*__first)) { *__result = *__first; ++__result; } } return __result;}// uniquetemplate <class _ForwardIterator, class _BinaryPredicate>_ForwardIteratorunique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred){ __first = _VSTD::adjacent_find<_ForwardIterator, typename add_lvalue_reference<_BinaryPredicate>::type> (__first, __last, __pred); if (__first != __last) { // ... a a ? ... // f i _ForwardIterator __i = __first; for (++__i; ++__i != __last;) if (!__pred(*__first, *__i)) *++__first = _VSTD::move(*__i); ++__first; } return __first;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorunique(_ForwardIterator __first, _ForwardIterator __last){ typedef typename iterator_traits<_ForwardIterator>::value_type __v; return _VSTD::unique(__first, __last, __equal_to<__v>());}// unique_copytemplate <class _BinaryPredicate, class _InputIterator, class _OutputIterator>_OutputIterator__unique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred, input_iterator_tag, output_iterator_tag){ if (__first != __last) { typename iterator_traits<_InputIterator>::value_type __t(*__first); *__result = __t; ++__result; while (++__first != __last) { if (!__pred(__t, *__first)) { __t = *__first; *__result = __t; ++__result; } } } return __result;}template <class _BinaryPredicate, class _ForwardIterator, class _OutputIterator>_OutputIterator__unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __pred, forward_iterator_tag, output_iterator_tag){ if (__first != __last) { _ForwardIterator __i = __first; *__result = *__i; ++__result; while (++__first != __last) { if (!__pred(*__i, *__first)) { *__result = *__first; ++__result; __i = __first; } } } return __result;}template <class _BinaryPredicate, class _InputIterator, class _ForwardIterator>_ForwardIterator__unique_copy(_InputIterator __first, _InputIterator __last, _ForwardIterator __result, _BinaryPredicate __pred, input_iterator_tag, forward_iterator_tag){ if (__first != __last) { *__result = *__first; while (++__first != __last) if (!__pred(*__result, *__first)) *++__result = *__first; ++__result; } return __result;}template <class _InputIterator, class _OutputIterator, class _BinaryPredicate>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorunique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _BinaryPredicate __pred){ return _VSTD::__unique_copy<typename add_lvalue_reference<_BinaryPredicate>::type> (__first, __last, __result, __pred, typename iterator_traits<_InputIterator>::iterator_category(), typename iterator_traits<_OutputIterator>::iterator_category());}template <class _InputIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorunique_copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result){ typedef typename iterator_traits<_InputIterator>::value_type __v; return _VSTD::unique_copy(__first, __last, __result, __equal_to<__v>());}// reversetemplate <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITYvoid__reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag){ while (__first != __last) { if (__first == --__last) break; _VSTD::iter_swap(__first, __last); ++__first; }}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoid__reverse(_RandomAccessIterator __first, _RandomAccessIterator __last, random_access_iterator_tag){ if (__first != __last) for (; __first < --__last; ++__first) _VSTD::iter_swap(__first, __last);}template <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITYvoidreverse(_BidirectionalIterator __first, _BidirectionalIterator __last){ _VSTD::__reverse(__first, __last, typename iterator_traits<_BidirectionalIterator>::iterator_category());}// reverse_copytemplate <class _BidirectionalIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorreverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last, _OutputIterator __result){ for (; __first != __last; ++__result) *__result = *--__last; return __result;}// rotatetemplate <class _ForwardIterator>_ForwardIterator__rotate_left(_ForwardIterator __first, _ForwardIterator __last){ typedef typename iterator_traits<_ForwardIterator>::value_type value_type; value_type __tmp = _VSTD::move(*__first); _ForwardIterator __lm1 = _VSTD::move(_VSTD::next(__first), __last, __first); *__lm1 = _VSTD::move(__tmp); return __lm1;}template <class _BidirectionalIterator>_BidirectionalIterator__rotate_right(_BidirectionalIterator __first, _BidirectionalIterator __last){ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; _BidirectionalIterator __lm1 = _VSTD::prev(__last); value_type __tmp = _VSTD::move(*__lm1); _BidirectionalIterator __fp1 = _VSTD::move_backward(__first, __lm1, __last); *__first = _VSTD::move(__tmp); return __fp1;}template <class _ForwardIterator>_ForwardIterator__rotate_forward(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last){ _ForwardIterator __i = __middle; while (true) { swap(*__first, *__i); ++__first; if (++__i == __last) break; if (__first == __middle) __middle = __i; } _ForwardIterator __r = __first; if (__first != __middle) { __i = __middle; while (true) { swap(*__first, *__i); ++__first; if (++__i == __last) { if (__first == __middle) break; __i = __middle; } else if (__first == __middle) __middle = __i; } } return __r;}template<typename _Integral>inline _LIBCPP_INLINE_VISIBILITY_Integral__algo_gcd(_Integral __x, _Integral __y){ do { _Integral __t = __x % __y; __x = __y; __y = __t; } while (__y); return __x;}template<typename _RandomAccessIterator>_RandomAccessIterator__rotate_gcd(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last){ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; const difference_type __m1 = __middle - __first; const difference_type __m2 = __last - __middle; if (__m1 == __m2) { _VSTD::swap_ranges(__first, __middle, __middle); return __middle; } const difference_type __g = _VSTD::__algo_gcd(__m1, __m2); for (_RandomAccessIterator __p = __first + __g; __p != __first;) { value_type __t(_VSTD::move(*--__p)); _RandomAccessIterator __p1 = __p; _RandomAccessIterator __p2 = __p1 + __m1; do { *__p1 = _VSTD::move(*__p2); __p1 = __p2; const difference_type __d = __last - __p2; if (__m1 < __d) __p2 += __m1; else __p2 = __first + (__m1 - __d); } while (__p2 != __p); *__p1 = _VSTD::move(__t); } return __first + __m2;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY_ForwardIterator__rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _VSTD::forward_iterator_tag){ typedef typename _VSTD::iterator_traits<_ForwardIterator>::value_type value_type; if (_VSTD::is_trivially_move_assignable<value_type>::value) { if (_VSTD::next(__first) == __middle) return _VSTD::__rotate_left(__first, __last); } return _VSTD::__rotate_forward(__first, __middle, __last);}template <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITY_BidirectionalIterator__rotate(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _VSTD::bidirectional_iterator_tag){ typedef typename _VSTD::iterator_traits<_BidirectionalIterator>::value_type value_type; if (_VSTD::is_trivially_move_assignable<value_type>::value) { if (_VSTD::next(__first) == __middle) return _VSTD::__rotate_left(__first, __last); if (_VSTD::next(__middle) == __last) return _VSTD::__rotate_right(__first, __last); } return _VSTD::__rotate_forward(__first, __middle, __last);}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITY_RandomAccessIterator__rotate(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _VSTD::random_access_iterator_tag){ typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::value_type value_type; if (_VSTD::is_trivially_move_assignable<value_type>::value) { if (_VSTD::next(__first) == __middle) return _VSTD::__rotate_left(__first, __last); if (_VSTD::next(__middle) == __last) return _VSTD::__rotate_right(__first, __last); return _VSTD::__rotate_gcd(__first, __middle, __last); } return _VSTD::__rotate_forward(__first, __middle, __last);}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorrotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last){ if (__first == __middle) return __last; if (__middle == __last) return __first; return _VSTD::__rotate(__first, __middle, __last, typename _VSTD::iterator_traits<_ForwardIterator>::iterator_category());}// rotate_copytemplate <class _ForwardIterator, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorrotate_copy(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, _OutputIterator __result){ return _VSTD::copy(__first, __middle, _VSTD::copy(__middle, __last, __result));}// min_elementtemplate <class _ForwardIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_ForwardIteratormin_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp){ if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) if (__comp(*__i, *__first)) __first = __i; } return __first;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_ForwardIteratormin_element(_ForwardIterator __first, _ForwardIterator __last){ return _VSTD::min_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());}// mintemplate <class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11const _Tp&min(const _Tp& __a, const _Tp& __b, _Compare __comp){ return __comp(__b, __a) ? __b : __a;}template <class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11const _Tp&min(const _Tp& __a, const _Tp& __b){ return _VSTD::min(__a, __b, __less<_Tp>());}#ifndef _LIBCPP_CXX03_LANGtemplate<class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_Tpmin(initializer_list<_Tp> __t, _Compare __comp){ return *_VSTD::min_element(__t.begin(), __t.end(), __comp);}template<class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_Tpmin(initializer_list<_Tp> __t){ return *_VSTD::min_element(__t.begin(), __t.end(), __less<_Tp>());}#endif // _LIBCPP_CXX03_LANG// max_elementtemplate <class _ForwardIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_ForwardIteratormax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp){ if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) if (__comp(*__first, *__i)) __first = __i; } return __first;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_ForwardIteratormax_element(_ForwardIterator __first, _ForwardIterator __last){ return _VSTD::max_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());}// maxtemplate <class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11const _Tp&max(const _Tp& __a, const _Tp& __b, _Compare __comp){ return __comp(__a, __b) ? __b : __a;}template <class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11const _Tp&max(const _Tp& __a, const _Tp& __b){ return _VSTD::max(__a, __b, __less<_Tp>());}#ifndef _LIBCPP_CXX03_LANGtemplate<class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_Tpmax(initializer_list<_Tp> __t, _Compare __comp){ return *_VSTD::max_element(__t.begin(), __t.end(), __comp);}template<class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11_Tpmax(initializer_list<_Tp> __t){ return *_VSTD::max_element(__t.begin(), __t.end(), __less<_Tp>());}#endif // _LIBCPP_CXX03_LANG#if _LIBCPP_STD_VER > 14// clamptemplate<class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPRconst _Tp&clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi, _Compare __comp){ _LIBCPP_ASSERT(!__comp(__hi, __lo), "Bad bounds passed to std::clamp"); return __comp(__v, __lo) ? __lo : __comp(__hi, __v) ? __hi : __v;}template<class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPRconst _Tp&clamp(const _Tp& __v, const _Tp& __lo, const _Tp& __hi){ return _VSTD::clamp(__v, __lo, __hi, __less<_Tp>());}#endif// minmax_elementtemplate <class _ForwardIterator, class _Compare>_LIBCPP_CONSTEXPR_AFTER_CXX11std::pair<_ForwardIterator, _ForwardIterator>minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp){ std::pair<_ForwardIterator, _ForwardIterator> __result(__first, __first); if (__first != __last) { if (++__first != __last) { if (__comp(*__first, *__result.first)) __result.first = __first; else __result.second = __first; while (++__first != __last) { _ForwardIterator __i = __first; if (++__first == __last) { if (__comp(*__i, *__result.first)) __result.first = __i; else if (!__comp(*__i, *__result.second)) __result.second = __i; break; } else { if (__comp(*__first, *__i)) { if (__comp(*__first, *__result.first)) __result.first = __first; if (!__comp(*__i, *__result.second)) __result.second = __i; } else { if (__comp(*__i, *__result.first)) __result.first = __i; if (!__comp(*__first, *__result.second)) __result.second = __first; } } } } } return __result;}template <class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11std::pair<_ForwardIterator, _ForwardIterator>minmax_element(_ForwardIterator __first, _ForwardIterator __last){ return _VSTD::minmax_element(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());}// minmaxtemplate<class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11pair<const _Tp&, const _Tp&>minmax(const _Tp& __a, const _Tp& __b, _Compare __comp){ return __comp(__b, __a) ? pair<const _Tp&, const _Tp&>(__b, __a) : pair<const _Tp&, const _Tp&>(__a, __b);}template<class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11pair<const _Tp&, const _Tp&>minmax(const _Tp& __a, const _Tp& __b){ return _VSTD::minmax(__a, __b, __less<_Tp>());}#ifndef _LIBCPP_CXX03_LANGtemplate<class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11pair<_Tp, _Tp>minmax(initializer_list<_Tp> __t, _Compare __comp){ typedef typename initializer_list<_Tp>::const_iterator _Iter; _Iter __first = __t.begin(); _Iter __last = __t.end(); std::pair<_Tp, _Tp> __result(*__first, *__first); ++__first; if (__t.size() % 2 == 0) { if (__comp(*__first, __result.first)) __result.first = *__first; else __result.second = *__first; ++__first; } while (__first != __last) { _Tp __prev = *__first++; if (__comp(*__first, __prev)) { if ( __comp(*__first, __result.first)) __result.first = *__first; if (!__comp(__prev, __result.second)) __result.second = __prev; } else { if ( __comp(__prev, __result.first)) __result.first = __prev; if (!__comp(*__first, __result.second)) __result.second = *__first; } __first++; } return __result;}template<class _Tp>inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX11pair<_Tp, _Tp>minmax(initializer_list<_Tp> __t){ return _VSTD::minmax(__t, __less<_Tp>());}#endif // _LIBCPP_CXX03_LANG// random_shuffle// __independent_bits_enginetemplate <unsigned long long _Xp, size_t _Rp>struct __log2_imp{ static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp : __log2_imp<_Xp, _Rp - 1>::value;};template <unsigned long long _Xp>struct __log2_imp<_Xp, 0>{ static const size_t value = 0;};template <size_t _Rp>struct __log2_imp<0, _Rp>{ static const size_t value = _Rp + 1;};template <class _UIntType, _UIntType _Xp>struct __log2{ static const size_t value = __log2_imp<_Xp, sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;};template<class _Engine, class _UIntType>class __independent_bits_engine{public: // types typedef _UIntType result_type;private: typedef typename _Engine::result_type _Engine_result_type; typedef typename conditional < sizeof(_Engine_result_type) <= sizeof(result_type), result_type, _Engine_result_type >::type _Working_result_type; _Engine& __e_; size_t __w_; size_t __w0_; size_t __n_; size_t __n0_; _Working_result_type __y0_; _Working_result_type __y1_; _Engine_result_type __mask0_; _Engine_result_type __mask1_;#ifdef _LIBCPP_CXX03_LANG static const _Working_result_type _Rp = _Engine::_Max - _Engine::_Min + _Working_result_type(1);#else static _LIBCPP_CONSTEXPR const _Working_result_type _Rp = _Engine::max() - _Engine::min() + _Working_result_type(1);#endif static _LIBCPP_CONSTEXPR const size_t __m = __log2<_Working_result_type, _Rp>::value; static _LIBCPP_CONSTEXPR const size_t _WDt = numeric_limits<_Working_result_type>::digits; static _LIBCPP_CONSTEXPR const size_t _EDt = numeric_limits<_Engine_result_type>::digits;public: // constructors and seeding functions __independent_bits_engine(_Engine& __e, size_t __w); // generating functions result_type operator()() {return __eval(integral_constant<bool, _Rp != 0>());}private: result_type __eval(false_type); result_type __eval(true_type);};template<class _Engine, class _UIntType>__independent_bits_engine<_Engine, _UIntType> ::__independent_bits_engine(_Engine& __e, size_t __w) : __e_(__e), __w_(__w){ __n_ = __w_ / __m + (__w_ % __m != 0); __w0_ = __w_ / __n_; if (_Rp == 0) __y0_ = _Rp; else if (__w0_ < _WDt) __y0_ = (_Rp >> __w0_) << __w0_; else __y0_ = 0; if (_Rp - __y0_ > __y0_ / __n_) { ++__n_; __w0_ = __w_ / __n_; if (__w0_ < _WDt) __y0_ = (_Rp >> __w0_) << __w0_; else __y0_ = 0; } __n0_ = __n_ - __w_ % __n_; if (__w0_ < _WDt - 1) __y1_ = (_Rp >> (__w0_ + 1)) << (__w0_ + 1); else __y1_ = 0; __mask0_ = __w0_ > 0 ? _Engine_result_type(~0) >> (_EDt - __w0_) : _Engine_result_type(0); __mask1_ = __w0_ < _EDt - 1 ? _Engine_result_type(~0) >> (_EDt - (__w0_ + 1)) : _Engine_result_type(~0);}template<class _Engine, class _UIntType>inline_UIntType__independent_bits_engine<_Engine, _UIntType>::__eval(false_type){ return static_cast<result_type>(__e_() & __mask0_);}template<class _Engine, class _UIntType>_UIntType__independent_bits_engine<_Engine, _UIntType>::__eval(true_type){ const size_t _WRt = numeric_limits<result_type>::digits; result_type _Sp = 0; for (size_t __k = 0; __k < __n0_; ++__k) { _Engine_result_type __u; do { __u = __e_() - _Engine::min(); } while (__u >= __y0_); if (__w0_ < _WRt) _Sp <<= __w0_; else _Sp = 0; _Sp += __u & __mask0_; } for (size_t __k = __n0_; __k < __n_; ++__k) { _Engine_result_type __u; do { __u = __e_() - _Engine::min(); } while (__u >= __y1_); if (__w0_ < _WRt - 1) _Sp <<= __w0_ + 1; else _Sp = 0; _Sp += __u & __mask1_; } return _Sp;}// uniform_int_distributiontemplate<class _IntType = int>class uniform_int_distribution{public: // types typedef _IntType result_type; class param_type { result_type __a_; result_type __b_; public: typedef uniform_int_distribution distribution_type; explicit param_type(result_type __a = 0, result_type __b = numeric_limits<result_type>::max()) : __a_(__a), __b_(__b) {} result_type a() const {return __a_;} result_type b() const {return __b_;} friend bool operator==(const param_type& __x, const param_type& __y) {return __x.__a_ == __y.__a_ && __x.__b_ == __y.__b_;} friend bool operator!=(const param_type& __x, const param_type& __y) {return !(__x == __y);} };private: param_type __p_;public: // constructors and reset functions explicit uniform_int_distribution(result_type __a = 0, result_type __b = numeric_limits<result_type>::max()) : __p_(param_type(__a, __b)) {} explicit uniform_int_distribution(const param_type& __p) : __p_(__p) {} void reset() {} // generating functions template<class _URNG> result_type operator()(_URNG& __g) {return (*this)(__g, __p_);} template<class _URNG> result_type operator()(_URNG& __g, const param_type& __p); // property functions result_type a() const {return __p_.a();} result_type b() const {return __p_.b();} param_type param() const {return __p_;} void param(const param_type& __p) {__p_ = __p;} result_type min() const {return a();} result_type max() const {return b();} friend bool operator==(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {return __x.__p_ == __y.__p_;} friend bool operator!=(const uniform_int_distribution& __x, const uniform_int_distribution& __y) {return !(__x == __y);}};template<class _IntType>template<class _URNG>typename uniform_int_distribution<_IntType>::result_typeuniform_int_distribution<_IntType>::operator()(_URNG& __g, const param_type& __p){ typedef typename conditional<sizeof(result_type) <= sizeof(uint32_t), uint32_t, uint64_t>::type _UIntType; const _UIntType _Rp = __p.b() - __p.a() + _UIntType(1); if (_Rp == 1) return __p.a(); const size_t _Dt = numeric_limits<_UIntType>::digits; typedef __independent_bits_engine<_URNG, _UIntType> _Eng; if (_Rp == 0) return static_cast<result_type>(_Eng(__g, _Dt)()); size_t __w = _Dt - __clz(_Rp) - 1; if ((_Rp & (std::numeric_limits<_UIntType>::max() >> (_Dt - __w))) != 0) ++__w; _Eng __e(__g, __w); _UIntType __u; do { __u = __e(); } while (__u >= _Rp); return static_cast<result_type>(__u + __p.a());}#if _LIBCPP_STD_VER <= 14 || defined(_LIBCPP_ENABLE_CXX17_REMOVED_RANDOM_SHUFFLE) \ || defined(_LIBCPP_BUILDING_LIBRARY)class _LIBCPP_TYPE_VIS __rs_default;_LIBCPP_FUNC_VIS __rs_default __rs_get();class _LIBCPP_TYPE_VIS __rs_default{ static unsigned __c_; __rs_default();public: typedef uint_fast32_t result_type; static const result_type _Min = 0; static const result_type _Max = 0xFFFFFFFF; __rs_default(const __rs_default&); ~__rs_default(); result_type operator()(); static _LIBCPP_CONSTEXPR result_type min() {return _Min;} static _LIBCPP_CONSTEXPR result_type max() {return _Max;} friend _LIBCPP_FUNC_VIS __rs_default __rs_get();};_LIBCPP_FUNC_VIS __rs_default __rs_get();template <class _RandomAccessIterator>voidrandom_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last){ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef uniform_int_distribution<ptrdiff_t> _Dp; typedef typename _Dp::param_type _Pp; difference_type __d = __last - __first; if (__d > 1) { _Dp __uid; __rs_default __g = __rs_get(); for (--__last, --__d; __first < __last; ++__first, --__d) { difference_type __i = __uid(__g, _Pp(0, __d)); if (__i != difference_type(0)) swap(*__first, *(__first + __i)); } }}template <class _RandomAccessIterator, class _RandomNumberGenerator>voidrandom_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,#ifndef _LIBCPP_CXX03_LANG _RandomNumberGenerator&& __rand)#else _RandomNumberGenerator& __rand)#endif{ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __d = __last - __first; if (__d > 1) { for (--__last; __first < __last; ++__first, --__d) { difference_type __i = __rand(__d); swap(*__first, *(__first + __i)); } }}#endiftemplate <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator>_LIBCPP_INLINE_VISIBILITY_SampleIterator __sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __output, _Distance __n, _UniformRandomNumberGenerator & __g, input_iterator_tag) { _Distance __k = 0; for (; __first != __last && __k < __n; ++__first, (void)++__k) __output[__k] = *__first; _Distance __sz = __k; for (; __first != __last; ++__first, (void)++__k) { _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, __k)(__g); if (__r < __sz) __output[__r] = *__first; } return __output + _VSTD::min(__n, __k);}template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator>_LIBCPP_INLINE_VISIBILITY_SampleIterator __sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __output, _Distance __n, _UniformRandomNumberGenerator& __g, forward_iterator_tag) { _Distance __unsampled_sz = _VSTD::distance(__first, __last); for (__n = _VSTD::min(__n, __unsampled_sz); __n != 0; ++__first) { _Distance __r = _VSTD::uniform_int_distribution<_Distance>(0, --__unsampled_sz)(__g); if (__r < __n) { *__output++ = *__first; --__n; } } return __output;}template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator>_LIBCPP_INLINE_VISIBILITY_SampleIterator __sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __output, _Distance __n, _UniformRandomNumberGenerator& __g) { typedef typename iterator_traits<_PopulationIterator>::iterator_category _PopCategory; typedef typename iterator_traits<_PopulationIterator>::difference_type _Difference; static_assert(__is_forward_iterator<_PopulationIterator>::value || __is_random_access_iterator<_SampleIterator>::value, "SampleIterator must meet the requirements of RandomAccessIterator"); typedef typename common_type<_Distance, _Difference>::type _CommonType; _LIBCPP_ASSERT(__n >= 0, "N must be a positive number."); return _VSTD::__sample( __first, __last, __output, _CommonType(__n), __g, _PopCategory());}#if _LIBCPP_STD_VER > 14template <class _PopulationIterator, class _SampleIterator, class _Distance, class _UniformRandomNumberGenerator>inline _LIBCPP_INLINE_VISIBILITY_SampleIterator sample(_PopulationIterator __first, _PopulationIterator __last, _SampleIterator __output, _Distance __n, _UniformRandomNumberGenerator&& __g) { return _VSTD::__sample(__first, __last, __output, __n, __g);}#endif // _LIBCPP_STD_VER > 14template<class _RandomAccessIterator, class _UniformRandomNumberGenerator> void shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,#ifndef _LIBCPP_CXX03_LANG _UniformRandomNumberGenerator&& __g)#else _UniformRandomNumberGenerator& __g)#endif{ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef uniform_int_distribution<ptrdiff_t> _Dp; typedef typename _Dp::param_type _Pp; difference_type __d = __last - __first; if (__d > 1) { _Dp __uid; for (--__last, --__d; __first < __last; ++__first, --__d) { difference_type __i = __uid(__g, _Pp(0, __d)); if (__i != difference_type(0)) swap(*__first, *(__first + __i)); } }}template <class _InputIterator, class _Predicate>boolis_partitioned(_InputIterator __first, _InputIterator __last, _Predicate __pred){ for (; __first != __last; ++__first) if (!__pred(*__first)) break; if ( __first == __last ) return true; ++__first; for (; __first != __last; ++__first) if (__pred(*__first)) return false; return true;}// partitiontemplate <class _Predicate, class _ForwardIterator>_ForwardIterator__partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag){ while (true) { if (__first == __last) return __first; if (!__pred(*__first)) break; ++__first; } for (_ForwardIterator __p = __first; ++__p != __last;) { if (__pred(*__p)) { swap(*__first, *__p); ++__first; } } return __first;}template <class _Predicate, class _BidirectionalIterator>_BidirectionalIterator__partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag){ while (true) { while (true) { if (__first == __last) return __first; if (!__pred(*__first)) break; ++__first; } do { if (__first == --__last) return __first; } while (!__pred(*__last)); swap(*__first, *__last); ++__first; }}template <class _ForwardIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorpartition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred){ return _VSTD::__partition<typename add_lvalue_reference<_Predicate>::type> (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());}// partition_copytemplate <class _InputIterator, class _OutputIterator1, class _OutputIterator2, class _Predicate>pair<_OutputIterator1, _OutputIterator2>partition_copy(_InputIterator __first, _InputIterator __last, _OutputIterator1 __out_true, _OutputIterator2 __out_false, _Predicate __pred){ for (; __first != __last; ++__first) { if (__pred(*__first)) { *__out_true = *__first; ++__out_true; } else { *__out_false = *__first; ++__out_false; } } return pair<_OutputIterator1, _OutputIterator2>(__out_true, __out_false);}// partition_pointtemplate<class _ForwardIterator, class _Predicate>_ForwardIteratorpartition_point(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred){ typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { difference_type __l2 = __len / 2; _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__pred(*__m)) { __first = ++__m; __len -= __l2 + 1; } else __len = __l2; } return __first;}// stable_partitiontemplate <class _Predicate, class _ForwardIterator, class _Distance, class _Pair>_ForwardIterator__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pair __p, forward_iterator_tag __fit){ // *__first is known to be false // __len >= 1 if (__len == 1) return __first; if (__len == 2) { _ForwardIterator __m = __first; if (__pred(*++__m)) { swap(*__first, *__m); return __m; } return __first; } if (__len <= __p.second) { // The buffer is big enough to use typedef typename iterator_traits<_ForwardIterator>::value_type value_type; __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); // Move the falses into the temporary buffer, and the trues to the front of the line // Update __first to always point to the end of the trues value_type* __t = __p.first; ::new(__t) value_type(_VSTD::move(*__first)); __d.__incr((value_type*)0); ++__t; _ForwardIterator __i = __first; while (++__i != __last) { if (__pred(*__i)) { *__first = _VSTD::move(*__i); ++__first; } else { ::new(__t) value_type(_VSTD::move(*__i)); __d.__incr((value_type*)0); ++__t; } } // All trues now at start of range, all falses in buffer // Move falses back into range, but don't mess up __first which points to first false __i = __first; for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) *__i = _VSTD::move(*__t2); // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer return __first; } // Else not enough buffer, do in place // __len >= 3 _ForwardIterator __m = __first; _Distance __len2 = __len / 2; // __len2 >= 2 _VSTD::advance(__m, __len2); // recurse on [__first, __m), *__first know to be false // F????????????????? // f m l typedef typename add_lvalue_reference<_Predicate>::type _PredRef; _ForwardIterator __first_false = __stable_partition<_PredRef>(__first, __m, __pred, __len2, __p, __fit); // TTTFFFFF?????????? // f ff m l // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true _ForwardIterator __m1 = __m; _ForwardIterator __second_false = __last; _Distance __len_half = __len - __len2; while (__pred(*__m1)) { if (++__m1 == __last) goto __second_half_done; --__len_half; } // TTTFFFFFTTTF?????? // f ff m m1 l __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __fit);__second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l return _VSTD::rotate(__first_false, __m, __second_false); // TTTTTTTTFFFFFFFFFF // |}struct __return_temporary_buffer{ template <class _Tp> _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);}};template <class _Predicate, class _ForwardIterator>_ForwardIterator__stable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag){ const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment // Either prove all true and return __first or point to first false while (true) { if (__first == __last) return __first; if (!__pred(*__first)) break; ++__first; } // We now have a reduced range [__first, __last) // *__first is known to be false typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; typedef typename iterator_traits<_ForwardIterator>::value_type value_type; difference_type __len = _VSTD::distance(__first, __last); pair<value_type*, ptrdiff_t> __p(0, 0); unique_ptr<value_type, __return_temporary_buffer> __h; if (__len >= __alloc_limit) { __p = _VSTD::get_temporary_buffer<value_type>(__len); __h.reset(__p.first); } return __stable_partition<typename add_lvalue_reference<_Predicate>::type> (__first, __last, __pred, __len, __p, forward_iterator_tag());}template <class _Predicate, class _BidirectionalIterator, class _Distance, class _Pair>_BidirectionalIterator__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, _Distance __len, _Pair __p, bidirectional_iterator_tag __bit){ // *__first is known to be false // *__last is known to be true // __len >= 2 if (__len == 2) { swap(*__first, *__last); return __last; } if (__len == 3) { _BidirectionalIterator __m = __first; if (__pred(*++__m)) { swap(*__first, *__m); swap(*__m, *__last); return __last; } swap(*__m, *__last); swap(*__first, *__m); return __m; } if (__len <= __p.second) { // The buffer is big enough to use typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h(__p.first, __d); // Move the falses into the temporary buffer, and the trues to the front of the line // Update __first to always point to the end of the trues value_type* __t = __p.first; ::new(__t) value_type(_VSTD::move(*__first)); __d.__incr((value_type*)0); ++__t; _BidirectionalIterator __i = __first; while (++__i != __last) { if (__pred(*__i)) { *__first = _VSTD::move(*__i); ++__first; } else { ::new(__t) value_type(_VSTD::move(*__i)); __d.__incr((value_type*)0); ++__t; } } // move *__last, known to be true *__first = _VSTD::move(*__i); __i = ++__first; // All trues now at start of range, all falses in buffer // Move falses back into range, but don't mess up __first which points to first false for (value_type* __t2 = __p.first; __t2 < __t; ++__t2, ++__i) *__i = _VSTD::move(*__t2); // __h destructs moved-from values out of the temp buffer, but doesn't deallocate buffer return __first; } // Else not enough buffer, do in place // __len >= 4 _BidirectionalIterator __m = __first; _Distance __len2 = __len / 2; // __len2 >= 2 _VSTD::advance(__m, __len2); // recurse on [__first, __m-1], except reduce __m-1 until *(__m-1) is true, *__first know to be false // F????????????????T // f m l _BidirectionalIterator __m1 = __m; _BidirectionalIterator __first_false = __first; _Distance __len_half = __len2; while (!__pred(*--__m1)) { if (__m1 == __first) goto __first_half_done; --__len_half; } // F???TFFF?????????T // f m1 m l typedef typename add_lvalue_reference<_Predicate>::type _PredRef; __first_false = __stable_partition<_PredRef>(__first, __m1, __pred, __len_half, __p, __bit);__first_half_done: // TTTFFFFF?????????T // f ff m l // recurse on [__m, __last], except increase __m until *(__m) is false, *__last know to be true __m1 = __m; _BidirectionalIterator __second_false = __last; ++__second_false; __len_half = __len - __len2; while (__pred(*__m1)) { if (++__m1 == __last) goto __second_half_done; --__len_half; } // TTTFFFFFTTTF?????T // f ff m m1 l __second_false = __stable_partition<_PredRef>(__m1, __last, __pred, __len_half, __p, __bit);__second_half_done: // TTTFFFFFTTTTTFFFFF // f ff m sf l return _VSTD::rotate(__first_false, __m, __second_false); // TTTTTTTTFFFFFFFFFF // |}template <class _Predicate, class _BidirectionalIterator>_BidirectionalIterator__stable_partition(_BidirectionalIterator __first, _BidirectionalIterator __last, _Predicate __pred, bidirectional_iterator_tag){ typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; const difference_type __alloc_limit = 4; // might want to make this a function of trivial assignment // Either prove all true and return __first or point to first false while (true) { if (__first == __last) return __first; if (!__pred(*__first)) break; ++__first; } // __first points to first false, everything prior to __first is already set. // Either prove [__first, __last) is all false and return __first, or point __last to last true do { if (__first == --__last) return __first; } while (!__pred(*__last)); // We now have a reduced range [__first, __last] // *__first is known to be false // *__last is known to be true // __len >= 2 difference_type __len = _VSTD::distance(__first, __last) + 1; pair<value_type*, ptrdiff_t> __p(0, 0); unique_ptr<value_type, __return_temporary_buffer> __h; if (__len >= __alloc_limit) { __p = _VSTD::get_temporary_buffer<value_type>(__len); __h.reset(__p.first); } return __stable_partition<typename add_lvalue_reference<_Predicate>::type> (__first, __last, __pred, __len, __p, bidirectional_iterator_tag());}template <class _ForwardIterator, class _Predicate>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorstable_partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred){ return __stable_partition<typename add_lvalue_reference<_Predicate>::type> (__first, __last, __pred, typename iterator_traits<_ForwardIterator>::iterator_category());}// is_sorted_untiltemplate <class _ForwardIterator, class _Compare>_ForwardIteratoris_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp){ if (__first != __last) { _ForwardIterator __i = __first; while (++__i != __last) { if (__comp(*__i, *__first)) return __i; __first = __i; } } return __last;}template<class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratoris_sorted_until(_ForwardIterator __first, _ForwardIterator __last){ return _VSTD::is_sorted_until(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());}// is_sortedtemplate <class _ForwardIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolis_sorted(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp){ return _VSTD::is_sorted_until(__first, __last, __comp) == __last;}template<class _ForwardIterator>inline _LIBCPP_INLINE_VISIBILITYboolis_sorted(_ForwardIterator __first, _ForwardIterator __last){ return _VSTD::is_sorted(__first, __last, __less<typename iterator_traits<_ForwardIterator>::value_type>());}// sort// stable, 2-3 compares, 0-2 swapstemplate <class _Compare, class _ForwardIterator>unsigned__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c){ unsigned __r = 0; if (!__c(*__y, *__x)) // if x <= y { if (!__c(*__z, *__y)) // if y <= z return __r; // x <= y && y <= z // x <= y && y > z swap(*__y, *__z); // x <= z && y < z __r = 1; if (__c(*__y, *__x)) // if x > y { swap(*__x, *__y); // x < y && y <= z __r = 2; } return __r; // x <= y && y < z } if (__c(*__z, *__y)) // x > y, if y > z { swap(*__x, *__z); // x < y && y < z __r = 1; return __r; } swap(*__x, *__y); // x > y && y <= z __r = 1; // x < y && x <= z if (__c(*__z, *__y)) // if y > z { swap(*__y, *__z); // x <= y && y < z __r = 2; } return __r;} // x <= y && y <= z// stable, 3-6 compares, 0-5 swapstemplate <class _Compare, class _ForwardIterator>unsigned__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _Compare __c){ unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c); if (__c(*__x4, *__x3)) { swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { swap(*__x1, *__x2); ++__r; } } } return __r;}// stable, 4-10 compares, 0-9 swapstemplate <class _Compare, class _ForwardIterator>unsigned__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3, _ForwardIterator __x4, _ForwardIterator __x5, _Compare __c){ unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c); if (__c(*__x5, *__x4)) { swap(*__x4, *__x5); ++__r; if (__c(*__x4, *__x3)) { swap(*__x3, *__x4); ++__r; if (__c(*__x3, *__x2)) { swap(*__x2, *__x3); ++__r; if (__c(*__x2, *__x1)) { swap(*__x1, *__x2); ++__r; } } } } return __r;}// Assumes size > 0template <class _Compare, class _BirdirectionalIterator>void__selection_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp){ _BirdirectionalIterator __lm1 = __last; for (--__lm1; __first != __lm1; ++__first) { _BirdirectionalIterator __i = _VSTD::min_element<_BirdirectionalIterator, typename add_lvalue_reference<_Compare>::type> (__first, __last, __comp); if (__i != __first) swap(*__first, *__i); }}template <class _Compare, class _BirdirectionalIterator>void__insertion_sort(_BirdirectionalIterator __first, _BirdirectionalIterator __last, _Compare __comp){ typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; if (__first != __last) { _BirdirectionalIterator __i = __first; for (++__i; __i != __last; ++__i) { _BirdirectionalIterator __j = __i; value_type __t(_VSTD::move(*__j)); for (_BirdirectionalIterator __k = __i; __k != __first && __comp(__t, *--__k); --__j) *__j = _VSTD::move(*__k); *__j = _VSTD::move(__t); } }}template <class _Compare, class _RandomAccessIterator>void__insertion_sort_3(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); } __j = __i; }}template <class _Compare, class _RandomAccessIterator>bool__insertion_sort_incomplete(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ switch (__last - __first) { case 0: case 1: return true; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return true; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return true; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return true; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return true; } typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; _RandomAccessIterator __j = __first+2; __sort3<_Compare>(__first, __first+1, __j, __comp); const unsigned __limit = 8; unsigned __count = 0; for (_RandomAccessIterator __i = __j+1; __i != __last; ++__i) { if (__comp(*__i, *__j)) { value_type __t(_VSTD::move(*__i)); _RandomAccessIterator __k = __j; __j = __i; do { *__j = _VSTD::move(*__k); __j = __k; } while (__j != __first && __comp(__t, *--__k)); *__j = _VSTD::move(__t); if (++__count == __limit) return ++__i == __last; } __j = __i; } return true;}template <class _Compare, class _BirdirectionalIterator>void__insertion_sort_move(_BirdirectionalIterator __first1, _BirdirectionalIterator __last1, typename iterator_traits<_BirdirectionalIterator>::value_type* __first2, _Compare __comp){ typedef typename iterator_traits<_BirdirectionalIterator>::value_type value_type; if (__first1 != __last1) { __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h(__first2, __d); value_type* __last2 = __first2; ::new(__last2) value_type(_VSTD::move(*__first1)); __d.__incr((value_type*)0); for (++__last2; ++__first1 != __last1; ++__last2) { value_type* __j2 = __last2; value_type* __i2 = __j2; if (__comp(*__first1, *--__i2)) { ::new(__j2) value_type(_VSTD::move(*__i2)); __d.__incr((value_type*)0); for (--__j2; __i2 != __first2 && __comp(*__first1, *--__i2); --__j2) *__j2 = _VSTD::move(*__i2); *__j2 = _VSTD::move(*__first1); } else { ::new(__j2) value_type(_VSTD::move(*__first1)); __d.__incr((value_type*)0); } } __h.release(); }}template <class _Compare, class _RandomAccessIterator>void__sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ // _Compare is known to be a reference type typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; const difference_type __limit = is_trivially_copy_constructible<value_type>::value && is_trivially_copy_assignable<value_type>::value ? 30 : 6; while (true) { __restart: difference_type __len = __last - __first; switch (__len) { case 0: case 1: return; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp); return; case 4: _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp); return; case 5: _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp); return; } if (__len <= __limit) { _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp); return; } // __len > 5 _RandomAccessIterator __m = __first; _RandomAccessIterator __lm1 = __last; --__lm1; unsigned __n_swaps; { difference_type __delta; if (__len >= 1000) { __delta = __len/2; __m += __delta; __delta /= 2; __n_swaps = _VSTD::__sort5<_Compare>(__first, __first + __delta, __m, __m+__delta, __lm1, __comp); } else { __delta = __len/2; __m += __delta; __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, __lm1, __comp); } } // *__m is median // partition [__first, __m) < *__m and *__m <= [__m, __last) // (this inhibits tossing elements equivalent to __m around unnecessarily) _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // j points beyond range to be tested, *__m is known to be <= *__lm1 // The search going up is known to be guarded but the search coming down isn't. // Prime the downward search with a guard. if (!__comp(*__i, *__m)) // if *__first == *__m { // *__first == *__m, *__first doesn't go in first part // manually guard downward moving __j against __i while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) ++__i; // __first + 1 __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) { while (true) { if (__i == __j) return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 if (__i == __j) return; while (true) { while (!__comp(*__first, *__i)) ++__i; while (__comp(*__first, *--__j)) ; if (__i >= __j) break; swap(*__i, *__j); ++__n_swaps; ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, sort the secod part // _VSTD::__sort<_Compare>(__i, __last, __comp); __first = __i; goto __restart; } if (__comp(*__j, *__m)) { swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } } // It is known that *__i < *__m ++__i; // j points beyond range to be tested, *__m is known to be <= *__lm1 // if not yet partitioned... if (__i < __j) { // known that *(__i - 1) < *__m // known that __i <= __m while (true) { // __m still guards upward moving __i while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j while (!__comp(*--__j, *__m)) ; if (__i > __j) break; swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it if (__m == __i) __m = __j; ++__i; } } // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { swap(*__i, *__m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) // If we were given a perfect partition, see if insertion sort is quick... if (__n_swaps == 0) { bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp); if (_VSTD::__insertion_sort_incomplete<_Compare>(__i+1, __last, __comp)) { if (__fs) return; __last = __i; continue; } else { if (__fs) { __first = ++__i; continue; } } } // sort smaller range with recursive call and larger with tail recursion elimination if (__i - __first < __last - __i) { _VSTD::__sort<_Compare>(__first, __i, __comp); // _VSTD::__sort<_Compare>(__i+1, __last, __comp); __first = ++__i; } else { _VSTD::__sort<_Compare>(__i+1, __last, __comp); // _VSTD::__sort<_Compare>(__first, __i, __comp); __last = __i; } }}// This forwarder keeps the top call and the recursive calls using the same instantiation, forcing a reference _Comparetemplate <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidsort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort<_Comp_ref>(__first, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort<_Comp_ref>(__first, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidsort(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}template <class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoidsort(_Tp** __first, _Tp** __last){ _VSTD::sort((size_t*)__first, (size_t*)__last, __less<size_t>());}template <class _Tp>inline _LIBCPP_INLINE_VISIBILITYvoidsort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last){ _VSTD::sort(__first.base(), __last.base());}template <class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidsort(__wrap_iter<_Tp*> __first, __wrap_iter<_Tp*> __last, _Compare __comp){ typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; _VSTD::sort<_Tp*, _Comp_ref>(__first.base(), __last.base(), __comp);}_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<char>&, char*>(char*, char*, __less<char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<short>&, short*>(short*, short*, __less<short>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<int>&, int*>(int*, int*, __less<int>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long>&, long*>(long*, long*, __less<long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<float>&, float*>(float*, float*, __less<float>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<double>&, double*>(double*, double*, __less<double>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void __sort<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<char>&, char*>(char*, char*, __less<char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<wchar_t>&, wchar_t*>(wchar_t*, wchar_t*, __less<wchar_t>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<signed char>&, signed char*>(signed char*, signed char*, __less<signed char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned char>&, unsigned char*>(unsigned char*, unsigned char*, __less<unsigned char>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<short>&, short*>(short*, short*, __less<short>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned short>&, unsigned short*>(unsigned short*, unsigned short*, __less<unsigned short>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<int>&, int*>(int*, int*, __less<int>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned>&, unsigned*>(unsigned*, unsigned*, __less<unsigned>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long>&, long*>(long*, long*, __less<long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long>&, unsigned long*>(unsigned long*, unsigned long*, __less<unsigned long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long long>&, long long*>(long long*, long long*, __less<long long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<unsigned long long>&, unsigned long long*>(unsigned long long*, unsigned long long*, __less<unsigned long long>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<float>&, float*>(float*, float*, __less<float>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<double>&, double*>(double*, double*, __less<double>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS bool __insertion_sort_incomplete<__less<long double>&, long double*>(long double*, long double*, __less<long double>&))_LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS unsigned __sort5<__less<long double>&, long double*>(long double*, long double*, long double*, long double*, long double*, __less<long double>&))// lower_boundtemplate <class _Compare, class _ForwardIterator, class _Tp>_ForwardIterator__lower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){ typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { difference_type __l2 = __len / 2; _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(*__m, __value_)) { __first = ++__m; __len -= __l2 + 1; } else __len = __l2; } return __first;}template <class _ForwardIterator, class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorlower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __lower_bound<_Comp_ref>(__first, __last, __value_, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __lower_bound<_Comp_ref>(__first, __last, __value_, __comp);#endif // _LIBCPP_DEBUG}template <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorlower_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ return _VSTD::lower_bound(__first, __last, __value_, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());}// upper_boundtemplate <class _Compare, class _ForwardIterator, class _Tp>_ForwardIterator__upper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){ typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { difference_type __l2 = __len / 2; _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(__value_, *__m)) __len = __l2; else { __first = ++__m; __len -= __l2 + 1; } } return __first;}template <class _ForwardIterator, class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorupper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __upper_bound<_Comp_ref>(__first, __last, __value_, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __upper_bound<_Comp_ref>(__first, __last, __value_, __comp);#endif // _LIBCPP_DEBUG}template <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITY_ForwardIteratorupper_bound(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ return _VSTD::upper_bound(__first, __last, __value_, __less<_Tp, typename iterator_traits<_ForwardIterator>::value_type>());}// equal_rangetemplate <class _Compare, class _ForwardIterator, class _Tp>pair<_ForwardIterator, _ForwardIterator>__equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){ typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; difference_type __len = _VSTD::distance(__first, __last); while (__len != 0) { difference_type __l2 = __len / 2; _ForwardIterator __m = __first; _VSTD::advance(__m, __l2); if (__comp(*__m, __value_)) { __first = ++__m; __len -= __l2 + 1; } else if (__comp(__value_, *__m)) { __last = __m; __len = __l2; } else { _ForwardIterator __mp1 = __m; return pair<_ForwardIterator, _ForwardIterator> ( __lower_bound<_Compare>(__first, __m, __value_, __comp), __upper_bound<_Compare>(++__mp1, __last, __value_, __comp) ); } } return pair<_ForwardIterator, _ForwardIterator>(__first, __first);}template <class _ForwardIterator, class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITYpair<_ForwardIterator, _ForwardIterator>equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __equal_range<_Comp_ref>(__first, __last, __value_, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __equal_range<_Comp_ref>(__first, __last, __value_, __comp);#endif // _LIBCPP_DEBUG}template <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYpair<_ForwardIterator, _ForwardIterator>equal_range(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ return _VSTD::equal_range(__first, __last, __value_, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());}// binary_searchtemplate <class _Compare, class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYbool__binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){ __first = __lower_bound<_Compare>(__first, __last, __value_, __comp); return __first != __last && !__comp(__value_, *__first);}template <class _ForwardIterator, class _Tp, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolbinary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __binary_search<_Comp_ref>(__first, __last, __value_, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __binary_search<_Comp_ref>(__first, __last, __value_, __comp);#endif // _LIBCPP_DEBUG}template <class _ForwardIterator, class _Tp>inline _LIBCPP_INLINE_VISIBILITYboolbinary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_){ return _VSTD::binary_search(__first, __last, __value_, __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());}// mergetemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>_OutputIterator__merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ for (; __first1 != __last1; ++__result) { if (__first2 == __last2) return _VSTD::copy(__first1, __last1, __result); if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; } else { *__result = *__first1; ++__first1; } } return _VSTD::copy(__first2, __last2, __result);}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratormerge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratormerge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result){ typedef typename iterator_traits<_InputIterator1>::value_type __v1; typedef typename iterator_traits<_InputIterator2>::value_type __v2; return merge(__first1, __last1, __first2, __last2, __result, __less<__v1, __v2>());}// inplace_mergetemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>void __half_inplace_merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { _VSTD::move(__first1, __last1, __result); return; } if (__comp(*__first2, *__first1)) { *__result = _VSTD::move(*__first2); ++__first2; } else { *__result = _VSTD::move(*__first1); ++__first1; } } // __first2 through __last2 are already in the right spot.}template <class _Compare, class _BidirectionalIterator>void__buffered_inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, typename iterator_traits<_BidirectionalIterator>::difference_type __len2, typename iterator_traits<_BidirectionalIterator>::value_type* __buff){ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); if (__len1 <= __len2) { value_type* __p = __buff; for (_BidirectionalIterator __i = __first; __i != __middle; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); __half_inplace_merge(__buff, __p, __middle, __last, __first, __comp); } else { value_type* __p = __buff; for (_BidirectionalIterator __i = __middle; __i != __last; __d.__incr((value_type*)0), (void) ++__i, ++__p) ::new(__p) value_type(_VSTD::move(*__i)); typedef reverse_iterator<_BidirectionalIterator> _RBi; typedef reverse_iterator<value_type*> _Rv; __half_inplace_merge(_Rv(__p), _Rv(__buff), _RBi(__middle), _RBi(__first), _RBi(__last), __negate<_Compare>(__comp)); }}template <class _Compare, class _BidirectionalIterator>void__inplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp, typename iterator_traits<_BidirectionalIterator>::difference_type __len1, typename iterator_traits<_BidirectionalIterator>::difference_type __len2, typename iterator_traits<_BidirectionalIterator>::value_type* __buff, ptrdiff_t __buff_size){ typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; while (true) { // if __middle == __last, we're done if (__len2 == 0) return; if (__len1 <= __buff_size || __len2 <= __buff_size) return __buffered_inplace_merge<_Compare> (__first, __middle, __last, __comp, __len1, __len2, __buff); // shrink [__first, __middle) as much as possible (with no moves), returning if it shrinks to 0 for (; true; ++__first, (void) --__len1) { if (__len1 == 0) return; if (__comp(*__middle, *__first)) break; } // __first < __middle < __last // *__first > *__middle // partition [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) such that // all elements in: // [__first, __m1) <= [__middle, __m2) // [__middle, __m2) < [__m1, __middle) // [__m1, __middle) <= [__m2, __last) // and __m1 or __m2 is in the middle of its range _BidirectionalIterator __m1; // "median" of [__first, __middle) _BidirectionalIterator __m2; // "median" of [__middle, __last) difference_type __len11; // distance(__first, __m1) difference_type __len21; // distance(__middle, __m2) // binary search smaller range if (__len1 < __len2) { // __len >= 1, __len2 >= 2 __len21 = __len2 / 2; __m2 = __middle; _VSTD::advance(__m2, __len21); __m1 = __upper_bound<_Compare>(__first, __middle, *__m2, __comp); __len11 = _VSTD::distance(__first, __m1); } else { if (__len1 == 1) { // __len1 >= __len2 && __len2 > 0, therefore __len2 == 1 // It is known *__first > *__middle swap(*__first, *__middle); return; } // __len1 >= 2, __len2 >= 1 __len11 = __len1 / 2; __m1 = __first; _VSTD::advance(__m1, __len11); __m2 = __lower_bound<_Compare>(__middle, __last, *__m1, __comp); __len21 = _VSTD::distance(__middle, __m2); } difference_type __len12 = __len1 - __len11; // distance(__m1, __middle) difference_type __len22 = __len2 - __len21; // distance(__m2, __last) // [__first, __m1) [__m1, __middle) [__middle, __m2) [__m2, __last) // swap middle two partitions __middle = _VSTD::rotate(__m1, __middle, __m2); // __len12 and __len21 now have swapped meanings // merge smaller range with recurisve call and larger with tail recursion elimination if (__len11 + __len21 < __len12 + __len22) { __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size);// __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size); __first = __middle; __middle = __m2; __len1 = __len12; __len2 = __len22; } else { __inplace_merge<_Compare>(__middle, __m2, __last, __comp, __len12, __len22, __buff, __buff_size);// __inplace_merge<_Compare>(__first, __m1, __middle, __comp, __len11, __len21, __buff, __buff_size); __last = __middle; __middle = __m1; __len1 = __len11; __len2 = __len21; } }}template <class _BidirectionalIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidinplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Compare __comp){ typedef typename iterator_traits<_BidirectionalIterator>::value_type value_type; typedef typename iterator_traits<_BidirectionalIterator>::difference_type difference_type; difference_type __len1 = _VSTD::distance(__first, __middle); difference_type __len2 = _VSTD::distance(__middle, __last); difference_type __buf_size = _VSTD::min(__len1, __len2); pair<value_type*, ptrdiff_t> __buf = _VSTD::get_temporary_buffer<value_type>(__buf_size); unique_ptr<value_type, __return_temporary_buffer> __h(__buf.first);#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __c, __len1, __len2, __buf.first, __buf.second);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return _VSTD::__inplace_merge<_Comp_ref>(__first, __middle, __last, __comp, __len1, __len2, __buf.first, __buf.second);#endif // _LIBCPP_DEBUG}template <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITYvoidinplace_merge(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last){ _VSTD::inplace_merge(__first, __middle, __last, __less<typename iterator_traits<_BidirectionalIterator>::value_type>());}// stable_sorttemplate <class _Compare, class _InputIterator1, class _InputIterator2>void__merge_move_construct(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, typename iterator_traits<_InputIterator1>::value_type* __result, _Compare __comp){ typedef typename iterator_traits<_InputIterator1>::value_type value_type; __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h(__result, __d); for (; true; ++__result) { if (__first1 == __last1) { for (; __first2 != __last2; ++__first2, ++__result, __d.__incr((value_type*)0)) ::new (__result) value_type(_VSTD::move(*__first2)); __h.release(); return; } if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, ++__result, __d.__incr((value_type*)0)) ::new (__result) value_type(_VSTD::move(*__first1)); __h.release(); return; } if (__comp(*__first2, *__first1)) { ::new (__result) value_type(_VSTD::move(*__first2)); __d.__incr((value_type*)0); ++__first2; } else { ::new (__result) value_type(_VSTD::move(*__first1)); __d.__incr((value_type*)0); ++__first1; } }}template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>void__merge_move_assign(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ for (; __first1 != __last1; ++__result) { if (__first2 == __last2) { for (; __first1 != __last1; ++__first1, ++__result) *__result = _VSTD::move(*__first1); return; } if (__comp(*__first2, *__first1)) { *__result = _VSTD::move(*__first2); ++__first2; } else { *__result = _VSTD::move(*__first1); ++__first1; } } for (; __first2 != __last2; ++__first2, ++__result) *__result = _VSTD::move(*__first2);}template <class _Compare, class _RandomAccessIterator>void__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size);template <class _Compare, class _RandomAccessIterator>void__stable_sort_move(_RandomAccessIterator __first1, _RandomAccessIterator __last1, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __first2){ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; switch (__len) { case 0: return; case 1: ::new(__first2) value_type(_VSTD::move(*__first1)); return; case 2: __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h2(__first2, __d); if (__comp(*--__last1, *__first1)) { ::new(__first2) value_type(_VSTD::move(*__last1)); __d.__incr((value_type*)0); ++__first2; ::new(__first2) value_type(_VSTD::move(*__first1)); } else { ::new(__first2) value_type(_VSTD::move(*__first1)); __d.__incr((value_type*)0); ++__first2; ::new(__first2) value_type(_VSTD::move(*__last1)); } __h2.release(); return; } if (__len <= 8) { __insertion_sort_move<_Compare>(__first1, __last1, __first2, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; _RandomAccessIterator __m = __first1 + __l2; __stable_sort<_Compare>(__first1, __m, __comp, __l2, __first2, __l2); __stable_sort<_Compare>(__m, __last1, __comp, __len - __l2, __first2 + __l2, __len - __l2); __merge_move_construct<_Compare>(__first1, __m, __m, __last1, __first2, __comp);}template <class _Tp>struct __stable_sort_switch{ static const unsigned value = 128*is_trivially_copy_assignable<_Tp>::value;};template <class _Compare, class _RandomAccessIterator>void__stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, typename iterator_traits<_RandomAccessIterator>::value_type* __buff, ptrdiff_t __buff_size){ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; switch (__len) { case 0: case 1: return; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return; } if (__len <= static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { __insertion_sort<_Compare>(__first, __last, __comp); return; } typename iterator_traits<_RandomAccessIterator>::difference_type __l2 = __len / 2; _RandomAccessIterator __m = __first + __l2; if (__len <= __buff_size) { __destruct_n __d(0); unique_ptr<value_type, __destruct_n&> __h2(__buff, __d); __stable_sort_move<_Compare>(__first, __m, __comp, __l2, __buff); __d.__set(__l2, (value_type*)0); __stable_sort_move<_Compare>(__m, __last, __comp, __len - __l2, __buff + __l2); __d.__set(__len, (value_type*)0); __merge_move_assign<_Compare>(__buff, __buff + __l2, __buff + __l2, __buff + __len, __first, __comp);// __merge<_Compare>(move_iterator<value_type*>(__buff),// move_iterator<value_type*>(__buff + __l2),// move_iterator<_RandomAccessIterator>(__buff + __l2),// move_iterator<_RandomAccessIterator>(__buff + __len),// __first, __comp); return; } __stable_sort<_Compare>(__first, __m, __comp, __l2, __buff, __buff_size); __stable_sort<_Compare>(__m, __last, __comp, __len - __l2, __buff, __buff_size); __inplace_merge<_Compare>(__first, __m, __last, __comp, __l2, __len - __l2, __buff, __buff_size);}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidstable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __len = __last - __first; pair<value_type*, ptrdiff_t> __buf(0, 0); unique_ptr<value_type, __return_temporary_buffer> __h; if (__len > static_cast<difference_type>(__stable_sort_switch<value_type>::value)) { __buf = _VSTD::get_temporary_buffer<value_type>(__len); __h.reset(__buf.first); }#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __stable_sort<_Comp_ref>(__first, __last, __c, __len, __buf.first, __buf.second);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __stable_sort<_Comp_ref>(__first, __last, __comp, __len, __buf.first, __buf.second);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidstable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::stable_sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// is_heap_untiltemplate <class _RandomAccessIterator, class _Compare>_RandomAccessIteratoris_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ typedef typename _VSTD::iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __len = __last - __first; difference_type __p = 0; difference_type __c = 1; _RandomAccessIterator __pp = __first; while (__c < __len) { _RandomAccessIterator __cp = __first + __c; if (__comp(*__pp, *__cp)) return __cp; ++__c; ++__cp; if (__c == __len) return __last; if (__comp(*__pp, *__cp)) return __cp; ++__p; ++__pp; __c = 2 * __p + 1; } return __last;}template<class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITY_RandomAccessIteratoris_heap_until(_RandomAccessIterator __first, _RandomAccessIterator __last){ return _VSTD::is_heap_until(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// is_heaptemplate <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolis_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ return _VSTD::is_heap_until(__first, __last, __comp) == __last;}template<class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYboolis_heap(_RandomAccessIterator __first, _RandomAccessIterator __last){ return _VSTD::is_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// push_heaptemplate <class _Compare, class _RandomAccessIterator>void__sift_up(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len){ typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; if (__len > 1) { __len = (__len - 2) / 2; _RandomAccessIterator __ptr = __first + __len; if (__comp(*__ptr, *--__last)) { value_type __t(_VSTD::move(*__last)); do { *__last = _VSTD::move(*__ptr); __last = __ptr; if (__len == 0) break; __len = (__len - 1) / 2; __ptr = __first + __len; } while (__comp(*__ptr, __t)); *__last = _VSTD::move(__t); } }}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidpush_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sift_up<_Comp_ref>(__first, __last, __c, __last - __first);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sift_up<_Comp_ref>(__first, __last, __comp, __last - __first);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidpush_heap(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::push_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// pop_heaptemplate <class _Compare, class _RandomAccessIterator>void__sift_down(_RandomAccessIterator __first, _RandomAccessIterator /*__last*/, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len, _RandomAccessIterator __start){ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; typedef typename iterator_traits<_RandomAccessIterator>::value_type value_type; // left-child of __start is at 2 * __start + 1 // right-child of __start is at 2 * __start + 2 difference_type __child = __start - __first; if (__len < 2 || (__len - 2) / 2 < __child) return; __child = 2 * __child + 1; _RandomAccessIterator __child_i = __first + __child; if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { // right-child exists and is greater than left-child ++__child_i; ++__child; } // check if we are in heap-order if (__comp(*__child_i, *__start)) // we are, __start is larger than it's largest child return; value_type __top(_VSTD::move(*__start)); do { // we are not in heap-order, swap the parent with it's largest child *__start = _VSTD::move(*__child_i); __start = __child_i; if ((__len - 2) / 2 < __child) break; // recompute the child based off of the updated parent __child = 2 * __child + 1; __child_i = __first + __child; if ((__child + 1) < __len && __comp(*__child_i, *(__child_i + 1))) { // right-child exists and is greater than left-child ++__child_i; ++__child; } // check if we are in heap-order } while (!__comp(*__child_i, __top)); *__start = _VSTD::move(__top);}template <class _Compare, class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoid__pop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, typename iterator_traits<_RandomAccessIterator>::difference_type __len){ if (__len > 1) { swap(*__first, *--__last); __sift_down<_Compare>(__first, __last, __comp, __len - 1, __first); }}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidpop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __pop_heap<_Comp_ref>(__first, __last, __c, __last - __first);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __pop_heap<_Comp_ref>(__first, __last, __comp, __last - __first);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidpop_heap(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::pop_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// make_heaptemplate <class _Compare, class _RandomAccessIterator>void__make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; difference_type __n = __last - __first; if (__n > 1) { // start from the first parent, there is no need to consider children for (difference_type __start = (__n - 2) / 2; __start >= 0; --__start) { __sift_down<_Compare>(__first, __last, __comp, __n, __first + __start); } }}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidmake_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __make_heap<_Comp_ref>(__first, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __make_heap<_Comp_ref>(__first, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidmake_heap(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::make_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// sort_heaptemplate <class _Compare, class _RandomAccessIterator>void__sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){ typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; for (difference_type __n = __last - __first; __n > 1; --__last, --__n) __pop_heap<_Compare>(__first, __last, __comp, __n);}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidsort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __sort_heap<_Comp_ref>(__first, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __sort_heap<_Comp_ref>(__first, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidsort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last){ _VSTD::sort_heap(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// partial_sorttemplate <class _Compare, class _RandomAccessIterator>void__partial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp){ __make_heap<_Compare>(__first, __middle, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __middle - __first; for (_RandomAccessIterator __i = __middle; __i != __last; ++__i) { if (__comp(*__i, *__first)) { swap(*__i, *__first); __sift_down<_Compare>(__first, __middle, __comp, __len, __first); } } __sort_heap<_Compare>(__first, __middle, __comp);}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidpartial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __partial_sort<_Comp_ref>(__first, __middle, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __partial_sort<_Comp_ref>(__first, __middle, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidpartial_sort(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last){ _VSTD::partial_sort(__first, __middle, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// partial_sort_copytemplate <class _Compare, class _InputIterator, class _RandomAccessIterator>_RandomAccessIterator__partial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp){ _RandomAccessIterator __r = __result_first; if (__r != __result_last) { for (; __first != __last && __r != __result_last; (void) ++__first, ++__r) *__r = *__first; __make_heap<_Compare>(__result_first, __r, __comp); typename iterator_traits<_RandomAccessIterator>::difference_type __len = __r - __result_first; for (; __first != __last; ++__first) if (__comp(*__first, *__result_first)) { *__result_first = *__first; __sift_down<_Compare>(__result_first, __r, __comp, __len, __result_first); } __sort_heap<_Compare>(__result_first, __r, __comp); } return __r;}template <class _InputIterator, class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_RandomAccessIteratorpartial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __partial_sort_copy<_Comp_ref>(__first, __last, __result_first, __result_last, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator, class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITY_RandomAccessIteratorpartial_sort_copy(_InputIterator __first, _InputIterator __last, _RandomAccessIterator __result_first, _RandomAccessIterator __result_last){ return _VSTD::partial_sort_copy(__first, __last, __result_first, __result_last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// nth_elementtemplate <class _Compare, class _RandomAccessIterator>void__nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp){ // _Compare is known to be a reference type typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; const difference_type __limit = 7; while (true) { __restart: if (__nth == __last) return; difference_type __len = __last - __first; switch (__len) { case 0: case 1: return; case 2: if (__comp(*--__last, *__first)) swap(*__first, *__last); return; case 3: { _RandomAccessIterator __m = __first; _VSTD::__sort3<_Compare>(__first, ++__m, --__last, __comp); return; } } if (__len <= __limit) { __selection_sort<_Compare>(__first, __last, __comp); return; } // __len > __limit >= 3 _RandomAccessIterator __m = __first + __len/2; _RandomAccessIterator __lm1 = __last; unsigned __n_swaps = _VSTD::__sort3<_Compare>(__first, __m, --__lm1, __comp); // *__m is median // partition [__first, __m) < *__m and *__m <= [__m, __last) // (this inhibits tossing elements equivalent to __m around unnecessarily) _RandomAccessIterator __i = __first; _RandomAccessIterator __j = __lm1; // j points beyond range to be tested, *__lm1 is known to be <= *__m // The search going up is known to be guarded but the search coming down isn't. // Prime the downward search with a guard. if (!__comp(*__i, *__m)) // if *__first == *__m { // *__first == *__m, *__first doesn't go in first part // manually guard downward moving __j against __i while (true) { if (__i == --__j) { // *__first == *__m, *__m <= all other elements // Parition instead into [__first, __i) == *__first and *__first < [__i, __last) ++__i; // __first + 1 __j = __last; if (!__comp(*__first, *--__j)) // we need a guard if *__first == *(__last-1) { while (true) { if (__i == __j) return; // [__first, __last) all equivalent elements if (__comp(*__first, *__i)) { swap(*__i, *__j); ++__n_swaps; ++__i; break; } ++__i; } } // [__first, __i) == *__first and *__first < [__j, __last) and __j == __last - 1 if (__i == __j) return; while (true) { while (!__comp(*__first, *__i)) ++__i; while (__comp(*__first, *--__j)) ; if (__i >= __j) break; swap(*__i, *__j); ++__n_swaps; ++__i; } // [__first, __i) == *__first and *__first < [__i, __last) // The first part is sorted, if (__nth < __i) return; // __nth_element the secod part // __nth_element<_Compare>(__i, __nth, __last, __comp); __first = __i; goto __restart; } if (__comp(*__j, *__m)) { swap(*__i, *__j); ++__n_swaps; break; // found guard for downward moving __j, now use unguarded partition } } } ++__i; // j points beyond range to be tested, *__lm1 is known to be <= *__m // if not yet partitioned... if (__i < __j) { // known that *(__i - 1) < *__m while (true) { // __m still guards upward moving __i while (__comp(*__i, *__m)) ++__i; // It is now known that a guard exists for downward moving __j while (!__comp(*--__j, *__m)) ; if (__i >= __j) break; swap(*__i, *__j); ++__n_swaps; // It is known that __m != __j // If __m just moved, follow it if (__m == __i) __m = __j; ++__i; } } // [__first, __i) < *__m and *__m <= [__i, __last) if (__i != __m && __comp(*__m, *__i)) { swap(*__i, *__m); ++__n_swaps; } // [__first, __i) < *__i and *__i <= [__i+1, __last) if (__nth == __i) return; if (__n_swaps == 0) { // We were given a perfectly partitioned sequence. Coincidence? if (__nth < __i) { // Check for [__first, __i) already sorted __j = __m = __first; while (++__j != __i) { if (__comp(*__j, *__m)) // not yet sorted, so sort goto not_sorted; __m = __j; } // [__first, __i) sorted return; } else { // Check for [__i, __last) already sorted __j = __m = __i; while (++__j != __last) { if (__comp(*__j, *__m)) // not yet sorted, so sort goto not_sorted; __m = __j; } // [__i, __last) sorted return; } }not_sorted: // __nth_element on range containing __nth if (__nth < __i) { // __nth_element<_Compare>(__first, __nth, __i, __comp); __last = __i; } else { // __nth_element<_Compare>(__i+1, __nth, __last, __comp); __first = ++__i; } }}template <class _RandomAccessIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYvoidnth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); __nth_element<_Comp_ref>(__first, __nth, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; __nth_element<_Comp_ref>(__first, __nth, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _RandomAccessIterator>inline _LIBCPP_INLINE_VISIBILITYvoidnth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth, _RandomAccessIterator __last){ _VSTD::nth_element(__first, __nth, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());}// includestemplate <class _Compare, class _InputIterator1, class _InputIterator2>bool__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp){ for (; __first2 != __last2; ++__first1) { if (__first1 == __last1 || __comp(*__first2, *__first1)) return false; if (!__comp(*__first1, *__first2)) ++__first2; } return true;}template <class _InputIterator1, class _InputIterator2, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolincludes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYboolincludes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2){ return _VSTD::includes(__first1, __last1, __first2, __last2, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// set_uniontemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>_OutputIterator__set_union(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ for (; __first1 != __last1; ++__result) { if (__first2 == __last2) return _VSTD::copy(__first1, __last1, __result); if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__first2; } else { *__result = *__first1; if (!__comp(*__first1, *__first2)) ++__first2; ++__first1; } } return _VSTD::copy(__first2, __last2, __result);}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_union(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __set_union<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_union(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result){ return _VSTD::set_union(__first1, __last1, __first2, __last2, __result, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// set_intersectiontemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>_OutputIterator__set_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ while (__first1 != __last1 && __first2 != __last2) { if (__comp(*__first1, *__first2)) ++__first1; else { if (!__comp(*__first2, *__first1)) { *__result = *__first1; ++__result; ++__first1; } ++__first2; } } return __result;}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __set_intersection<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_intersection(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result){ return _VSTD::set_intersection(__first1, __last1, __first2, __last2, __result, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// set_differencetemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>_OutputIterator__set_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ while (__first1 != __last1) { if (__first2 == __last2) return _VSTD::copy(__first1, __last1, __result); if (__comp(*__first1, *__first2)) { *__result = *__first1; ++__result; ++__first1; } else { if (!__comp(*__first2, *__first1)) ++__first1; ++__first2; } } return __result;}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __set_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result){ return _VSTD::set_difference(__first1, __last1, __first2, __last2, __result, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// set_symmetric_differencetemplate <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>_OutputIterator__set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){ while (__first1 != __last1) { if (__first2 == __last2) return _VSTD::copy(__first1, __last1, __result); if (__comp(*__first1, *__first2)) { *__result = *__first1; ++__result; ++__first1; } else { if (__comp(*__first2, *__first1)) { *__result = *__first2; ++__result; } else ++__first1; ++__first2; } } return _VSTD::copy(__first2, __last2, __result);}template <class _InputIterator1, class _InputIterator2, class _OutputIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __set_symmetric_difference<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2, class _OutputIterator>inline _LIBCPP_INLINE_VISIBILITY_OutputIteratorset_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result){ return _VSTD::set_symmetric_difference(__first1, __last1, __first2, __last2, __result, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// lexicographical_comparetemplate <class _Compare, class _InputIterator1, class _InputIterator2>bool__lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp){ for (; __first2 != __last2; ++__first1, (void) ++__first2) { if (__first1 == __last1 || __comp(*__first1, *__first2)) return true; if (__comp(*__first2, *__first1)) return false; } return false;}template <class _InputIterator1, class _InputIterator2, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboollexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __lexicographical_compare<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);#endif // _LIBCPP_DEBUG}template <class _InputIterator1, class _InputIterator2>inline _LIBCPP_INLINE_VISIBILITYboollexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2){ return _VSTD::lexicographical_compare(__first1, __last1, __first2, __last2, __less<typename iterator_traits<_InputIterator1>::value_type, typename iterator_traits<_InputIterator2>::value_type>());}// next_permutationtemplate <class _Compare, class _BidirectionalIterator>bool__next_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp){ _BidirectionalIterator __i = __last; if (__first == __last || __first == --__i) return false; while (true) { _BidirectionalIterator __ip1 = __i; if (__comp(*--__i, *__ip1)) { _BidirectionalIterator __j = __last; while (!__comp(*__i, *--__j)) ; swap(*__i, *__j); _VSTD::reverse(__ip1, __last); return true; } if (__i == __first) { _VSTD::reverse(__first, __last); return false; } }}template <class _BidirectionalIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolnext_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __next_permutation<_Comp_ref>(__first, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __next_permutation<_Comp_ref>(__first, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITYboolnext_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last){ return _VSTD::next_permutation(__first, __last, __less<typename iterator_traits<_BidirectionalIterator>::value_type>());}// prev_permutationtemplate <class _Compare, class _BidirectionalIterator>bool__prev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp){ _BidirectionalIterator __i = __last; if (__first == __last || __first == --__i) return false; while (true) { _BidirectionalIterator __ip1 = __i; if (__comp(*__ip1, *--__i)) { _BidirectionalIterator __j = __last; while (!__comp(*--__j, *__i)) ; swap(*__i, *__j); _VSTD::reverse(__ip1, __last); return true; } if (__i == __first) { _VSTD::reverse(__first, __last); return false; } }}template <class _BidirectionalIterator, class _Compare>inline _LIBCPP_INLINE_VISIBILITYboolprev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last, _Compare __comp){#ifdef _LIBCPP_DEBUG typedef typename add_lvalue_reference<__debug_less<_Compare> >::type _Comp_ref; __debug_less<_Compare> __c(__comp); return __prev_permutation<_Comp_ref>(__first, __last, __c);#else // _LIBCPP_DEBUG typedef typename add_lvalue_reference<_Compare>::type _Comp_ref; return __prev_permutation<_Comp_ref>(__first, __last, __comp);#endif // _LIBCPP_DEBUG}template <class _BidirectionalIterator>inline _LIBCPP_INLINE_VISIBILITYboolprev_permutation(_BidirectionalIterator __first, _BidirectionalIterator __last){ return _VSTD::prev_permutation(__first, __last, __less<typename iterator_traits<_BidirectionalIterator>::value_type>());}_LIBCPP_END_NAMESPACE_STD_LIBCPP_POP_MACROS#endif // _LIBCPP_ALGORITHM