algorithm.h 203 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073307430753076307730783079308030813082308330843085308630873088308930903091309230933094309530963097309830993100310131023103310431053106310731083109311031113112311331143115311631173118311931203121312231233124312531263127312831293130313131323133313431353136313731383139314031413142314331443145314631473148314931503151315231533154315531563157315831593160316131623163316431653166316731683169317031713172317331743175317631773178317931803181318231833184318531863187318831893190319131923193319431953196319731983199320032013202320332043205320632073208320932103211321232133214321532163217321832193220322132223223322432253226322732283229323032313232323332343235323632373238323932403241324232433244324532463247324832493250325132523253325432553256325732583259326032613262326332643265326632673268326932703271327232733274327532763277327832793280328132823283328432853286328732883289329032913292329332943295329632973298329933003301330233033304330533063307330833093310331133123313331433153316331733183319332033213322332333243325332633273328332933303331333233333334333533363337333833393340334133423343334433453346334733483349335033513352335333543355335633573358335933603361336233633364336533663367336833693370337133723373337433753376337733783379338033813382338333843385338633873388338933903391339233933394339533963397339833993400340134023403340434053406340734083409341034113412341334143415341634173418341934203421342234233424342534263427342834293430343134323433343434353436343734383439344034413442344334443445344634473448344934503451345234533454345534563457345834593460346134623463346434653466346734683469347034713472347334743475347634773478347934803481348234833484348534863487348834893490349134923493349434953496349734983499350035013502350335043505350635073508350935103511351235133514351535163517351835193520352135223523352435253526352735283529353035313532353335343535353635373538353935403541354235433544354535463547354835493550355135523553355435553556355735583559356035613562356335643565356635673568356935703571357235733574357535763577357835793580358135823583358435853586358735883589359035913592359335943595359635973598359936003601360236033604360536063607360836093610361136123613361436153616361736183619362036213622362336243625362636273628362936303631363236333634363536363637363836393640364136423643364436453646364736483649365036513652365336543655365636573658365936603661366236633664366536663667366836693670367136723673367436753676367736783679368036813682368336843685368636873688368936903691369236933694369536963697369836993700370137023703370437053706370737083709371037113712371337143715371637173718371937203721372237233724372537263727372837293730373137323733373437353736373737383739374037413742374337443745374637473748374937503751375237533754375537563757375837593760376137623763376437653766376737683769377037713772377337743775377637773778377937803781378237833784378537863787378837893790379137923793379437953796379737983799380038013802380338043805380638073808380938103811381238133814381538163817381838193820382138223823382438253826382738283829383038313832383338343835383638373838383938403841384238433844384538463847384838493850385138523853385438553856385738583859386038613862386338643865386638673868386938703871387238733874387538763877387838793880388138823883388438853886388738883889389038913892389338943895389638973898389939003901390239033904390539063907390839093910391139123913391439153916391739183919392039213922392339243925392639273928392939303931393239333934393539363937393839393940394139423943394439453946394739483949395039513952395339543955395639573958395939603961396239633964396539663967396839693970397139723973397439753976397739783979398039813982398339843985398639873988398939903991399239933994399539963997399839994000400140024003400440054006400740084009401040114012401340144015401640174018401940204021402240234024402540264027402840294030403140324033403440354036403740384039404040414042404340444045404640474048404940504051405240534054405540564057405840594060406140624063406440654066406740684069407040714072407340744075407640774078407940804081408240834084408540864087408840894090409140924093409440954096409740984099410041014102410341044105410641074108410941104111411241134114411541164117411841194120412141224123412441254126412741284129413041314132413341344135413641374138413941404141414241434144414541464147414841494150415141524153415441554156415741584159416041614162416341644165416641674168416941704171417241734174417541764177417841794180418141824183418441854186418741884189419041914192419341944195419641974198419942004201420242034204420542064207420842094210421142124213421442154216421742184219422042214222422342244225422642274228422942304231423242334234423542364237423842394240424142424243424442454246424742484249425042514252425342544255425642574258425942604261426242634264426542664267426842694270427142724273427442754276427742784279428042814282428342844285428642874288428942904291429242934294429542964297429842994300430143024303430443054306430743084309431043114312431343144315431643174318431943204321432243234324432543264327432843294330433143324333433443354336433743384339434043414342434343444345434643474348434943504351435243534354435543564357435843594360436143624363436443654366436743684369437043714372437343744375437643774378437943804381438243834384438543864387438843894390439143924393439443954396439743984399440044014402440344044405440644074408440944104411441244134414441544164417441844194420442144224423442444254426442744284429443044314432443344344435443644374438443944404441444244434444444544464447444844494450445144524453445444554456445744584459446044614462446344644465446644674468446944704471447244734474447544764477447844794480448144824483448444854486448744884489449044914492449344944495449644974498449945004501450245034504450545064507450845094510451145124513451445154516451745184519452045214522452345244525452645274528452945304531453245334534453545364537453845394540454145424543454445454546454745484549455045514552455345544555455645574558455945604561456245634564456545664567456845694570457145724573457445754576457745784579458045814582458345844585458645874588458945904591459245934594459545964597459845994600460146024603460446054606460746084609461046114612461346144615461646174618461946204621462246234624462546264627462846294630463146324633463446354636463746384639464046414642464346444645464646474648464946504651465246534654465546564657465846594660466146624663466446654666466746684669467046714672467346744675467646774678467946804681468246834684468546864687468846894690469146924693469446954696469746984699470047014702470347044705470647074708470947104711471247134714471547164717471847194720472147224723472447254726472747284729473047314732473347344735473647374738473947404741474247434744474547464747474847494750475147524753475447554756475747584759476047614762476347644765476647674768476947704771477247734774477547764777477847794780478147824783478447854786478747884789479047914792479347944795479647974798479948004801480248034804480548064807480848094810481148124813481448154816481748184819482048214822482348244825482648274828482948304831483248334834483548364837483848394840484148424843484448454846484748484849485048514852485348544855485648574858485948604861486248634864486548664867486848694870487148724873487448754876487748784879488048814882488348844885488648874888488948904891489248934894489548964897489848994900490149024903490449054906490749084909491049114912491349144915491649174918491949204921492249234924492549264927492849294930493149324933493449354936493749384939494049414942494349444945494649474948494949504951495249534954495549564957495849594960496149624963496449654966496749684969497049714972497349744975497649774978497949804981498249834984498549864987498849894990499149924993499449954996499749984999500050015002500350045005500650075008500950105011
  1. // Copyright 2020 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef BASE_RANGES_ALGORITHM_H_
  5. #define BASE_RANGES_ALGORITHM_H_
  6. #include <algorithm>
  7. #include <initializer_list>
  8. #include <iterator>
  9. #include <type_traits>
  10. #include <utility>
  11. #include "base/check.h"
  12. #include "base/compiler_specific.h"
  13. #include "base/functional/identity.h"
  14. #include "base/functional/invoke.h"
  15. #include "base/ranges/functional.h"
  16. #include "base/ranges/ranges.h"
  17. #include "base/template_util.h"
  18. namespace base {
  19. namespace internal {
  20. // Returns a transformed version of the unary predicate `pred` applying `proj`
  21. // to its argument before invoking `pred` on it.
  22. // Ensures that the return type of `invoke(pred, ...)` is convertible to bool.
  23. template <typename Pred, typename Proj>
  24. constexpr auto ProjectedUnaryPredicate(Pred& pred, Proj& proj) noexcept {
  25. return [&pred, &proj](auto&& arg) -> bool {
  26. return base::invoke(pred,
  27. base::invoke(proj, std::forward<decltype(arg)>(arg)));
  28. };
  29. }
  30. // Returns a transformed version of the binary predicate `pred` applying `proj1`
  31. // and `proj2` to its arguments before invoking `pred` on them.
  32. //
  33. // Provides an opt-in to considers all four permutations of projections and
  34. // argument types. This is sometimes necessary to allow usage with legacy
  35. // non-ranges std:: algorithms that don't support projections.
  36. //
  37. // These permutations are assigned different priorities to break ambiguities in
  38. // case several permutations are possible, e.g. when Proj1 and Proj2 are the
  39. // same type.
  40. //
  41. // Note that even when opting in to using all permutations of projections,
  42. // calling code should still ensure that the canonical mapping of {Proj1, Proj2}
  43. // to {LHS, RHS} compiles for all members of the range. This can be done by
  44. // adding the following constraint:
  45. //
  46. // typename = indirect_result_t<Pred&,
  47. // projected<iterator_t<Range1>, Proj1>,
  48. // projected<iterator_t<Range2>, Proj2>>
  49. //
  50. // Ensures that the return type of `invoke(pred, ...)` is convertible to bool.
  51. template <typename Pred, typename Proj1, typename Proj2, bool kPermute = false>
  52. class BinaryPredicateProjector {
  53. public:
  54. constexpr BinaryPredicateProjector(Pred& pred, Proj1& proj1, Proj2& proj2)
  55. : pred_(pred), proj1_(proj1), proj2_(proj2) {}
  56. private:
  57. template <typename ProjT, typename ProjU, typename T, typename U>
  58. using InvokeResult = std::invoke_result_t<Pred&,
  59. std::invoke_result_t<ProjT&, T&&>,
  60. std::invoke_result_t<ProjU&, U&&>>;
  61. template <typename T, typename U, typename = InvokeResult<Proj1, Proj2, T, U>>
  62. constexpr std::pair<Proj1&, Proj2&> GetProjs(priority_tag<3>) const {
  63. return {proj1_, proj2_};
  64. }
  65. template <typename T,
  66. typename U,
  67. bool LazyPermute = kPermute,
  68. typename = std::enable_if_t<LazyPermute>,
  69. typename = InvokeResult<Proj2, Proj1, T, U>>
  70. constexpr std::pair<Proj2&, Proj1&> GetProjs(priority_tag<2>) const {
  71. return {proj2_, proj1_};
  72. }
  73. template <typename T,
  74. typename U,
  75. bool LazyPermute = kPermute,
  76. typename = std::enable_if_t<LazyPermute>,
  77. typename = InvokeResult<Proj1, Proj1, T, U>>
  78. constexpr std::pair<Proj1&, Proj1&> GetProjs(priority_tag<1>) const {
  79. return {proj1_, proj1_};
  80. }
  81. template <typename T,
  82. typename U,
  83. bool LazyPermute = kPermute,
  84. typename = std::enable_if_t<LazyPermute>,
  85. typename = InvokeResult<Proj2, Proj2, T, U>>
  86. constexpr std::pair<Proj2&, Proj2&> GetProjs(priority_tag<0>) const {
  87. return {proj2_, proj2_};
  88. }
  89. public:
  90. template <typename T, typename U>
  91. constexpr bool operator()(T&& lhs, U&& rhs) const {
  92. auto projs = GetProjs<T, U>(priority_tag<3>());
  93. return base::invoke(pred_, base::invoke(projs.first, std::forward<T>(lhs)),
  94. base::invoke(projs.second, std::forward<U>(rhs)));
  95. }
  96. private:
  97. Pred& pred_;
  98. Proj1& proj1_;
  99. Proj2& proj2_;
  100. };
  101. // Small wrappers around BinaryPredicateProjector to make the calling side more
  102. // readable.
  103. template <typename Pred, typename Proj1, typename Proj2>
  104. constexpr auto ProjectedBinaryPredicate(Pred& pred,
  105. Proj1& proj1,
  106. Proj2& proj2) noexcept {
  107. return BinaryPredicateProjector<Pred, Proj1, Proj2>(pred, proj1, proj2);
  108. }
  109. template <typename Pred, typename Proj1, typename Proj2>
  110. constexpr auto PermutedProjectedBinaryPredicate(Pred& pred,
  111. Proj1& proj1,
  112. Proj2& proj2) noexcept {
  113. return BinaryPredicateProjector<Pred, Proj1, Proj2, true>(pred, proj1, proj2);
  114. }
  115. // This alias is used below to restrict iterator based APIs to types for which
  116. // `iterator_category` and the pre-increment and post-increment operators are
  117. // defined. This is required in situations where otherwise an undesired overload
  118. // would be chosen, e.g. copy_if. In spirit this is similar to C++20's
  119. // std::input_or_output_iterator, a concept that each iterator should satisfy.
  120. template <typename Iter,
  121. typename = decltype(++std::declval<Iter&>()),
  122. typename = decltype(std::declval<Iter&>()++)>
  123. using iterator_category_t =
  124. typename std::iterator_traits<Iter>::iterator_category;
  125. // This alias is used below to restrict range based APIs to types for which
  126. // `iterator_category_t` is defined for the underlying iterator. This is
  127. // required in situations where otherwise an undesired overload would be chosen,
  128. // e.g. transform. In spirit this is similar to C++20's std::ranges::range, a
  129. // concept that each range should satisfy.
  130. template <typename Range>
  131. using range_category_t = iterator_category_t<ranges::iterator_t<Range>>;
  132. } // namespace internal
  133. namespace ranges {
  134. // C++14 implementation of std::ranges::in_fun_result.
  135. //
  136. // Reference: https://wg21.link/algorithms.results#:~:text=in_fun_result
  137. template <typename I, typename F>
  138. struct in_fun_result {
  139. NO_UNIQUE_ADDRESS I in;
  140. NO_UNIQUE_ADDRESS F fun;
  141. template <typename I2,
  142. typename F2,
  143. std::enable_if_t<std::is_convertible<const I&, I2>{} &&
  144. std::is_convertible<const F&, F2>{}>>
  145. constexpr operator in_fun_result<I2, F2>() const& {
  146. return {in, fun};
  147. }
  148. template <typename I2,
  149. typename F2,
  150. std::enable_if_t<std::is_convertible<I, I2>{} &&
  151. std::is_convertible<F, F2>{}>>
  152. constexpr operator in_fun_result<I2, F2>() && {
  153. return {std::move(in), std::move(fun)};
  154. }
  155. };
  156. // TODO(crbug.com/1071094): Implement the other result types.
  157. // [alg.nonmodifying] Non-modifying sequence operations
  158. // Reference: https://wg21.link/alg.nonmodifying
  159. // [alg.all.of] All of
  160. // Reference: https://wg21.link/alg.all.of
  161. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  162. //
  163. // Returns: `false` if `E(i)` is `false` for some iterator `i` in the range
  164. // `[first, last)`, and `true` otherwise.
  165. //
  166. // Complexity: At most `last - first` applications of the predicate and any
  167. // projection.
  168. //
  169. // Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(I
  170. template <typename InputIterator,
  171. typename Pred,
  172. typename Proj = identity,
  173. typename = internal::iterator_category_t<InputIterator>>
  174. constexpr bool all_of(InputIterator first,
  175. InputIterator last,
  176. Pred pred,
  177. Proj proj = {}) {
  178. for (; first != last; ++first) {
  179. if (!base::invoke(pred, base::invoke(proj, *first)))
  180. return false;
  181. }
  182. return true;
  183. }
  184. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  185. //
  186. // Returns: `false` if `E(i)` is `false` for some iterator `i` in `range`, and
  187. // `true` otherwise.
  188. //
  189. // Complexity: At most `size(range)` applications of the predicate and any
  190. // projection.
  191. //
  192. // Reference: https://wg21.link/alg.all.of#:~:text=ranges::all_of(R
  193. template <typename Range,
  194. typename Pred,
  195. typename Proj = identity,
  196. typename = internal::range_category_t<Range>>
  197. constexpr bool all_of(Range&& range, Pred pred, Proj proj = {}) {
  198. return ranges::all_of(ranges::begin(range), ranges::end(range),
  199. std::move(pred), std::move(proj));
  200. }
  201. // [alg.any.of] Any of
  202. // Reference: https://wg21.link/alg.any.of
  203. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  204. //
  205. // Returns: `true` if `E(i)` is `true` for some iterator `i` in the range
  206. // `[first, last)`, and `false` otherwise.
  207. //
  208. // Complexity: At most `last - first` applications of the predicate and any
  209. // projection.
  210. //
  211. // Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(I
  212. template <typename InputIterator,
  213. typename Pred,
  214. typename Proj = identity,
  215. typename = internal::iterator_category_t<InputIterator>>
  216. constexpr bool any_of(InputIterator first,
  217. InputIterator last,
  218. Pred pred,
  219. Proj proj = {}) {
  220. for (; first != last; ++first) {
  221. if (base::invoke(pred, base::invoke(proj, *first)))
  222. return true;
  223. }
  224. return false;
  225. }
  226. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  227. //
  228. // Returns: `true` if `E(i)` is `true` for some iterator `i` in `range`, and
  229. // `false` otherwise.
  230. //
  231. // Complexity: At most `size(range)` applications of the predicate and any
  232. // projection.
  233. //
  234. // Reference: https://wg21.link/alg.any.of#:~:text=ranges::any_of(R
  235. template <typename Range,
  236. typename Pred,
  237. typename Proj = identity,
  238. typename = internal::range_category_t<Range>>
  239. constexpr bool any_of(Range&& range, Pred pred, Proj proj = {}) {
  240. return ranges::any_of(ranges::begin(range), ranges::end(range),
  241. std::move(pred), std::move(proj));
  242. }
  243. // [alg.none.of] None of
  244. // Reference: https://wg21.link/alg.none.of
  245. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  246. //
  247. // Returns: `false` if `E(i)` is `true` for some iterator `i` in the range
  248. // `[first, last)`, and `true` otherwise.
  249. //
  250. // Complexity: At most `last - first` applications of the predicate and any
  251. // projection.
  252. //
  253. // Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(I
  254. template <typename InputIterator,
  255. typename Pred,
  256. typename Proj = identity,
  257. typename = internal::iterator_category_t<InputIterator>>
  258. constexpr bool none_of(InputIterator first,
  259. InputIterator last,
  260. Pred pred,
  261. Proj proj = {}) {
  262. for (; first != last; ++first) {
  263. if (base::invoke(pred, base::invoke(proj, *first)))
  264. return false;
  265. }
  266. return true;
  267. }
  268. // Let `E(i)` be `invoke(pred, invoke(proj, *i))`.
  269. //
  270. // Returns: `false` if `E(i)` is `true` for some iterator `i` in `range`, and
  271. // `true` otherwise.
  272. //
  273. // Complexity: At most `size(range)` applications of the predicate and any
  274. // projection.
  275. //
  276. // Reference: https://wg21.link/alg.none.of#:~:text=ranges::none_of(R
  277. template <typename Range,
  278. typename Pred,
  279. typename Proj = identity,
  280. typename = internal::range_category_t<Range>>
  281. constexpr bool none_of(Range&& range, Pred pred, Proj proj = {}) {
  282. return ranges::none_of(ranges::begin(range), ranges::end(range),
  283. std::move(pred), std::move(proj));
  284. }
  285. // [alg.foreach] For each
  286. // Reference: https://wg21.link/alg.foreach
  287. // Reference: https://wg21.link/algorithm.syn#:~:text=for_each_result
  288. template <typename I, typename F>
  289. using for_each_result = in_fun_result<I, F>;
  290. // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
  291. // range `[first, last)`, starting from `first` and proceeding to `last - 1`.
  292. //
  293. // Returns: `{last, std::move(f)}`.
  294. //
  295. // Complexity: Applies `f` and `proj` exactly `last - first` times.
  296. //
  297. // Remarks: If `f` returns a result, the result is ignored.
  298. //
  299. // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(I
  300. template <typename InputIterator,
  301. typename Fun,
  302. typename Proj = identity,
  303. typename = internal::iterator_category_t<InputIterator>>
  304. constexpr auto for_each(InputIterator first,
  305. InputIterator last,
  306. Fun f,
  307. Proj proj = {}) {
  308. for (; first != last; ++first)
  309. base::invoke(f, base::invoke(proj, *first));
  310. return for_each_result<InputIterator, Fun>{first, std::move(f)};
  311. }
  312. // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
  313. // range `range`, starting from `begin(range)` and proceeding to `end(range) -
  314. // 1`.
  315. //
  316. // Returns: `{last, std::move(f)}`.
  317. //
  318. // Complexity: Applies `f` and `proj` exactly `size(range)` times.
  319. //
  320. // Remarks: If `f` returns a result, the result is ignored.
  321. //
  322. // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each(R
  323. template <typename Range,
  324. typename Fun,
  325. typename Proj = identity,
  326. typename = internal::range_category_t<Range>>
  327. constexpr auto for_each(Range&& range, Fun f, Proj proj = {}) {
  328. return ranges::for_each(ranges::begin(range), ranges::end(range),
  329. std::move(f), std::move(proj));
  330. }
  331. // Reference: https://wg21.link/algorithm.syn#:~:text=for_each_n_result
  332. template <typename I, typename F>
  333. using for_each_n_result = in_fun_result<I, F>;
  334. // Preconditions: `n >= 0` is `true`.
  335. //
  336. // Effects: Calls `invoke(f, invoke(proj, *i))` for every iterator `i` in the
  337. // range `[first, first + n)` in order.
  338. //
  339. // Returns: `{first + n, std::move(f)}`.
  340. //
  341. // Remarks: If `f` returns a result, the result is ignored.
  342. //
  343. // Reference: https://wg21.link/alg.foreach#:~:text=ranges::for_each_n
  344. template <typename InputIterator,
  345. typename Size,
  346. typename Fun,
  347. typename Proj = identity,
  348. typename = internal::iterator_category_t<InputIterator>>
  349. constexpr auto for_each_n(InputIterator first, Size n, Fun f, Proj proj = {}) {
  350. while (n > 0) {
  351. base::invoke(f, base::invoke(proj, *first));
  352. ++first;
  353. --n;
  354. }
  355. return for_each_n_result<InputIterator, Fun>{first, std::move(f)};
  356. }
  357. // [alg.find] Find
  358. // Reference: https://wg21.link/alg.find
  359. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  360. //
  361. // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
  362. // is `true`. Returns `last` if no such iterator is found.
  363. //
  364. // Complexity: At most `last - first` applications of the corresponding
  365. // predicate and any projection.
  366. //
  367. // Reference: https://wg21.link/alg.find#:~:text=ranges::find(I
  368. template <typename InputIterator,
  369. typename T,
  370. typename Proj = identity,
  371. typename = internal::iterator_category_t<InputIterator>>
  372. constexpr auto find(InputIterator first,
  373. InputIterator last,
  374. const T& value,
  375. Proj proj = {}) {
  376. for (; first != last; ++first) {
  377. if (base::invoke(proj, *first) == value)
  378. break;
  379. }
  380. return first;
  381. }
  382. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  383. //
  384. // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
  385. // Returns `end(range)` if no such iterator is found.
  386. //
  387. // Complexity: At most `size(range)` applications of the corresponding predicate
  388. // and any projection.
  389. //
  390. // Reference: https://wg21.link/alg.find#:~:text=ranges::find(R
  391. template <typename Range,
  392. typename T,
  393. typename Proj = identity,
  394. typename = internal::range_category_t<Range>>
  395. constexpr auto find(Range&& range, const T& value, Proj proj = {}) {
  396. return ranges::find(ranges::begin(range), ranges::end(range), value,
  397. std::move(proj));
  398. }
  399. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  400. //
  401. // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
  402. // is `true`. Returns `last` if no such iterator is found.
  403. //
  404. // Complexity: At most `last - first` applications of the corresponding
  405. // predicate and any projection.
  406. //
  407. // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(I
  408. template <typename InputIterator,
  409. typename Pred,
  410. typename Proj = identity,
  411. typename = internal::iterator_category_t<InputIterator>>
  412. constexpr auto find_if(InputIterator first,
  413. InputIterator last,
  414. Pred pred,
  415. Proj proj = {}) {
  416. return std::find_if(first, last,
  417. internal::ProjectedUnaryPredicate(pred, proj));
  418. }
  419. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  420. //
  421. // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
  422. // Returns `end(range)` if no such iterator is found.
  423. //
  424. // Complexity: At most `size(range)` applications of the corresponding predicate
  425. // and any projection.
  426. //
  427. // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if(R
  428. template <typename Range,
  429. typename Pred,
  430. typename Proj = identity,
  431. typename = internal::range_category_t<Range>>
  432. constexpr auto find_if(Range&& range, Pred pred, Proj proj = {}) {
  433. return ranges::find_if(ranges::begin(range), ranges::end(range),
  434. std::move(pred), std::move(proj));
  435. }
  436. // Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`.
  437. //
  438. // Returns: The first iterator `i` in the range `[first, last)` for which `E(i)`
  439. // is `true`. Returns `last` if no such iterator is found.
  440. //
  441. // Complexity: At most `last - first` applications of the corresponding
  442. // predicate and any projection.
  443. //
  444. // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(I
  445. template <typename InputIterator,
  446. typename Pred,
  447. typename Proj = identity,
  448. typename = internal::iterator_category_t<InputIterator>>
  449. constexpr auto find_if_not(InputIterator first,
  450. InputIterator last,
  451. Pred pred,
  452. Proj proj = {}) {
  453. return std::find_if_not(first, last,
  454. internal::ProjectedUnaryPredicate(pred, proj));
  455. }
  456. // Let `E(i)` be `bool(!invoke(pred, invoke(proj, *i)))`.
  457. //
  458. // Returns: The first iterator `i` in `range` for which `E(i)` is `true`.
  459. // Returns `end(range)` if no such iterator is found.
  460. //
  461. // Complexity: At most `size(range)` applications of the corresponding predicate
  462. // and any projection.
  463. //
  464. // Reference: https://wg21.link/alg.find#:~:text=ranges::find_if_not(R
  465. template <typename Range,
  466. typename Pred,
  467. typename Proj = identity,
  468. typename = internal::range_category_t<Range>>
  469. constexpr auto find_if_not(Range&& range, Pred pred, Proj proj = {}) {
  470. return ranges::find_if_not(ranges::begin(range), ranges::end(range),
  471. std::move(pred), std::move(proj));
  472. }
  473. // [alg.find.end] Find end
  474. // Reference: https://wg21.link/alg.find.end
  475. // Let:
  476. // - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)),
  477. // invoke(proj2, *(first2 + n)))`
  478. //
  479. // - `i` be `last1` if `[first2, last2)` is empty, or if
  480. // `(last2 - first2) > (last1 - first1)` is `true`, or if there is no iterator
  481. // in the range `[first1, last1 - (last2 - first2))` such that for every
  482. // non-negative integer `n < (last2 - first2)`, `E(i,n)` is `true`. Otherwise
  483. // `i` is the last such iterator in `[first1, last1 - (last2 - first2))`.
  484. //
  485. // Returns: `i`
  486. // Note: std::ranges::find_end(I1 first1,...) returns a range, rather than an
  487. // iterator. For simplicitly we match std::find_end's return type instead.
  488. //
  489. // Complexity:
  490. // At most `(last2 - first2) * (last1 - first1 - (last2 - first2) + 1)`
  491. // applications of the corresponding predicate and any projections.
  492. //
  493. // Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(I1
  494. template <typename ForwardIterator1,
  495. typename ForwardIterator2,
  496. typename Pred = ranges::equal_to,
  497. typename Proj1 = identity,
  498. typename Proj2 = identity,
  499. typename = internal::iterator_category_t<ForwardIterator1>,
  500. typename = internal::iterator_category_t<ForwardIterator2>,
  501. typename = indirect_result_t<Pred&,
  502. projected<ForwardIterator1, Proj1>,
  503. projected<ForwardIterator2, Proj2>>>
  504. constexpr auto find_end(ForwardIterator1 first1,
  505. ForwardIterator1 last1,
  506. ForwardIterator2 first2,
  507. ForwardIterator2 last2,
  508. Pred pred = {},
  509. Proj1 proj1 = {},
  510. Proj2 proj2 = {}) {
  511. return std::find_end(first1, last1, first2, last2,
  512. internal::ProjectedBinaryPredicate(pred, proj1, proj2));
  513. }
  514. // Let:
  515. // - `E(i,n)` be `invoke(pred, invoke(proj1, *(i + n)),
  516. // invoke(proj2, *(first2 + n)))`
  517. //
  518. // - `i` be `end(range1)` if `range2` is empty, or if
  519. // `size(range2) > size(range1)` is `true`, or if there is no iterator in the
  520. // range `[begin(range1), end(range1) - size(range2))` such that for every
  521. // non-negative integer `n < size(range2)`, `E(i,n)` is `true`. Otherwise `i`
  522. // is the last such iterator in `[begin(range1), end(range1) - size(range2))`.
  523. //
  524. // Returns: `i`
  525. // Note: std::ranges::find_end(R1&& r1,...) returns a range, rather than an
  526. // iterator. For simplicitly we match std::find_end's return type instead.
  527. //
  528. // Complexity: At most `size(range2) * (size(range1) - size(range2) + 1)`
  529. // applications of the corresponding predicate and any projections.
  530. //
  531. // Reference: https://wg21.link/alg.find.end#:~:text=ranges::find_end(R1
  532. template <typename Range1,
  533. typename Range2,
  534. typename Pred = ranges::equal_to,
  535. typename Proj1 = identity,
  536. typename Proj2 = identity,
  537. typename = internal::range_category_t<Range1>,
  538. typename = internal::range_category_t<Range2>,
  539. typename = indirect_result_t<Pred&,
  540. projected<iterator_t<Range1>, Proj1>,
  541. projected<iterator_t<Range2>, Proj2>>>
  542. constexpr auto find_end(Range1&& range1,
  543. Range2&& range2,
  544. Pred pred = {},
  545. Proj1 proj1 = {},
  546. Proj2 proj2 = {}) {
  547. return ranges::find_end(ranges::begin(range1), ranges::end(range1),
  548. ranges::begin(range2), ranges::end(range2),
  549. std::move(pred), std::move(proj1), std::move(proj2));
  550. }
  551. // [alg.find.first.of] Find first
  552. // Reference: https://wg21.link/alg.find.first.of
  553. // Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`.
  554. //
  555. // Effects: Finds an element that matches one of a set of values.
  556. //
  557. // Returns: The first iterator `i` in the range `[first1, last1)` such that for
  558. // some iterator `j` in the range `[first2, last2)` `E(i,j)` holds. Returns
  559. // `last1` if `[first2, last2)` is empty or if no such iterator is found.
  560. //
  561. // Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the
  562. // corresponding predicate and any projections.
  563. //
  564. // Reference:
  565. // https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(I1
  566. template <typename ForwardIterator1,
  567. typename ForwardIterator2,
  568. typename Pred = ranges::equal_to,
  569. typename Proj1 = identity,
  570. typename Proj2 = identity,
  571. typename = internal::iterator_category_t<ForwardIterator1>,
  572. typename = internal::iterator_category_t<ForwardIterator2>,
  573. typename = indirect_result_t<Pred&,
  574. projected<ForwardIterator1, Proj1>,
  575. projected<ForwardIterator2, Proj2>>>
  576. constexpr auto find_first_of(ForwardIterator1 first1,
  577. ForwardIterator1 last1,
  578. ForwardIterator2 first2,
  579. ForwardIterator2 last2,
  580. Pred pred = {},
  581. Proj1 proj1 = {},
  582. Proj2 proj2 = {}) {
  583. return std::find_first_of(
  584. first1, last1, first2, last2,
  585. internal::ProjectedBinaryPredicate(pred, proj1, proj2));
  586. }
  587. // Let `E(i,j)` be `bool(invoke(pred, invoke(proj1, *i), invoke(proj2, *j)))`.
  588. //
  589. // Effects: Finds an element that matches one of a set of values.
  590. //
  591. // Returns: The first iterator `i` in `range1` such that for some iterator `j`
  592. // in `range2` `E(i,j)` holds. Returns `end(range1)` if `range2` is empty or if
  593. // no such iterator is found.
  594. //
  595. // Complexity: At most `size(range1) * size(range2)` applications of the
  596. // corresponding predicate and any projections.
  597. //
  598. // Reference:
  599. // https://wg21.link/alg.find.first.of#:~:text=ranges::find_first_of(R1
  600. template <typename Range1,
  601. typename Range2,
  602. typename Pred = ranges::equal_to,
  603. typename Proj1 = identity,
  604. typename Proj2 = identity,
  605. typename = internal::range_category_t<Range1>,
  606. typename = internal::range_category_t<Range2>,
  607. typename = indirect_result_t<Pred&,
  608. projected<iterator_t<Range1>, Proj1>,
  609. projected<iterator_t<Range2>, Proj2>>>
  610. constexpr auto find_first_of(Range1&& range1,
  611. Range2&& range2,
  612. Pred pred = {},
  613. Proj1 proj1 = {},
  614. Proj2 proj2 = {}) {
  615. return ranges::find_first_of(
  616. ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
  617. ranges::end(range2), std::move(pred), std::move(proj1), std::move(proj2));
  618. }
  619. // [alg.adjacent.find] Adjacent find
  620. // Reference: https://wg21.link/alg.adjacent.find
  621. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`.
  622. //
  623. // Returns: The first iterator `i` such that both `i` and `i + 1` are in the
  624. // range `[first, last)` for which `E(i)` holds. Returns `last` if no such
  625. // iterator is found.
  626. //
  627. // Complexity: Exactly `min((i - first) + 1, (last - first) - 1)` applications
  628. // of the corresponding predicate, where `i` is `adjacent_find`'s return value.
  629. //
  630. // Reference:
  631. // https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(I
  632. template <typename ForwardIterator,
  633. typename Pred = ranges::equal_to,
  634. typename Proj = identity,
  635. typename = internal::iterator_category_t<ForwardIterator>>
  636. constexpr auto adjacent_find(ForwardIterator first,
  637. ForwardIterator last,
  638. Pred pred = {},
  639. Proj proj = {}) {
  640. // Implementation inspired by cppreference.com:
  641. // https://en.cppreference.com/w/cpp/algorithm/adjacent_find
  642. //
  643. // A reimplementation is required, because std::adjacent_find is not constexpr
  644. // prior to C++20. Once we have C++20, we should switch to standard library
  645. // implementation.
  646. if (first == last)
  647. return last;
  648. for (ForwardIterator next = first; ++next != last; ++first) {
  649. if (base::invoke(pred, base::invoke(proj, *first),
  650. base::invoke(proj, *next))) {
  651. return first;
  652. }
  653. }
  654. return last;
  655. }
  656. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i), invoke(proj, *(i + 1))))`.
  657. //
  658. // Returns: The first iterator `i` such that both `i` and `i + 1` are in the
  659. // range `range` for which `E(i)` holds. Returns `end(range)` if no such
  660. // iterator is found.
  661. //
  662. // Complexity: Exactly `min((i - begin(range)) + 1, size(range) - 1)`
  663. // applications of the corresponding predicate, where `i` is `adjacent_find`'s
  664. // return value.
  665. //
  666. // Reference:
  667. // https://wg21.link/alg.adjacent.find#:~:text=ranges::adjacent_find(R
  668. template <typename Range,
  669. typename Pred = ranges::equal_to,
  670. typename Proj = identity,
  671. typename = internal::range_category_t<Range>>
  672. constexpr auto adjacent_find(Range&& range, Pred pred = {}, Proj proj = {}) {
  673. return ranges::adjacent_find(ranges::begin(range), ranges::end(range),
  674. std::move(pred), std::move(proj));
  675. }
  676. // [alg.count] Count
  677. // Reference: https://wg21.link/alg.count
  678. // Let `E(i)` be `invoke(proj, *i) == value`.
  679. //
  680. // Effects: Returns the number of iterators `i` in the range `[first, last)` for
  681. // which `E(i)` holds.
  682. //
  683. // Complexity: Exactly `last - first` applications of the corresponding
  684. // predicate and any projection.
  685. //
  686. // Reference: https://wg21.link/alg.count#:~:text=ranges::count(I
  687. template <typename InputIterator,
  688. typename T,
  689. typename Proj = identity,
  690. typename = internal::iterator_category_t<InputIterator>>
  691. constexpr auto count(InputIterator first,
  692. InputIterator last,
  693. const T& value,
  694. Proj proj = {}) {
  695. // Note: In order to be able to apply `proj` to each element in [first, last)
  696. // we are dispatching to std::count_if instead of std::count.
  697. return std::count_if(first, last, [&proj, &value](auto&& lhs) {
  698. return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
  699. });
  700. }
  701. // Let `E(i)` be `invoke(proj, *i) == value`.
  702. //
  703. // Effects: Returns the number of iterators `i` in `range` for which `E(i)`
  704. // holds.
  705. //
  706. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  707. // and any projection.
  708. //
  709. // Reference: https://wg21.link/alg.count#:~:text=ranges::count(R
  710. template <typename Range,
  711. typename T,
  712. typename Proj = identity,
  713. typename = internal::range_category_t<Range>>
  714. constexpr auto count(Range&& range, const T& value, Proj proj = {}) {
  715. return ranges::count(ranges::begin(range), ranges::end(range), value,
  716. std::move(proj));
  717. }
  718. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  719. //
  720. // Effects: Returns the number of iterators `i` in the range `[first, last)` for
  721. // which `E(i)` holds.
  722. //
  723. // Complexity: Exactly `last - first` applications of the corresponding
  724. // predicate and any projection.
  725. //
  726. // Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(I
  727. template <typename InputIterator,
  728. typename Pred,
  729. typename Proj = identity,
  730. typename = internal::iterator_category_t<InputIterator>>
  731. constexpr auto count_if(InputIterator first,
  732. InputIterator last,
  733. Pred pred,
  734. Proj proj = {}) {
  735. return std::count_if(first, last,
  736. internal::ProjectedUnaryPredicate(pred, proj));
  737. }
  738. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  739. //
  740. // Effects: Returns the number of iterators `i` in `range` for which `E(i)`
  741. // holds.
  742. //
  743. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  744. // and any projection.
  745. //
  746. // Reference: https://wg21.link/alg.count#:~:text=ranges::count_if(R
  747. template <typename Range,
  748. typename Pred,
  749. typename Proj = identity,
  750. typename = internal::range_category_t<Range>>
  751. constexpr auto count_if(Range&& range, Pred pred, Proj proj = {}) {
  752. return ranges::count_if(ranges::begin(range), ranges::end(range),
  753. std::move(pred), std::move(proj));
  754. }
  755. // [mismatch] Mismatch
  756. // Reference: https://wg21.link/mismatch
  757. // Let `E(n)` be `!invoke(pred, invoke(proj1, *(first1 + n)),
  758. // invoke(proj2, *(first2 + n)))`.
  759. //
  760. // Let `N` be `min(last1 - first1, last2 - first2)`.
  761. //
  762. // Returns: `{ first1 + n, first2 + n }`, where `n` is the smallest integer in
  763. // `[0, N)` such that `E(n)` holds, or `N` if no such integer exists.
  764. //
  765. // Complexity: At most `N` applications of the corresponding predicate and any
  766. // projections.
  767. //
  768. // Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(I1
  769. template <typename ForwardIterator1,
  770. typename ForwardIterator2,
  771. typename Pred = ranges::equal_to,
  772. typename Proj1 = identity,
  773. typename Proj2 = identity,
  774. typename = internal::iterator_category_t<ForwardIterator1>,
  775. typename = internal::iterator_category_t<ForwardIterator2>,
  776. typename = indirect_result_t<Pred&,
  777. projected<ForwardIterator1, Proj1>,
  778. projected<ForwardIterator2, Proj2>>>
  779. constexpr auto mismatch(ForwardIterator1 first1,
  780. ForwardIterator1 last1,
  781. ForwardIterator2 first2,
  782. ForwardIterator2 last2,
  783. Pred pred = {},
  784. Proj1 proj1 = {},
  785. Proj2 proj2 = {}) {
  786. return std::mismatch(first1, last1, first2, last2,
  787. internal::ProjectedBinaryPredicate(pred, proj1, proj2));
  788. }
  789. // Let `E(n)` be `!invoke(pred, invoke(proj1, *(begin(range1) + n)),
  790. // invoke(proj2, *(begin(range2) + n)))`.
  791. //
  792. // Let `N` be `min(size(range1), size(range2))`.
  793. //
  794. // Returns: `{ begin(range1) + n, begin(range2) + n }`, where `n` is the
  795. // smallest integer in `[0, N)` such that `E(n)` holds, or `N` if no such
  796. // integer exists.
  797. //
  798. // Complexity: At most `N` applications of the corresponding predicate and any
  799. // projections.
  800. //
  801. // Reference: https://wg21.link/mismatch#:~:text=ranges::mismatch(R1
  802. template <typename Range1,
  803. typename Range2,
  804. typename Pred = ranges::equal_to,
  805. typename Proj1 = identity,
  806. typename Proj2 = identity,
  807. typename = internal::range_category_t<Range1>,
  808. typename = internal::range_category_t<Range2>,
  809. typename = indirect_result_t<Pred&,
  810. projected<iterator_t<Range1>, Proj1>,
  811. projected<iterator_t<Range2>, Proj2>>>
  812. constexpr auto mismatch(Range1&& range1,
  813. Range2&& range2,
  814. Pred pred = {},
  815. Proj1 proj1 = {},
  816. Proj2 proj2 = {}) {
  817. return ranges::mismatch(ranges::begin(range1), ranges::end(range1),
  818. ranges::begin(range2), ranges::end(range2),
  819. std::move(pred), std::move(proj1), std::move(proj2));
  820. }
  821. // [alg.equal] Equal
  822. // Reference: https://wg21.link/alg.equal
  823. // Let `E(i)` be
  824. // `invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))`.
  825. //
  826. // Returns: If `last1 - first1 != last2 - first2`, return `false.` Otherwise
  827. // return `true` if `E(i)` holds for every iterator `i` in the range `[first1,
  828. // last1)`. Otherwise, returns `false`.
  829. //
  830. // Complexity: If the types of `first1`, `last1`, `first2`, and `last2` meet the
  831. // `RandomAccessIterator` requirements and `last1 - first1 != last2 - first2`,
  832. // then no applications of the corresponding predicate and each projection;
  833. // otherwise, at most `min(last1 - first1, last2 - first2)` applications of the
  834. // corresponding predicate and any projections.
  835. //
  836. // Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(I1
  837. template <typename ForwardIterator1,
  838. typename ForwardIterator2,
  839. typename Pred = ranges::equal_to,
  840. typename Proj1 = identity,
  841. typename Proj2 = identity,
  842. typename = internal::iterator_category_t<ForwardIterator1>,
  843. typename = internal::iterator_category_t<ForwardIterator2>,
  844. typename = indirect_result_t<Pred&,
  845. projected<ForwardIterator1, Proj1>,
  846. projected<ForwardIterator2, Proj2>>>
  847. constexpr bool equal(ForwardIterator1 first1,
  848. ForwardIterator1 last1,
  849. ForwardIterator2 first2,
  850. ForwardIterator2 last2,
  851. Pred pred = {},
  852. Proj1 proj1 = {},
  853. Proj2 proj2 = {}) {
  854. if (base::is_constant_evaluated()) {
  855. for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
  856. if (!base::invoke(pred, base::invoke(proj1, *first1),
  857. base::invoke(proj2, *first2))) {
  858. return false;
  859. }
  860. }
  861. return first1 == last1 && first2 == last2;
  862. }
  863. return std::equal(first1, last1, first2, last2,
  864. internal::ProjectedBinaryPredicate(pred, proj1, proj2));
  865. }
  866. // Let `E(i)` be
  867. // `invoke(pred, invoke(proj1, *i),
  868. // invoke(proj2, *(begin(range2) + (i - begin(range1)))))`.
  869. //
  870. // Returns: If `size(range1) != size(range2)`, return `false.` Otherwise return
  871. // `true` if `E(i)` holds for every iterator `i` in `range1`. Otherwise, returns
  872. // `false`.
  873. //
  874. // Complexity: If the types of `begin(range1)`, `end(range1)`, `begin(range2)`,
  875. // and `end(range2)` meet the `RandomAccessIterator` requirements and
  876. // `size(range1) != size(range2)`, then no applications of the corresponding
  877. // predicate and each projection;
  878. // otherwise, at most `min(size(range1), size(range2))` applications of the
  879. // corresponding predicate and any projections.
  880. //
  881. // Reference: https://wg21.link/alg.equal#:~:text=ranges::equal(R1
  882. template <typename Range1,
  883. typename Range2,
  884. typename Pred = ranges::equal_to,
  885. typename Proj1 = identity,
  886. typename Proj2 = identity,
  887. typename = internal::range_category_t<Range1>,
  888. typename = internal::range_category_t<Range2>,
  889. typename = indirect_result_t<Pred&,
  890. projected<iterator_t<Range1>, Proj1>,
  891. projected<iterator_t<Range2>, Proj2>>>
  892. constexpr bool equal(Range1&& range1,
  893. Range2&& range2,
  894. Pred pred = {},
  895. Proj1 proj1 = {},
  896. Proj2 proj2 = {}) {
  897. return ranges::equal(ranges::begin(range1), ranges::end(range1),
  898. ranges::begin(range2), ranges::end(range2),
  899. std::move(pred), std::move(proj1), std::move(proj2));
  900. }
  901. // [alg.is.permutation] Is permutation
  902. // Reference: https://wg21.link/alg.is.permutation
  903. // Returns: If `last1 - first1 != last2 - first2`, return `false`. Otherwise
  904. // return `true` if there exists a permutation of the elements in the range
  905. // `[first2, last2)`, bounded by `[pfirst, plast)`, such that
  906. // `ranges::equal(first1, last1, pfirst, plast, pred, proj, proj)` returns
  907. // `true`; otherwise, returns `false`.
  908. //
  909. // Complexity: No applications of the corresponding predicate if
  910. // ForwardIterator1 and ForwardIterator2 meet the requirements of random access
  911. // iterators and `last1 - first1 != last2 - first2`. Otherwise, exactly
  912. // `last1 - first1` applications of the corresponding predicate and projections
  913. // if `ranges::equal(first1, last1, first2, last2, pred, proj, proj)` would
  914. // return true;
  915. // otherwise, at worst `O(N^2)`, where `N` has the value `last1 - first1`.
  916. //
  917. // Reference:
  918. // https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(I1
  919. template <typename ForwardIterator1,
  920. typename ForwardIterator2,
  921. typename Pred = ranges::equal_to,
  922. typename Proj1 = identity,
  923. typename Proj2 = identity,
  924. typename = internal::iterator_category_t<ForwardIterator1>,
  925. typename = internal::iterator_category_t<ForwardIterator2>,
  926. typename = indirect_result_t<Pred&,
  927. projected<ForwardIterator1, Proj1>,
  928. projected<ForwardIterator2, Proj2>>>
  929. constexpr bool is_permutation(ForwardIterator1 first1,
  930. ForwardIterator1 last1,
  931. ForwardIterator2 first2,
  932. ForwardIterator2 last2,
  933. Pred pred = {},
  934. Proj1 proj1 = {},
  935. Proj2 proj2 = {}) {
  936. // Needs to opt-in to all permutations, since std::is_permutation expects
  937. // pred(proj1(lhs), proj1(rhs)) to compile.
  938. return std::is_permutation(
  939. first1, last1, first2, last2,
  940. internal::PermutedProjectedBinaryPredicate(pred, proj1, proj2));
  941. }
  942. // Returns: If `size(range1) != size(range2)`, return `false`. Otherwise return
  943. // `true` if there exists a permutation of the elements in `range2`, bounded by
  944. // `[pbegin, pend)`, such that
  945. // `ranges::equal(range1, [pbegin, pend), pred, proj, proj)` returns `true`;
  946. // otherwise, returns `false`.
  947. //
  948. // Complexity: No applications of the corresponding predicate if Range1 and
  949. // Range2 meet the requirements of random access ranges and
  950. // `size(range1) != size(range2)`. Otherwise, exactly `size(range1)`
  951. // applications of the corresponding predicate and projections if
  952. // `ranges::equal(range1, range2, pred, proj, proj)` would return true;
  953. // otherwise, at worst `O(N^2)`, where `N` has the value `size(range1)`.
  954. //
  955. // Reference:
  956. // https://wg21.link/alg.is.permutation#:~:text=ranges::is_permutation(R1
  957. template <typename Range1,
  958. typename Range2,
  959. typename Pred = ranges::equal_to,
  960. typename Proj1 = identity,
  961. typename Proj2 = identity,
  962. typename = internal::range_category_t<Range1>,
  963. typename = internal::range_category_t<Range2>,
  964. typename = indirect_result_t<Pred&,
  965. projected<iterator_t<Range1>, Proj1>,
  966. projected<iterator_t<Range2>, Proj2>>>
  967. constexpr bool is_permutation(Range1&& range1,
  968. Range2&& range2,
  969. Pred pred = {},
  970. Proj1 proj1 = {},
  971. Proj2 proj2 = {}) {
  972. return ranges::is_permutation(
  973. ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
  974. ranges::end(range2), std::move(pred), std::move(proj1), std::move(proj2));
  975. }
  976. // [alg.search] Search
  977. // Reference: https://wg21.link/alg.search
  978. // Returns: `i`, where `i` is the first iterator in the range
  979. // `[first1, last1 - (last2 - first2))` such that for every non-negative integer
  980. // `n` less than `last2 - first2` the condition
  981. // `bool(invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(first2 + n))))`
  982. // is `true`.
  983. // Returns `last1` if no such iterator exists.
  984. // Note: std::ranges::search(I1 first1,...) returns a range, rather than an
  985. // iterator. For simplicitly we match std::search's return type instead.
  986. //
  987. // Complexity: At most `(last1 - first1) * (last2 - first2)` applications of the
  988. // corresponding predicate and projections.
  989. //
  990. // Reference: https://wg21.link/alg.search#:~:text=ranges::search(I1
  991. template <typename ForwardIterator1,
  992. typename ForwardIterator2,
  993. typename Pred = ranges::equal_to,
  994. typename Proj1 = identity,
  995. typename Proj2 = identity,
  996. typename = internal::iterator_category_t<ForwardIterator1>,
  997. typename = internal::iterator_category_t<ForwardIterator2>,
  998. typename = indirect_result_t<Pred&,
  999. projected<ForwardIterator1, Proj1>,
  1000. projected<ForwardIterator2, Proj2>>>
  1001. constexpr auto search(ForwardIterator1 first1,
  1002. ForwardIterator1 last1,
  1003. ForwardIterator2 first2,
  1004. ForwardIterator2 last2,
  1005. Pred pred = {},
  1006. Proj1 proj1 = {},
  1007. Proj2 proj2 = {}) {
  1008. return std::search(first1, last1, first2, last2,
  1009. internal::ProjectedBinaryPredicate(pred, proj1, proj2));
  1010. }
  1011. // Returns: `i`, where `i` is the first iterator in the range
  1012. // `[begin(range1), end(range1) - size(range2))` such that for every
  1013. // non-negative integer `n` less than `size(range2)` the condition
  1014. // `bool(invoke(pred, invoke(proj1, *(i + n)),
  1015. // invoke(proj2, *(begin(range2) + n))))` is `true`.
  1016. // Returns `end(range1)` if no such iterator exists.
  1017. // Note: std::ranges::search(R1&& r1,...) returns a range, rather than an
  1018. // iterator. For simplicitly we match std::search's return type instead.
  1019. //
  1020. // Complexity: At most `size(range1) * size(range2)` applications of the
  1021. // corresponding predicate and projections.
  1022. //
  1023. // Reference: https://wg21.link/alg.search#:~:text=ranges::search(R1
  1024. template <typename Range1,
  1025. typename Range2,
  1026. typename Pred = ranges::equal_to,
  1027. typename Proj1 = identity,
  1028. typename Proj2 = identity,
  1029. typename = internal::range_category_t<Range1>,
  1030. typename = internal::range_category_t<Range2>,
  1031. typename = indirect_result_t<Pred&,
  1032. projected<iterator_t<Range1>, Proj1>,
  1033. projected<iterator_t<Range2>, Proj2>>>
  1034. constexpr auto search(Range1&& range1,
  1035. Range2&& range2,
  1036. Pred pred = {},
  1037. Proj1 proj1 = {},
  1038. Proj2 proj2 = {}) {
  1039. return ranges::search(ranges::begin(range1), ranges::end(range1),
  1040. ranges::begin(range2), ranges::end(range2),
  1041. std::move(pred), std::move(proj1), std::move(proj2));
  1042. }
  1043. // Mandates: The type `Size` is convertible to an integral type.
  1044. //
  1045. // Returns: `i` where `i` is the first iterator in the range
  1046. // `[first, last - count)` such that for every non-negative integer `n` less
  1047. // than `count`, the following condition holds:
  1048. // `invoke(pred, invoke(proj, *(i + n)), value)`.
  1049. // Returns `last` if no such iterator is found.
  1050. // Note: std::ranges::search_n(I1 first1,...) returns a range, rather than an
  1051. // iterator. For simplicitly we match std::search_n's return type instead.
  1052. //
  1053. // Complexity: At most `last - first` applications of the corresponding
  1054. // predicate and projection.
  1055. //
  1056. // Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(I
  1057. template <typename ForwardIterator,
  1058. typename Size,
  1059. typename T,
  1060. typename Pred = ranges::equal_to,
  1061. typename Proj = identity,
  1062. typename = internal::iterator_category_t<ForwardIterator>>
  1063. constexpr auto search_n(ForwardIterator first,
  1064. ForwardIterator last,
  1065. Size count,
  1066. const T& value,
  1067. Pred pred = {},
  1068. Proj proj = {}) {
  1069. // The second arg is guaranteed to be `value`, so we'll simply apply the
  1070. // identity projection.
  1071. identity value_proj;
  1072. return std::search_n(
  1073. first, last, count, value,
  1074. internal::ProjectedBinaryPredicate(pred, proj, value_proj));
  1075. }
  1076. // Mandates: The type `Size` is convertible to an integral type.
  1077. //
  1078. // Returns: `i` where `i` is the first iterator in the range
  1079. // `[begin(range), end(range) - count)` such that for every non-negative integer
  1080. // `n` less than `count`, the following condition holds:
  1081. // `invoke(pred, invoke(proj, *(i + n)), value)`.
  1082. // Returns `end(arnge)` if no such iterator is found.
  1083. // Note: std::ranges::search_n(R1&& r1,...) returns a range, rather than an
  1084. // iterator. For simplicitly we match std::search_n's return type instead.
  1085. //
  1086. // Complexity: At most `size(range)` applications of the corresponding predicate
  1087. // and projection.
  1088. //
  1089. // Reference: https://wg21.link/alg.search#:~:text=ranges::search_n(R
  1090. template <typename Range,
  1091. typename Size,
  1092. typename T,
  1093. typename Pred = ranges::equal_to,
  1094. typename Proj = identity,
  1095. typename = internal::range_category_t<Range>>
  1096. constexpr auto search_n(Range&& range,
  1097. Size count,
  1098. const T& value,
  1099. Pred pred = {},
  1100. Proj proj = {}) {
  1101. return ranges::search_n(ranges::begin(range), ranges::end(range), count,
  1102. value, std::move(pred), std::move(proj));
  1103. }
  1104. // [alg.modifying.operations] Mutating sequence operations
  1105. // Reference: https://wg21.link/alg.modifying.operations
  1106. // [alg.copy] Copy
  1107. // Reference: https://wg21.link/alg.copy
  1108. // Let N be `last - first`.
  1109. //
  1110. // Preconditions: `result` is not in the range `[first, last)`.
  1111. //
  1112. // Effects: Copies elements in the range `[first, last)` into the range
  1113. // `[result, result + N)` starting from `first` and proceeding to `last`. For
  1114. // each non-negative integer `n < N` , performs `*(result + n) = *(first + n)`.
  1115. //
  1116. // Returns: `result + N`
  1117. //
  1118. // Complexity: Exactly `N` assignments.
  1119. //
  1120. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(I
  1121. template <typename InputIterator,
  1122. typename OutputIterator,
  1123. typename = internal::iterator_category_t<InputIterator>,
  1124. typename = internal::iterator_category_t<OutputIterator>>
  1125. constexpr auto copy(InputIterator first,
  1126. InputIterator last,
  1127. OutputIterator result) {
  1128. return std::copy(first, last, result);
  1129. }
  1130. // Let N be `size(range)`.
  1131. //
  1132. // Preconditions: `result` is not in `range`.
  1133. //
  1134. // Effects: Copies elements in `range` into the range `[result, result + N)`
  1135. // starting from `begin(range)` and proceeding to `end(range)`. For each
  1136. // non-negative integer `n < N` , performs
  1137. // *(result + n) = *(begin(range) + n)`.
  1138. //
  1139. // Returns: `result + N`
  1140. //
  1141. // Complexity: Exactly `N` assignments.
  1142. //
  1143. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy(R
  1144. template <typename Range,
  1145. typename OutputIterator,
  1146. typename = internal::range_category_t<Range>,
  1147. typename = internal::iterator_category_t<OutputIterator>>
  1148. constexpr auto copy(Range&& range, OutputIterator result) {
  1149. return ranges::copy(ranges::begin(range), ranges::end(range), result);
  1150. }
  1151. // Let `N` be `max(0, n)`.
  1152. //
  1153. // Mandates: The type `Size` is convertible to an integral type.
  1154. //
  1155. // Effects: For each non-negative integer `i < N`, performs
  1156. // `*(result + i) = *(first + i)`.
  1157. //
  1158. // Returns: `result + N`
  1159. //
  1160. // Complexity: Exactly `N` assignments.
  1161. //
  1162. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_n
  1163. template <typename InputIterator,
  1164. typename Size,
  1165. typename OutputIterator,
  1166. typename = internal::iterator_category_t<InputIterator>,
  1167. typename = internal::iterator_category_t<OutputIterator>>
  1168. constexpr auto copy_n(InputIterator first, Size n, OutputIterator result) {
  1169. return std::copy_n(first, n, result);
  1170. }
  1171. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number
  1172. // of iterators `i` in the range `[first, last)` for which the condition `E(i)`
  1173. // holds.
  1174. //
  1175. // Preconditions: The ranges `[first, last)` and
  1176. // `[result, result + (last - first))` do not overlap.
  1177. //
  1178. // Effects: Copies all of the elements referred to by the iterator `i` in the
  1179. // range `[first, last)` for which `E(i)` is true.
  1180. //
  1181. // Returns: `result + N`
  1182. //
  1183. // Complexity: Exactly `last - first` applications of the corresponding
  1184. // predicate and any projection.
  1185. //
  1186. // Remarks: Stable.
  1187. //
  1188. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(I
  1189. template <typename InputIterator,
  1190. typename OutputIterator,
  1191. typename Pred,
  1192. typename Proj = identity,
  1193. typename = internal::iterator_category_t<InputIterator>,
  1194. typename = internal::iterator_category_t<OutputIterator>>
  1195. constexpr auto copy_if(InputIterator first,
  1196. InputIterator last,
  1197. OutputIterator result,
  1198. Pred pred,
  1199. Proj proj = {}) {
  1200. return std::copy_if(first, last, result,
  1201. internal::ProjectedUnaryPredicate(pred, proj));
  1202. }
  1203. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`, and `N` be the number
  1204. // of iterators `i` in `range` for which the condition `E(i)` holds.
  1205. //
  1206. // Preconditions: `range` and `[result, result + size(range))` do not overlap.
  1207. //
  1208. // Effects: Copies all of the elements referred to by the iterator `i` in
  1209. // `range` for which `E(i)` is true.
  1210. //
  1211. // Returns: `result + N`
  1212. //
  1213. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  1214. // and any projection.
  1215. //
  1216. // Remarks: Stable.
  1217. //
  1218. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_if(R
  1219. template <typename Range,
  1220. typename OutputIterator,
  1221. typename Pred,
  1222. typename Proj = identity,
  1223. typename = internal::range_category_t<Range>,
  1224. typename = internal::iterator_category_t<OutputIterator>>
  1225. constexpr auto copy_if(Range&& range,
  1226. OutputIterator result,
  1227. Pred pred,
  1228. Proj proj = {}) {
  1229. return ranges::copy_if(ranges::begin(range), ranges::end(range), result,
  1230. std::move(pred), std::move(proj));
  1231. }
  1232. // Let `N` be `last - first`.
  1233. //
  1234. // Preconditions: `result` is not in the range `(first, last]`.
  1235. //
  1236. // Effects: Copies elements in the range `[first, last)` into the range
  1237. // `[result - N, result)` starting from `last - 1` and proceeding to `first`.
  1238. // For each positive integer `n ≤ N`, performs `*(result - n) = *(last - n)`.
  1239. //
  1240. // Returns: `result - N`
  1241. //
  1242. // Complexity: Exactly `N` assignments.
  1243. //
  1244. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(I1
  1245. template <typename BidirectionalIterator1,
  1246. typename BidirectionalIterator2,
  1247. typename = internal::iterator_category_t<BidirectionalIterator1>,
  1248. typename = internal::iterator_category_t<BidirectionalIterator2>>
  1249. constexpr auto copy_backward(BidirectionalIterator1 first,
  1250. BidirectionalIterator1 last,
  1251. BidirectionalIterator2 result) {
  1252. return std::copy_backward(first, last, result);
  1253. }
  1254. // Let `N` be `size(range)`.
  1255. //
  1256. // Preconditions: `result` is not in the range `(begin(range), end(range)]`.
  1257. //
  1258. // Effects: Copies elements in `range` into the range `[result - N, result)`
  1259. // starting from `end(range) - 1` and proceeding to `begin(range)`. For each
  1260. // positive integer `n ≤ N`, performs `*(result - n) = *(end(range) - n)`.
  1261. //
  1262. // Returns: `result - N`
  1263. //
  1264. // Complexity: Exactly `N` assignments.
  1265. //
  1266. // Reference: https://wg21.link/alg.copy#:~:text=ranges::copy_backward(R
  1267. template <typename Range,
  1268. typename BidirectionalIterator,
  1269. typename = internal::range_category_t<Range>,
  1270. typename = internal::iterator_category_t<BidirectionalIterator>>
  1271. constexpr auto copy_backward(Range&& range, BidirectionalIterator result) {
  1272. return ranges::copy_backward(ranges::begin(range), ranges::end(range),
  1273. result);
  1274. }
  1275. // [alg.move] Move
  1276. // Reference: https://wg21.link/alg.move
  1277. // Let `E(n)` be `std::move(*(first + n))`.
  1278. //
  1279. // Let `N` be `last - first`.
  1280. //
  1281. // Preconditions: `result` is not in the range `[first, last)`.
  1282. //
  1283. // Effects: Moves elements in the range `[first, last)` into the range `[result,
  1284. // result + N)` starting from `first` and proceeding to `last`. For each
  1285. // non-negative integer `n < N`, performs `*(result + n) = E(n)`.
  1286. //
  1287. // Returns: `result + N`
  1288. //
  1289. // Complexity: Exactly `N` assignments.
  1290. //
  1291. // Reference: https://wg21.link/alg.move#:~:text=ranges::move(I
  1292. template <typename InputIterator,
  1293. typename OutputIterator,
  1294. typename = internal::iterator_category_t<InputIterator>,
  1295. typename = internal::iterator_category_t<OutputIterator>>
  1296. constexpr auto move(InputIterator first,
  1297. InputIterator last,
  1298. OutputIterator result) {
  1299. return std::move(first, last, result);
  1300. }
  1301. // Let `E(n)` be `std::move(*(begin(range) + n))`.
  1302. //
  1303. // Let `N` be `size(range)`.
  1304. //
  1305. // Preconditions: `result` is not in `range`.
  1306. //
  1307. // Effects: Moves elements in `range` into the range `[result, result + N)`
  1308. // starting from `begin(range)` and proceeding to `end(range)`. For each
  1309. // non-negative integer `n < N`, performs `*(result + n) = E(n)`.
  1310. //
  1311. // Returns: `result + N`
  1312. //
  1313. // Complexity: Exactly `N` assignments.
  1314. //
  1315. // Reference: https://wg21.link/alg.move#:~:text=ranges::move(R
  1316. template <typename Range,
  1317. typename OutputIterator,
  1318. typename = internal::range_category_t<Range>,
  1319. typename = internal::iterator_category_t<OutputIterator>>
  1320. constexpr auto move(Range&& range, OutputIterator result) {
  1321. return ranges::move(ranges::begin(range), ranges::end(range), result);
  1322. }
  1323. // Let `E(n)` be `std::move(*(last - n))`.
  1324. //
  1325. // Let `N` be `last - first`.
  1326. //
  1327. // Preconditions: `result` is not in the range `(first, last]`.
  1328. //
  1329. // Effects: Moves elements in the range `[first, last)` into the range
  1330. // `[result - N, result)` starting from `last - 1` and proceeding to `first`.
  1331. // For each positive integer `n ≤ N`, performs `*(result - n) = E(n)`.
  1332. //
  1333. // Returns: `result - N`
  1334. //
  1335. // Complexity: Exactly `N` assignments.
  1336. //
  1337. // Reference: https://wg21.link/alg.move#:~:text=ranges::move_backward(I1
  1338. template <typename BidirectionalIterator1,
  1339. typename BidirectionalIterator2,
  1340. typename = internal::iterator_category_t<BidirectionalIterator1>,
  1341. typename = internal::iterator_category_t<BidirectionalIterator2>>
  1342. constexpr auto move_backward(BidirectionalIterator1 first,
  1343. BidirectionalIterator1 last,
  1344. BidirectionalIterator2 result) {
  1345. return std::move_backward(first, last, result);
  1346. }
  1347. // Let `E(n)` be `std::move(*(end(range) - n))`.
  1348. //
  1349. // Let `N` be `size(range)`.
  1350. //
  1351. // Preconditions: `result` is not in the range `(begin(range), end(range)]`.
  1352. //
  1353. // Effects: Moves elements in `range` into the range `[result - N, result)`
  1354. // starting from `end(range) - 1` and proceeding to `begin(range)`. For each
  1355. // positive integer `n ≤ N`, performs `*(result - n) = E(n)`.
  1356. //
  1357. // Returns: `result - N`
  1358. //
  1359. // Complexity: Exactly `N` assignments.
  1360. //
  1361. // Reference: https://wg21.link/alg.move#:~:text=ranges::move_backward(R
  1362. template <typename Range,
  1363. typename BidirectionalIterator,
  1364. typename = internal::range_category_t<Range>,
  1365. typename = internal::iterator_category_t<BidirectionalIterator>>
  1366. constexpr auto move_backward(Range&& range, BidirectionalIterator result) {
  1367. return ranges::move_backward(ranges::begin(range), ranges::end(range),
  1368. result);
  1369. }
  1370. // [alg.swap] Swap
  1371. // Reference: https://wg21.link/alg.swap
  1372. // Let `M` be `min(last1 - first1, last2 - first2)`.
  1373. //
  1374. // Preconditions: The two ranges `[first1, last1)` and `[first2, last2)` do not
  1375. // overlap. `*(first1 + n)` is swappable with `*(first2 + n)`.
  1376. //
  1377. // Effects: For each non-negative integer `n < M` performs
  1378. // `swap(*(first1 + n), *(first2 + n))`
  1379. //
  1380. // Returns: `first2 + M`
  1381. //
  1382. // Complexity: Exactly `M` swaps.
  1383. //
  1384. // Reference: https://wg21.link/alg.swap#:~:text=ranges::swap_ranges(I1
  1385. template <typename ForwardIterator1,
  1386. typename ForwardIterator2,
  1387. typename = internal::iterator_category_t<ForwardIterator1>,
  1388. typename = internal::iterator_category_t<ForwardIterator2>>
  1389. constexpr auto swap_ranges(ForwardIterator1 first1,
  1390. ForwardIterator1 last1,
  1391. ForwardIterator2 first2,
  1392. ForwardIterator2 last2) {
  1393. // std::swap_ranges does not have a `last2` overload. Thus we need to
  1394. // adjust `last1` to ensure to not read past `last2`.
  1395. last1 = std::next(first1, std::min(std::distance(first1, last1),
  1396. std::distance(first2, last2)));
  1397. return std::swap_ranges(first1, last1, first2);
  1398. }
  1399. // Let `M` be `min(size(range1), size(range2))`.
  1400. //
  1401. // Preconditions: The two ranges `range1` and `range2` do not overlap.
  1402. // `*(begin(range1) + n)` is swappable with `*(begin(range2) + n)`.
  1403. //
  1404. // Effects: For each non-negative integer `n < M` performs
  1405. // `swap(*(begin(range1) + n), *(begin(range2) + n))`
  1406. //
  1407. // Returns: `begin(range2) + M`
  1408. //
  1409. // Complexity: Exactly `M` swaps.
  1410. //
  1411. // Reference: https://wg21.link/alg.swap#:~:text=ranges::swap_ranges(R1
  1412. template <typename Range1,
  1413. typename Range2,
  1414. typename = internal::range_category_t<Range1>,
  1415. typename = internal::range_category_t<Range2>>
  1416. constexpr auto swap_ranges(Range1&& range1, Range2&& range2) {
  1417. return ranges::swap_ranges(ranges::begin(range1), ranges::end(range1),
  1418. ranges::begin(range2), ranges::end(range2));
  1419. }
  1420. // [alg.transform] Transform
  1421. // Reference: https://wg21.link/alg.transform
  1422. // Let `N` be `last1 - first1`,
  1423. // `E(i)` be `invoke(op, invoke(proj, *(first1 + (i - result))))`.
  1424. //
  1425. // Preconditions: `op` does not invalidate iterators or subranges, nor modify
  1426. // elements in the ranges `[first1, first1 + N]`, and `[result, result + N]`.
  1427. //
  1428. // Effects: Assigns through every iterator `i` in the range
  1429. // `[result, result + N)` a new corresponding value equal to `E(i)`.
  1430. //
  1431. // Returns: `result + N`
  1432. //
  1433. // Complexity: Exactly `N` applications of `op` and any projections.
  1434. //
  1435. // Remarks: result may be equal to `first1`.
  1436. //
  1437. // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(I
  1438. template <typename InputIterator,
  1439. typename OutputIterator,
  1440. typename UnaryOperation,
  1441. typename Proj = identity,
  1442. typename = internal::iterator_category_t<InputIterator>,
  1443. typename = internal::iterator_category_t<OutputIterator>,
  1444. typename = indirect_result_t<UnaryOperation&,
  1445. projected<InputIterator, Proj>>>
  1446. constexpr auto transform(InputIterator first1,
  1447. InputIterator last1,
  1448. OutputIterator result,
  1449. UnaryOperation op,
  1450. Proj proj = {}) {
  1451. return std::transform(first1, last1, result, [&op, &proj](auto&& arg) {
  1452. return base::invoke(op,
  1453. base::invoke(proj, std::forward<decltype(arg)>(arg)));
  1454. });
  1455. }
  1456. // Let `N` be `size(range)`,
  1457. // `E(i)` be `invoke(op, invoke(proj, *(begin(range) + (i - result))))`.
  1458. //
  1459. // Preconditions: `op` does not invalidate iterators or subranges, nor modify
  1460. // elements in the ranges `[begin(range), end(range)]`, and
  1461. // `[result, result + N]`.
  1462. //
  1463. // Effects: Assigns through every iterator `i` in the range
  1464. // `[result, result + N)` a new corresponding value equal to `E(i)`.
  1465. //
  1466. // Returns: `result + N`
  1467. //
  1468. // Complexity: Exactly `N` applications of `op` and any projections.
  1469. //
  1470. // Remarks: result may be equal to `begin(range)`.
  1471. //
  1472. // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(R
  1473. template <typename Range,
  1474. typename OutputIterator,
  1475. typename UnaryOperation,
  1476. typename Proj = identity,
  1477. typename = internal::range_category_t<Range>,
  1478. typename = internal::iterator_category_t<OutputIterator>,
  1479. typename = indirect_result_t<UnaryOperation&,
  1480. projected<iterator_t<Range>, Proj>>>
  1481. constexpr auto transform(Range&& range,
  1482. OutputIterator result,
  1483. UnaryOperation op,
  1484. Proj proj = {}) {
  1485. return ranges::transform(ranges::begin(range), ranges::end(range), result,
  1486. std::move(op), std::move(proj));
  1487. }
  1488. // Let:
  1489. // `N` be `min(last1 - first1, last2 - first2)`,
  1490. // `E(i)` be `invoke(binary_op, invoke(proj1, *(first1 + (i - result))),
  1491. // invoke(proj2, *(first2 + (i - result))))`.
  1492. //
  1493. // Preconditions: `binary_op` does not invalidate iterators or subranges, nor
  1494. // modify elements in the ranges `[first1, first1 + N]`, `[first2, first2 + N]`,
  1495. // and `[result, result + N]`.
  1496. //
  1497. // Effects: Assigns through every iterator `i` in the range
  1498. // `[result, result + N)` a new corresponding value equal to `E(i)`.
  1499. //
  1500. // Returns: `result + N`
  1501. //
  1502. // Complexity: Exactly `N` applications of `binary_op`, and any projections.
  1503. //
  1504. // Remarks: `result` may be equal to `first1` or `first2`.
  1505. //
  1506. // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(I1
  1507. template <typename ForwardIterator1,
  1508. typename ForwardIterator2,
  1509. typename OutputIterator,
  1510. typename BinaryOperation,
  1511. typename Proj1 = identity,
  1512. typename Proj2 = identity,
  1513. typename = internal::iterator_category_t<ForwardIterator1>,
  1514. typename = internal::iterator_category_t<ForwardIterator2>,
  1515. typename = internal::iterator_category_t<OutputIterator>,
  1516. typename = indirect_result_t<BinaryOperation&,
  1517. projected<ForwardIterator1, Proj1>,
  1518. projected<ForwardIterator2, Proj2>>>
  1519. constexpr auto transform(ForwardIterator1 first1,
  1520. ForwardIterator1 last1,
  1521. ForwardIterator2 first2,
  1522. ForwardIterator2 last2,
  1523. OutputIterator result,
  1524. BinaryOperation binary_op,
  1525. Proj1 proj1 = {},
  1526. Proj2 proj2 = {}) {
  1527. // std::transform does not have a `last2` overload. Thus we need to adjust
  1528. // `last1` to ensure to not read past `last2`.
  1529. last1 = std::next(first1, std::min(std::distance(first1, last1),
  1530. std::distance(first2, last2)));
  1531. return std::transform(
  1532. first1, last1, first2, result,
  1533. [&binary_op, &proj1, &proj2](auto&& lhs, auto&& rhs) {
  1534. return base::invoke(
  1535. binary_op, base::invoke(proj1, std::forward<decltype(lhs)>(lhs)),
  1536. base::invoke(proj2, std::forward<decltype(rhs)>(rhs)));
  1537. });
  1538. }
  1539. // Let:
  1540. // `N` be `min(size(range1), size(range2)`,
  1541. // `E(i)` be `invoke(binary_op, invoke(proj1, *(begin(range1) + (i - result))),
  1542. // invoke(proj2, *(begin(range2) + (i - result))))`
  1543. //
  1544. // Preconditions: `binary_op` does not invalidate iterators or subranges, nor
  1545. // modify elements in the ranges `[begin(range1), end(range1)]`,
  1546. // `[begin(range2), end(range2)]`, and `[result, result + N]`.
  1547. //
  1548. // Effects: Assigns through every iterator `i` in the range
  1549. // `[result, result + N)` a new corresponding value equal to `E(i)`.
  1550. //
  1551. // Returns: `result + N`
  1552. //
  1553. // Complexity: Exactly `N` applications of `binary_op`, and any projections.
  1554. //
  1555. // Remarks: `result` may be equal to `begin(range1)` or `begin(range2)`.
  1556. //
  1557. // Reference: https://wg21.link/alg.transform#:~:text=ranges::transform(R1
  1558. template <typename Range1,
  1559. typename Range2,
  1560. typename OutputIterator,
  1561. typename BinaryOperation,
  1562. typename Proj1 = identity,
  1563. typename Proj2 = identity,
  1564. typename = internal::range_category_t<Range1>,
  1565. typename = internal::range_category_t<Range2>,
  1566. typename = internal::iterator_category_t<OutputIterator>,
  1567. typename = indirect_result_t<BinaryOperation&,
  1568. projected<iterator_t<Range1>, Proj1>,
  1569. projected<iterator_t<Range2>, Proj2>>>
  1570. constexpr auto transform(Range1&& range1,
  1571. Range2&& range2,
  1572. OutputIterator result,
  1573. BinaryOperation binary_op,
  1574. Proj1 proj1 = {},
  1575. Proj2 proj2 = {}) {
  1576. return ranges::transform(ranges::begin(range1), ranges::end(range1),
  1577. ranges::begin(range2), ranges::end(range2), result,
  1578. std::move(binary_op), std::move(proj1),
  1579. std::move(proj2));
  1580. }
  1581. // [alg.replace] Replace
  1582. // Reference: https://wg21.link/alg.replace
  1583. // Let `E(i)` be `bool(invoke(proj, *i) == old_value)`.
  1584. //
  1585. // Mandates: `new_value` is writable to `first`.
  1586. //
  1587. // Effects: Substitutes elements referred by the iterator `i` in the range
  1588. // `[first, last)` with `new_value`, when `E(i)` is true.
  1589. //
  1590. // Returns: `last`
  1591. //
  1592. // Complexity: Exactly `last - first` applications of the corresponding
  1593. // predicate and any projection.
  1594. //
  1595. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace(I
  1596. template <typename ForwardIterator,
  1597. typename T,
  1598. typename Proj = identity,
  1599. typename = internal::iterator_category_t<ForwardIterator>>
  1600. constexpr auto replace(ForwardIterator first,
  1601. ForwardIterator last,
  1602. const T& old_value,
  1603. const T& new_value,
  1604. Proj proj = {}) {
  1605. // Note: In order to be able to apply `proj` to each element in [first, last)
  1606. // we are dispatching to std::replace_if instead of std::replace.
  1607. std::replace_if(
  1608. first, last,
  1609. [&proj, &old_value](auto&& lhs) {
  1610. return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) ==
  1611. old_value;
  1612. },
  1613. new_value);
  1614. return last;
  1615. }
  1616. // Let `E(i)` be `bool(invoke(proj, *i) == old_value)`.
  1617. //
  1618. // Mandates: `new_value` is writable to `begin(range)`.
  1619. //
  1620. // Effects: Substitutes elements referred by the iterator `i` in `range` with
  1621. // `new_value`, when `E(i)` is true.
  1622. //
  1623. // Returns: `end(range)`
  1624. //
  1625. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  1626. // and any projection.
  1627. //
  1628. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace(R
  1629. template <typename Range,
  1630. typename T,
  1631. typename Proj = identity,
  1632. typename = internal::range_category_t<Range>>
  1633. constexpr auto replace(Range&& range,
  1634. const T& old_value,
  1635. const T& new_value,
  1636. Proj proj = {}) {
  1637. return ranges::replace(ranges::begin(range), ranges::end(range), old_value,
  1638. new_value, std::move(proj));
  1639. }
  1640. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  1641. //
  1642. // Mandates: `new_value` is writable to `first`.
  1643. //
  1644. // Effects: Substitutes elements referred by the iterator `i` in the range
  1645. // `[first, last)` with `new_value`, when `E(i)` is true.
  1646. //
  1647. // Returns: `last`
  1648. //
  1649. // Complexity: Exactly `last - first` applications of the corresponding
  1650. // predicate and any projection.
  1651. //
  1652. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_if(I
  1653. template <typename ForwardIterator,
  1654. typename Predicate,
  1655. typename T,
  1656. typename Proj = identity,
  1657. typename = internal::iterator_category_t<ForwardIterator>>
  1658. constexpr auto replace_if(ForwardIterator first,
  1659. ForwardIterator last,
  1660. Predicate pred,
  1661. const T& new_value,
  1662. Proj proj = {}) {
  1663. std::replace_if(first, last, internal::ProjectedUnaryPredicate(pred, proj),
  1664. new_value);
  1665. return last;
  1666. }
  1667. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  1668. //
  1669. // Mandates: `new_value` is writable to `begin(range)`.
  1670. //
  1671. // Effects: Substitutes elements referred by the iterator `i` in `range` with
  1672. // `new_value`, when `E(i)` is true.
  1673. //
  1674. // Returns: `end(range)`
  1675. //
  1676. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  1677. // and any projection.
  1678. //
  1679. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_if(R
  1680. template <typename Range,
  1681. typename Predicate,
  1682. typename T,
  1683. typename Proj = identity,
  1684. typename = internal::range_category_t<Range>>
  1685. constexpr auto replace_if(Range&& range,
  1686. Predicate pred,
  1687. const T& new_value,
  1688. Proj proj = {}) {
  1689. return ranges::replace_if(ranges::begin(range), ranges::end(range),
  1690. std::move(pred), new_value, std::move(proj));
  1691. }
  1692. // Let `E(i)` be `bool(invoke(proj, *(first + (i - result))) == old_value)`.
  1693. //
  1694. // Mandates: The results of the expressions `*first` and `new_value` are
  1695. // writable to `result`.
  1696. //
  1697. // Preconditions: The ranges `[first, last)` and `[result, result + (last -
  1698. // first))` do not overlap.
  1699. //
  1700. // Effects: Assigns through every iterator `i` in the range `[result, result +
  1701. // (last - first))` a new corresponding value, `new_value` if `E(i)` is true, or
  1702. // `*(first + (i - result))` otherwise.
  1703. //
  1704. // Returns: `result + (last - first)`.
  1705. //
  1706. // Complexity: Exactly `last - first` applications of the corresponding
  1707. // predicate and any projection.
  1708. //
  1709. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy(I
  1710. template <typename InputIterator,
  1711. typename OutputIterator,
  1712. typename T,
  1713. typename Proj = identity,
  1714. typename = internal::iterator_category_t<InputIterator>,
  1715. typename = internal::iterator_category_t<OutputIterator>>
  1716. constexpr auto replace_copy(InputIterator first,
  1717. InputIterator last,
  1718. OutputIterator result,
  1719. const T& old_value,
  1720. const T& new_value,
  1721. Proj proj = {}) {
  1722. // Note: In order to be able to apply `proj` to each element in [first, last)
  1723. // we are dispatching to std::replace_copy_if instead of std::replace_copy.
  1724. std::replace_copy_if(
  1725. first, last, result,
  1726. [&proj, &old_value](auto&& lhs) {
  1727. return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) ==
  1728. old_value;
  1729. },
  1730. new_value);
  1731. return last;
  1732. }
  1733. // Let `E(i)` be
  1734. // `bool(invoke(proj, *(begin(range) + (i - result))) == old_value)`.
  1735. //
  1736. // Mandates: The results of the expressions `*begin(range)` and `new_value` are
  1737. // writable to `result`.
  1738. //
  1739. // Preconditions: The ranges `range` and `[result, result + size(range))` do not
  1740. // overlap.
  1741. //
  1742. // Effects: Assigns through every iterator `i` in the range `[result, result +
  1743. // size(range))` a new corresponding value, `new_value` if `E(i)` is true, or
  1744. // `*(begin(range) + (i - result))` otherwise.
  1745. //
  1746. // Returns: `result + size(range)`.
  1747. //
  1748. // Complexity: Exactly `size(range)` applications of the corresponding
  1749. // predicate and any projection.
  1750. //
  1751. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy(R
  1752. template <typename Range,
  1753. typename OutputIterator,
  1754. typename T,
  1755. typename Proj = identity,
  1756. typename = internal::range_category_t<Range>,
  1757. typename = internal::iterator_category_t<OutputIterator>>
  1758. constexpr auto replace_copy(Range&& range,
  1759. OutputIterator result,
  1760. const T& old_value,
  1761. const T& new_value,
  1762. Proj proj = {}) {
  1763. return ranges::replace_copy(ranges::begin(range), ranges::end(range), result,
  1764. old_value, new_value, std::move(proj));
  1765. }
  1766. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *(first + (i - result)))))`.
  1767. //
  1768. // Mandates: The results of the expressions `*first` and `new_value` are
  1769. // writable to `result`.
  1770. //
  1771. // Preconditions: The ranges `[first, last)` and `[result, result + (last -
  1772. // first))` do not overlap.
  1773. //
  1774. // Effects: Assigns through every iterator `i` in the range `[result, result +
  1775. // (last - first))` a new corresponding value, `new_value` if `E(i)` is true, or
  1776. // `*(first + (i - result))` otherwise.
  1777. //
  1778. // Returns: `result + (last - first)`.
  1779. //
  1780. // Complexity: Exactly `last - first` applications of the corresponding
  1781. // predicate and any projection.
  1782. //
  1783. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy_if(I
  1784. template <typename InputIterator,
  1785. typename OutputIterator,
  1786. typename Predicate,
  1787. typename T,
  1788. typename Proj = identity,
  1789. typename = internal::iterator_category_t<InputIterator>,
  1790. typename = internal::iterator_category_t<OutputIterator>>
  1791. constexpr auto replace_copy_if(InputIterator first,
  1792. InputIterator last,
  1793. OutputIterator result,
  1794. Predicate pred,
  1795. const T& new_value,
  1796. Proj proj = {}) {
  1797. return std::replace_copy_if(first, last, result,
  1798. internal::ProjectedUnaryPredicate(pred, proj),
  1799. new_value);
  1800. }
  1801. // Let `E(i)` be
  1802. // `bool(invoke(pred, invoke(proj, *(begin(range) + (i - result)))))`.
  1803. //
  1804. // Mandates: The results of the expressions `*begin(range)` and `new_value` are
  1805. // writable to `result`.
  1806. //
  1807. // Preconditions: The ranges `range` and `[result, result + size(range))` do not
  1808. // overlap.
  1809. //
  1810. // Effects: Assigns through every iterator `i` in the range `[result, result +
  1811. // size(range))` a new corresponding value, `new_value` if `E(i)` is true, or
  1812. // `*(begin(range) + (i - result))` otherwise.
  1813. //
  1814. // Returns: `result + size(range)`.
  1815. //
  1816. // Complexity: Exactly `size(range)` applications of the corresponding
  1817. // predicate and any projection.
  1818. //
  1819. // Reference: https://wg21.link/alg.replace#:~:text=ranges::replace_copy_if(R
  1820. template <typename Range,
  1821. typename OutputIterator,
  1822. typename Predicate,
  1823. typename T,
  1824. typename Proj = identity,
  1825. typename = internal::range_category_t<Range>,
  1826. typename = internal::iterator_category_t<OutputIterator>>
  1827. constexpr auto replace_copy_if(Range&& range,
  1828. OutputIterator result,
  1829. Predicate pred,
  1830. const T& new_value,
  1831. Proj proj = {}) {
  1832. return ranges::replace_copy_if(ranges::begin(range), ranges::end(range),
  1833. result, pred, new_value, std::move(proj));
  1834. }
  1835. // [alg.fill] Fill
  1836. // Reference: https://wg21.link/alg.fill
  1837. // Let `N` be `last - first`.
  1838. //
  1839. // Mandates: The expression `value` is writable to the output iterator.
  1840. //
  1841. // Effects: Assigns `value` through all the iterators in the range
  1842. // `[first, last)`.
  1843. //
  1844. // Returns: `last`.
  1845. //
  1846. // Complexity: Exactly `N` assignments.
  1847. //
  1848. // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill(O
  1849. template <typename OutputIterator,
  1850. typename T,
  1851. typename = internal::iterator_category_t<OutputIterator>>
  1852. constexpr auto fill(OutputIterator first, OutputIterator last, const T& value) {
  1853. std::fill(first, last, value);
  1854. return last;
  1855. }
  1856. // Let `N` be `size(range)`.
  1857. //
  1858. // Mandates: The expression `value` is writable to the output iterator.
  1859. //
  1860. // Effects: Assigns `value` through all the iterators in `range`.
  1861. //
  1862. // Returns: `end(range)`.
  1863. //
  1864. // Complexity: Exactly `N` assignments.
  1865. //
  1866. // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill(R
  1867. template <typename Range,
  1868. typename T,
  1869. typename = internal::range_category_t<Range>>
  1870. constexpr auto fill(Range&& range, const T& value) {
  1871. return ranges::fill(ranges::begin(range), ranges::end(range), value);
  1872. }
  1873. // Let `N` be `max(0, n)`.
  1874. //
  1875. // Mandates: The expression `value` is writable to the output iterator.
  1876. // The type `Size` is convertible to an integral type.
  1877. //
  1878. // Effects: Assigns `value` through all the iterators in `[first, first + N)`.
  1879. //
  1880. // Returns: `first + N`.
  1881. //
  1882. // Complexity: Exactly `N` assignments.
  1883. //
  1884. // Reference: https://wg21.link/alg.fill#:~:text=ranges::fill_n(O
  1885. template <typename OutputIterator,
  1886. typename Size,
  1887. typename T,
  1888. typename = internal::iterator_category_t<OutputIterator>>
  1889. constexpr auto fill_n(OutputIterator first, Size n, const T& value) {
  1890. return std::fill_n(first, n, value);
  1891. }
  1892. // [alg.generate] Generate
  1893. // Reference: https://wg21.link/alg.generate
  1894. // Let `N` be `last - first`.
  1895. //
  1896. // Effects: Assigns the result of successive evaluations of gen() through each
  1897. // iterator in the range `[first, last)`.
  1898. //
  1899. // Returns: `last`.
  1900. //
  1901. // Complexity: Exactly `N` evaluations of `gen()` and assignments.
  1902. //
  1903. // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate(O
  1904. template <typename OutputIterator,
  1905. typename Generator,
  1906. typename = internal::iterator_category_t<OutputIterator>>
  1907. constexpr auto generate(OutputIterator first,
  1908. OutputIterator last,
  1909. Generator gen) {
  1910. std::generate(first, last, std::move(gen));
  1911. return last;
  1912. }
  1913. // Let `N` be `size(range)`.
  1914. //
  1915. // Effects: Assigns the result of successive evaluations of gen() through each
  1916. // iterator in `range`.
  1917. //
  1918. // Returns: `end(range)`.
  1919. //
  1920. // Complexity: Exactly `N` evaluations of `gen()` and assignments.
  1921. //
  1922. // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate(R
  1923. template <typename Range,
  1924. typename Generator,
  1925. typename = internal::range_category_t<Range>>
  1926. constexpr auto generate(Range&& range, Generator gen) {
  1927. return ranges::generate(ranges::begin(range), ranges::end(range),
  1928. std::move(gen));
  1929. }
  1930. // Let `N` be `max(0, n)`.
  1931. //
  1932. // Mandates: `Size` is convertible to an integral type.
  1933. //
  1934. // Effects: Assigns the result of successive evaluations of gen() through each
  1935. // iterator in the range `[first, first + N)`.
  1936. //
  1937. // Returns: `first + N`.
  1938. //
  1939. // Complexity: Exactly `N` evaluations of `gen()` and assignments.
  1940. //
  1941. // Reference: https://wg21.link/alg.generate#:~:text=ranges::generate_n(O
  1942. template <typename OutputIterator,
  1943. typename Size,
  1944. typename Generator,
  1945. typename = internal::iterator_category_t<OutputIterator>>
  1946. constexpr auto generate_n(OutputIterator first, Size n, Generator gen) {
  1947. return std::generate_n(first, n, std::move(gen));
  1948. }
  1949. // [alg.remove] Remove
  1950. // Reference: https://wg21.link/alg.remove
  1951. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  1952. //
  1953. // Effects: Eliminates all the elements referred to by iterator `i` in the range
  1954. // `[first, last)` for which `E(i)` holds.
  1955. //
  1956. // Returns: The end of the resulting range.
  1957. //
  1958. // Remarks: Stable.
  1959. //
  1960. // Complexity: Exactly `last - first` applications of the corresponding
  1961. // predicate and any projection.
  1962. //
  1963. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove(I
  1964. template <typename ForwardIterator,
  1965. typename T,
  1966. typename Proj = identity,
  1967. typename = internal::iterator_category_t<ForwardIterator>>
  1968. constexpr auto remove(ForwardIterator first,
  1969. ForwardIterator last,
  1970. const T& value,
  1971. Proj proj = {}) {
  1972. // Note: In order to be able to apply `proj` to each element in [first, last)
  1973. // we are dispatching to std::remove_if instead of std::remove.
  1974. return std::remove_if(first, last, [&proj, &value](auto&& lhs) {
  1975. return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
  1976. });
  1977. }
  1978. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  1979. //
  1980. // Effects: Eliminates all the elements referred to by iterator `i` in `range`
  1981. // for which `E(i)` holds.
  1982. //
  1983. // Returns: The end of the resulting range.
  1984. //
  1985. // Remarks: Stable.
  1986. //
  1987. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  1988. // and any projection.
  1989. //
  1990. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove(R
  1991. template <typename Range,
  1992. typename T,
  1993. typename Proj = identity,
  1994. typename = internal::range_category_t<Range>>
  1995. constexpr auto remove(Range&& range, const T& value, Proj proj = {}) {
  1996. return ranges::remove(ranges::begin(range), ranges::end(range), value,
  1997. std::move(proj));
  1998. }
  1999. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  2000. //
  2001. // Effects: Eliminates all the elements referred to by iterator `i` in the range
  2002. // `[first, last)` for which `E(i)` holds.
  2003. //
  2004. // Returns: The end of the resulting range.
  2005. //
  2006. // Remarks: Stable.
  2007. //
  2008. // Complexity: Exactly `last - first` applications of the corresponding
  2009. // predicate and any projection.
  2010. //
  2011. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_if(I
  2012. template <typename ForwardIterator,
  2013. typename Predicate,
  2014. typename Proj = identity,
  2015. typename = internal::iterator_category_t<ForwardIterator>>
  2016. constexpr auto remove_if(ForwardIterator first,
  2017. ForwardIterator last,
  2018. Predicate pred,
  2019. Proj proj = {}) {
  2020. return std::remove_if(first, last,
  2021. internal::ProjectedUnaryPredicate(pred, proj));
  2022. }
  2023. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  2024. //
  2025. // Effects: Eliminates all the elements referred to by iterator `i` in `range`.
  2026. //
  2027. // Returns: The end of the resulting range.
  2028. //
  2029. // Remarks: Stable.
  2030. //
  2031. // Complexity: Exactly `size(range)` applications of the corresponding predicate
  2032. // and any projection.
  2033. //
  2034. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_if(R
  2035. template <typename Range,
  2036. typename Predicate,
  2037. typename Proj = identity,
  2038. typename = internal::range_category_t<Range>>
  2039. constexpr auto remove_if(Range&& range, Predicate pred, Proj proj = {}) {
  2040. return ranges::remove_if(ranges::begin(range), ranges::end(range),
  2041. std::move(pred), std::move(proj));
  2042. }
  2043. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  2044. //
  2045. // Let `N` be the number of elements in `[first, last)` for which `E(i)` is
  2046. // false.
  2047. //
  2048. // Mandates: `*first` is writable to `result`.
  2049. //
  2050. // Preconditions: The ranges `[first, last)` and `[result, result + (last -
  2051. // first))` do not overlap.
  2052. //
  2053. // Effects: Copies all the elements referred to by the iterator `i` in the range
  2054. // `[first, last)` for which `E(i)` is false.
  2055. //
  2056. // Returns: `result + N`.
  2057. //
  2058. // Complexity: Exactly `last - first` applications of the corresponding
  2059. // predicate and any projection.
  2060. //
  2061. // Remarks: Stable.
  2062. //
  2063. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(I
  2064. template <typename InputIterator,
  2065. typename OutputIterator,
  2066. typename T,
  2067. typename Proj = identity,
  2068. typename = internal::iterator_category_t<InputIterator>,
  2069. typename = internal::iterator_category_t<OutputIterator>>
  2070. constexpr auto remove_copy(InputIterator first,
  2071. InputIterator last,
  2072. OutputIterator result,
  2073. const T& value,
  2074. Proj proj = {}) {
  2075. // Note: In order to be able to apply `proj` to each element in [first, last)
  2076. // we are dispatching to std::remove_copy_if instead of std::remove_copy.
  2077. return std::remove_copy_if(first, last, result, [&proj, &value](auto&& lhs) {
  2078. return base::invoke(proj, std::forward<decltype(lhs)>(lhs)) == value;
  2079. });
  2080. }
  2081. // Let `E(i)` be `bool(invoke(proj, *i) == value)`.
  2082. //
  2083. // Let `N` be the number of elements in `range` for which `E(i)` is false.
  2084. //
  2085. // Mandates: `*begin(range)` is writable to `result`.
  2086. //
  2087. // Preconditions: The ranges `range` and `[result, result + size(range))` do not
  2088. // overlap.
  2089. //
  2090. // Effects: Copies all the elements referred to by the iterator `i` in `range`
  2091. // for which `E(i)` is false.
  2092. //
  2093. // Returns: `result + N`.
  2094. //
  2095. // Complexity: Exactly `size(range)` applications of the corresponding
  2096. // predicate and any projection.
  2097. //
  2098. // Remarks: Stable.
  2099. //
  2100. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(R
  2101. template <typename Range,
  2102. typename OutputIterator,
  2103. typename T,
  2104. typename Proj = identity,
  2105. typename = internal::range_category_t<Range>,
  2106. typename = internal::iterator_category_t<OutputIterator>>
  2107. constexpr auto remove_copy(Range&& range,
  2108. OutputIterator result,
  2109. const T& value,
  2110. Proj proj = {}) {
  2111. return ranges::remove_copy(ranges::begin(range), ranges::end(range), result,
  2112. value, std::move(proj));
  2113. }
  2114. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  2115. //
  2116. // Let `N` be the number of elements in `[first, last)` for which `E(i)` is
  2117. // false.
  2118. //
  2119. // Mandates: `*first` is writable to `result`.
  2120. //
  2121. // Preconditions: The ranges `[first, last)` and `[result, result + (last -
  2122. // first))` do not overlap.
  2123. //
  2124. // Effects: Copies all the elements referred to by the iterator `i` in the range
  2125. // `[first, last)` for which `E(i)` is false.
  2126. //
  2127. // Returns: `result + N`.
  2128. //
  2129. // Complexity: Exactly `last - first` applications of the corresponding
  2130. // predicate and any projection.
  2131. //
  2132. // Remarks: Stable.
  2133. //
  2134. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy_if(I
  2135. template <typename InputIterator,
  2136. typename OutputIterator,
  2137. typename Pred,
  2138. typename Proj = identity,
  2139. typename = internal::iterator_category_t<InputIterator>,
  2140. typename = internal::iterator_category_t<OutputIterator>>
  2141. constexpr auto remove_copy_if(InputIterator first,
  2142. InputIterator last,
  2143. OutputIterator result,
  2144. Pred pred,
  2145. Proj proj = {}) {
  2146. return std::remove_copy_if(first, last, result,
  2147. internal::ProjectedUnaryPredicate(pred, proj));
  2148. }
  2149. // Let `E(i)` be `bool(invoke(pred, invoke(proj, *i)))`.
  2150. //
  2151. // Let `N` be the number of elements in `range` for which `E(i)` is false.
  2152. //
  2153. // Mandates: `*begin(range)` is writable to `result`.
  2154. //
  2155. // Preconditions: The ranges `range` and `[result, result + size(range))` do not
  2156. // overlap.
  2157. //
  2158. // Effects: Copies all the elements referred to by the iterator `i` in `range`
  2159. // for which `E(i)` is false.
  2160. //
  2161. // Returns: `result + N`.
  2162. //
  2163. // Complexity: Exactly `size(range)` applications of the corresponding
  2164. // predicate and any projection.
  2165. //
  2166. // Remarks: Stable.
  2167. //
  2168. // Reference: https://wg21.link/alg.remove#:~:text=ranges::remove_copy(R
  2169. template <typename Range,
  2170. typename OutputIterator,
  2171. typename Pred,
  2172. typename Proj = identity,
  2173. typename = internal::range_category_t<Range>,
  2174. typename = internal::iterator_category_t<OutputIterator>>
  2175. constexpr auto remove_copy_if(Range&& range,
  2176. OutputIterator result,
  2177. Pred pred,
  2178. Proj proj = {}) {
  2179. return ranges::remove_copy_if(ranges::begin(range), ranges::end(range),
  2180. result, std::move(pred), std::move(proj));
  2181. }
  2182. // [alg.unique] Unique
  2183. // Reference: https://wg21.link/alg.unique
  2184. // Let `E(i)` be `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))`.
  2185. //
  2186. // Effects: For a nonempty range, eliminates all but the first element from
  2187. // every consecutive group of equivalent elements referred to by the iterator
  2188. // `i` in the range `[first + 1, last)` for which `E(i)` is true.
  2189. //
  2190. // Returns: The end of the resulting range.
  2191. //
  2192. // Complexity: For nonempty ranges, exactly `(last - first) - 1` applications of
  2193. // the corresponding predicate and no more than twice as many applications of
  2194. // any projection.
  2195. //
  2196. // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique(I
  2197. template <typename ForwardIterator,
  2198. typename Comp = ranges::equal_to,
  2199. typename Proj = identity,
  2200. typename = internal::iterator_category_t<ForwardIterator>,
  2201. typename = indirect_result_t<Comp&,
  2202. projected<ForwardIterator, Proj>,
  2203. projected<ForwardIterator, Proj>>>
  2204. constexpr auto unique(ForwardIterator first,
  2205. ForwardIterator last,
  2206. Comp comp = {},
  2207. Proj proj = {}) {
  2208. return std::unique(first, last,
  2209. internal::ProjectedBinaryPredicate(comp, proj, proj));
  2210. }
  2211. // Let `E(i)` be `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))`.
  2212. //
  2213. // Effects: For a nonempty range, eliminates all but the first element from
  2214. // every consecutive group of equivalent elements referred to by the iterator
  2215. // `i` in the range `[begin(range) + 1, end(range))` for which `E(i)` is true.
  2216. //
  2217. // Returns: The end of the resulting range.
  2218. //
  2219. // Complexity: For nonempty ranges, exactly `size(range) - 1` applications of
  2220. // the corresponding predicate and no more than twice as many applications of
  2221. // any projection.
  2222. //
  2223. // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique(R
  2224. template <typename Range,
  2225. typename Comp = ranges::equal_to,
  2226. typename Proj = identity,
  2227. typename = internal::range_category_t<Range>,
  2228. typename = indirect_result_t<Comp&,
  2229. projected<iterator_t<Range>, Proj>,
  2230. projected<iterator_t<Range>, Proj>>>
  2231. constexpr auto unique(Range&& range, Comp comp = {}, Proj proj = {}) {
  2232. return ranges::unique(ranges::begin(range), ranges::end(range),
  2233. std::move(comp), std::move(proj));
  2234. }
  2235. // Let `E(i)` be `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))`.
  2236. //
  2237. // Mandates: `*first` is writable to `result`.
  2238. //
  2239. // Preconditions: The ranges `[first, last)` and
  2240. // `[result, result + (last - first))` do not overlap.
  2241. //
  2242. // Effects: Copies only the first element from every consecutive group of equal
  2243. // elements referred to by the iterator `i` in the range `[first, last)` for
  2244. // which `E(i)` holds.
  2245. //
  2246. // Returns: `result + N`.
  2247. //
  2248. // Complexity: Exactly `last - first - 1` applications of the corresponding
  2249. // predicate and no more than twice as many applications of any projection.
  2250. //
  2251. // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique_copy(I
  2252. template <typename ForwardIterator,
  2253. typename OutputIterator,
  2254. typename Comp = ranges::equal_to,
  2255. typename Proj = identity,
  2256. typename = internal::iterator_category_t<ForwardIterator>,
  2257. typename = internal::iterator_category_t<OutputIterator>>
  2258. constexpr auto unique_copy(ForwardIterator first,
  2259. ForwardIterator last,
  2260. OutputIterator result,
  2261. Comp comp = {},
  2262. Proj proj = {}) {
  2263. return std::unique_copy(first, last, result,
  2264. internal::ProjectedBinaryPredicate(comp, proj, proj));
  2265. }
  2266. // Let `E(i)` be `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))`.
  2267. //
  2268. // Mandates: `*begin(range)` is writable to `result`.
  2269. //
  2270. // Preconditions: The ranges `range` and `[result, result + size(range))` do not
  2271. // overlap.
  2272. //
  2273. // Effects: Copies only the first element from every consecutive group of equal
  2274. // elements referred to by the iterator `i` in `range` for which `E(i)` holds.
  2275. //
  2276. // Returns: `result + N`.
  2277. //
  2278. // Complexity: Exactly `size(range) - 1` applications of the corresponding
  2279. // predicate and no more than twice as many applications of any projection.
  2280. //
  2281. // Reference: https://wg21.link/alg.unique#:~:text=ranges::unique_copy(R
  2282. template <typename Range,
  2283. typename OutputIterator,
  2284. typename Comp = ranges::equal_to,
  2285. typename Proj = identity,
  2286. typename = internal::range_category_t<Range>,
  2287. typename = internal::iterator_category_t<OutputIterator>>
  2288. constexpr auto unique_copy(Range&& range,
  2289. OutputIterator result,
  2290. Comp comp = {},
  2291. Proj proj = {}) {
  2292. return ranges::unique_copy(ranges::begin(range), ranges::end(range), result,
  2293. std::move(comp), std::move(proj));
  2294. }
  2295. // [alg.reverse] Reverse
  2296. // Reference: https://wg21.link/alg.reverse
  2297. // Effects: For each non-negative integer `i < (last - first) / 2`, applies
  2298. // `std::iter_swap` to all pairs of iterators `first + i, (last - i) - 1`.
  2299. //
  2300. // Returns: `last`.
  2301. //
  2302. // Complexity: Exactly `(last - first)/2` swaps.
  2303. //
  2304. // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse(I
  2305. template <typename BidirectionalIterator,
  2306. typename = internal::iterator_category_t<BidirectionalIterator>>
  2307. constexpr auto reverse(BidirectionalIterator first,
  2308. BidirectionalIterator last) {
  2309. std::reverse(first, last);
  2310. return last;
  2311. }
  2312. // Effects: For each non-negative integer `i < size(range) / 2`, applies
  2313. // `std::iter_swap` to all pairs of iterators
  2314. // `begin(range) + i, (end(range) - i) - 1`.
  2315. //
  2316. // Returns: `end(range)`.
  2317. //
  2318. // Complexity: Exactly `size(range)/2` swaps.
  2319. //
  2320. // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse(R
  2321. template <typename Range, typename = internal::range_category_t<Range>>
  2322. constexpr auto reverse(Range&& range) {
  2323. return ranges::reverse(ranges::begin(range), ranges::end(range));
  2324. }
  2325. // Let `N` be `last - first`.
  2326. //
  2327. // Preconditions: The ranges `[first, last)` and `[result, result + N)` do not
  2328. // overlap.
  2329. //
  2330. // Effects: Copies the range `[first, last)` to the range `[result, result + N)`
  2331. // such that for every non-negative integer `i < N` the following assignment
  2332. // takes place: `*(result + N - 1 - i) = *(first + i)`.
  2333. //
  2334. // Returns: `result + N`.
  2335. //
  2336. // Complexity: Exactly `N` assignments.
  2337. //
  2338. // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse_copy(I
  2339. template <typename BidirectionalIterator,
  2340. typename OutputIterator,
  2341. typename = internal::iterator_category_t<BidirectionalIterator>,
  2342. typename = internal::iterator_category_t<OutputIterator>>
  2343. constexpr auto reverse_copy(BidirectionalIterator first,
  2344. BidirectionalIterator last,
  2345. OutputIterator result) {
  2346. return std::reverse_copy(first, last, result);
  2347. }
  2348. // Let `N` be `size(range)`.
  2349. //
  2350. // Preconditions: The ranges `range` and `[result, result + N)` do not
  2351. // overlap.
  2352. //
  2353. // Effects: Copies `range` to the range `[result, result + N)` such that for
  2354. // every non-negative integer `i < N` the following assignment takes place:
  2355. // `*(result + N - 1 - i) = *(begin(range) + i)`.
  2356. //
  2357. // Returns: `result + N`.
  2358. //
  2359. // Complexity: Exactly `N` assignments.
  2360. //
  2361. // Reference: https://wg21.link/alg.reverse#:~:text=ranges::reverse_copy(R
  2362. template <typename Range,
  2363. typename OutputIterator,
  2364. typename = internal::range_category_t<Range>,
  2365. typename = internal::iterator_category_t<OutputIterator>>
  2366. constexpr auto reverse_copy(Range&& range, OutputIterator result) {
  2367. return ranges::reverse_copy(ranges::begin(range), ranges::end(range), result);
  2368. }
  2369. // [alg.rotate] Rotate
  2370. // Reference: https://wg21.link/alg.rotate
  2371. // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges.
  2372. //
  2373. // Effects: For each non-negative integer `i < (last - first)`, places the
  2374. // element from the position `first + i` into position
  2375. // `first + (i + (last - middle)) % (last - first)`.
  2376. //
  2377. // Returns: `first + (last - middle)`.
  2378. //
  2379. // Complexity: At most `last - first` swaps.
  2380. //
  2381. // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate(I
  2382. template <typename ForwardIterator,
  2383. typename = internal::iterator_category_t<ForwardIterator>>
  2384. constexpr auto rotate(ForwardIterator first,
  2385. ForwardIterator middle,
  2386. ForwardIterator last) {
  2387. return std::rotate(first, middle, last);
  2388. }
  2389. // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
  2390. // ranges.
  2391. //
  2392. // Effects: For each non-negative integer `i < size(range)`, places the element
  2393. // from the position `begin(range) + i` into position
  2394. // `begin(range) + (i + (end(range) - middle)) % size(range)`.
  2395. //
  2396. // Returns: `begin(range) + (end(range) - middle)`.
  2397. //
  2398. // Complexity: At most `size(range)` swaps.
  2399. //
  2400. // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate(R
  2401. template <typename Range, typename = internal::range_category_t<Range>>
  2402. constexpr auto rotate(Range&& range, iterator_t<Range> middle) {
  2403. return ranges::rotate(ranges::begin(range), middle, ranges::end(range));
  2404. }
  2405. // Let `N` be `last - first`.
  2406. //
  2407. // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges. The
  2408. // ranges `[first, last)` and `[result, result + N)` do not overlap.
  2409. //
  2410. // Effects: Copies the range `[first, last)` to the range `[result, result + N)`
  2411. // such that for each non-negative integer `i < N` the following assignment
  2412. // takes place: `*(result + i) = *(first + (i + (middle - first)) % N)`.
  2413. //
  2414. // Returns: `result + N`.
  2415. //
  2416. // Complexity: Exactly `N` assignments.
  2417. //
  2418. // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate_copy(I
  2419. template <typename ForwardIterator,
  2420. typename OutputIterator,
  2421. typename = internal::iterator_category_t<ForwardIterator>,
  2422. typename = internal::iterator_category_t<OutputIterator>>
  2423. constexpr auto rotate_copy(ForwardIterator first,
  2424. ForwardIterator middle,
  2425. ForwardIterator last,
  2426. OutputIterator result) {
  2427. return std::rotate_copy(first, middle, last, result);
  2428. }
  2429. // Let `N` be `size(range)`.
  2430. //
  2431. // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
  2432. // ranges. The ranges `range` and `[result, result + N)` do not overlap.
  2433. //
  2434. // Effects: Copies `range` to the range `[result, result + N)` such that for
  2435. // each non-negative integer `i < N` the following assignment takes place:
  2436. // `*(result + i) = *(begin(range) + (i + (middle - begin(range))) % N)`.
  2437. //
  2438. // Returns: `result + N`.
  2439. //
  2440. // Complexity: Exactly `N` assignments.
  2441. //
  2442. // Reference: https://wg21.link/alg.rotate#:~:text=ranges::rotate_copy(R
  2443. template <typename Range,
  2444. typename OutputIterator,
  2445. typename = internal::range_category_t<Range>,
  2446. typename = internal::iterator_category_t<OutputIterator>>
  2447. constexpr auto rotate_copy(Range&& range,
  2448. iterator_t<Range> middle,
  2449. OutputIterator result) {
  2450. return ranges::rotate_copy(ranges::begin(range), middle, ranges::end(range),
  2451. result);
  2452. }
  2453. // [alg.random.sample] Sample
  2454. // Reference: https://wg21.link/alg.random.sample
  2455. // Currently not implemented due to lack of std::sample in C++14.
  2456. // TODO(crbug.com/1071094): Consider implementing a hand-rolled version.
  2457. // [alg.random.shuffle] Shuffle
  2458. // Reference: https://wg21.link/alg.random.shuffle
  2459. // Preconditions: The type `std::remove_reference_t<UniformRandomBitGenerator>`
  2460. // meets the uniform random bit generator requirements.
  2461. //
  2462. // Effects: Permutes the elements in the range `[first, last)` such that each
  2463. // possible permutation of those elements has equal probability of appearance.
  2464. //
  2465. // Returns: `last`.
  2466. //
  2467. // Complexity: Exactly `(last - first) - 1` swaps.
  2468. //
  2469. // Remarks: To the extent that the implementation of this function makes use of
  2470. // random numbers, the object referenced by g shall serve as the
  2471. // implementation's source of randomness.
  2472. //
  2473. // Reference: https://wg21.link/alg.random.shuffle#:~:text=ranges::shuffle(I
  2474. template <typename RandomAccessIterator,
  2475. typename UniformRandomBitGenerator,
  2476. typename = internal::iterator_category_t<RandomAccessIterator>>
  2477. constexpr auto shuffle(RandomAccessIterator first,
  2478. RandomAccessIterator last,
  2479. UniformRandomBitGenerator&& g) {
  2480. std::shuffle(first, last, std::forward<UniformRandomBitGenerator>(g));
  2481. return last;
  2482. }
  2483. // Preconditions: The type `std::remove_reference_t<UniformRandomBitGenerator>`
  2484. // meets the uniform random bit generator requirements.
  2485. //
  2486. // Effects: Permutes the elements in `range` such that each possible permutation
  2487. // of those elements has equal probability of appearance.
  2488. //
  2489. // Returns: `end(range)`.
  2490. //
  2491. // Complexity: Exactly `size(range) - 1` swaps.
  2492. //
  2493. // Remarks: To the extent that the implementation of this function makes use of
  2494. // random numbers, the object referenced by g shall serve as the
  2495. // implementation's source of randomness.
  2496. //
  2497. // Reference: https://wg21.link/alg.random.shuffle#:~:text=ranges::shuffle(R
  2498. template <typename Range,
  2499. typename UniformRandomBitGenerator,
  2500. typename = internal::range_category_t<Range>>
  2501. constexpr auto shuffle(Range&& range, UniformRandomBitGenerator&& g) {
  2502. return ranges::shuffle(ranges::begin(range), ranges::end(range),
  2503. std::forward<UniformRandomBitGenerator>(g));
  2504. }
  2505. // [alg.nonmodifying] Sorting and related operations
  2506. // Reference: https://wg21.link/alg.sorting
  2507. // [alg.sort] Sorting
  2508. // Reference: https://wg21.link/alg.sort
  2509. // [sort] sort
  2510. // Reference: https://wg21.link/sort
  2511. // Effects: Sorts the elements in the range `[first, last)` with respect to
  2512. // `comp` and `proj`.
  2513. //
  2514. // Returns: `last`.
  2515. //
  2516. // Complexity: Let `N` be `last - first`. `O(N log N)` comparisons and
  2517. // projections.
  2518. //
  2519. // Reference: https://wg21.link/sort#:~:text=ranges::sort(I
  2520. template <typename RandomAccessIterator,
  2521. typename Comp = ranges::less,
  2522. typename Proj = identity,
  2523. typename = internal::iterator_category_t<RandomAccessIterator>,
  2524. typename = indirect_result_t<Comp&,
  2525. projected<RandomAccessIterator, Proj>,
  2526. projected<RandomAccessIterator, Proj>>>
  2527. constexpr auto sort(RandomAccessIterator first,
  2528. RandomAccessIterator last,
  2529. Comp comp = {},
  2530. Proj proj = {}) {
  2531. std::sort(first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
  2532. return last;
  2533. }
  2534. // Effects: Sorts the elements in `range` with respect to `comp` and `proj`.
  2535. //
  2536. // Returns: `end(range)`.
  2537. //
  2538. // Complexity: Let `N` be `size(range)`. `O(N log N)` comparisons and
  2539. // projections.
  2540. //
  2541. // Reference: https://wg21.link/sort#:~:text=ranges::sort(R
  2542. template <typename Range,
  2543. typename Comp = ranges::less,
  2544. typename Proj = identity,
  2545. typename = internal::range_category_t<Range>,
  2546. typename = indirect_result_t<Comp&,
  2547. projected<iterator_t<Range>, Proj>,
  2548. projected<iterator_t<Range>, Proj>>>
  2549. constexpr auto sort(Range&& range, Comp comp = {}, Proj proj = {}) {
  2550. return ranges::sort(ranges::begin(range), ranges::end(range), std::move(comp),
  2551. std::move(proj));
  2552. }
  2553. // [stable.sort] stable_sort
  2554. // Reference: https://wg21.link/stable.sort
  2555. // Effects: Sorts the elements in the range `[first, last)` with respect to
  2556. // `comp` and `proj`.
  2557. //
  2558. // Returns: `last`.
  2559. //
  2560. // Complexity: Let `N` be `last - first`. If enough extra memory is available,
  2561. // `N log (N)` comparisons. Otherwise, at most `N log^2 (N)` comparisons. In
  2562. // either case, twice as many projections as the number of comparisons.
  2563. //
  2564. // Remarks: Stable.
  2565. //
  2566. // Reference: https://wg21.link/stable.sort#:~:text=ranges::stable_sort(I
  2567. template <typename RandomAccessIterator,
  2568. typename Comp = ranges::less,
  2569. typename Proj = identity,
  2570. typename = internal::iterator_category_t<RandomAccessIterator>,
  2571. typename = indirect_result_t<Comp&,
  2572. projected<RandomAccessIterator, Proj>,
  2573. projected<RandomAccessIterator, Proj>>>
  2574. constexpr auto stable_sort(RandomAccessIterator first,
  2575. RandomAccessIterator last,
  2576. Comp comp = {},
  2577. Proj proj = {}) {
  2578. std::stable_sort(first, last,
  2579. internal::ProjectedBinaryPredicate(comp, proj, proj));
  2580. return last;
  2581. }
  2582. // Effects: Sorts the elements in `range` with respect to `comp` and `proj`.
  2583. //
  2584. // Returns: `end(rang)`.
  2585. //
  2586. // Complexity: Let `N` be `size(range)`. If enough extra memory is available,
  2587. // `N log (N)` comparisons. Otherwise, at most `N log^2 (N)` comparisons. In
  2588. // either case, twice as many projections as the number of comparisons.
  2589. //
  2590. // Remarks: Stable.
  2591. //
  2592. // Reference: https://wg21.link/stable.sort#:~:text=ranges::stable_sort(R
  2593. template <typename Range,
  2594. typename Comp = ranges::less,
  2595. typename Proj = identity,
  2596. typename = internal::range_category_t<Range>,
  2597. typename = indirect_result_t<Comp&,
  2598. projected<iterator_t<Range>, Proj>,
  2599. projected<iterator_t<Range>, Proj>>>
  2600. constexpr auto stable_sort(Range&& range, Comp comp = {}, Proj proj = {}) {
  2601. return ranges::stable_sort(ranges::begin(range), ranges::end(range),
  2602. std::move(comp), std::move(proj));
  2603. }
  2604. // [partial.sort] partial_sort
  2605. // Reference: https://wg21.link/partial.sort
  2606. // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges.
  2607. //
  2608. // Effects: Places the first `middle - first` elements from the range
  2609. // `[first, last)` as sorted with respect to `comp` and `proj` into the range
  2610. // `[first, middle)`. The rest of the elements in the range `[middle, last)` are
  2611. // placed in an unspecified order.
  2612. //
  2613. // Returns: `last`.
  2614. //
  2615. // Complexity: Approximately `(last - first) * log(middle - first)` comparisons,
  2616. // and twice as many projections.
  2617. //
  2618. // Reference: https://wg21.link/partial.sort#:~:text=ranges::partial_sort(I
  2619. template <typename RandomAccessIterator,
  2620. typename Comp = ranges::less,
  2621. typename Proj = identity,
  2622. typename = internal::iterator_category_t<RandomAccessIterator>,
  2623. typename = indirect_result_t<Comp&,
  2624. projected<RandomAccessIterator, Proj>,
  2625. projected<RandomAccessIterator, Proj>>>
  2626. constexpr auto partial_sort(RandomAccessIterator first,
  2627. RandomAccessIterator middle,
  2628. RandomAccessIterator last,
  2629. Comp comp = {},
  2630. Proj proj = {}) {
  2631. std::partial_sort(first, middle, last,
  2632. internal::ProjectedBinaryPredicate(comp, proj, proj));
  2633. return last;
  2634. }
  2635. // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
  2636. // ranges.
  2637. //
  2638. // Effects: Places the first `middle - begin(range)` elements from `range` as
  2639. // sorted with respect to `comp` and `proj` into the range
  2640. // `[begin(range), middle)`. The rest of the elements in the range
  2641. // `[middle, end(range))` are placed in an unspecified order.
  2642. //
  2643. // Returns: `end(range)`.
  2644. //
  2645. // Complexity: Approximately `size(range) * log(middle - begin(range))`
  2646. // comparisons, and twice as many projections.
  2647. //
  2648. // Reference: https://wg21.link/partial.sort#:~:text=ranges::partial_sort(R
  2649. template <typename Range,
  2650. typename Comp = ranges::less,
  2651. typename Proj = identity,
  2652. typename = internal::range_category_t<Range>,
  2653. typename = indirect_result_t<Comp&,
  2654. projected<iterator_t<Range>, Proj>,
  2655. projected<iterator_t<Range>, Proj>>>
  2656. constexpr auto partial_sort(Range&& range,
  2657. iterator_t<Range> middle,
  2658. Comp comp = {},
  2659. Proj proj = {}) {
  2660. return ranges::partial_sort(ranges::begin(range), middle, ranges::end(range),
  2661. std::move(comp), std::move(proj));
  2662. }
  2663. // [partial.sort.copy] partial_sort_copy
  2664. // Reference: https://wg21.link/partial.sort.copy
  2665. // Let `N` be `min(last - first, result_last - result_first)`.
  2666. //
  2667. // Preconditions: For iterators `a1` and `b1` in `[first, last)`, and iterators
  2668. // `x2` and `y2` in `[result_first, result_last)`, after evaluating the
  2669. // assignment `*y2 = *b1`, let `E` be the value of `bool(invoke(comp,
  2670. // invoke(proj1, *a1), invoke(proj2, *y2)))`. Then, after evaluating the
  2671. // assignment `*x2 = *a1`, `E` is equal to `bool(invoke(comp, invoke(proj2,
  2672. // *x2), invoke(proj2, *y2)))`.
  2673. //
  2674. // Effects: Places the first `N` elements as sorted with respect to `comp` and
  2675. // `proj2` into the range `[result_first, result_first + N)`.
  2676. //
  2677. // Returns: `result_first + N`.
  2678. //
  2679. // Complexity: Approximately `(last - first) * log N` comparisons, and twice as
  2680. // many projections.
  2681. //
  2682. // Reference:
  2683. // https://wg21.link/partial.sort.copy#:~:text=ranges::partial_sort_copy(I1
  2684. template <typename InputIterator,
  2685. typename RandomAccessIterator,
  2686. typename Comp = ranges::less,
  2687. typename Proj1 = identity,
  2688. typename Proj2 = identity,
  2689. typename = internal::iterator_category_t<InputIterator>,
  2690. typename = internal::iterator_category_t<RandomAccessIterator>,
  2691. typename = indirect_result_t<Comp&,
  2692. projected<InputIterator, Proj1>,
  2693. projected<RandomAccessIterator, Proj2>>,
  2694. typename = indirect_result_t<Comp&,
  2695. projected<RandomAccessIterator, Proj2>,
  2696. projected<InputIterator, Proj1>>>
  2697. constexpr auto partial_sort_copy(InputIterator first,
  2698. InputIterator last,
  2699. RandomAccessIterator result_first,
  2700. RandomAccessIterator result_last,
  2701. Comp comp = {},
  2702. Proj1 proj1 = {},
  2703. Proj2 proj2 = {}) {
  2704. // Needs to opt-in to all permutations, since std::partial_sort_copy expects
  2705. // comp(proj2(lhs), proj1(rhs)) to compile.
  2706. return std::partial_sort_copy(
  2707. first, last, result_first, result_last,
  2708. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  2709. }
  2710. // Let `N` be `min(size(range), size(result_range))`.
  2711. //
  2712. // Preconditions: For iterators `a1` and `b1` in `range`, and iterators
  2713. // `x2` and `y2` in `result_range`, after evaluating the assignment
  2714. // `*y2 = *b1`, let `E` be the value of
  2715. // `bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2)))`. Then, after
  2716. // evaluating the assignment `*x2 = *a1`, `E` is equal to
  2717. // `bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2)))`.
  2718. //
  2719. // Effects: Places the first `N` elements as sorted with respect to `comp` and
  2720. // `proj2` into the range `[begin(result_range), begin(result_range) + N)`.
  2721. //
  2722. // Returns: `begin(result_range) + N`.
  2723. //
  2724. // Complexity: Approximately `size(range) * log N` comparisons, and twice as
  2725. // many projections.
  2726. //
  2727. // Reference:
  2728. // https://wg21.link/partial.sort.copy#:~:text=ranges::partial_sort_copy(R1
  2729. template <typename Range1,
  2730. typename Range2,
  2731. typename Comp = ranges::less,
  2732. typename Proj1 = identity,
  2733. typename Proj2 = identity,
  2734. typename = internal::range_category_t<Range1>,
  2735. typename = internal::range_category_t<Range2>,
  2736. typename = indirect_result_t<Comp&,
  2737. projected<iterator_t<Range1>, Proj1>,
  2738. projected<iterator_t<Range2>, Proj2>>,
  2739. typename = indirect_result_t<Comp&,
  2740. projected<iterator_t<Range2>, Proj2>,
  2741. projected<iterator_t<Range1>, Proj1>>>
  2742. constexpr auto partial_sort_copy(Range1&& range,
  2743. Range2&& result_range,
  2744. Comp comp = {},
  2745. Proj1 proj1 = {},
  2746. Proj2 proj2 = {}) {
  2747. return ranges::partial_sort_copy(ranges::begin(range), ranges::end(range),
  2748. ranges::begin(result_range),
  2749. ranges::end(result_range), std::move(comp),
  2750. std::move(proj1), std::move(proj2));
  2751. }
  2752. // [is.sorted] is_sorted
  2753. // Reference: https://wg21.link/is.sorted
  2754. // Returns: The last iterator `i` in `[first, last]` for which the range
  2755. // `[first, i)` is sorted with respect to `comp` and `proj`.
  2756. //
  2757. // Complexity: Linear.
  2758. //
  2759. // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted_until(I
  2760. template <typename ForwardIterator,
  2761. typename Comp = ranges::less,
  2762. typename Proj = identity,
  2763. typename = internal::iterator_category_t<ForwardIterator>,
  2764. typename = indirect_result_t<Comp&,
  2765. projected<ForwardIterator, Proj>,
  2766. projected<ForwardIterator, Proj>>>
  2767. constexpr auto is_sorted_until(ForwardIterator first,
  2768. ForwardIterator last,
  2769. Comp comp = {},
  2770. Proj proj = {}) {
  2771. // Implementation inspired by cppreference.com:
  2772. // https://en.cppreference.com/w/cpp/algorithm/is_sorted_until
  2773. //
  2774. // A reimplementation is required, because std::is_sorted_until is not
  2775. // constexpr prior to C++20. Once we have C++20, we should switch to standard
  2776. // library implementation.
  2777. if (first == last)
  2778. return last;
  2779. for (ForwardIterator next = first; ++next != last; ++first) {
  2780. if (base::invoke(comp, base::invoke(proj, *next),
  2781. base::invoke(proj, *first))) {
  2782. return next;
  2783. }
  2784. }
  2785. return last;
  2786. }
  2787. // Returns: The last iterator `i` in `[begin(range), end(range)]` for which the
  2788. // range `[begin(range), i)` is sorted with respect to `comp` and `proj`.
  2789. //
  2790. // Complexity: Linear.
  2791. //
  2792. // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted_until(R
  2793. template <typename Range,
  2794. typename Comp = ranges::less,
  2795. typename Proj = identity,
  2796. typename = internal::range_category_t<Range>,
  2797. typename = indirect_result_t<Comp&,
  2798. projected<iterator_t<Range>, Proj>,
  2799. projected<iterator_t<Range>, Proj>>>
  2800. constexpr auto is_sorted_until(Range&& range, Comp comp = {}, Proj proj = {}) {
  2801. return ranges::is_sorted_until(ranges::begin(range), ranges::end(range),
  2802. std::move(comp), std::move(proj));
  2803. }
  2804. // Returns: Whether the range `[first, last)` is sorted with respect to `comp`
  2805. // and `proj`.
  2806. //
  2807. // Complexity: Linear.
  2808. //
  2809. // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted(I
  2810. template <typename ForwardIterator,
  2811. typename Comp = ranges::less,
  2812. typename Proj = identity,
  2813. typename = internal::iterator_category_t<ForwardIterator>,
  2814. typename = indirect_result_t<Comp&,
  2815. projected<ForwardIterator, Proj>,
  2816. projected<ForwardIterator, Proj>>>
  2817. constexpr auto is_sorted(ForwardIterator first,
  2818. ForwardIterator last,
  2819. Comp comp = {},
  2820. Proj proj = {}) {
  2821. return ranges::is_sorted_until(first, last, std::move(comp),
  2822. std::move(proj)) == last;
  2823. }
  2824. // Returns: Whether `range` is sorted with respect to `comp` and `proj`.
  2825. //
  2826. // Complexity: Linear.
  2827. //
  2828. // Reference: https://wg21.link/is.sorted#:~:text=ranges::is_sorted(R
  2829. template <typename Range,
  2830. typename Comp = ranges::less,
  2831. typename Proj = identity,
  2832. typename = internal::range_category_t<Range>,
  2833. typename = indirect_result_t<Comp&,
  2834. projected<iterator_t<Range>, Proj>,
  2835. projected<iterator_t<Range>, Proj>>>
  2836. constexpr auto is_sorted(Range&& range, Comp comp = {}, Proj proj = {}) {
  2837. return ranges::is_sorted(ranges::begin(range), ranges::end(range),
  2838. std::move(comp), std::move(proj));
  2839. }
  2840. // [alg.nth.element] Nth element
  2841. // Reference: https://wg21.link/alg.nth.element
  2842. // Preconditions: `[first, nth)` and `[nth, last)` are valid ranges.
  2843. //
  2844. // Effects: After `nth_element` the element in the position pointed to by `nth`
  2845. // is the element that would be in that position if the whole range were sorted
  2846. // with respect to `comp` and `proj`, unless `nth == last`. Also for every
  2847. // iterator `i` in the range `[first, nth)` and every iterator `j` in the range
  2848. // `[nth, last)` it holds that:
  2849. // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is false.
  2850. //
  2851. // Returns: `last`.
  2852. //
  2853. // Complexity: Linear on average.
  2854. //
  2855. // Reference: https://wg21.link/alg.nth.element#:~:text=ranges::nth_element(I
  2856. template <typename RandomAccessIterator,
  2857. typename Comp = ranges::less,
  2858. typename Proj = identity,
  2859. typename = internal::iterator_category_t<RandomAccessIterator>,
  2860. typename = indirect_result_t<Comp&,
  2861. projected<RandomAccessIterator, Proj>,
  2862. projected<RandomAccessIterator, Proj>>>
  2863. constexpr auto nth_element(RandomAccessIterator first,
  2864. RandomAccessIterator nth,
  2865. RandomAccessIterator last,
  2866. Comp comp = {},
  2867. Proj proj = {}) {
  2868. std::nth_element(first, nth, last,
  2869. internal::ProjectedBinaryPredicate(comp, proj, proj));
  2870. return last;
  2871. }
  2872. // Preconditions: `[begin(range), nth)` and `[nth, end(range))` are valid
  2873. // ranges.
  2874. //
  2875. // Effects: After `nth_element` the element in the position pointed to by `nth`
  2876. // is the element that would be in that position if the whole range were sorted
  2877. // with respect to `comp` and `proj`, unless `nth == end(range)`. Also for every
  2878. // iterator `i` in the range `[begin(range), nth)` and every iterator `j` in the
  2879. // range `[nth, end(range))` it holds that:
  2880. // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is false.
  2881. //
  2882. // Returns: `end(range)`.
  2883. //
  2884. // Complexity: Linear on average.
  2885. //
  2886. // Reference: https://wg21.link/alg.nth.element#:~:text=ranges::nth_element(R
  2887. template <typename Range,
  2888. typename Comp = ranges::less,
  2889. typename Proj = identity,
  2890. typename = internal::range_category_t<Range>,
  2891. typename = indirect_result_t<Comp&,
  2892. projected<iterator_t<Range>, Proj>,
  2893. projected<iterator_t<Range>, Proj>>>
  2894. constexpr auto nth_element(Range&& range,
  2895. iterator_t<Range> nth,
  2896. Comp comp = {},
  2897. Proj proj = {}) {
  2898. return ranges::nth_element(ranges::begin(range), nth, ranges::end(range),
  2899. std::move(comp), std::move(proj));
  2900. }
  2901. // [alg.binary.search] Binary search
  2902. // Reference: https://wg21.link/alg.binary.search
  2903. // [lower.bound] lower_bound
  2904. // Reference: https://wg21.link/lower.bound
  2905. // Preconditions: The elements `e` of `[first, last)` are partitioned with
  2906. // respect to the expression `bool(invoke(comp, invoke(proj, e), value))`.
  2907. //
  2908. // Returns: The furthermost iterator `i` in the range `[first, last]` such that
  2909. // for every iterator `j` in the range `[first, i)`,
  2910. // `bool(invoke(comp, invoke(proj, *j), value))` is true.
  2911. //
  2912. // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
  2913. //
  2914. // Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(I
  2915. template <typename ForwardIterator,
  2916. typename T,
  2917. typename Comp = ranges::less,
  2918. typename Proj = identity,
  2919. typename = internal::iterator_category_t<ForwardIterator>>
  2920. constexpr auto lower_bound(ForwardIterator first,
  2921. ForwardIterator last,
  2922. const T& value,
  2923. Comp comp = {},
  2924. Proj proj = {}) {
  2925. // The second arg is guaranteed to be `value`, so we'll simply apply the
  2926. // identity projection.
  2927. identity value_proj;
  2928. return std::lower_bound(
  2929. first, last, value,
  2930. internal::ProjectedBinaryPredicate(comp, proj, value_proj));
  2931. }
  2932. // Preconditions: The elements `e` of `range` are partitioned with respect to
  2933. // the expression `bool(invoke(comp, invoke(proj, e), value))`.
  2934. //
  2935. // Returns: The furthermost iterator `i` in the range
  2936. // `[begin(range), end(range)]` such that for every iterator `j` in the range
  2937. // `[begin(range), i)`, `bool(invoke(comp, invoke(proj, *j), value))` is true.
  2938. //
  2939. // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
  2940. //
  2941. // Reference: https://wg21.link/lower.bound#:~:text=ranges::lower_bound(R
  2942. template <typename Range,
  2943. typename T,
  2944. typename Comp = ranges::less,
  2945. typename Proj = identity,
  2946. typename = internal::range_category_t<Range>>
  2947. constexpr auto lower_bound(Range&& range,
  2948. const T& value,
  2949. Comp comp = {},
  2950. Proj proj = {}) {
  2951. return ranges::lower_bound(ranges::begin(range), ranges::end(range), value,
  2952. std::move(comp), std::move(proj));
  2953. }
  2954. // [upper.bound] upper_bound
  2955. // Reference: https://wg21.link/upper.bound
  2956. // Preconditions: The elements `e` of `[first, last)` are partitioned with
  2957. // respect to the expression `!bool(invoke(comp, value, invoke(proj, e)))`.
  2958. //
  2959. // Returns: The furthermost iterator `i` in the range `[first, last]` such that
  2960. // for every iterator `j` in the range `[first, i)`,
  2961. // `!bool(invoke(comp, value, invoke(proj, *j)))` is true.
  2962. //
  2963. // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
  2964. //
  2965. // Reference: https://wg21.link/upper.bound#:~:text=ranges::upper_bound(I
  2966. template <typename ForwardIterator,
  2967. typename T,
  2968. typename Comp = ranges::less,
  2969. typename Proj = identity,
  2970. typename = internal::iterator_category_t<ForwardIterator>>
  2971. constexpr auto upper_bound(ForwardIterator first,
  2972. ForwardIterator last,
  2973. const T& value,
  2974. Comp comp = {},
  2975. Proj proj = {}) {
  2976. // The first arg is guaranteed to be `value`, so we'll simply apply the
  2977. // identity projection.
  2978. identity value_proj;
  2979. return std::upper_bound(
  2980. first, last, value,
  2981. internal::ProjectedBinaryPredicate(comp, value_proj, proj));
  2982. }
  2983. // Preconditions: The elements `e` of `range` are partitioned with
  2984. // respect to the expression `!bool(invoke(comp, value, invoke(proj, e)))`.
  2985. //
  2986. // Returns: The furthermost iterator `i` in the range
  2987. // `[begin(range), end(range)]` such that for every iterator `j` in the range
  2988. // `[begin(range), i)`, `!bool(invoke(comp, value, invoke(proj, *j)))` is true.
  2989. //
  2990. // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
  2991. //
  2992. // Reference: https://wg21.link/upper.bound#:~:text=ranges::upper_bound(R
  2993. template <typename Range,
  2994. typename T,
  2995. typename Comp = ranges::less,
  2996. typename Proj = identity,
  2997. typename = internal::range_category_t<Range>>
  2998. constexpr auto upper_bound(Range&& range,
  2999. const T& value,
  3000. Comp comp = {},
  3001. Proj proj = {}) {
  3002. return ranges::upper_bound(ranges::begin(range), ranges::end(range), value,
  3003. std::move(comp), std::move(proj));
  3004. }
  3005. // [equal.range] equal_range
  3006. // Reference: https://wg21.link/equal.range
  3007. // Preconditions: The elements `e` of `[first, last)` are partitioned with
  3008. // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
  3009. // `!bool(invoke(comp, value, invoke(proj, e)))`.
  3010. //
  3011. // Returns: `{ranges::lower_bound(first, last, value, comp, proj),
  3012. // ranges::upper_bound(first, last, value, comp, proj)}`.
  3013. //
  3014. // Complexity: At most 2 ∗ log_2(last - first) + O(1) comparisons and
  3015. // projections.
  3016. //
  3017. // Reference: https://wg21.link/equal.range#:~:text=ranges::equal_range(I
  3018. template <typename ForwardIterator,
  3019. typename T,
  3020. typename Comp = ranges::less,
  3021. typename Proj = identity,
  3022. typename = internal::iterator_category_t<ForwardIterator>>
  3023. constexpr auto equal_range(ForwardIterator first,
  3024. ForwardIterator last,
  3025. const T& value,
  3026. Comp comp = {},
  3027. Proj proj = {}) {
  3028. // Note: This does not dispatch to std::equal_range, as otherwise it would not
  3029. // be possible to prevent applying `proj` to `value`, which can result in
  3030. // unintended behavior.
  3031. return std::make_pair(ranges::lower_bound(first, last, value, comp, proj),
  3032. ranges::upper_bound(first, last, value, comp, proj));
  3033. }
  3034. // Preconditions: The elements `e` of `range` are partitioned with
  3035. // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
  3036. // `!bool(invoke(comp, value, invoke(proj, e)))`.
  3037. //
  3038. // Returns: `{ranges::lower_bound(range, value, comp, proj),
  3039. // ranges::upper_bound(range, value, comp, proj)}`.
  3040. //
  3041. // Complexity: At most 2 ∗ log_2(size(range)) + O(1) comparisons and
  3042. // projections.
  3043. //
  3044. // Reference: https://wg21.link/equal.range#:~:text=ranges::equal_range(R
  3045. template <typename Range,
  3046. typename T,
  3047. typename Comp = ranges::less,
  3048. typename Proj = identity,
  3049. typename = internal::range_category_t<Range>>
  3050. constexpr auto equal_range(Range&& range,
  3051. const T& value,
  3052. Comp comp = {},
  3053. Proj proj = {}) {
  3054. return ranges::equal_range(ranges::begin(range), ranges::end(range), value,
  3055. std::move(comp), std::move(proj));
  3056. }
  3057. // [binary.search] binary_search
  3058. // Reference: https://wg21.link/binary.search
  3059. // Preconditions: The elements `e` of `[first, last)` are partitioned with
  3060. // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
  3061. // `!bool(invoke(comp, value, invoke(proj, e)))`.
  3062. //
  3063. // Returns: `true` if and only if for some iterator `i` in the range
  3064. // `[first, last)`, `!bool(invoke(comp, invoke(proj, *i), value)) &&
  3065. // !bool(invoke(comp, value, invoke(proj, *i)))` is true.
  3066. //
  3067. // Complexity: At most `log_2(last - first) + O(1)` comparisons and projections.
  3068. //
  3069. // Reference: https://wg21.link/binary.search#:~:text=ranges::binary_search(I
  3070. template <typename ForwardIterator,
  3071. typename T,
  3072. typename Comp = ranges::less,
  3073. typename Proj = identity,
  3074. typename = internal::iterator_category_t<ForwardIterator>>
  3075. constexpr auto binary_search(ForwardIterator first,
  3076. ForwardIterator last,
  3077. const T& value,
  3078. Comp comp = {},
  3079. Proj proj = {}) {
  3080. first = ranges::lower_bound(first, last, value, comp, proj);
  3081. return first != last &&
  3082. !base::invoke(comp, value, base::invoke(proj, *first));
  3083. }
  3084. // Preconditions: The elements `e` of `range` are partitioned with
  3085. // respect to the expressions `bool(invoke(comp, invoke(proj, e), value))` and
  3086. // `!bool(invoke(comp, value, invoke(proj, e)))`.
  3087. //
  3088. // Returns: `true` if and only if for some iterator `i` in `range`
  3089. // `!bool(invoke(comp, invoke(proj, *i), value)) &&
  3090. // !bool(invoke(comp, value, invoke(proj, *i)))` is true.
  3091. //
  3092. // Complexity: At most `log_2(size(range)) + O(1)` comparisons and projections.
  3093. //
  3094. // Reference: https://wg21.link/binary.search#:~:text=ranges::binary_search(R
  3095. template <typename Range,
  3096. typename T,
  3097. typename Comp = ranges::less,
  3098. typename Proj = identity,
  3099. typename = internal::range_category_t<Range>>
  3100. constexpr auto binary_search(Range&& range,
  3101. const T& value,
  3102. Comp comp = {},
  3103. Proj proj = {}) {
  3104. return ranges::binary_search(ranges::begin(range), ranges::end(range), value,
  3105. std::move(comp), std::move(proj));
  3106. }
  3107. // [alg.partitions] Partitions
  3108. // Reference: https://wg21.link/alg.partitions
  3109. // Returns: `true` if and only if the elements `e` of `[first, last)` are
  3110. // partitioned with respect to the expression
  3111. // `bool(invoke(pred, invoke(proj, e)))`.
  3112. //
  3113. // Complexity: Linear. At most `last - first` applications of `pred` and `proj`.
  3114. //
  3115. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::is_partitioned(I
  3116. template <typename ForwardIterator,
  3117. typename Pred,
  3118. typename Proj = identity,
  3119. typename = internal::iterator_category_t<ForwardIterator>>
  3120. constexpr auto is_partitioned(ForwardIterator first,
  3121. ForwardIterator last,
  3122. Pred pred,
  3123. Proj proj = {}) {
  3124. return std::is_partitioned(first, last,
  3125. internal::ProjectedUnaryPredicate(pred, proj));
  3126. }
  3127. // Returns: `true` if and only if the elements `e` of `range` are partitioned
  3128. // with respect to the expression `bool(invoke(pred, invoke(proj, e)))`.
  3129. //
  3130. // Complexity: Linear. At most `size(range)` applications of `pred` and `proj`.
  3131. //
  3132. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::is_partitioned(R
  3133. template <typename Range,
  3134. typename Pred,
  3135. typename Proj = identity,
  3136. typename = internal::range_category_t<Range>>
  3137. constexpr auto is_partitioned(Range&& range, Pred pred, Proj proj = {}) {
  3138. return ranges::is_partitioned(ranges::begin(range), ranges::end(range),
  3139. std::move(pred), std::move(proj));
  3140. }
  3141. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3142. //
  3143. // Effects: Places all the elements `e` in `[first, last)` that satisfy `E(e)`
  3144. // before all the elements that do not.
  3145. //
  3146. // Returns: Let `i` be an iterator such that `E(*j)` is `true` for every
  3147. // iterator `j` in `[first, i)` and `false` for every iterator `j` in
  3148. // `[i, last)`. Returns: i.
  3149. //
  3150. // Complexity: Let `N = last - first`:
  3151. // Exactly `N` applications of the predicate and projection. At most `N / 2`
  3152. // swaps if the type of `first` models `bidirectional_iterator`, and at most `N`
  3153. // swaps otherwise.
  3154. //
  3155. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition(I
  3156. template <typename ForwardIterator,
  3157. typename Pred,
  3158. typename Proj = identity,
  3159. typename = internal::iterator_category_t<ForwardIterator>>
  3160. constexpr auto partition(ForwardIterator first,
  3161. ForwardIterator last,
  3162. Pred pred,
  3163. Proj proj = {}) {
  3164. return std::partition(first, last,
  3165. internal::ProjectedUnaryPredicate(pred, proj));
  3166. }
  3167. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3168. //
  3169. // Effects: Places all the elements `e` in `range` that satisfy `E(e)` before
  3170. // all the elements that do not.
  3171. //
  3172. // Returns: Let `i` be an iterator such that `E(*j)` is `true` for every
  3173. // iterator `j` in `[begin(range), i)` and `false` for every iterator `j` in
  3174. // `[i, last)`. Returns: i.
  3175. //
  3176. // Complexity: Let `N = size(range)`:
  3177. // Exactly `N` applications of the predicate and projection. At most `N / 2`
  3178. // swaps if the type of `first` models `bidirectional_iterator`, and at most `N`
  3179. // swaps otherwise.
  3180. //
  3181. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition(R
  3182. template <typename Range,
  3183. typename Pred,
  3184. typename Proj = identity,
  3185. typename = internal::range_category_t<Range>>
  3186. constexpr auto partition(Range&& range, Pred pred, Proj proj = {}) {
  3187. return ranges::partition(ranges::begin(range), ranges::end(range),
  3188. std::move(pred), std::move(proj));
  3189. }
  3190. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3191. //
  3192. // Effects: Places all the elements `e` in `[first, last)` that satisfy `E(e)`
  3193. // before all the elements that do not. The relative order of the elements in
  3194. // both groups is preserved.
  3195. //
  3196. // Returns: Let `i` be an iterator such that for every iterator `j` in
  3197. // `[first, i)`, `E(*j)` is `true`, and for every iterator `j` in the range
  3198. // `[i, last)`, `E(*j)` is `false`. Returns: `i`.
  3199. //
  3200. // Complexity: Let `N = last - first`:
  3201. // At most `N log N` swaps, but only `O(N)` swaps if there is enough extra
  3202. // memory. Exactly `N` applications of the predicate and projection.
  3203. //
  3204. // Reference:
  3205. // https://wg21.link/alg.partitions#:~:text=ranges::stable_partition(I
  3206. template <typename BidirectionalIterator,
  3207. typename Pred,
  3208. typename Proj = identity,
  3209. typename = internal::iterator_category_t<BidirectionalIterator>>
  3210. constexpr auto stable_partition(BidirectionalIterator first,
  3211. BidirectionalIterator last,
  3212. Pred pred,
  3213. Proj proj = {}) {
  3214. return std::stable_partition(first, last,
  3215. internal::ProjectedUnaryPredicate(pred, proj));
  3216. }
  3217. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3218. //
  3219. // Effects: Places all the elements `e` in `range` that satisfy `E(e)` before
  3220. // all the elements that do not. The relative order of the elements in both
  3221. // groups is preserved.
  3222. //
  3223. // Returns: Let `i` be an iterator such that for every iterator `j` in
  3224. // `[begin(range), i)`, `E(*j)` is `true`, and for every iterator `j` in the
  3225. // range `[i, end(range))`, `E(*j)` is `false`. Returns: `i`.
  3226. //
  3227. // Complexity: Let `N = size(range)`:
  3228. // At most `N log N` swaps, but only `O(N)` swaps if there is enough extra
  3229. // memory. Exactly `N` applications of the predicate and projection.
  3230. //
  3231. // Reference:
  3232. // https://wg21.link/alg.partitions#:~:text=ranges::stable_partition(R
  3233. template <typename Range,
  3234. typename Pred,
  3235. typename Proj = identity,
  3236. typename = internal::range_category_t<Range>>
  3237. constexpr auto stable_partition(Range&& range, Pred pred, Proj proj = {}) {
  3238. return ranges::stable_partition(ranges::begin(range), ranges::end(range),
  3239. std::move(pred), std::move(proj));
  3240. }
  3241. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3242. //
  3243. // Mandates: The expression `*first` is writable to `out_true` and `out_false`.
  3244. //
  3245. // Preconditions: The input range and output ranges do not overlap.
  3246. //
  3247. // Effects: For each iterator `i` in `[first, last)`, copies `*i` to the output
  3248. // range beginning with `out_true` if `E(*i)` is `true`, or to the output range
  3249. // beginning with `out_false` otherwise.
  3250. //
  3251. // Returns: Let `o1` be the end of the output range beginning at `out_true`, and
  3252. // `o2` the end of the output range beginning at `out_false`.
  3253. // Returns `{o1, o2}`.
  3254. //
  3255. // Complexity: Exactly `last - first` applications of `pred` and `proj`.
  3256. //
  3257. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_copy(I
  3258. template <typename InputIterator,
  3259. typename OutputIterator1,
  3260. typename OutputIterator2,
  3261. typename Pred,
  3262. typename Proj = identity,
  3263. typename = internal::iterator_category_t<InputIterator>,
  3264. typename = internal::iterator_category_t<OutputIterator1>,
  3265. typename = internal::iterator_category_t<OutputIterator2>>
  3266. constexpr auto partition_copy(InputIterator first,
  3267. InputIterator last,
  3268. OutputIterator1 out_true,
  3269. OutputIterator2 out_false,
  3270. Pred pred,
  3271. Proj proj = {}) {
  3272. return std::partition_copy(first, last, out_true, out_false,
  3273. internal::ProjectedUnaryPredicate(pred, proj));
  3274. }
  3275. // Let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3276. //
  3277. // Mandates: The expression `*begin(range)` is writable to `out_true` and
  3278. // `out_false`.
  3279. //
  3280. // Preconditions: The input range and output ranges do not overlap.
  3281. //
  3282. // Effects: For each iterator `i` in `range`, copies `*i` to the output range
  3283. // beginning with `out_true` if `E(*i)` is `true`, or to the output range
  3284. // beginning with `out_false` otherwise.
  3285. //
  3286. // Returns: Let `o1` be the end of the output range beginning at `out_true`, and
  3287. // `o2` the end of the output range beginning at `out_false`.
  3288. // Returns `{o1, o2}`.
  3289. //
  3290. // Complexity: Exactly `size(range)` applications of `pred` and `proj`.
  3291. //
  3292. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_copy(R
  3293. template <typename Range,
  3294. typename OutputIterator1,
  3295. typename OutputIterator2,
  3296. typename Pred,
  3297. typename Proj = identity,
  3298. typename = internal::range_category_t<Range>,
  3299. typename = internal::iterator_category_t<OutputIterator1>,
  3300. typename = internal::iterator_category_t<OutputIterator2>>
  3301. constexpr auto partition_copy(Range&& range,
  3302. OutputIterator1 out_true,
  3303. OutputIterator2 out_false,
  3304. Pred pred,
  3305. Proj proj = {}) {
  3306. return ranges::partition_copy(ranges::begin(range), ranges::end(range),
  3307. out_true, out_false, std::move(pred),
  3308. std::move(proj));
  3309. }
  3310. // let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3311. //
  3312. // Preconditions: The elements `e` of `[first, last)` are partitioned with
  3313. // respect to `E(e)`.
  3314. //
  3315. // Returns: An iterator `mid` such that `E(*i)` is `true` for all iterators `i`
  3316. // in `[first, mid)`, and `false` for all iterators `i` in `[mid, last)`.
  3317. //
  3318. // Complexity: `O(log(last - first))` applications of `pred` and `proj`.
  3319. //
  3320. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_point(I
  3321. template <typename ForwardIterator,
  3322. typename Pred,
  3323. typename Proj = identity,
  3324. typename = internal::iterator_category_t<ForwardIterator>>
  3325. constexpr auto partition_point(ForwardIterator first,
  3326. ForwardIterator last,
  3327. Pred pred,
  3328. Proj proj = {}) {
  3329. return std::partition_point(first, last,
  3330. internal::ProjectedUnaryPredicate(pred, proj));
  3331. }
  3332. // let `E(x)` be `bool(invoke(pred, invoke(proj, x)))`.
  3333. //
  3334. // Preconditions: The elements `e` of `range` are partitioned with respect to
  3335. // `E(e)`.
  3336. //
  3337. // Returns: An iterator `mid` such that `E(*i)` is `true` for all iterators `i`
  3338. // in `[begin(range), mid)`, and `false` for all iterators `i` in
  3339. // `[mid, end(range))`.
  3340. //
  3341. // Complexity: `O(log(size(range)))` applications of `pred` and `proj`.
  3342. //
  3343. // Reference: https://wg21.link/alg.partitions#:~:text=ranges::partition_point(R
  3344. template <typename Range,
  3345. typename Pred,
  3346. typename Proj = identity,
  3347. typename = internal::range_category_t<Range>>
  3348. constexpr auto partition_point(Range&& range, Pred pred, Proj proj = {}) {
  3349. return ranges::partition_point(ranges::begin(range), ranges::end(range),
  3350. std::move(pred), std::move(proj));
  3351. }
  3352. // [alg.merge] Merge
  3353. // Reference: https://wg21.link/alg.merge
  3354. // Let `N` be `(last1 - first1) + (last2 - first2)`.
  3355. //
  3356. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3357. // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
  3358. // range does not overlap with either of the original ranges.
  3359. //
  3360. // Effects: Copies all the elements of the two ranges `[first1, last1)` and
  3361. // `[first2, last2)` into the range `[result, result_last)`, where `result_last`
  3362. // is `result + N`. If an element `a` precedes `b` in an input range, `a` is
  3363. // copied into the output range before `b`. If `e1` is an element of
  3364. // `[first1, last1)` and `e2` of `[first2, last2)`, `e2` is copied into the
  3365. // output range before `e1` if and only if
  3366. // `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
  3367. //
  3368. // Returns: `result_last`.
  3369. //
  3370. // Complexity: At most `N - 1` comparisons and applications of each projection.
  3371. //
  3372. // Remarks: Stable.
  3373. //
  3374. // Reference: https://wg21.link/alg.merge#:~:text=ranges::merge(I1
  3375. template <typename InputIterator1,
  3376. typename InputIterator2,
  3377. typename OutputIterator,
  3378. typename Comp = ranges::less,
  3379. typename Proj1 = identity,
  3380. typename Proj2 = identity,
  3381. typename = internal::iterator_category_t<InputIterator1>,
  3382. typename = internal::iterator_category_t<InputIterator2>,
  3383. typename = internal::iterator_category_t<OutputIterator>,
  3384. typename = indirect_result_t<Comp&,
  3385. projected<InputIterator1, Proj1>,
  3386. projected<InputIterator2, Proj2>>,
  3387. typename = indirect_result_t<Comp&,
  3388. projected<InputIterator2, Proj2>,
  3389. projected<InputIterator1, Proj1>>>
  3390. constexpr auto merge(InputIterator1 first1,
  3391. InputIterator1 last1,
  3392. InputIterator2 first2,
  3393. InputIterator2 last2,
  3394. OutputIterator result,
  3395. Comp comp = {},
  3396. Proj1 proj1 = {},
  3397. Proj2 proj2 = {}) {
  3398. // Needs to opt-in to all permutations, since std::merge expects
  3399. // comp(proj2(lhs), proj1(rhs)) to compile.
  3400. return std::merge(
  3401. first1, last1, first2, last2, result,
  3402. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3403. }
  3404. // Let `N` be `size(range1) + size(range2)`.
  3405. //
  3406. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3407. // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
  3408. // overlap with either of the original ranges.
  3409. //
  3410. // Effects: Copies all the elements of the two ranges `range1` and `range2` into
  3411. // the range `[result, result_last)`, where `result_last` is `result + N`. If an
  3412. // element `a` precedes `b` in an input range, `a` is copied into the output
  3413. // range before `b`. If `e1` is an element of `range1` and `e2` of `range2`,
  3414. // `e2` is copied into the output range before `e1` if and only if
  3415. // `bool(invoke(comp, invoke(proj2, e2), invoke(proj1, e1)))` is `true`.
  3416. //
  3417. // Returns: `result_last`.
  3418. //
  3419. // Complexity: At most `N - 1` comparisons and applications of each projection.
  3420. //
  3421. // Remarks: Stable.
  3422. //
  3423. // Reference: https://wg21.link/alg.merge#:~:text=ranges::merge(R1
  3424. template <typename Range1,
  3425. typename Range2,
  3426. typename OutputIterator,
  3427. typename Comp = ranges::less,
  3428. typename Proj1 = identity,
  3429. typename Proj2 = identity,
  3430. typename = internal::range_category_t<Range1>,
  3431. typename = internal::range_category_t<Range2>,
  3432. typename = internal::iterator_category_t<OutputIterator>,
  3433. typename = indirect_result_t<Comp&,
  3434. projected<iterator_t<Range1>, Proj1>,
  3435. projected<iterator_t<Range2>, Proj2>>,
  3436. typename = indirect_result_t<Comp&,
  3437. projected<iterator_t<Range2>, Proj2>,
  3438. projected<iterator_t<Range1>, Proj1>>>
  3439. constexpr auto merge(Range1&& range1,
  3440. Range2&& range2,
  3441. OutputIterator result,
  3442. Comp comp = {},
  3443. Proj1 proj1 = {},
  3444. Proj2 proj2 = {}) {
  3445. return ranges::merge(ranges::begin(range1), ranges::end(range1),
  3446. ranges::begin(range2), ranges::end(range2), result,
  3447. std::move(comp), std::move(proj1), std::move(proj2));
  3448. }
  3449. // Preconditions: `[first, middle)` and `[middle, last)` are valid ranges sorted
  3450. // with respect to `comp` and `proj`.
  3451. //
  3452. // Effects: Merges two sorted consecutive ranges `[first, middle)` and
  3453. // `[middle, last)`, putting the result of the merge into the range
  3454. // `[first, last)`. The resulting range is sorted with respect to `comp` and
  3455. // `proj`.
  3456. //
  3457. // Returns: `last`.
  3458. //
  3459. // Complexity: Let `N = last - first`: If enough additional memory is available,
  3460. // exactly `N - 1` comparisons. Otherwise, `O(N log N)` comparisons. In either
  3461. // case, twice as many projections as comparisons.
  3462. //
  3463. // Remarks: Stable.
  3464. //
  3465. // Reference: https://wg21.link/alg.merge#:~:text=ranges::inplace_merge(I
  3466. template <typename BidirectionalIterator,
  3467. typename Comp = ranges::less,
  3468. typename Proj = identity,
  3469. typename = internal::iterator_category_t<BidirectionalIterator>>
  3470. constexpr auto inplace_merge(BidirectionalIterator first,
  3471. BidirectionalIterator middle,
  3472. BidirectionalIterator last,
  3473. Comp comp = {},
  3474. Proj proj = {}) {
  3475. std::inplace_merge(first, middle, last,
  3476. internal::ProjectedBinaryPredicate(comp, proj, proj));
  3477. return last;
  3478. }
  3479. // Preconditions: `[begin(range), middle)` and `[middle, end(range))` are valid
  3480. // ranges sorted with respect to `comp` and `proj`.
  3481. //
  3482. // Effects: Merges two sorted consecutive ranges `[begin(range), middle)` and
  3483. // `[middle, end(range))`, putting the result of the merge into `range`. The
  3484. // resulting range is sorted with respect to `comp` and `proj`.
  3485. //
  3486. // Returns: `end(range)`.
  3487. //
  3488. // Complexity: Let `N = size(range)`: If enough additional memory is available,
  3489. // exactly `N - 1` comparisons. Otherwise, `O(N log N)` comparisons. In either
  3490. // case, twice as many projections as comparisons.
  3491. //
  3492. // Remarks: Stable.
  3493. //
  3494. // Reference: https://wg21.link/alg.merge#:~:text=ranges::inplace_merge(R
  3495. template <typename Range,
  3496. typename Comp = ranges::less,
  3497. typename Proj = identity,
  3498. typename = internal::range_category_t<Range>>
  3499. constexpr auto inplace_merge(Range&& range,
  3500. iterator_t<Range> middle,
  3501. Comp comp = {},
  3502. Proj proj = {}) {
  3503. return ranges::inplace_merge(ranges::begin(range), middle, ranges::end(range),
  3504. std::move(comp), std::move(proj));
  3505. }
  3506. // [alg.set.operations] Set operations on sorted structures
  3507. // Reference: https://wg21.link/alg.set.operations
  3508. // [includes] includes
  3509. // Reference: https://wg21.link/includes
  3510. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3511. // with respect to `comp` and `proj1` or `proj2`, respectively.
  3512. //
  3513. // Returns: `true` if and only if `[first2, last2)` is a subsequence of
  3514. // `[first1, last1)`.
  3515. //
  3516. // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
  3517. // comparisons and applications of each projection.
  3518. //
  3519. // Reference: https://wg21.link/includes#:~:text=ranges::includes(I1
  3520. template <typename InputIterator1,
  3521. typename InputIterator2,
  3522. typename Comp = ranges::less,
  3523. typename Proj1 = identity,
  3524. typename Proj2 = identity,
  3525. typename = internal::iterator_category_t<InputIterator1>,
  3526. typename = internal::iterator_category_t<InputIterator2>,
  3527. typename = indirect_result_t<Comp&,
  3528. projected<InputIterator1, Proj1>,
  3529. projected<InputIterator2, Proj2>>,
  3530. typename = indirect_result_t<Comp&,
  3531. projected<InputIterator2, Proj2>,
  3532. projected<InputIterator1, Proj1>>>
  3533. constexpr auto includes(InputIterator1 first1,
  3534. InputIterator1 last1,
  3535. InputIterator2 first2,
  3536. InputIterator2 last2,
  3537. Comp comp = {},
  3538. Proj1 proj1 = {},
  3539. Proj2 proj2 = {}) {
  3540. DCHECK(ranges::is_sorted(first1, last1, comp, proj1));
  3541. DCHECK(ranges::is_sorted(first2, last2, comp, proj2));
  3542. // Needs to opt-in to all permutations, since std::includes expects
  3543. // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
  3544. return std::includes(
  3545. first1, last1, first2, last2,
  3546. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3547. }
  3548. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3549. // `comp` and `proj1` or `proj2`, respectively.
  3550. //
  3551. // Returns: `true` if and only if `range2` is a subsequence of `range1`.
  3552. //
  3553. // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
  3554. // applications of each projection.
  3555. //
  3556. // Reference: https://wg21.link/includes#:~:text=ranges::includes(R1
  3557. template <typename Range1,
  3558. typename Range2,
  3559. typename Comp = ranges::less,
  3560. typename Proj1 = identity,
  3561. typename Proj2 = identity,
  3562. typename = internal::range_category_t<Range1>,
  3563. typename = internal::range_category_t<Range2>,
  3564. typename = indirect_result_t<Comp&,
  3565. projected<iterator_t<Range1>, Proj1>,
  3566. projected<iterator_t<Range2>, Proj2>>,
  3567. typename = indirect_result_t<Comp&,
  3568. projected<iterator_t<Range2>, Proj2>,
  3569. projected<iterator_t<Range1>, Proj1>>>
  3570. constexpr auto includes(Range1&& range1,
  3571. Range2&& range2,
  3572. Comp comp = {},
  3573. Proj1 proj1 = {},
  3574. Proj2 proj2 = {}) {
  3575. return ranges::includes(ranges::begin(range1), ranges::end(range1),
  3576. ranges::begin(range2), ranges::end(range2),
  3577. std::move(comp), std::move(proj1), std::move(proj2));
  3578. }
  3579. // [set.union] set_union
  3580. // Reference: https://wg21.link/set.union
  3581. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3582. // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
  3583. // range does not overlap with either of the original ranges.
  3584. //
  3585. // Effects: Constructs a sorted union of the elements from the two ranges; that
  3586. // is, the set of elements that are present in one or both of the ranges.
  3587. //
  3588. // Returns: The end of the constructed range.
  3589. //
  3590. // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
  3591. // comparisons and applications of each projection.
  3592. //
  3593. // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
  3594. // equivalent to each other and `[first2, last2)` contains `n` elements that are
  3595. // equivalent to them, then all `m` elements from the first range are copied to
  3596. // the output range, in order, and then the final `max(n - m , 0)` elements from
  3597. // the second range are copied to the output range, in order.
  3598. //
  3599. // Reference: https://wg21.link/set.union#:~:text=ranges::set_union(I1
  3600. template <typename InputIterator1,
  3601. typename InputIterator2,
  3602. typename OutputIterator,
  3603. typename Comp = ranges::less,
  3604. typename Proj1 = identity,
  3605. typename Proj2 = identity,
  3606. typename = internal::iterator_category_t<InputIterator1>,
  3607. typename = internal::iterator_category_t<InputIterator2>,
  3608. typename = internal::iterator_category_t<OutputIterator>,
  3609. typename = indirect_result_t<Comp&,
  3610. projected<InputIterator1, Proj1>,
  3611. projected<InputIterator2, Proj2>>,
  3612. typename = indirect_result_t<Comp&,
  3613. projected<InputIterator2, Proj2>,
  3614. projected<InputIterator1, Proj1>>>
  3615. constexpr auto set_union(InputIterator1 first1,
  3616. InputIterator1 last1,
  3617. InputIterator2 first2,
  3618. InputIterator2 last2,
  3619. OutputIterator result,
  3620. Comp comp = {},
  3621. Proj1 proj1 = {},
  3622. Proj2 proj2 = {}) {
  3623. // Needs to opt-in to all permutations, since std::set_union expects
  3624. // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
  3625. return std::set_union(
  3626. first1, last1, first2, last2, result,
  3627. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3628. }
  3629. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3630. // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
  3631. // overlap with either of the original ranges.
  3632. //
  3633. // Effects: Constructs a sorted union of the elements from the two ranges; that
  3634. // is, the set of elements that are present in one or both of the ranges.
  3635. //
  3636. // Returns: The end of the constructed range.
  3637. //
  3638. // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
  3639. // applications of each projection.
  3640. //
  3641. // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
  3642. // each other and `range2` contains `n` elements that are equivalent to them,
  3643. // then all `m` elements from the first range are copied to the output range, in
  3644. // order, and then the final `max(n - m , 0)` elements from the second range are
  3645. // copied to the output range, in order.
  3646. //
  3647. // Reference: https://wg21.link/set.union#:~:text=ranges::set_union(R1
  3648. template <typename Range1,
  3649. typename Range2,
  3650. typename OutputIterator,
  3651. typename Comp = ranges::less,
  3652. typename Proj1 = identity,
  3653. typename Proj2 = identity,
  3654. typename = internal::range_category_t<Range1>,
  3655. typename = internal::range_category_t<Range2>,
  3656. typename = internal::iterator_category_t<OutputIterator>,
  3657. typename = indirect_result_t<Comp&,
  3658. projected<iterator_t<Range1>, Proj1>,
  3659. projected<iterator_t<Range2>, Proj2>>,
  3660. typename = indirect_result_t<Comp&,
  3661. projected<iterator_t<Range2>, Proj2>,
  3662. projected<iterator_t<Range1>, Proj1>>>
  3663. constexpr auto set_union(Range1&& range1,
  3664. Range2&& range2,
  3665. OutputIterator result,
  3666. Comp comp = {},
  3667. Proj1 proj1 = {},
  3668. Proj2 proj2 = {}) {
  3669. return ranges::set_union(ranges::begin(range1), ranges::end(range1),
  3670. ranges::begin(range2), ranges::end(range2), result,
  3671. std::move(comp), std::move(proj1), std::move(proj2));
  3672. }
  3673. // [set.intersection] set_intersection
  3674. // Reference: https://wg21.link/set.intersection
  3675. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3676. // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
  3677. // range does not overlap with either of the original ranges.
  3678. //
  3679. // Effects: Constructs a sorted intersection of the elements from the two
  3680. // ranges; that is, the set of elements that are present in both of the ranges.
  3681. //
  3682. // Returns: The end of the constructed range.
  3683. //
  3684. // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
  3685. // comparisons and applications of each projection.
  3686. //
  3687. // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
  3688. // equivalent to each other and `[first2, last2)` contains `n` elements that are
  3689. // equivalent to them, the first `min(m, n)` elements are copied from the first
  3690. // range to the output range, in order.
  3691. //
  3692. // Reference:
  3693. // https://wg21.link/set.intersection#:~:text=ranges::set_intersection(I1
  3694. template <typename InputIterator1,
  3695. typename InputIterator2,
  3696. typename OutputIterator,
  3697. typename Comp = ranges::less,
  3698. typename Proj1 = identity,
  3699. typename Proj2 = identity,
  3700. typename = internal::iterator_category_t<InputIterator1>,
  3701. typename = internal::iterator_category_t<InputIterator2>,
  3702. typename = internal::iterator_category_t<OutputIterator>,
  3703. typename = indirect_result_t<Comp&,
  3704. projected<InputIterator1, Proj1>,
  3705. projected<InputIterator2, Proj2>>,
  3706. typename = indirect_result_t<Comp&,
  3707. projected<InputIterator2, Proj2>,
  3708. projected<InputIterator1, Proj1>>>
  3709. constexpr auto set_intersection(InputIterator1 first1,
  3710. InputIterator1 last1,
  3711. InputIterator2 first2,
  3712. InputIterator2 last2,
  3713. OutputIterator result,
  3714. Comp comp = {},
  3715. Proj1 proj1 = {},
  3716. Proj2 proj2 = {}) {
  3717. // Needs to opt-in to all permutations, since std::set_intersection expects
  3718. // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
  3719. return std::set_intersection(
  3720. first1, last1, first2, last2, result,
  3721. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3722. }
  3723. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3724. // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
  3725. // overlap with either of the original ranges.
  3726. //
  3727. // Effects: Constructs a sorted intersection of the elements from the two
  3728. // ranges; that is, the set of elements that are present in both of the ranges.
  3729. //
  3730. // Returns: The end of the constructed range.
  3731. //
  3732. // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
  3733. // applications of each projection.
  3734. //
  3735. // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
  3736. // each other and `range2` contains `n` elements that are equivalent to them,
  3737. // the first `min(m, n)` elements are copied from the first range to the output
  3738. // range, in order.
  3739. //
  3740. // Reference:
  3741. // https://wg21.link/set.intersection#:~:text=ranges::set_intersection(R1
  3742. template <typename Range1,
  3743. typename Range2,
  3744. typename OutputIterator,
  3745. typename Comp = ranges::less,
  3746. typename Proj1 = identity,
  3747. typename Proj2 = identity,
  3748. typename = internal::range_category_t<Range1>,
  3749. typename = internal::range_category_t<Range2>,
  3750. typename = internal::iterator_category_t<OutputIterator>,
  3751. typename = indirect_result_t<Comp&,
  3752. projected<iterator_t<Range1>, Proj1>,
  3753. projected<iterator_t<Range2>, Proj2>>,
  3754. typename = indirect_result_t<Comp&,
  3755. projected<iterator_t<Range2>, Proj2>,
  3756. projected<iterator_t<Range1>, Proj1>>>
  3757. constexpr auto set_intersection(Range1&& range1,
  3758. Range2&& range2,
  3759. OutputIterator result,
  3760. Comp comp = {},
  3761. Proj1 proj1 = {},
  3762. Proj2 proj2 = {}) {
  3763. return ranges::set_intersection(ranges::begin(range1), ranges::end(range1),
  3764. ranges::begin(range2), ranges::end(range2),
  3765. result, std::move(comp), std::move(proj1),
  3766. std::move(proj2));
  3767. }
  3768. // [set.difference] set_difference
  3769. // Reference: https://wg21.link/set.difference
  3770. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3771. // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
  3772. // range does not overlap with either of the original ranges.
  3773. //
  3774. // Effects: Copies the elements of the range `[first1, last1)` which are not
  3775. // present in the range `[first2, last2)` to the range beginning at `result`.
  3776. // The elements in the constructed range are sorted.
  3777. //
  3778. // Returns: The end of the constructed range.
  3779. //
  3780. // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
  3781. // comparisons and applications of each projection.
  3782. //
  3783. // Remarks: If `[first1, last1)` contains `m` elements that are equivalent to
  3784. // each other and `[first2, last2)` contains `n` elements that are equivalent to
  3785. // them, the last `max(m - n, 0)` elements from `[first1, last1)` are copied to
  3786. // the output range, in order.
  3787. //
  3788. // Reference:
  3789. // https://wg21.link/set.difference#:~:text=ranges::set_difference(I1
  3790. template <typename InputIterator1,
  3791. typename InputIterator2,
  3792. typename OutputIterator,
  3793. typename Comp = ranges::less,
  3794. typename Proj1 = identity,
  3795. typename Proj2 = identity,
  3796. typename = internal::iterator_category_t<InputIterator1>,
  3797. typename = internal::iterator_category_t<InputIterator2>,
  3798. typename = internal::iterator_category_t<OutputIterator>,
  3799. typename = indirect_result_t<Comp&,
  3800. projected<InputIterator1, Proj1>,
  3801. projected<InputIterator2, Proj2>>,
  3802. typename = indirect_result_t<Comp&,
  3803. projected<InputIterator2, Proj2>,
  3804. projected<InputIterator1, Proj1>>>
  3805. constexpr auto set_difference(InputIterator1 first1,
  3806. InputIterator1 last1,
  3807. InputIterator2 first2,
  3808. InputIterator2 last2,
  3809. OutputIterator result,
  3810. Comp comp = {},
  3811. Proj1 proj1 = {},
  3812. Proj2 proj2 = {}) {
  3813. // Needs to opt-in to all permutations, since std::set_difference expects
  3814. // comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to compile.
  3815. return std::set_difference(
  3816. first1, last1, first2, last2, result,
  3817. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3818. }
  3819. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3820. // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
  3821. // overlap with either of the original ranges.
  3822. //
  3823. // Effects: Copies the elements of `range1` which are not present in `range2`
  3824. // to the range beginning at `result`. The elements in the constructed range are
  3825. // sorted.
  3826. //
  3827. // Returns: The end of the constructed range.
  3828. //
  3829. // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
  3830. // applications of each projection.
  3831. //
  3832. // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
  3833. // each other and `range2` contains `n` elements that are equivalent to them,
  3834. // the last `max(m - n, 0)` elements from `range1` are copied to the output
  3835. // range, in order.
  3836. //
  3837. // Reference:
  3838. // https://wg21.link/set.difference#:~:text=ranges::set_difference(R1
  3839. template <typename Range1,
  3840. typename Range2,
  3841. typename OutputIterator,
  3842. typename Comp = ranges::less,
  3843. typename Proj1 = identity,
  3844. typename Proj2 = identity,
  3845. typename = internal::range_category_t<Range1>,
  3846. typename = internal::range_category_t<Range2>,
  3847. typename = internal::iterator_category_t<OutputIterator>,
  3848. typename = indirect_result_t<Comp&,
  3849. projected<iterator_t<Range1>, Proj1>,
  3850. projected<iterator_t<Range2>, Proj2>>,
  3851. typename = indirect_result_t<Comp&,
  3852. projected<iterator_t<Range2>, Proj2>,
  3853. projected<iterator_t<Range1>, Proj1>>>
  3854. constexpr auto set_difference(Range1&& range1,
  3855. Range2&& range2,
  3856. OutputIterator result,
  3857. Comp comp = {},
  3858. Proj1 proj1 = {},
  3859. Proj2 proj2 = {}) {
  3860. return ranges::set_difference(ranges::begin(range1), ranges::end(range1),
  3861. ranges::begin(range2), ranges::end(range2),
  3862. result, std::move(comp), std::move(proj1),
  3863. std::move(proj2));
  3864. }
  3865. // [set.symmetric.difference] set_symmetric_difference
  3866. // Reference: https://wg21.link/set.symmetric.difference
  3867. // Preconditions: The ranges `[first1, last1)` and `[first2, last2)` are sorted
  3868. // with respect to `comp` and `proj1` or `proj2`, respectively. The resulting
  3869. // range does not overlap with either of the original ranges.
  3870. //
  3871. // Effects: Copies the elements of the range `[first1, last1)` that are not
  3872. // present in the range `[first2, last2)`, and the elements of the range
  3873. // `[first2, last2)` that are not present in the range `[first1, last1)` to the
  3874. // range beginning at `result`. The elements in the constructed range are
  3875. // sorted.
  3876. //
  3877. // Returns: The end of the constructed range.
  3878. //
  3879. // Complexity: At most `2 * ((last1 - first1) + (last2 - first2)) - 1`
  3880. // comparisons and applications of each projection.
  3881. //
  3882. // Remarks: Stable. If `[first1, last1)` contains `m` elements that are
  3883. // equivalent to each other and `[first2, last2)` contains `n` elements that are
  3884. // equivalent to them, then `|m - n|` of those elements shall be copied to the
  3885. // output range: the last `m - n` of these elements from `[first1, last1)` if
  3886. // `m > n`, and the last `n - m` of these elements from `[first2, last2)` if
  3887. // `m < n`. In either case, the elements are copied in order.
  3888. //
  3889. // Reference:
  3890. // https://wg21.link/set.symmetric.difference#:~:text=set_symmetric_difference(I1
  3891. template <typename InputIterator1,
  3892. typename InputIterator2,
  3893. typename OutputIterator,
  3894. typename Comp = ranges::less,
  3895. typename Proj1 = identity,
  3896. typename Proj2 = identity,
  3897. typename = internal::iterator_category_t<InputIterator1>,
  3898. typename = internal::iterator_category_t<InputIterator2>,
  3899. typename = internal::iterator_category_t<OutputIterator>,
  3900. typename = indirect_result_t<Comp&,
  3901. projected<InputIterator1, Proj1>,
  3902. projected<InputIterator2, Proj2>>,
  3903. typename = indirect_result_t<Comp&,
  3904. projected<InputIterator2, Proj2>,
  3905. projected<InputIterator1, Proj1>>>
  3906. constexpr auto set_symmetric_difference(InputIterator1 first1,
  3907. InputIterator1 last1,
  3908. InputIterator2 first2,
  3909. InputIterator2 last2,
  3910. OutputIterator result,
  3911. Comp comp = {},
  3912. Proj1 proj1 = {},
  3913. Proj2 proj2 = {}) {
  3914. // Needs to opt-in to all permutations, since std::set_symmetric_difference
  3915. // expects comp(proj1(lhs), proj2(rhs)) and comp(proj2(lhs), proj1(rhs)) to
  3916. // compile.
  3917. return std::set_symmetric_difference(
  3918. first1, last1, first2, last2, result,
  3919. internal::PermutedProjectedBinaryPredicate(comp, proj1, proj2));
  3920. }
  3921. // Preconditions: The ranges `range1` and `range2` are sorted with respect to
  3922. // `comp` and `proj1` or `proj2`, respectively. The resulting range does not
  3923. // overlap with either of the original ranges.
  3924. //
  3925. // Effects: Copies the elements of `range1` that are not present in `range2`,
  3926. // and the elements of `range2` that are not present in `range1` to the range
  3927. // beginning at `result`. The elements in the constructed range are sorted.
  3928. //
  3929. // Returns: The end of the constructed range.
  3930. //
  3931. // Complexity: At most `2 * (size(range1) + size(range2)) - 1` comparisons and
  3932. // applications of each projection.
  3933. //
  3934. // Remarks: Stable. If `range1` contains `m` elements that are equivalent to
  3935. // each other and `range2` contains `n` elements that are equivalent to them,
  3936. // then `|m - n|` of those elements shall be copied to the output range: the
  3937. // last `m - n` of these elements from `range1` if `m > n`, and the last `n - m`
  3938. // of these elements from `range2` if `m < n`. In either case, the elements are
  3939. // copied in order.
  3940. //
  3941. // Reference:
  3942. // https://wg21.link/set.symmetric.difference#:~:text=set_symmetric_difference(R1
  3943. template <typename Range1,
  3944. typename Range2,
  3945. typename OutputIterator,
  3946. typename Comp = ranges::less,
  3947. typename Proj1 = identity,
  3948. typename Proj2 = identity,
  3949. typename = internal::range_category_t<Range1>,
  3950. typename = internal::range_category_t<Range2>,
  3951. typename = internal::iterator_category_t<OutputIterator>,
  3952. typename = indirect_result_t<Comp&,
  3953. projected<iterator_t<Range1>, Proj1>,
  3954. projected<iterator_t<Range2>, Proj2>>,
  3955. typename = indirect_result_t<Comp&,
  3956. projected<iterator_t<Range2>, Proj2>,
  3957. projected<iterator_t<Range1>, Proj1>>>
  3958. constexpr auto set_symmetric_difference(Range1&& range1,
  3959. Range2&& range2,
  3960. OutputIterator result,
  3961. Comp comp = {},
  3962. Proj1 proj1 = {},
  3963. Proj2 proj2 = {}) {
  3964. return ranges::set_symmetric_difference(
  3965. ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
  3966. ranges::end(range2), result, std::move(comp), std::move(proj1),
  3967. std::move(proj2));
  3968. }
  3969. // [alg.heap.operations] Heap operations
  3970. // Reference: https://wg21.link/alg.heap.operations
  3971. // [push.heap] push_heap
  3972. // Reference: https://wg21.link/push.heap
  3973. // Preconditions: The range `[first, last - 1)` is a valid heap with respect to
  3974. // `comp` and `proj`.
  3975. //
  3976. // Effects: Places the value in the location `last - 1` into the resulting heap
  3977. // `[first, last)`.
  3978. //
  3979. // Returns: `last`.
  3980. //
  3981. // Complexity: At most `log(last - first)` comparisons and twice as many
  3982. // projections.
  3983. //
  3984. // Reference: https://wg21.link/push.heap#:~:text=ranges::push_heap(I
  3985. template <typename RandomAccessIterator,
  3986. typename Comp = ranges::less,
  3987. typename Proj = identity,
  3988. typename = internal::iterator_category_t<RandomAccessIterator>,
  3989. typename = indirect_result_t<Comp&,
  3990. projected<RandomAccessIterator, Proj>,
  3991. projected<RandomAccessIterator, Proj>>>
  3992. constexpr auto push_heap(RandomAccessIterator first,
  3993. RandomAccessIterator last,
  3994. Comp comp = {},
  3995. Proj proj = {}) {
  3996. std::push_heap(first, last,
  3997. internal::ProjectedBinaryPredicate(comp, proj, proj));
  3998. return last;
  3999. }
  4000. // Preconditions: The range `[begin(range), end(range) - 1)` is a valid heap
  4001. // with respect to `comp` and `proj`.
  4002. //
  4003. // Effects: Places the value in the location `end(range) - 1` into the resulting
  4004. // heap `range`.
  4005. //
  4006. // Returns: `end(range)`.
  4007. //
  4008. // Complexity: At most `log(size(range))` comparisons and twice as many
  4009. // projections.
  4010. //
  4011. // Reference: https://wg21.link/push.heap#:~:text=ranges::push_heap(R
  4012. template <typename Range,
  4013. typename Comp = ranges::less,
  4014. typename Proj = identity,
  4015. typename = internal::range_category_t<Range>,
  4016. typename = indirect_result_t<Comp&,
  4017. projected<iterator_t<Range>, Proj>,
  4018. projected<iterator_t<Range>, Proj>>>
  4019. constexpr auto push_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
  4020. return ranges::push_heap(ranges::begin(range), ranges::end(range),
  4021. std::move(comp), std::move(proj));
  4022. }
  4023. // [pop.heap] pop_heap
  4024. // Reference: https://wg21.link/pop.heap
  4025. // Preconditions: The range `[first, last)` is a valid non-empty heap with
  4026. // respect to `comp` and `proj`.
  4027. //
  4028. // Effects: Swaps the value in the location `first` with the value in the
  4029. // location `last - 1` and makes `[first, last - 1)` into a heap with respect to
  4030. // `comp` and `proj`.
  4031. //
  4032. // Returns: `last`.
  4033. //
  4034. // Complexity: At most `2 log(last - first)` comparisons and twice as many
  4035. // projections.
  4036. //
  4037. // Reference: https://wg21.link/pop.heap#:~:text=ranges::pop_heap(I
  4038. template <typename RandomAccessIterator,
  4039. typename Comp = ranges::less,
  4040. typename Proj = identity,
  4041. typename = internal::iterator_category_t<RandomAccessIterator>,
  4042. typename = indirect_result_t<Comp&,
  4043. projected<RandomAccessIterator, Proj>,
  4044. projected<RandomAccessIterator, Proj>>>
  4045. constexpr auto pop_heap(RandomAccessIterator first,
  4046. RandomAccessIterator last,
  4047. Comp comp = {},
  4048. Proj proj = {}) {
  4049. std::pop_heap(first, last,
  4050. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4051. return last;
  4052. }
  4053. // Preconditions: `range` is a valid non-empty heap with respect to `comp` and
  4054. // `proj`.
  4055. //
  4056. // Effects: Swaps the value in the location `begin(range)` with the value in the
  4057. // location `end(range) - 1` and makes `[begin(range), end(range) - 1)` into a
  4058. // heap with respect to `comp` and `proj`.
  4059. //
  4060. // Returns: `end(range)`.
  4061. //
  4062. // Complexity: At most `2 log(size(range))` comparisons and twice as many
  4063. // projections.
  4064. //
  4065. // Reference: https://wg21.link/pop.heap#:~:text=ranges::pop_heap(R
  4066. template <typename Range,
  4067. typename Comp = ranges::less,
  4068. typename Proj = identity,
  4069. typename = internal::range_category_t<Range>,
  4070. typename = indirect_result_t<Comp&,
  4071. projected<iterator_t<Range>, Proj>,
  4072. projected<iterator_t<Range>, Proj>>>
  4073. constexpr auto pop_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
  4074. return ranges::pop_heap(ranges::begin(range), ranges::end(range),
  4075. std::move(comp), std::move(proj));
  4076. }
  4077. // [make.heap] make_heap
  4078. // Reference: https://wg21.link/make.heap
  4079. // Effects: Constructs a heap with respect to `comp` and `proj` out of the range
  4080. // `[first, last)`.
  4081. //
  4082. // Returns: `last`.
  4083. //
  4084. // Complexity: At most `3 * (last - first)` comparisons and twice as many
  4085. // projections.
  4086. //
  4087. // Reference: https://wg21.link/make.heap#:~:text=ranges::make_heap(I
  4088. template <typename RandomAccessIterator,
  4089. typename Comp = ranges::less,
  4090. typename Proj = identity,
  4091. typename = internal::iterator_category_t<RandomAccessIterator>,
  4092. typename = indirect_result_t<Comp&,
  4093. projected<RandomAccessIterator, Proj>,
  4094. projected<RandomAccessIterator, Proj>>>
  4095. constexpr auto make_heap(RandomAccessIterator first,
  4096. RandomAccessIterator last,
  4097. Comp comp = {},
  4098. Proj proj = {}) {
  4099. std::make_heap(first, last,
  4100. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4101. return last;
  4102. }
  4103. // Effects: Constructs a heap with respect to `comp` and `proj` out of `range`.
  4104. //
  4105. // Returns: `end(range)`.
  4106. //
  4107. // Complexity: At most `3 * size(range)` comparisons and twice as many
  4108. // projections.
  4109. //
  4110. // Reference: https://wg21.link/make.heap#:~:text=ranges::make_heap(R
  4111. template <typename Range,
  4112. typename Comp = ranges::less,
  4113. typename Proj = identity,
  4114. typename = internal::range_category_t<Range>,
  4115. typename = indirect_result_t<Comp&,
  4116. projected<iterator_t<Range>, Proj>,
  4117. projected<iterator_t<Range>, Proj>>>
  4118. constexpr auto make_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
  4119. return ranges::make_heap(ranges::begin(range), ranges::end(range),
  4120. std::move(comp), std::move(proj));
  4121. }
  4122. // [sort.heap] sort_heap
  4123. // Reference: https://wg21.link/sort.heap
  4124. // Preconditions: The range `[first, last)` is a valid heap with respect to
  4125. // `comp` and `proj`.
  4126. //
  4127. // Effects: Sorts elements in the heap `[first, last)` with respect to `comp`
  4128. // and `proj`.
  4129. //
  4130. // Returns: `last`.
  4131. //
  4132. // Complexity: At most `2 N log N` comparisons, where `N = last - first`, and
  4133. // twice as many projections.
  4134. //
  4135. // Reference: https://wg21.link/sort.heap#:~:text=ranges::sort_heap(I
  4136. template <typename RandomAccessIterator,
  4137. typename Comp = ranges::less,
  4138. typename Proj = identity,
  4139. typename = internal::iterator_category_t<RandomAccessIterator>,
  4140. typename = indirect_result_t<Comp&,
  4141. projected<RandomAccessIterator, Proj>,
  4142. projected<RandomAccessIterator, Proj>>>
  4143. constexpr auto sort_heap(RandomAccessIterator first,
  4144. RandomAccessIterator last,
  4145. Comp comp = {},
  4146. Proj proj = {}) {
  4147. std::sort_heap(first, last,
  4148. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4149. return last;
  4150. }
  4151. // Preconditions: `range` is a valid heap with respect to `comp` and `proj`.
  4152. //
  4153. // Effects: Sorts elements in the heap `range` with respect to `comp` and
  4154. // `proj`.
  4155. //
  4156. // Returns: `end(range)`.
  4157. //
  4158. // Complexity: At most `2 N log N` comparisons, where `N = size(range)`, and
  4159. // twice as many projections.
  4160. //
  4161. // Reference: https://wg21.link/sort.heap#:~:text=ranges::sort_heap(R
  4162. template <typename Range,
  4163. typename Comp = ranges::less,
  4164. typename Proj = identity,
  4165. typename = internal::range_category_t<Range>,
  4166. typename = indirect_result_t<Comp&,
  4167. projected<iterator_t<Range>, Proj>,
  4168. projected<iterator_t<Range>, Proj>>>
  4169. constexpr auto sort_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
  4170. return ranges::sort_heap(ranges::begin(range), ranges::end(range),
  4171. std::move(comp), std::move(proj));
  4172. }
  4173. // [is.heap] is_heap
  4174. // Reference: https://wg21.link/is.heap
  4175. // Returns: Whether the range `[first, last)` is a heap with respect to `comp`
  4176. // and `proj`.
  4177. //
  4178. // Complexity: Linear.
  4179. //
  4180. // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap(I
  4181. template <typename RandomAccessIterator,
  4182. typename Comp = ranges::less,
  4183. typename Proj = identity,
  4184. typename = internal::iterator_category_t<RandomAccessIterator>,
  4185. typename = indirect_result_t<Comp&,
  4186. projected<RandomAccessIterator, Proj>,
  4187. projected<RandomAccessIterator, Proj>>>
  4188. constexpr auto is_heap(RandomAccessIterator first,
  4189. RandomAccessIterator last,
  4190. Comp comp = {},
  4191. Proj proj = {}) {
  4192. return std::is_heap(first, last,
  4193. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4194. }
  4195. // Returns: Whether `range` is a heap with respect to `comp` and `proj`.
  4196. //
  4197. // Complexity: Linear.
  4198. //
  4199. // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap(R
  4200. template <typename Range,
  4201. typename Comp = ranges::less,
  4202. typename Proj = identity,
  4203. typename = internal::range_category_t<Range>,
  4204. typename = indirect_result_t<Comp&,
  4205. projected<iterator_t<Range>, Proj>,
  4206. projected<iterator_t<Range>, Proj>>>
  4207. constexpr auto is_heap(Range&& range, Comp comp = {}, Proj proj = {}) {
  4208. return ranges::is_heap(ranges::begin(range), ranges::end(range),
  4209. std::move(comp), std::move(proj));
  4210. }
  4211. // Returns: The last iterator `i` in `[first, last]` for which the range
  4212. // `[first, i)` is a heap with respect to `comp` and `proj`.
  4213. //
  4214. // Complexity: Linear.
  4215. //
  4216. // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap_until(I
  4217. template <typename RandomAccessIterator,
  4218. typename Comp = ranges::less,
  4219. typename Proj = identity,
  4220. typename = internal::iterator_category_t<RandomAccessIterator>,
  4221. typename = indirect_result_t<Comp&,
  4222. projected<RandomAccessIterator, Proj>,
  4223. projected<RandomAccessIterator, Proj>>>
  4224. constexpr auto is_heap_until(RandomAccessIterator first,
  4225. RandomAccessIterator last,
  4226. Comp comp = {},
  4227. Proj proj = {}) {
  4228. return std::is_heap_until(
  4229. first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
  4230. }
  4231. // Returns: The last iterator `i` in `[begin(range), end(range)]` for which the
  4232. // range `[begin(range), i)` is a heap with respect to `comp` and `proj`.
  4233. //
  4234. // Complexity: Linear.
  4235. //
  4236. // Reference: https://wg21.link/is.heap#:~:text=ranges::is_heap_until(R
  4237. template <typename Range,
  4238. typename Comp = ranges::less,
  4239. typename Proj = identity,
  4240. typename = internal::range_category_t<Range>,
  4241. typename = indirect_result_t<Comp&,
  4242. projected<iterator_t<Range>, Proj>,
  4243. projected<iterator_t<Range>, Proj>>>
  4244. constexpr auto is_heap_until(Range&& range, Comp comp = {}, Proj proj = {}) {
  4245. return ranges::is_heap_until(ranges::begin(range), ranges::end(range),
  4246. std::move(comp), std::move(proj));
  4247. }
  4248. // [alg.min.max] Minimum and maximum
  4249. // Reference: https://wg21.link/alg.min.max
  4250. // Returns: The smaller value. Returns the first argument when the arguments are
  4251. // equivalent.
  4252. //
  4253. // Complexity: Exactly one comparison and two applications of the projection, if
  4254. // any.
  4255. //
  4256. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min
  4257. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4258. constexpr const T& min(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
  4259. return base::invoke(comp, base::invoke(proj, b), base::invoke(proj, a)) ? b
  4260. : a;
  4261. }
  4262. // Preconditions: `!empty(ilist)`.
  4263. //
  4264. // Returns: The smallest value in the input range. Returns a copy of the
  4265. // leftmost element when several elements are equivalent to the smallest.
  4266. //
  4267. // Complexity: Exactly `size(ilist) - 1` comparisons and twice as many
  4268. // applications of the projection, if any.
  4269. //
  4270. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min(initializer_list
  4271. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4272. constexpr T min(std::initializer_list<T> ilist,
  4273. Comp comp = {},
  4274. Proj proj = {}) {
  4275. return *std::min_element(
  4276. ilist.begin(), ilist.end(),
  4277. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4278. }
  4279. // Preconditions: `!empty(range)`.
  4280. //
  4281. // Returns: The smallest value in the input range. Returns a copy of the
  4282. // leftmost element when several elements are equivalent to the smallest.
  4283. //
  4284. // Complexity: Exactly `size(range) - 1` comparisons and twice as many
  4285. // applications of the projection, if any.
  4286. //
  4287. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min(R
  4288. template <typename Range,
  4289. typename Comp = ranges::less,
  4290. typename Proj = identity,
  4291. typename = internal::range_category_t<Range>>
  4292. constexpr auto min(Range&& range, Comp comp = {}, Proj proj = {}) {
  4293. return *std::min_element(
  4294. ranges::begin(range), ranges::end(range),
  4295. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4296. }
  4297. // Returns: The larger value. Returns the first argument when the arguments are
  4298. // equivalent.
  4299. //
  4300. // Complexity: Exactly one comparison and two applications of the projection, if
  4301. // any.
  4302. //
  4303. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max
  4304. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4305. constexpr const T& max(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
  4306. return base::invoke(comp, base::invoke(proj, a), base::invoke(proj, b)) ? b
  4307. : a;
  4308. }
  4309. // Preconditions: `!empty(ilist)`.
  4310. //
  4311. // Returns: The largest value in the input range. Returns a copy of the leftmost
  4312. // element when several elements are equivalent to the largest.
  4313. //
  4314. // Complexity: Exactly `size(ilist) - 1` comparisons and twice as many
  4315. // applications of the projection, if any.
  4316. //
  4317. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max(initializer_list
  4318. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4319. constexpr T max(std::initializer_list<T> ilist,
  4320. Comp comp = {},
  4321. Proj proj = {}) {
  4322. return *std::max_element(
  4323. ilist.begin(), ilist.end(),
  4324. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4325. }
  4326. // Preconditions: `!empty(range)`.
  4327. //
  4328. // Returns: The largest value in the input range. Returns a copy of the leftmost
  4329. // element when several elements are equivalent to the smallest.
  4330. //
  4331. // Complexity: Exactly `size(range) - 1` comparisons and twice as many
  4332. // applications of the projection, if any.
  4333. //
  4334. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max(R
  4335. template <typename Range,
  4336. typename Comp = ranges::less,
  4337. typename Proj = identity,
  4338. typename = internal::range_category_t<Range>>
  4339. constexpr auto max(Range&& range, Comp comp = {}, Proj proj = {}) {
  4340. return *std::max_element(
  4341. ranges::begin(range), ranges::end(range),
  4342. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4343. }
  4344. // Returns: `{b, a}` if `b` is smaller than `a`, and `{a, b}` otherwise.
  4345. //
  4346. // Complexity: Exactly one comparison and two applications of the projection, if
  4347. // any.
  4348. //
  4349. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax
  4350. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4351. constexpr auto minmax(const T& a, const T& b, Comp comp = {}, Proj proj = {}) {
  4352. return std::minmax(a, b,
  4353. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4354. }
  4355. // Preconditions: `!empty(ilist)`.
  4356. //
  4357. // Returns: Let `X` be the return type. Returns `X{x, y}`, where `x` is a copy
  4358. // of the leftmost element with the smallest value and `y` a copy of the
  4359. // rightmost element with the largest value in the input range.
  4360. //
  4361. // Complexity: At most `(3/2) size(ilist)` applications of the corresponding
  4362. // predicate and twice as many applications of the projection, if any.
  4363. //
  4364. // Reference:
  4365. // https://wg21.link/alg.min.max#:~:text=ranges::minmax(initializer_list
  4366. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4367. constexpr auto minmax(std::initializer_list<T> ilist,
  4368. Comp comp = {},
  4369. Proj proj = {}) {
  4370. auto it =
  4371. std::minmax_element(ranges::begin(ilist), ranges::end(ilist),
  4372. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4373. return std::pair<T, T>{*it.first, *it.second};
  4374. }
  4375. // Preconditions: `!empty(range)`.
  4376. //
  4377. // Returns: Let `X` be the return type. Returns `X{x, y}`, where `x` is a copy
  4378. // of the leftmost element with the smallest value and `y` a copy of the
  4379. // rightmost element with the largest value in the input range.
  4380. //
  4381. // Complexity: At most `(3/2) size(range)` applications of the corresponding
  4382. // predicate and twice as many applications of the projection, if any.
  4383. //
  4384. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax(R
  4385. template <typename Range,
  4386. typename Comp = ranges::less,
  4387. typename Proj = identity,
  4388. typename = internal::range_category_t<Range>>
  4389. constexpr auto minmax(Range&& range, Comp comp = {}, Proj proj = {}) {
  4390. using T = range_value_t<Range>;
  4391. auto it =
  4392. std::minmax_element(ranges::begin(range), ranges::end(range),
  4393. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4394. return std::pair<T, T>{*it.first, *it.second};
  4395. }
  4396. // Returns: The first iterator i in the range `[first, last)` such that for
  4397. // every iterator `j` in the range `[first, last)`,
  4398. // `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`. Returns
  4399. // `last` if `first == last`.
  4400. //
  4401. // Complexity: Exactly `max(last - first - 1, 0)` comparisons and twice as
  4402. // many projections.
  4403. //
  4404. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min_element(I
  4405. template <typename ForwardIterator,
  4406. typename Comp = ranges::less,
  4407. typename Proj = identity,
  4408. typename = internal::iterator_category_t<ForwardIterator>,
  4409. typename = indirect_result_t<Comp&,
  4410. projected<ForwardIterator, Proj>,
  4411. projected<ForwardIterator, Proj>>>
  4412. constexpr auto min_element(ForwardIterator first,
  4413. ForwardIterator last,
  4414. Comp comp = {},
  4415. Proj proj = {}) {
  4416. return std::min_element(first, last,
  4417. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4418. }
  4419. // Returns: The first iterator i in `range` such that for every iterator `j` in
  4420. // `range`, `bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
  4421. // Returns `end(range)` if `empty(range)`.
  4422. //
  4423. // Complexity: Exactly `max(size(range) - 1, 0)` comparisons and twice as many
  4424. // projections.
  4425. //
  4426. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::min_element(R
  4427. template <typename Range,
  4428. typename Comp = ranges::less,
  4429. typename Proj = identity,
  4430. typename = internal::range_category_t<Range>,
  4431. typename = indirect_result_t<Comp&,
  4432. projected<iterator_t<Range>, Proj>,
  4433. projected<iterator_t<Range>, Proj>>>
  4434. constexpr auto min_element(Range&& range, Comp comp = {}, Proj proj = {}) {
  4435. return ranges::min_element(ranges::begin(range), ranges::end(range),
  4436. std::move(comp), std::move(proj));
  4437. }
  4438. // Returns: The first iterator i in the range `[first, last)` such that for
  4439. // every iterator `j` in the range `[first, last)`,
  4440. // `bool(invoke(comp, invoke(proj, *i), invoke(proj, *j)))` is `false`.
  4441. // Returns `last` if `first == last`.
  4442. //
  4443. // Complexity: Exactly `max(last - first - 1, 0)` comparisons and twice as
  4444. // many projections.
  4445. //
  4446. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max_element(I
  4447. template <typename ForwardIterator,
  4448. typename Comp = ranges::less,
  4449. typename Proj = identity,
  4450. typename = internal::iterator_category_t<ForwardIterator>,
  4451. typename = indirect_result_t<Comp&,
  4452. projected<ForwardIterator, Proj>,
  4453. projected<ForwardIterator, Proj>>>
  4454. constexpr auto max_element(ForwardIterator first,
  4455. ForwardIterator last,
  4456. Comp comp = {},
  4457. Proj proj = {}) {
  4458. return std::max_element(first, last,
  4459. internal::ProjectedBinaryPredicate(comp, proj, proj));
  4460. }
  4461. // Returns: The first iterator i in `range` such that for every iterator `j`
  4462. // in `range`, `bool(invoke(comp, invoke(proj, *j), invoke(proj, *j)))` is
  4463. // `false`. Returns `end(range)` if `empty(range)`.
  4464. //
  4465. // Complexity: Exactly `max(size(range) - 1, 0)` comparisons and twice as many
  4466. // projections.
  4467. //
  4468. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::max_element(R
  4469. template <typename Range,
  4470. typename Comp = ranges::less,
  4471. typename Proj = identity,
  4472. typename = internal::range_category_t<Range>,
  4473. typename = indirect_result_t<Comp&,
  4474. projected<iterator_t<Range>, Proj>,
  4475. projected<iterator_t<Range>, Proj>>>
  4476. constexpr auto max_element(Range&& range, Comp comp = {}, Proj proj = {}) {
  4477. return ranges::max_element(ranges::begin(range), ranges::end(range),
  4478. std::move(comp), std::move(proj));
  4479. }
  4480. // Returns: `{first, first}` if `[first, last)` is empty, otherwise `{m, M}`,
  4481. // where `m` is the first iterator in `[first, last)` such that no iterator in
  4482. // the range refers to a smaller element, and where `M` is the last iterator
  4483. // in
  4484. // `[first, last)` such that no iterator in the range refers to a larger
  4485. // element.
  4486. //
  4487. // Complexity: Let `N` be `last - first`. At most `max(3/2 (N − 1), 0)`
  4488. // comparisons and twice as many applications of the projection, if any.
  4489. //
  4490. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax_element(I
  4491. template <typename ForwardIterator,
  4492. typename Comp = ranges::less,
  4493. typename Proj = identity,
  4494. typename = internal::iterator_category_t<ForwardIterator>,
  4495. typename = indirect_result_t<Comp&,
  4496. projected<ForwardIterator, Proj>,
  4497. projected<ForwardIterator, Proj>>>
  4498. constexpr auto minmax_element(ForwardIterator first,
  4499. ForwardIterator last,
  4500. Comp comp = {},
  4501. Proj proj = {}) {
  4502. return std::minmax_element(
  4503. first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
  4504. }
  4505. // Returns: `{begin(range), begin(range)}` if `range` is empty, otherwise
  4506. // `{m, M}`, where `m` is the first iterator in `range` such that no iterator
  4507. // in the range refers to a smaller element, and where `M` is the last
  4508. // iterator in `range` such that no iterator in the range refers to a larger
  4509. // element.
  4510. //
  4511. // Complexity: Let `N` be `size(range)`. At most `max(3/2 (N − 1), 0)`
  4512. // comparisons and twice as many applications of the projection, if any.
  4513. //
  4514. // Reference: https://wg21.link/alg.min.max#:~:text=ranges::minmax_element(R
  4515. template <typename Range,
  4516. typename Comp = ranges::less,
  4517. typename Proj = identity,
  4518. typename = internal::range_category_t<Range>,
  4519. typename = indirect_result_t<Comp&,
  4520. projected<iterator_t<Range>, Proj>,
  4521. projected<iterator_t<Range>, Proj>>>
  4522. constexpr auto minmax_element(Range&& range, Comp comp = {}, Proj proj = {}) {
  4523. return ranges::minmax_element(ranges::begin(range), ranges::end(range),
  4524. std::move(comp), std::move(proj));
  4525. }
  4526. // [alg.clamp] Bounded value
  4527. // Reference: https://wg21.link/alg.clamp
  4528. // Preconditions: `bool(invoke(comp, invoke(proj, hi), invoke(proj, lo)))` is
  4529. // `false`.
  4530. //
  4531. // Returns: `lo` if `bool(invoke(comp, invoke(proj, v), invoke(proj, lo)))` is
  4532. // `true`, `hi` if `bool(invoke(comp, invoke(proj, hi), invoke(proj, v)))` is
  4533. // `true`, otherwise `v`.
  4534. //
  4535. // Complexity: At most two comparisons and three applications of the
  4536. // projection.
  4537. //
  4538. // Reference: https://wg21.link/alg.clamp#:~:text=ranges::clamp
  4539. template <typename T, typename Comp = ranges::less, typename Proj = identity>
  4540. constexpr const T& clamp(const T& v,
  4541. const T& lo,
  4542. const T& hi,
  4543. Comp comp = {},
  4544. Proj proj = {}) {
  4545. auto&& projected_v = base::invoke(proj, v);
  4546. if (base::invoke(comp, projected_v, base::invoke(proj, lo)))
  4547. return lo;
  4548. return base::invoke(comp, base::invoke(proj, hi), projected_v) ? hi : v;
  4549. }
  4550. // [alg.lex.comparison] Lexicographical comparison
  4551. // Reference: https://wg21.link/alg.lex.comparison
  4552. // Returns: `true` if and only if the sequence of elements defined by the range
  4553. // `[first1, last1)` is lexicographically less than the sequence of elements
  4554. // defined by the range `[first2, last2)`.
  4555. //
  4556. // Complexity: At most `2 min(last1 - first1, last2 - first2)` applications of
  4557. // the corresponding comparison and each projection, if any.
  4558. //
  4559. // Remarks: If two sequences have the same number of elements and their
  4560. // corresponding elements (if any) are equivalent, then neither sequence is
  4561. // lexicographically less than the other. If one sequence is a proper prefix of
  4562. // the other, then the shorter sequence is lexicographically less than the
  4563. // longer sequence. Otherwise, the lexicographical comparison of the sequences
  4564. // yields the same result as the comparison of the first corresponding pair of
  4565. // elements that are not equivalent.
  4566. //
  4567. // Reference:
  4568. // https://wg21.link/alg.lex.comparison#:~:text=lexicographical_compare(I1
  4569. template <typename ForwardIterator1,
  4570. typename ForwardIterator2,
  4571. typename Comp = ranges::less,
  4572. typename Proj1 = identity,
  4573. typename Proj2 = identity,
  4574. typename = internal::iterator_category_t<ForwardIterator1>,
  4575. typename = internal::iterator_category_t<ForwardIterator2>,
  4576. typename = indirect_result_t<Comp&,
  4577. projected<ForwardIterator1, Proj1>,
  4578. projected<ForwardIterator2, Proj2>>,
  4579. typename = indirect_result_t<Comp&,
  4580. projected<ForwardIterator2, Proj2>,
  4581. projected<ForwardIterator1, Proj1>>>
  4582. constexpr bool lexicographical_compare(ForwardIterator1 first1,
  4583. ForwardIterator1 last1,
  4584. ForwardIterator2 first2,
  4585. ForwardIterator2 last2,
  4586. Comp comp = {},
  4587. Proj1 proj1 = {},
  4588. Proj2 proj2 = {}) {
  4589. for (; first1 != last1 && first2 != last2; ++first1, ++first2) {
  4590. auto&& projected_first1 = base::invoke(proj1, *first1);
  4591. auto&& projected_first2 = base::invoke(proj2, *first2);
  4592. if (base::invoke(comp, projected_first1, projected_first2))
  4593. return true;
  4594. if (base::invoke(comp, projected_first2, projected_first1))
  4595. return false;
  4596. }
  4597. // `first2 != last2` is equivalent to `first1 == last1 && first2 != last2`
  4598. // here, since we broke out of the loop above.
  4599. return first2 != last2;
  4600. }
  4601. // Returns: `true` if and only if the sequence of elements defined by `range1`
  4602. // is lexicographically less than the sequence of elements defined by `range2`.
  4603. //
  4604. // Complexity: At most `2 min(size(range1), size(range2))` applications of the
  4605. // corresponding comparison and each projection, if any.
  4606. //
  4607. // Remarks: If two sequences have the same number of elements and their
  4608. // corresponding elements (if any) are equivalent, then neither sequence is
  4609. // lexicographically less than the other. If one sequence is a proper prefix of
  4610. // the other, then the shorter sequence is lexicographically less than the
  4611. // longer sequence. Otherwise, the lexicographical comparison of the sequences
  4612. // yields the same result as the comparison of the first corresponding pair of
  4613. // elements that are not equivalent.
  4614. //
  4615. // Reference:
  4616. // https://wg21.link/alg.lex.comparison#:~:text=lexicographical_compare(R1
  4617. template <typename Range1,
  4618. typename Range2,
  4619. typename Comp = ranges::less,
  4620. typename Proj1 = identity,
  4621. typename Proj2 = identity,
  4622. typename = internal::range_category_t<Range1>,
  4623. typename = internal::range_category_t<Range2>,
  4624. typename = indirect_result_t<Comp&,
  4625. projected<iterator_t<Range1>, Proj1>,
  4626. projected<iterator_t<Range2>, Proj2>>,
  4627. typename = indirect_result_t<Comp&,
  4628. projected<iterator_t<Range2>, Proj2>,
  4629. projected<iterator_t<Range1>, Proj1>>>
  4630. constexpr bool lexicographical_compare(Range1&& range1,
  4631. Range2&& range2,
  4632. Comp comp = {},
  4633. Proj1 proj1 = {},
  4634. Proj2 proj2 = {}) {
  4635. return ranges::lexicographical_compare(
  4636. ranges::begin(range1), ranges::end(range1), ranges::begin(range2),
  4637. ranges::end(range2), std::move(comp), std::move(proj1), std::move(proj2));
  4638. }
  4639. // [alg.permutation.generators] Permutation generators
  4640. // Reference: https://wg21.link/alg.permutation.generators
  4641. // Effects: Takes a sequence defined by the range `[first, last)` and transforms
  4642. // it into the next permutation. The next permutation is found by assuming that
  4643. // the set of all permutations is lexicographically sorted with respect to
  4644. // `comp` and `proj`. If no such permutation exists, transforms the sequence
  4645. // into the first permutation; that is, the ascendingly-sorted one.
  4646. //
  4647. // Returns: `true` if a next permutation was found and otherwise `false`.
  4648. //
  4649. // Complexity: At most `(last - first) / 2` swaps.
  4650. //
  4651. // Reference:
  4652. // https://wg21.link/alg.permutation.generators#:~:text=next_permutation(I
  4653. template <typename BidirectionalIterator,
  4654. typename Comp = ranges::less,
  4655. typename Proj = identity,
  4656. typename = internal::iterator_category_t<BidirectionalIterator>,
  4657. typename = indirect_result_t<Comp&,
  4658. projected<BidirectionalIterator, Proj>,
  4659. projected<BidirectionalIterator, Proj>>>
  4660. constexpr auto next_permutation(BidirectionalIterator first,
  4661. BidirectionalIterator last,
  4662. Comp comp = {},
  4663. Proj proj = {}) {
  4664. return std::next_permutation(
  4665. first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
  4666. }
  4667. // Effects: Takes a sequence defined by `range` and transforms it into the next
  4668. // permutation. The next permutation is found by assuming that the set of all
  4669. // permutations is lexicographically sorted with respect to `comp` and `proj`.
  4670. // If no such permutation exists, transforms the sequence into the first
  4671. // permutation; that is, the ascendingly-sorted one.
  4672. //
  4673. // Returns: `true` if a next permutation was found and otherwise `false`.
  4674. //
  4675. // Complexity: At most `size(range) / 2` swaps.
  4676. //
  4677. // Reference:
  4678. // https://wg21.link/alg.permutation.generators#:~:text=next_permutation(R
  4679. template <typename Range,
  4680. typename Comp = ranges::less,
  4681. typename Proj = identity,
  4682. typename = internal::range_category_t<Range>,
  4683. typename = indirect_result_t<Comp&,
  4684. projected<iterator_t<Range>, Proj>,
  4685. projected<iterator_t<Range>, Proj>>>
  4686. constexpr auto next_permutation(Range&& range, Comp comp = {}, Proj proj = {}) {
  4687. return ranges::next_permutation(ranges::begin(range), ranges::end(range),
  4688. std::move(comp), std::move(proj));
  4689. }
  4690. // Effects: Takes a sequence defined by the range `[first, last)` and transforms
  4691. // it into the previous permutation. The previous permutation is found by
  4692. // assuming that the set of all permutations is lexicographically sorted with
  4693. // respect to `comp` and `proj`. If no such permutation exists, transforms the
  4694. // sequence into the last permutation; that is, the decreasingly-sorted one.
  4695. //
  4696. // Returns: `true` if a next permutation was found and otherwise `false`.
  4697. //
  4698. // Complexity: At most `(last - first) / 2` swaps.
  4699. //
  4700. // Reference:
  4701. // https://wg21.link/alg.permutation.generators#:~:text=prev_permutation(I
  4702. template <typename BidirectionalIterator,
  4703. typename Comp = ranges::less,
  4704. typename Proj = identity,
  4705. typename = internal::iterator_category_t<BidirectionalIterator>,
  4706. typename = indirect_result_t<Comp&,
  4707. projected<BidirectionalIterator, Proj>,
  4708. projected<BidirectionalIterator, Proj>>>
  4709. constexpr auto prev_permutation(BidirectionalIterator first,
  4710. BidirectionalIterator last,
  4711. Comp comp = {},
  4712. Proj proj = {}) {
  4713. return std::prev_permutation(
  4714. first, last, internal::ProjectedBinaryPredicate(comp, proj, proj));
  4715. }
  4716. // Effects: Takes a sequence defined by `range` and transforms it into the
  4717. // previous permutation. The previous permutation is found by assuming that the
  4718. // set of all permutations is lexicographically sorted with respect to `comp`
  4719. // and `proj`. If no such permutation exists, transforms the sequence into the
  4720. // last permutation; that is, the decreasingly-sorted one.
  4721. //
  4722. // Returns: `true` if a previous permutation was found and otherwise `false`.
  4723. //
  4724. // Complexity: At most `size(range) / 2` swaps.
  4725. //
  4726. // Reference:
  4727. // https://wg21.link/alg.permutation.generators#:~:text=prev_permutation(R
  4728. template <typename Range,
  4729. typename Comp = ranges::less,
  4730. typename Proj = identity,
  4731. typename = internal::range_category_t<Range>,
  4732. typename = indirect_result_t<Comp&,
  4733. projected<iterator_t<Range>, Proj>,
  4734. projected<iterator_t<Range>, Proj>>>
  4735. constexpr auto prev_permutation(Range&& range, Comp comp = {}, Proj proj = {}) {
  4736. return ranges::prev_permutation(ranges::begin(range), ranges::end(range),
  4737. std::move(comp), std::move(proj));
  4738. }
  4739. } // namespace ranges
  4740. } // namespace base
  4741. #endif // BASE_RANGES_ALGORITHM_H_