vector 108 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308
  1. // -*- C++ -*-
  2. //===----------------------------------------------------------------------===//
  3. //
  4. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  5. // See https://llvm.org/LICENSE.txt for license information.
  6. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  7. //
  8. //===----------------------------------------------------------------------===//
  9. #ifndef _LIBCPP_VECTOR
  10. #define _LIBCPP_VECTOR
  11. /*
  12. vector synopsis
  13. namespace std
  14. {
  15. template <class T, class Allocator = allocator<T> >
  16. class vector
  17. {
  18. public:
  19. typedef T value_type;
  20. typedef Allocator allocator_type;
  21. typedef typename allocator_type::reference reference;
  22. typedef typename allocator_type::const_reference const_reference;
  23. typedef implementation-defined iterator;
  24. typedef implementation-defined const_iterator;
  25. typedef typename allocator_type::size_type size_type;
  26. typedef typename allocator_type::difference_type difference_type;
  27. typedef typename allocator_type::pointer pointer;
  28. typedef typename allocator_type::const_pointer const_pointer;
  29. typedef std::reverse_iterator<iterator> reverse_iterator;
  30. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  31. vector()
  32. noexcept(is_nothrow_default_constructible<allocator_type>::value);
  33. explicit vector(const allocator_type&);
  34. explicit vector(size_type n);
  35. explicit vector(size_type n, const allocator_type&); // C++14
  36. vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  37. template <class InputIterator>
  38. vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  39. vector(const vector& x);
  40. vector(vector&& x)
  41. noexcept(is_nothrow_move_constructible<allocator_type>::value);
  42. vector(initializer_list<value_type> il);
  43. vector(initializer_list<value_type> il, const allocator_type& a);
  44. ~vector();
  45. vector& operator=(const vector& x);
  46. vector& operator=(vector&& x)
  47. noexcept(
  48. allocator_type::propagate_on_container_move_assignment::value ||
  49. allocator_type::is_always_equal::value); // C++17
  50. vector& operator=(initializer_list<value_type> il);
  51. template <class InputIterator>
  52. void assign(InputIterator first, InputIterator last);
  53. void assign(size_type n, const value_type& u);
  54. void assign(initializer_list<value_type> il);
  55. allocator_type get_allocator() const noexcept;
  56. iterator begin() noexcept;
  57. const_iterator begin() const noexcept;
  58. iterator end() noexcept;
  59. const_iterator end() const noexcept;
  60. reverse_iterator rbegin() noexcept;
  61. const_reverse_iterator rbegin() const noexcept;
  62. reverse_iterator rend() noexcept;
  63. const_reverse_iterator rend() const noexcept;
  64. const_iterator cbegin() const noexcept;
  65. const_iterator cend() const noexcept;
  66. const_reverse_iterator crbegin() const noexcept;
  67. const_reverse_iterator crend() const noexcept;
  68. size_type size() const noexcept;
  69. size_type max_size() const noexcept;
  70. size_type capacity() const noexcept;
  71. bool empty() const noexcept;
  72. void reserve(size_type n);
  73. void shrink_to_fit() noexcept;
  74. reference operator[](size_type n);
  75. const_reference operator[](size_type n) const;
  76. reference at(size_type n);
  77. const_reference at(size_type n) const;
  78. reference front();
  79. const_reference front() const;
  80. reference back();
  81. const_reference back() const;
  82. value_type* data() noexcept;
  83. const value_type* data() const noexcept;
  84. void push_back(const value_type& x);
  85. void push_back(value_type&& x);
  86. template <class... Args>
  87. reference emplace_back(Args&&... args); // reference in C++17
  88. void pop_back();
  89. template <class... Args> iterator emplace(const_iterator position, Args&&... args);
  90. iterator insert(const_iterator position, const value_type& x);
  91. iterator insert(const_iterator position, value_type&& x);
  92. iterator insert(const_iterator position, size_type n, const value_type& x);
  93. template <class InputIterator>
  94. iterator insert(const_iterator position, InputIterator first, InputIterator last);
  95. iterator insert(const_iterator position, initializer_list<value_type> il);
  96. iterator erase(const_iterator position);
  97. iterator erase(const_iterator first, const_iterator last);
  98. void clear() noexcept;
  99. void resize(size_type sz);
  100. void resize(size_type sz, const value_type& c);
  101. void swap(vector&)
  102. noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
  103. allocator_traits<allocator_type>::is_always_equal::value); // C++17
  104. bool __invariants() const;
  105. };
  106. template <class Allocator = allocator<T> >
  107. class vector<bool, Allocator>
  108. {
  109. public:
  110. typedef bool value_type;
  111. typedef Allocator allocator_type;
  112. typedef implementation-defined iterator;
  113. typedef implementation-defined const_iterator;
  114. typedef typename allocator_type::size_type size_type;
  115. typedef typename allocator_type::difference_type difference_type;
  116. typedef iterator pointer;
  117. typedef const_iterator const_pointer;
  118. typedef std::reverse_iterator<iterator> reverse_iterator;
  119. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  120. class reference
  121. {
  122. public:
  123. reference(const reference&) noexcept;
  124. operator bool() const noexcept;
  125. reference& operator=(bool x) noexcept;
  126. reference& operator=(const reference& x) noexcept;
  127. iterator operator&() const noexcept;
  128. void flip() noexcept;
  129. };
  130. class const_reference
  131. {
  132. public:
  133. const_reference(const reference&) noexcept;
  134. operator bool() const noexcept;
  135. const_iterator operator&() const noexcept;
  136. };
  137. vector()
  138. noexcept(is_nothrow_default_constructible<allocator_type>::value);
  139. explicit vector(const allocator_type&);
  140. explicit vector(size_type n, const allocator_type& a = allocator_type()); // C++14
  141. vector(size_type n, const value_type& value, const allocator_type& = allocator_type());
  142. template <class InputIterator>
  143. vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type());
  144. vector(const vector& x);
  145. vector(vector&& x)
  146. noexcept(is_nothrow_move_constructible<allocator_type>::value);
  147. vector(initializer_list<value_type> il);
  148. vector(initializer_list<value_type> il, const allocator_type& a);
  149. ~vector();
  150. vector& operator=(const vector& x);
  151. vector& operator=(vector&& x)
  152. noexcept(
  153. allocator_type::propagate_on_container_move_assignment::value ||
  154. allocator_type::is_always_equal::value); // C++17
  155. vector& operator=(initializer_list<value_type> il);
  156. template <class InputIterator>
  157. void assign(InputIterator first, InputIterator last);
  158. void assign(size_type n, const value_type& u);
  159. void assign(initializer_list<value_type> il);
  160. allocator_type get_allocator() const noexcept;
  161. iterator begin() noexcept;
  162. const_iterator begin() const noexcept;
  163. iterator end() noexcept;
  164. const_iterator end() const noexcept;
  165. reverse_iterator rbegin() noexcept;
  166. const_reverse_iterator rbegin() const noexcept;
  167. reverse_iterator rend() noexcept;
  168. const_reverse_iterator rend() const noexcept;
  169. const_iterator cbegin() const noexcept;
  170. const_iterator cend() const noexcept;
  171. const_reverse_iterator crbegin() const noexcept;
  172. const_reverse_iterator crend() const noexcept;
  173. size_type size() const noexcept;
  174. size_type max_size() const noexcept;
  175. size_type capacity() const noexcept;
  176. bool empty() const noexcept;
  177. void reserve(size_type n);
  178. void shrink_to_fit() noexcept;
  179. reference operator[](size_type n);
  180. const_reference operator[](size_type n) const;
  181. reference at(size_type n);
  182. const_reference at(size_type n) const;
  183. reference front();
  184. const_reference front() const;
  185. reference back();
  186. const_reference back() const;
  187. void push_back(const value_type& x);
  188. template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17
  189. void pop_back();
  190. template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14
  191. iterator insert(const_iterator position, const value_type& x);
  192. iterator insert(const_iterator position, size_type n, const value_type& x);
  193. template <class InputIterator>
  194. iterator insert(const_iterator position, InputIterator first, InputIterator last);
  195. iterator insert(const_iterator position, initializer_list<value_type> il);
  196. iterator erase(const_iterator position);
  197. iterator erase(const_iterator first, const_iterator last);
  198. void clear() noexcept;
  199. void resize(size_type sz);
  200. void resize(size_type sz, value_type x);
  201. void swap(vector&)
  202. noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
  203. allocator_traits<allocator_type>::is_always_equal::value); // C++17
  204. void flip() noexcept;
  205. bool __invariants() const;
  206. };
  207. template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
  208. vector(InputIterator, InputIterator, Allocator = Allocator())
  209. -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
  210. template <class Allocator> struct hash<std::vector<bool, Allocator>>;
  211. template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  212. template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  213. template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  214. template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  215. template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  216. template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
  217. template <class T, class Allocator>
  218. void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
  219. noexcept(noexcept(x.swap(y)));
  220. template <class T, class Allocator, class U>
  221. typename vector<T, Allocator>::size_type
  222. erase(vector<T, Allocator>& c, const U& value); // C++20
  223. template <class T, class Allocator, class Predicate>
  224. typename vector<T, Allocator>::size_type
  225. erase_if(vector<T, Allocator>& c, Predicate pred); // C++20
  226. } // std
  227. */
  228. #include <__algorithm/copy.h>
  229. #include <__algorithm/equal.h>
  230. #include <__algorithm/fill_n.h>
  231. #include <__algorithm/lexicographical_compare.h>
  232. #include <__algorithm/remove.h>
  233. #include <__algorithm/remove_if.h>
  234. #include <__algorithm/rotate.h>
  235. #include <__algorithm/unwrap_iter.h>
  236. #include <__assert> // all public C++ headers provide the assertion handler
  237. #include <__bit_reference>
  238. #include <__config>
  239. #include <__debug>
  240. #include <__format/enable_insertable.h>
  241. #include <__functional/hash.h>
  242. #include <__functional/unary_function.h>
  243. #include <__iterator/advance.h>
  244. #include <__iterator/iterator_traits.h>
  245. #include <__iterator/reverse_iterator.h>
  246. #include <__iterator/wrap_iter.h>
  247. #include <__memory/allocate_at_least.h>
  248. #include <__split_buffer>
  249. #include <__utility/forward.h>
  250. #include <__utility/move.h>
  251. #include <__utility/swap.h>
  252. #include <climits>
  253. #include <cstdlib>
  254. #include <cstring>
  255. #include <iosfwd> // for forward declaration of vector
  256. #include <limits>
  257. #include <memory>
  258. #include <stdexcept>
  259. #include <type_traits>
  260. #include <version>
  261. #ifndef _LIBCPP_REMOVE_TRANSITIVE_INCLUDES
  262. # include <algorithm>
  263. # include <typeinfo>
  264. # include <utility>
  265. #endif
  266. // standard-mandated includes
  267. // [iterator.range]
  268. #include <__iterator/access.h>
  269. #include <__iterator/data.h>
  270. #include <__iterator/empty.h>
  271. #include <__iterator/reverse_access.h>
  272. #include <__iterator/size.h>
  273. // [vector.syn]
  274. #include <compare>
  275. #include <initializer_list>
  276. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  277. # pragma GCC system_header
  278. #endif
  279. _LIBCPP_PUSH_MACROS
  280. #include <__undef_macros>
  281. _LIBCPP_BEGIN_NAMESPACE_STD
  282. template <class _Tp, class _Allocator /* = allocator<_Tp> */>
  283. class _LIBCPP_TEMPLATE_VIS vector
  284. {
  285. private:
  286. typedef allocator<_Tp> __default_allocator_type;
  287. public:
  288. typedef vector __self;
  289. typedef _Tp value_type;
  290. typedef _Allocator allocator_type;
  291. typedef allocator_traits<allocator_type> __alloc_traits;
  292. typedef value_type& reference;
  293. typedef const value_type& const_reference;
  294. typedef typename __alloc_traits::size_type size_type;
  295. typedef typename __alloc_traits::difference_type difference_type;
  296. typedef typename __alloc_traits::pointer pointer;
  297. typedef typename __alloc_traits::const_pointer const_pointer;
  298. #if _YNDX_LIBCPP_MAKE_VECTOR_ITERATOR_POINTERS == 1
  299. typedef pointer iterator;
  300. typedef const_pointer const_iterator;
  301. #else
  302. typedef __wrap_iter<pointer> iterator;
  303. typedef __wrap_iter<const_pointer> const_iterator;
  304. #endif
  305. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  306. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  307. static_assert((is_same<typename allocator_type::value_type, value_type>::value),
  308. "Allocator::value_type must be same type as value_type");
  309. _LIBCPP_INLINE_VISIBILITY
  310. vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  311. {
  312. _VSTD::__debug_db_insert_c(this);
  313. }
  314. _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
  315. #if _LIBCPP_STD_VER <= 14
  316. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
  317. #else
  318. _NOEXCEPT
  319. #endif
  320. : __end_cap_(nullptr, __a)
  321. {
  322. _VSTD::__debug_db_insert_c(this);
  323. }
  324. explicit vector(size_type __n);
  325. #if _LIBCPP_STD_VER > 11
  326. explicit vector(size_type __n, const allocator_type& __a);
  327. #endif
  328. vector(size_type __n, const value_type& __x);
  329. template <class = __enable_if_t<__is_allocator<_Allocator>::value> >
  330. vector(size_type __n, const value_type& __x, const allocator_type& __a)
  331. : __end_cap_(nullptr, __a)
  332. {
  333. _VSTD::__debug_db_insert_c(this);
  334. if (__n > 0)
  335. {
  336. __vallocate(__n);
  337. __construct_at_end(__n, __x);
  338. }
  339. }
  340. template <class _InputIterator>
  341. vector(_InputIterator __first,
  342. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  343. is_constructible<
  344. value_type,
  345. typename iterator_traits<_InputIterator>::reference>::value,
  346. _InputIterator>::type __last);
  347. template <class _InputIterator>
  348. vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  349. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  350. is_constructible<
  351. value_type,
  352. typename iterator_traits<_InputIterator>::reference>::value>::type* = 0);
  353. template <class _ForwardIterator>
  354. vector(_ForwardIterator __first,
  355. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
  356. is_constructible<
  357. value_type,
  358. typename iterator_traits<_ForwardIterator>::reference>::value,
  359. _ForwardIterator>::type __last);
  360. template <class _ForwardIterator>
  361. vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  362. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
  363. is_constructible<
  364. value_type,
  365. typename iterator_traits<_ForwardIterator>::reference>::value>::type* = 0);
  366. _LIBCPP_INLINE_VISIBILITY
  367. ~vector()
  368. {
  369. __annotate_delete();
  370. std::__debug_db_erase_c(this);
  371. if (this->__begin_ != nullptr)
  372. {
  373. __clear();
  374. __alloc_traits::deallocate(__alloc(), this->__begin_, capacity());
  375. }
  376. }
  377. vector(const vector& __x);
  378. vector(const vector& __x, const __type_identity_t<allocator_type>& __a);
  379. _LIBCPP_INLINE_VISIBILITY
  380. vector& operator=(const vector& __x);
  381. #ifndef _LIBCPP_CXX03_LANG
  382. _LIBCPP_INLINE_VISIBILITY
  383. vector(initializer_list<value_type> __il);
  384. _LIBCPP_INLINE_VISIBILITY
  385. vector(initializer_list<value_type> __il, const allocator_type& __a);
  386. _LIBCPP_INLINE_VISIBILITY
  387. vector& operator=(initializer_list<value_type> __il)
  388. {assign(__il.begin(), __il.end()); return *this;}
  389. #endif // !_LIBCPP_CXX03_LANG
  390. _LIBCPP_INLINE_VISIBILITY
  391. vector(vector&& __x)
  392. #if _LIBCPP_STD_VER > 14
  393. noexcept;
  394. #else
  395. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  396. #endif
  397. _LIBCPP_INLINE_VISIBILITY
  398. vector(vector&& __x, const __type_identity_t<allocator_type>& __a);
  399. _LIBCPP_INLINE_VISIBILITY
  400. vector& operator=(vector&& __x)
  401. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
  402. template <class _InputIterator>
  403. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  404. is_constructible<
  405. value_type,
  406. typename iterator_traits<_InputIterator>::reference>::value,
  407. void
  408. >::type
  409. assign(_InputIterator __first, _InputIterator __last);
  410. template <class _ForwardIterator>
  411. typename enable_if
  412. <
  413. __is_cpp17_forward_iterator<_ForwardIterator>::value &&
  414. is_constructible<
  415. value_type,
  416. typename iterator_traits<_ForwardIterator>::reference>::value,
  417. void
  418. >::type
  419. assign(_ForwardIterator __first, _ForwardIterator __last);
  420. void assign(size_type __n, const_reference __u);
  421. #ifndef _LIBCPP_CXX03_LANG
  422. _LIBCPP_INLINE_VISIBILITY
  423. void assign(initializer_list<value_type> __il)
  424. {assign(__il.begin(), __il.end());}
  425. #endif
  426. _LIBCPP_INLINE_VISIBILITY
  427. allocator_type get_allocator() const _NOEXCEPT
  428. {return this->__alloc();}
  429. _LIBCPP_INLINE_VISIBILITY iterator begin() _NOEXCEPT;
  430. _LIBCPP_INLINE_VISIBILITY const_iterator begin() const _NOEXCEPT;
  431. _LIBCPP_INLINE_VISIBILITY iterator end() _NOEXCEPT;
  432. _LIBCPP_INLINE_VISIBILITY const_iterator end() const _NOEXCEPT;
  433. _LIBCPP_INLINE_VISIBILITY
  434. reverse_iterator rbegin() _NOEXCEPT
  435. {return reverse_iterator(end());}
  436. _LIBCPP_INLINE_VISIBILITY
  437. const_reverse_iterator rbegin() const _NOEXCEPT
  438. {return const_reverse_iterator(end());}
  439. _LIBCPP_INLINE_VISIBILITY
  440. reverse_iterator rend() _NOEXCEPT
  441. {return reverse_iterator(begin());}
  442. _LIBCPP_INLINE_VISIBILITY
  443. const_reverse_iterator rend() const _NOEXCEPT
  444. {return const_reverse_iterator(begin());}
  445. _LIBCPP_INLINE_VISIBILITY
  446. const_iterator cbegin() const _NOEXCEPT
  447. {return begin();}
  448. _LIBCPP_INLINE_VISIBILITY
  449. const_iterator cend() const _NOEXCEPT
  450. {return end();}
  451. _LIBCPP_INLINE_VISIBILITY
  452. const_reverse_iterator crbegin() const _NOEXCEPT
  453. {return rbegin();}
  454. _LIBCPP_INLINE_VISIBILITY
  455. const_reverse_iterator crend() const _NOEXCEPT
  456. {return rend();}
  457. _LIBCPP_INLINE_VISIBILITY
  458. size_type size() const _NOEXCEPT
  459. {return static_cast<size_type>(this->__end_ - this->__begin_);}
  460. _LIBCPP_INLINE_VISIBILITY
  461. size_type capacity() const _NOEXCEPT
  462. {return static_cast<size_type>(__end_cap() - this->__begin_);}
  463. _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
  464. bool empty() const _NOEXCEPT
  465. {return this->__begin_ == this->__end_;}
  466. size_type max_size() const _NOEXCEPT;
  467. void reserve(size_type __n);
  468. void shrink_to_fit() _NOEXCEPT;
  469. _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) _NOEXCEPT;
  470. _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const _NOEXCEPT;
  471. reference at(size_type __n);
  472. const_reference at(size_type __n) const;
  473. _LIBCPP_INLINE_VISIBILITY reference front() _NOEXCEPT
  474. {
  475. _LIBCPP_ASSERT(!empty(), "front() called on an empty vector");
  476. return *this->__begin_;
  477. }
  478. _LIBCPP_INLINE_VISIBILITY const_reference front() const _NOEXCEPT
  479. {
  480. _LIBCPP_ASSERT(!empty(), "front() called on an empty vector");
  481. return *this->__begin_;
  482. }
  483. _LIBCPP_INLINE_VISIBILITY reference back() _NOEXCEPT
  484. {
  485. _LIBCPP_ASSERT(!empty(), "back() called on an empty vector");
  486. return *(this->__end_ - 1);
  487. }
  488. _LIBCPP_INLINE_VISIBILITY const_reference back() const _NOEXCEPT
  489. {
  490. _LIBCPP_ASSERT(!empty(), "back() called on an empty vector");
  491. return *(this->__end_ - 1);
  492. }
  493. _LIBCPP_INLINE_VISIBILITY
  494. value_type* data() _NOEXCEPT
  495. {return _VSTD::__to_address(this->__begin_);}
  496. _LIBCPP_INLINE_VISIBILITY
  497. const value_type* data() const _NOEXCEPT
  498. {return _VSTD::__to_address(this->__begin_);}
  499. _LIBCPP_INLINE_VISIBILITY void push_back(const_reference __x);
  500. _LIBCPP_INLINE_VISIBILITY void push_back(value_type&& __x);
  501. template <class... _Args>
  502. _LIBCPP_INLINE_VISIBILITY
  503. #if _LIBCPP_STD_VER > 14
  504. reference emplace_back(_Args&&... __args);
  505. #else
  506. void emplace_back(_Args&&... __args);
  507. #endif
  508. _LIBCPP_INLINE_VISIBILITY
  509. void pop_back();
  510. iterator insert(const_iterator __position, const_reference __x);
  511. iterator insert(const_iterator __position, value_type&& __x);
  512. template <class... _Args>
  513. iterator emplace(const_iterator __position, _Args&&... __args);
  514. iterator insert(const_iterator __position, size_type __n, const_reference __x);
  515. template <class _InputIterator>
  516. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  517. is_constructible<
  518. value_type,
  519. typename iterator_traits<_InputIterator>::reference>::value,
  520. iterator
  521. >::type
  522. insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
  523. template <class _ForwardIterator>
  524. typename enable_if
  525. <
  526. __is_cpp17_forward_iterator<_ForwardIterator>::value &&
  527. is_constructible<
  528. value_type,
  529. typename iterator_traits<_ForwardIterator>::reference>::value,
  530. iterator
  531. >::type
  532. insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
  533. #ifndef _LIBCPP_CXX03_LANG
  534. _LIBCPP_INLINE_VISIBILITY
  535. iterator insert(const_iterator __position, initializer_list<value_type> __il)
  536. {return insert(__position, __il.begin(), __il.end());}
  537. #endif
  538. _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
  539. iterator erase(const_iterator __first, const_iterator __last);
  540. _LIBCPP_REINITIALIZES_OBJECT _LIBCPP_INLINE_VISIBILITY
  541. void clear() _NOEXCEPT
  542. {
  543. size_type __old_size = size();
  544. __clear();
  545. __annotate_shrink(__old_size);
  546. std::__debug_db_invalidate_all(this);
  547. }
  548. #if _YNDX_LIBCXX_ENABLE_VECTOR_POD_RESIZE_UNINITIALIZED
  549. void resize_uninitialized(size_type __sz);
  550. #endif
  551. void resize(size_type __sz);
  552. void resize(size_type __sz, const_reference __x);
  553. void swap(vector&)
  554. #if _LIBCPP_STD_VER >= 14
  555. _NOEXCEPT;
  556. #else
  557. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  558. __is_nothrow_swappable<allocator_type>::value);
  559. #endif
  560. bool __invariants() const;
  561. #ifdef _LIBCPP_ENABLE_DEBUG_MODE
  562. bool __dereferenceable(const const_iterator* __i) const;
  563. bool __decrementable(const const_iterator* __i) const;
  564. bool __addable(const const_iterator* __i, ptrdiff_t __n) const;
  565. bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const;
  566. #endif // _LIBCPP_ENABLE_DEBUG_MODE
  567. private:
  568. pointer __begin_ = nullptr;
  569. pointer __end_ = nullptr;
  570. __compressed_pair<pointer, allocator_type> __end_cap_ =
  571. __compressed_pair<pointer, allocator_type>(nullptr, __default_init_tag());
  572. _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(pointer __new_last);
  573. // Allocate space for __n objects
  574. // throws length_error if __n > max_size()
  575. // throws (probably bad_alloc) if memory run out
  576. // Precondition: __begin_ == __end_ == __end_cap() == 0
  577. // Precondition: __n > 0
  578. // Postcondition: capacity() >= __n
  579. // Postcondition: size() == 0
  580. _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
  581. if (__n > max_size())
  582. __throw_length_error();
  583. auto __allocation = std::__allocate_at_least(__alloc(), __n);
  584. __begin_ = __allocation.ptr;
  585. __end_ = __allocation.ptr;
  586. __end_cap() = __begin_ + __allocation.count;
  587. __annotate_new(0);
  588. }
  589. void __vdeallocate() _NOEXCEPT;
  590. _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
  591. void __construct_at_end(size_type __n);
  592. _LIBCPP_INLINE_VISIBILITY
  593. void __construct_at_end(size_type __n, const_reference __x);
  594. template <class _ForwardIterator>
  595. typename enable_if
  596. <
  597. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  598. void
  599. >::type
  600. __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n);
  601. void __append_uninitialized(size_type __n);
  602. void __append(size_type __n);
  603. void __append(size_type __n, const_reference __x);
  604. _LIBCPP_INLINE_VISIBILITY
  605. iterator __make_iter(pointer __p) _NOEXCEPT;
  606. _LIBCPP_INLINE_VISIBILITY
  607. const_iterator __make_iter(const_pointer __p) const _NOEXCEPT;
  608. void __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v);
  609. pointer __swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p);
  610. void __move_range(pointer __from_s, pointer __from_e, pointer __to);
  611. void __move_assign(vector& __c, true_type)
  612. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
  613. void __move_assign(vector& __c, false_type)
  614. _NOEXCEPT_(__alloc_traits::is_always_equal::value);
  615. _LIBCPP_INLINE_VISIBILITY
  616. void __destruct_at_end(pointer __new_last) _NOEXCEPT
  617. {
  618. __invalidate_iterators_past(__new_last);
  619. size_type __old_size = size();
  620. __base_destruct_at_end(__new_last);
  621. __annotate_shrink(__old_size);
  622. }
  623. template <class _Up>
  624. _LIBCPP_INLINE_VISIBILITY
  625. inline void __push_back_slow_path(_Up&& __x);
  626. template <class... _Args>
  627. _LIBCPP_INLINE_VISIBILITY
  628. inline void __emplace_back_slow_path(_Args&&... __args);
  629. // The following functions are no-ops outside of AddressSanitizer mode.
  630. // We call annotatations only for the default Allocator because other allocators
  631. // may not meet the AddressSanitizer alignment constraints.
  632. // See the documentation for __sanitizer_annotate_contiguous_container for more details.
  633. #ifndef _LIBCPP_HAS_NO_ASAN
  634. void __annotate_contiguous_container(const void *__beg, const void *__end,
  635. const void *__old_mid,
  636. const void *__new_mid) const
  637. {
  638. if (__beg && is_same<allocator_type, __default_allocator_type>::value)
  639. __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid);
  640. }
  641. #else
  642. _LIBCPP_INLINE_VISIBILITY
  643. void __annotate_contiguous_container(const void*, const void*, const void*,
  644. const void*) const _NOEXCEPT {}
  645. #endif
  646. _LIBCPP_INLINE_VISIBILITY
  647. void __annotate_new(size_type __current_size) const _NOEXCEPT {
  648. __annotate_contiguous_container(data(), data() + capacity(),
  649. data() + capacity(), data() + __current_size);
  650. }
  651. _LIBCPP_INLINE_VISIBILITY
  652. void __annotate_delete() const _NOEXCEPT {
  653. __annotate_contiguous_container(data(), data() + capacity(),
  654. data() + size(), data() + capacity());
  655. }
  656. _LIBCPP_INLINE_VISIBILITY
  657. void __annotate_increase(size_type __n) const _NOEXCEPT
  658. {
  659. __annotate_contiguous_container(data(), data() + capacity(),
  660. data() + size(), data() + size() + __n);
  661. }
  662. _LIBCPP_INLINE_VISIBILITY
  663. void __annotate_shrink(size_type __old_size) const _NOEXCEPT
  664. {
  665. __annotate_contiguous_container(data(), data() + capacity(),
  666. data() + __old_size, data() + size());
  667. }
  668. struct _ConstructTransaction {
  669. explicit _ConstructTransaction(vector &__v, size_type __n)
  670. : __v_(__v), __pos_(__v.__end_), __new_end_(__v.__end_ + __n) {
  671. #ifndef _LIBCPP_HAS_NO_ASAN
  672. __v_.__annotate_increase(__n);
  673. #endif
  674. }
  675. ~_ConstructTransaction() {
  676. __v_.__end_ = __pos_;
  677. #ifndef _LIBCPP_HAS_NO_ASAN
  678. if (__pos_ != __new_end_) {
  679. __v_.__annotate_shrink(__new_end_ - __v_.__begin_);
  680. }
  681. #endif
  682. }
  683. vector &__v_;
  684. pointer __pos_;
  685. const_pointer const __new_end_;
  686. private:
  687. _ConstructTransaction(_ConstructTransaction const&) = delete;
  688. _ConstructTransaction& operator=(_ConstructTransaction const&) = delete;
  689. };
  690. template <class ..._Args>
  691. _LIBCPP_INLINE_VISIBILITY
  692. void __construct_one_at_end(_Args&& ...__args) {
  693. _ConstructTransaction __tx(*this, 1);
  694. __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_),
  695. _VSTD::forward<_Args>(__args)...);
  696. ++__tx.__pos_;
  697. }
  698. _LIBCPP_INLINE_VISIBILITY
  699. allocator_type& __alloc() _NOEXCEPT
  700. {return this->__end_cap_.second();}
  701. _LIBCPP_INLINE_VISIBILITY
  702. const allocator_type& __alloc() const _NOEXCEPT
  703. {return this->__end_cap_.second();}
  704. _LIBCPP_INLINE_VISIBILITY
  705. pointer& __end_cap() _NOEXCEPT
  706. {return this->__end_cap_.first();}
  707. _LIBCPP_INLINE_VISIBILITY
  708. const pointer& __end_cap() const _NOEXCEPT
  709. {return this->__end_cap_.first();}
  710. _LIBCPP_INLINE_VISIBILITY
  711. void __clear() _NOEXCEPT {__base_destruct_at_end(this->__begin_);}
  712. _LIBCPP_INLINE_VISIBILITY
  713. void __base_destruct_at_end(pointer __new_last) _NOEXCEPT {
  714. pointer __soon_to_be_end = this->__end_;
  715. while (__new_last != __soon_to_be_end)
  716. __alloc_traits::destroy(__alloc(), _VSTD::__to_address(--__soon_to_be_end));
  717. this->__end_ = __new_last;
  718. }
  719. _LIBCPP_INLINE_VISIBILITY
  720. void __copy_assign_alloc(const vector& __c)
  721. {__copy_assign_alloc(__c, integral_constant<bool,
  722. __alloc_traits::propagate_on_container_copy_assignment::value>());}
  723. _LIBCPP_INLINE_VISIBILITY
  724. void __move_assign_alloc(vector& __c)
  725. _NOEXCEPT_(
  726. !__alloc_traits::propagate_on_container_move_assignment::value ||
  727. is_nothrow_move_assignable<allocator_type>::value)
  728. {__move_assign_alloc(__c, integral_constant<bool,
  729. __alloc_traits::propagate_on_container_move_assignment::value>());}
  730. _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
  731. void __throw_length_error() const {
  732. _VSTD::__throw_length_error("vector");
  733. }
  734. _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
  735. void __throw_out_of_range() const {
  736. _VSTD::__throw_out_of_range("vector");
  737. }
  738. _LIBCPP_INLINE_VISIBILITY
  739. void __copy_assign_alloc(const vector& __c, true_type)
  740. {
  741. if (__alloc() != __c.__alloc())
  742. {
  743. __clear();
  744. __alloc_traits::deallocate(__alloc(), this->__begin_, capacity());
  745. this->__begin_ = this->__end_ = __end_cap() = nullptr;
  746. }
  747. __alloc() = __c.__alloc();
  748. }
  749. _LIBCPP_INLINE_VISIBILITY
  750. void __copy_assign_alloc(const vector&, false_type)
  751. {}
  752. _LIBCPP_INLINE_VISIBILITY
  753. void __move_assign_alloc(vector& __c, true_type)
  754. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  755. {
  756. __alloc() = _VSTD::move(__c.__alloc());
  757. }
  758. _LIBCPP_INLINE_VISIBILITY
  759. void __move_assign_alloc(vector&, false_type)
  760. _NOEXCEPT
  761. {}
  762. };
  763. #if _LIBCPP_STD_VER >= 17
  764. template<class _InputIterator,
  765. class _Alloc = allocator<__iter_value_type<_InputIterator>>,
  766. class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  767. class = enable_if_t<__is_allocator<_Alloc>::value>
  768. >
  769. vector(_InputIterator, _InputIterator)
  770. -> vector<__iter_value_type<_InputIterator>, _Alloc>;
  771. template<class _InputIterator,
  772. class _Alloc,
  773. class = enable_if_t<__is_cpp17_input_iterator<_InputIterator>::value>,
  774. class = enable_if_t<__is_allocator<_Alloc>::value>
  775. >
  776. vector(_InputIterator, _InputIterator, _Alloc)
  777. -> vector<__iter_value_type<_InputIterator>, _Alloc>;
  778. #endif
  779. template <class _Tp, class _Allocator>
  780. void
  781. vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v)
  782. {
  783. __annotate_delete();
  784. _VSTD::__construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, this->__end_, __v.__begin_);
  785. _VSTD::swap(this->__begin_, __v.__begin_);
  786. _VSTD::swap(this->__end_, __v.__end_);
  787. _VSTD::swap(this->__end_cap(), __v.__end_cap());
  788. __v.__first_ = __v.__begin_;
  789. __annotate_new(size());
  790. std::__debug_db_invalidate_all(this);
  791. }
  792. template <class _Tp, class _Allocator>
  793. typename vector<_Tp, _Allocator>::pointer
  794. vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p)
  795. {
  796. __annotate_delete();
  797. pointer __r = __v.__begin_;
  798. _VSTD::__construct_backward_with_exception_guarantees(this->__alloc(), this->__begin_, __p, __v.__begin_);
  799. _VSTD::__construct_forward_with_exception_guarantees(this->__alloc(), __p, this->__end_, __v.__end_);
  800. _VSTD::swap(this->__begin_, __v.__begin_);
  801. _VSTD::swap(this->__end_, __v.__end_);
  802. _VSTD::swap(this->__end_cap(), __v.__end_cap());
  803. __v.__first_ = __v.__begin_;
  804. __annotate_new(size());
  805. std::__debug_db_invalidate_all(this);
  806. return __r;
  807. }
  808. template <class _Tp, class _Allocator>
  809. void
  810. vector<_Tp, _Allocator>::__vdeallocate() _NOEXCEPT
  811. {
  812. if (this->__begin_ != nullptr)
  813. {
  814. clear();
  815. __alloc_traits::deallocate(this->__alloc(), this->__begin_, capacity());
  816. this->__begin_ = this->__end_ = this->__end_cap() = nullptr;
  817. }
  818. }
  819. template <class _Tp, class _Allocator>
  820. typename vector<_Tp, _Allocator>::size_type
  821. vector<_Tp, _Allocator>::max_size() const _NOEXCEPT
  822. {
  823. return _VSTD::min<size_type>(__alloc_traits::max_size(this->__alloc()),
  824. numeric_limits<difference_type>::max());
  825. }
  826. // Precondition: __new_size > capacity()
  827. template <class _Tp, class _Allocator>
  828. inline _LIBCPP_INLINE_VISIBILITY
  829. typename vector<_Tp, _Allocator>::size_type
  830. vector<_Tp, _Allocator>::__recommend(size_type __new_size) const
  831. {
  832. const size_type __ms = max_size();
  833. if (__new_size > __ms)
  834. this->__throw_length_error();
  835. const size_type __cap = capacity();
  836. if (__cap >= __ms / 2)
  837. return __ms;
  838. return _VSTD::max<size_type>(2 * __cap, __new_size);
  839. }
  840. // Default constructs __n objects starting at __end_
  841. // throws if construction throws
  842. // Precondition: __n > 0
  843. // Precondition: size() + __n <= capacity()
  844. // Postcondition: size() == size() + __n
  845. template <class _Tp, class _Allocator>
  846. void
  847. vector<_Tp, _Allocator>::__construct_at_end(size_type __n)
  848. {
  849. _ConstructTransaction __tx(*this, __n);
  850. const_pointer __new_end = __tx.__new_end_;
  851. for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
  852. __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos));
  853. }
  854. }
  855. // Copy constructs __n objects starting at __end_ from __x
  856. // throws if construction throws
  857. // Precondition: __n > 0
  858. // Precondition: size() + __n <= capacity()
  859. // Postcondition: size() == old size() + __n
  860. // Postcondition: [i] == __x for all i in [size() - __n, __n)
  861. template <class _Tp, class _Allocator>
  862. inline
  863. void
  864. vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x)
  865. {
  866. _ConstructTransaction __tx(*this, __n);
  867. const_pointer __new_end = __tx.__new_end_;
  868. for (pointer __pos = __tx.__pos_; __pos != __new_end; __tx.__pos_ = ++__pos) {
  869. __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__pos), __x);
  870. }
  871. }
  872. template <class _Tp, class _Allocator>
  873. template <class _ForwardIterator>
  874. typename enable_if
  875. <
  876. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  877. void
  878. >::type
  879. vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n)
  880. {
  881. _ConstructTransaction __tx(*this, __n);
  882. _VSTD::__construct_range_forward(this->__alloc(), __first, __last, __tx.__pos_);
  883. }
  884. template <class _Tp, class _Allocator>
  885. void
  886. vector<_Tp, _Allocator>::__append_uninitialized(size_type __n)
  887. {
  888. if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n) {
  889. __annotate_increase(__n);
  890. this->__end_ += __n;
  891. }
  892. else
  893. {
  894. allocator_type& __a = this->__alloc();
  895. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
  896. __v.__uninitialized_at_end(__n);
  897. __swap_out_circular_buffer(__v);
  898. }
  899. }
  900. // Default constructs __n objects starting at __end_
  901. // throws if construction throws
  902. // Postcondition: size() == size() + __n
  903. // Exception safety: strong.
  904. template <class _Tp, class _Allocator>
  905. void
  906. vector<_Tp, _Allocator>::__append(size_type __n)
  907. {
  908. if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
  909. this->__construct_at_end(__n);
  910. else
  911. {
  912. allocator_type& __a = this->__alloc();
  913. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
  914. __v.__construct_at_end(__n);
  915. __swap_out_circular_buffer(__v);
  916. }
  917. }
  918. // Default constructs __n objects starting at __end_
  919. // throws if construction throws
  920. // Postcondition: size() == size() + __n
  921. // Exception safety: strong.
  922. template <class _Tp, class _Allocator>
  923. void
  924. vector<_Tp, _Allocator>::__append(size_type __n, const_reference __x)
  925. {
  926. if (static_cast<size_type>(this->__end_cap() - this->__end_) >= __n)
  927. this->__construct_at_end(__n, __x);
  928. else
  929. {
  930. allocator_type& __a = this->__alloc();
  931. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), size(), __a);
  932. __v.__construct_at_end(__n, __x);
  933. __swap_out_circular_buffer(__v);
  934. }
  935. }
  936. template <class _Tp, class _Allocator>
  937. vector<_Tp, _Allocator>::vector(size_type __n)
  938. {
  939. _VSTD::__debug_db_insert_c(this);
  940. if (__n > 0)
  941. {
  942. __vallocate(__n);
  943. __construct_at_end(__n);
  944. }
  945. }
  946. #if _LIBCPP_STD_VER > 11
  947. template <class _Tp, class _Allocator>
  948. vector<_Tp, _Allocator>::vector(size_type __n, const allocator_type& __a)
  949. : __end_cap_(nullptr, __a)
  950. {
  951. _VSTD::__debug_db_insert_c(this);
  952. if (__n > 0)
  953. {
  954. __vallocate(__n);
  955. __construct_at_end(__n);
  956. }
  957. }
  958. #endif
  959. template <class _Tp, class _Allocator>
  960. vector<_Tp, _Allocator>::vector(size_type __n, const value_type& __x)
  961. {
  962. _VSTD::__debug_db_insert_c(this);
  963. if (__n > 0)
  964. {
  965. __vallocate(__n);
  966. __construct_at_end(__n, __x);
  967. }
  968. }
  969. template <class _Tp, class _Allocator>
  970. template <class _InputIterator>
  971. vector<_Tp, _Allocator>::vector(_InputIterator __first,
  972. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  973. is_constructible<
  974. value_type,
  975. typename iterator_traits<_InputIterator>::reference>::value,
  976. _InputIterator>::type __last)
  977. {
  978. _VSTD::__debug_db_insert_c(this);
  979. for (; __first != __last; ++__first)
  980. emplace_back(*__first);
  981. }
  982. template <class _Tp, class _Allocator>
  983. template <class _InputIterator>
  984. vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  985. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  986. is_constructible<
  987. value_type,
  988. typename iterator_traits<_InputIterator>::reference>::value>::type*)
  989. : __end_cap_(nullptr, __a)
  990. {
  991. _VSTD::__debug_db_insert_c(this);
  992. for (; __first != __last; ++__first)
  993. emplace_back(*__first);
  994. }
  995. template <class _Tp, class _Allocator>
  996. template <class _ForwardIterator>
  997. vector<_Tp, _Allocator>::vector(_ForwardIterator __first,
  998. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
  999. is_constructible<
  1000. value_type,
  1001. typename iterator_traits<_ForwardIterator>::reference>::value,
  1002. _ForwardIterator>::type __last)
  1003. {
  1004. _VSTD::__debug_db_insert_c(this);
  1005. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  1006. if (__n > 0)
  1007. {
  1008. __vallocate(__n);
  1009. __construct_at_end(__first, __last, __n);
  1010. }
  1011. }
  1012. template <class _Tp, class _Allocator>
  1013. template <class _ForwardIterator>
  1014. vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  1015. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value &&
  1016. is_constructible<
  1017. value_type,
  1018. typename iterator_traits<_ForwardIterator>::reference>::value>::type*)
  1019. : __end_cap_(nullptr, __a)
  1020. {
  1021. _VSTD::__debug_db_insert_c(this);
  1022. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  1023. if (__n > 0)
  1024. {
  1025. __vallocate(__n);
  1026. __construct_at_end(__first, __last, __n);
  1027. }
  1028. }
  1029. template <class _Tp, class _Allocator>
  1030. vector<_Tp, _Allocator>::vector(const vector& __x)
  1031. : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc()))
  1032. {
  1033. _VSTD::__debug_db_insert_c(this);
  1034. size_type __n = __x.size();
  1035. if (__n > 0)
  1036. {
  1037. __vallocate(__n);
  1038. __construct_at_end(__x.__begin_, __x.__end_, __n);
  1039. }
  1040. }
  1041. template <class _Tp, class _Allocator>
  1042. vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t<allocator_type>& __a)
  1043. : __end_cap_(nullptr, __a)
  1044. {
  1045. _VSTD::__debug_db_insert_c(this);
  1046. size_type __n = __x.size();
  1047. if (__n > 0)
  1048. {
  1049. __vallocate(__n);
  1050. __construct_at_end(__x.__begin_, __x.__end_, __n);
  1051. }
  1052. }
  1053. template <class _Tp, class _Allocator>
  1054. inline _LIBCPP_INLINE_VISIBILITY
  1055. vector<_Tp, _Allocator>::vector(vector&& __x)
  1056. #if _LIBCPP_STD_VER > 14
  1057. noexcept
  1058. #else
  1059. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
  1060. #endif
  1061. : __end_cap_(nullptr, _VSTD::move(__x.__alloc()))
  1062. {
  1063. _VSTD::__debug_db_insert_c(this);
  1064. std::__debug_db_swap(this, std::addressof(__x));
  1065. this->__begin_ = __x.__begin_;
  1066. this->__end_ = __x.__end_;
  1067. this->__end_cap() = __x.__end_cap();
  1068. __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
  1069. }
  1070. template <class _Tp, class _Allocator>
  1071. inline _LIBCPP_INLINE_VISIBILITY
  1072. vector<_Tp, _Allocator>::vector(vector&& __x, const __type_identity_t<allocator_type>& __a)
  1073. : __end_cap_(nullptr, __a)
  1074. {
  1075. _VSTD::__debug_db_insert_c(this);
  1076. if (__a == __x.__alloc())
  1077. {
  1078. this->__begin_ = __x.__begin_;
  1079. this->__end_ = __x.__end_;
  1080. this->__end_cap() = __x.__end_cap();
  1081. __x.__begin_ = __x.__end_ = __x.__end_cap() = nullptr;
  1082. std::__debug_db_swap(this, std::addressof(__x));
  1083. }
  1084. else
  1085. {
  1086. typedef move_iterator<iterator> _Ip;
  1087. assign(_Ip(__x.begin()), _Ip(__x.end()));
  1088. }
  1089. }
  1090. #ifndef _LIBCPP_CXX03_LANG
  1091. template <class _Tp, class _Allocator>
  1092. inline _LIBCPP_INLINE_VISIBILITY
  1093. vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il)
  1094. {
  1095. _VSTD::__debug_db_insert_c(this);
  1096. if (__il.size() > 0)
  1097. {
  1098. __vallocate(__il.size());
  1099. __construct_at_end(__il.begin(), __il.end(), __il.size());
  1100. }
  1101. }
  1102. template <class _Tp, class _Allocator>
  1103. inline _LIBCPP_INLINE_VISIBILITY
  1104. vector<_Tp, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
  1105. : __end_cap_(nullptr, __a)
  1106. {
  1107. _VSTD::__debug_db_insert_c(this);
  1108. if (__il.size() > 0)
  1109. {
  1110. __vallocate(__il.size());
  1111. __construct_at_end(__il.begin(), __il.end(), __il.size());
  1112. }
  1113. }
  1114. #endif // _LIBCPP_CXX03_LANG
  1115. template <class _Tp, class _Allocator>
  1116. inline _LIBCPP_INLINE_VISIBILITY
  1117. vector<_Tp, _Allocator>&
  1118. vector<_Tp, _Allocator>::operator=(vector&& __x)
  1119. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
  1120. {
  1121. __move_assign(__x, integral_constant<bool,
  1122. __alloc_traits::propagate_on_container_move_assignment::value>());
  1123. return *this;
  1124. }
  1125. template <class _Tp, class _Allocator>
  1126. void
  1127. vector<_Tp, _Allocator>::__move_assign(vector& __c, false_type)
  1128. _NOEXCEPT_(__alloc_traits::is_always_equal::value)
  1129. {
  1130. if (__alloc() != __c.__alloc())
  1131. {
  1132. typedef move_iterator<iterator> _Ip;
  1133. assign(_Ip(__c.begin()), _Ip(__c.end()));
  1134. }
  1135. else
  1136. __move_assign(__c, true_type());
  1137. }
  1138. template <class _Tp, class _Allocator>
  1139. void
  1140. vector<_Tp, _Allocator>::__move_assign(vector& __c, true_type)
  1141. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  1142. {
  1143. __vdeallocate();
  1144. __move_assign_alloc(__c); // this can throw
  1145. this->__begin_ = __c.__begin_;
  1146. this->__end_ = __c.__end_;
  1147. this->__end_cap() = __c.__end_cap();
  1148. __c.__begin_ = __c.__end_ = __c.__end_cap() = nullptr;
  1149. std::__debug_db_swap(this, std::addressof(__c));
  1150. }
  1151. template <class _Tp, class _Allocator>
  1152. inline _LIBCPP_INLINE_VISIBILITY
  1153. vector<_Tp, _Allocator>&
  1154. vector<_Tp, _Allocator>::operator=(const vector& __x)
  1155. {
  1156. if (this != _VSTD::addressof(__x))
  1157. {
  1158. __copy_assign_alloc(__x);
  1159. assign(__x.__begin_, __x.__end_);
  1160. }
  1161. return *this;
  1162. }
  1163. template <class _Tp, class _Allocator>
  1164. template <class _InputIterator>
  1165. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  1166. is_constructible<
  1167. _Tp,
  1168. typename iterator_traits<_InputIterator>::reference>::value,
  1169. void
  1170. >::type
  1171. vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
  1172. {
  1173. clear();
  1174. for (; __first != __last; ++__first)
  1175. emplace_back(*__first);
  1176. }
  1177. template <class _Tp, class _Allocator>
  1178. template <class _ForwardIterator>
  1179. typename enable_if
  1180. <
  1181. __is_cpp17_forward_iterator<_ForwardIterator>::value &&
  1182. is_constructible<
  1183. _Tp,
  1184. typename iterator_traits<_ForwardIterator>::reference>::value,
  1185. void
  1186. >::type
  1187. vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
  1188. {
  1189. size_type __new_size = static_cast<size_type>(_VSTD::distance(__first, __last));
  1190. if (__new_size <= capacity())
  1191. {
  1192. _ForwardIterator __mid = __last;
  1193. bool __growing = false;
  1194. if (__new_size > size())
  1195. {
  1196. __growing = true;
  1197. __mid = __first;
  1198. _VSTD::advance(__mid, size());
  1199. }
  1200. pointer __m = _VSTD::copy(__first, __mid, this->__begin_);
  1201. if (__growing)
  1202. __construct_at_end(__mid, __last, __new_size - size());
  1203. else
  1204. this->__destruct_at_end(__m);
  1205. }
  1206. else
  1207. {
  1208. __vdeallocate();
  1209. __vallocate(__recommend(__new_size));
  1210. __construct_at_end(__first, __last, __new_size);
  1211. }
  1212. std::__debug_db_invalidate_all(this);
  1213. }
  1214. template <class _Tp, class _Allocator>
  1215. void
  1216. vector<_Tp, _Allocator>::assign(size_type __n, const_reference __u)
  1217. {
  1218. if (__n <= capacity())
  1219. {
  1220. size_type __s = size();
  1221. _VSTD::fill_n(this->__begin_, _VSTD::min(__n, __s), __u);
  1222. if (__n > __s)
  1223. __construct_at_end(__n - __s, __u);
  1224. else
  1225. this->__destruct_at_end(this->__begin_ + __n);
  1226. }
  1227. else
  1228. {
  1229. __vdeallocate();
  1230. __vallocate(__recommend(static_cast<size_type>(__n)));
  1231. __construct_at_end(__n, __u);
  1232. }
  1233. std::__debug_db_invalidate_all(this);
  1234. }
  1235. // We need to save the make_iter function and replace all constructor calls with it
  1236. // Made to support pointer iterators
  1237. template <class _Tp, class _Allocator>
  1238. inline _LIBCPP_INLINE_VISIBILITY
  1239. typename vector<_Tp, _Allocator>::iterator
  1240. vector<_Tp, _Allocator>::__make_iter(pointer __p) _NOEXCEPT
  1241. {
  1242. #if _YNDX_LIBCPP_MAKE_STRING_ITERATOR_POINTERS == 1
  1243. return iterator(__p);
  1244. #else
  1245. return iterator(this, __p);
  1246. #endif
  1247. }
  1248. template <class _Tp, class _Allocator>
  1249. inline _LIBCPP_INLINE_VISIBILITY
  1250. typename vector<_Tp, _Allocator>::const_iterator
  1251. vector<_Tp, _Allocator>::__make_iter(const_pointer __p) const _NOEXCEPT
  1252. {
  1253. #if _YNDX_LIBCPP_MAKE_STRING_ITERATOR_POINTERS == 1
  1254. return const_iterator(__p);
  1255. #else
  1256. return const_iterator(this, __p);
  1257. #endif
  1258. }
  1259. template <class _Tp, class _Allocator>
  1260. inline _LIBCPP_INLINE_VISIBILITY
  1261. typename vector<_Tp, _Allocator>::iterator
  1262. vector<_Tp, _Allocator>::begin() _NOEXCEPT
  1263. {
  1264. return __make_iter(this->__begin_);
  1265. }
  1266. template <class _Tp, class _Allocator>
  1267. inline _LIBCPP_INLINE_VISIBILITY
  1268. typename vector<_Tp, _Allocator>::const_iterator
  1269. vector<_Tp, _Allocator>::begin() const _NOEXCEPT
  1270. {
  1271. return __make_iter(this->__begin_);
  1272. }
  1273. template <class _Tp, class _Allocator>
  1274. inline _LIBCPP_INLINE_VISIBILITY
  1275. typename vector<_Tp, _Allocator>::iterator
  1276. vector<_Tp, _Allocator>::end() _NOEXCEPT
  1277. {
  1278. return __make_iter(this->__end_);
  1279. }
  1280. template <class _Tp, class _Allocator>
  1281. inline _LIBCPP_INLINE_VISIBILITY
  1282. typename vector<_Tp, _Allocator>::const_iterator
  1283. vector<_Tp, _Allocator>::end() const _NOEXCEPT
  1284. {
  1285. return __make_iter(this->__end_);
  1286. }
  1287. template <class _Tp, class _Allocator>
  1288. inline _LIBCPP_INLINE_VISIBILITY
  1289. typename vector<_Tp, _Allocator>::reference
  1290. vector<_Tp, _Allocator>::operator[](size_type __n) _NOEXCEPT
  1291. {
  1292. _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
  1293. return this->__begin_[__n];
  1294. }
  1295. template <class _Tp, class _Allocator>
  1296. inline _LIBCPP_INLINE_VISIBILITY
  1297. typename vector<_Tp, _Allocator>::const_reference
  1298. vector<_Tp, _Allocator>::operator[](size_type __n) const _NOEXCEPT
  1299. {
  1300. _LIBCPP_ASSERT(__n < size(), "vector[] index out of bounds");
  1301. return this->__begin_[__n];
  1302. }
  1303. template <class _Tp, class _Allocator>
  1304. typename vector<_Tp, _Allocator>::reference
  1305. vector<_Tp, _Allocator>::at(size_type __n)
  1306. {
  1307. if (__n >= size())
  1308. this->__throw_out_of_range();
  1309. return this->__begin_[__n];
  1310. }
  1311. template <class _Tp, class _Allocator>
  1312. typename vector<_Tp, _Allocator>::const_reference
  1313. vector<_Tp, _Allocator>::at(size_type __n) const
  1314. {
  1315. if (__n >= size())
  1316. this->__throw_out_of_range();
  1317. return this->__begin_[__n];
  1318. }
  1319. template <class _Tp, class _Allocator>
  1320. void
  1321. vector<_Tp, _Allocator>::reserve(size_type __n)
  1322. {
  1323. if (__n > capacity())
  1324. {
  1325. if (__n > max_size())
  1326. this->__throw_length_error();
  1327. allocator_type& __a = this->__alloc();
  1328. __split_buffer<value_type, allocator_type&> __v(__n, size(), __a);
  1329. __swap_out_circular_buffer(__v);
  1330. }
  1331. }
  1332. template <class _Tp, class _Allocator>
  1333. void
  1334. vector<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT
  1335. {
  1336. if (capacity() > size())
  1337. {
  1338. #ifndef _LIBCPP_NO_EXCEPTIONS
  1339. try
  1340. {
  1341. #endif // _LIBCPP_NO_EXCEPTIONS
  1342. allocator_type& __a = this->__alloc();
  1343. __split_buffer<value_type, allocator_type&> __v(size(), size(), __a);
  1344. __swap_out_circular_buffer(__v);
  1345. #ifndef _LIBCPP_NO_EXCEPTIONS
  1346. }
  1347. catch (...)
  1348. {
  1349. }
  1350. #endif // _LIBCPP_NO_EXCEPTIONS
  1351. }
  1352. }
  1353. template <class _Tp, class _Allocator>
  1354. template <class _Up>
  1355. void
  1356. vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x)
  1357. {
  1358. allocator_type& __a = this->__alloc();
  1359. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
  1360. // __v.push_back(_VSTD::forward<_Up>(__x));
  1361. __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x));
  1362. __v.__end_++;
  1363. __swap_out_circular_buffer(__v);
  1364. }
  1365. template <class _Tp, class _Allocator>
  1366. inline _LIBCPP_INLINE_VISIBILITY
  1367. void
  1368. vector<_Tp, _Allocator>::push_back(const_reference __x)
  1369. {
  1370. if (this->__end_ != this->__end_cap())
  1371. {
  1372. __construct_one_at_end(__x);
  1373. }
  1374. else
  1375. __push_back_slow_path(__x);
  1376. }
  1377. template <class _Tp, class _Allocator>
  1378. inline _LIBCPP_INLINE_VISIBILITY
  1379. void
  1380. vector<_Tp, _Allocator>::push_back(value_type&& __x)
  1381. {
  1382. if (this->__end_ < this->__end_cap())
  1383. {
  1384. __construct_one_at_end(_VSTD::move(__x));
  1385. }
  1386. else
  1387. __push_back_slow_path(_VSTD::move(__x));
  1388. }
  1389. template <class _Tp, class _Allocator>
  1390. template <class... _Args>
  1391. void
  1392. vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args)
  1393. {
  1394. allocator_type& __a = this->__alloc();
  1395. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), __a);
  1396. // __v.emplace_back(_VSTD::forward<_Args>(__args)...);
  1397. __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...);
  1398. __v.__end_++;
  1399. __swap_out_circular_buffer(__v);
  1400. }
  1401. template <class _Tp, class _Allocator>
  1402. template <class... _Args>
  1403. inline
  1404. #if _LIBCPP_STD_VER > 14
  1405. typename vector<_Tp, _Allocator>::reference
  1406. #else
  1407. void
  1408. #endif
  1409. vector<_Tp, _Allocator>::emplace_back(_Args&&... __args)
  1410. {
  1411. if (this->__end_ < this->__end_cap())
  1412. {
  1413. __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
  1414. }
  1415. else
  1416. __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...);
  1417. #if _LIBCPP_STD_VER > 14
  1418. return this->back();
  1419. #endif
  1420. }
  1421. template <class _Tp, class _Allocator>
  1422. inline
  1423. void
  1424. vector<_Tp, _Allocator>::pop_back()
  1425. {
  1426. _LIBCPP_ASSERT(!empty(), "vector::pop_back called on an empty vector");
  1427. this->__destruct_at_end(this->__end_ - 1);
  1428. }
  1429. template <class _Tp, class _Allocator>
  1430. inline _LIBCPP_INLINE_VISIBILITY
  1431. typename vector<_Tp, _Allocator>::iterator
  1432. vector<_Tp, _Allocator>::erase(const_iterator __position)
  1433. {
  1434. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1435. "vector::erase(iterator) called with an iterator not referring to this vector");
  1436. _LIBCPP_ASSERT(__position != end(),
  1437. "vector::erase(iterator) called with a non-dereferenceable iterator");
  1438. difference_type __ps = __position - cbegin();
  1439. pointer __p = this->__begin_ + __ps;
  1440. this->__destruct_at_end(_VSTD::move(__p + 1, this->__end_, __p));
  1441. this->__invalidate_iterators_past(__p-1);
  1442. iterator __r = __make_iter(__p);
  1443. return __r;
  1444. }
  1445. template <class _Tp, class _Allocator>
  1446. typename vector<_Tp, _Allocator>::iterator
  1447. vector<_Tp, _Allocator>::erase(const_iterator __first, const_iterator __last)
  1448. {
  1449. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__first)) == this,
  1450. "vector::erase(iterator, iterator) called with an iterator not referring to this vector");
  1451. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__last)) == this,
  1452. "vector::erase(iterator, iterator) called with an iterator not referring to this vector");
  1453. _LIBCPP_ASSERT(__first <= __last, "vector::erase(first, last) called with invalid range");
  1454. pointer __p = this->__begin_ + (__first - begin());
  1455. if (__first != __last) {
  1456. this->__destruct_at_end(_VSTD::move(__p + (__last - __first), this->__end_, __p));
  1457. this->__invalidate_iterators_past(__p - 1);
  1458. }
  1459. iterator __r = __make_iter(__p);
  1460. return __r;
  1461. }
  1462. template <class _Tp, class _Allocator>
  1463. void
  1464. vector<_Tp, _Allocator>::__move_range(pointer __from_s, pointer __from_e, pointer __to)
  1465. {
  1466. pointer __old_last = this->__end_;
  1467. difference_type __n = __old_last - __to;
  1468. {
  1469. pointer __i = __from_s + __n;
  1470. _ConstructTransaction __tx(*this, __from_e - __i);
  1471. for (pointer __pos = __tx.__pos_; __i < __from_e;
  1472. ++__i, (void) ++__pos, __tx.__pos_ = __pos) {
  1473. __alloc_traits::construct(this->__alloc(),
  1474. _VSTD::__to_address(__pos),
  1475. _VSTD::move(*__i));
  1476. }
  1477. }
  1478. _VSTD::move_backward(__from_s, __from_s + __n, __old_last);
  1479. }
  1480. template <class _Tp, class _Allocator>
  1481. typename vector<_Tp, _Allocator>::iterator
  1482. vector<_Tp, _Allocator>::insert(const_iterator __position, const_reference __x)
  1483. {
  1484. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1485. "vector::insert(iterator, x) called with an iterator not referring to this vector");
  1486. pointer __p = this->__begin_ + (__position - begin());
  1487. if (this->__end_ < this->__end_cap())
  1488. {
  1489. if (__p == this->__end_)
  1490. {
  1491. __construct_one_at_end(__x);
  1492. }
  1493. else
  1494. {
  1495. __move_range(__p, this->__end_, __p + 1);
  1496. const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
  1497. if (__p <= __xr && __xr < this->__end_)
  1498. ++__xr;
  1499. *__p = *__xr;
  1500. }
  1501. }
  1502. else
  1503. {
  1504. allocator_type& __a = this->__alloc();
  1505. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1506. __v.push_back(__x);
  1507. __p = __swap_out_circular_buffer(__v, __p);
  1508. }
  1509. return __make_iter(__p);
  1510. }
  1511. template <class _Tp, class _Allocator>
  1512. typename vector<_Tp, _Allocator>::iterator
  1513. vector<_Tp, _Allocator>::insert(const_iterator __position, value_type&& __x)
  1514. {
  1515. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1516. "vector::insert(iterator, x) called with an iterator not referring to this vector");
  1517. pointer __p = this->__begin_ + (__position - begin());
  1518. if (this->__end_ < this->__end_cap())
  1519. {
  1520. if (__p == this->__end_)
  1521. {
  1522. __construct_one_at_end(_VSTD::move(__x));
  1523. }
  1524. else
  1525. {
  1526. __move_range(__p, this->__end_, __p + 1);
  1527. *__p = _VSTD::move(__x);
  1528. }
  1529. }
  1530. else
  1531. {
  1532. allocator_type& __a = this->__alloc();
  1533. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1534. __v.push_back(_VSTD::move(__x));
  1535. __p = __swap_out_circular_buffer(__v, __p);
  1536. }
  1537. return __make_iter(__p);
  1538. }
  1539. template <class _Tp, class _Allocator>
  1540. template <class... _Args>
  1541. typename vector<_Tp, _Allocator>::iterator
  1542. vector<_Tp, _Allocator>::emplace(const_iterator __position, _Args&&... __args)
  1543. {
  1544. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1545. "vector::emplace(iterator, x) called with an iterator not referring to this vector");
  1546. pointer __p = this->__begin_ + (__position - begin());
  1547. if (this->__end_ < this->__end_cap())
  1548. {
  1549. if (__p == this->__end_)
  1550. {
  1551. __construct_one_at_end(_VSTD::forward<_Args>(__args)...);
  1552. }
  1553. else
  1554. {
  1555. __temp_value<value_type, _Allocator> __tmp(this->__alloc(), _VSTD::forward<_Args>(__args)...);
  1556. __move_range(__p, this->__end_, __p + 1);
  1557. *__p = _VSTD::move(__tmp.get());
  1558. }
  1559. }
  1560. else
  1561. {
  1562. allocator_type& __a = this->__alloc();
  1563. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), __p - this->__begin_, __a);
  1564. __v.emplace_back(_VSTD::forward<_Args>(__args)...);
  1565. __p = __swap_out_circular_buffer(__v, __p);
  1566. }
  1567. return __make_iter(__p);
  1568. }
  1569. template <class _Tp, class _Allocator>
  1570. typename vector<_Tp, _Allocator>::iterator
  1571. vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_reference __x)
  1572. {
  1573. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1574. "vector::insert(iterator, n, x) called with an iterator not referring to this vector");
  1575. pointer __p = this->__begin_ + (__position - begin());
  1576. if (__n > 0)
  1577. {
  1578. if (__n <= static_cast<size_type>(this->__end_cap() - this->__end_))
  1579. {
  1580. size_type __old_n = __n;
  1581. pointer __old_last = this->__end_;
  1582. if (__n > static_cast<size_type>(this->__end_ - __p))
  1583. {
  1584. size_type __cx = __n - (this->__end_ - __p);
  1585. __construct_at_end(__cx, __x);
  1586. __n -= __cx;
  1587. }
  1588. if (__n > 0)
  1589. {
  1590. __move_range(__p, __old_last, __p + __old_n);
  1591. const_pointer __xr = pointer_traits<const_pointer>::pointer_to(__x);
  1592. if (__p <= __xr && __xr < this->__end_)
  1593. __xr += __old_n;
  1594. _VSTD::fill_n(__p, __n, *__xr);
  1595. }
  1596. }
  1597. else
  1598. {
  1599. allocator_type& __a = this->__alloc();
  1600. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
  1601. __v.__construct_at_end(__n, __x);
  1602. __p = __swap_out_circular_buffer(__v, __p);
  1603. }
  1604. }
  1605. return __make_iter(__p);
  1606. }
  1607. template <class _Tp, class _Allocator>
  1608. template <class _InputIterator>
  1609. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value &&
  1610. is_constructible<
  1611. _Tp,
  1612. typename iterator_traits<_InputIterator>::reference>::value,
  1613. typename vector<_Tp, _Allocator>::iterator
  1614. >::type
  1615. vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
  1616. {
  1617. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1618. "vector::insert(iterator, range) called with an iterator not referring to this vector");
  1619. difference_type __off = __position - begin();
  1620. pointer __p = this->__begin_ + __off;
  1621. allocator_type& __a = this->__alloc();
  1622. pointer __old_last = this->__end_;
  1623. for (; this->__end_ != this->__end_cap() && __first != __last; ++__first)
  1624. {
  1625. __construct_one_at_end(*__first);
  1626. }
  1627. __split_buffer<value_type, allocator_type&> __v(__a);
  1628. if (__first != __last)
  1629. {
  1630. #ifndef _LIBCPP_NO_EXCEPTIONS
  1631. try
  1632. {
  1633. #endif // _LIBCPP_NO_EXCEPTIONS
  1634. __v.__construct_at_end(__first, __last);
  1635. difference_type __old_size = __old_last - this->__begin_;
  1636. difference_type __old_p = __p - this->__begin_;
  1637. reserve(__recommend(size() + __v.size()));
  1638. __p = this->__begin_ + __old_p;
  1639. __old_last = this->__begin_ + __old_size;
  1640. #ifndef _LIBCPP_NO_EXCEPTIONS
  1641. }
  1642. catch (...)
  1643. {
  1644. erase(__make_iter(__old_last), end());
  1645. throw;
  1646. }
  1647. #endif // _LIBCPP_NO_EXCEPTIONS
  1648. }
  1649. __p = _VSTD::rotate(__p, __old_last, this->__end_);
  1650. insert(__make_iter(__p), _VSTD::make_move_iterator(__v.begin()),
  1651. _VSTD::make_move_iterator(__v.end()));
  1652. return begin() + __off;
  1653. }
  1654. template <class _Tp, class _Allocator>
  1655. template <class _ForwardIterator>
  1656. typename enable_if
  1657. <
  1658. __is_cpp17_forward_iterator<_ForwardIterator>::value &&
  1659. is_constructible<
  1660. _Tp,
  1661. typename iterator_traits<_ForwardIterator>::reference>::value,
  1662. typename vector<_Tp, _Allocator>::iterator
  1663. >::type
  1664. vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
  1665. {
  1666. _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(_VSTD::addressof(__position)) == this,
  1667. "vector::insert(iterator, range) called with an iterator not referring to this vector");
  1668. pointer __p = this->__begin_ + (__position - begin());
  1669. difference_type __n = _VSTD::distance(__first, __last);
  1670. if (__n > 0)
  1671. {
  1672. if (__n <= this->__end_cap() - this->__end_)
  1673. {
  1674. size_type __old_n = __n;
  1675. pointer __old_last = this->__end_;
  1676. _ForwardIterator __m = __last;
  1677. difference_type __dx = this->__end_ - __p;
  1678. if (__n > __dx)
  1679. {
  1680. __m = __first;
  1681. difference_type __diff = this->__end_ - __p;
  1682. _VSTD::advance(__m, __diff);
  1683. __construct_at_end(__m, __last, __n - __diff);
  1684. __n = __dx;
  1685. }
  1686. if (__n > 0)
  1687. {
  1688. __move_range(__p, __old_last, __p + __old_n);
  1689. _VSTD::copy(__first, __m, __p);
  1690. }
  1691. }
  1692. else
  1693. {
  1694. allocator_type& __a = this->__alloc();
  1695. __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a);
  1696. __v.__construct_at_end(__first, __last);
  1697. __p = __swap_out_circular_buffer(__v, __p);
  1698. }
  1699. }
  1700. return __make_iter(__p);
  1701. }
  1702. template <class _Tp, class _Allocator>
  1703. void
  1704. vector<_Tp, _Allocator>::resize(size_type __sz)
  1705. {
  1706. size_type __cs = size();
  1707. if (__cs < __sz)
  1708. this->__append(__sz - __cs);
  1709. else if (__cs > __sz)
  1710. this->__destruct_at_end(this->__begin_ + __sz);
  1711. }
  1712. template <class _Tp, class _Allocator>
  1713. void
  1714. vector<_Tp, _Allocator>::resize(size_type __sz, const_reference __x)
  1715. {
  1716. size_type __cs = size();
  1717. if (__cs < __sz)
  1718. this->__append(__sz - __cs, __x);
  1719. else if (__cs > __sz)
  1720. this->__destruct_at_end(this->__begin_ + __sz);
  1721. }
  1722. #if _YNDX_LIBCXX_ENABLE_VECTOR_POD_RESIZE_UNINITIALIZED
  1723. template <class _Tp, class _Allocator>
  1724. void
  1725. vector<_Tp, _Allocator>::resize_uninitialized(size_type __sz)
  1726. {
  1727. size_type __cs = size();
  1728. if (__cs < __sz)
  1729. this->__append_uninitialized(__sz - __cs);
  1730. else if (__cs > __sz) {
  1731. this->__end_ = this->__begin_ + __sz;
  1732. __annotate_shrink(__cs);
  1733. }
  1734. }
  1735. #endif
  1736. template <class _Tp, class _Allocator>
  1737. void
  1738. vector<_Tp, _Allocator>::swap(vector& __x)
  1739. #if _LIBCPP_STD_VER >= 14
  1740. _NOEXCEPT
  1741. #else
  1742. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  1743. __is_nothrow_swappable<allocator_type>::value)
  1744. #endif
  1745. {
  1746. _LIBCPP_ASSERT(__alloc_traits::propagate_on_container_swap::value ||
  1747. this->__alloc() == __x.__alloc(),
  1748. "vector::swap: Either propagate_on_container_swap must be true"
  1749. " or the allocators must compare equal");
  1750. _VSTD::swap(this->__begin_, __x.__begin_);
  1751. _VSTD::swap(this->__end_, __x.__end_);
  1752. _VSTD::swap(this->__end_cap(), __x.__end_cap());
  1753. _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
  1754. integral_constant<bool,__alloc_traits::propagate_on_container_swap::value>());
  1755. std::__debug_db_swap(this, std::addressof(__x));
  1756. }
  1757. template <class _Tp, class _Allocator>
  1758. bool
  1759. vector<_Tp, _Allocator>::__invariants() const
  1760. {
  1761. if (this->__begin_ == nullptr)
  1762. {
  1763. if (this->__end_ != nullptr || this->__end_cap() != nullptr)
  1764. return false;
  1765. }
  1766. else
  1767. {
  1768. if (this->__begin_ > this->__end_)
  1769. return false;
  1770. if (this->__begin_ == this->__end_cap())
  1771. return false;
  1772. if (this->__end_ > this->__end_cap())
  1773. return false;
  1774. }
  1775. return true;
  1776. }
  1777. #ifdef _LIBCPP_ENABLE_DEBUG_MODE
  1778. template <class _Tp, class _Allocator>
  1779. bool
  1780. vector<_Tp, _Allocator>::__dereferenceable(const const_iterator* __i) const
  1781. {
  1782. return this->__begin_ <= __i->base() && __i->base() < this->__end_;
  1783. }
  1784. template <class _Tp, class _Allocator>
  1785. bool
  1786. vector<_Tp, _Allocator>::__decrementable(const const_iterator* __i) const
  1787. {
  1788. return this->__begin_ < __i->base() && __i->base() <= this->__end_;
  1789. }
  1790. template <class _Tp, class _Allocator>
  1791. bool
  1792. vector<_Tp, _Allocator>::__addable(const const_iterator* __i, ptrdiff_t __n) const
  1793. {
  1794. const_pointer __p = __i->base() + __n;
  1795. return this->__begin_ <= __p && __p <= this->__end_;
  1796. }
  1797. template <class _Tp, class _Allocator>
  1798. bool
  1799. vector<_Tp, _Allocator>::__subscriptable(const const_iterator* __i, ptrdiff_t __n) const
  1800. {
  1801. const_pointer __p = __i->base() + __n;
  1802. return this->__begin_ <= __p && __p < this->__end_;
  1803. }
  1804. #endif // _LIBCPP_ENABLE_DEBUG_MODE
  1805. template <class _Tp, class _Allocator>
  1806. inline _LIBCPP_INLINE_VISIBILITY
  1807. void
  1808. vector<_Tp, _Allocator>::__invalidate_iterators_past(pointer __new_last) {
  1809. #ifdef _LIBCPP_ENABLE_DEBUG_MODE
  1810. __c_node* __c = __get_db()->__find_c_and_lock(this);
  1811. for (__i_node** __p = __c->end_; __p != __c->beg_; ) {
  1812. --__p;
  1813. const_iterator* __i = static_cast<const_iterator*>((*__p)->__i_);
  1814. if (__i->base() > __new_last) {
  1815. (*__p)->__c_ = nullptr;
  1816. if (--__c->end_ != __p)
  1817. _VSTD::memmove(__p, __p+1, (__c->end_ - __p)*sizeof(__i_node*));
  1818. }
  1819. }
  1820. __get_db()->unlock();
  1821. #else
  1822. ((void)__new_last);
  1823. #endif
  1824. }
  1825. #if _YNDX_LIBCXX_ENABLE_VECTOR_BOOL_COMPRESSION == 1
  1826. // vector<bool>
  1827. template <class _Allocator> class vector<bool, _Allocator>;
  1828. template <class _Allocator> struct hash<vector<bool, _Allocator> >;
  1829. template <class _Allocator>
  1830. struct __has_storage_type<vector<bool, _Allocator> >
  1831. {
  1832. static const bool value = true;
  1833. };
  1834. template <class _Allocator>
  1835. class _LIBCPP_TEMPLATE_VIS vector<bool, _Allocator>
  1836. {
  1837. public:
  1838. typedef vector __self;
  1839. typedef bool value_type;
  1840. typedef _Allocator allocator_type;
  1841. typedef allocator_traits<allocator_type> __alloc_traits;
  1842. typedef typename __alloc_traits::size_type size_type;
  1843. typedef typename __alloc_traits::difference_type difference_type;
  1844. typedef size_type __storage_type;
  1845. typedef __bit_iterator<vector, false> pointer;
  1846. typedef __bit_iterator<vector, true> const_pointer;
  1847. typedef pointer iterator;
  1848. typedef const_pointer const_iterator;
  1849. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  1850. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  1851. private:
  1852. typedef typename __rebind_alloc_helper<__alloc_traits, __storage_type>::type __storage_allocator;
  1853. typedef allocator_traits<__storage_allocator> __storage_traits;
  1854. typedef typename __storage_traits::pointer __storage_pointer;
  1855. typedef typename __storage_traits::const_pointer __const_storage_pointer;
  1856. __storage_pointer __begin_;
  1857. size_type __size_;
  1858. __compressed_pair<size_type, __storage_allocator> __cap_alloc_;
  1859. public:
  1860. typedef __bit_reference<vector> reference;
  1861. #ifdef _LIBCPP_ABI_BITSET_VECTOR_BOOL_CONST_SUBSCRIPT_RETURN_BOOL
  1862. using const_reference = bool;
  1863. #else
  1864. typedef __bit_const_reference<vector> const_reference;
  1865. #endif
  1866. private:
  1867. _LIBCPP_INLINE_VISIBILITY
  1868. size_type& __cap() _NOEXCEPT
  1869. {return __cap_alloc_.first();}
  1870. _LIBCPP_INLINE_VISIBILITY
  1871. const size_type& __cap() const _NOEXCEPT
  1872. {return __cap_alloc_.first();}
  1873. _LIBCPP_INLINE_VISIBILITY
  1874. __storage_allocator& __alloc() _NOEXCEPT
  1875. {return __cap_alloc_.second();}
  1876. _LIBCPP_INLINE_VISIBILITY
  1877. const __storage_allocator& __alloc() const _NOEXCEPT
  1878. {return __cap_alloc_.second();}
  1879. static const unsigned __bits_per_word = static_cast<unsigned>(sizeof(__storage_type) * CHAR_BIT);
  1880. _LIBCPP_INLINE_VISIBILITY
  1881. static size_type __internal_cap_to_external(size_type __n) _NOEXCEPT
  1882. {return __n * __bits_per_word;}
  1883. _LIBCPP_INLINE_VISIBILITY
  1884. static size_type __external_cap_to_internal(size_type __n) _NOEXCEPT
  1885. {return (__n - 1) / __bits_per_word + 1;}
  1886. public:
  1887. _LIBCPP_INLINE_VISIBILITY
  1888. vector() _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
  1889. _LIBCPP_INLINE_VISIBILITY explicit vector(const allocator_type& __a)
  1890. #if _LIBCPP_STD_VER <= 14
  1891. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value);
  1892. #else
  1893. _NOEXCEPT;
  1894. #endif
  1895. ~vector();
  1896. explicit vector(size_type __n);
  1897. #if _LIBCPP_STD_VER > 11
  1898. explicit vector(size_type __n, const allocator_type& __a);
  1899. #endif
  1900. vector(size_type __n, const value_type& __v);
  1901. vector(size_type __n, const value_type& __v, const allocator_type& __a);
  1902. template <class _InputIterator>
  1903. vector(_InputIterator __first, _InputIterator __last,
  1904. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type* = 0);
  1905. template <class _InputIterator>
  1906. vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  1907. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type* = 0);
  1908. template <class _ForwardIterator>
  1909. vector(_ForwardIterator __first, _ForwardIterator __last,
  1910. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
  1911. template <class _ForwardIterator>
  1912. vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  1913. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0);
  1914. vector(const vector& __v);
  1915. vector(const vector& __v, const allocator_type& __a);
  1916. vector& operator=(const vector& __v);
  1917. #ifndef _LIBCPP_CXX03_LANG
  1918. vector(initializer_list<value_type> __il);
  1919. vector(initializer_list<value_type> __il, const allocator_type& __a);
  1920. _LIBCPP_INLINE_VISIBILITY
  1921. vector& operator=(initializer_list<value_type> __il)
  1922. {assign(__il.begin(), __il.end()); return *this;}
  1923. #endif // !_LIBCPP_CXX03_LANG
  1924. _LIBCPP_INLINE_VISIBILITY
  1925. vector(vector&& __v)
  1926. #if _LIBCPP_STD_VER > 14
  1927. noexcept;
  1928. #else
  1929. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
  1930. #endif
  1931. vector(vector&& __v, const __type_identity_t<allocator_type>& __a);
  1932. _LIBCPP_INLINE_VISIBILITY
  1933. vector& operator=(vector&& __v)
  1934. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value));
  1935. template <class _InputIterator>
  1936. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value,
  1937. void
  1938. >::type
  1939. assign(_InputIterator __first, _InputIterator __last);
  1940. template <class _ForwardIterator>
  1941. typename enable_if
  1942. <
  1943. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  1944. void
  1945. >::type
  1946. assign(_ForwardIterator __first, _ForwardIterator __last);
  1947. void assign(size_type __n, const value_type& __x);
  1948. #ifndef _LIBCPP_CXX03_LANG
  1949. _LIBCPP_INLINE_VISIBILITY
  1950. void assign(initializer_list<value_type> __il)
  1951. {assign(__il.begin(), __il.end());}
  1952. #endif
  1953. _LIBCPP_INLINE_VISIBILITY allocator_type get_allocator() const _NOEXCEPT
  1954. {return allocator_type(this->__alloc());}
  1955. size_type max_size() const _NOEXCEPT;
  1956. _LIBCPP_INLINE_VISIBILITY
  1957. size_type capacity() const _NOEXCEPT
  1958. {return __internal_cap_to_external(__cap());}
  1959. _LIBCPP_INLINE_VISIBILITY
  1960. size_type size() const _NOEXCEPT
  1961. {return __size_;}
  1962. _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
  1963. bool empty() const _NOEXCEPT
  1964. {return __size_ == 0;}
  1965. void reserve(size_type __n);
  1966. void shrink_to_fit() _NOEXCEPT;
  1967. _LIBCPP_INLINE_VISIBILITY
  1968. iterator begin() _NOEXCEPT
  1969. {return __make_iter(0);}
  1970. _LIBCPP_INLINE_VISIBILITY
  1971. const_iterator begin() const _NOEXCEPT
  1972. {return __make_iter(0);}
  1973. _LIBCPP_INLINE_VISIBILITY
  1974. iterator end() _NOEXCEPT
  1975. {return __make_iter(__size_);}
  1976. _LIBCPP_INLINE_VISIBILITY
  1977. const_iterator end() const _NOEXCEPT
  1978. {return __make_iter(__size_);}
  1979. _LIBCPP_INLINE_VISIBILITY
  1980. reverse_iterator rbegin() _NOEXCEPT
  1981. {return reverse_iterator(end());}
  1982. _LIBCPP_INLINE_VISIBILITY
  1983. const_reverse_iterator rbegin() const _NOEXCEPT
  1984. {return const_reverse_iterator(end());}
  1985. _LIBCPP_INLINE_VISIBILITY
  1986. reverse_iterator rend() _NOEXCEPT
  1987. {return reverse_iterator(begin());}
  1988. _LIBCPP_INLINE_VISIBILITY
  1989. const_reverse_iterator rend() const _NOEXCEPT
  1990. {return const_reverse_iterator(begin());}
  1991. _LIBCPP_INLINE_VISIBILITY
  1992. const_iterator cbegin() const _NOEXCEPT
  1993. {return __make_iter(0);}
  1994. _LIBCPP_INLINE_VISIBILITY
  1995. const_iterator cend() const _NOEXCEPT
  1996. {return __make_iter(__size_);}
  1997. _LIBCPP_INLINE_VISIBILITY
  1998. const_reverse_iterator crbegin() const _NOEXCEPT
  1999. {return rbegin();}
  2000. _LIBCPP_INLINE_VISIBILITY
  2001. const_reverse_iterator crend() const _NOEXCEPT
  2002. {return rend();}
  2003. _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __n) {return __make_ref(__n);}
  2004. _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __n) const {return __make_ref(__n);}
  2005. reference at(size_type __n);
  2006. const_reference at(size_type __n) const;
  2007. _LIBCPP_INLINE_VISIBILITY reference front() {return __make_ref(0);}
  2008. _LIBCPP_INLINE_VISIBILITY const_reference front() const {return __make_ref(0);}
  2009. _LIBCPP_INLINE_VISIBILITY reference back() {return __make_ref(__size_ - 1);}
  2010. _LIBCPP_INLINE_VISIBILITY const_reference back() const {return __make_ref(__size_ - 1);}
  2011. void push_back(const value_type& __x);
  2012. #if _LIBCPP_STD_VER > 11
  2013. template <class... _Args>
  2014. #if _LIBCPP_STD_VER > 14
  2015. _LIBCPP_INLINE_VISIBILITY reference emplace_back(_Args&&... __args)
  2016. #else
  2017. _LIBCPP_INLINE_VISIBILITY void emplace_back(_Args&&... __args)
  2018. #endif
  2019. {
  2020. push_back ( value_type ( _VSTD::forward<_Args>(__args)... ));
  2021. #if _LIBCPP_STD_VER > 14
  2022. return this->back();
  2023. #endif
  2024. }
  2025. #endif
  2026. _LIBCPP_INLINE_VISIBILITY void pop_back() {--__size_;}
  2027. #if _LIBCPP_STD_VER > 11
  2028. template <class... _Args>
  2029. _LIBCPP_INLINE_VISIBILITY iterator emplace(const_iterator __position, _Args&&... __args)
  2030. { return insert ( __position, value_type ( _VSTD::forward<_Args>(__args)... )); }
  2031. #endif
  2032. iterator insert(const_iterator __position, const value_type& __x);
  2033. iterator insert(const_iterator __position, size_type __n, const value_type& __x);
  2034. template <class _InputIterator>
  2035. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value,
  2036. iterator
  2037. >::type
  2038. insert(const_iterator __position, _InputIterator __first, _InputIterator __last);
  2039. template <class _ForwardIterator>
  2040. typename enable_if
  2041. <
  2042. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  2043. iterator
  2044. >::type
  2045. insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last);
  2046. #ifndef _LIBCPP_CXX03_LANG
  2047. _LIBCPP_INLINE_VISIBILITY
  2048. iterator insert(const_iterator __position, initializer_list<value_type> __il)
  2049. {return insert(__position, __il.begin(), __il.end());}
  2050. #endif
  2051. _LIBCPP_INLINE_VISIBILITY iterator erase(const_iterator __position);
  2052. iterator erase(const_iterator __first, const_iterator __last);
  2053. _LIBCPP_REINITIALIZES_OBJECT _LIBCPP_INLINE_VISIBILITY
  2054. void clear() _NOEXCEPT {__size_ = 0;}
  2055. void swap(vector&)
  2056. #if _LIBCPP_STD_VER >= 14
  2057. _NOEXCEPT;
  2058. #else
  2059. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  2060. __is_nothrow_swappable<allocator_type>::value);
  2061. #endif
  2062. static void swap(reference __x, reference __y) _NOEXCEPT { _VSTD::swap(__x, __y); }
  2063. void resize(size_type __sz, value_type __x = false);
  2064. void flip() _NOEXCEPT;
  2065. bool __invariants() const;
  2066. private:
  2067. _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
  2068. void __throw_length_error() const {
  2069. _VSTD::__throw_length_error("vector");
  2070. }
  2071. _LIBCPP_NORETURN _LIBCPP_HIDE_FROM_ABI
  2072. void __throw_out_of_range() const {
  2073. _VSTD::__throw_out_of_range("vector");
  2074. }
  2075. // Allocate space for __n objects
  2076. // throws length_error if __n > max_size()
  2077. // throws (probably bad_alloc) if memory run out
  2078. // Precondition: __begin_ == __end_ == __cap() == 0
  2079. // Precondition: __n > 0
  2080. // Postcondition: capacity() >= __n
  2081. // Postcondition: size() == 0
  2082. _LIBCPP_HIDE_FROM_ABI void __vallocate(size_type __n) {
  2083. if (__n > max_size())
  2084. __throw_length_error();
  2085. auto __allocation = std::__allocate_at_least(__alloc(), __external_cap_to_internal(__n));
  2086. __begin_ = __allocation.ptr;
  2087. __size_ = 0;
  2088. __cap() = __allocation.count;
  2089. }
  2090. void __vdeallocate() _NOEXCEPT;
  2091. _LIBCPP_INLINE_VISIBILITY
  2092. static size_type __align_it(size_type __new_size) _NOEXCEPT
  2093. {return (__new_size + (__bits_per_word-1)) & ~((size_type)__bits_per_word-1);}
  2094. _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const;
  2095. _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, bool __x);
  2096. template <class _ForwardIterator>
  2097. typename enable_if
  2098. <
  2099. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  2100. void
  2101. >::type
  2102. __construct_at_end(_ForwardIterator __first, _ForwardIterator __last);
  2103. void __append(size_type __n, const_reference __x);
  2104. _LIBCPP_INLINE_VISIBILITY
  2105. reference __make_ref(size_type __pos) _NOEXCEPT
  2106. {return reference(__begin_ + __pos / __bits_per_word, __storage_type(1) << __pos % __bits_per_word);}
  2107. _LIBCPP_INLINE_VISIBILITY
  2108. const_reference __make_ref(size_type __pos) const _NOEXCEPT {
  2109. return __bit_const_reference<vector>(__begin_ + __pos / __bits_per_word,
  2110. __storage_type(1) << __pos % __bits_per_word);
  2111. }
  2112. _LIBCPP_INLINE_VISIBILITY
  2113. iterator __make_iter(size_type __pos) _NOEXCEPT
  2114. {return iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
  2115. _LIBCPP_INLINE_VISIBILITY
  2116. const_iterator __make_iter(size_type __pos) const _NOEXCEPT
  2117. {return const_iterator(__begin_ + __pos / __bits_per_word, static_cast<unsigned>(__pos % __bits_per_word));}
  2118. _LIBCPP_INLINE_VISIBILITY
  2119. iterator __const_iterator_cast(const_iterator __p) _NOEXCEPT
  2120. {return begin() + (__p - cbegin());}
  2121. _LIBCPP_INLINE_VISIBILITY
  2122. void __copy_assign_alloc(const vector& __v)
  2123. {__copy_assign_alloc(__v, integral_constant<bool,
  2124. __storage_traits::propagate_on_container_copy_assignment::value>());}
  2125. _LIBCPP_INLINE_VISIBILITY
  2126. void __copy_assign_alloc(const vector& __c, true_type)
  2127. {
  2128. if (__alloc() != __c.__alloc())
  2129. __vdeallocate();
  2130. __alloc() = __c.__alloc();
  2131. }
  2132. _LIBCPP_INLINE_VISIBILITY
  2133. void __copy_assign_alloc(const vector&, false_type)
  2134. {}
  2135. void __move_assign(vector& __c, false_type);
  2136. void __move_assign(vector& __c, true_type)
  2137. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
  2138. _LIBCPP_INLINE_VISIBILITY
  2139. void __move_assign_alloc(vector& __c)
  2140. _NOEXCEPT_(
  2141. !__storage_traits::propagate_on_container_move_assignment::value ||
  2142. is_nothrow_move_assignable<allocator_type>::value)
  2143. {__move_assign_alloc(__c, integral_constant<bool,
  2144. __storage_traits::propagate_on_container_move_assignment::value>());}
  2145. _LIBCPP_INLINE_VISIBILITY
  2146. void __move_assign_alloc(vector& __c, true_type)
  2147. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  2148. {
  2149. __alloc() = _VSTD::move(__c.__alloc());
  2150. }
  2151. _LIBCPP_INLINE_VISIBILITY
  2152. void __move_assign_alloc(vector&, false_type)
  2153. _NOEXCEPT
  2154. {}
  2155. size_t __hash_code() const _NOEXCEPT;
  2156. friend class __bit_reference<vector>;
  2157. friend class __bit_const_reference<vector>;
  2158. friend class __bit_iterator<vector, false>;
  2159. friend class __bit_iterator<vector, true>;
  2160. friend struct __bit_array<vector>;
  2161. friend struct _LIBCPP_TEMPLATE_VIS hash<vector>;
  2162. };
  2163. template <class _Allocator>
  2164. void
  2165. vector<bool, _Allocator>::__vdeallocate() _NOEXCEPT
  2166. {
  2167. if (this->__begin_ != nullptr)
  2168. {
  2169. __storage_traits::deallocate(this->__alloc(), this->__begin_, __cap());
  2170. std::__debug_db_invalidate_all(this);
  2171. this->__begin_ = nullptr;
  2172. this->__size_ = this->__cap() = 0;
  2173. }
  2174. }
  2175. template <class _Allocator>
  2176. typename vector<bool, _Allocator>::size_type
  2177. vector<bool, _Allocator>::max_size() const _NOEXCEPT
  2178. {
  2179. size_type __amax = __storage_traits::max_size(__alloc());
  2180. size_type __nmax = numeric_limits<size_type>::max() / 2; // end() >= begin(), always
  2181. if (__nmax / __bits_per_word <= __amax)
  2182. return __nmax;
  2183. return __internal_cap_to_external(__amax);
  2184. }
  2185. // Precondition: __new_size > capacity()
  2186. template <class _Allocator>
  2187. inline _LIBCPP_INLINE_VISIBILITY
  2188. typename vector<bool, _Allocator>::size_type
  2189. vector<bool, _Allocator>::__recommend(size_type __new_size) const
  2190. {
  2191. const size_type __ms = max_size();
  2192. if (__new_size > __ms)
  2193. this->__throw_length_error();
  2194. const size_type __cap = capacity();
  2195. if (__cap >= __ms / 2)
  2196. return __ms;
  2197. return _VSTD::max(2 * __cap, __align_it(__new_size));
  2198. }
  2199. // Default constructs __n objects starting at __end_
  2200. // Precondition: __n > 0
  2201. // Precondition: size() + __n <= capacity()
  2202. // Postcondition: size() == size() + __n
  2203. template <class _Allocator>
  2204. inline _LIBCPP_INLINE_VISIBILITY
  2205. void
  2206. vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x)
  2207. {
  2208. size_type __old_size = this->__size_;
  2209. this->__size_ += __n;
  2210. if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
  2211. {
  2212. if (this->__size_ <= __bits_per_word)
  2213. this->__begin_[0] = __storage_type(0);
  2214. else
  2215. this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
  2216. }
  2217. _VSTD::fill_n(__make_iter(__old_size), __n, __x);
  2218. }
  2219. template <class _Allocator>
  2220. template <class _ForwardIterator>
  2221. typename enable_if
  2222. <
  2223. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  2224. void
  2225. >::type
  2226. vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last)
  2227. {
  2228. size_type __old_size = this->__size_;
  2229. this->__size_ += _VSTD::distance(__first, __last);
  2230. if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word))
  2231. {
  2232. if (this->__size_ <= __bits_per_word)
  2233. this->__begin_[0] = __storage_type(0);
  2234. else
  2235. this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0);
  2236. }
  2237. _VSTD::copy(__first, __last, __make_iter(__old_size));
  2238. }
  2239. template <class _Allocator>
  2240. inline _LIBCPP_INLINE_VISIBILITY
  2241. vector<bool, _Allocator>::vector()
  2242. _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
  2243. : __begin_(nullptr),
  2244. __size_(0),
  2245. __cap_alloc_(0, __default_init_tag())
  2246. {
  2247. }
  2248. template <class _Allocator>
  2249. inline _LIBCPP_INLINE_VISIBILITY
  2250. vector<bool, _Allocator>::vector(const allocator_type& __a)
  2251. #if _LIBCPP_STD_VER <= 14
  2252. _NOEXCEPT_(is_nothrow_copy_constructible<allocator_type>::value)
  2253. #else
  2254. _NOEXCEPT
  2255. #endif
  2256. : __begin_(nullptr),
  2257. __size_(0),
  2258. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2259. {
  2260. }
  2261. template <class _Allocator>
  2262. vector<bool, _Allocator>::vector(size_type __n)
  2263. : __begin_(nullptr),
  2264. __size_(0),
  2265. __cap_alloc_(0, __default_init_tag())
  2266. {
  2267. if (__n > 0)
  2268. {
  2269. __vallocate(__n);
  2270. __construct_at_end(__n, false);
  2271. }
  2272. }
  2273. #if _LIBCPP_STD_VER > 11
  2274. template <class _Allocator>
  2275. vector<bool, _Allocator>::vector(size_type __n, const allocator_type& __a)
  2276. : __begin_(nullptr),
  2277. __size_(0),
  2278. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2279. {
  2280. if (__n > 0)
  2281. {
  2282. __vallocate(__n);
  2283. __construct_at_end(__n, false);
  2284. }
  2285. }
  2286. #endif
  2287. template <class _Allocator>
  2288. vector<bool, _Allocator>::vector(size_type __n, const value_type& __x)
  2289. : __begin_(nullptr),
  2290. __size_(0),
  2291. __cap_alloc_(0, __default_init_tag())
  2292. {
  2293. if (__n > 0)
  2294. {
  2295. __vallocate(__n);
  2296. __construct_at_end(__n, __x);
  2297. }
  2298. }
  2299. template <class _Allocator>
  2300. vector<bool, _Allocator>::vector(size_type __n, const value_type& __x, const allocator_type& __a)
  2301. : __begin_(nullptr),
  2302. __size_(0),
  2303. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2304. {
  2305. if (__n > 0)
  2306. {
  2307. __vallocate(__n);
  2308. __construct_at_end(__n, __x);
  2309. }
  2310. }
  2311. template <class _Allocator>
  2312. template <class _InputIterator>
  2313. vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last,
  2314. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type*)
  2315. : __begin_(nullptr),
  2316. __size_(0),
  2317. __cap_alloc_(0, __default_init_tag())
  2318. {
  2319. #ifndef _LIBCPP_NO_EXCEPTIONS
  2320. try
  2321. {
  2322. #endif // _LIBCPP_NO_EXCEPTIONS
  2323. for (; __first != __last; ++__first)
  2324. push_back(*__first);
  2325. #ifndef _LIBCPP_NO_EXCEPTIONS
  2326. }
  2327. catch (...)
  2328. {
  2329. if (__begin_ != nullptr)
  2330. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2331. std::__debug_db_invalidate_all(this);
  2332. throw;
  2333. }
  2334. #endif // _LIBCPP_NO_EXCEPTIONS
  2335. }
  2336. template <class _Allocator>
  2337. template <class _InputIterator>
  2338. vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a,
  2339. typename enable_if<__is_exactly_cpp17_input_iterator<_InputIterator>::value>::type*)
  2340. : __begin_(nullptr),
  2341. __size_(0),
  2342. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2343. {
  2344. #ifndef _LIBCPP_NO_EXCEPTIONS
  2345. try
  2346. {
  2347. #endif // _LIBCPP_NO_EXCEPTIONS
  2348. for (; __first != __last; ++__first)
  2349. push_back(*__first);
  2350. #ifndef _LIBCPP_NO_EXCEPTIONS
  2351. }
  2352. catch (...)
  2353. {
  2354. if (__begin_ != nullptr)
  2355. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2356. std::__debug_db_invalidate_all(this);
  2357. throw;
  2358. }
  2359. #endif // _LIBCPP_NO_EXCEPTIONS
  2360. }
  2361. template <class _Allocator>
  2362. template <class _ForwardIterator>
  2363. vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last,
  2364. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
  2365. : __begin_(nullptr),
  2366. __size_(0),
  2367. __cap_alloc_(0, __default_init_tag())
  2368. {
  2369. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  2370. if (__n > 0)
  2371. {
  2372. __vallocate(__n);
  2373. __construct_at_end(__first, __last);
  2374. }
  2375. }
  2376. template <class _Allocator>
  2377. template <class _ForwardIterator>
  2378. vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a,
  2379. typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type*)
  2380. : __begin_(nullptr),
  2381. __size_(0),
  2382. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2383. {
  2384. size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
  2385. if (__n > 0)
  2386. {
  2387. __vallocate(__n);
  2388. __construct_at_end(__first, __last);
  2389. }
  2390. }
  2391. #ifndef _LIBCPP_CXX03_LANG
  2392. template <class _Allocator>
  2393. vector<bool, _Allocator>::vector(initializer_list<value_type> __il)
  2394. : __begin_(nullptr),
  2395. __size_(0),
  2396. __cap_alloc_(0, __default_init_tag())
  2397. {
  2398. size_type __n = static_cast<size_type>(__il.size());
  2399. if (__n > 0)
  2400. {
  2401. __vallocate(__n);
  2402. __construct_at_end(__il.begin(), __il.end());
  2403. }
  2404. }
  2405. template <class _Allocator>
  2406. vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const allocator_type& __a)
  2407. : __begin_(nullptr),
  2408. __size_(0),
  2409. __cap_alloc_(0, static_cast<__storage_allocator>(__a))
  2410. {
  2411. size_type __n = static_cast<size_type>(__il.size());
  2412. if (__n > 0)
  2413. {
  2414. __vallocate(__n);
  2415. __construct_at_end(__il.begin(), __il.end());
  2416. }
  2417. }
  2418. #endif // _LIBCPP_CXX03_LANG
  2419. template <class _Allocator>
  2420. vector<bool, _Allocator>::~vector()
  2421. {
  2422. if (__begin_ != nullptr)
  2423. __storage_traits::deallocate(__alloc(), __begin_, __cap());
  2424. std::__debug_db_invalidate_all(this);
  2425. }
  2426. template <class _Allocator>
  2427. vector<bool, _Allocator>::vector(const vector& __v)
  2428. : __begin_(nullptr),
  2429. __size_(0),
  2430. __cap_alloc_(0, __storage_traits::select_on_container_copy_construction(__v.__alloc()))
  2431. {
  2432. if (__v.size() > 0)
  2433. {
  2434. __vallocate(__v.size());
  2435. __construct_at_end(__v.begin(), __v.end());
  2436. }
  2437. }
  2438. template <class _Allocator>
  2439. vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a)
  2440. : __begin_(nullptr),
  2441. __size_(0),
  2442. __cap_alloc_(0, __a)
  2443. {
  2444. if (__v.size() > 0)
  2445. {
  2446. __vallocate(__v.size());
  2447. __construct_at_end(__v.begin(), __v.end());
  2448. }
  2449. }
  2450. template <class _Allocator>
  2451. vector<bool, _Allocator>&
  2452. vector<bool, _Allocator>::operator=(const vector& __v)
  2453. {
  2454. if (this != _VSTD::addressof(__v))
  2455. {
  2456. __copy_assign_alloc(__v);
  2457. if (__v.__size_)
  2458. {
  2459. if (__v.__size_ > capacity())
  2460. {
  2461. __vdeallocate();
  2462. __vallocate(__v.__size_);
  2463. }
  2464. _VSTD::copy(__v.__begin_, __v.__begin_ + __external_cap_to_internal(__v.__size_), __begin_);
  2465. }
  2466. __size_ = __v.__size_;
  2467. }
  2468. return *this;
  2469. }
  2470. template <class _Allocator>
  2471. inline _LIBCPP_INLINE_VISIBILITY vector<bool, _Allocator>::vector(vector&& __v)
  2472. #if _LIBCPP_STD_VER > 14
  2473. _NOEXCEPT
  2474. #else
  2475. _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
  2476. #endif
  2477. : __begin_(__v.__begin_),
  2478. __size_(__v.__size_),
  2479. __cap_alloc_(_VSTD::move(__v.__cap_alloc_)) {
  2480. __v.__begin_ = nullptr;
  2481. __v.__size_ = 0;
  2482. __v.__cap() = 0;
  2483. }
  2484. template <class _Allocator>
  2485. vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator_type>& __a)
  2486. : __begin_(nullptr),
  2487. __size_(0),
  2488. __cap_alloc_(0, __a)
  2489. {
  2490. if (__a == allocator_type(__v.__alloc()))
  2491. {
  2492. this->__begin_ = __v.__begin_;
  2493. this->__size_ = __v.__size_;
  2494. this->__cap() = __v.__cap();
  2495. __v.__begin_ = nullptr;
  2496. __v.__cap() = __v.__size_ = 0;
  2497. }
  2498. else if (__v.size() > 0)
  2499. {
  2500. __vallocate(__v.size());
  2501. __construct_at_end(__v.begin(), __v.end());
  2502. }
  2503. }
  2504. template <class _Allocator>
  2505. inline _LIBCPP_INLINE_VISIBILITY
  2506. vector<bool, _Allocator>&
  2507. vector<bool, _Allocator>::operator=(vector&& __v)
  2508. _NOEXCEPT_((__noexcept_move_assign_container<_Allocator, __alloc_traits>::value))
  2509. {
  2510. __move_assign(__v, integral_constant<bool,
  2511. __storage_traits::propagate_on_container_move_assignment::value>());
  2512. return *this;
  2513. }
  2514. template <class _Allocator>
  2515. void
  2516. vector<bool, _Allocator>::__move_assign(vector& __c, false_type)
  2517. {
  2518. if (__alloc() != __c.__alloc())
  2519. assign(__c.begin(), __c.end());
  2520. else
  2521. __move_assign(__c, true_type());
  2522. }
  2523. template <class _Allocator>
  2524. void
  2525. vector<bool, _Allocator>::__move_assign(vector& __c, true_type)
  2526. _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
  2527. {
  2528. __vdeallocate();
  2529. __move_assign_alloc(__c);
  2530. this->__begin_ = __c.__begin_;
  2531. this->__size_ = __c.__size_;
  2532. this->__cap() = __c.__cap();
  2533. __c.__begin_ = nullptr;
  2534. __c.__cap() = __c.__size_ = 0;
  2535. }
  2536. template <class _Allocator>
  2537. void
  2538. vector<bool, _Allocator>::assign(size_type __n, const value_type& __x)
  2539. {
  2540. __size_ = 0;
  2541. if (__n > 0)
  2542. {
  2543. size_type __c = capacity();
  2544. if (__n <= __c)
  2545. __size_ = __n;
  2546. else
  2547. {
  2548. vector __v(get_allocator());
  2549. __v.reserve(__recommend(__n));
  2550. __v.__size_ = __n;
  2551. swap(__v);
  2552. }
  2553. _VSTD::fill_n(begin(), __n, __x);
  2554. }
  2555. std::__debug_db_invalidate_all(this);
  2556. }
  2557. template <class _Allocator>
  2558. template <class _InputIterator>
  2559. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value,
  2560. void
  2561. >::type
  2562. vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
  2563. {
  2564. clear();
  2565. for (; __first != __last; ++__first)
  2566. push_back(*__first);
  2567. }
  2568. template <class _Allocator>
  2569. template <class _ForwardIterator>
  2570. typename enable_if
  2571. <
  2572. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  2573. void
  2574. >::type
  2575. vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
  2576. {
  2577. clear();
  2578. difference_type __ns = _VSTD::distance(__first, __last);
  2579. _LIBCPP_ASSERT(__ns >= 0, "invalid range specified");
  2580. const size_t __n = static_cast<size_type>(__ns);
  2581. if (__n)
  2582. {
  2583. if (__n > capacity())
  2584. {
  2585. __vdeallocate();
  2586. __vallocate(__n);
  2587. }
  2588. __construct_at_end(__first, __last);
  2589. }
  2590. }
  2591. template <class _Allocator>
  2592. void
  2593. vector<bool, _Allocator>::reserve(size_type __n)
  2594. {
  2595. if (__n > capacity())
  2596. {
  2597. if (__n > max_size())
  2598. this->__throw_length_error();
  2599. vector __v(this->get_allocator());
  2600. __v.__vallocate(__n);
  2601. __v.__construct_at_end(this->begin(), this->end());
  2602. swap(__v);
  2603. std::__debug_db_invalidate_all(this);
  2604. }
  2605. }
  2606. template <class _Allocator>
  2607. void
  2608. vector<bool, _Allocator>::shrink_to_fit() _NOEXCEPT
  2609. {
  2610. if (__external_cap_to_internal(size()) > __cap())
  2611. {
  2612. #ifndef _LIBCPP_NO_EXCEPTIONS
  2613. try
  2614. {
  2615. #endif // _LIBCPP_NO_EXCEPTIONS
  2616. vector(*this, allocator_type(__alloc())).swap(*this);
  2617. #ifndef _LIBCPP_NO_EXCEPTIONS
  2618. }
  2619. catch (...)
  2620. {
  2621. }
  2622. #endif // _LIBCPP_NO_EXCEPTIONS
  2623. }
  2624. }
  2625. template <class _Allocator>
  2626. typename vector<bool, _Allocator>::reference
  2627. vector<bool, _Allocator>::at(size_type __n)
  2628. {
  2629. if (__n >= size())
  2630. this->__throw_out_of_range();
  2631. return (*this)[__n];
  2632. }
  2633. template <class _Allocator>
  2634. typename vector<bool, _Allocator>::const_reference
  2635. vector<bool, _Allocator>::at(size_type __n) const
  2636. {
  2637. if (__n >= size())
  2638. this->__throw_out_of_range();
  2639. return (*this)[__n];
  2640. }
  2641. template <class _Allocator>
  2642. void
  2643. vector<bool, _Allocator>::push_back(const value_type& __x)
  2644. {
  2645. if (this->__size_ == this->capacity())
  2646. reserve(__recommend(this->__size_ + 1));
  2647. ++this->__size_;
  2648. back() = __x;
  2649. }
  2650. template <class _Allocator>
  2651. typename vector<bool, _Allocator>::iterator
  2652. vector<bool, _Allocator>::insert(const_iterator __position, const value_type& __x)
  2653. {
  2654. iterator __r;
  2655. if (size() < capacity())
  2656. {
  2657. const_iterator __old_end = end();
  2658. ++__size_;
  2659. _VSTD::copy_backward(__position, __old_end, end());
  2660. __r = __const_iterator_cast(__position);
  2661. }
  2662. else
  2663. {
  2664. vector __v(get_allocator());
  2665. __v.reserve(__recommend(__size_ + 1));
  2666. __v.__size_ = __size_ + 1;
  2667. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  2668. _VSTD::copy_backward(__position, cend(), __v.end());
  2669. swap(__v);
  2670. }
  2671. *__r = __x;
  2672. return __r;
  2673. }
  2674. template <class _Allocator>
  2675. typename vector<bool, _Allocator>::iterator
  2676. vector<bool, _Allocator>::insert(const_iterator __position, size_type __n, const value_type& __x)
  2677. {
  2678. iterator __r;
  2679. size_type __c = capacity();
  2680. if (__n <= __c && size() <= __c - __n)
  2681. {
  2682. const_iterator __old_end = end();
  2683. __size_ += __n;
  2684. _VSTD::copy_backward(__position, __old_end, end());
  2685. __r = __const_iterator_cast(__position);
  2686. }
  2687. else
  2688. {
  2689. vector __v(get_allocator());
  2690. __v.reserve(__recommend(__size_ + __n));
  2691. __v.__size_ = __size_ + __n;
  2692. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  2693. _VSTD::copy_backward(__position, cend(), __v.end());
  2694. swap(__v);
  2695. }
  2696. _VSTD::fill_n(__r, __n, __x);
  2697. return __r;
  2698. }
  2699. template <class _Allocator>
  2700. template <class _InputIterator>
  2701. typename enable_if <__is_exactly_cpp17_input_iterator<_InputIterator>::value,
  2702. typename vector<bool, _Allocator>::iterator
  2703. >::type
  2704. vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last)
  2705. {
  2706. difference_type __off = __position - begin();
  2707. iterator __p = __const_iterator_cast(__position);
  2708. iterator __old_end = end();
  2709. for (; size() != capacity() && __first != __last; ++__first)
  2710. {
  2711. ++this->__size_;
  2712. back() = *__first;
  2713. }
  2714. vector __v(get_allocator());
  2715. if (__first != __last)
  2716. {
  2717. #ifndef _LIBCPP_NO_EXCEPTIONS
  2718. try
  2719. {
  2720. #endif // _LIBCPP_NO_EXCEPTIONS
  2721. __v.assign(__first, __last);
  2722. difference_type __old_size = static_cast<difference_type>(__old_end - begin());
  2723. difference_type __old_p = __p - begin();
  2724. reserve(__recommend(size() + __v.size()));
  2725. __p = begin() + __old_p;
  2726. __old_end = begin() + __old_size;
  2727. #ifndef _LIBCPP_NO_EXCEPTIONS
  2728. }
  2729. catch (...)
  2730. {
  2731. erase(__old_end, end());
  2732. throw;
  2733. }
  2734. #endif // _LIBCPP_NO_EXCEPTIONS
  2735. }
  2736. __p = _VSTD::rotate(__p, __old_end, end());
  2737. insert(__p, __v.begin(), __v.end());
  2738. return begin() + __off;
  2739. }
  2740. template <class _Allocator>
  2741. template <class _ForwardIterator>
  2742. typename enable_if
  2743. <
  2744. __is_cpp17_forward_iterator<_ForwardIterator>::value,
  2745. typename vector<bool, _Allocator>::iterator
  2746. >::type
  2747. vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last)
  2748. {
  2749. const difference_type __n_signed = _VSTD::distance(__first, __last);
  2750. _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified");
  2751. const size_type __n = static_cast<size_type>(__n_signed);
  2752. iterator __r;
  2753. size_type __c = capacity();
  2754. if (__n <= __c && size() <= __c - __n)
  2755. {
  2756. const_iterator __old_end = end();
  2757. __size_ += __n;
  2758. _VSTD::copy_backward(__position, __old_end, end());
  2759. __r = __const_iterator_cast(__position);
  2760. }
  2761. else
  2762. {
  2763. vector __v(get_allocator());
  2764. __v.reserve(__recommend(__size_ + __n));
  2765. __v.__size_ = __size_ + __n;
  2766. __r = _VSTD::copy(cbegin(), __position, __v.begin());
  2767. _VSTD::copy_backward(__position, cend(), __v.end());
  2768. swap(__v);
  2769. }
  2770. _VSTD::copy(__first, __last, __r);
  2771. return __r;
  2772. }
  2773. template <class _Allocator>
  2774. inline _LIBCPP_INLINE_VISIBILITY
  2775. typename vector<bool, _Allocator>::iterator
  2776. vector<bool, _Allocator>::erase(const_iterator __position)
  2777. {
  2778. iterator __r = __const_iterator_cast(__position);
  2779. _VSTD::copy(__position + 1, this->cend(), __r);
  2780. --__size_;
  2781. return __r;
  2782. }
  2783. template <class _Allocator>
  2784. typename vector<bool, _Allocator>::iterator
  2785. vector<bool, _Allocator>::erase(const_iterator __first, const_iterator __last)
  2786. {
  2787. iterator __r = __const_iterator_cast(__first);
  2788. difference_type __d = __last - __first;
  2789. _VSTD::copy(__last, this->cend(), __r);
  2790. __size_ -= __d;
  2791. return __r;
  2792. }
  2793. template <class _Allocator>
  2794. void
  2795. vector<bool, _Allocator>::swap(vector& __x)
  2796. #if _LIBCPP_STD_VER >= 14
  2797. _NOEXCEPT
  2798. #else
  2799. _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
  2800. __is_nothrow_swappable<allocator_type>::value)
  2801. #endif
  2802. {
  2803. _VSTD::swap(this->__begin_, __x.__begin_);
  2804. _VSTD::swap(this->__size_, __x.__size_);
  2805. _VSTD::swap(this->__cap(), __x.__cap());
  2806. _VSTD::__swap_allocator(this->__alloc(), __x.__alloc(),
  2807. integral_constant<bool, __alloc_traits::propagate_on_container_swap::value>());
  2808. }
  2809. template <class _Allocator>
  2810. void
  2811. vector<bool, _Allocator>::resize(size_type __sz, value_type __x)
  2812. {
  2813. size_type __cs = size();
  2814. if (__cs < __sz)
  2815. {
  2816. iterator __r;
  2817. size_type __c = capacity();
  2818. size_type __n = __sz - __cs;
  2819. if (__n <= __c && __cs <= __c - __n)
  2820. {
  2821. __r = end();
  2822. __size_ += __n;
  2823. }
  2824. else
  2825. {
  2826. vector __v(get_allocator());
  2827. __v.reserve(__recommend(__size_ + __n));
  2828. __v.__size_ = __size_ + __n;
  2829. __r = _VSTD::copy(cbegin(), cend(), __v.begin());
  2830. swap(__v);
  2831. }
  2832. _VSTD::fill_n(__r, __n, __x);
  2833. }
  2834. else
  2835. __size_ = __sz;
  2836. }
  2837. template <class _Allocator>
  2838. void
  2839. vector<bool, _Allocator>::flip() _NOEXCEPT
  2840. {
  2841. // do middle whole words
  2842. size_type __n = __size_;
  2843. __storage_pointer __p = __begin_;
  2844. for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
  2845. *__p = ~*__p;
  2846. // do last partial word
  2847. if (__n > 0)
  2848. {
  2849. __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
  2850. __storage_type __b = *__p & __m;
  2851. *__p &= ~__m;
  2852. *__p |= ~__b & __m;
  2853. }
  2854. }
  2855. template <class _Allocator>
  2856. bool
  2857. vector<bool, _Allocator>::__invariants() const
  2858. {
  2859. if (this->__begin_ == nullptr)
  2860. {
  2861. if (this->__size_ != 0 || this->__cap() != 0)
  2862. return false;
  2863. }
  2864. else
  2865. {
  2866. if (this->__cap() == 0)
  2867. return false;
  2868. if (this->__size_ > this->capacity())
  2869. return false;
  2870. }
  2871. return true;
  2872. }
  2873. template <class _Allocator>
  2874. size_t
  2875. vector<bool, _Allocator>::__hash_code() const _NOEXCEPT
  2876. {
  2877. size_t __h = 0;
  2878. // do middle whole words
  2879. size_type __n = __size_;
  2880. __storage_pointer __p = __begin_;
  2881. for (; __n >= __bits_per_word; ++__p, __n -= __bits_per_word)
  2882. __h ^= *__p;
  2883. // do last partial word
  2884. if (__n > 0)
  2885. {
  2886. const __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n);
  2887. __h ^= *__p & __m;
  2888. }
  2889. return __h;
  2890. }
  2891. template <class _Allocator>
  2892. struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
  2893. : public __unary_function<vector<bool, _Allocator>, size_t>
  2894. {
  2895. _LIBCPP_INLINE_VISIBILITY
  2896. size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
  2897. {return __vec.__hash_code();}
  2898. };
  2899. #else // _YNDX_LIBCXX_ENABLE_VECTOR_BOOL_COMPRESSION
  2900. // Hash function implementation for uncompressed std::vector<bool> which returns the same result.
  2901. template <class _Allocator>
  2902. struct _LIBCPP_TEMPLATE_VIS hash<vector<bool, _Allocator> >
  2903. : public unary_function<vector<bool, _Allocator>, size_t>
  2904. {
  2905. _LIBCPP_INLINE_VISIBILITY
  2906. size_t operator()(const vector<bool, _Allocator>& __vec) const _NOEXCEPT
  2907. {
  2908. size_t __h = 0;
  2909. size_t __idx = 0;
  2910. size_t __n = __vec.size();
  2911. constexpr size_t __bits_per_word = sizeof(typename allocator_traits<_Allocator>::size_type) * CHAR_BIT;
  2912. static_assert(sizeof(typename allocator_traits<_Allocator>::size_type) <= sizeof(size_t), "size_type constraint violated");
  2913. for (;__idx + __bits_per_word <= __n;) {
  2914. for (size_t __bit = 0; __bit < __bits_per_word; __bit++, __idx++) {
  2915. __h ^= static_cast<size_t>(__vec[__idx]) << __bit;
  2916. }
  2917. }
  2918. for (size_t __bit = 0; __idx < __n; __bit++, __idx++) {
  2919. __h ^= static_cast<size_t>(__vec[__idx]) << __bit;
  2920. }
  2921. return __h;
  2922. }
  2923. };
  2924. #endif // _YNDX_LIBCXX_ENABLE_VECTOR_BOOL_COMPRESSION
  2925. template <class _Tp, class _Allocator>
  2926. inline _LIBCPP_INLINE_VISIBILITY
  2927. bool
  2928. operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2929. {
  2930. const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
  2931. return __sz == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
  2932. }
  2933. template <class _Tp, class _Allocator>
  2934. inline _LIBCPP_INLINE_VISIBILITY
  2935. bool
  2936. operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2937. {
  2938. return !(__x == __y);
  2939. }
  2940. template <class _Tp, class _Allocator>
  2941. inline _LIBCPP_INLINE_VISIBILITY
  2942. bool
  2943. operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2944. {
  2945. return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
  2946. }
  2947. template <class _Tp, class _Allocator>
  2948. inline _LIBCPP_INLINE_VISIBILITY
  2949. bool
  2950. operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2951. {
  2952. return __y < __x;
  2953. }
  2954. template <class _Tp, class _Allocator>
  2955. inline _LIBCPP_INLINE_VISIBILITY
  2956. bool
  2957. operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2958. {
  2959. return !(__x < __y);
  2960. }
  2961. template <class _Tp, class _Allocator>
  2962. inline _LIBCPP_INLINE_VISIBILITY
  2963. bool
  2964. operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
  2965. {
  2966. return !(__y < __x);
  2967. }
  2968. template <class _Tp, class _Allocator>
  2969. inline _LIBCPP_INLINE_VISIBILITY
  2970. void
  2971. swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
  2972. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  2973. {
  2974. __x.swap(__y);
  2975. }
  2976. #if _LIBCPP_STD_VER > 17
  2977. template <class _Tp, class _Allocator, class _Up>
  2978. inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type
  2979. erase(vector<_Tp, _Allocator>& __c, const _Up& __v) {
  2980. auto __old_size = __c.size();
  2981. __c.erase(_VSTD::remove(__c.begin(), __c.end(), __v), __c.end());
  2982. return __old_size - __c.size();
  2983. }
  2984. template <class _Tp, class _Allocator, class _Predicate>
  2985. inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type
  2986. erase_if(vector<_Tp, _Allocator>& __c, _Predicate __pred) {
  2987. auto __old_size = __c.size();
  2988. __c.erase(_VSTD::remove_if(__c.begin(), __c.end(), __pred), __c.end());
  2989. return __old_size - __c.size();
  2990. }
  2991. template <>
  2992. inline constexpr bool __format::__enable_insertable<std::vector<char>> = true;
  2993. #ifndef _LIBCPP_HAS_NO_WIDE_CHARACTERS
  2994. template <>
  2995. inline constexpr bool __format::__enable_insertable<std::vector<wchar_t>> = true;
  2996. #endif
  2997. #endif // _LIBCPP_STD_VER > 17
  2998. _LIBCPP_END_NAMESPACE_STD
  2999. _LIBCPP_POP_MACROS
  3000. #endif // _LIBCPP_VECTOR