map 72 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893189418951896189718981899190019011902190319041905190619071908190919101911191219131914191519161917191819191920192119221923192419251926192719281929193019311932193319341935193619371938193919401941194219431944194519461947194819491950195119521953195419551956195719581959196019611962196319641965196619671968196919701971197219731974197519761977197819791980198119821983198419851986198719881989199019911992199319941995199619971998199920002001200220032004
  1. // -*- C++ -*-
  2. //===----------------------------- map ------------------------------------===//
  3. //
  4. // The LLVM Compiler Infrastructure
  5. //
  6. // This file is dual licensed under the MIT and the University of Illinois Open
  7. // Source Licenses. See LICENSE.TXT for details.
  8. //
  9. //===----------------------------------------------------------------------===//
  10. #ifndef _LIBCPP_MAP
  11. #define _LIBCPP_MAP
  12. /*
  13. map synopsis
  14. namespace std
  15. {
  16. template <class Key, class T, class Compare = less<Key>,
  17. class Allocator = allocator<pair<const Key, T>>>
  18. class map
  19. {
  20. public:
  21. // types:
  22. typedef Key key_type;
  23. typedef T mapped_type;
  24. typedef pair<const key_type, mapped_type> value_type;
  25. typedef Compare key_compare;
  26. typedef Allocator allocator_type;
  27. typedef typename allocator_type::reference reference;
  28. typedef typename allocator_type::const_reference const_reference;
  29. typedef typename allocator_type::pointer pointer;
  30. typedef typename allocator_type::const_pointer const_pointer;
  31. typedef typename allocator_type::size_type size_type;
  32. typedef typename allocator_type::difference_type difference_type;
  33. typedef implementation-defined iterator;
  34. typedef implementation-defined const_iterator;
  35. typedef std::reverse_iterator<iterator> reverse_iterator;
  36. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  37. class value_compare
  38. : public binary_function<value_type, value_type, bool>
  39. {
  40. friend class map;
  41. protected:
  42. key_compare comp;
  43. value_compare(key_compare c);
  44. public:
  45. bool operator()(const value_type& x, const value_type& y) const;
  46. };
  47. // construct/copy/destroy:
  48. map()
  49. noexcept(
  50. is_nothrow_default_constructible<allocator_type>::value &&
  51. is_nothrow_default_constructible<key_compare>::value &&
  52. is_nothrow_copy_constructible<key_compare>::value);
  53. explicit map(const key_compare& comp);
  54. map(const key_compare& comp, const allocator_type& a);
  55. template <class InputIterator>
  56. map(InputIterator first, InputIterator last,
  57. const key_compare& comp = key_compare());
  58. template <class InputIterator>
  59. map(InputIterator first, InputIterator last,
  60. const key_compare& comp, const allocator_type& a);
  61. map(const map& m);
  62. map(map&& m)
  63. noexcept(
  64. is_nothrow_move_constructible<allocator_type>::value &&
  65. is_nothrow_move_constructible<key_compare>::value);
  66. explicit map(const allocator_type& a);
  67. map(const map& m, const allocator_type& a);
  68. map(map&& m, const allocator_type& a);
  69. map(initializer_list<value_type> il, const key_compare& comp = key_compare());
  70. map(initializer_list<value_type> il, const key_compare& comp, const allocator_type& a);
  71. template <class InputIterator>
  72. map(InputIterator first, InputIterator last, const allocator_type& a)
  73. : map(first, last, Compare(), a) {} // C++14
  74. map(initializer_list<value_type> il, const allocator_type& a)
  75. : map(il, Compare(), a) {} // C++14
  76. ~map();
  77. map& operator=(const map& m);
  78. map& operator=(map&& m)
  79. noexcept(
  80. allocator_type::propagate_on_container_move_assignment::value &&
  81. is_nothrow_move_assignable<allocator_type>::value &&
  82. is_nothrow_move_assignable<key_compare>::value);
  83. map& operator=(initializer_list<value_type> il);
  84. // iterators:
  85. iterator begin() noexcept;
  86. const_iterator begin() const noexcept;
  87. iterator end() noexcept;
  88. const_iterator end() const noexcept;
  89. reverse_iterator rbegin() noexcept;
  90. const_reverse_iterator rbegin() const noexcept;
  91. reverse_iterator rend() noexcept;
  92. const_reverse_iterator rend() const noexcept;
  93. const_iterator cbegin() const noexcept;
  94. const_iterator cend() const noexcept;
  95. const_reverse_iterator crbegin() const noexcept;
  96. const_reverse_iterator crend() const noexcept;
  97. // capacity:
  98. bool empty() const noexcept;
  99. size_type size() const noexcept;
  100. size_type max_size() const noexcept;
  101. // element access:
  102. mapped_type& operator[](const key_type& k);
  103. mapped_type& operator[](key_type&& k);
  104. mapped_type& at(const key_type& k);
  105. const mapped_type& at(const key_type& k) const;
  106. // modifiers:
  107. template <class... Args>
  108. pair<iterator, bool> emplace(Args&&... args);
  109. template <class... Args>
  110. iterator emplace_hint(const_iterator position, Args&&... args);
  111. pair<iterator, bool> insert(const value_type& v);
  112. pair<iterator, bool> insert( value_type&& v); // C++17
  113. template <class P>
  114. pair<iterator, bool> insert(P&& p);
  115. iterator insert(const_iterator position, const value_type& v);
  116. iterator insert(const_iterator position, value_type&& v); // C++17
  117. template <class P>
  118. iterator insert(const_iterator position, P&& p);
  119. template <class InputIterator>
  120. void insert(InputIterator first, InputIterator last);
  121. void insert(initializer_list<value_type> il);
  122. template <class... Args>
  123. pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); // C++17
  124. template <class... Args>
  125. pair<iterator, bool> try_emplace(key_type&& k, Args&&... args); // C++17
  126. template <class... Args>
  127. iterator try_emplace(const_iterator hint, const key_type& k, Args&&... args); // C++17
  128. template <class... Args>
  129. iterator try_emplace(const_iterator hint, key_type&& k, Args&&... args); // C++17
  130. template <class M>
  131. pair<iterator, bool> insert_or_assign(const key_type& k, M&& obj); // C++17
  132. template <class M>
  133. pair<iterator, bool> insert_or_assign(key_type&& k, M&& obj); // C++17
  134. template <class M>
  135. iterator insert_or_assign(const_iterator hint, const key_type& k, M&& obj); // C++17
  136. template <class M>
  137. iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj); // C++17
  138. iterator erase(const_iterator position);
  139. iterator erase(iterator position); // C++14
  140. size_type erase(const key_type& k);
  141. iterator erase(const_iterator first, const_iterator last);
  142. void clear() noexcept;
  143. void swap(map& m)
  144. noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
  145. is_nothrow_swappable<key_compare>::value); // C++17
  146. // observers:
  147. allocator_type get_allocator() const noexcept;
  148. key_compare key_comp() const;
  149. value_compare value_comp() const;
  150. // map operations:
  151. iterator find(const key_type& k);
  152. const_iterator find(const key_type& k) const;
  153. template<typename K>
  154. iterator find(const K& x); // C++14
  155. template<typename K>
  156. const_iterator find(const K& x) const; // C++14
  157. template<typename K>
  158. size_type count(const K& x) const; // C++14
  159. size_type count(const key_type& k) const;
  160. iterator lower_bound(const key_type& k);
  161. const_iterator lower_bound(const key_type& k) const;
  162. template<typename K>
  163. iterator lower_bound(const K& x); // C++14
  164. template<typename K>
  165. const_iterator lower_bound(const K& x) const; // C++14
  166. iterator upper_bound(const key_type& k);
  167. const_iterator upper_bound(const key_type& k) const;
  168. template<typename K>
  169. iterator upper_bound(const K& x); // C++14
  170. template<typename K>
  171. const_iterator upper_bound(const K& x) const; // C++14
  172. pair<iterator,iterator> equal_range(const key_type& k);
  173. pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
  174. template<typename K>
  175. pair<iterator,iterator> equal_range(const K& x); // C++14
  176. template<typename K>
  177. pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
  178. };
  179. template <class Key, class T, class Compare, class Allocator>
  180. bool
  181. operator==(const map<Key, T, Compare, Allocator>& x,
  182. const map<Key, T, Compare, Allocator>& y);
  183. template <class Key, class T, class Compare, class Allocator>
  184. bool
  185. operator< (const map<Key, T, Compare, Allocator>& x,
  186. const map<Key, T, Compare, Allocator>& y);
  187. template <class Key, class T, class Compare, class Allocator>
  188. bool
  189. operator!=(const map<Key, T, Compare, Allocator>& x,
  190. const map<Key, T, Compare, Allocator>& y);
  191. template <class Key, class T, class Compare, class Allocator>
  192. bool
  193. operator> (const map<Key, T, Compare, Allocator>& x,
  194. const map<Key, T, Compare, Allocator>& y);
  195. template <class Key, class T, class Compare, class Allocator>
  196. bool
  197. operator>=(const map<Key, T, Compare, Allocator>& x,
  198. const map<Key, T, Compare, Allocator>& y);
  199. template <class Key, class T, class Compare, class Allocator>
  200. bool
  201. operator<=(const map<Key, T, Compare, Allocator>& x,
  202. const map<Key, T, Compare, Allocator>& y);
  203. // specialized algorithms:
  204. template <class Key, class T, class Compare, class Allocator>
  205. void
  206. swap(map<Key, T, Compare, Allocator>& x, map<Key, T, Compare, Allocator>& y)
  207. noexcept(noexcept(x.swap(y)));
  208. template <class Key, class T, class Compare = less<Key>,
  209. class Allocator = allocator<pair<const Key, T>>>
  210. class multimap
  211. {
  212. public:
  213. // types:
  214. typedef Key key_type;
  215. typedef T mapped_type;
  216. typedef pair<const key_type,mapped_type> value_type;
  217. typedef Compare key_compare;
  218. typedef Allocator allocator_type;
  219. typedef typename allocator_type::reference reference;
  220. typedef typename allocator_type::const_reference const_reference;
  221. typedef typename allocator_type::size_type size_type;
  222. typedef typename allocator_type::difference_type difference_type;
  223. typedef typename allocator_type::pointer pointer;
  224. typedef typename allocator_type::const_pointer const_pointer;
  225. typedef implementation-defined iterator;
  226. typedef implementation-defined const_iterator;
  227. typedef std::reverse_iterator<iterator> reverse_iterator;
  228. typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  229. class value_compare
  230. : public binary_function<value_type,value_type,bool>
  231. {
  232. friend class multimap;
  233. protected:
  234. key_compare comp;
  235. value_compare(key_compare c);
  236. public:
  237. bool operator()(const value_type& x, const value_type& y) const;
  238. };
  239. // construct/copy/destroy:
  240. multimap()
  241. noexcept(
  242. is_nothrow_default_constructible<allocator_type>::value &&
  243. is_nothrow_default_constructible<key_compare>::value &&
  244. is_nothrow_copy_constructible<key_compare>::value);
  245. explicit multimap(const key_compare& comp);
  246. multimap(const key_compare& comp, const allocator_type& a);
  247. template <class InputIterator>
  248. multimap(InputIterator first, InputIterator last, const key_compare& comp);
  249. template <class InputIterator>
  250. multimap(InputIterator first, InputIterator last, const key_compare& comp,
  251. const allocator_type& a);
  252. multimap(const multimap& m);
  253. multimap(multimap&& m)
  254. noexcept(
  255. is_nothrow_move_constructible<allocator_type>::value &&
  256. is_nothrow_move_constructible<key_compare>::value);
  257. explicit multimap(const allocator_type& a);
  258. multimap(const multimap& m, const allocator_type& a);
  259. multimap(multimap&& m, const allocator_type& a);
  260. multimap(initializer_list<value_type> il, const key_compare& comp = key_compare());
  261. multimap(initializer_list<value_type> il, const key_compare& comp,
  262. const allocator_type& a);
  263. template <class InputIterator>
  264. multimap(InputIterator first, InputIterator last, const allocator_type& a)
  265. : multimap(first, last, Compare(), a) {} // C++14
  266. multimap(initializer_list<value_type> il, const allocator_type& a)
  267. : multimap(il, Compare(), a) {} // C++14
  268. ~multimap();
  269. multimap& operator=(const multimap& m);
  270. multimap& operator=(multimap&& m)
  271. noexcept(
  272. allocator_type::propagate_on_container_move_assignment::value &&
  273. is_nothrow_move_assignable<allocator_type>::value &&
  274. is_nothrow_move_assignable<key_compare>::value);
  275. multimap& operator=(initializer_list<value_type> il);
  276. // iterators:
  277. iterator begin() noexcept;
  278. const_iterator begin() const noexcept;
  279. iterator end() noexcept;
  280. const_iterator end() const noexcept;
  281. reverse_iterator rbegin() noexcept;
  282. const_reverse_iterator rbegin() const noexcept;
  283. reverse_iterator rend() noexcept;
  284. const_reverse_iterator rend() const noexcept;
  285. const_iterator cbegin() const noexcept;
  286. const_iterator cend() const noexcept;
  287. const_reverse_iterator crbegin() const noexcept;
  288. const_reverse_iterator crend() const noexcept;
  289. // capacity:
  290. bool empty() const noexcept;
  291. size_type size() const noexcept;
  292. size_type max_size() const noexcept;
  293. // modifiers:
  294. template <class... Args>
  295. iterator emplace(Args&&... args);
  296. template <class... Args>
  297. iterator emplace_hint(const_iterator position, Args&&... args);
  298. iterator insert(const value_type& v);
  299. iterator insert( value_type&& v); // C++17
  300. template <class P>
  301. iterator insert(P&& p);
  302. iterator insert(const_iterator position, const value_type& v);
  303. iterator insert(const_iterator position, value_type&& v); // C++17
  304. template <class P>
  305. iterator insert(const_iterator position, P&& p);
  306. template <class InputIterator>
  307. void insert(InputIterator first, InputIterator last);
  308. void insert(initializer_list<value_type> il);
  309. iterator erase(const_iterator position);
  310. iterator erase(iterator position); // C++14
  311. size_type erase(const key_type& k);
  312. iterator erase(const_iterator first, const_iterator last);
  313. void clear() noexcept;
  314. void swap(multimap& m)
  315. noexcept(allocator_traits<allocator_type>::is_always_equal::value &&
  316. is_nothrow_swappable<key_compare>::value); // C++17
  317. // observers:
  318. allocator_type get_allocator() const noexcept;
  319. key_compare key_comp() const;
  320. value_compare value_comp() const;
  321. // map operations:
  322. iterator find(const key_type& k);
  323. const_iterator find(const key_type& k) const;
  324. template<typename K>
  325. iterator find(const K& x); // C++14
  326. template<typename K>
  327. const_iterator find(const K& x) const; // C++14
  328. template<typename K>
  329. size_type count(const K& x) const; // C++14
  330. size_type count(const key_type& k) const;
  331. iterator lower_bound(const key_type& k);
  332. const_iterator lower_bound(const key_type& k) const;
  333. template<typename K>
  334. iterator lower_bound(const K& x); // C++14
  335. template<typename K>
  336. const_iterator lower_bound(const K& x) const; // C++14
  337. iterator upper_bound(const key_type& k);
  338. const_iterator upper_bound(const key_type& k) const;
  339. template<typename K>
  340. iterator upper_bound(const K& x); // C++14
  341. template<typename K>
  342. const_iterator upper_bound(const K& x) const; // C++14
  343. pair<iterator,iterator> equal_range(const key_type& k);
  344. pair<const_iterator,const_iterator> equal_range(const key_type& k) const;
  345. template<typename K>
  346. pair<iterator,iterator> equal_range(const K& x); // C++14
  347. template<typename K>
  348. pair<const_iterator,const_iterator> equal_range(const K& x) const; // C++14
  349. };
  350. template <class Key, class T, class Compare, class Allocator>
  351. bool
  352. operator==(const multimap<Key, T, Compare, Allocator>& x,
  353. const multimap<Key, T, Compare, Allocator>& y);
  354. template <class Key, class T, class Compare, class Allocator>
  355. bool
  356. operator< (const multimap<Key, T, Compare, Allocator>& x,
  357. const multimap<Key, T, Compare, Allocator>& y);
  358. template <class Key, class T, class Compare, class Allocator>
  359. bool
  360. operator!=(const multimap<Key, T, Compare, Allocator>& x,
  361. const multimap<Key, T, Compare, Allocator>& y);
  362. template <class Key, class T, class Compare, class Allocator>
  363. bool
  364. operator> (const multimap<Key, T, Compare, Allocator>& x,
  365. const multimap<Key, T, Compare, Allocator>& y);
  366. template <class Key, class T, class Compare, class Allocator>
  367. bool
  368. operator>=(const multimap<Key, T, Compare, Allocator>& x,
  369. const multimap<Key, T, Compare, Allocator>& y);
  370. template <class Key, class T, class Compare, class Allocator>
  371. bool
  372. operator<=(const multimap<Key, T, Compare, Allocator>& x,
  373. const multimap<Key, T, Compare, Allocator>& y);
  374. // specialized algorithms:
  375. template <class Key, class T, class Compare, class Allocator>
  376. void
  377. swap(multimap<Key, T, Compare, Allocator>& x,
  378. multimap<Key, T, Compare, Allocator>& y)
  379. noexcept(noexcept(x.swap(y)));
  380. } // std
  381. */
  382. #include <__config>
  383. #include <__tree>
  384. #include <iterator>
  385. #include <memory>
  386. #include <utility>
  387. #include <functional>
  388. #include <initializer_list>
  389. #include <type_traits>
  390. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  391. #pragma GCC system_header
  392. #endif
  393. _LIBCPP_BEGIN_NAMESPACE_STD
  394. template <class _Key, class _CP, class _Compare,
  395. bool = is_empty<_Compare>::value && !__libcpp_is_final<_Compare>::value
  396. >
  397. class __map_value_compare
  398. : private _Compare
  399. {
  400. public:
  401. _LIBCPP_INLINE_VISIBILITY
  402. __map_value_compare()
  403. _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
  404. : _Compare() {}
  405. _LIBCPP_INLINE_VISIBILITY
  406. __map_value_compare(_Compare c)
  407. _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
  408. : _Compare(c) {}
  409. _LIBCPP_INLINE_VISIBILITY
  410. const _Compare& key_comp() const _NOEXCEPT {return *this;}
  411. _LIBCPP_INLINE_VISIBILITY
  412. bool operator()(const _CP& __x, const _CP& __y) const
  413. {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y.__cc.first);}
  414. _LIBCPP_INLINE_VISIBILITY
  415. bool operator()(const _CP& __x, const _Key& __y) const
  416. {return static_cast<const _Compare&>(*this)(__x.__cc.first, __y);}
  417. _LIBCPP_INLINE_VISIBILITY
  418. bool operator()(const _Key& __x, const _CP& __y) const
  419. {return static_cast<const _Compare&>(*this)(__x, __y.__cc.first);}
  420. void swap(__map_value_compare&__y)
  421. _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
  422. {
  423. using _VSTD::swap;
  424. swap(static_cast<const _Compare&>(*this), static_cast<const _Compare&>(__y));
  425. }
  426. #if _LIBCPP_STD_VER > 11
  427. template <typename _K2>
  428. _LIBCPP_INLINE_VISIBILITY
  429. typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
  430. operator () ( const _K2& __x, const _CP& __y ) const
  431. {return static_cast<const _Compare&>(*this) (__x, __y.__cc.first);}
  432. template <typename _K2>
  433. _LIBCPP_INLINE_VISIBILITY
  434. typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
  435. operator () (const _CP& __x, const _K2& __y) const
  436. {return static_cast<const _Compare&>(*this) (__x.__cc.first, __y);}
  437. #endif
  438. };
  439. template <class _Key, class _CP, class _Compare>
  440. class __map_value_compare<_Key, _CP, _Compare, false>
  441. {
  442. _Compare comp;
  443. public:
  444. _LIBCPP_INLINE_VISIBILITY
  445. __map_value_compare()
  446. _NOEXCEPT_(is_nothrow_default_constructible<_Compare>::value)
  447. : comp() {}
  448. _LIBCPP_INLINE_VISIBILITY
  449. __map_value_compare(_Compare c)
  450. _NOEXCEPT_(is_nothrow_copy_constructible<_Compare>::value)
  451. : comp(c) {}
  452. _LIBCPP_INLINE_VISIBILITY
  453. const _Compare& key_comp() const _NOEXCEPT {return comp;}
  454. _LIBCPP_INLINE_VISIBILITY
  455. bool operator()(const _CP& __x, const _CP& __y) const
  456. {return comp(__x.__cc.first, __y.__cc.first);}
  457. _LIBCPP_INLINE_VISIBILITY
  458. bool operator()(const _CP& __x, const _Key& __y) const
  459. {return comp(__x.__cc.first, __y);}
  460. _LIBCPP_INLINE_VISIBILITY
  461. bool operator()(const _Key& __x, const _CP& __y) const
  462. {return comp(__x, __y.__cc.first);}
  463. void swap(__map_value_compare&__y)
  464. _NOEXCEPT_(__is_nothrow_swappable<_Compare>::value)
  465. {
  466. using _VSTD::swap;
  467. swap(comp, __y.comp);
  468. }
  469. #if _LIBCPP_STD_VER > 11
  470. template <typename _K2>
  471. _LIBCPP_INLINE_VISIBILITY
  472. typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
  473. operator () ( const _K2& __x, const _CP& __y ) const
  474. {return comp (__x, __y.__cc.first);}
  475. template <typename _K2>
  476. _LIBCPP_INLINE_VISIBILITY
  477. typename enable_if<__is_transparent<_Compare, _K2>::value, bool>::type
  478. operator () (const _CP& __x, const _K2& __y) const
  479. {return comp (__x.__cc.first, __y);}
  480. #endif
  481. };
  482. template <class _Key, class _CP, class _Compare, bool __b>
  483. inline _LIBCPP_INLINE_VISIBILITY
  484. void
  485. swap(__map_value_compare<_Key, _CP, _Compare, __b>& __x,
  486. __map_value_compare<_Key, _CP, _Compare, __b>& __y)
  487. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  488. {
  489. __x.swap(__y);
  490. }
  491. template <class _Allocator>
  492. class __map_node_destructor
  493. {
  494. typedef _Allocator allocator_type;
  495. typedef allocator_traits<allocator_type> __alloc_traits;
  496. public:
  497. typedef typename __alloc_traits::pointer pointer;
  498. private:
  499. allocator_type& __na_;
  500. __map_node_destructor& operator=(const __map_node_destructor&);
  501. public:
  502. bool __first_constructed;
  503. bool __second_constructed;
  504. _LIBCPP_INLINE_VISIBILITY
  505. explicit __map_node_destructor(allocator_type& __na) _NOEXCEPT
  506. : __na_(__na),
  507. __first_constructed(false),
  508. __second_constructed(false)
  509. {}
  510. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  511. _LIBCPP_INLINE_VISIBILITY
  512. __map_node_destructor(__tree_node_destructor<allocator_type>&& __x) _NOEXCEPT
  513. : __na_(__x.__na_),
  514. __first_constructed(__x.__value_constructed),
  515. __second_constructed(__x.__value_constructed)
  516. {
  517. __x.__value_constructed = false;
  518. }
  519. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  520. _LIBCPP_INLINE_VISIBILITY
  521. void operator()(pointer __p) _NOEXCEPT
  522. {
  523. if (__second_constructed)
  524. __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.second));
  525. if (__first_constructed)
  526. __alloc_traits::destroy(__na_, _VSTD::addressof(__p->__value_.__cc.first));
  527. if (__p)
  528. __alloc_traits::deallocate(__na_, __p, 1);
  529. }
  530. };
  531. template <class _Key, class _Tp, class _Compare, class _Allocator>
  532. class map;
  533. template <class _Key, class _Tp, class _Compare, class _Allocator>
  534. class multimap;
  535. template <class _TreeIterator> class __map_const_iterator;
  536. #ifndef _LIBCPP_CXX03_LANG
  537. template <class _Key, class _Tp>
  538. union __value_type
  539. {
  540. typedef _Key key_type;
  541. typedef _Tp mapped_type;
  542. typedef pair<const key_type, mapped_type> value_type;
  543. typedef pair<key_type, mapped_type> __nc_value_type;
  544. value_type __cc;
  545. __nc_value_type __nc;
  546. _LIBCPP_INLINE_VISIBILITY
  547. __value_type& operator=(const __value_type& __v)
  548. {__nc = __v.__cc; return *this;}
  549. _LIBCPP_INLINE_VISIBILITY
  550. __value_type& operator=(__value_type&& __v)
  551. {__nc = _VSTD::move(__v.__nc); return *this;}
  552. template <class _ValueTp,
  553. class = typename enable_if<
  554. __is_same_uncvref<_ValueTp, value_type>::value
  555. >::type
  556. >
  557. _LIBCPP_INLINE_VISIBILITY
  558. __value_type& operator=(_ValueTp&& __v) {
  559. __nc = _VSTD::forward<_ValueTp>(__v); return *this;
  560. }
  561. private:
  562. __value_type() _LIBCPP_EQUAL_DELETE;
  563. ~__value_type() _LIBCPP_EQUAL_DELETE;
  564. __value_type(const __value_type& __v) _LIBCPP_EQUAL_DELETE;
  565. __value_type(__value_type&& __v) _LIBCPP_EQUAL_DELETE;
  566. };
  567. #else
  568. template <class _Key, class _Tp>
  569. struct __value_type
  570. {
  571. typedef _Key key_type;
  572. typedef _Tp mapped_type;
  573. typedef pair<const key_type, mapped_type> value_type;
  574. value_type __cc;
  575. private:
  576. __value_type();
  577. __value_type(__value_type const&);
  578. __value_type& operator=(__value_type const&);
  579. ~__value_type();
  580. };
  581. #endif
  582. template <class _Tp>
  583. struct __extract_key_value_types;
  584. template <class _Key, class _Tp>
  585. struct __extract_key_value_types<__value_type<_Key, _Tp> >
  586. {
  587. typedef _Key const __key_type;
  588. typedef _Tp __mapped_type;
  589. };
  590. template <class _TreeIterator>
  591. class _LIBCPP_TYPE_VIS_ONLY __map_iterator
  592. {
  593. typedef typename _TreeIterator::_NodeTypes _NodeTypes;
  594. typedef typename _TreeIterator::__pointer_traits __pointer_traits;
  595. _TreeIterator __i_;
  596. public:
  597. typedef bidirectional_iterator_tag iterator_category;
  598. typedef typename _NodeTypes::__map_value_type value_type;
  599. typedef typename _TreeIterator::difference_type difference_type;
  600. typedef value_type& reference;
  601. typedef typename _NodeTypes::__map_value_type_pointer pointer;
  602. _LIBCPP_INLINE_VISIBILITY
  603. __map_iterator() _NOEXCEPT {}
  604. _LIBCPP_INLINE_VISIBILITY
  605. __map_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
  606. _LIBCPP_INLINE_VISIBILITY
  607. reference operator*() const {return __i_->__cc;}
  608. _LIBCPP_INLINE_VISIBILITY
  609. pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
  610. _LIBCPP_INLINE_VISIBILITY
  611. __map_iterator& operator++() {++__i_; return *this;}
  612. _LIBCPP_INLINE_VISIBILITY
  613. __map_iterator operator++(int)
  614. {
  615. __map_iterator __t(*this);
  616. ++(*this);
  617. return __t;
  618. }
  619. _LIBCPP_INLINE_VISIBILITY
  620. __map_iterator& operator--() {--__i_; return *this;}
  621. _LIBCPP_INLINE_VISIBILITY
  622. __map_iterator operator--(int)
  623. {
  624. __map_iterator __t(*this);
  625. --(*this);
  626. return __t;
  627. }
  628. friend _LIBCPP_INLINE_VISIBILITY
  629. bool operator==(const __map_iterator& __x, const __map_iterator& __y)
  630. {return __x.__i_ == __y.__i_;}
  631. friend
  632. _LIBCPP_INLINE_VISIBILITY
  633. bool operator!=(const __map_iterator& __x, const __map_iterator& __y)
  634. {return __x.__i_ != __y.__i_;}
  635. template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
  636. template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
  637. template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;
  638. };
  639. template <class _TreeIterator>
  640. class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator
  641. {
  642. typedef typename _TreeIterator::_NodeTypes _NodeTypes;
  643. typedef typename _TreeIterator::__pointer_traits __pointer_traits;
  644. _TreeIterator __i_;
  645. public:
  646. typedef bidirectional_iterator_tag iterator_category;
  647. typedef typename _NodeTypes::__map_value_type value_type;
  648. typedef typename _TreeIterator::difference_type difference_type;
  649. typedef const value_type& reference;
  650. typedef typename _NodeTypes::__const_map_value_type_pointer pointer;
  651. _LIBCPP_INLINE_VISIBILITY
  652. __map_const_iterator() _NOEXCEPT {}
  653. _LIBCPP_INLINE_VISIBILITY
  654. __map_const_iterator(_TreeIterator __i) _NOEXCEPT : __i_(__i) {}
  655. _LIBCPP_INLINE_VISIBILITY
  656. __map_const_iterator(__map_iterator<
  657. typename _TreeIterator::__non_const_iterator> __i) _NOEXCEPT
  658. : __i_(__i.__i_) {}
  659. _LIBCPP_INLINE_VISIBILITY
  660. reference operator*() const {return __i_->__cc;}
  661. _LIBCPP_INLINE_VISIBILITY
  662. pointer operator->() const {return pointer_traits<pointer>::pointer_to(__i_->__cc);}
  663. _LIBCPP_INLINE_VISIBILITY
  664. __map_const_iterator& operator++() {++__i_; return *this;}
  665. _LIBCPP_INLINE_VISIBILITY
  666. __map_const_iterator operator++(int)
  667. {
  668. __map_const_iterator __t(*this);
  669. ++(*this);
  670. return __t;
  671. }
  672. _LIBCPP_INLINE_VISIBILITY
  673. __map_const_iterator& operator--() {--__i_; return *this;}
  674. _LIBCPP_INLINE_VISIBILITY
  675. __map_const_iterator operator--(int)
  676. {
  677. __map_const_iterator __t(*this);
  678. --(*this);
  679. return __t;
  680. }
  681. friend _LIBCPP_INLINE_VISIBILITY
  682. bool operator==(const __map_const_iterator& __x, const __map_const_iterator& __y)
  683. {return __x.__i_ == __y.__i_;}
  684. friend _LIBCPP_INLINE_VISIBILITY
  685. bool operator!=(const __map_const_iterator& __x, const __map_const_iterator& __y)
  686. {return __x.__i_ != __y.__i_;}
  687. template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;
  688. template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;
  689. template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;
  690. };
  691. template <class _Key, class _Tp, class _Compare = less<_Key>,
  692. class _Allocator = allocator<pair<const _Key, _Tp> > >
  693. class _LIBCPP_TYPE_VIS_ONLY map
  694. {
  695. public:
  696. // types:
  697. typedef _Key key_type;
  698. typedef _Tp mapped_type;
  699. typedef pair<const key_type, mapped_type> value_type;
  700. typedef pair<key_type, mapped_type> __nc_value_type;
  701. typedef _Compare key_compare;
  702. typedef _Allocator allocator_type;
  703. typedef value_type& reference;
  704. typedef const value_type& const_reference;
  705. static_assert((is_same<typename allocator_type::value_type, value_type>::value),
  706. "Allocator::value_type must be same type as value_type");
  707. class _LIBCPP_TYPE_VIS_ONLY value_compare
  708. : public binary_function<value_type, value_type, bool>
  709. {
  710. friend class map;
  711. protected:
  712. key_compare comp;
  713. _LIBCPP_INLINE_VISIBILITY value_compare(key_compare c) : comp(c) {}
  714. public:
  715. _LIBCPP_INLINE_VISIBILITY
  716. bool operator()(const value_type& __x, const value_type& __y) const
  717. {return comp(__x.first, __y.first);}
  718. };
  719. private:
  720. typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
  721. typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
  722. typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
  723. __value_type>::type __allocator_type;
  724. typedef __tree<__value_type, __vc, __allocator_type> __base;
  725. typedef typename __base::__node_traits __node_traits;
  726. typedef allocator_traits<allocator_type> __alloc_traits;
  727. __base __tree_;
  728. public:
  729. typedef typename __alloc_traits::pointer pointer;
  730. typedef typename __alloc_traits::const_pointer const_pointer;
  731. typedef typename __alloc_traits::size_type size_type;
  732. typedef typename __alloc_traits::difference_type difference_type;
  733. typedef __map_iterator<typename __base::iterator> iterator;
  734. typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
  735. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  736. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  737. _LIBCPP_INLINE_VISIBILITY
  738. map()
  739. _NOEXCEPT_(
  740. is_nothrow_default_constructible<allocator_type>::value &&
  741. is_nothrow_default_constructible<key_compare>::value &&
  742. is_nothrow_copy_constructible<key_compare>::value)
  743. : __tree_(__vc(key_compare())) {}
  744. _LIBCPP_INLINE_VISIBILITY
  745. explicit map(const key_compare& __comp)
  746. _NOEXCEPT_(
  747. is_nothrow_default_constructible<allocator_type>::value &&
  748. is_nothrow_copy_constructible<key_compare>::value)
  749. : __tree_(__vc(__comp)) {}
  750. _LIBCPP_INLINE_VISIBILITY
  751. explicit map(const key_compare& __comp, const allocator_type& __a)
  752. : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
  753. template <class _InputIterator>
  754. _LIBCPP_INLINE_VISIBILITY
  755. map(_InputIterator __f, _InputIterator __l,
  756. const key_compare& __comp = key_compare())
  757. : __tree_(__vc(__comp))
  758. {
  759. insert(__f, __l);
  760. }
  761. template <class _InputIterator>
  762. _LIBCPP_INLINE_VISIBILITY
  763. map(_InputIterator __f, _InputIterator __l,
  764. const key_compare& __comp, const allocator_type& __a)
  765. : __tree_(__vc(__comp), typename __base::allocator_type(__a))
  766. {
  767. insert(__f, __l);
  768. }
  769. #if _LIBCPP_STD_VER > 11
  770. template <class _InputIterator>
  771. _LIBCPP_INLINE_VISIBILITY
  772. map(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
  773. : map(__f, __l, key_compare(), __a) {}
  774. #endif
  775. _LIBCPP_INLINE_VISIBILITY
  776. map(const map& __m)
  777. : __tree_(__m.__tree_)
  778. {
  779. insert(__m.begin(), __m.end());
  780. }
  781. _LIBCPP_INLINE_VISIBILITY
  782. map& operator=(const map& __m)
  783. {
  784. #ifndef _LIBCPP_CXX03_LANG
  785. __tree_ = __m.__tree_;
  786. #else
  787. if (this != &__m) {
  788. __tree_.clear();
  789. __tree_.value_comp() = __m.__tree_.value_comp();
  790. __tree_.__copy_assign_alloc(__m.__tree_);
  791. insert(__m.begin(), __m.end());
  792. }
  793. #endif
  794. return *this;
  795. }
  796. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  797. _LIBCPP_INLINE_VISIBILITY
  798. map(map&& __m)
  799. _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
  800. : __tree_(_VSTD::move(__m.__tree_))
  801. {
  802. }
  803. map(map&& __m, const allocator_type& __a);
  804. _LIBCPP_INLINE_VISIBILITY
  805. map& operator=(map&& __m)
  806. _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
  807. {
  808. __tree_ = _VSTD::move(__m.__tree_);
  809. return *this;
  810. }
  811. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  812. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  813. _LIBCPP_INLINE_VISIBILITY
  814. map(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
  815. : __tree_(__vc(__comp))
  816. {
  817. insert(__il.begin(), __il.end());
  818. }
  819. _LIBCPP_INLINE_VISIBILITY
  820. map(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
  821. : __tree_(__vc(__comp), typename __base::allocator_type(__a))
  822. {
  823. insert(__il.begin(), __il.end());
  824. }
  825. #if _LIBCPP_STD_VER > 11
  826. _LIBCPP_INLINE_VISIBILITY
  827. map(initializer_list<value_type> __il, const allocator_type& __a)
  828. : map(__il, key_compare(), __a) {}
  829. #endif
  830. _LIBCPP_INLINE_VISIBILITY
  831. map& operator=(initializer_list<value_type> __il)
  832. {
  833. __tree_.__assign_unique(__il.begin(), __il.end());
  834. return *this;
  835. }
  836. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  837. _LIBCPP_INLINE_VISIBILITY
  838. explicit map(const allocator_type& __a)
  839. : __tree_(typename __base::allocator_type(__a))
  840. {
  841. }
  842. _LIBCPP_INLINE_VISIBILITY
  843. map(const map& __m, const allocator_type& __a)
  844. : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
  845. {
  846. insert(__m.begin(), __m.end());
  847. }
  848. _LIBCPP_INLINE_VISIBILITY
  849. iterator begin() _NOEXCEPT {return __tree_.begin();}
  850. _LIBCPP_INLINE_VISIBILITY
  851. const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
  852. _LIBCPP_INLINE_VISIBILITY
  853. iterator end() _NOEXCEPT {return __tree_.end();}
  854. _LIBCPP_INLINE_VISIBILITY
  855. const_iterator end() const _NOEXCEPT {return __tree_.end();}
  856. _LIBCPP_INLINE_VISIBILITY
  857. reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
  858. _LIBCPP_INLINE_VISIBILITY
  859. const_reverse_iterator rbegin() const _NOEXCEPT
  860. {return const_reverse_iterator(end());}
  861. _LIBCPP_INLINE_VISIBILITY
  862. reverse_iterator rend() _NOEXCEPT
  863. {return reverse_iterator(begin());}
  864. _LIBCPP_INLINE_VISIBILITY
  865. const_reverse_iterator rend() const _NOEXCEPT
  866. {return const_reverse_iterator(begin());}
  867. _LIBCPP_INLINE_VISIBILITY
  868. const_iterator cbegin() const _NOEXCEPT {return begin();}
  869. _LIBCPP_INLINE_VISIBILITY
  870. const_iterator cend() const _NOEXCEPT {return end();}
  871. _LIBCPP_INLINE_VISIBILITY
  872. const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
  873. _LIBCPP_INLINE_VISIBILITY
  874. const_reverse_iterator crend() const _NOEXCEPT {return rend();}
  875. _LIBCPP_INLINE_VISIBILITY
  876. bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
  877. _LIBCPP_INLINE_VISIBILITY
  878. size_type size() const _NOEXCEPT {return __tree_.size();}
  879. _LIBCPP_INLINE_VISIBILITY
  880. size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
  881. mapped_type& operator[](const key_type& __k);
  882. #ifndef _LIBCPP_CXX03_LANG
  883. mapped_type& operator[](key_type&& __k);
  884. #endif
  885. mapped_type& at(const key_type& __k);
  886. const mapped_type& at(const key_type& __k) const;
  887. _LIBCPP_INLINE_VISIBILITY
  888. allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
  889. _LIBCPP_INLINE_VISIBILITY
  890. key_compare key_comp() const {return __tree_.value_comp().key_comp();}
  891. _LIBCPP_INLINE_VISIBILITY
  892. value_compare value_comp() const {return value_compare(__tree_.value_comp().key_comp());}
  893. #ifndef _LIBCPP_CXX03_LANG
  894. template <class ..._Args>
  895. _LIBCPP_INLINE_VISIBILITY
  896. pair<iterator, bool> emplace(_Args&& ...__args) {
  897. return __tree_.__emplace_unique(_VSTD::forward<_Args>(__args)...);
  898. }
  899. template <class ..._Args>
  900. _LIBCPP_INLINE_VISIBILITY
  901. iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
  902. return __tree_.__emplace_hint_unique(__p.__i_, _VSTD::forward<_Args>(__args)...);
  903. }
  904. template <class _Pp,
  905. class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
  906. _LIBCPP_INLINE_VISIBILITY
  907. pair<iterator, bool> insert(_Pp&& __p)
  908. {return __tree_.__insert_unique(_VSTD::forward<_Pp>(__p));}
  909. template <class _Pp,
  910. class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
  911. _LIBCPP_INLINE_VISIBILITY
  912. iterator insert(const_iterator __pos, _Pp&& __p)
  913. {return __tree_.__insert_unique(__pos.__i_, _VSTD::forward<_Pp>(__p));}
  914. #endif // _LIBCPP_CXX03_LANG
  915. _LIBCPP_INLINE_VISIBILITY
  916. pair<iterator, bool>
  917. insert(const value_type& __v) {return __tree_.__insert_unique(__v);}
  918. _LIBCPP_INLINE_VISIBILITY
  919. iterator
  920. insert(const_iterator __p, const value_type& __v)
  921. {return __tree_.__insert_unique(__p.__i_, __v);}
  922. #ifndef _LIBCPP_CXX03_LANG
  923. _LIBCPP_INLINE_VISIBILITY
  924. pair<iterator, bool>
  925. insert(value_type&& __v) {return __tree_.__insert_unique(_VSTD::move(__v));}
  926. _LIBCPP_INLINE_VISIBILITY
  927. iterator insert(const_iterator __p, value_type&& __v)
  928. {return __tree_.__insert_unique(__p.__i_, _VSTD::move(__v));}
  929. #endif
  930. template <class _InputIterator>
  931. _LIBCPP_INLINE_VISIBILITY
  932. void insert(_InputIterator __f, _InputIterator __l)
  933. {
  934. for (const_iterator __e = cend(); __f != __l; ++__f)
  935. insert(__e.__i_, *__f);
  936. }
  937. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  938. _LIBCPP_INLINE_VISIBILITY
  939. void insert(initializer_list<value_type> __il)
  940. {insert(__il.begin(), __il.end());}
  941. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  942. #if _LIBCPP_STD_VER > 14
  943. template <class... _Args>
  944. _LIBCPP_INLINE_VISIBILITY
  945. pair<iterator, bool> try_emplace(const key_type& __k, _Args&&... __args)
  946. {
  947. return __tree_.__emplace_unique_key_args(__k,
  948. _VSTD::piecewise_construct,
  949. _VSTD::forward_as_tuple(__k),
  950. _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
  951. }
  952. template <class... _Args>
  953. _LIBCPP_INLINE_VISIBILITY
  954. pair<iterator, bool> try_emplace(key_type&& __k, _Args&&... __args)
  955. {
  956. return __tree_.__emplace_unique_key_args(__k,
  957. _VSTD::piecewise_construct,
  958. _VSTD::forward_as_tuple(_VSTD::move(__k)),
  959. _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
  960. }
  961. template <class... _Args>
  962. _LIBCPP_INLINE_VISIBILITY
  963. iterator try_emplace(const_iterator __h, const key_type& __k, _Args&&... __args)
  964. {
  965. return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
  966. _VSTD::piecewise_construct,
  967. _VSTD::forward_as_tuple(__k),
  968. _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
  969. }
  970. template <class... _Args>
  971. _LIBCPP_INLINE_VISIBILITY
  972. iterator try_emplace(const_iterator __h, key_type&& __k, _Args&&... __args)
  973. {
  974. return __tree_.__emplace_hint_unique_key_args(__h.__i_, __k,
  975. _VSTD::piecewise_construct,
  976. _VSTD::forward_as_tuple(_VSTD::move(__k)),
  977. _VSTD::forward_as_tuple(_VSTD::forward<_Args>(__args)...));
  978. }
  979. template <class _Vp>
  980. _LIBCPP_INLINE_VISIBILITY
  981. pair<iterator, bool> insert_or_assign(const key_type& __k, _Vp&& __v)
  982. {
  983. iterator __p = lower_bound(__k);
  984. if ( __p != end() && !key_comp()(__k, __p->first))
  985. {
  986. __p->second = _VSTD::forward<_Vp>(__v);
  987. return _VSTD::make_pair(__p, false);
  988. }
  989. return _VSTD::make_pair(emplace_hint(__p, __k, _VSTD::forward<_Vp>(__v)), true);
  990. }
  991. template <class _Vp>
  992. _LIBCPP_INLINE_VISIBILITY
  993. pair<iterator, bool> insert_or_assign(key_type&& __k, _Vp&& __v)
  994. {
  995. iterator __p = lower_bound(__k);
  996. if ( __p != end() && !key_comp()(__k, __p->first))
  997. {
  998. __p->second = _VSTD::forward<_Vp>(__v);
  999. return _VSTD::make_pair(__p, false);
  1000. }
  1001. return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
  1002. }
  1003. template <class _Vp>
  1004. _LIBCPP_INLINE_VISIBILITY
  1005. iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
  1006. {
  1007. iterator __p = lower_bound(__k);
  1008. if ( __p != end() && !key_comp()(__k, __p->first))
  1009. {
  1010. __p->second = _VSTD::forward<_Vp>(__v);
  1011. return __p;
  1012. }
  1013. return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
  1014. }
  1015. template <class _Vp>
  1016. _LIBCPP_INLINE_VISIBILITY
  1017. iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
  1018. {
  1019. iterator __p = lower_bound(__k);
  1020. if ( __p != end() && !key_comp()(__k, __p->first))
  1021. {
  1022. __p->second = _VSTD::forward<_Vp>(__v);
  1023. return __p;
  1024. }
  1025. return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
  1026. }
  1027. #endif
  1028. _LIBCPP_INLINE_VISIBILITY
  1029. iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
  1030. _LIBCPP_INLINE_VISIBILITY
  1031. iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
  1032. _LIBCPP_INLINE_VISIBILITY
  1033. size_type erase(const key_type& __k)
  1034. {return __tree_.__erase_unique(__k);}
  1035. _LIBCPP_INLINE_VISIBILITY
  1036. iterator erase(const_iterator __f, const_iterator __l)
  1037. {return __tree_.erase(__f.__i_, __l.__i_);}
  1038. _LIBCPP_INLINE_VISIBILITY
  1039. void clear() _NOEXCEPT {__tree_.clear();}
  1040. _LIBCPP_INLINE_VISIBILITY
  1041. void swap(map& __m)
  1042. _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
  1043. {__tree_.swap(__m.__tree_);}
  1044. _LIBCPP_INLINE_VISIBILITY
  1045. iterator find(const key_type& __k) {return __tree_.find(__k);}
  1046. _LIBCPP_INLINE_VISIBILITY
  1047. const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
  1048. #if _LIBCPP_STD_VER > 11
  1049. template <typename _K2>
  1050. _LIBCPP_INLINE_VISIBILITY
  1051. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1052. find(const _K2& __k) {return __tree_.find(__k);}
  1053. template <typename _K2>
  1054. _LIBCPP_INLINE_VISIBILITY
  1055. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1056. find(const _K2& __k) const {return __tree_.find(__k);}
  1057. #endif
  1058. _LIBCPP_INLINE_VISIBILITY
  1059. size_type count(const key_type& __k) const
  1060. {return __tree_.__count_unique(__k);}
  1061. #if _LIBCPP_STD_VER > 11
  1062. template <typename _K2>
  1063. _LIBCPP_INLINE_VISIBILITY
  1064. typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
  1065. count(const _K2& __k) const {return __tree_.__count_unique(__k);}
  1066. #endif
  1067. _LIBCPP_INLINE_VISIBILITY
  1068. iterator lower_bound(const key_type& __k)
  1069. {return __tree_.lower_bound(__k);}
  1070. _LIBCPP_INLINE_VISIBILITY
  1071. const_iterator lower_bound(const key_type& __k) const
  1072. {return __tree_.lower_bound(__k);}
  1073. #if _LIBCPP_STD_VER > 11
  1074. template <typename _K2>
  1075. _LIBCPP_INLINE_VISIBILITY
  1076. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1077. lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
  1078. template <typename _K2>
  1079. _LIBCPP_INLINE_VISIBILITY
  1080. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1081. lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
  1082. #endif
  1083. _LIBCPP_INLINE_VISIBILITY
  1084. iterator upper_bound(const key_type& __k)
  1085. {return __tree_.upper_bound(__k);}
  1086. _LIBCPP_INLINE_VISIBILITY
  1087. const_iterator upper_bound(const key_type& __k) const
  1088. {return __tree_.upper_bound(__k);}
  1089. #if _LIBCPP_STD_VER > 11
  1090. template <typename _K2>
  1091. _LIBCPP_INLINE_VISIBILITY
  1092. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1093. upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
  1094. template <typename _K2>
  1095. _LIBCPP_INLINE_VISIBILITY
  1096. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1097. upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
  1098. #endif
  1099. _LIBCPP_INLINE_VISIBILITY
  1100. pair<iterator,iterator> equal_range(const key_type& __k)
  1101. {return __tree_.__equal_range_unique(__k);}
  1102. _LIBCPP_INLINE_VISIBILITY
  1103. pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
  1104. {return __tree_.__equal_range_unique(__k);}
  1105. #if _LIBCPP_STD_VER > 11
  1106. template <typename _K2>
  1107. _LIBCPP_INLINE_VISIBILITY
  1108. typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
  1109. equal_range(const _K2& __k) {return __tree_.__equal_range_unique(__k);}
  1110. template <typename _K2>
  1111. _LIBCPP_INLINE_VISIBILITY
  1112. typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
  1113. equal_range(const _K2& __k) const {return __tree_.__equal_range_unique(__k);}
  1114. #endif
  1115. private:
  1116. typedef typename __base::__node __node;
  1117. typedef typename __base::__node_allocator __node_allocator;
  1118. typedef typename __base::__node_pointer __node_pointer;
  1119. typedef typename __base::__node_base_pointer __node_base_pointer;
  1120. typedef __map_node_destructor<__node_allocator> _Dp;
  1121. typedef unique_ptr<__node, _Dp> __node_holder;
  1122. #ifdef _LIBCPP_CXX03_LANG
  1123. __node_holder __construct_node_with_key(const key_type& __k);
  1124. #endif
  1125. __node_base_pointer const&
  1126. __find_equal_key(__node_base_pointer& __parent, const key_type& __k) const;
  1127. _LIBCPP_INLINE_VISIBILITY
  1128. __node_base_pointer&
  1129. __find_equal_key(__node_base_pointer& __parent, const key_type& __k) {
  1130. map const* __const_this = this;
  1131. return const_cast<__node_base_pointer&>(
  1132. __const_this->__find_equal_key(__parent, __k));
  1133. }
  1134. };
  1135. // Find __k
  1136. // Set __parent to parent of null leaf and
  1137. // return reference to null leaf iv __k does not exist.
  1138. // If __k exists, set parent to node of __k and return reference to node of __k
  1139. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1140. typename map<_Key, _Tp, _Compare, _Allocator>::__node_base_pointer const&
  1141. map<_Key, _Tp, _Compare, _Allocator>::__find_equal_key(__node_base_pointer& __parent,
  1142. const key_type& __k) const
  1143. {
  1144. __node_pointer __nd = __tree_.__root();
  1145. if (__nd != nullptr)
  1146. {
  1147. while (true)
  1148. {
  1149. if (__tree_.value_comp().key_comp()(__k, __nd->__value_.__cc.first))
  1150. {
  1151. if (__nd->__left_ != nullptr)
  1152. __nd = static_cast<__node_pointer>(__nd->__left_);
  1153. else
  1154. {
  1155. __parent = static_cast<__node_base_pointer>(__nd);
  1156. return __parent->__left_;
  1157. }
  1158. }
  1159. else if (__tree_.value_comp().key_comp()(__nd->__value_.__cc.first, __k))
  1160. {
  1161. if (__nd->__right_ != nullptr)
  1162. __nd = static_cast<__node_pointer>(__nd->__right_);
  1163. else
  1164. {
  1165. __parent = static_cast<__node_base_pointer>(__nd);
  1166. return __parent->__right_;
  1167. }
  1168. }
  1169. else
  1170. {
  1171. __parent = static_cast<__node_base_pointer>(__nd);
  1172. return __parent;
  1173. }
  1174. }
  1175. }
  1176. __parent = static_cast<__node_base_pointer>(__tree_.__end_node());
  1177. return __parent->__left_;
  1178. }
  1179. #ifndef _LIBCPP_CXX03_LANG
  1180. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1181. map<_Key, _Tp, _Compare, _Allocator>::map(map&& __m, const allocator_type& __a)
  1182. : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
  1183. {
  1184. if (__a != __m.get_allocator())
  1185. {
  1186. const_iterator __e = cend();
  1187. while (!__m.empty())
  1188. __tree_.__insert_unique(__e.__i_,
  1189. _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
  1190. }
  1191. }
  1192. #endif // !_LIBCPP_CXX03_LANG
  1193. #ifdef _LIBCPP_CXX03_LANG
  1194. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1195. typename map<_Key, _Tp, _Compare, _Allocator>::__node_holder
  1196. map<_Key, _Tp, _Compare, _Allocator>::__construct_node_with_key(const key_type& __k)
  1197. {
  1198. __node_allocator& __na = __tree_.__node_alloc();
  1199. __node_holder __h(__node_traits::allocate(__na, 1), _Dp(__na));
  1200. __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.first), __k);
  1201. __h.get_deleter().__first_constructed = true;
  1202. __node_traits::construct(__na, _VSTD::addressof(__h->__value_.__cc.second));
  1203. __h.get_deleter().__second_constructed = true;
  1204. return _LIBCPP_EXPLICIT_MOVE(__h); // explicitly moved for C++03
  1205. }
  1206. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1207. _Tp&
  1208. map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
  1209. {
  1210. __node_base_pointer __parent;
  1211. __node_base_pointer& __child = __find_equal_key(__parent, __k);
  1212. __node_pointer __r = static_cast<__node_pointer>(__child);
  1213. if (__child == nullptr)
  1214. {
  1215. __node_holder __h = __construct_node_with_key(__k);
  1216. __tree_.__insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
  1217. __r = __h.release();
  1218. }
  1219. return __r->__value_.__cc.second;
  1220. }
  1221. #else
  1222. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1223. _Tp&
  1224. map<_Key, _Tp, _Compare, _Allocator>::operator[](const key_type& __k)
  1225. {
  1226. return __tree_.__emplace_unique_key_args(__k,
  1227. _VSTD::piecewise_construct,
  1228. _VSTD::forward_as_tuple(__k),
  1229. _VSTD::forward_as_tuple()).first->__cc.second;
  1230. }
  1231. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1232. _Tp&
  1233. map<_Key, _Tp, _Compare, _Allocator>::operator[](key_type&& __k)
  1234. {
  1235. return __tree_.__emplace_unique_key_args(__k,
  1236. _VSTD::piecewise_construct,
  1237. _VSTD::forward_as_tuple(_VSTD::move(__k)),
  1238. _VSTD::forward_as_tuple()).first->__cc.second;
  1239. }
  1240. #endif // !_LIBCPP_CXX03_LANG
  1241. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1242. _Tp&
  1243. map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k)
  1244. {
  1245. __node_base_pointer __parent;
  1246. __node_base_pointer& __child = __find_equal_key(__parent, __k);
  1247. #ifndef _LIBCPP_NO_EXCEPTIONS
  1248. if (__child == nullptr)
  1249. throw out_of_range("map::at: key not found");
  1250. #endif // _LIBCPP_NO_EXCEPTIONS
  1251. return static_cast<__node_pointer>(__child)->__value_.__cc.second;
  1252. }
  1253. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1254. const _Tp&
  1255. map<_Key, _Tp, _Compare, _Allocator>::at(const key_type& __k) const
  1256. {
  1257. __node_base_pointer __parent;
  1258. __node_base_pointer __child = __find_equal_key(__parent, __k);
  1259. #ifndef _LIBCPP_NO_EXCEPTIONS
  1260. if (__child == nullptr)
  1261. throw out_of_range("map::at: key not found");
  1262. #endif // _LIBCPP_NO_EXCEPTIONS
  1263. return static_cast<__node_pointer>(__child)->__value_.__cc.second;
  1264. }
  1265. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1266. inline _LIBCPP_INLINE_VISIBILITY
  1267. bool
  1268. operator==(const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1269. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1270. {
  1271. return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
  1272. }
  1273. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1274. inline _LIBCPP_INLINE_VISIBILITY
  1275. bool
  1276. operator< (const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1277. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1278. {
  1279. return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
  1280. }
  1281. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1282. inline _LIBCPP_INLINE_VISIBILITY
  1283. bool
  1284. operator!=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1285. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1286. {
  1287. return !(__x == __y);
  1288. }
  1289. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1290. inline _LIBCPP_INLINE_VISIBILITY
  1291. bool
  1292. operator> (const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1293. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1294. {
  1295. return __y < __x;
  1296. }
  1297. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1298. inline _LIBCPP_INLINE_VISIBILITY
  1299. bool
  1300. operator>=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1301. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1302. {
  1303. return !(__x < __y);
  1304. }
  1305. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1306. inline _LIBCPP_INLINE_VISIBILITY
  1307. bool
  1308. operator<=(const map<_Key, _Tp, _Compare, _Allocator>& __x,
  1309. const map<_Key, _Tp, _Compare, _Allocator>& __y)
  1310. {
  1311. return !(__y < __x);
  1312. }
  1313. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1314. inline _LIBCPP_INLINE_VISIBILITY
  1315. void
  1316. swap(map<_Key, _Tp, _Compare, _Allocator>& __x,
  1317. map<_Key, _Tp, _Compare, _Allocator>& __y)
  1318. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  1319. {
  1320. __x.swap(__y);
  1321. }
  1322. template <class _Key, class _Tp, class _Compare = less<_Key>,
  1323. class _Allocator = allocator<pair<const _Key, _Tp> > >
  1324. class _LIBCPP_TYPE_VIS_ONLY multimap
  1325. {
  1326. public:
  1327. // types:
  1328. typedef _Key key_type;
  1329. typedef _Tp mapped_type;
  1330. typedef pair<const key_type, mapped_type> value_type;
  1331. typedef pair<key_type, mapped_type> __nc_value_type;
  1332. typedef _Compare key_compare;
  1333. typedef _Allocator allocator_type;
  1334. typedef value_type& reference;
  1335. typedef const value_type& const_reference;
  1336. static_assert((is_same<typename allocator_type::value_type, value_type>::value),
  1337. "Allocator::value_type must be same type as value_type");
  1338. class _LIBCPP_TYPE_VIS_ONLY value_compare
  1339. : public binary_function<value_type, value_type, bool>
  1340. {
  1341. friend class multimap;
  1342. protected:
  1343. key_compare comp;
  1344. _LIBCPP_INLINE_VISIBILITY
  1345. value_compare(key_compare c) : comp(c) {}
  1346. public:
  1347. _LIBCPP_INLINE_VISIBILITY
  1348. bool operator()(const value_type& __x, const value_type& __y) const
  1349. {return comp(__x.first, __y.first);}
  1350. };
  1351. private:
  1352. typedef _VSTD::__value_type<key_type, mapped_type> __value_type;
  1353. typedef __map_value_compare<key_type, __value_type, key_compare> __vc;
  1354. typedef typename __rebind_alloc_helper<allocator_traits<allocator_type>,
  1355. __value_type>::type __allocator_type;
  1356. typedef __tree<__value_type, __vc, __allocator_type> __base;
  1357. typedef typename __base::__node_traits __node_traits;
  1358. typedef allocator_traits<allocator_type> __alloc_traits;
  1359. __base __tree_;
  1360. public:
  1361. typedef typename __alloc_traits::pointer pointer;
  1362. typedef typename __alloc_traits::const_pointer const_pointer;
  1363. typedef typename __alloc_traits::size_type size_type;
  1364. typedef typename __alloc_traits::difference_type difference_type;
  1365. typedef __map_iterator<typename __base::iterator> iterator;
  1366. typedef __map_const_iterator<typename __base::const_iterator> const_iterator;
  1367. typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
  1368. typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
  1369. _LIBCPP_INLINE_VISIBILITY
  1370. multimap()
  1371. _NOEXCEPT_(
  1372. is_nothrow_default_constructible<allocator_type>::value &&
  1373. is_nothrow_default_constructible<key_compare>::value &&
  1374. is_nothrow_copy_constructible<key_compare>::value)
  1375. : __tree_(__vc(key_compare())) {}
  1376. _LIBCPP_INLINE_VISIBILITY
  1377. explicit multimap(const key_compare& __comp)
  1378. _NOEXCEPT_(
  1379. is_nothrow_default_constructible<allocator_type>::value &&
  1380. is_nothrow_copy_constructible<key_compare>::value)
  1381. : __tree_(__vc(__comp)) {}
  1382. _LIBCPP_INLINE_VISIBILITY
  1383. explicit multimap(const key_compare& __comp, const allocator_type& __a)
  1384. : __tree_(__vc(__comp), typename __base::allocator_type(__a)) {}
  1385. template <class _InputIterator>
  1386. _LIBCPP_INLINE_VISIBILITY
  1387. multimap(_InputIterator __f, _InputIterator __l,
  1388. const key_compare& __comp = key_compare())
  1389. : __tree_(__vc(__comp))
  1390. {
  1391. insert(__f, __l);
  1392. }
  1393. template <class _InputIterator>
  1394. _LIBCPP_INLINE_VISIBILITY
  1395. multimap(_InputIterator __f, _InputIterator __l,
  1396. const key_compare& __comp, const allocator_type& __a)
  1397. : __tree_(__vc(__comp), typename __base::allocator_type(__a))
  1398. {
  1399. insert(__f, __l);
  1400. }
  1401. #if _LIBCPP_STD_VER > 11
  1402. template <class _InputIterator>
  1403. _LIBCPP_INLINE_VISIBILITY
  1404. multimap(_InputIterator __f, _InputIterator __l, const allocator_type& __a)
  1405. : multimap(__f, __l, key_compare(), __a) {}
  1406. #endif
  1407. _LIBCPP_INLINE_VISIBILITY
  1408. multimap(const multimap& __m)
  1409. : __tree_(__m.__tree_.value_comp(),
  1410. __alloc_traits::select_on_container_copy_construction(__m.__tree_.__alloc()))
  1411. {
  1412. insert(__m.begin(), __m.end());
  1413. }
  1414. _LIBCPP_INLINE_VISIBILITY
  1415. multimap& operator=(const multimap& __m)
  1416. {
  1417. #ifndef _LIBCPP_CXX03_LANG
  1418. __tree_ = __m.__tree_;
  1419. #else
  1420. if (this != &__m) {
  1421. __tree_.clear();
  1422. __tree_.value_comp() = __m.__tree_.value_comp();
  1423. __tree_.__copy_assign_alloc(__m.__tree_);
  1424. insert(__m.begin(), __m.end());
  1425. }
  1426. #endif
  1427. return *this;
  1428. }
  1429. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1430. _LIBCPP_INLINE_VISIBILITY
  1431. multimap(multimap&& __m)
  1432. _NOEXCEPT_(is_nothrow_move_constructible<__base>::value)
  1433. : __tree_(_VSTD::move(__m.__tree_))
  1434. {
  1435. }
  1436. multimap(multimap&& __m, const allocator_type& __a);
  1437. _LIBCPP_INLINE_VISIBILITY
  1438. multimap& operator=(multimap&& __m)
  1439. _NOEXCEPT_(is_nothrow_move_assignable<__base>::value)
  1440. {
  1441. __tree_ = _VSTD::move(__m.__tree_);
  1442. return *this;
  1443. }
  1444. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1445. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1446. _LIBCPP_INLINE_VISIBILITY
  1447. multimap(initializer_list<value_type> __il, const key_compare& __comp = key_compare())
  1448. : __tree_(__vc(__comp))
  1449. {
  1450. insert(__il.begin(), __il.end());
  1451. }
  1452. _LIBCPP_INLINE_VISIBILITY
  1453. multimap(initializer_list<value_type> __il, const key_compare& __comp, const allocator_type& __a)
  1454. : __tree_(__vc(__comp), typename __base::allocator_type(__a))
  1455. {
  1456. insert(__il.begin(), __il.end());
  1457. }
  1458. #if _LIBCPP_STD_VER > 11
  1459. _LIBCPP_INLINE_VISIBILITY
  1460. multimap(initializer_list<value_type> __il, const allocator_type& __a)
  1461. : multimap(__il, key_compare(), __a) {}
  1462. #endif
  1463. _LIBCPP_INLINE_VISIBILITY
  1464. multimap& operator=(initializer_list<value_type> __il)
  1465. {
  1466. __tree_.__assign_multi(__il.begin(), __il.end());
  1467. return *this;
  1468. }
  1469. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1470. _LIBCPP_INLINE_VISIBILITY
  1471. explicit multimap(const allocator_type& __a)
  1472. : __tree_(typename __base::allocator_type(__a))
  1473. {
  1474. }
  1475. _LIBCPP_INLINE_VISIBILITY
  1476. multimap(const multimap& __m, const allocator_type& __a)
  1477. : __tree_(__m.__tree_.value_comp(), typename __base::allocator_type(__a))
  1478. {
  1479. insert(__m.begin(), __m.end());
  1480. }
  1481. _LIBCPP_INLINE_VISIBILITY
  1482. iterator begin() _NOEXCEPT {return __tree_.begin();}
  1483. _LIBCPP_INLINE_VISIBILITY
  1484. const_iterator begin() const _NOEXCEPT {return __tree_.begin();}
  1485. _LIBCPP_INLINE_VISIBILITY
  1486. iterator end() _NOEXCEPT {return __tree_.end();}
  1487. _LIBCPP_INLINE_VISIBILITY
  1488. const_iterator end() const _NOEXCEPT {return __tree_.end();}
  1489. _LIBCPP_INLINE_VISIBILITY
  1490. reverse_iterator rbegin() _NOEXCEPT {return reverse_iterator(end());}
  1491. _LIBCPP_INLINE_VISIBILITY
  1492. const_reverse_iterator rbegin() const _NOEXCEPT
  1493. {return const_reverse_iterator(end());}
  1494. _LIBCPP_INLINE_VISIBILITY
  1495. reverse_iterator rend() _NOEXCEPT {return reverse_iterator(begin());}
  1496. _LIBCPP_INLINE_VISIBILITY
  1497. const_reverse_iterator rend() const _NOEXCEPT
  1498. {return const_reverse_iterator(begin());}
  1499. _LIBCPP_INLINE_VISIBILITY
  1500. const_iterator cbegin() const _NOEXCEPT {return begin();}
  1501. _LIBCPP_INLINE_VISIBILITY
  1502. const_iterator cend() const _NOEXCEPT {return end();}
  1503. _LIBCPP_INLINE_VISIBILITY
  1504. const_reverse_iterator crbegin() const _NOEXCEPT {return rbegin();}
  1505. _LIBCPP_INLINE_VISIBILITY
  1506. const_reverse_iterator crend() const _NOEXCEPT {return rend();}
  1507. _LIBCPP_INLINE_VISIBILITY
  1508. bool empty() const _NOEXCEPT {return __tree_.size() == 0;}
  1509. _LIBCPP_INLINE_VISIBILITY
  1510. size_type size() const _NOEXCEPT {return __tree_.size();}
  1511. _LIBCPP_INLINE_VISIBILITY
  1512. size_type max_size() const _NOEXCEPT {return __tree_.max_size();}
  1513. _LIBCPP_INLINE_VISIBILITY
  1514. allocator_type get_allocator() const _NOEXCEPT {return allocator_type(__tree_.__alloc());}
  1515. _LIBCPP_INLINE_VISIBILITY
  1516. key_compare key_comp() const {return __tree_.value_comp().key_comp();}
  1517. _LIBCPP_INLINE_VISIBILITY
  1518. value_compare value_comp() const
  1519. {return value_compare(__tree_.value_comp().key_comp());}
  1520. #ifndef _LIBCPP_CXX03_LANG
  1521. template <class ..._Args>
  1522. _LIBCPP_INLINE_VISIBILITY
  1523. iterator emplace(_Args&& ...__args) {
  1524. return __tree_.__emplace_multi(_VSTD::forward<_Args>(__args)...);
  1525. }
  1526. template <class ..._Args>
  1527. _LIBCPP_INLINE_VISIBILITY
  1528. iterator emplace_hint(const_iterator __p, _Args&& ...__args) {
  1529. return __tree_.__emplace_hint_multi(__p.__i_, _VSTD::forward<_Args>(__args)...);
  1530. }
  1531. template <class _Pp,
  1532. class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
  1533. _LIBCPP_INLINE_VISIBILITY
  1534. iterator insert(_Pp&& __p)
  1535. {return __tree_.__insert_multi(_VSTD::forward<_Pp>(__p));}
  1536. template <class _Pp,
  1537. class = typename enable_if<is_constructible<value_type, _Pp>::value>::type>
  1538. _LIBCPP_INLINE_VISIBILITY
  1539. iterator insert(const_iterator __pos, _Pp&& __p)
  1540. {return __tree_.__insert_multi(__pos.__i_, _VSTD::forward<_Pp>(__p));}
  1541. _LIBCPP_INLINE_VISIBILITY
  1542. iterator insert(value_type&& __v)
  1543. {return __tree_.__insert_multi(_VSTD::move(__v));}
  1544. _LIBCPP_INLINE_VISIBILITY
  1545. iterator insert(const_iterator __p, value_type&& __v)
  1546. {return __tree_.__insert_multi(__p.__i_, _VSTD::move(__v));}
  1547. #endif // _LIBCPP_CXX03_LANG
  1548. _LIBCPP_INLINE_VISIBILITY
  1549. iterator insert(const value_type& __v) {return __tree_.__insert_multi(__v);}
  1550. _LIBCPP_INLINE_VISIBILITY
  1551. iterator insert(const_iterator __p, const value_type& __v)
  1552. {return __tree_.__insert_multi(__p.__i_, __v);}
  1553. template <class _InputIterator>
  1554. _LIBCPP_INLINE_VISIBILITY
  1555. void insert(_InputIterator __f, _InputIterator __l)
  1556. {
  1557. for (const_iterator __e = cend(); __f != __l; ++__f)
  1558. __tree_.__insert_multi(__e.__i_, *__f);
  1559. }
  1560. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1561. _LIBCPP_INLINE_VISIBILITY
  1562. void insert(initializer_list<value_type> __il)
  1563. {insert(__il.begin(), __il.end());}
  1564. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1565. _LIBCPP_INLINE_VISIBILITY
  1566. iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
  1567. _LIBCPP_INLINE_VISIBILITY
  1568. iterator erase(iterator __p) {return __tree_.erase(__p.__i_);}
  1569. _LIBCPP_INLINE_VISIBILITY
  1570. size_type erase(const key_type& __k) {return __tree_.__erase_multi(__k);}
  1571. _LIBCPP_INLINE_VISIBILITY
  1572. iterator erase(const_iterator __f, const_iterator __l)
  1573. {return __tree_.erase(__f.__i_, __l.__i_);}
  1574. _LIBCPP_INLINE_VISIBILITY
  1575. void clear() {__tree_.clear();}
  1576. _LIBCPP_INLINE_VISIBILITY
  1577. void swap(multimap& __m)
  1578. _NOEXCEPT_(__is_nothrow_swappable<__base>::value)
  1579. {__tree_.swap(__m.__tree_);}
  1580. _LIBCPP_INLINE_VISIBILITY
  1581. iterator find(const key_type& __k) {return __tree_.find(__k);}
  1582. _LIBCPP_INLINE_VISIBILITY
  1583. const_iterator find(const key_type& __k) const {return __tree_.find(__k);}
  1584. #if _LIBCPP_STD_VER > 11
  1585. template <typename _K2>
  1586. _LIBCPP_INLINE_VISIBILITY
  1587. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1588. find(const _K2& __k) {return __tree_.find(__k);}
  1589. template <typename _K2>
  1590. _LIBCPP_INLINE_VISIBILITY
  1591. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1592. find(const _K2& __k) const {return __tree_.find(__k);}
  1593. #endif
  1594. _LIBCPP_INLINE_VISIBILITY
  1595. size_type count(const key_type& __k) const
  1596. {return __tree_.__count_multi(__k);}
  1597. #if _LIBCPP_STD_VER > 11
  1598. template <typename _K2>
  1599. _LIBCPP_INLINE_VISIBILITY
  1600. typename enable_if<__is_transparent<_Compare, _K2>::value,size_type>::type
  1601. count(const _K2& __k) const {return __tree_.__count_multi(__k);}
  1602. #endif
  1603. _LIBCPP_INLINE_VISIBILITY
  1604. iterator lower_bound(const key_type& __k)
  1605. {return __tree_.lower_bound(__k);}
  1606. _LIBCPP_INLINE_VISIBILITY
  1607. const_iterator lower_bound(const key_type& __k) const
  1608. {return __tree_.lower_bound(__k);}
  1609. #if _LIBCPP_STD_VER > 11
  1610. template <typename _K2>
  1611. _LIBCPP_INLINE_VISIBILITY
  1612. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1613. lower_bound(const _K2& __k) {return __tree_.lower_bound(__k);}
  1614. template <typename _K2>
  1615. _LIBCPP_INLINE_VISIBILITY
  1616. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1617. lower_bound(const _K2& __k) const {return __tree_.lower_bound(__k);}
  1618. #endif
  1619. _LIBCPP_INLINE_VISIBILITY
  1620. iterator upper_bound(const key_type& __k)
  1621. {return __tree_.upper_bound(__k);}
  1622. _LIBCPP_INLINE_VISIBILITY
  1623. const_iterator upper_bound(const key_type& __k) const
  1624. {return __tree_.upper_bound(__k);}
  1625. #if _LIBCPP_STD_VER > 11
  1626. template <typename _K2>
  1627. _LIBCPP_INLINE_VISIBILITY
  1628. typename enable_if<__is_transparent<_Compare, _K2>::value,iterator>::type
  1629. upper_bound(const _K2& __k) {return __tree_.upper_bound(__k);}
  1630. template <typename _K2>
  1631. _LIBCPP_INLINE_VISIBILITY
  1632. typename enable_if<__is_transparent<_Compare, _K2>::value,const_iterator>::type
  1633. upper_bound(const _K2& __k) const {return __tree_.upper_bound(__k);}
  1634. #endif
  1635. _LIBCPP_INLINE_VISIBILITY
  1636. pair<iterator,iterator> equal_range(const key_type& __k)
  1637. {return __tree_.__equal_range_multi(__k);}
  1638. _LIBCPP_INLINE_VISIBILITY
  1639. pair<const_iterator,const_iterator> equal_range(const key_type& __k) const
  1640. {return __tree_.__equal_range_multi(__k);}
  1641. #if _LIBCPP_STD_VER > 11
  1642. template <typename _K2>
  1643. _LIBCPP_INLINE_VISIBILITY
  1644. typename enable_if<__is_transparent<_Compare, _K2>::value,pair<iterator,iterator>>::type
  1645. equal_range(const _K2& __k) {return __tree_.__equal_range_multi(__k);}
  1646. template <typename _K2>
  1647. _LIBCPP_INLINE_VISIBILITY
  1648. typename enable_if<__is_transparent<_Compare, _K2>::value,pair<const_iterator,const_iterator>>::type
  1649. equal_range(const _K2& __k) const {return __tree_.__equal_range_multi(__k);}
  1650. #endif
  1651. private:
  1652. typedef typename __base::__node __node;
  1653. typedef typename __base::__node_allocator __node_allocator;
  1654. typedef typename __base::__node_pointer __node_pointer;
  1655. typedef __map_node_destructor<__node_allocator> _Dp;
  1656. typedef unique_ptr<__node, _Dp> __node_holder;
  1657. };
  1658. #ifndef _LIBCPP_CXX03_LANG
  1659. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1660. multimap<_Key, _Tp, _Compare, _Allocator>::multimap(multimap&& __m, const allocator_type& __a)
  1661. : __tree_(_VSTD::move(__m.__tree_), typename __base::allocator_type(__a))
  1662. {
  1663. if (__a != __m.get_allocator())
  1664. {
  1665. const_iterator __e = cend();
  1666. while (!__m.empty())
  1667. __tree_.__insert_multi(__e.__i_,
  1668. _VSTD::move(__m.__tree_.remove(__m.begin().__i_)->__value_.__nc));
  1669. }
  1670. }
  1671. #endif
  1672. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1673. inline _LIBCPP_INLINE_VISIBILITY
  1674. bool
  1675. operator==(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1676. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1677. {
  1678. return __x.size() == __y.size() && _VSTD::equal(__x.begin(), __x.end(), __y.begin());
  1679. }
  1680. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1681. inline _LIBCPP_INLINE_VISIBILITY
  1682. bool
  1683. operator< (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1684. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1685. {
  1686. return _VSTD::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
  1687. }
  1688. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1689. inline _LIBCPP_INLINE_VISIBILITY
  1690. bool
  1691. operator!=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1692. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1693. {
  1694. return !(__x == __y);
  1695. }
  1696. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1697. inline _LIBCPP_INLINE_VISIBILITY
  1698. bool
  1699. operator> (const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1700. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1701. {
  1702. return __y < __x;
  1703. }
  1704. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1705. inline _LIBCPP_INLINE_VISIBILITY
  1706. bool
  1707. operator>=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1708. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1709. {
  1710. return !(__x < __y);
  1711. }
  1712. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1713. inline _LIBCPP_INLINE_VISIBILITY
  1714. bool
  1715. operator<=(const multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1716. const multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1717. {
  1718. return !(__y < __x);
  1719. }
  1720. template <class _Key, class _Tp, class _Compare, class _Allocator>
  1721. inline _LIBCPP_INLINE_VISIBILITY
  1722. void
  1723. swap(multimap<_Key, _Tp, _Compare, _Allocator>& __x,
  1724. multimap<_Key, _Tp, _Compare, _Allocator>& __y)
  1725. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  1726. {
  1727. __x.swap(__y);
  1728. }
  1729. _LIBCPP_END_NAMESPACE_STD
  1730. #endif // _LIBCPP_MAP