Cider Isn't Darwin Emulation, Really
Something went wrong. Try again.
99 kB · 2692 lines
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693// -*- C++ -*-//===----------------------------------------------------------------------===////// The LLVM Compiler Infrastructure//// This file is dual licensed under the MIT and the University of Illinois Open// Source Licenses. See LICENSE.TXT for details.////===----------------------------------------------------------------------===//#ifndef _LIBCPP___TREE#define _LIBCPP___TREE#include <__config>#include <iterator>#include <memory>#include <stdexcept>#include <algorithm>#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)#pragma GCC system_header#endif_LIBCPP_PUSH_MACROS#include <__undef_macros>_LIBCPP_BEGIN_NAMESPACE_STDtemplate <class _Tp, class _Compare, class _Allocator> class __tree;template <class _Tp, class _NodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_iterator;template <class _Tp, class _ConstNodePtr, class _DiffType> class _LIBCPP_TEMPLATE_VIS __tree_const_iterator;template <class _Pointer> class __tree_end_node;template <class _VoidPtr> class __tree_node_base;template <class _Tp, class _VoidPtr> class __tree_node;#ifndef _LIBCPP_CXX03_LANGtemplate <class _Key, class _Value>union __value_type;#elsetemplate <class _Key, class _Value>struct __value_type;#endiftemplate <class _Key, class _CP, class _Compare, bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value>class __map_value_compare;template <class _Allocator> class __map_node_destructor;template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_iterator;template <class _TreeIterator> class _LIBCPP_TEMPLATE_VIS __map_const_iterator;/*_NodePtr algorithmsThe algorithms taking _NodePtr are red black tree algorithms. Thosealgorithms taking a parameter named __root should assume that __rootpoints to a proper red black tree (unless otherwise specified).Each algorithm herein assumes that __root->__parent_ points to a non-nullstructure which has a member __left_ which points back to __root. No othermember is read or written to at __root->__parent_.__root->__parent_ will be referred to below (in comments only) as end_node.end_node->__left_ is an externably accessible lvalue for __root, and can bechanged by node insertion and removal (without explicit reference to end_node).All nodes (with the exception of end_node), even the node referred to as__root, have a non-null __parent_ field.*/// Returns: true if __x is a left child of its parent, else false// Precondition: __x != nullptr.template <class _NodePtr>inline _LIBCPP_INLINE_VISIBILITYbool__tree_is_left_child(_NodePtr __x) _NOEXCEPT{ return __x == __x->__parent_->__left_;}// Determintes if the subtree rooted at __x is a proper red black subtree. If// __x is a proper subtree, returns the black height (null counts as 1). If// __x is an improper subtree, returns 0.template <class _NodePtr>unsigned__tree_sub_invariant(_NodePtr __x){ if (__x == nullptr) return 1; // parent consistency checked by caller // check __x->__left_ consistency if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) return 0; // check __x->__right_ consistency if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) return 0; // check __x->__left_ != __x->__right_ unless both are nullptr if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) return 0; // If this is red, neither child can be red if (!__x->__is_black_) { if (__x->__left_ && !__x->__left_->__is_black_) return 0; if (__x->__right_ && !__x->__right_->__is_black_) return 0; } unsigned __h = __tree_sub_invariant(__x->__left_); if (__h == 0) return 0; // invalid left subtree if (__h != __tree_sub_invariant(__x->__right_)) return 0; // invalid or different height right subtree return __h + __x->__is_black_; // return black height of this node}// Determintes if the red black tree rooted at __root is a proper red black tree.// __root == nullptr is a proper tree. Returns true is __root is a proper// red black tree, else returns false.template <class _NodePtr>bool__tree_invariant(_NodePtr __root){ if (__root == nullptr) return true; // check __x->__parent_ consistency if (__root->__parent_ == nullptr) return false; if (!__tree_is_left_child(__root)) return false; // root must be black if (!__root->__is_black_) return false; // do normal node checks return __tree_sub_invariant(__root) != 0;}// Returns: pointer to the left-most node under __x.// Precondition: __x != nullptr.template <class _NodePtr>inline _LIBCPP_INLINE_VISIBILITY_NodePtr__tree_min(_NodePtr __x) _NOEXCEPT{ while (__x->__left_ != nullptr) __x = __x->__left_; return __x;}// Returns: pointer to the right-most node under __x.// Precondition: __x != nullptr.template <class _NodePtr>inline _LIBCPP_INLINE_VISIBILITY_NodePtr__tree_max(_NodePtr __x) _NOEXCEPT{ while (__x->__right_ != nullptr) __x = __x->__right_; return __x;}// Returns: pointer to the next in-order node after __x.// Precondition: __x != nullptr.template <class _NodePtr>_NodePtr__tree_next(_NodePtr __x) _NOEXCEPT{ if (__x->__right_ != nullptr) return __tree_min(__x->__right_); while (!__tree_is_left_child(__x)) __x = __x->__parent_unsafe(); return __x->__parent_unsafe();}template <class _EndNodePtr, class _NodePtr>inline _LIBCPP_INLINE_VISIBILITY_EndNodePtr__tree_next_iter(_NodePtr __x) _NOEXCEPT{ if (__x->__right_ != nullptr) return static_cast<_EndNodePtr>(__tree_min(__x->__right_)); while (!__tree_is_left_child(__x)) __x = __x->__parent_unsafe(); return static_cast<_EndNodePtr>(__x->__parent_);}// Returns: pointer to the previous in-order node before __x.// Precondition: __x != nullptr.// Note: __x may be the end node.template <class _NodePtr, class _EndNodePtr>inline _LIBCPP_INLINE_VISIBILITY_NodePtr__tree_prev_iter(_EndNodePtr __x) _NOEXCEPT{ if (__x->__left_ != nullptr) return __tree_max(__x->__left_); _NodePtr __xx = static_cast<_NodePtr>(__x); while (__tree_is_left_child(__xx)) __xx = __xx->__parent_unsafe(); return __xx->__parent_unsafe();}// Returns: pointer to a node which has no children// Precondition: __x != nullptr.template <class _NodePtr>_NodePtr__tree_leaf(_NodePtr __x) _NOEXCEPT{ while (true) { if (__x->__left_ != nullptr) { __x = __x->__left_; continue; } if (__x->__right_ != nullptr) { __x = __x->__right_; continue; } break; } return __x;}// Effects: Makes __x->__right_ the subtree root with __x as its left child// while preserving in-order order.// Precondition: __x->__right_ != nullptrtemplate <class _NodePtr>void__tree_left_rotate(_NodePtr __x) _NOEXCEPT{ _NodePtr __y = __x->__right_; __x->__right_ = __y->__left_; if (__x->__right_ != nullptr) __x->__right_->__set_parent(__x); __y->__parent_ = __x->__parent_; if (__tree_is_left_child(__x)) __x->__parent_->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; __y->__left_ = __x; __x->__set_parent(__y);}// Effects: Makes __x->__left_ the subtree root with __x as its right child// while preserving in-order order.// Precondition: __x->__left_ != nullptrtemplate <class _NodePtr>void__tree_right_rotate(_NodePtr __x) _NOEXCEPT{ _NodePtr __y = __x->__left_; __x->__left_ = __y->__right_; if (__x->__left_ != nullptr) __x->__left_->__set_parent(__x); __y->__parent_ = __x->__parent_; if (__tree_is_left_child(__x)) __x->__parent_->__left_ = __y; else __x->__parent_unsafe()->__right_ = __y; __y->__right_ = __x; __x->__set_parent(__y);}// Effects: Rebalances __root after attaching __x to a leaf.// Precondition: __root != nulptr && __x != nullptr.// __x has no children.// __x == __root or == a direct or indirect child of __root.// If __x were to be unlinked from __root (setting __root to// nullptr if __root == __x), __tree_invariant(__root) == true.// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_// may be different than the value passed in as __root.template <class _NodePtr>void__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT{ __x->__is_black_ = __x == __root; while (__x != __root && !__x->__parent_unsafe()->__is_black_) { // __x->__parent_ != __root because __x->__parent_->__is_black == false if (__tree_is_left_child(__x->__parent_unsafe())) { _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_; if (__y != nullptr && !__y->__is_black_) { __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = __x == __root; __y->__is_black_ = true; } else { if (!__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); __tree_left_rotate(__x); } __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = false; __tree_right_rotate(__x); break; } } else { _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_; if (__y != nullptr && !__y->__is_black_) { __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = __x == __root; __y->__is_black_ = true; } else { if (__tree_is_left_child(__x)) { __x = __x->__parent_unsafe(); __tree_right_rotate(__x); } __x = __x->__parent_unsafe(); __x->__is_black_ = true; __x = __x->__parent_unsafe(); __x->__is_black_ = false; __tree_left_rotate(__x); break; } } }}// Precondition: __root != nullptr && __z != nullptr.// __tree_invariant(__root) == true.// __z == __root or == a direct or indirect child of __root.// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed.// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_// nor any of its children refer to __z. end_node->__left_// may be different than the value passed in as __root.template <class _NodePtr>void__tree_remove(_NodePtr __root, _NodePtr __z) _NOEXCEPT{ // __z will be removed from the tree. Client still needs to destruct/deallocate it // __y is either __z, or if __z has two children, __tree_next(__z). // __y will have at most one child. // __y will be the initial hole in the tree (make the hole at a leaf) _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? __z : __tree_next(__z); // __x is __y's possibly null single child _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; // __w is __x's possibly null uncle (will become __x's sibling) _NodePtr __w = nullptr; // link __x to __y's parent, and find __w if (__x != nullptr) __x->__parent_ = __y->__parent_; if (__tree_is_left_child(__y)) { __y->__parent_->__left_ = __x; if (__y != __root) __w = __y->__parent_unsafe()->__right_; else __root = __x; // __w == nullptr } else { __y->__parent_unsafe()->__right_ = __x; // __y can't be root if it is a right child __w = __y->__parent_->__left_; } bool __removed_black = __y->__is_black_; // If we didn't remove __z, do so now by splicing in __y for __z, // but copy __z's color. This does not impact __x or __w. if (__y != __z) { // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr __y->__parent_ = __z->__parent_; if (__tree_is_left_child(__z)) __y->__parent_->__left_ = __y; else __y->__parent_unsafe()->__right_ = __y; __y->__left_ = __z->__left_; __y->__left_->__set_parent(__y); __y->__right_ = __z->__right_; if (__y->__right_ != nullptr) __y->__right_->__set_parent(__y); __y->__is_black_ = __z->__is_black_; if (__root == __z) __root = __y; } // There is no need to rebalance if we removed a red, or if we removed // the last node. if (__removed_black && __root != nullptr) { // Rebalance: // __x has an implicit black color (transferred from the removed __y) // associated with it, no matter what its color is. // If __x is __root (in which case it can't be null), it is supposed // to be black anyway, and if it is doubly black, then the double // can just be ignored. // If __x is red (in which case it can't be null), then it can absorb // the implicit black just by setting its color to black. // Since __y was black and only had one child (which __x points to), __x // is either red with no children, else null, otherwise __y would have // different black heights under left and right pointers. // if (__x == __root || __x != nullptr && !__x->__is_black_) if (__x != nullptr) __x->__is_black_ = true; else { // Else __x isn't root, and is "doubly black", even though it may // be null. __w can not be null here, else the parent would // see a black height >= 2 on the __x side and a black height // of 1 on the __w side (__w must be a non-null black or a red // with a non-null black child). while (true) { if (!__tree_is_left_child(__w)) // if x is left child { if (!__w->__is_black_) { __w->__is_black_ = true; __w->__parent_unsafe()->__is_black_ = false; __tree_left_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary if (__root == __w->__left_) __root = __w; // reset sibling, and it still can't be null __w = __w->__left_->__right_; } // __w->__is_black_ is now true, __w may have null children if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && (__w->__right_ == nullptr || __w->__right_->__is_black_)) { __w->__is_black_ = false; __x = __w->__parent_unsafe(); // __x can no longer be null if (__x == __root || !__x->__is_black_) { __x->__is_black_ = true; break; } // reset sibling, and it still can't be null __w = __tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; // continue; } else // __w has a red child { if (__w->__right_ == nullptr || __w->__right_->__is_black_) { // __w left child is non-null and red __w->__left_->__is_black_ = true; __w->__is_black_ = false; __tree_right_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); } // __w has a right red child, left child may be null __w->__is_black_ = __w->__parent_unsafe()->__is_black_; __w->__parent_unsafe()->__is_black_ = true; __w->__right_->__is_black_ = true; __tree_left_rotate(__w->__parent_unsafe()); break; } } else { if (!__w->__is_black_) { __w->__is_black_ = true; __w->__parent_unsafe()->__is_black_ = false; __tree_right_rotate(__w->__parent_unsafe()); // __x is still valid // reset __root only if necessary if (__root == __w->__right_) __root = __w; // reset sibling, and it still can't be null __w = __w->__right_->__left_; } // __w->__is_black_ is now true, __w may have null children if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && (__w->__right_ == nullptr || __w->__right_->__is_black_)) { __w->__is_black_ = false; __x = __w->__parent_unsafe(); // __x can no longer be null if (!__x->__is_black_ || __x == __root) { __x->__is_black_ = true; break; } // reset sibling, and it still can't be null __w = __tree_is_left_child(__x) ? __x->__parent_unsafe()->__right_ : __x->__parent_->__left_; // continue; } else // __w has a red child { if (__w->__left_ == nullptr || __w->__left_->__is_black_) { // __w right child is non-null and red __w->__right_->__is_black_ = true; __w->__is_black_ = false; __tree_left_rotate(__w); // __w is known not to be root, so root hasn't changed // reset sibling, and it still can't be null __w = __w->__parent_unsafe(); } // __w has a left red child, right child may be null __w->__is_black_ = __w->__parent_unsafe()->__is_black_; __w->__parent_unsafe()->__is_black_ = true; __w->__left_->__is_black_ = true; __tree_right_rotate(__w->__parent_unsafe()); break; } } } } }}// node traits#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp>struct __is_tree_value_type_imp : false_type {};template <class _Key, class _Value>struct __is_tree_value_type_imp<__value_type<_Key, _Value>> : true_type {};template <class ..._Args>struct __is_tree_value_type : false_type {};template <class _One>struct __is_tree_value_type<_One> : __is_tree_value_type_imp<typename __uncvref<_One>::type> {};#endiftemplate <class _Tp>struct __tree_key_value_types { typedef _Tp key_type; typedef _Tp __node_value_type; typedef _Tp __container_value_type; static const bool __is_map = false; _LIBCPP_INLINE_VISIBILITY static key_type const& __get_key(_Tp const& __v) { return __v; } _LIBCPP_INLINE_VISIBILITY static __container_value_type const& __get_value(__node_value_type const& __v) { return __v; } _LIBCPP_INLINE_VISIBILITY static __container_value_type* __get_ptr(__node_value_type& __n) { return _VSTD::addressof(__n); }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY static __container_value_type&& __move(__node_value_type& __v) { return _VSTD::move(__v); }#endif};template <class _Key, class _Tp>struct __tree_key_value_types<__value_type<_Key, _Tp> > { typedef _Key key_type; typedef _Tp mapped_type; typedef __value_type<_Key, _Tp> __node_value_type; typedef pair<const _Key, _Tp> __container_value_type; typedef pair<_Key, _Tp> __nc_value_type; typedef __container_value_type __map_value_type; static const bool __is_map = true; _LIBCPP_INLINE_VISIBILITY static key_type const& __get_key(__node_value_type const& __t) { return __t.__cc.first; } template <class _Up> _LIBCPP_INLINE_VISIBILITY static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, key_type const&>::type __get_key(_Up& __t) { return __t.first; } _LIBCPP_INLINE_VISIBILITY static __container_value_type const& __get_value(__node_value_type const& __t) { return __t.__cc; } template <class _Up> _LIBCPP_INLINE_VISIBILITY static typename enable_if<__is_same_uncvref<_Up, __container_value_type>::value, __container_value_type const&>::type __get_value(_Up& __t) { return __t; } _LIBCPP_INLINE_VISIBILITY static __container_value_type* __get_ptr(__node_value_type& __n) { return _VSTD::addressof(__n.__cc); }#ifndef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY static __nc_value_type&& __move(__node_value_type& __v) { return _VSTD::move(__v.__nc); }#endif};template <class _VoidPtr>struct __tree_node_base_types { typedef _VoidPtr __void_pointer; typedef __tree_node_base<__void_pointer> __node_base_type; typedef typename __rebind_pointer<_VoidPtr, __node_base_type>::type __node_base_pointer; typedef __tree_end_node<__node_base_pointer> __end_node_type; typedef typename __rebind_pointer<_VoidPtr, __end_node_type>::type __end_node_pointer;#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) typedef __end_node_pointer __parent_pointer;#else typedef typename conditional< is_pointer<__end_node_pointer>::value, __end_node_pointer, __node_base_pointer>::type __parent_pointer;#endifprivate: static_assert((is_same<typename pointer_traits<_VoidPtr>::element_type, void>::value), "_VoidPtr does not point to unqualified void type");};template <class _Tp, class _AllocPtr, class _KVTypes = __tree_key_value_types<_Tp>, bool = _KVTypes::__is_map>struct __tree_map_pointer_types {};template <class _Tp, class _AllocPtr, class _KVTypes>struct __tree_map_pointer_types<_Tp, _AllocPtr, _KVTypes, true> { typedef typename _KVTypes::__map_value_type _Mv; typedef typename __rebind_pointer<_AllocPtr, _Mv>::type __map_value_type_pointer; typedef typename __rebind_pointer<_AllocPtr, const _Mv>::type __const_map_value_type_pointer;};template <class _NodePtr, class _NodeT = typename pointer_traits<_NodePtr>::element_type>struct __tree_node_types;template <class _NodePtr, class _Tp, class _VoidPtr>struct __tree_node_types<_NodePtr, __tree_node<_Tp, _VoidPtr> > : public __tree_node_base_types<_VoidPtr>, __tree_key_value_types<_Tp>, __tree_map_pointer_types<_Tp, _VoidPtr>{ typedef __tree_node_base_types<_VoidPtr> __base; typedef __tree_key_value_types<_Tp> __key_base; typedef __tree_map_pointer_types<_Tp, _VoidPtr> __map_pointer_base;public: typedef typename pointer_traits<_NodePtr>::element_type __node_type; typedef _NodePtr __node_pointer; typedef _Tp __node_value_type; typedef typename __rebind_pointer<_VoidPtr, __node_value_type>::type __node_value_type_pointer; typedef typename __rebind_pointer<_VoidPtr, const __node_value_type>::type __const_node_value_type_pointer;#if defined(_LIBCPP_ABI_TREE_REMOVE_NODE_POINTER_UB) typedef typename __base::__end_node_pointer __iter_pointer;#else typedef typename conditional< is_pointer<__node_pointer>::value, typename __base::__end_node_pointer, __node_pointer>::type __iter_pointer;#endifprivate: static_assert(!is_const<__node_type>::value, "_NodePtr should never be a pointer to const"); static_assert((is_same<typename __rebind_pointer<_VoidPtr, __node_type>::type, _NodePtr>::value), "_VoidPtr does not rebind to _NodePtr.");};template <class _ValueTp, class _VoidPtr>struct __make_tree_node_types { typedef typename __rebind_pointer<_VoidPtr, __tree_node<_ValueTp, _VoidPtr> >::type _NodePtr; typedef __tree_node_types<_NodePtr> type;};// nodetemplate <class _Pointer>class __tree_end_node{public: typedef _Pointer pointer; pointer __left_; _LIBCPP_INLINE_VISIBILITY __tree_end_node() _NOEXCEPT : __left_() {}};template <class _VoidPtr>class __tree_node_base : public __tree_node_base_types<_VoidPtr>::__end_node_type{ typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;public: typedef typename _NodeBaseTypes::__node_base_pointer pointer; typedef typename _NodeBaseTypes::__parent_pointer __parent_pointer; pointer __right_; __parent_pointer __parent_; bool __is_black_; _LIBCPP_INLINE_VISIBILITY pointer __parent_unsafe() const { return static_cast<pointer>(__parent_);} _LIBCPP_INLINE_VISIBILITY void __set_parent(pointer __p) { __parent_ = static_cast<__parent_pointer>(__p); }private: ~__tree_node_base() _LIBCPP_EQUAL_DELETE; __tree_node_base(__tree_node_base const&) _LIBCPP_EQUAL_DELETE; __tree_node_base& operator=(__tree_node_base const&) _LIBCPP_EQUAL_DELETE;};template <class _Tp, class _VoidPtr>class __tree_node : public __tree_node_base<_VoidPtr>{public: typedef _Tp __node_value_type; __node_value_type __value_;private: ~__tree_node() _LIBCPP_EQUAL_DELETE; __tree_node(__tree_node const&) _LIBCPP_EQUAL_DELETE; __tree_node& operator=(__tree_node const&) _LIBCPP_EQUAL_DELETE;};template <class _Allocator>class __tree_node_destructor{ typedef _Allocator allocator_type; typedef allocator_traits<allocator_type> __alloc_traits;public: typedef typename __alloc_traits::pointer pointer;private: typedef __tree_node_types<pointer> _NodeTypes; allocator_type& __na_; __tree_node_destructor& operator=(const __tree_node_destructor&);public: bool __value_constructed; _LIBCPP_INLINE_VISIBILITY explicit __tree_node_destructor(allocator_type& __na, bool __val = false) _NOEXCEPT : __na_(__na), __value_constructed(__val) {} _LIBCPP_INLINE_VISIBILITY void operator()(pointer __p) _NOEXCEPT { if (__value_constructed) __alloc_traits::destroy(__na_, _NodeTypes::__get_ptr(__p->__value_)); if (__p) __alloc_traits::deallocate(__na_, __p, 1); } template <class> friend class __map_node_destructor;};template <class _Tp, class _NodePtr, class _DiffType>class _LIBCPP_TEMPLATE_VIS __tree_iterator{ typedef __tree_node_types<_NodePtr> _NodeTypes; typedef _NodePtr __node_pointer; typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; typedef typename _NodeTypes::__iter_pointer __iter_pointer; typedef pointer_traits<__node_pointer> __pointer_traits; __iter_pointer __ptr_;public: typedef bidirectional_iterator_tag iterator_category; typedef _Tp value_type; typedef _DiffType difference_type; typedef value_type& reference; typedef typename _NodeTypes::__node_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __tree_iterator() _NOEXCEPT#if _LIBCPP_STD_VER > 11 : __ptr_(nullptr)#endif {} _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __get_np()->__value_;} _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} _LIBCPP_INLINE_VISIBILITY __tree_iterator& operator++() { __ptr_ = static_cast<__iter_pointer>( __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); return *this; } _LIBCPP_INLINE_VISIBILITY __tree_iterator operator++(int) {__tree_iterator __t(*this); ++(*this); return __t;} _LIBCPP_INLINE_VISIBILITY __tree_iterator& operator--() { __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>( static_cast<__end_node_pointer>(__ptr_))); return *this; } _LIBCPP_INLINE_VISIBILITY __tree_iterator operator--(int) {__tree_iterator __t(*this); --(*this); return __t;} friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) {return __x.__ptr_ == __y.__ptr_;} friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) {return !(__x == __y);}private: _LIBCPP_INLINE_VISIBILITY explicit __tree_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} _LIBCPP_INLINE_VISIBILITY explicit __tree_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} _LIBCPP_INLINE_VISIBILITY __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } template <class, class, class> friend class __tree; template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS __tree_const_iterator; template <class> friend class _LIBCPP_TEMPLATE_VIS __map_iterator; template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset;};template <class _Tp, class _NodePtr, class _DiffType>class _LIBCPP_TEMPLATE_VIS __tree_const_iterator{ typedef __tree_node_types<_NodePtr> _NodeTypes; typedef typename _NodeTypes::__node_pointer __node_pointer; typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; typedef typename _NodeTypes::__end_node_pointer __end_node_pointer; typedef typename _NodeTypes::__iter_pointer __iter_pointer; typedef pointer_traits<__node_pointer> __pointer_traits; __iter_pointer __ptr_;public: typedef bidirectional_iterator_tag iterator_category; typedef _Tp value_type; typedef _DiffType difference_type; typedef const value_type& reference; typedef typename _NodeTypes::__const_node_value_type_pointer pointer; _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() _NOEXCEPT#if _LIBCPP_STD_VER > 11 : __ptr_(nullptr)#endif {}private: typedef __tree_iterator<value_type, __node_pointer, difference_type> __non_const_iterator;public: _LIBCPP_INLINE_VISIBILITY __tree_const_iterator(__non_const_iterator __p) _NOEXCEPT : __ptr_(__p.__ptr_) {} _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __get_np()->__value_;} _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return pointer_traits<pointer>::pointer_to(__get_np()->__value_);} _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator++() { __ptr_ = static_cast<__iter_pointer>( __tree_next_iter<__end_node_pointer>(static_cast<__node_base_pointer>(__ptr_))); return *this; } _LIBCPP_INLINE_VISIBILITY __tree_const_iterator operator++(int) {__tree_const_iterator __t(*this); ++(*this); return __t;} _LIBCPP_INLINE_VISIBILITY __tree_const_iterator& operator--() { __ptr_ = static_cast<__iter_pointer>(__tree_prev_iter<__node_base_pointer>( static_cast<__end_node_pointer>(__ptr_))); return *this; } _LIBCPP_INLINE_VISIBILITY __tree_const_iterator operator--(int) {__tree_const_iterator __t(*this); --(*this); return __t;} friend _LIBCPP_INLINE_VISIBILITY bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {return __x.__ptr_ == __y.__ptr_;} friend _LIBCPP_INLINE_VISIBILITY bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) {return !(__x == __y);}private: _LIBCPP_INLINE_VISIBILITY explicit __tree_const_iterator(__node_pointer __p) _NOEXCEPT : __ptr_(__p) {} _LIBCPP_INLINE_VISIBILITY explicit __tree_const_iterator(__end_node_pointer __p) _NOEXCEPT : __ptr_(__p) {} _LIBCPP_INLINE_VISIBILITY __node_pointer __get_np() const { return static_cast<__node_pointer>(__ptr_); } template <class, class, class> friend class __tree; template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap; template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS set; template <class, class, class> friend class _LIBCPP_TEMPLATE_VIS multiset; template <class> friend class _LIBCPP_TEMPLATE_VIS __map_const_iterator;};#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>struct __diagnose_tree_helper { static constexpr bool __trigger_diagnostics() _LIBCPP_DIAGNOSE_WARNING(!__invokable<_Compare const&, _Tp const&, _Tp const&>::value, "the specified comparator type does not provide a const call operator") { return true; }};template <class _Key, class _Value, class _KeyComp, class _Alloc>struct __diagnose_tree_helper< __value_type<_Key, _Value>, __map_value_compare<_Key, __value_type<_Key, _Value>, _KeyComp>, _Alloc> : __diagnose_tree_helper<_Key, _KeyComp, _Alloc>{};#endif // !_LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>class __tree{public: typedef _Tp value_type; typedef _Compare value_compare; typedef _Allocator allocator_type;private: typedef allocator_traits<allocator_type> __alloc_traits; typedef typename __make_tree_node_types<value_type, typename __alloc_traits::void_pointer>::type _NodeTypes; typedef typename _NodeTypes::key_type key_type;public: typedef typename _NodeTypes::__node_value_type __node_value_type; typedef typename _NodeTypes::__container_value_type __container_value_type; typedef typename __alloc_traits::pointer pointer; typedef typename __alloc_traits::const_pointer const_pointer; typedef typename __alloc_traits::size_type size_type; typedef typename __alloc_traits::difference_type difference_type;public: typedef typename _NodeTypes::__void_pointer __void_pointer; typedef typename _NodeTypes::__node_type __node; typedef typename _NodeTypes::__node_pointer __node_pointer; typedef typename _NodeTypes::__node_base_type __node_base; typedef typename _NodeTypes::__node_base_pointer __node_base_pointer; typedef typename _NodeTypes::__end_node_type __end_node_t; typedef typename _NodeTypes::__end_node_pointer __end_node_ptr; typedef typename _NodeTypes::__parent_pointer __parent_pointer; typedef typename _NodeTypes::__iter_pointer __iter_pointer; typedef typename __rebind_alloc_helper<__alloc_traits, __node>::type __node_allocator; typedef allocator_traits<__node_allocator> __node_traits;private: // check for sane allocator pointer rebinding semantics. Rebinding the // allocator for a new pointer type should be exactly the same as rebinding // the pointer using 'pointer_traits'. static_assert((is_same<__node_pointer, typename __node_traits::pointer>::value), "Allocator does not rebind pointers in a sane manner."); typedef typename __rebind_alloc_helper<__node_traits, __node_base>::type __node_base_allocator; typedef allocator_traits<__node_base_allocator> __node_base_traits; static_assert((is_same<__node_base_pointer, typename __node_base_traits::pointer>::value), "Allocator does not rebind pointers in a sane manner.");private: __iter_pointer __begin_node_; __compressed_pair<__end_node_t, __node_allocator> __pair1_; __compressed_pair<size_type, value_compare> __pair3_;public: _LIBCPP_INLINE_VISIBILITY __iter_pointer __end_node() _NOEXCEPT { return static_cast<__iter_pointer>( pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) ); } _LIBCPP_INLINE_VISIBILITY __iter_pointer __end_node() const _NOEXCEPT { return static_cast<__iter_pointer>( pointer_traits<__end_node_ptr>::pointer_to( const_cast<__end_node_t&>(__pair1_.first()) ) ); } _LIBCPP_INLINE_VISIBILITY __node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}private: _LIBCPP_INLINE_VISIBILITY const __node_allocator& __node_alloc() const _NOEXCEPT {return __pair1_.second();} _LIBCPP_INLINE_VISIBILITY __iter_pointer& __begin_node() _NOEXCEPT {return __begin_node_;} _LIBCPP_INLINE_VISIBILITY const __iter_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}public: _LIBCPP_INLINE_VISIBILITY allocator_type __alloc() const _NOEXCEPT {return allocator_type(__node_alloc());}private: _LIBCPP_INLINE_VISIBILITY size_type& size() _NOEXCEPT {return __pair3_.first();}public: _LIBCPP_INLINE_VISIBILITY const size_type& size() const _NOEXCEPT {return __pair3_.first();} _LIBCPP_INLINE_VISIBILITY value_compare& value_comp() _NOEXCEPT {return __pair3_.second();} _LIBCPP_INLINE_VISIBILITY const value_compare& value_comp() const _NOEXCEPT {return __pair3_.second();}public: _LIBCPP_INLINE_VISIBILITY __node_pointer __root() const _NOEXCEPT {return static_cast<__node_pointer>(__end_node()->__left_);} __node_base_pointer* __root_ptr() const _NOEXCEPT { return _VSTD::addressof(__end_node()->__left_); } typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; typedef __tree_const_iterator<value_type, __node_pointer, difference_type> const_iterator; explicit __tree(const value_compare& __comp) _NOEXCEPT_( is_nothrow_default_constructible<__node_allocator>::value && is_nothrow_copy_constructible<value_compare>::value); explicit __tree(const allocator_type& __a); __tree(const value_compare& __comp, const allocator_type& __a); __tree(const __tree& __t); __tree& operator=(const __tree& __t); template <class _InputIterator> void __assign_unique(_InputIterator __first, _InputIterator __last); template <class _InputIterator> void __assign_multi(_InputIterator __first, _InputIterator __last);#ifndef _LIBCPP_CXX03_LANG __tree(__tree&& __t) _NOEXCEPT_( is_nothrow_move_constructible<__node_allocator>::value && is_nothrow_move_constructible<value_compare>::value); __tree(__tree&& __t, const allocator_type& __a); __tree& operator=(__tree&& __t) _NOEXCEPT_( __node_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value);#endif // _LIBCPP_CXX03_LANG ~__tree(); _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT {return iterator(__begin_node());} _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());} _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT {return iterator(__end_node());} _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());} _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT {return std::min<size_type>( __node_traits::max_size(__node_alloc()), numeric_limits<difference_type >::max());} void clear() _NOEXCEPT; void swap(__tree& __t)#if _LIBCPP_STD_VER <= 11 _NOEXCEPT_( __is_nothrow_swappable<value_compare>::value && (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable<__node_allocator>::value) );#else _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value);#endif#ifndef _LIBCPP_CXX03_LANG template <class _Key, class ..._Args> pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args&&... __args); template <class _Key, class ..._Args> iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&&...); template <class... _Args> pair<iterator, bool> __emplace_unique_impl(_Args&&... __args); template <class... _Args> iterator __emplace_hint_unique_impl(const_iterator __p, _Args&&... __args); template <class... _Args> iterator __emplace_multi(_Args&&... __args); template <class... _Args> iterator __emplace_hint_multi(const_iterator __p, _Args&&... __args); template <class _Pp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique(_Pp&& __x) { return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); } template <class _First, class _Second> _LIBCPP_INLINE_VISIBILITY typename enable_if< __can_extract_map_key<_First, key_type, __container_value_type>::value, pair<iterator, bool> >::type __emplace_unique(_First&& __f, _Second&& __s) { return __emplace_unique_key_args(__f, _VSTD::forward<_First>(__f), _VSTD::forward<_Second>(__s)); } template <class... _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique(_Args&&... __args) { return __emplace_unique_impl(_VSTD::forward<_Args>(__args)...); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) { return __emplace_unique_impl(_VSTD::forward<_Pp>(__x)); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) { return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x)); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) { return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x)); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) { return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x), __can_extract_key<_Pp, key_type>()); } template <class _First, class _Second> _LIBCPP_INLINE_VISIBILITY typename enable_if< __can_extract_map_key<_First, key_type, __container_value_type>::value, iterator >::type __emplace_hint_unique(const_iterator __p, _First&& __f, _Second&& __s) { return __emplace_hint_unique_key_args(__p, __f, _VSTD::forward<_First>(__f), _VSTD::forward<_Second>(__s)); } template <class... _Args> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique(const_iterator __p, _Args&&... __args) { return __emplace_hint_unique_impl(__p, _VSTD::forward<_Args>(__args)...); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) { return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x)); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) { return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)); } template <class _Pp> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) { return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)); }#else template <class _Key, class _Args> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __emplace_unique_key_args(_Key const&, _Args& __args); template <class _Key, class _Args> _LIBCPP_INLINE_VISIBILITY iterator __emplace_hint_unique_key_args(const_iterator, _Key const&, _Args&);#endif _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __insert_unique(const __container_value_type& __v) { return __emplace_unique_key_args(_NodeTypes::__get_key(__v), __v); } _LIBCPP_INLINE_VISIBILITY iterator __insert_unique(const_iterator __p, const __container_value_type& __v) { return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), __v); }#ifdef _LIBCPP_CXX03_LANG _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(const __container_value_type& __v); _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(const_iterator __p, const __container_value_type& __v);#else _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __insert_unique(__container_value_type&& __v) { return __emplace_unique_key_args(_NodeTypes::__get_key(__v), _VSTD::move(__v)); } _LIBCPP_INLINE_VISIBILITY iterator __insert_unique(const_iterator __p, __container_value_type&& __v) { return __emplace_hint_unique_key_args(__p, _NodeTypes::__get_key(__v), _VSTD::move(__v)); } template <class _Vp, class = typename enable_if< !is_same<typename __unconstref<_Vp>::type, __container_value_type >::value >::type> _LIBCPP_INLINE_VISIBILITY pair<iterator, bool> __insert_unique(_Vp&& __v) { return __emplace_unique(_VSTD::forward<_Vp>(__v)); } template <class _Vp, class = typename enable_if< !is_same<typename __unconstref<_Vp>::type, __container_value_type >::value >::type> _LIBCPP_INLINE_VISIBILITY iterator __insert_unique(const_iterator __p, _Vp&& __v) { return __emplace_hint_unique(__p, _VSTD::forward<_Vp>(__v)); } _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(__container_value_type&& __v) { return __emplace_multi(_VSTD::move(__v)); } _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(const_iterator __p, __container_value_type&& __v) { return __emplace_hint_multi(__p, _VSTD::move(__v)); } template <class _Vp> _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(_Vp&& __v) { return __emplace_multi(_VSTD::forward<_Vp>(__v)); } template <class _Vp> _LIBCPP_INLINE_VISIBILITY iterator __insert_multi(const_iterator __p, _Vp&& __v) { return __emplace_hint_multi(__p, _VSTD::forward<_Vp>(__v)); }#endif // !_LIBCPP_CXX03_LANG pair<iterator, bool> __node_insert_unique(__node_pointer __nd); iterator __node_insert_unique(const_iterator __p, __node_pointer __nd); iterator __node_insert_multi(__node_pointer __nd); iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); iterator erase(const_iterator __p); iterator erase(const_iterator __f, const_iterator __l); template <class _Key> size_type __erase_unique(const _Key& __k); template <class _Key> size_type __erase_multi(const _Key& __k); void __insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node); template <class _Key> iterator find(const _Key& __v); template <class _Key> const_iterator find(const _Key& __v) const; template <class _Key> size_type __count_unique(const _Key& __k) const; template <class _Key> size_type __count_multi(const _Key& __k) const; template <class _Key> _LIBCPP_INLINE_VISIBILITY iterator lower_bound(const _Key& __v) {return __lower_bound(__v, __root(), __end_node());} template <class _Key> iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); template <class _Key> _LIBCPP_INLINE_VISIBILITY const_iterator lower_bound(const _Key& __v) const {return __lower_bound(__v, __root(), __end_node());} template <class _Key> const_iterator __lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; template <class _Key> _LIBCPP_INLINE_VISIBILITY iterator upper_bound(const _Key& __v) {return __upper_bound(__v, __root(), __end_node());} template <class _Key> iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result); template <class _Key> _LIBCPP_INLINE_VISIBILITY const_iterator upper_bound(const _Key& __v) const {return __upper_bound(__v, __root(), __end_node());} template <class _Key> const_iterator __upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const; template <class _Key> pair<iterator, iterator> __equal_range_unique(const _Key& __k); template <class _Key> pair<const_iterator, const_iterator> __equal_range_unique(const _Key& __k) const; template <class _Key> pair<iterator, iterator> __equal_range_multi(const _Key& __k); template <class _Key> pair<const_iterator, const_iterator> __equal_range_multi(const _Key& __k) const; typedef __tree_node_destructor<__node_allocator> _Dp; typedef unique_ptr<__node, _Dp> __node_holder; __node_holder remove(const_iterator __p) _NOEXCEPT;private: __node_base_pointer& __find_leaf_low(__parent_pointer& __parent, const key_type& __v); __node_base_pointer& __find_leaf_high(__parent_pointer& __parent, const key_type& __v); __node_base_pointer& __find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v); // FIXME: Make this function const qualified. Unfortunetly doing so // breaks existing code which uses non-const callable comparators. template <class _Key> __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v); template <class _Key> _LIBCPP_INLINE_VISIBILITY __node_base_pointer& __find_equal(__parent_pointer& __parent, const _Key& __v) const { return const_cast<__tree*>(this)->__find_equal(__parent, __v); } template <class _Key> __node_base_pointer& __find_equal(const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v);#ifndef _LIBCPP_CXX03_LANG template <class ..._Args> __node_holder __construct_node(_Args&& ...__args);#else __node_holder __construct_node(const __container_value_type& __v);#endif void destroy(__node_pointer __nd) _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const __tree& __t) {__copy_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_copy_assignment::value>());} _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const __tree& __t, true_type) { if (__node_alloc() != __t.__node_alloc()) clear(); __node_alloc() = __t.__node_alloc(); } _LIBCPP_INLINE_VISIBILITY void __copy_assign_alloc(const __tree&, false_type) {} void __move_assign(__tree& __t, false_type); void __move_assign(__tree& __t, true_type) _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value); _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(__tree& __t) _NOEXCEPT_( !__node_traits::propagate_on_container_move_assignment::value || is_nothrow_move_assignable<__node_allocator>::value) {__move_assign_alloc(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>());} _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(__tree& __t, true_type) _NOEXCEPT_(is_nothrow_move_assignable<__node_allocator>::value) {__node_alloc() = _VSTD::move(__t.__node_alloc());} _LIBCPP_INLINE_VISIBILITY void __move_assign_alloc(__tree&, false_type) _NOEXCEPT {} __node_pointer __detach(); static __node_pointer __detach(__node_pointer); template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS map; template <class, class, class, class> friend class _LIBCPP_TEMPLATE_VIS multimap;};template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp) _NOEXCEPT_( is_nothrow_default_constructible<__node_allocator>::value && is_nothrow_copy_constructible<value_compare>::value) : __pair3_(0, __comp){ __begin_node() = __end_node();}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(const allocator_type& __a) : __begin_node_(__iter_pointer()), __pair1_(__second_tag(), __node_allocator(__a)), __pair3_(0){ __begin_node() = __end_node();}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(const value_compare& __comp, const allocator_type& __a) : __begin_node_(__iter_pointer()), __pair1_(__second_tag(), __node_allocator(__a)), __pair3_(0, __comp){ __begin_node() = __end_node();}// Precondition: size() != 0template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_pointer__tree<_Tp, _Compare, _Allocator>::__detach(){ __node_pointer __cache = static_cast<__node_pointer>(__begin_node()); __begin_node() = __end_node(); __end_node()->__left_->__parent_ = nullptr; __end_node()->__left_ = nullptr; size() = 0; // __cache->__left_ == nullptr if (__cache->__right_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__right_); // __cache->__left_ == nullptr // __cache->__right_ == nullptr return __cache;}// Precondition: __cache != nullptr// __cache->left_ == nullptr// __cache->right_ == nullptr// This is no longer a red-black treetemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_pointer__tree<_Tp, _Compare, _Allocator>::__detach(__node_pointer __cache){ if (__cache->__parent_ == nullptr) return nullptr; if (__tree_is_left_child(static_cast<__node_base_pointer>(__cache))) { __cache->__parent_->__left_ = nullptr; __cache = static_cast<__node_pointer>(__cache->__parent_); if (__cache->__right_ == nullptr) return __cache; return static_cast<__node_pointer>(__tree_leaf(__cache->__right_)); } // __cache is right child __cache->__parent_unsafe()->__right_ = nullptr; __cache = static_cast<__node_pointer>(__cache->__parent_); if (__cache->__left_ == nullptr) return __cache; return static_cast<__node_pointer>(__tree_leaf(__cache->__left_));}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>&__tree<_Tp, _Compare, _Allocator>::operator=(const __tree& __t){ if (this != &__t) { value_comp() = __t.value_comp(); __copy_assign_alloc(__t); __assign_multi(__t.begin(), __t.end()); } return *this;}template <class _Tp, class _Compare, class _Allocator>template <class _InputIterator>void__tree<_Tp, _Compare, _Allocator>::__assign_unique(_InputIterator __first, _InputIterator __last){ typedef iterator_traits<_InputIterator> _ITraits; typedef typename _ITraits::value_type _ItValueType; static_assert((is_same<_ItValueType, __container_value_type>::value), "__assign_unique may only be called with the containers value type"); if (size() != 0) { __node_pointer __cache = __detach();#ifndef _LIBCPP_NO_EXCEPTIONS try {#endif // _LIBCPP_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { __cache->__value_ = *__first; __node_pointer __next = __detach(__cache); __node_insert_unique(__cache); __cache = __next; }#ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); throw; }#endif // _LIBCPP_NO_EXCEPTIONS if (__cache != nullptr) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); } } for (; __first != __last; ++__first) __insert_unique(*__first);}template <class _Tp, class _Compare, class _Allocator>template <class _InputIterator>void__tree<_Tp, _Compare, _Allocator>::__assign_multi(_InputIterator __first, _InputIterator __last){ typedef iterator_traits<_InputIterator> _ITraits; typedef typename _ITraits::value_type _ItValueType; static_assert((is_same<_ItValueType, __container_value_type>::value || is_same<_ItValueType, __node_value_type>::value), "__assign_multi may only be called with the containers value type" " or the nodes value type"); if (size() != 0) { __node_pointer __cache = __detach();#ifndef _LIBCPP_NO_EXCEPTIONS try {#endif // _LIBCPP_NO_EXCEPTIONS for (; __cache != nullptr && __first != __last; ++__first) { __cache->__value_ = *__first; __node_pointer __next = __detach(__cache); __node_insert_multi(__cache); __cache = __next; }#ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); throw; }#endif // _LIBCPP_NO_EXCEPTIONS if (__cache != nullptr) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); } } for (; __first != __last; ++__first) __insert_multi(_NodeTypes::__get_value(*__first));}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(const __tree& __t) : __begin_node_(__iter_pointer()), __pair1_(__second_tag(), __node_traits::select_on_container_copy_construction(__t.__node_alloc())), __pair3_(0, __t.value_comp()){ __begin_node() = __end_node();}#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t) _NOEXCEPT_( is_nothrow_move_constructible<__node_allocator>::value && is_nothrow_move_constructible<value_compare>::value) : __begin_node_(_VSTD::move(__t.__begin_node_)), __pair1_(_VSTD::move(__t.__pair1_)), __pair3_(_VSTD::move(__t.__pair3_)){ if (size() == 0) __begin_node() = __end_node(); else { __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); __t.__begin_node() = __t.__end_node(); __t.__end_node()->__left_ = nullptr; __t.size() = 0; }}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::__tree(__tree&& __t, const allocator_type& __a) : __pair1_(__second_tag(), __node_allocator(__a)), __pair3_(0, _VSTD::move(__t.value_comp())){ if (__a == __t.__alloc()) { if (__t.size() == 0) __begin_node() = __end_node(); else { __begin_node() = __t.__begin_node(); __end_node()->__left_ = __t.__end_node()->__left_; __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); size() = __t.size(); __t.__begin_node() = __t.__end_node(); __t.__end_node()->__left_ = nullptr; __t.size() = 0; } } else { __begin_node() = __end_node(); }}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, true_type) _NOEXCEPT_(is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value){ destroy(static_cast<__node_pointer>(__end_node()->__left_)); __begin_node_ = __t.__begin_node_; __pair1_.first() = __t.__pair1_.first(); __move_assign_alloc(__t); __pair3_ = _VSTD::move(__t.__pair3_); if (size() == 0) __begin_node() = __end_node(); else { __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); __t.__begin_node() = __t.__end_node(); __t.__end_node()->__left_ = nullptr; __t.size() = 0; }}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::__move_assign(__tree& __t, false_type){ if (__node_alloc() == __t.__node_alloc()) __move_assign(__t, true_type()); else { value_comp() = _VSTD::move(__t.value_comp()); const_iterator __e = end(); if (size() != 0) { __node_pointer __cache = __detach();#ifndef _LIBCPP_NO_EXCEPTIONS try {#endif // _LIBCPP_NO_EXCEPTIONS while (__cache != nullptr && __t.size() != 0) { __cache->__value_ = _VSTD::move(__t.remove(__t.begin())->__value_); __node_pointer __next = __detach(__cache); __node_insert_multi(__cache); __cache = __next; }#ifndef _LIBCPP_NO_EXCEPTIONS } catch (...) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); throw; }#endif // _LIBCPP_NO_EXCEPTIONS if (__cache != nullptr) { while (__cache->__parent_ != nullptr) __cache = static_cast<__node_pointer>(__cache->__parent_); destroy(__cache); } } while (__t.size() != 0) __insert_multi(__e, _NodeTypes::__move(__t.remove(__t.begin())->__value_)); }}template <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>&__tree<_Tp, _Compare, _Allocator>::operator=(__tree&& __t) _NOEXCEPT_( __node_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<value_compare>::value && is_nothrow_move_assignable<__node_allocator>::value) { __move_assign(__t, integral_constant<bool, __node_traits::propagate_on_container_move_assignment::value>()); return *this;}#endif // _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>__tree<_Tp, _Compare, _Allocator>::~__tree(){ static_assert((is_copy_constructible<value_compare>::value), "Comparator must be copy-constructible.");#ifndef _LIBCPP_CXX03_LANG static_assert((__diagnose_tree_helper<_Tp, _Compare, _Allocator>:: __trigger_diagnostics()), "");#endif destroy(__root());}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::destroy(__node_pointer __nd) _NOEXCEPT{ if (__nd != nullptr) { destroy(static_cast<__node_pointer>(__nd->__left_)); destroy(static_cast<__node_pointer>(__nd->__right_)); __node_allocator& __na = __node_alloc(); __node_traits::destroy(__na, _NodeTypes::__get_ptr(__nd->__value_)); __node_traits::deallocate(__na, __nd, 1); }}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::swap(__tree& __t)#if _LIBCPP_STD_VER <= 11 _NOEXCEPT_( __is_nothrow_swappable<value_compare>::value && (!__node_traits::propagate_on_container_swap::value || __is_nothrow_swappable<__node_allocator>::value) )#else _NOEXCEPT_(__is_nothrow_swappable<value_compare>::value)#endif{ using _VSTD::swap; swap(__begin_node_, __t.__begin_node_); swap(__pair1_.first(), __t.__pair1_.first()); __swap_allocator(__node_alloc(), __t.__node_alloc()); __pair3_.swap(__t.__pair3_); if (size() == 0) __begin_node() = __end_node(); else __end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__end_node()); if (__t.size() == 0) __t.__begin_node() = __t.__end_node(); else __t.__end_node()->__left_->__parent_ = static_cast<__parent_pointer>(__t.__end_node());}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::clear() _NOEXCEPT{ destroy(__root()); size() = 0; __begin_node() = __end_node(); __end_node()->__left_ = nullptr;}// Find lower_bound place to insert// Set __parent to parent of null leaf// Return reference to null leaftemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&__tree<_Tp, _Compare, _Allocator>::__find_leaf_low(__parent_pointer& __parent, const key_type& __v){ __node_pointer __nd = __root(); if (__nd != nullptr) { while (true) { if (value_comp()(__nd->__value_, __v)) { if (__nd->__right_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__right_); else { __parent = static_cast<__parent_pointer>(__nd); return __nd->__right_; } } else { if (__nd->__left_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__left_); else { __parent = static_cast<__parent_pointer>(__nd); return __parent->__left_; } } } } __parent = static_cast<__parent_pointer>(__end_node()); return __parent->__left_;}// Find upper_bound place to insert// Set __parent to parent of null leaf// Return reference to null leaftemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&__tree<_Tp, _Compare, _Allocator>::__find_leaf_high(__parent_pointer& __parent, const key_type& __v){ __node_pointer __nd = __root(); if (__nd != nullptr) { while (true) { if (value_comp()(__v, __nd->__value_)) { if (__nd->__left_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__left_); else { __parent = static_cast<__parent_pointer>(__nd); return __parent->__left_; } } else { if (__nd->__right_ != nullptr) __nd = static_cast<__node_pointer>(__nd->__right_); else { __parent = static_cast<__parent_pointer>(__nd); return __nd->__right_; } } } } __parent = static_cast<__parent_pointer>(__end_node()); return __parent->__left_;}// Find leaf place to insert closest to __hint// First check prior to __hint.// Next check after __hint.// Next do O(log N) search.// Set __parent to parent of null leaf// Return reference to null leaftemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&__tree<_Tp, _Compare, _Allocator>::__find_leaf(const_iterator __hint, __parent_pointer& __parent, const key_type& __v){ if (__hint == end() || !value_comp()(*__hint, __v)) // check before { // __v <= *__hint const_iterator __prior = __hint; if (__prior == begin() || !value_comp()(__v, *--__prior)) { // *prev(__hint) <= __v <= *__hint if (__hint.__ptr_->__left_ == nullptr) { __parent = static_cast<__parent_pointer>(__hint.__ptr_); return __parent->__left_; } else { __parent = static_cast<__parent_pointer>(__prior.__ptr_); return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; } } // __v < *prev(__hint) return __find_leaf_high(__parent, __v); } // else __v > *__hint return __find_leaf_low(__parent, __v);}// Find place to insert if __v doesn't exist// Set __parent to parent of null leaf// Return reference to null leaf// If __v exists, set parent to node of __v and return reference to node of __vtemplate <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&__tree<_Tp, _Compare, _Allocator>::__find_equal(__parent_pointer& __parent, const _Key& __v){ __node_pointer __nd = __root(); __node_base_pointer* __nd_ptr = __root_ptr(); if (__nd != nullptr) { while (true) { if (value_comp()(__v, __nd->__value_)) { if (__nd->__left_ != nullptr) { __nd_ptr = _VSTD::addressof(__nd->__left_); __nd = static_cast<__node_pointer>(__nd->__left_); } else { __parent = static_cast<__parent_pointer>(__nd); return __parent->__left_; } } else if (value_comp()(__nd->__value_, __v)) { if (__nd->__right_ != nullptr) { __nd_ptr = _VSTD::addressof(__nd->__right_); __nd = static_cast<__node_pointer>(__nd->__right_); } else { __parent = static_cast<__parent_pointer>(__nd); return __nd->__right_; } } else { __parent = static_cast<__parent_pointer>(__nd); return *__nd_ptr; } } } __parent = static_cast<__parent_pointer>(__end_node()); return __parent->__left_;}// Find place to insert if __v doesn't exist// First check prior to __hint.// Next check after __hint.// Next do O(log N) search.// Set __parent to parent of null leaf// Return reference to null leaf// If __v exists, set parent to node of __v and return reference to node of __vtemplate <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::__node_base_pointer&__tree<_Tp, _Compare, _Allocator>::__find_equal(const_iterator __hint, __parent_pointer& __parent, __node_base_pointer& __dummy, const _Key& __v){ if (__hint == end() || value_comp()(__v, *__hint)) // check before { // __v < *__hint const_iterator __prior = __hint; if (__prior == begin() || value_comp()(*--__prior, __v)) { // *prev(__hint) < __v < *__hint if (__hint.__ptr_->__left_ == nullptr) { __parent = static_cast<__parent_pointer>(__hint.__ptr_); return __parent->__left_; } else { __parent = static_cast<__parent_pointer>(__prior.__ptr_); return static_cast<__node_base_pointer>(__prior.__ptr_)->__right_; } } // __v <= *prev(__hint) return __find_equal(__parent, __v); } else if (value_comp()(*__hint, __v)) // check after { // *__hint < __v const_iterator __next = _VSTD::next(__hint); if (__next == end() || value_comp()(__v, *__next)) { // *__hint < __v < *_VSTD::next(__hint) if (__hint.__get_np()->__right_ == nullptr) { __parent = static_cast<__parent_pointer>(__hint.__ptr_); return static_cast<__node_base_pointer>(__hint.__ptr_)->__right_; } else { __parent = static_cast<__parent_pointer>(__next.__ptr_); return __parent->__left_; } } // *next(__hint) <= __v return __find_equal(__parent, __v); } // else __v == *__hint __parent = static_cast<__parent_pointer>(__hint.__ptr_); __dummy = static_cast<__node_base_pointer>(__hint.__ptr_); return __dummy;}template <class _Tp, class _Compare, class _Allocator>void__tree<_Tp, _Compare, _Allocator>::__insert_node_at(__parent_pointer __parent, __node_base_pointer& __child, __node_base_pointer __new_node){ __new_node->__left_ = nullptr; __new_node->__right_ = nullptr; __new_node->__parent_ = __parent; // __new_node->__is_black_ is initialized in __tree_balance_after_insert __child = __new_node; if (__begin_node()->__left_ != nullptr) __begin_node() = static_cast<__iter_pointer>(__begin_node()->__left_); __tree_balance_after_insert(__end_node()->__left_, __child); ++size();}#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>template <class _Key, class... _Args>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args&&... __args)#elsetemplate <class _Tp, class _Compare, class _Allocator>template <class _Key, class _Args>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>__tree<_Tp, _Compare, _Allocator>::__emplace_unique_key_args(_Key const& __k, _Args& __args)#endif{ __parent_pointer __parent; __node_base_pointer& __child = __find_equal(__parent, __k); __node_pointer __r = static_cast<__node_pointer>(__child); bool __inserted = false; if (__child == nullptr) {#ifndef _LIBCPP_CXX03_LANG __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);#else __node_holder __h = __construct_node(__args);#endif __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); __inserted = true; } return pair<iterator, bool>(iterator(__r), __inserted);}#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>template <class _Key, class... _Args>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( const_iterator __p, _Key const& __k, _Args&&... __args)#elsetemplate <class _Tp, class _Compare, class _Allocator>template <class _Key, class _Args>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_key_args( const_iterator __p, _Key const& __k, _Args& __args)#endif{ __parent_pointer __parent; __node_base_pointer __dummy; __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k); __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) {#ifndef _LIBCPP_CXX03_LANG __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...);#else __node_holder __h = __construct_node(__args);#endif __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); } return iterator(__r);}#ifndef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>template <class ..._Args>typename __tree<_Tp, _Compare, _Allocator>::__node_holder__tree<_Tp, _Compare, _Allocator>::__construct_node(_Args&& ...__args){ static_assert(!__is_tree_value_type<_Args...>::value, "Cannot construct from __value_type"); __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), _VSTD::forward<_Args>(__args)...); __h.get_deleter().__value_constructed = true; return __h;}template <class _Tp, class _Compare, class _Allocator>template <class... _Args>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>__tree<_Tp, _Compare, _Allocator>::__emplace_unique_impl(_Args&&... __args){ __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __parent_pointer __parent; __node_base_pointer& __child = __find_equal(__parent, __h->__value_); __node_pointer __r = static_cast<__node_pointer>(__child); bool __inserted = false; if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); __inserted = true; } return pair<iterator, bool>(iterator(__r), __inserted);}template <class _Tp, class _Compare, class _Allocator>template <class... _Args>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__emplace_hint_unique_impl(const_iterator __p, _Args&&... __args){ __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __parent_pointer __parent; __node_base_pointer __dummy; __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __h->__value_); __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); __r = __h.release(); } return iterator(__r);}template <class _Tp, class _Compare, class _Allocator>template <class... _Args>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__emplace_multi(_Args&&... __args){ __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __parent_pointer __parent; __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__h->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release()));}template <class _Tp, class _Compare, class _Allocator>template <class... _Args>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__emplace_hint_multi(const_iterator __p, _Args&&... __args){ __node_holder __h = __construct_node(_VSTD::forward<_Args>(__args)...); __parent_pointer __parent; __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__h->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(static_cast<__node_pointer>(__h.release()));}#else // _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_holder__tree<_Tp, _Compare, _Allocator>::__construct_node(const __container_value_type& __v){ __node_allocator& __na = __node_alloc(); __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na)); __node_traits::construct(__na, _NodeTypes::__get_ptr(__h->__value_), __v); __h.get_deleter().__value_constructed = true; return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03}#endif // _LIBCPP_CXX03_LANG#ifdef _LIBCPP_CXX03_LANGtemplate <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__insert_multi(const __container_value_type& __v){ __parent_pointer __parent; __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__v)); __node_holder __h = __construct_node(__v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(__h.release());}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__insert_multi(const_iterator __p, const __container_value_type& __v){ __parent_pointer __parent; __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__v)); __node_holder __h = __construct_node(__v); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get())); return iterator(__h.release());}#endiftemplate <class _Tp, class _Compare, class _Allocator>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, bool>__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(__node_pointer __nd){ __parent_pointer __parent; __node_base_pointer& __child = __find_equal(__parent, __nd->__value_); __node_pointer __r = static_cast<__node_pointer>(__child); bool __inserted = false; if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); __r = __nd; __inserted = true; } return pair<iterator, bool>(iterator(__r), __inserted);}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__node_insert_unique(const_iterator __p, __node_pointer __nd){ __parent_pointer __parent; __node_base_pointer __dummy; __node_base_pointer& __child = __find_equal(__p, __parent, __nd->__value_); __node_pointer __r = static_cast<__node_pointer>(__child); if (__child == nullptr) { __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); __r = __nd; } return iterator(__r);}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(__node_pointer __nd){ __parent_pointer __parent; __node_base_pointer& __child = __find_leaf_high(__parent, _NodeTypes::__get_key(__nd->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd);}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__node_insert_multi(const_iterator __p, __node_pointer __nd){ __parent_pointer __parent; __node_base_pointer& __child = __find_leaf(__p, __parent, _NodeTypes::__get_key(__nd->__value_)); __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__nd)); return iterator(__nd);}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p){ __node_pointer __np = __p.__get_np(); iterator __r(__p.__ptr_); ++__r; if (__begin_node() == __p.__ptr_) __begin_node() = __r.__ptr_; --size(); __node_allocator& __na = __node_alloc(); __tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np)); __node_traits::destroy(__na, _NodeTypes::__get_ptr( const_cast<__node_value_type&>(*__p))); __node_traits::deallocate(__na, __np, 1); return __r;}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::erase(const_iterator __f, const_iterator __l){ while (__f != __l) __f = erase(__f); return iterator(__l.__ptr_);}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::size_type__tree<_Tp, _Compare, _Allocator>::__erase_unique(const _Key& __k){ iterator __i = find(__k); if (__i == end()) return 0; erase(__i); return 1;}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::size_type__tree<_Tp, _Compare, _Allocator>::__erase_multi(const _Key& __k){ pair<iterator, iterator> __p = __equal_range_multi(__k); size_type __r = 0; for (; __p.first != __p.second; ++__r) __p.first = erase(__p.first); return __r;}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v){ iterator __p = __lower_bound(__v, __root(), __end_node()); if (__p != end() && !value_comp()(__v, *__p)) return __p; return end();}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::const_iterator__tree<_Tp, _Compare, _Allocator>::find(const _Key& __v) const{ const_iterator __p = __lower_bound(__v, __root(), __end_node()); if (__p != end() && !value_comp()(__v, *__p)) return __p; return end();}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::size_type__tree<_Tp, _Compare, _Allocator>::__count_unique(const _Key& __k) const{ __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return 1; } return 0;}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::size_type__tree<_Tp, _Compare, _Allocator>::__count_multi(const _Key& __k) const{ __iter_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __result = static_cast<__iter_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _VSTD::distance( __lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result) ); } return 0;}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result){ while (__root != nullptr) { if (!value_comp()(__root->__value_, __v)) { __result = static_cast<__iter_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else __root = static_cast<__node_pointer>(__root->__right_); } return iterator(__result);}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::const_iterator__tree<_Tp, _Compare, _Allocator>::__lower_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const{ while (__root != nullptr) { if (!value_comp()(__root->__value_, __v)) { __result = static_cast<__iter_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else __root = static_cast<__node_pointer>(__root->__right_); } return const_iterator(__result);}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::iterator__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result){ while (__root != nullptr) { if (value_comp()(__v, __root->__value_)) { __result = static_cast<__iter_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else __root = static_cast<__node_pointer>(__root->__right_); } return iterator(__result);}template <class _Tp, class _Compare, class _Allocator>template <class _Key>typename __tree<_Tp, _Compare, _Allocator>::const_iterator__tree<_Tp, _Compare, _Allocator>::__upper_bound(const _Key& __v, __node_pointer __root, __iter_pointer __result) const{ while (__root != nullptr) { if (value_comp()(__v, __root->__value_)) { __result = static_cast<__iter_pointer>(__root); __root = static_cast<__node_pointer>(__root->__left_); } else __root = static_cast<__node_pointer>(__root->__right_); } return const_iterator(__result);}template <class _Tp, class _Compare, class _Allocator>template <class _Key>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k){ typedef pair<iterator, iterator> _Pp; __iter_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __result = static_cast<__iter_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(iterator(__rt), iterator( __rt->__right_ != nullptr ? static_cast<__iter_pointer>(__tree_min(__rt->__right_)) : __result)); } return _Pp(iterator(__result), iterator(__result));}template <class _Tp, class _Compare, class _Allocator>template <class _Key>pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator>__tree<_Tp, _Compare, _Allocator>::__equal_range_unique(const _Key& __k) const{ typedef pair<const_iterator, const_iterator> _Pp; __iter_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __result = static_cast<__iter_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(const_iterator(__rt), const_iterator( __rt->__right_ != nullptr ? static_cast<__iter_pointer>(__tree_min(__rt->__right_)) : __result)); } return _Pp(const_iterator(__result), const_iterator(__result));}template <class _Tp, class _Compare, class _Allocator>template <class _Key>pair<typename __tree<_Tp, _Compare, _Allocator>::iterator, typename __tree<_Tp, _Compare, _Allocator>::iterator>__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k){ typedef pair<iterator, iterator> _Pp; __iter_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __result = static_cast<__iter_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); } return _Pp(iterator(__result), iterator(__result));}template <class _Tp, class _Compare, class _Allocator>template <class _Key>pair<typename __tree<_Tp, _Compare, _Allocator>::const_iterator, typename __tree<_Tp, _Compare, _Allocator>::const_iterator>__tree<_Tp, _Compare, _Allocator>::__equal_range_multi(const _Key& __k) const{ typedef pair<const_iterator, const_iterator> _Pp; __iter_pointer __result = __end_node(); __node_pointer __rt = __root(); while (__rt != nullptr) { if (value_comp()(__k, __rt->__value_)) { __result = static_cast<__iter_pointer>(__rt); __rt = static_cast<__node_pointer>(__rt->__left_); } else if (value_comp()(__rt->__value_, __k)) __rt = static_cast<__node_pointer>(__rt->__right_); else return _Pp(__lower_bound(__k, static_cast<__node_pointer>(__rt->__left_), static_cast<__iter_pointer>(__rt)), __upper_bound(__k, static_cast<__node_pointer>(__rt->__right_), __result)); } return _Pp(const_iterator(__result), const_iterator(__result));}template <class _Tp, class _Compare, class _Allocator>typename __tree<_Tp, _Compare, _Allocator>::__node_holder__tree<_Tp, _Compare, _Allocator>::remove(const_iterator __p) _NOEXCEPT{ __node_pointer __np = __p.__get_np(); if (__begin_node() == __p.__ptr_) { if (__np->__right_ != nullptr) __begin_node() = static_cast<__iter_pointer>(__np->__right_); else __begin_node() = static_cast<__iter_pointer>(__np->__parent_); } --size(); __tree_remove(__end_node()->__left_, static_cast<__node_base_pointer>(__np)); return __node_holder(__np, _Dp(__node_alloc(), true));}template <class _Tp, class _Compare, class _Allocator>inline _LIBCPP_INLINE_VISIBILITYvoidswap(__tree<_Tp, _Compare, _Allocator>& __x, __tree<_Tp, _Compare, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))){ __x.swap(__y);}_LIBCPP_END_NAMESPACE_STD_LIBCPP_POP_MACROS#endif // _LIBCPP___TREE