unordered_set 54 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388
  1. // -*- C++ -*-
  2. //===-------------------------- unordered_set -----------------------------===//
  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_UNORDERED_SET
  11. #define _LIBCPP_UNORDERED_SET
  12. /*
  13. unordered_set synopsis
  14. #include <initializer_list>
  15. namespace std
  16. {
  17. template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  18. class Alloc = allocator<Value>>
  19. class unordered_set
  20. {
  21. public:
  22. // types
  23. typedef Value key_type;
  24. typedef key_type value_type;
  25. typedef Hash hasher;
  26. typedef Pred key_equal;
  27. typedef Alloc allocator_type;
  28. typedef value_type& reference;
  29. typedef const value_type& const_reference;
  30. typedef typename allocator_traits<allocator_type>::pointer pointer;
  31. typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
  32. typedef typename allocator_traits<allocator_type>::size_type size_type;
  33. typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  34. typedef /unspecified/ iterator;
  35. typedef /unspecified/ const_iterator;
  36. typedef /unspecified/ local_iterator;
  37. typedef /unspecified/ const_local_iterator;
  38. unordered_set()
  39. noexcept(
  40. is_nothrow_default_constructible<hasher>::value &&
  41. is_nothrow_default_constructible<key_equal>::value &&
  42. is_nothrow_default_constructible<allocator_type>::value);
  43. explicit unordered_set(size_type n, const hasher& hf = hasher(),
  44. const key_equal& eql = key_equal(),
  45. const allocator_type& a = allocator_type());
  46. template <class InputIterator>
  47. unordered_set(InputIterator f, InputIterator l,
  48. size_type n = 0, const hasher& hf = hasher(),
  49. const key_equal& eql = key_equal(),
  50. const allocator_type& a = allocator_type());
  51. explicit unordered_set(const allocator_type&);
  52. unordered_set(const unordered_set&);
  53. unordered_set(const unordered_set&, const Allocator&);
  54. unordered_set(unordered_set&&)
  55. noexcept(
  56. is_nothrow_move_constructible<hasher>::value &&
  57. is_nothrow_move_constructible<key_equal>::value &&
  58. is_nothrow_move_constructible<allocator_type>::value);
  59. unordered_set(unordered_set&&, const Allocator&);
  60. unordered_set(initializer_list<value_type>, size_type n = 0,
  61. const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  62. const allocator_type& a = allocator_type());
  63. unordered_set(size_type n, const allocator_type& a); // C++14
  64. unordered_set(size_type n, const hasher& hf, const allocator_type& a); // C++14
  65. template <class InputIterator>
  66. unordered_set(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
  67. template <class InputIterator>
  68. unordered_set(InputIterator f, InputIterator l, size_type n,
  69. const hasher& hf, const allocator_type& a); // C++14
  70. unordered_set(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
  71. unordered_set(initializer_list<value_type> il, size_type n,
  72. const hasher& hf, const allocator_type& a); // C++14
  73. ~unordered_set();
  74. unordered_set& operator=(const unordered_set&);
  75. unordered_set& operator=(unordered_set&&)
  76. noexcept(
  77. allocator_type::propagate_on_container_move_assignment::value &&
  78. is_nothrow_move_assignable<allocator_type>::value &&
  79. is_nothrow_move_assignable<hasher>::value &&
  80. is_nothrow_move_assignable<key_equal>::value);
  81. unordered_set& operator=(initializer_list<value_type>);
  82. allocator_type get_allocator() const noexcept;
  83. bool empty() const noexcept;
  84. size_type size() const noexcept;
  85. size_type max_size() const noexcept;
  86. iterator begin() noexcept;
  87. iterator end() noexcept;
  88. const_iterator begin() const noexcept;
  89. const_iterator end() const noexcept;
  90. const_iterator cbegin() const noexcept;
  91. const_iterator cend() const noexcept;
  92. template <class... Args>
  93. pair<iterator, bool> emplace(Args&&... args);
  94. template <class... Args>
  95. iterator emplace_hint(const_iterator position, Args&&... args);
  96. pair<iterator, bool> insert(const value_type& obj);
  97. pair<iterator, bool> insert(value_type&& obj);
  98. iterator insert(const_iterator hint, const value_type& obj);
  99. iterator insert(const_iterator hint, value_type&& obj);
  100. template <class InputIterator>
  101. void insert(InputIterator first, InputIterator last);
  102. void insert(initializer_list<value_type>);
  103. iterator erase(const_iterator position);
  104. iterator erase(iterator position); // C++14
  105. size_type erase(const key_type& k);
  106. iterator erase(const_iterator first, const_iterator last);
  107. void clear() noexcept;
  108. void swap(unordered_set&)
  109. noexcept(allocator_traits<Allocator>::is_always_equal::value &&
  110. noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
  111. noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
  112. hasher hash_function() const;
  113. key_equal key_eq() const;
  114. iterator find(const key_type& k);
  115. const_iterator find(const key_type& k) const;
  116. size_type count(const key_type& k) const;
  117. pair<iterator, iterator> equal_range(const key_type& k);
  118. pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
  119. size_type bucket_count() const noexcept;
  120. size_type max_bucket_count() const noexcept;
  121. size_type bucket_size(size_type n) const;
  122. size_type bucket(const key_type& k) const;
  123. local_iterator begin(size_type n);
  124. local_iterator end(size_type n);
  125. const_local_iterator begin(size_type n) const;
  126. const_local_iterator end(size_type n) const;
  127. const_local_iterator cbegin(size_type n) const;
  128. const_local_iterator cend(size_type n) const;
  129. float load_factor() const noexcept;
  130. float max_load_factor() const noexcept;
  131. void max_load_factor(float z);
  132. void rehash(size_type n);
  133. void reserve(size_type n);
  134. };
  135. template <class Value, class Hash, class Pred, class Alloc>
  136. void swap(unordered_set<Value, Hash, Pred, Alloc>& x,
  137. unordered_set<Value, Hash, Pred, Alloc>& y)
  138. noexcept(noexcept(x.swap(y)));
  139. template <class Value, class Hash, class Pred, class Alloc>
  140. bool
  141. operator==(const unordered_set<Value, Hash, Pred, Alloc>& x,
  142. const unordered_set<Value, Hash, Pred, Alloc>& y);
  143. template <class Value, class Hash, class Pred, class Alloc>
  144. bool
  145. operator!=(const unordered_set<Value, Hash, Pred, Alloc>& x,
  146. const unordered_set<Value, Hash, Pred, Alloc>& y);
  147. template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
  148. class Alloc = allocator<Value>>
  149. class unordered_multiset
  150. {
  151. public:
  152. // types
  153. typedef Value key_type;
  154. typedef key_type value_type;
  155. typedef Hash hasher;
  156. typedef Pred key_equal;
  157. typedef Alloc allocator_type;
  158. typedef value_type& reference;
  159. typedef const value_type& const_reference;
  160. typedef typename allocator_traits<allocator_type>::pointer pointer;
  161. typedef typename allocator_traits<allocator_type>::const_pointer const_pointer;
  162. typedef typename allocator_traits<allocator_type>::size_type size_type;
  163. typedef typename allocator_traits<allocator_type>::difference_type difference_type;
  164. typedef /unspecified/ iterator;
  165. typedef /unspecified/ const_iterator;
  166. typedef /unspecified/ local_iterator;
  167. typedef /unspecified/ const_local_iterator;
  168. unordered_multiset()
  169. noexcept(
  170. is_nothrow_default_constructible<hasher>::value &&
  171. is_nothrow_default_constructible<key_equal>::value &&
  172. is_nothrow_default_constructible<allocator_type>::value);
  173. explicit unordered_multiset(size_type n, const hasher& hf = hasher(),
  174. const key_equal& eql = key_equal(),
  175. const allocator_type& a = allocator_type());
  176. template <class InputIterator>
  177. unordered_multiset(InputIterator f, InputIterator l,
  178. size_type n = 0, const hasher& hf = hasher(),
  179. const key_equal& eql = key_equal(),
  180. const allocator_type& a = allocator_type());
  181. explicit unordered_multiset(const allocator_type&);
  182. unordered_multiset(const unordered_multiset&);
  183. unordered_multiset(const unordered_multiset&, const Allocator&);
  184. unordered_multiset(unordered_multiset&&)
  185. noexcept(
  186. is_nothrow_move_constructible<hasher>::value &&
  187. is_nothrow_move_constructible<key_equal>::value &&
  188. is_nothrow_move_constructible<allocator_type>::value);
  189. unordered_multiset(unordered_multiset&&, const Allocator&);
  190. unordered_multiset(initializer_list<value_type>, size_type n = /see below/,
  191. const hasher& hf = hasher(), const key_equal& eql = key_equal(),
  192. const allocator_type& a = allocator_type());
  193. unordered_multiset(size_type n, const allocator_type& a); // C++14
  194. unordered_multiset(size_type n, const hasher& hf, const allocator_type& a); // C++14
  195. template <class InputIterator>
  196. unordered_multiset(InputIterator f, InputIterator l, size_type n, const allocator_type& a); // C++14
  197. template <class InputIterator>
  198. unordered_multiset(InputIterator f, InputIterator l, size_type n,
  199. const hasher& hf, const allocator_type& a); // C++14
  200. unordered_multiset(initializer_list<value_type> il, size_type n, const allocator_type& a); // C++14
  201. unordered_multiset(initializer_list<value_type> il, size_type n,
  202. const hasher& hf, const allocator_type& a); // C++14
  203. ~unordered_multiset();
  204. unordered_multiset& operator=(const unordered_multiset&);
  205. unordered_multiset& operator=(unordered_multiset&&)
  206. noexcept(
  207. allocator_type::propagate_on_container_move_assignment::value &&
  208. is_nothrow_move_assignable<allocator_type>::value &&
  209. is_nothrow_move_assignable<hasher>::value &&
  210. is_nothrow_move_assignable<key_equal>::value);
  211. unordered_multiset& operator=(initializer_list<value_type>);
  212. allocator_type get_allocator() const noexcept;
  213. bool empty() const noexcept;
  214. size_type size() const noexcept;
  215. size_type max_size() const noexcept;
  216. iterator begin() noexcept;
  217. iterator end() noexcept;
  218. const_iterator begin() const noexcept;
  219. const_iterator end() const noexcept;
  220. const_iterator cbegin() const noexcept;
  221. const_iterator cend() const noexcept;
  222. template <class... Args>
  223. iterator emplace(Args&&... args);
  224. template <class... Args>
  225. iterator emplace_hint(const_iterator position, Args&&... args);
  226. iterator insert(const value_type& obj);
  227. iterator insert(value_type&& obj);
  228. iterator insert(const_iterator hint, const value_type& obj);
  229. iterator insert(const_iterator hint, value_type&& obj);
  230. template <class InputIterator>
  231. void insert(InputIterator first, InputIterator last);
  232. void insert(initializer_list<value_type>);
  233. iterator erase(const_iterator position);
  234. iterator erase(iterator position); // C++14
  235. size_type erase(const key_type& k);
  236. iterator erase(const_iterator first, const_iterator last);
  237. void clear() noexcept;
  238. void swap(unordered_multiset&)
  239. noexcept(allocator_traits<Allocator>::is_always_equal::value &&
  240. noexcept(swap(declval<hasher&>(), declval<hasher&>())) &&
  241. noexcept(swap(declval<key_equal&>(), declval<key_equal&>()))); // C++17
  242. hasher hash_function() const;
  243. key_equal key_eq() const;
  244. iterator find(const key_type& k);
  245. const_iterator find(const key_type& k) const;
  246. size_type count(const key_type& k) const;
  247. pair<iterator, iterator> equal_range(const key_type& k);
  248. pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
  249. size_type bucket_count() const noexcept;
  250. size_type max_bucket_count() const noexcept;
  251. size_type bucket_size(size_type n) const;
  252. size_type bucket(const key_type& k) const;
  253. local_iterator begin(size_type n);
  254. local_iterator end(size_type n);
  255. const_local_iterator begin(size_type n) const;
  256. const_local_iterator end(size_type n) const;
  257. const_local_iterator cbegin(size_type n) const;
  258. const_local_iterator cend(size_type n) const;
  259. float load_factor() const noexcept;
  260. float max_load_factor() const noexcept;
  261. void max_load_factor(float z);
  262. void rehash(size_type n);
  263. void reserve(size_type n);
  264. };
  265. template <class Value, class Hash, class Pred, class Alloc>
  266. void swap(unordered_multiset<Value, Hash, Pred, Alloc>& x,
  267. unordered_multiset<Value, Hash, Pred, Alloc>& y)
  268. noexcept(noexcept(x.swap(y)));
  269. template <class Value, class Hash, class Pred, class Alloc>
  270. bool
  271. operator==(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
  272. const unordered_multiset<Value, Hash, Pred, Alloc>& y);
  273. template <class Value, class Hash, class Pred, class Alloc>
  274. bool
  275. operator!=(const unordered_multiset<Value, Hash, Pred, Alloc>& x,
  276. const unordered_multiset<Value, Hash, Pred, Alloc>& y);
  277. } // std
  278. */
  279. #include <__config>
  280. #include <__hash_table>
  281. #include <functional>
  282. #include <__debug>
  283. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  284. #pragma GCC system_header
  285. #endif
  286. _LIBCPP_BEGIN_NAMESPACE_STD
  287. template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
  288. class _Alloc = allocator<_Value> >
  289. class _LIBCPP_TYPE_VIS_ONLY unordered_set
  290. {
  291. public:
  292. // types
  293. typedef _Value key_type;
  294. typedef key_type value_type;
  295. typedef _Hash hasher;
  296. typedef _Pred key_equal;
  297. typedef _Alloc allocator_type;
  298. typedef value_type& reference;
  299. typedef const value_type& const_reference;
  300. static_assert((is_same<value_type, typename allocator_type::value_type>::value),
  301. "Invalid allocator::value_type");
  302. private:
  303. typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
  304. __table __table_;
  305. public:
  306. typedef typename __table::pointer pointer;
  307. typedef typename __table::const_pointer const_pointer;
  308. typedef typename __table::size_type size_type;
  309. typedef typename __table::difference_type difference_type;
  310. typedef typename __table::const_iterator iterator;
  311. typedef typename __table::const_iterator const_iterator;
  312. typedef typename __table::const_local_iterator local_iterator;
  313. typedef typename __table::const_local_iterator const_local_iterator;
  314. _LIBCPP_INLINE_VISIBILITY
  315. unordered_set()
  316. _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
  317. {
  318. #if _LIBCPP_DEBUG_LEVEL >= 2
  319. __get_db()->__insert_c(this);
  320. #endif
  321. }
  322. explicit unordered_set(size_type __n, const hasher& __hf = hasher(),
  323. const key_equal& __eql = key_equal());
  324. #if _LIBCPP_STD_VER > 11
  325. inline _LIBCPP_INLINE_VISIBILITY
  326. unordered_set(size_type __n, const allocator_type& __a)
  327. : unordered_set(__n, hasher(), key_equal(), __a) {}
  328. inline _LIBCPP_INLINE_VISIBILITY
  329. unordered_set(size_type __n, const hasher& __hf, const allocator_type& __a)
  330. : unordered_set(__n, __hf, key_equal(), __a) {}
  331. #endif
  332. unordered_set(size_type __n, const hasher& __hf, const key_equal& __eql,
  333. const allocator_type& __a);
  334. template <class _InputIterator>
  335. unordered_set(_InputIterator __first, _InputIterator __last);
  336. template <class _InputIterator>
  337. unordered_set(_InputIterator __first, _InputIterator __last,
  338. size_type __n, const hasher& __hf = hasher(),
  339. const key_equal& __eql = key_equal());
  340. template <class _InputIterator>
  341. unordered_set(_InputIterator __first, _InputIterator __last,
  342. size_type __n, const hasher& __hf, const key_equal& __eql,
  343. const allocator_type& __a);
  344. #if _LIBCPP_STD_VER > 11
  345. template <class _InputIterator>
  346. inline _LIBCPP_INLINE_VISIBILITY
  347. unordered_set(_InputIterator __first, _InputIterator __last,
  348. size_type __n, const allocator_type& __a)
  349. : unordered_set(__first, __last, __n, hasher(), key_equal(), __a) {}
  350. template <class _InputIterator>
  351. unordered_set(_InputIterator __first, _InputIterator __last,
  352. size_type __n, const hasher& __hf, const allocator_type& __a)
  353. : unordered_set(__first, __last, __n, __hf, key_equal(), __a) {}
  354. #endif
  355. _LIBCPP_INLINE_VISIBILITY
  356. explicit unordered_set(const allocator_type& __a);
  357. unordered_set(const unordered_set& __u);
  358. unordered_set(const unordered_set& __u, const allocator_type& __a);
  359. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  360. _LIBCPP_INLINE_VISIBILITY
  361. unordered_set(unordered_set&& __u)
  362. _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
  363. unordered_set(unordered_set&& __u, const allocator_type& __a);
  364. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  365. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  366. unordered_set(initializer_list<value_type> __il);
  367. unordered_set(initializer_list<value_type> __il, size_type __n,
  368. const hasher& __hf = hasher(),
  369. const key_equal& __eql = key_equal());
  370. unordered_set(initializer_list<value_type> __il, size_type __n,
  371. const hasher& __hf, const key_equal& __eql,
  372. const allocator_type& __a);
  373. #if _LIBCPP_STD_VER > 11
  374. inline _LIBCPP_INLINE_VISIBILITY
  375. unordered_set(initializer_list<value_type> __il, size_type __n,
  376. const allocator_type& __a)
  377. : unordered_set(__il, __n, hasher(), key_equal(), __a) {}
  378. inline _LIBCPP_INLINE_VISIBILITY
  379. unordered_set(initializer_list<value_type> __il, size_type __n,
  380. const hasher& __hf, const allocator_type& __a)
  381. : unordered_set(__il, __n, __hf, key_equal(), __a) {}
  382. #endif
  383. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  384. // ~unordered_set() = default;
  385. _LIBCPP_INLINE_VISIBILITY
  386. unordered_set& operator=(const unordered_set& __u)
  387. {
  388. __table_ = __u.__table_;
  389. return *this;
  390. }
  391. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  392. _LIBCPP_INLINE_VISIBILITY
  393. unordered_set& operator=(unordered_set&& __u)
  394. _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
  395. #endif
  396. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  397. _LIBCPP_INLINE_VISIBILITY
  398. unordered_set& operator=(initializer_list<value_type> __il);
  399. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  400. _LIBCPP_INLINE_VISIBILITY
  401. allocator_type get_allocator() const _NOEXCEPT
  402. {return allocator_type(__table_.__node_alloc());}
  403. _LIBCPP_INLINE_VISIBILITY
  404. bool empty() const _NOEXCEPT {return __table_.size() == 0;}
  405. _LIBCPP_INLINE_VISIBILITY
  406. size_type size() const _NOEXCEPT {return __table_.size();}
  407. _LIBCPP_INLINE_VISIBILITY
  408. size_type max_size() const _NOEXCEPT {return __table_.max_size();}
  409. _LIBCPP_INLINE_VISIBILITY
  410. iterator begin() _NOEXCEPT {return __table_.begin();}
  411. _LIBCPP_INLINE_VISIBILITY
  412. iterator end() _NOEXCEPT {return __table_.end();}
  413. _LIBCPP_INLINE_VISIBILITY
  414. const_iterator begin() const _NOEXCEPT {return __table_.begin();}
  415. _LIBCPP_INLINE_VISIBILITY
  416. const_iterator end() const _NOEXCEPT {return __table_.end();}
  417. _LIBCPP_INLINE_VISIBILITY
  418. const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
  419. _LIBCPP_INLINE_VISIBILITY
  420. const_iterator cend() const _NOEXCEPT {return __table_.end();}
  421. #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
  422. template <class... _Args>
  423. _LIBCPP_INLINE_VISIBILITY
  424. pair<iterator, bool> emplace(_Args&&... __args)
  425. {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...);}
  426. template <class... _Args>
  427. _LIBCPP_INLINE_VISIBILITY
  428. #if _LIBCPP_DEBUG_LEVEL >= 2
  429. iterator emplace_hint(const_iterator __p, _Args&&... __args)
  430. {
  431. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
  432. "unordered_set::emplace_hint(const_iterator, args...) called with an iterator not"
  433. " referring to this unordered_set");
  434. return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;
  435. }
  436. #else
  437. iterator emplace_hint(const_iterator, _Args&&... __args)
  438. {return __table_.__emplace_unique(_VSTD::forward<_Args>(__args)...).first;}
  439. #endif
  440. #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
  441. _LIBCPP_INLINE_VISIBILITY
  442. pair<iterator, bool> insert(const value_type& __x)
  443. {return __table_.__insert_unique(__x);}
  444. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  445. _LIBCPP_INLINE_VISIBILITY
  446. pair<iterator, bool> insert(value_type&& __x)
  447. {return __table_.__insert_unique(_VSTD::move(__x));}
  448. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  449. _LIBCPP_INLINE_VISIBILITY
  450. #if _LIBCPP_DEBUG_LEVEL >= 2
  451. iterator insert(const_iterator __p, const value_type& __x)
  452. {
  453. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
  454. "unordered_set::insert(const_iterator, const value_type&) called with an iterator not"
  455. " referring to this unordered_set");
  456. return insert(__x).first;
  457. }
  458. #else
  459. iterator insert(const_iterator, const value_type& __x)
  460. {return insert(__x).first;}
  461. #endif
  462. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  463. _LIBCPP_INLINE_VISIBILITY
  464. #if _LIBCPP_DEBUG_LEVEL >= 2
  465. iterator insert(const_iterator __p, value_type&& __x)
  466. {
  467. _LIBCPP_ASSERT(__get_const_db()->__find_c_from_i(&__p) == this,
  468. "unordered_set::insert(const_iterator, value_type&&) called with an iterator not"
  469. " referring to this unordered_set");
  470. return insert(_VSTD::move(__x)).first;
  471. }
  472. #else
  473. iterator insert(const_iterator, value_type&& __x)
  474. {return insert(_VSTD::move(__x)).first;}
  475. #endif
  476. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  477. template <class _InputIterator>
  478. _LIBCPP_INLINE_VISIBILITY
  479. void insert(_InputIterator __first, _InputIterator __last);
  480. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  481. _LIBCPP_INLINE_VISIBILITY
  482. void insert(initializer_list<value_type> __il)
  483. {insert(__il.begin(), __il.end());}
  484. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  485. _LIBCPP_INLINE_VISIBILITY
  486. iterator erase(const_iterator __p) {return __table_.erase(__p);}
  487. _LIBCPP_INLINE_VISIBILITY
  488. size_type erase(const key_type& __k) {return __table_.__erase_unique(__k);}
  489. _LIBCPP_INLINE_VISIBILITY
  490. iterator erase(const_iterator __first, const_iterator __last)
  491. {return __table_.erase(__first, __last);}
  492. _LIBCPP_INLINE_VISIBILITY
  493. void clear() _NOEXCEPT {__table_.clear();}
  494. _LIBCPP_INLINE_VISIBILITY
  495. void swap(unordered_set& __u)
  496. _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
  497. {__table_.swap(__u.__table_);}
  498. _LIBCPP_INLINE_VISIBILITY
  499. hasher hash_function() const {return __table_.hash_function();}
  500. _LIBCPP_INLINE_VISIBILITY
  501. key_equal key_eq() const {return __table_.key_eq();}
  502. _LIBCPP_INLINE_VISIBILITY
  503. iterator find(const key_type& __k) {return __table_.find(__k);}
  504. _LIBCPP_INLINE_VISIBILITY
  505. const_iterator find(const key_type& __k) const {return __table_.find(__k);}
  506. _LIBCPP_INLINE_VISIBILITY
  507. size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
  508. _LIBCPP_INLINE_VISIBILITY
  509. pair<iterator, iterator> equal_range(const key_type& __k)
  510. {return __table_.__equal_range_unique(__k);}
  511. _LIBCPP_INLINE_VISIBILITY
  512. pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
  513. {return __table_.__equal_range_unique(__k);}
  514. _LIBCPP_INLINE_VISIBILITY
  515. size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
  516. _LIBCPP_INLINE_VISIBILITY
  517. size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
  518. _LIBCPP_INLINE_VISIBILITY
  519. size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
  520. _LIBCPP_INLINE_VISIBILITY
  521. size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
  522. _LIBCPP_INLINE_VISIBILITY
  523. local_iterator begin(size_type __n) {return __table_.begin(__n);}
  524. _LIBCPP_INLINE_VISIBILITY
  525. local_iterator end(size_type __n) {return __table_.end(__n);}
  526. _LIBCPP_INLINE_VISIBILITY
  527. const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
  528. _LIBCPP_INLINE_VISIBILITY
  529. const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
  530. _LIBCPP_INLINE_VISIBILITY
  531. const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
  532. _LIBCPP_INLINE_VISIBILITY
  533. const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
  534. _LIBCPP_INLINE_VISIBILITY
  535. float load_factor() const _NOEXCEPT {return __table_.load_factor();}
  536. _LIBCPP_INLINE_VISIBILITY
  537. float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
  538. _LIBCPP_INLINE_VISIBILITY
  539. void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
  540. _LIBCPP_INLINE_VISIBILITY
  541. void rehash(size_type __n) {__table_.rehash(__n);}
  542. _LIBCPP_INLINE_VISIBILITY
  543. void reserve(size_type __n) {__table_.reserve(__n);}
  544. #if _LIBCPP_DEBUG_LEVEL >= 2
  545. bool __dereferenceable(const const_iterator* __i) const
  546. {return __table_.__dereferenceable(__i);}
  547. bool __decrementable(const const_iterator* __i) const
  548. {return __table_.__decrementable(__i);}
  549. bool __addable(const const_iterator* __i, ptrdiff_t __n) const
  550. {return __table_.__addable(__i, __n);}
  551. bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
  552. {return __table_.__addable(__i, __n);}
  553. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  554. };
  555. template <class _Value, class _Hash, class _Pred, class _Alloc>
  556. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
  557. const hasher& __hf, const key_equal& __eql)
  558. : __table_(__hf, __eql)
  559. {
  560. #if _LIBCPP_DEBUG_LEVEL >= 2
  561. __get_db()->__insert_c(this);
  562. #endif
  563. __table_.rehash(__n);
  564. }
  565. template <class _Value, class _Hash, class _Pred, class _Alloc>
  566. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(size_type __n,
  567. const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
  568. : __table_(__hf, __eql, __a)
  569. {
  570. #if _LIBCPP_DEBUG_LEVEL >= 2
  571. __get_db()->__insert_c(this);
  572. #endif
  573. __table_.rehash(__n);
  574. }
  575. template <class _Value, class _Hash, class _Pred, class _Alloc>
  576. template <class _InputIterator>
  577. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  578. _InputIterator __first, _InputIterator __last)
  579. {
  580. #if _LIBCPP_DEBUG_LEVEL >= 2
  581. __get_db()->__insert_c(this);
  582. #endif
  583. insert(__first, __last);
  584. }
  585. template <class _Value, class _Hash, class _Pred, class _Alloc>
  586. template <class _InputIterator>
  587. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  588. _InputIterator __first, _InputIterator __last, size_type __n,
  589. const hasher& __hf, const key_equal& __eql)
  590. : __table_(__hf, __eql)
  591. {
  592. #if _LIBCPP_DEBUG_LEVEL >= 2
  593. __get_db()->__insert_c(this);
  594. #endif
  595. __table_.rehash(__n);
  596. insert(__first, __last);
  597. }
  598. template <class _Value, class _Hash, class _Pred, class _Alloc>
  599. template <class _InputIterator>
  600. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  601. _InputIterator __first, _InputIterator __last, size_type __n,
  602. const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
  603. : __table_(__hf, __eql, __a)
  604. {
  605. #if _LIBCPP_DEBUG_LEVEL >= 2
  606. __get_db()->__insert_c(this);
  607. #endif
  608. __table_.rehash(__n);
  609. insert(__first, __last);
  610. }
  611. template <class _Value, class _Hash, class _Pred, class _Alloc>
  612. inline
  613. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  614. const allocator_type& __a)
  615. : __table_(__a)
  616. {
  617. #if _LIBCPP_DEBUG_LEVEL >= 2
  618. __get_db()->__insert_c(this);
  619. #endif
  620. }
  621. template <class _Value, class _Hash, class _Pred, class _Alloc>
  622. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  623. const unordered_set& __u)
  624. : __table_(__u.__table_)
  625. {
  626. #if _LIBCPP_DEBUG_LEVEL >= 2
  627. __get_db()->__insert_c(this);
  628. #endif
  629. __table_.rehash(__u.bucket_count());
  630. insert(__u.begin(), __u.end());
  631. }
  632. template <class _Value, class _Hash, class _Pred, class _Alloc>
  633. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  634. const unordered_set& __u, const allocator_type& __a)
  635. : __table_(__u.__table_, __a)
  636. {
  637. #if _LIBCPP_DEBUG_LEVEL >= 2
  638. __get_db()->__insert_c(this);
  639. #endif
  640. __table_.rehash(__u.bucket_count());
  641. insert(__u.begin(), __u.end());
  642. }
  643. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  644. template <class _Value, class _Hash, class _Pred, class _Alloc>
  645. inline
  646. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  647. unordered_set&& __u)
  648. _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
  649. : __table_(_VSTD::move(__u.__table_))
  650. {
  651. #if _LIBCPP_DEBUG_LEVEL >= 2
  652. __get_db()->__insert_c(this);
  653. __get_db()->swap(this, &__u);
  654. #endif
  655. }
  656. template <class _Value, class _Hash, class _Pred, class _Alloc>
  657. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  658. unordered_set&& __u, const allocator_type& __a)
  659. : __table_(_VSTD::move(__u.__table_), __a)
  660. {
  661. #if _LIBCPP_DEBUG_LEVEL >= 2
  662. __get_db()->__insert_c(this);
  663. #endif
  664. if (__a != __u.get_allocator())
  665. {
  666. iterator __i = __u.begin();
  667. while (__u.size() != 0)
  668. __table_.__insert_unique(_VSTD::move(__u.__table_.remove(__i++)->__value_));
  669. }
  670. #if _LIBCPP_DEBUG_LEVEL >= 2
  671. else
  672. __get_db()->swap(this, &__u);
  673. #endif
  674. }
  675. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  676. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  677. template <class _Value, class _Hash, class _Pred, class _Alloc>
  678. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  679. initializer_list<value_type> __il)
  680. {
  681. #if _LIBCPP_DEBUG_LEVEL >= 2
  682. __get_db()->__insert_c(this);
  683. #endif
  684. insert(__il.begin(), __il.end());
  685. }
  686. template <class _Value, class _Hash, class _Pred, class _Alloc>
  687. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  688. initializer_list<value_type> __il, size_type __n, const hasher& __hf,
  689. const key_equal& __eql)
  690. : __table_(__hf, __eql)
  691. {
  692. #if _LIBCPP_DEBUG_LEVEL >= 2
  693. __get_db()->__insert_c(this);
  694. #endif
  695. __table_.rehash(__n);
  696. insert(__il.begin(), __il.end());
  697. }
  698. template <class _Value, class _Hash, class _Pred, class _Alloc>
  699. unordered_set<_Value, _Hash, _Pred, _Alloc>::unordered_set(
  700. initializer_list<value_type> __il, size_type __n, const hasher& __hf,
  701. const key_equal& __eql, const allocator_type& __a)
  702. : __table_(__hf, __eql, __a)
  703. {
  704. #if _LIBCPP_DEBUG_LEVEL >= 2
  705. __get_db()->__insert_c(this);
  706. #endif
  707. __table_.rehash(__n);
  708. insert(__il.begin(), __il.end());
  709. }
  710. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  711. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  712. template <class _Value, class _Hash, class _Pred, class _Alloc>
  713. inline
  714. unordered_set<_Value, _Hash, _Pred, _Alloc>&
  715. unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(unordered_set&& __u)
  716. _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
  717. {
  718. __table_ = _VSTD::move(__u.__table_);
  719. return *this;
  720. }
  721. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  722. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  723. template <class _Value, class _Hash, class _Pred, class _Alloc>
  724. inline
  725. unordered_set<_Value, _Hash, _Pred, _Alloc>&
  726. unordered_set<_Value, _Hash, _Pred, _Alloc>::operator=(
  727. initializer_list<value_type> __il)
  728. {
  729. __table_.__assign_unique(__il.begin(), __il.end());
  730. return *this;
  731. }
  732. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  733. template <class _Value, class _Hash, class _Pred, class _Alloc>
  734. template <class _InputIterator>
  735. inline
  736. void
  737. unordered_set<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
  738. _InputIterator __last)
  739. {
  740. for (; __first != __last; ++__first)
  741. __table_.__insert_unique(*__first);
  742. }
  743. template <class _Value, class _Hash, class _Pred, class _Alloc>
  744. inline _LIBCPP_INLINE_VISIBILITY
  745. void
  746. swap(unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  747. unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  748. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  749. {
  750. __x.swap(__y);
  751. }
  752. template <class _Value, class _Hash, class _Pred, class _Alloc>
  753. bool
  754. operator==(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  755. const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  756. {
  757. if (__x.size() != __y.size())
  758. return false;
  759. typedef typename unordered_set<_Value, _Hash, _Pred, _Alloc>::const_iterator
  760. const_iterator;
  761. for (const_iterator __i = __x.begin(), __ex = __x.end(), __ey = __y.end();
  762. __i != __ex; ++__i)
  763. {
  764. const_iterator __j = __y.find(*__i);
  765. if (__j == __ey || !(*__i == *__j))
  766. return false;
  767. }
  768. return true;
  769. }
  770. template <class _Value, class _Hash, class _Pred, class _Alloc>
  771. inline _LIBCPP_INLINE_VISIBILITY
  772. bool
  773. operator!=(const unordered_set<_Value, _Hash, _Pred, _Alloc>& __x,
  774. const unordered_set<_Value, _Hash, _Pred, _Alloc>& __y)
  775. {
  776. return !(__x == __y);
  777. }
  778. template <class _Value, class _Hash = hash<_Value>, class _Pred = equal_to<_Value>,
  779. class _Alloc = allocator<_Value> >
  780. class _LIBCPP_TYPE_VIS_ONLY unordered_multiset
  781. {
  782. public:
  783. // types
  784. typedef _Value key_type;
  785. typedef key_type value_type;
  786. typedef _Hash hasher;
  787. typedef _Pred key_equal;
  788. typedef _Alloc allocator_type;
  789. typedef value_type& reference;
  790. typedef const value_type& const_reference;
  791. static_assert((is_same<value_type, typename allocator_type::value_type>::value),
  792. "Invalid allocator::value_type");
  793. private:
  794. typedef __hash_table<value_type, hasher, key_equal, allocator_type> __table;
  795. __table __table_;
  796. public:
  797. typedef typename __table::pointer pointer;
  798. typedef typename __table::const_pointer const_pointer;
  799. typedef typename __table::size_type size_type;
  800. typedef typename __table::difference_type difference_type;
  801. typedef typename __table::const_iterator iterator;
  802. typedef typename __table::const_iterator const_iterator;
  803. typedef typename __table::const_local_iterator local_iterator;
  804. typedef typename __table::const_local_iterator const_local_iterator;
  805. _LIBCPP_INLINE_VISIBILITY
  806. unordered_multiset()
  807. _NOEXCEPT_(is_nothrow_default_constructible<__table>::value)
  808. {
  809. #if _LIBCPP_DEBUG_LEVEL >= 2
  810. __get_db()->__insert_c(this);
  811. #endif
  812. }
  813. explicit unordered_multiset(size_type __n, const hasher& __hf = hasher(),
  814. const key_equal& __eql = key_equal());
  815. unordered_multiset(size_type __n, const hasher& __hf,
  816. const key_equal& __eql, const allocator_type& __a);
  817. #if _LIBCPP_STD_VER > 11
  818. inline _LIBCPP_INLINE_VISIBILITY
  819. unordered_multiset(size_type __n, const allocator_type& __a)
  820. : unordered_multiset(__n, hasher(), key_equal(), __a) {}
  821. inline _LIBCPP_INLINE_VISIBILITY
  822. unordered_multiset(size_type __n, const hasher& __hf, const allocator_type& __a)
  823. : unordered_multiset(__n, __hf, key_equal(), __a) {}
  824. #endif
  825. template <class _InputIterator>
  826. unordered_multiset(_InputIterator __first, _InputIterator __last);
  827. template <class _InputIterator>
  828. unordered_multiset(_InputIterator __first, _InputIterator __last,
  829. size_type __n, const hasher& __hf = hasher(),
  830. const key_equal& __eql = key_equal());
  831. template <class _InputIterator>
  832. unordered_multiset(_InputIterator __first, _InputIterator __last,
  833. size_type __n , const hasher& __hf,
  834. const key_equal& __eql, const allocator_type& __a);
  835. #if _LIBCPP_STD_VER > 11
  836. template <class _InputIterator>
  837. inline _LIBCPP_INLINE_VISIBILITY
  838. unordered_multiset(_InputIterator __first, _InputIterator __last,
  839. size_type __n, const allocator_type& __a)
  840. : unordered_multiset(__first, __last, __n, hasher(), key_equal(), __a) {}
  841. template <class _InputIterator>
  842. inline _LIBCPP_INLINE_VISIBILITY
  843. unordered_multiset(_InputIterator __first, _InputIterator __last,
  844. size_type __n, const hasher& __hf, const allocator_type& __a)
  845. : unordered_multiset(__first, __last, __n, __hf, key_equal(), __a) {}
  846. #endif
  847. _LIBCPP_INLINE_VISIBILITY
  848. explicit unordered_multiset(const allocator_type& __a);
  849. unordered_multiset(const unordered_multiset& __u);
  850. unordered_multiset(const unordered_multiset& __u, const allocator_type& __a);
  851. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  852. _LIBCPP_INLINE_VISIBILITY
  853. unordered_multiset(unordered_multiset&& __u)
  854. _NOEXCEPT_(is_nothrow_move_constructible<__table>::value);
  855. unordered_multiset(unordered_multiset&& __u, const allocator_type& __a);
  856. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  857. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  858. unordered_multiset(initializer_list<value_type> __il);
  859. unordered_multiset(initializer_list<value_type> __il, size_type __n,
  860. const hasher& __hf = hasher(),
  861. const key_equal& __eql = key_equal());
  862. unordered_multiset(initializer_list<value_type> __il, size_type __n,
  863. const hasher& __hf, const key_equal& __eql,
  864. const allocator_type& __a);
  865. #if _LIBCPP_STD_VER > 11
  866. inline _LIBCPP_INLINE_VISIBILITY
  867. unordered_multiset(initializer_list<value_type> __il, size_type __n, const allocator_type& __a)
  868. : unordered_multiset(__il, __n, hasher(), key_equal(), __a) {}
  869. inline _LIBCPP_INLINE_VISIBILITY
  870. unordered_multiset(initializer_list<value_type> __il, size_type __n, const hasher& __hf, const allocator_type& __a)
  871. : unordered_multiset(__il, __n, __hf, key_equal(), __a) {}
  872. #endif
  873. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  874. // ~unordered_multiset() = default;
  875. _LIBCPP_INLINE_VISIBILITY
  876. unordered_multiset& operator=(const unordered_multiset& __u)
  877. {
  878. __table_ = __u.__table_;
  879. return *this;
  880. }
  881. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  882. _LIBCPP_INLINE_VISIBILITY
  883. unordered_multiset& operator=(unordered_multiset&& __u)
  884. _NOEXCEPT_(is_nothrow_move_assignable<__table>::value);
  885. #endif
  886. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  887. unordered_multiset& operator=(initializer_list<value_type> __il);
  888. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  889. _LIBCPP_INLINE_VISIBILITY
  890. allocator_type get_allocator() const _NOEXCEPT
  891. {return allocator_type(__table_.__node_alloc());}
  892. _LIBCPP_INLINE_VISIBILITY
  893. bool empty() const _NOEXCEPT {return __table_.size() == 0;}
  894. _LIBCPP_INLINE_VISIBILITY
  895. size_type size() const _NOEXCEPT {return __table_.size();}
  896. _LIBCPP_INLINE_VISIBILITY
  897. size_type max_size() const _NOEXCEPT {return __table_.max_size();}
  898. _LIBCPP_INLINE_VISIBILITY
  899. iterator begin() _NOEXCEPT {return __table_.begin();}
  900. _LIBCPP_INLINE_VISIBILITY
  901. iterator end() _NOEXCEPT {return __table_.end();}
  902. _LIBCPP_INLINE_VISIBILITY
  903. const_iterator begin() const _NOEXCEPT {return __table_.begin();}
  904. _LIBCPP_INLINE_VISIBILITY
  905. const_iterator end() const _NOEXCEPT {return __table_.end();}
  906. _LIBCPP_INLINE_VISIBILITY
  907. const_iterator cbegin() const _NOEXCEPT {return __table_.begin();}
  908. _LIBCPP_INLINE_VISIBILITY
  909. const_iterator cend() const _NOEXCEPT {return __table_.end();}
  910. #if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
  911. template <class... _Args>
  912. _LIBCPP_INLINE_VISIBILITY
  913. iterator emplace(_Args&&... __args)
  914. {return __table_.__emplace_multi(_VSTD::forward<_Args>(__args)...);}
  915. template <class... _Args>
  916. _LIBCPP_INLINE_VISIBILITY
  917. iterator emplace_hint(const_iterator __p, _Args&&... __args)
  918. {return __table_.__emplace_hint_multi(__p, _VSTD::forward<_Args>(__args)...);}
  919. #endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS)
  920. _LIBCPP_INLINE_VISIBILITY
  921. iterator insert(const value_type& __x) {return __table_.__insert_multi(__x);}
  922. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  923. _LIBCPP_INLINE_VISIBILITY
  924. iterator insert(value_type&& __x) {return __table_.__insert_multi(_VSTD::move(__x));}
  925. #endif
  926. _LIBCPP_INLINE_VISIBILITY
  927. iterator insert(const_iterator __p, const value_type& __x)
  928. {return __table_.__insert_multi(__p, __x);}
  929. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  930. _LIBCPP_INLINE_VISIBILITY
  931. iterator insert(const_iterator __p, value_type&& __x)
  932. {return __table_.__insert_multi(__p, _VSTD::move(__x));}
  933. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  934. template <class _InputIterator>
  935. _LIBCPP_INLINE_VISIBILITY
  936. void insert(_InputIterator __first, _InputIterator __last);
  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. _LIBCPP_INLINE_VISIBILITY
  943. iterator erase(const_iterator __p) {return __table_.erase(__p);}
  944. _LIBCPP_INLINE_VISIBILITY
  945. size_type erase(const key_type& __k) {return __table_.__erase_multi(__k);}
  946. _LIBCPP_INLINE_VISIBILITY
  947. iterator erase(const_iterator __first, const_iterator __last)
  948. {return __table_.erase(__first, __last);}
  949. _LIBCPP_INLINE_VISIBILITY
  950. void clear() _NOEXCEPT {__table_.clear();}
  951. _LIBCPP_INLINE_VISIBILITY
  952. void swap(unordered_multiset& __u)
  953. _NOEXCEPT_(__is_nothrow_swappable<__table>::value)
  954. {__table_.swap(__u.__table_);}
  955. _LIBCPP_INLINE_VISIBILITY
  956. hasher hash_function() const {return __table_.hash_function();}
  957. _LIBCPP_INLINE_VISIBILITY
  958. key_equal key_eq() const {return __table_.key_eq();}
  959. _LIBCPP_INLINE_VISIBILITY
  960. iterator find(const key_type& __k) {return __table_.find(__k);}
  961. _LIBCPP_INLINE_VISIBILITY
  962. const_iterator find(const key_type& __k) const {return __table_.find(__k);}
  963. _LIBCPP_INLINE_VISIBILITY
  964. size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
  965. _LIBCPP_INLINE_VISIBILITY
  966. pair<iterator, iterator> equal_range(const key_type& __k)
  967. {return __table_.__equal_range_multi(__k);}
  968. _LIBCPP_INLINE_VISIBILITY
  969. pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
  970. {return __table_.__equal_range_multi(__k);}
  971. _LIBCPP_INLINE_VISIBILITY
  972. size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
  973. _LIBCPP_INLINE_VISIBILITY
  974. size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
  975. _LIBCPP_INLINE_VISIBILITY
  976. size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
  977. _LIBCPP_INLINE_VISIBILITY
  978. size_type bucket(const key_type& __k) const {return __table_.bucket(__k);}
  979. _LIBCPP_INLINE_VISIBILITY
  980. local_iterator begin(size_type __n) {return __table_.begin(__n);}
  981. _LIBCPP_INLINE_VISIBILITY
  982. local_iterator end(size_type __n) {return __table_.end(__n);}
  983. _LIBCPP_INLINE_VISIBILITY
  984. const_local_iterator begin(size_type __n) const {return __table_.cbegin(__n);}
  985. _LIBCPP_INLINE_VISIBILITY
  986. const_local_iterator end(size_type __n) const {return __table_.cend(__n);}
  987. _LIBCPP_INLINE_VISIBILITY
  988. const_local_iterator cbegin(size_type __n) const {return __table_.cbegin(__n);}
  989. _LIBCPP_INLINE_VISIBILITY
  990. const_local_iterator cend(size_type __n) const {return __table_.cend(__n);}
  991. _LIBCPP_INLINE_VISIBILITY
  992. float load_factor() const _NOEXCEPT {return __table_.load_factor();}
  993. _LIBCPP_INLINE_VISIBILITY
  994. float max_load_factor() const _NOEXCEPT {return __table_.max_load_factor();}
  995. _LIBCPP_INLINE_VISIBILITY
  996. void max_load_factor(float __mlf) {__table_.max_load_factor(__mlf);}
  997. _LIBCPP_INLINE_VISIBILITY
  998. void rehash(size_type __n) {__table_.rehash(__n);}
  999. _LIBCPP_INLINE_VISIBILITY
  1000. void reserve(size_type __n) {__table_.reserve(__n);}
  1001. #if _LIBCPP_DEBUG_LEVEL >= 2
  1002. bool __dereferenceable(const const_iterator* __i) const
  1003. {return __table_.__dereferenceable(__i);}
  1004. bool __decrementable(const const_iterator* __i) const
  1005. {return __table_.__decrementable(__i);}
  1006. bool __addable(const const_iterator* __i, ptrdiff_t __n) const
  1007. {return __table_.__addable(__i, __n);}
  1008. bool __subscriptable(const const_iterator* __i, ptrdiff_t __n) const
  1009. {return __table_.__addable(__i, __n);}
  1010. #endif // _LIBCPP_DEBUG_LEVEL >= 2
  1011. };
  1012. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1013. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1014. size_type __n, const hasher& __hf, const key_equal& __eql)
  1015. : __table_(__hf, __eql)
  1016. {
  1017. #if _LIBCPP_DEBUG_LEVEL >= 2
  1018. __get_db()->__insert_c(this);
  1019. #endif
  1020. __table_.rehash(__n);
  1021. }
  1022. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1023. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1024. size_type __n, const hasher& __hf, const key_equal& __eql,
  1025. const allocator_type& __a)
  1026. : __table_(__hf, __eql, __a)
  1027. {
  1028. #if _LIBCPP_DEBUG_LEVEL >= 2
  1029. __get_db()->__insert_c(this);
  1030. #endif
  1031. __table_.rehash(__n);
  1032. }
  1033. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1034. template <class _InputIterator>
  1035. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1036. _InputIterator __first, _InputIterator __last)
  1037. {
  1038. #if _LIBCPP_DEBUG_LEVEL >= 2
  1039. __get_db()->__insert_c(this);
  1040. #endif
  1041. insert(__first, __last);
  1042. }
  1043. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1044. template <class _InputIterator>
  1045. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1046. _InputIterator __first, _InputIterator __last, size_type __n,
  1047. const hasher& __hf, const key_equal& __eql)
  1048. : __table_(__hf, __eql)
  1049. {
  1050. #if _LIBCPP_DEBUG_LEVEL >= 2
  1051. __get_db()->__insert_c(this);
  1052. #endif
  1053. __table_.rehash(__n);
  1054. insert(__first, __last);
  1055. }
  1056. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1057. template <class _InputIterator>
  1058. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1059. _InputIterator __first, _InputIterator __last, size_type __n,
  1060. const hasher& __hf, const key_equal& __eql, const allocator_type& __a)
  1061. : __table_(__hf, __eql, __a)
  1062. {
  1063. #if _LIBCPP_DEBUG_LEVEL >= 2
  1064. __get_db()->__insert_c(this);
  1065. #endif
  1066. __table_.rehash(__n);
  1067. insert(__first, __last);
  1068. }
  1069. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1070. inline
  1071. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1072. const allocator_type& __a)
  1073. : __table_(__a)
  1074. {
  1075. #if _LIBCPP_DEBUG_LEVEL >= 2
  1076. __get_db()->__insert_c(this);
  1077. #endif
  1078. }
  1079. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1080. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1081. const unordered_multiset& __u)
  1082. : __table_(__u.__table_)
  1083. {
  1084. #if _LIBCPP_DEBUG_LEVEL >= 2
  1085. __get_db()->__insert_c(this);
  1086. #endif
  1087. __table_.rehash(__u.bucket_count());
  1088. insert(__u.begin(), __u.end());
  1089. }
  1090. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1091. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1092. const unordered_multiset& __u, const allocator_type& __a)
  1093. : __table_(__u.__table_, __a)
  1094. {
  1095. #if _LIBCPP_DEBUG_LEVEL >= 2
  1096. __get_db()->__insert_c(this);
  1097. #endif
  1098. __table_.rehash(__u.bucket_count());
  1099. insert(__u.begin(), __u.end());
  1100. }
  1101. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1102. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1103. inline
  1104. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1105. unordered_multiset&& __u)
  1106. _NOEXCEPT_(is_nothrow_move_constructible<__table>::value)
  1107. : __table_(_VSTD::move(__u.__table_))
  1108. {
  1109. #if _LIBCPP_DEBUG_LEVEL >= 2
  1110. __get_db()->__insert_c(this);
  1111. __get_db()->swap(this, &__u);
  1112. #endif
  1113. }
  1114. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1115. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1116. unordered_multiset&& __u, const allocator_type& __a)
  1117. : __table_(_VSTD::move(__u.__table_), __a)
  1118. {
  1119. #if _LIBCPP_DEBUG_LEVEL >= 2
  1120. __get_db()->__insert_c(this);
  1121. #endif
  1122. if (__a != __u.get_allocator())
  1123. {
  1124. iterator __i = __u.begin();
  1125. while (__u.size() != 0)
  1126. __table_.__insert_multi(_VSTD::move(__u.__table_.remove(__i++)->__value_));
  1127. }
  1128. #if _LIBCPP_DEBUG_LEVEL >= 2
  1129. else
  1130. __get_db()->swap(this, &__u);
  1131. #endif
  1132. }
  1133. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1134. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1135. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1136. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1137. initializer_list<value_type> __il)
  1138. {
  1139. #if _LIBCPP_DEBUG_LEVEL >= 2
  1140. __get_db()->__insert_c(this);
  1141. #endif
  1142. insert(__il.begin(), __il.end());
  1143. }
  1144. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1145. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1146. initializer_list<value_type> __il, size_type __n, const hasher& __hf,
  1147. const key_equal& __eql)
  1148. : __table_(__hf, __eql)
  1149. {
  1150. #if _LIBCPP_DEBUG_LEVEL >= 2
  1151. __get_db()->__insert_c(this);
  1152. #endif
  1153. __table_.rehash(__n);
  1154. insert(__il.begin(), __il.end());
  1155. }
  1156. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1157. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::unordered_multiset(
  1158. initializer_list<value_type> __il, size_type __n, const hasher& __hf,
  1159. const key_equal& __eql, const allocator_type& __a)
  1160. : __table_(__hf, __eql, __a)
  1161. {
  1162. #if _LIBCPP_DEBUG_LEVEL >= 2
  1163. __get_db()->__insert_c(this);
  1164. #endif
  1165. __table_.rehash(__n);
  1166. insert(__il.begin(), __il.end());
  1167. }
  1168. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1169. #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1170. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1171. inline
  1172. unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
  1173. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
  1174. unordered_multiset&& __u)
  1175. _NOEXCEPT_(is_nothrow_move_assignable<__table>::value)
  1176. {
  1177. __table_ = _VSTD::move(__u.__table_);
  1178. return *this;
  1179. }
  1180. #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
  1181. #ifndef _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1182. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1183. inline
  1184. unordered_multiset<_Value, _Hash, _Pred, _Alloc>&
  1185. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::operator=(
  1186. initializer_list<value_type> __il)
  1187. {
  1188. __table_.__assign_multi(__il.begin(), __il.end());
  1189. return *this;
  1190. }
  1191. #endif // _LIBCPP_HAS_NO_GENERALIZED_INITIALIZERS
  1192. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1193. template <class _InputIterator>
  1194. inline
  1195. void
  1196. unordered_multiset<_Value, _Hash, _Pred, _Alloc>::insert(_InputIterator __first,
  1197. _InputIterator __last)
  1198. {
  1199. for (; __first != __last; ++__first)
  1200. __table_.__insert_multi(*__first);
  1201. }
  1202. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1203. inline _LIBCPP_INLINE_VISIBILITY
  1204. void
  1205. swap(unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  1206. unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  1207. _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
  1208. {
  1209. __x.swap(__y);
  1210. }
  1211. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1212. bool
  1213. operator==(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  1214. const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  1215. {
  1216. if (__x.size() != __y.size())
  1217. return false;
  1218. typedef typename unordered_multiset<_Value, _Hash, _Pred, _Alloc>::const_iterator
  1219. const_iterator;
  1220. typedef pair<const_iterator, const_iterator> _EqRng;
  1221. for (const_iterator __i = __x.begin(), __ex = __x.end(); __i != __ex;)
  1222. {
  1223. _EqRng __xeq = __x.equal_range(*__i);
  1224. _EqRng __yeq = __y.equal_range(*__i);
  1225. if (_VSTD::distance(__xeq.first, __xeq.second) !=
  1226. _VSTD::distance(__yeq.first, __yeq.second) ||
  1227. !_VSTD::is_permutation(__xeq.first, __xeq.second, __yeq.first))
  1228. return false;
  1229. __i = __xeq.second;
  1230. }
  1231. return true;
  1232. }
  1233. template <class _Value, class _Hash, class _Pred, class _Alloc>
  1234. inline _LIBCPP_INLINE_VISIBILITY
  1235. bool
  1236. operator!=(const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __x,
  1237. const unordered_multiset<_Value, _Hash, _Pred, _Alloc>& __y)
  1238. {
  1239. return !(__x == __y);
  1240. }
  1241. _LIBCPP_END_NAMESPACE_STD
  1242. #endif // _LIBCPP_UNORDERED_SET