set.rs source code [crates/hashbrown-0.15.2/src/set.rs]

1	use crate::{Equivalent, TryReserveError};
2	use core::hash::{BuildHasher, Hash};
3	use core::iter::{Chain, FusedIterator};
4	use core::ops::{BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Sub, SubAssign};
5	use core::{fmt, mem};
6	use map::make_hash;
7
8	use super::map::{self, HashMap, Keys};
9	use crate::raw::{Allocator, Global, RawExtractIf};
10	use crate::DefaultHashBuilder;
11
12	// Future Optimization (FIXME!)
13	// =============================
14	//
15	// Iteration over zero sized values is a noop. There is no need
16	// for `bucket.val` in the case of HashSet. I suppose we would need HKT
17	// to get rid of it properly.
18
19	/// A hash set implemented as a `HashMap` where the value is `()`.
20	///
21	/// As with the [`HashMap`] type, a `HashSet` requires that the elements
22	/// implement the [`Eq`] and [`Hash`] traits. This can frequently be achieved by
23	/// using `#[derive(PartialEq, Eq, Hash)]`. If you implement these yourself,
24	/// it is important that the following property holds:
25	///
26	/// ```text
27	/// k1 == k2 -> hash(k1) == hash(k2)
28	/// ```
29	///
30	/// In other words, if two keys are equal, their hashes must be equal.
31	///
32	///
33	/// It is a logic error for an item to be modified in such a way that the
34	/// item's hash, as determined by the [`Hash`] trait, or its equality, as
35	/// determined by the [`Eq`] trait, changes while it is in the set. This is
36	/// normally only possible through [`Cell`], [`RefCell`], global state, I/O, or
37	/// unsafe code.
38	///
39	/// It is also a logic error for the [`Hash`] implementation of a key to panic.
40	/// This is generally only possible if the trait is implemented manually. If a
41	/// panic does occur then the contents of the `HashSet` may become corrupted and
42	/// some items may be dropped from the table.
43	///
44	/// # Examples
45	///
46	/// ```
47	/// use hashbrown::HashSet;
48	/// // Type inference lets us omit an explicit type signature (which
49	/// // would be `HashSet<String>` in this example).
50	/// let mut books = HashSet::new();
51	///
52	/// // Add some books.
53	/// books.insert("A Dance With Dragons".to_string());
54	/// books.insert("To Kill a Mockingbird".to_string());
55	/// books.insert("The Odyssey".to_string());
56	/// books.insert("The Great Gatsby".to_string());
57	///
58	/// // Check for a specific one.
59	/// if !books.contains("The Winds of Winter") {
60	/// println!("We have {} books, but The Winds of Winter ain't one.",
61	/// books.len());
62	/// }
63	///
64	/// // Remove a book.
65	/// books.remove("The Odyssey");
66	///
67	/// // Iterate over everything.
68	/// for book in &books {
69	/// println!("{}", book);
70	/// }
71	/// ```
72	///
73	/// The easiest way to use `HashSet` with a custom type is to derive
74	/// [`Eq`] and [`Hash`]. We must also derive [`PartialEq`]. This will in the
75	/// future be implied by [`Eq`].
76	///
77	/// ```
78	/// use hashbrown::HashSet;
79	/// #[derive(Hash, Eq, PartialEq, Debug)]
80	/// struct Viking {
81	/// name: String,
82	/// power: usize,
83	/// }
84	///
85	/// let mut vikings = HashSet::new();
86	///
87	/// vikings.insert(Viking { name: "Einar".to_string(), power: `9` });
88	/// vikings.insert(Viking { name: "Einar".to_string(), power: `9` });
89	/// vikings.insert(Viking { name: "Olaf".to_string(), power: `4` });
90	/// vikings.insert(Viking { name: "Harald".to_string(), power: `8` });
91	///
92	/// // Use derived implementation to print the vikings.
93	/// for x in &vikings {
94	/// println!("{:?}", x);
95	/// }
96	/// ```
97	///
98	/// A `HashSet` with fixed list of elements can be initialized from an array:
99	///
100	/// ```
101	/// use hashbrown::HashSet;
102	///
103	/// let viking_names: HashSet<&'static str> =
104	/// [ "Einar", "Olaf", "Harald" ].into_iter().collect();
105	/// // use the values stored in the set
106	/// ```
107	///
108	/// [`Cell`]: https://doc.rust-lang.org/std/cell/struct.Cell.html
109	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
110	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
111	/// [`HashMap`]: struct.HashMap.html
112	/// [`PartialEq`]: https://doc.rust-lang.org/std/cmp/trait.PartialEq.html
113	/// [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
114	pub struct HashSet<T, S = DefaultHashBuilder, A: Allocator = Global> {
115	pub(crate) map: HashMap<T, (), S, A>,
116	}
117
118	impl<T: Clone, S: Clone, A: Allocator + Clone> Clone for HashSet<T, S, A> {
119	fn clone(&self) -> Self {
120	HashSet {
121	map: self.map.clone(),
122	}
123	}
124
125	fn clone_from(&mut self, source: &Self) {
126	self.map.clone_from(&source.map);
127	}
128	}
129
130	#[cfg(feature = "default-hasher")]
131	impl<T> HashSet<T, DefaultHashBuilder> {
132	/// Creates an empty `HashSet`.
133	///
134	/// The hash set is initially created with a capacity of 0, so it will not allocate until it
135	/// is first inserted into.
136	///
137	/// # HashDoS resistance
138	///
139	/// The `hash_builder` normally use a fixed key by default and that does
140	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
141	/// Users who require HashDoS resistance should explicitly use
142	/// [`std::collections::hash_map::RandomState`]
143	/// as the hasher when creating a [`HashSet`], for example with
144	/// [`with_hasher`](HashSet::with_hasher) method.
145	///
146	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
147	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
148	///
149	/// # Examples
150	///
151	/// ```
152	/// use hashbrown::HashSet;
153	/// let set: HashSet<i32> = HashSet::new();
154	/// ```
155	#[cfg_attr(feature = "inline-more", inline)]
156	pub fn new() -> Self {
157	Self {
158	map: HashMap::new(),
159	}
160	}
161
162	/// Creates an empty `HashSet` with the specified capacity.
163	///
164	/// The hash set will be able to hold at least `capacity` elements without
165	/// reallocating. If `capacity` is 0, the hash set will not allocate.
166	///
167	/// # HashDoS resistance
168	///
169	/// The `hash_builder` normally use a fixed key by default and that does
170	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
171	/// Users who require HashDoS resistance should explicitly use
172	/// [`std::collections::hash_map::RandomState`]
173	/// as the hasher when creating a [`HashSet`], for example with
174	/// [`with_capacity_and_hasher`](HashSet::with_capacity_and_hasher) method.
175	///
176	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
177	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
178	///
179	/// # Examples
180	///
181	/// ```
182	/// use hashbrown::HashSet;
183	/// let set: HashSet<i32> = HashSet::with_capacity(`10`);
184	/// assert!(set.capacity() >= `10`);
185	/// ```
186	#[cfg_attr(feature = "inline-more", inline)]
187	pub fn with_capacity(capacity: usize) -> Self {
188	Self {
189	map: HashMap::with_capacity(capacity),
190	}
191	}
192	}
193
194	#[cfg(feature = "default-hasher")]
195	impl<T: Hash + Eq, A: Allocator> HashSet<T, DefaultHashBuilder, A> {
196	/// Creates an empty `HashSet`.
197	///
198	/// The hash set is initially created with a capacity of 0, so it will not allocate until it
199	/// is first inserted into.
200	///
201	/// # HashDoS resistance
202	///
203	/// The `hash_builder` normally use a fixed key by default and that does
204	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
205	/// Users who require HashDoS resistance should explicitly use
206	/// [`std::collections::hash_map::RandomState`]
207	/// as the hasher when creating a [`HashSet`], for example with
208	/// [`with_hasher_in`](HashSet::with_hasher_in) method.
209	///
210	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
211	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
212	///
213	/// # Examples
214	///
215	/// ```
216	/// use hashbrown::HashSet;
217	/// let set: HashSet<i32> = HashSet::new();
218	/// ```
219	#[cfg_attr(feature = "inline-more", inline)]
220	pub fn new_in(alloc: A) -> Self {
221	Self {
222	map: HashMap::new_in(alloc),
223	}
224	}
225
226	/// Creates an empty `HashSet` with the specified capacity.
227	///
228	/// The hash set will be able to hold at least `capacity` elements without
229	/// reallocating. If `capacity` is 0, the hash set will not allocate.
230	///
231	/// # HashDoS resistance
232	///
233	/// The `hash_builder` normally use a fixed key by default and that does
234	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
235	/// Users who require HashDoS resistance should explicitly use
236	/// [`std::collections::hash_map::RandomState`]
237	/// as the hasher when creating a [`HashSet`], for example with
238	/// [`with_capacity_and_hasher_in`](HashSet::with_capacity_and_hasher_in) method.
239	///
240	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
241	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
242	///
243	/// # Examples
244	///
245	/// ```
246	/// use hashbrown::HashSet;
247	/// let set: HashSet<i32> = HashSet::with_capacity(`10`);
248	/// assert!(set.capacity() >= `10`);
249	/// ```
250	#[cfg_attr(feature = "inline-more", inline)]
251	pub fn with_capacity_in(capacity: usize, alloc: A) -> Self {
252	Self {
253	map: HashMap::with_capacity_in(capacity, alloc),
254	}
255	}
256	}
257
258	impl<T, S, A: Allocator> HashSet<T, S, A> {
259	/// Returns the number of elements the set can hold without reallocating.
260	///
261	/// # Examples
262	///
263	/// ```
264	/// use hashbrown::HashSet;
265	/// let set: HashSet<i32> = HashSet::with_capacity(`100`);
266	/// assert!(set.capacity() >= `100`);
267	/// ```
268	#[cfg_attr(feature = "inline-more", inline)]
269	pub fn capacity(&self) -> usize {
270	self.map.capacity()
271	}
272
273	/// An iterator visiting all elements in arbitrary order.
274	/// The iterator element type is `&'a T`.
275	///
276	/// # Examples
277	///
278	/// ```
279	/// use hashbrown::HashSet;
280	/// let mut set = HashSet::new();
281	/// set.insert("a");
282	/// set.insert("b");
283	///
284	/// // Will print in an arbitrary order.
285	/// for x in set.iter() {
286	/// println!("{}", x);
287	/// }
288	/// ```
289	#[cfg_attr(feature = "inline-more", inline)]
290	pub fn iter(&self) -> Iter<'_, T> {
291	Iter {
292	iter: self.map.keys(),
293	}
294	}
295
296	/// Returns the number of elements in the set.
297	///
298	/// # Examples
299	///
300	/// ```
301	/// use hashbrown::HashSet;
302	///
303	/// let mut v = HashSet::new();
304	/// assert_eq!(v.len(), `0`);
305	/// v.insert(`1`);
306	/// assert_eq!(v.len(), `1`);
307	/// ```
308	#[cfg_attr(feature = "inline-more", inline)]
309	pub fn len(&self) -> usize {
310	self.map.len()
311	}
312
313	/// Returns `true` if the set contains no elements.
314	///
315	/// # Examples
316	///
317	/// ```
318	/// use hashbrown::HashSet;
319	///
320	/// let mut v = HashSet::new();
321	/// assert!(v.is_empty());
322	/// v.insert(`1`);
323	/// assert!(!v.is_empty());
324	/// ```
325	#[cfg_attr(feature = "inline-more", inline)]
326	pub fn is_empty(&self) -> bool {
327	self.map.is_empty()
328	}
329
330	/// Clears the set, returning all elements in an iterator.
331	///
332	/// # Examples
333	///
334	/// ```
335	/// use hashbrown::HashSet;
336	///
337	/// let mut set: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
338	/// assert!(!set.is_empty());
339	///
340	/// // print 1, 2, 3 in an arbitrary order
341	/// for i in set.drain() {
342	/// println!("{}", i);
343	/// }
344	///
345	/// assert!(set.is_empty());
346	/// ```
347	#[cfg_attr(feature = "inline-more", inline)]
348	pub fn drain(&mut self) -> Drain<'_, T, A> {
349	Drain {
350	iter: self.map.drain(),
351	}
352	}
353
354	/// Retains only the elements specified by the predicate.
355	///
356	/// In other words, remove all elements `e` such that `f(&e)` returns `false`.
357	///
358	/// # Examples
359	///
360	/// ```
361	/// use hashbrown::HashSet;
362	///
363	/// let xs = [`1`,`2`,`3`,`4`,`5`,`6`];
364	/// let mut set: HashSet<i32> = xs.into_iter().collect();
365	/// set.retain(\|&k\| k % `2` == `0`);
366	/// assert_eq!(set.len(), `3`);
367	/// ```
368	pub fn retain<F>(&mut self, mut f: F)
369	where
370	F: FnMut(&T) -> bool,
371	{
372	self.map.retain(\|k, _\| f(k));
373	}
374
375	/// Drains elements which are true under the given predicate,
376	/// and returns an iterator over the removed items.
377	///
378	/// In other words, move all elements `e` such that `f(&e)` returns `true` out
379	/// into another iterator.
380	///
381	/// If the returned `ExtractIf` is not exhausted, e.g. because it is dropped without iterating
382	/// or the iteration short-circuits, then the remaining elements will be retained.
383	/// Use [`retain()`] with a negated predicate if you do not need the returned iterator.
384	///
385	/// [`retain()`]: HashSet::retain
386	///
387	/// # Examples
388	///
389	/// ```
390	/// use hashbrown::HashSet;
391	///
392	/// let mut set: HashSet<i32> = (`0`..`8`).collect();
393	/// let drained: HashSet<i32> = set.extract_if(\|v\| v % `2` == `0`).collect();
394	///
395	/// let mut evens = drained.into_iter().collect::<Vec<_>>();
396	/// let mut odds = set.into_iter().collect::<Vec<_>>();
397	/// evens.sort();
398	/// odds.sort();
399	///
400	/// assert_eq!(evens, vec![`0`, `2`, `4`, `6`]);
401	/// assert_eq!(odds, vec![`1`, `3`, `5`, `7`]);
402	/// ```
403	#[cfg_attr(feature = "inline-more", inline)]
404	pub fn extract_if<F>(&mut self, f: F) -> ExtractIf<'_, T, F, A>
405	where
406	F: FnMut(&T) -> bool,
407	{
408	ExtractIf {
409	f,
410	inner: RawExtractIf {
411	iter: unsafe { self.map.table.iter() },
412	table: &mut self.map.table,
413	},
414	}
415	}
416
417	/// Clears the set, removing all values.
418	///
419	/// # Examples
420	///
421	/// ```
422	/// use hashbrown::HashSet;
423	///
424	/// let mut v = HashSet::new();
425	/// v.insert(`1`);
426	/// v.clear();
427	/// assert!(v.is_empty());
428	/// ```
429	#[cfg_attr(feature = "inline-more", inline)]
430	pub fn clear(&mut self) {
431	self.map.clear();
432	}
433	}
434
435	impl<T, S> HashSet<T, S, Global> {
436	/// Creates a new empty hash set which will use the given hasher to hash
437	/// keys.
438	///
439	/// The hash set is initially created with a capacity of 0, so it will not
440	/// allocate until it is first inserted into.
441	///
442	/// # HashDoS resistance
443	///
444	/// The `hash_builder` normally use a fixed key by default and that does
445	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
446	/// Users who require HashDoS resistance should explicitly use
447	/// [`std::collections::hash_map::RandomState`]
448	/// as the hasher when creating a [`HashSet`].
449	///
450	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
451	/// the `HashSet` to be useful, see its documentation for details.
452	///
453	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
454	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
455	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
456	///
457	/// # Examples
458	///
459	/// ```
460	/// use hashbrown::HashSet;
461	/// use hashbrown::DefaultHashBuilder;
462	///
463	/// let s = DefaultHashBuilder::default();
464	/// let mut set = HashSet::with_hasher(s);
465	/// set.insert(`2`);
466	/// ```
467	#[cfg_attr(feature = "inline-more", inline)]
468	#[cfg_attr(feature = "rustc-dep-of-std", rustc_const_stable_indirect)]
469	pub const fn with_hasher(hasher: S) -> Self {
470	Self {
471	map: HashMap::with_hasher(hasher),
472	}
473	}
474
475	/// Creates an empty `HashSet` with the specified capacity, using
476	/// `hasher` to hash the keys.
477	///
478	/// The hash set will be able to hold at least `capacity` elements without
479	/// reallocating. If `capacity` is 0, the hash set will not allocate.
480	///
481	/// # HashDoS resistance
482	///
483	/// The `hash_builder` normally use a fixed key by default and that does
484	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
485	/// Users who require HashDoS resistance should explicitly use
486	/// [`std::collections::hash_map::RandomState`]
487	/// as the hasher when creating a [`HashSet`].
488	///
489	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
490	/// the `HashSet` to be useful, see its documentation for details.
491	///
492	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
493	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
494	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
495	///
496	/// # Examples
497	///
498	/// ```
499	/// use hashbrown::HashSet;
500	/// use hashbrown::DefaultHashBuilder;
501	///
502	/// let s = DefaultHashBuilder::default();
503	/// let mut set = HashSet::with_capacity_and_hasher(`10`, s);
504	/// set.insert(`1`);
505	/// ```
506	#[cfg_attr(feature = "inline-more", inline)]
507	pub fn with_capacity_and_hasher(capacity: usize, hasher: S) -> Self {
508	Self {
509	map: HashMap::with_capacity_and_hasher(capacity, hasher),
510	}
511	}
512	}
513
514	impl<T, S, A> HashSet<T, S, A>
515	where
516	A: Allocator,
517	{
518	/// Returns a reference to the underlying allocator.
519	#[inline]
520	pub fn allocator(&self) -> &A {
521	self.map.allocator()
522	}
523
524	/// Creates a new empty hash set which will use the given hasher to hash
525	/// keys.
526	///
527	/// The hash set is initially created with a capacity of 0, so it will not
528	/// allocate until it is first inserted into.
529	///
530	/// # HashDoS resistance
531	///
532	/// The `hash_builder` normally use a fixed key by default and that does
533	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
534	/// Users who require HashDoS resistance should explicitly use
535	/// [`std::collections::hash_map::RandomState`]
536	/// as the hasher when creating a [`HashSet`].
537	///
538	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
539	/// the `HashSet` to be useful, see its documentation for details.
540	///
541	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
542	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
543	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
544	///
545	/// # Examples
546	///
547	/// ```
548	/// use hashbrown::HashSet;
549	/// use hashbrown::DefaultHashBuilder;
550	///
551	/// let s = DefaultHashBuilder::default();
552	/// let mut set = HashSet::with_hasher(s);
553	/// set.insert(`2`);
554	/// ```
555	#[cfg_attr(feature = "inline-more", inline)]
556	#[cfg_attr(feature = "rustc-dep-of-std", rustc_const_stable_indirect)]
557	pub const fn with_hasher_in(hasher: S, alloc: A) -> Self {
558	Self {
559	map: HashMap::with_hasher_in(hasher, alloc),
560	}
561	}
562
563	/// Creates an empty `HashSet` with the specified capacity, using
564	/// `hasher` to hash the keys.
565	///
566	/// The hash set will be able to hold at least `capacity` elements without
567	/// reallocating. If `capacity` is 0, the hash set will not allocate.
568	///
569	/// # HashDoS resistance
570	///
571	/// The `hash_builder` normally use a fixed key by default and that does
572	/// not allow the `HashSet` to be protected against attacks such as [`HashDoS`].
573	/// Users who require HashDoS resistance should explicitly use
574	/// [`std::collections::hash_map::RandomState`]
575	/// as the hasher when creating a [`HashSet`].
576	///
577	/// The `hash_builder` passed should implement the [`BuildHasher`] trait for
578	/// the `HashSet` to be useful, see its documentation for details.
579	///
580	/// [`HashDoS`]: https://en.wikipedia.org/wiki/Collision_attack
581	/// [`std::collections::hash_map::RandomState`]: https://doc.rust-lang.org/std/collections/hash_map/struct.RandomState.html
582	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
583	///
584	/// # Examples
585	///
586	/// ```
587	/// use hashbrown::HashSet;
588	/// use hashbrown::DefaultHashBuilder;
589	///
590	/// let s = DefaultHashBuilder::default();
591	/// let mut set = HashSet::with_capacity_and_hasher(`10`, s);
592	/// set.insert(`1`);
593	/// ```
594	#[cfg_attr(feature = "inline-more", inline)]
595	pub fn with_capacity_and_hasher_in(capacity: usize, hasher: S, alloc: A) -> Self {
596	Self {
597	map: HashMap::with_capacity_and_hasher_in(capacity, hasher, alloc),
598	}
599	}
600
601	/// Returns a reference to the set's [`BuildHasher`].
602	///
603	/// [`BuildHasher`]: https://doc.rust-lang.org/std/hash/trait.BuildHasher.html
604	///
605	/// # Examples
606	///
607	/// ```
608	/// use hashbrown::HashSet;
609	/// use hashbrown::DefaultHashBuilder;
610	///
611	/// let hasher = DefaultHashBuilder::default();
612	/// let set: HashSet<i32> = HashSet::with_hasher(hasher);
613	/// let hasher: &DefaultHashBuilder = set.hasher();
614	/// ```
615	#[cfg_attr(feature = "inline-more", inline)]
616	pub fn hasher(&self) -> &S {
617	self.map.hasher()
618	}
619	}
620
621	impl<T, S, A> HashSet<T, S, A>
622	where
623	T: Eq + Hash,
624	S: BuildHasher,
625	A: Allocator,
626	{
627	/// Reserves capacity for at least `additional` more elements to be inserted
628	/// in the `HashSet`. The collection may reserve more space to avoid
629	/// frequent reallocations.
630	///
631	/// # Panics
632	///
633	/// Panics if the new capacity exceeds [`isize::MAX`] bytes and [`abort`] the program
634	/// in case of allocation error. Use [`try_reserve`](HashSet::try_reserve) instead
635	/// if you want to handle memory allocation failure.
636	///
637	/// [`isize::MAX`]: https://doc.rust-lang.org/std/primitive.isize.html
638	/// [`abort`]: https://doc.rust-lang.org/alloc/alloc/fn.handle_alloc_error.html
639	///
640	/// # Examples
641	///
642	/// ```
643	/// use hashbrown::HashSet;
644	/// let mut set: HashSet<i32> = HashSet::new();
645	/// set.reserve(`10`);
646	/// assert!(set.capacity() >= `10`);
647	/// ```
648	#[cfg_attr(feature = "inline-more", inline)]
649	pub fn reserve(&mut self, additional: usize) {
650	self.map.reserve(additional);
651	}
652
653	/// Tries to reserve capacity for at least `additional` more elements to be inserted
654	/// in the given `HashSet<K,V>`. The collection may reserve more space to avoid
655	/// frequent reallocations.
656	///
657	/// # Errors
658	///
659	/// If the capacity overflows, or the allocator reports a failure, then an error
660	/// is returned.
661	///
662	/// # Examples
663	///
664	/// ```
665	/// use hashbrown::HashSet;
666	/// let mut set: HashSet<i32> = HashSet::new();
667	/// set.try_reserve(`10`).expect("why is the test harness OOMing on 10 bytes?");
668	/// ```
669	#[cfg_attr(feature = "inline-more", inline)]
670	pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
671	self.map.try_reserve(additional)
672	}
673
674	/// Shrinks the capacity of the set as much as possible. It will drop
675	/// down as much as possible while maintaining the internal rules
676	/// and possibly leaving some space in accordance with the resize policy.
677	///
678	/// # Examples
679	///
680	/// ```
681	/// use hashbrown::HashSet;
682	///
683	/// let mut set = HashSet::with_capacity(`100`);
684	/// set.insert(`1`);
685	/// set.insert(`2`);
686	/// assert!(set.capacity() >= `100`);
687	/// set.shrink_to_fit();
688	/// assert!(set.capacity() >= `2`);
689	/// ```
690	#[cfg_attr(feature = "inline-more", inline)]
691	pub fn shrink_to_fit(&mut self) {
692	self.map.shrink_to_fit();
693	}
694
695	/// Shrinks the capacity of the set with a lower limit. It will drop
696	/// down no lower than the supplied limit while maintaining the internal rules
697	/// and possibly leaving some space in accordance with the resize policy.
698	///
699	/// Panics if the current capacity is smaller than the supplied
700	/// minimum capacity.
701	///
702	/// # Examples
703	///
704	/// ```
705	/// use hashbrown::HashSet;
706	///
707	/// let mut set = HashSet::with_capacity(`100`);
708	/// set.insert(`1`);
709	/// set.insert(`2`);
710	/// assert!(set.capacity() >= `100`);
711	/// set.shrink_to(`10`);
712	/// assert!(set.capacity() >= `10`);
713	/// set.shrink_to(`0`);
714	/// assert!(set.capacity() >= `2`);
715	/// ```
716	#[cfg_attr(feature = "inline-more", inline)]
717	pub fn shrink_to(&mut self, min_capacity: usize) {
718	self.map.shrink_to(min_capacity);
719	}
720
721	/// Visits the values representing the difference,
722	/// i.e., the values that are in `self` but not in `other`.
723	///
724	/// # Examples
725	///
726	/// ```
727	/// use hashbrown::HashSet;
728	/// let a: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
729	/// let b: HashSet<_> = [`4`, `2`, `3`, `4`].into_iter().collect();
730	///
731	/// // Can be seen as `a - b`.
732	/// for x in a.difference(&b) {
733	/// println!("{}", x); // Print 1
734	/// }
735	///
736	/// let diff: HashSet<_> = a.difference(&b).collect();
737	/// assert_eq!(diff, [`1`].iter().collect());
738	///
739	/// // Note that difference is not symmetric,
740	/// // and `b - a` means something else:
741	/// let diff: HashSet<_> = b.difference(&a).collect();
742	/// assert_eq!(diff, [`4`].iter().collect());
743	/// ```
744	#[cfg_attr(feature = "inline-more", inline)]
745	pub fn difference<'a>(&'a self, other: &'a Self) -> Difference<'a, T, S, A> {
746	Difference {
747	iter: self.iter(),
748	other,
749	}
750	}
751
752	/// Visits the values representing the symmetric difference,
753	/// i.e., the values that are in `self` or in `other` but not in both.
754	///
755	/// # Examples
756	///
757	/// ```
758	/// use hashbrown::HashSet;
759	/// let a: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
760	/// let b: HashSet<_> = [`4`, `2`, `3`, `4`].into_iter().collect();
761	///
762	/// // Print 1, 4 in arbitrary order.
763	/// for x in a.symmetric_difference(&b) {
764	/// println!("{}", x);
765	/// }
766	///
767	/// let diff1: HashSet<_> = a.symmetric_difference(&b).collect();
768	/// let diff2: HashSet<_> = b.symmetric_difference(&a).collect();
769	///
770	/// assert_eq!(diff1, diff2);
771	/// assert_eq!(diff1, [`1`, `4`].iter().collect());
772	/// ```
773	#[cfg_attr(feature = "inline-more", inline)]
774	pub fn symmetric_difference<'a>(&'a self, other: &'a Self) -> SymmetricDifference<'a, T, S, A> {
775	SymmetricDifference {
776	iter: self.difference(other).chain(other.difference(self)),
777	}
778	}
779
780	/// Visits the values representing the intersection,
781	/// i.e., the values that are both in `self` and `other`.
782	///
783	/// # Examples
784	///
785	/// ```
786	/// use hashbrown::HashSet;
787	/// let a: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
788	/// let b: HashSet<_> = [`4`, `2`, `3`, `4`].into_iter().collect();
789	///
790	/// // Print 2, 3 in arbitrary order.
791	/// for x in a.intersection(&b) {
792	/// println!("{}", x);
793	/// }
794	///
795	/// let intersection: HashSet<_> = a.intersection(&b).collect();
796	/// assert_eq!(intersection, [`2`, `3`].iter().collect());
797	/// ```
798	#[cfg_attr(feature = "inline-more", inline)]
799	pub fn intersection<'a>(&'a self, other: &'a Self) -> Intersection<'a, T, S, A> {
800	let (smaller, larger) = if self.len() <= other.len() {
801	(self, other)
802	} else {
803	(other, self)
804	};
805	Intersection {
806	iter: smaller.iter(),
807	other: larger,
808	}
809	}
810
811	/// Visits the values representing the union,
812	/// i.e., all the values in `self` or `other`, without duplicates.
813	///
814	/// # Examples
815	///
816	/// ```
817	/// use hashbrown::HashSet;
818	/// let a: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
819	/// let b: HashSet<_> = [`4`, `2`, `3`, `4`].into_iter().collect();
820	///
821	/// // Print 1, 2, 3, 4 in arbitrary order.
822	/// for x in a.union(&b) {
823	/// println!("{}", x);
824	/// }
825	///
826	/// let union: HashSet<_> = a.union(&b).collect();
827	/// assert_eq!(union, [`1`, `2`, `3`, `4`].iter().collect());
828	/// ```
829	#[cfg_attr(feature = "inline-more", inline)]
830	pub fn union<'a>(&'a self, other: &'a Self) -> Union<'a, T, S, A> {
831	// We'll iterate one set in full, and only the remaining difference from the other.
832	// Use the smaller set for the difference in order to reduce hash lookups.
833	let (smaller, larger) = if self.len() <= other.len() {
834	(self, other)
835	} else {
836	(other, self)
837	};
838	Union {
839	iter: larger.iter().chain(smaller.difference(larger)),
840	}
841	}
842
843	/// Returns `true` if the set contains a value.
844	///
845	/// The value may be any borrowed form of the set's value type, but
846	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
847	/// the value type.
848	///
849	/// # Examples
850	///
851	/// ```
852	/// use hashbrown::HashSet;
853	///
854	/// let set: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
855	/// assert_eq!(set.contains(&`1`), `true`);
856	/// assert_eq!(set.contains(&`4`), `false`);
857	/// ```
858	///
859	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
860	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
861	#[cfg_attr(feature = "inline-more", inline)]
862	pub fn contains<Q>(&self, value: &Q) -> bool
863	where
864	Q: Hash + Equivalent<T> + ?Sized,
865	{
866	self.map.contains_key(value)
867	}
868
869	/// Returns a reference to the value in the set, if any, that is equal to the given value.
870	///
871	/// The value may be any borrowed form of the set's value type, but
872	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
873	/// the value type.
874	///
875	/// # Examples
876	///
877	/// ```
878	/// use hashbrown::HashSet;
879	///
880	/// let set: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
881	/// assert_eq!(set.get(&`2`), Some(&`2`));
882	/// assert_eq!(set.get(&`4`), None);
883	/// ```
884	///
885	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
886	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
887	#[cfg_attr(feature = "inline-more", inline)]
888	pub fn get<Q>(&self, value: &Q) -> Option<&T>
889	where
890	Q: Hash + Equivalent<T> + ?Sized,
891	{
892	// Avoid `Option::map` because it bloats LLVM IR.
893	match self.map.get_key_value(value) {
894	Some((k, _)) => Some(k),
895	None => None,
896	}
897	}
898
899	/// Inserts the given `value` into the set if it is not present, then
900	/// returns a reference to the value in the set.
901	///
902	/// # Examples
903	///
904	/// ```
905	/// use hashbrown::HashSet;
906	///
907	/// let mut set: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
908	/// assert_eq!(set.len(), `3`);
909	/// assert_eq!(set.get_or_insert(`2`), &`2`);
910	/// assert_eq!(set.get_or_insert(`100`), &`100`);
911	/// assert_eq!(set.len(), `4`); // 100 was inserted
912	/// ```
913	#[cfg_attr(feature = "inline-more", inline)]
914	pub fn get_or_insert(&mut self, value: T) -> &T {
915	let hash = make_hash(&self.map.hash_builder, &value);
916	let bucket = match self.map.find_or_find_insert_slot(hash, &value) {
917	Ok(bucket) => bucket,
918	Err(slot) => unsafe { self.map.table.insert_in_slot(hash, slot, (value, ())) },
919	};
920	unsafe { &bucket.as_ref().0 }
921	}
922
923	/// Inserts a value computed from `f` into the set if the given `value` is
924	/// not present, then returns a reference to the value in the set.
925	///
926	/// # Examples
927	///
928	/// ```
929	/// use hashbrown::HashSet;
930	///
931	/// let mut set: HashSet<String> = ["cat", "dog", "horse"]
932	/// .iter().map(\|&pet\| pet.to_owned()).collect();
933	///
934	/// assert_eq!(set.len(), `3`);
935	/// for &pet in &["cat", "dog", "fish"] {
936	/// let value = set.get_or_insert_with(pet, str::to_owned);
937	/// assert_eq!(value, pet);
938	/// }
939	/// assert_eq!(set.len(), `4`); // a new "fish" was inserted
940	/// ```
941	///
942	/// The following example will panic because the new value doesn't match.
943	///
944	/// ```should_panic
945	/// let mut set = hashbrown::HashSet::new();
946	/// set.get_or_insert_with("rust", \|_\| String::new());
947	/// ```
948	#[cfg_attr(feature = "inline-more", inline)]
949	pub fn get_or_insert_with<Q, F>(&mut self, value: &Q, f: F) -> &T
950	where
951	Q: Hash + Equivalent<T> + ?Sized,
952	F: FnOnce(&Q) -> T,
953	{
954	let hash = make_hash(&self.map.hash_builder, value);
955	let bucket = match self.map.find_or_find_insert_slot(hash, value) {
956	Ok(bucket) => bucket,
957	Err(slot) => {
958	let new = f(value);
959	assert!(value.equivalent(&new), "new value is not equivalent");
960	unsafe { self.map.table.insert_in_slot(hash, slot, (new, ())) }
961	}
962	};
963	unsafe { &bucket.as_ref().0 }
964	}
965
966	/// Gets the given value's corresponding entry in the set for in-place manipulation.
967	///
968	/// # Examples
969	///
970	/// ```
971	/// use hashbrown::HashSet;
972	/// use hashbrown::hash_set::Entry::*;
973	///
974	/// let mut singles = HashSet::new();
975	/// let mut dupes = HashSet::new();
976	///
977	/// for ch in "a short treatise on fungi".chars() {
978	/// if let Vacant(dupe_entry) = dupes.entry(ch) {
979	/// // We haven't already seen a duplicate, so
980	/// // check if we've at least seen it once.
981	/// match singles.entry(ch) {
982	/// Vacant(single_entry) => {
983	/// // We found a new character for the first time.
984	/// single_entry.insert();
985	/// }
986	/// Occupied(single_entry) => {
987	/// // We've already seen this once, "move" it to dupes.
988	/// single_entry.remove();
989	/// dupe_entry.insert();
990	/// }
991	/// }
992	/// }
993	/// }
994	///
995	/// assert!(!singles.contains(&'t') && dupes.contains(&'t'));
996	/// assert!(singles.contains(&'u') && !dupes.contains(&'u'));
997	/// assert!(!singles.contains(&'v') && !dupes.contains(&'v'));
998	/// ```
999	#[cfg_attr(feature = "inline-more", inline)]
1000	pub fn entry(&mut self, value: T) -> Entry<'_, T, S, A> {
1001	match self.map.entry(value) {
1002	map::Entry::Occupied(entry) => Entry::Occupied(OccupiedEntry { inner: entry }),
1003	map::Entry::Vacant(entry) => Entry::Vacant(VacantEntry { inner: entry }),
1004	}
1005	}
1006
1007	/// Returns `true` if `self` has no elements in common with `other`.
1008	/// This is equivalent to checking for an empty intersection.
1009	///
1010	/// # Examples
1011	///
1012	/// ```
1013	/// use hashbrown::HashSet;
1014	///
1015	/// let a: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
1016	/// let mut b = HashSet::new();
1017	///
1018	/// assert_eq!(a.is_disjoint(&b), `true`);
1019	/// b.insert(`4`);
1020	/// assert_eq!(a.is_disjoint(&b), `true`);
1021	/// b.insert(`1`);
1022	/// assert_eq!(a.is_disjoint(&b), `false`);
1023	/// ```
1024	pub fn is_disjoint(&self, other: &Self) -> bool {
1025	self.intersection(other).next().is_none()
1026	}
1027
1028	/// Returns `true` if the set is a subset of another,
1029	/// i.e., `other` contains at least all the values in `self`.
1030	///
1031	/// # Examples
1032	///
1033	/// ```
1034	/// use hashbrown::HashSet;
1035	///
1036	/// let sup: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
1037	/// let mut set = HashSet::new();
1038	///
1039	/// assert_eq!(set.is_subset(&sup), `true`);
1040	/// set.insert(`2`);
1041	/// assert_eq!(set.is_subset(&sup), `true`);
1042	/// set.insert(`4`);
1043	/// assert_eq!(set.is_subset(&sup), `false`);
1044	/// ```
1045	pub fn is_subset(&self, other: &Self) -> bool {
1046	self.len() <= other.len() && self.iter().all(\|v\| other.contains(v))
1047	}
1048
1049	/// Returns `true` if the set is a superset of another,
1050	/// i.e., `self` contains at least all the values in `other`.
1051	///
1052	/// # Examples
1053	///
1054	/// ```
1055	/// use hashbrown::HashSet;
1056	///
1057	/// let sub: HashSet<_> = [`1`, `2`].into_iter().collect();
1058	/// let mut set = HashSet::new();
1059	///
1060	/// assert_eq!(set.is_superset(&sub), `false`);
1061	///
1062	/// set.insert(`0`);
1063	/// set.insert(`1`);
1064	/// assert_eq!(set.is_superset(&sub), `false`);
1065	///
1066	/// set.insert(`2`);
1067	/// assert_eq!(set.is_superset(&sub), `true`);
1068	/// ```
1069	#[cfg_attr(feature = "inline-more", inline)]
1070	pub fn is_superset(&self, other: &Self) -> bool {
1071	other.is_subset(self)
1072	}
1073
1074	/// Adds a value to the set.
1075	///
1076	/// If the set did not have this value present, `true` is returned.
1077	///
1078	/// If the set did have this value present, `false` is returned.
1079	///
1080	/// # Examples
1081	///
1082	/// ```
1083	/// use hashbrown::HashSet;
1084	///
1085	/// let mut set = HashSet::new();
1086	///
1087	/// assert_eq!(set.insert(`2`), `true`);
1088	/// assert_eq!(set.insert(`2`), `false`);
1089	/// assert_eq!(set.len(), `1`);
1090	/// ```
1091	#[cfg_attr(feature = "inline-more", inline)]
1092	pub fn insert(&mut self, value: T) -> bool {
1093	self.map.insert(value, ()).is_none()
1094	}
1095
1096	/// Insert a value the set without checking if the value already exists in the set.
1097	///
1098	/// This operation is faster than regular insert, because it does not perform
1099	/// lookup before insertion.
1100	///
1101	/// This operation is useful during initial population of the set.
1102	/// For example, when constructing a set from another set, we know
1103	/// that values are unique.
1104	///
1105	/// # Safety
1106	///
1107	/// This operation is safe if a value does not exist in the set.
1108	///
1109	/// However, if a value exists in the set already, the behavior is unspecified:
1110	/// this operation may panic, loop forever, or any following operation with the set
1111	/// may panic, loop forever or return arbitrary result.
1112	///
1113	/// That said, this operation (and following operations) are guaranteed to
1114	/// not violate memory safety.
1115	///
1116	/// However this operation is still unsafe because the resulting `HashSet`
1117	/// may be passed to unsafe code which does expect the set to behave
1118	/// correctly, and would cause unsoundness as a result.
1119	#[cfg_attr(feature = "inline-more", inline)]
1120	pub unsafe fn insert_unique_unchecked(&mut self, value: T) -> &T {
1121	self.map.insert_unique_unchecked(value, ()).0
1122	}
1123
1124	/// Adds a value to the set, replacing the existing value, if any, that is equal to the given
1125	/// one. Returns the replaced value.
1126	///
1127	/// # Examples
1128	///
1129	/// ```
1130	/// use hashbrown::HashSet;
1131	///
1132	/// let mut set = HashSet::new();
1133	/// set.insert(Vec::<i32>::new());
1134	///
1135	/// assert_eq!(set.get(&[][..]).unwrap().capacity(), `0`);
1136	/// set.replace(Vec::with_capacity(`10`));
1137	/// assert_eq!(set.get(&[][..]).unwrap().capacity(), `10`);
1138	/// ```
1139	#[cfg_attr(feature = "inline-more", inline)]
1140	pub fn replace(&mut self, value: T) -> Option<T> {
1141	let hash = make_hash(&self.map.hash_builder, &value);
1142	match self.map.find_or_find_insert_slot(hash, &value) {
1143	Ok(bucket) => Some(mem::replace(unsafe { &mut bucket.as_mut().0 }, value)),
1144	Err(slot) => {
1145	unsafe {
1146	self.map.table.insert_in_slot(hash, slot, (value, ()));
1147	}
1148	None
1149	}
1150	}
1151	}
1152
1153	/// Removes a value from the set. Returns whether the value was
1154	/// present in the set.
1155	///
1156	/// The value may be any borrowed form of the set's value type, but
1157	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1158	/// the value type.
1159	///
1160	/// # Examples
1161	///
1162	/// ```
1163	/// use hashbrown::HashSet;
1164	///
1165	/// let mut set = HashSet::new();
1166	///
1167	/// set.insert(`2`);
1168	/// assert_eq!(set.remove(&`2`), `true`);
1169	/// assert_eq!(set.remove(&`2`), `false`);
1170	/// ```
1171	///
1172	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1173	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1174	#[cfg_attr(feature = "inline-more", inline)]
1175	pub fn remove<Q>(&mut self, value: &Q) -> bool
1176	where
1177	Q: Hash + Equivalent<T> + ?Sized,
1178	{
1179	self.map.remove(value).is_some()
1180	}
1181
1182	/// Removes and returns the value in the set, if any, that is equal to the given one.
1183	///
1184	/// The value may be any borrowed form of the set's value type, but
1185	/// [`Hash`] and [`Eq`] on the borrowed form must* match those for*
1186	/// the value type.
1187	///
1188	/// # Examples
1189	///
1190	/// ```
1191	/// use hashbrown::HashSet;
1192	///
1193	/// let mut set: HashSet<_> = [`1`, `2`, `3`].into_iter().collect();
1194	/// assert_eq!(set.take(&`2`), Some(`2`));
1195	/// assert_eq!(set.take(&`2`), None);
1196	/// ```
1197	///
1198	/// [`Eq`]: https://doc.rust-lang.org/std/cmp/trait.Eq.html
1199	/// [`Hash`]: https://doc.rust-lang.org/std/hash/trait.Hash.html
1200	#[cfg_attr(feature = "inline-more", inline)]
1201	pub fn take<Q>(&mut self, value: &Q) -> Option<T>
1202	where
1203	Q: Hash + Equivalent<T> + ?Sized,
1204	{
1205	// Avoid `Option::map` because it bloats LLVM IR.
1206	match self.map.remove_entry(value) {
1207	Some((k, _)) => Some(k),
1208	None => None,
1209	}
1210	}
1211
1212	/// Returns the total amount of memory allocated internally by the hash
1213	/// set, in bytes.
1214	///
1215	/// The returned number is informational only. It is intended to be
1216	/// primarily used for memory profiling.
1217	#[inline]
1218	pub fn allocation_size(&self) -> usize {
1219	self.map.allocation_size()
1220	}
1221	}
1222
1223	impl<T, S, A> PartialEq for HashSet<T, S, A>
1224	where
1225	T: Eq + Hash,
1226	S: BuildHasher,
1227	A: Allocator,
1228	{
1229	fn eq(&self, other: &Self) -> bool {
1230	if self.len() != other.len() {
1231	return `false`;
1232	}
1233
1234	self.iter().all(\|key: &T\| other.contains(key))
1235	}
1236	}
1237
1238	impl<T, S, A> Eq for HashSet<T, S, A>
1239	where
1240	T: Eq + Hash,
1241	S: BuildHasher,
1242	A: Allocator,
1243	{
1244	}
1245
1246	impl<T, S, A> fmt::Debug for HashSet<T, S, A>
1247	where
1248	T: fmt::Debug,
1249	A: Allocator,
1250	{
1251	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1252	f.debug_set().entries(self.iter()).finish()
1253	}
1254	}
1255
1256	impl<T, S, A> From<HashMap<T, (), S, A>> for HashSet<T, S, A>
1257	where
1258	A: Allocator,
1259	{
1260	fn from(map: HashMap<T, (), S, A>) -> Self {
1261	Self { map }
1262	}
1263	}
1264
1265	impl<T, S, A> FromIterator<T> for HashSet<T, S, A>
1266	where
1267	T: Eq + Hash,
1268	S: BuildHasher + Default,
1269	A: Default + Allocator,
1270	{
1271	#[cfg_attr(feature = "inline-more", inline)]
1272	fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
1273	let mut set: HashSet = Self::with_hasher_in(hasher:Default::default(), alloc:Default::default());
1274	set.extend(iter);
1275	set
1276	}
1277	}
1278
1279	// The default hasher is used to match the std implementation signature
1280	#[cfg(feature = "default-hasher")]
1281	impl<T, A, const N: usize> From<[T; N]> for HashSet<T, DefaultHashBuilder, A>
1282	where
1283	T: Eq + Hash,
1284	A: Default + Allocator,
1285	{
1286	/// # Examples
1287	///
1288	/// ```
1289	/// use hashbrown::HashSet;
1290	///
1291	/// let set1 = HashSet::from([`1`, `2`, `3`, `4`]);
1292	/// let set2: HashSet<_> = [`1`, `2`, `3`, `4`].into();
1293	/// assert_eq!(set1, set2);
1294	/// ```
1295	fn from(arr: [T; N]) -> Self {
1296	arr.into_iter().collect()
1297	}
1298	}
1299
1300	impl<T, S, A> Extend<T> for HashSet<T, S, A>
1301	where
1302	T: Eq + Hash,
1303	S: BuildHasher,
1304	A: Allocator,
1305	{
1306	#[cfg_attr(feature = "inline-more", inline)]
1307	fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
1308	self.map.extend(iter.into_iter().map(\|k: T\| (k, ())));
1309	}
1310
1311	#[inline]
1312	#[cfg(feature = "nightly")]
1313	fn extend_one(&mut self, k: T) {
1314	self.map.insert(k, ());
1315	}
1316
1317	#[inline]
1318	#[cfg(feature = "nightly")]
1319	fn extend_reserve(&mut self, additional: usize) {
1320	Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1321	}
1322	}
1323
1324	impl<'a, T, S, A> Extend<&'a T> for HashSet<T, S, A>
1325	where
1326	T: 'a + Eq + Hash + Copy,
1327	S: BuildHasher,
1328	A: Allocator,
1329	{
1330	#[cfg_attr(feature = "inline-more", inline)]
1331	fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
1332	self.extend(iter.into_iter().copied());
1333	}
1334
1335	#[inline]
1336	#[cfg(feature = "nightly")]
1337	fn extend_one(&mut self, k: &'a T) {
1338	self.map.insert(*k, ());
1339	}
1340
1341	#[inline]
1342	#[cfg(feature = "nightly")]
1343	fn extend_reserve(&mut self, additional: usize) {
1344	Extend::<(T, ())>::extend_reserve(&mut self.map, additional);
1345	}
1346	}
1347
1348	impl<T, S, A> Default for HashSet<T, S, A>
1349	where
1350	S: Default,
1351	A: Default + Allocator,
1352	{
1353	/// Creates an empty `HashSet<T, S>` with the `Default` value for the hasher.
1354	#[cfg_attr(feature = "inline-more", inline)]
1355	fn default() -> Self {
1356	Self {
1357	map: HashMap::default(),
1358	}
1359	}
1360	}
1361
1362	impl<T, S, A> BitOr<&HashSet<T, S, A>> for &HashSet<T, S, A>
1363	where
1364	T: Eq + Hash + Clone,
1365	S: BuildHasher + Default,
1366	A: Allocator + Default,
1367	{
1368	type Output = HashSet<T, S, A>;
1369
1370	/// Returns the union of `self` and `rhs` as a new `HashSet<T, S>`.
1371	///
1372	/// # Examples
1373	///
1374	/// ```
1375	/// use hashbrown::HashSet;
1376	///
1377	/// let a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1378	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1379	///
1380	/// let set = &a \| &b;
1381	///
1382	/// let mut i = `0`;
1383	/// let expected = [`1`, `2`, `3`, `4`, `5`];
1384	/// for x in &set {
1385	/// assert!(expected.contains(x));
1386	/// i += `1`;
1387	/// }
1388	/// assert_eq!(i, expected.len());
1389	/// ```
1390	fn bitor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S, A> {
1391	self.union(rhs).cloned().collect()
1392	}
1393	}
1394
1395	impl<T, S, A> BitAnd<&HashSet<T, S, A>> for &HashSet<T, S, A>
1396	where
1397	T: Eq + Hash + Clone,
1398	S: BuildHasher + Default,
1399	A: Allocator + Default,
1400	{
1401	type Output = HashSet<T, S, A>;
1402
1403	/// Returns the intersection of `self` and `rhs` as a new `HashSet<T, S>`.
1404	///
1405	/// # Examples
1406	///
1407	/// ```
1408	/// use hashbrown::HashSet;
1409	///
1410	/// let a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1411	/// let b: HashSet<_> = vec![`2`, `3`, `4`].into_iter().collect();
1412	///
1413	/// let set = &a & &b;
1414	///
1415	/// let mut i = `0`;
1416	/// let expected = [`2`, `3`];
1417	/// for x in &set {
1418	/// assert!(expected.contains(x));
1419	/// i += `1`;
1420	/// }
1421	/// assert_eq!(i, expected.len());
1422	/// ```
1423	fn bitand(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S, A> {
1424	self.intersection(rhs).cloned().collect()
1425	}
1426	}
1427
1428	impl<T, S, A> BitXor<&HashSet<T, S, A>> for &HashSet<T, S, A>
1429	where
1430	T: Eq + Hash + Clone,
1431	S: BuildHasher + Default,
1432	A: Allocator + Default,
1433	{
1434	type Output = HashSet<T, S, A>;
1435
1436	/// Returns the symmetric difference of `self` and `rhs` as a new `HashSet<T, S>`.
1437	///
1438	/// # Examples
1439	///
1440	/// ```
1441	/// use hashbrown::HashSet;
1442	///
1443	/// let a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1444	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1445	///
1446	/// let set = &a ^ &b;
1447	///
1448	/// let mut i = `0`;
1449	/// let expected = [`1`, `2`, `4`, `5`];
1450	/// for x in &set {
1451	/// assert!(expected.contains(x));
1452	/// i += `1`;
1453	/// }
1454	/// assert_eq!(i, expected.len());
1455	/// ```
1456	fn bitxor(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S, A> {
1457	self.symmetric_difference(rhs).cloned().collect()
1458	}
1459	}
1460
1461	impl<T, S, A> Sub<&HashSet<T, S, A>> for &HashSet<T, S, A>
1462	where
1463	T: Eq + Hash + Clone,
1464	S: BuildHasher + Default,
1465	A: Allocator + Default,
1466	{
1467	type Output = HashSet<T, S, A>;
1468
1469	/// Returns the difference of `self` and `rhs` as a new `HashSet<T, S>`.
1470	///
1471	/// # Examples
1472	///
1473	/// ```
1474	/// use hashbrown::HashSet;
1475	///
1476	/// let a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1477	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1478	///
1479	/// let set = &a - &b;
1480	///
1481	/// let mut i = `0`;
1482	/// let expected = [`1`, `2`];
1483	/// for x in &set {
1484	/// assert!(expected.contains(x));
1485	/// i += `1`;
1486	/// }
1487	/// assert_eq!(i, expected.len());
1488	/// ```
1489	fn sub(self, rhs: &HashSet<T, S, A>) -> HashSet<T, S, A> {
1490	self.difference(rhs).cloned().collect()
1491	}
1492	}
1493
1494	impl<T, S, A> BitOrAssign<&HashSet<T, S, A>> for HashSet<T, S, A>
1495	where
1496	T: Eq + Hash + Clone,
1497	S: BuildHasher,
1498	A: Allocator,
1499	{
1500	/// Modifies this set to contain the union of `self` and `rhs`.
1501	///
1502	/// # Examples
1503	///
1504	/// ```
1505	/// use hashbrown::HashSet;
1506	///
1507	/// let mut a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1508	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1509	///
1510	/// a \|= &b;
1511	///
1512	/// let mut i = `0`;
1513	/// let expected = [`1`, `2`, `3`, `4`, `5`];
1514	/// for x in &a {
1515	/// assert!(expected.contains(x));
1516	/// i += `1`;
1517	/// }
1518	/// assert_eq!(i, expected.len());
1519	/// ```
1520	fn bitor_assign(&mut self, rhs: &HashSet<T, S, A>) {
1521	for item in rhs {
1522	if !self.contains(item) {
1523	self.insert(item.clone());
1524	}
1525	}
1526	}
1527	}
1528
1529	impl<T, S, A> BitAndAssign<&HashSet<T, S, A>> for HashSet<T, S, A>
1530	where
1531	T: Eq + Hash + Clone,
1532	S: BuildHasher,
1533	A: Allocator,
1534	{
1535	/// Modifies this set to contain the intersection of `self` and `rhs`.
1536	///
1537	/// # Examples
1538	///
1539	/// ```
1540	/// use hashbrown::HashSet;
1541	///
1542	/// let mut a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1543	/// let b: HashSet<_> = vec![`2`, `3`, `4`].into_iter().collect();
1544	///
1545	/// a &= &b;
1546	///
1547	/// let mut i = `0`;
1548	/// let expected = [`2`, `3`];
1549	/// for x in &a {
1550	/// assert!(expected.contains(x));
1551	/// i += `1`;
1552	/// }
1553	/// assert_eq!(i, expected.len());
1554	/// ```
1555	fn bitand_assign(&mut self, rhs: &HashSet<T, S, A>) {
1556	self.retain(\|item\| rhs.contains(item));
1557	}
1558	}
1559
1560	impl<T, S, A> BitXorAssign<&HashSet<T, S, A>> for HashSet<T, S, A>
1561	where
1562	T: Eq + Hash + Clone,
1563	S: BuildHasher,
1564	A: Allocator,
1565	{
1566	/// Modifies this set to contain the symmetric difference of `self` and `rhs`.
1567	///
1568	/// # Examples
1569	///
1570	/// ```
1571	/// use hashbrown::HashSet;
1572	///
1573	/// let mut a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1574	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1575	///
1576	/// a ^= &b;
1577	///
1578	/// let mut i = `0`;
1579	/// let expected = [`1`, `2`, `4`, `5`];
1580	/// for x in &a {
1581	/// assert!(expected.contains(x));
1582	/// i += `1`;
1583	/// }
1584	/// assert_eq!(i, expected.len());
1585	/// ```
1586	fn bitxor_assign(&mut self, rhs: &HashSet<T, S, A>) {
1587	for item in rhs {
1588	let hash = make_hash(&self.map.hash_builder, item);
1589	match self.map.find_or_find_insert_slot(hash, item) {
1590	Ok(bucket) => unsafe {
1591	self.map.table.remove(bucket);
1592	},
1593	Err(slot) => unsafe {
1594	self.map
1595	.table
1596	.insert_in_slot(hash, slot, (item.clone(), ()));
1597	},
1598	}
1599	}
1600	}
1601	}
1602
1603	impl<T, S, A> SubAssign<&HashSet<T, S, A>> for HashSet<T, S, A>
1604	where
1605	T: Eq + Hash + Clone,
1606	S: BuildHasher,
1607	A: Allocator,
1608	{
1609	/// Modifies this set to contain the difference of `self` and `rhs`.
1610	///
1611	/// # Examples
1612	///
1613	/// ```
1614	/// use hashbrown::HashSet;
1615	///
1616	/// let mut a: HashSet<_> = vec![`1`, `2`, `3`].into_iter().collect();
1617	/// let b: HashSet<_> = vec![`3`, `4`, `5`].into_iter().collect();
1618	///
1619	/// a -= &b;
1620	///
1621	/// let mut i = `0`;
1622	/// let expected = [`1`, `2`];
1623	/// for x in &a {
1624	/// assert!(expected.contains(x));
1625	/// i += `1`;
1626	/// }
1627	/// assert_eq!(i, expected.len());
1628	/// ```
1629	fn sub_assign(&mut self, rhs: &HashSet<T, S, A>) {
1630	if rhs.len() < self.len() {
1631	for item in rhs {
1632	self.remove(item);
1633	}
1634	} else {
1635	self.retain(\|item\| !rhs.contains(item));
1636	}
1637	}
1638	}
1639
1640	/// An iterator over the items of a `HashSet`.
1641	///
1642	/// This `struct` is created by the [`iter`] method on [`HashSet`].
1643	/// See its documentation for more.
1644	///
1645	/// [`HashSet`]: struct.HashSet.html
1646	/// [`iter`]: struct.HashSet.html#method.iter
1647	pub struct Iter<'a, K> {
1648	iter: Keys<'a, K, ()>,
1649	}
1650
1651	/// An owning iterator over the items of a `HashSet`.
1652	///
1653	/// This `struct` is created by the [`into_iter`] method on [`HashSet`]
1654	/// (provided by the `IntoIterator` trait). See its documentation for more.
1655	///
1656	/// [`HashSet`]: struct.HashSet.html
1657	/// [`into_iter`]: struct.HashSet.html#method.into_iter
1658	pub struct IntoIter<K, A: Allocator = Global> {
1659	iter: map::IntoIter<K, (), A>,
1660	}
1661
1662	/// A draining iterator over the items of a `HashSet`.
1663	///
1664	/// This `struct` is created by the [`drain`] method on [`HashSet`].
1665	/// See its documentation for more.
1666	///
1667	/// [`HashSet`]: struct.HashSet.html
1668	/// [`drain`]: struct.HashSet.html#method.drain
1669	pub struct Drain<'a, K, A: Allocator = Global> {
1670	iter: map::Drain<'a, K, (), A>,
1671	}
1672
1673	/// A draining iterator over entries of a `HashSet` which don't satisfy the predicate `f`.
1674	///
1675	/// This `struct` is created by the [`extract_if`] method on [`HashSet`]. See its
1676	/// documentation for more.
1677	///
1678	/// [`extract_if`]: struct.HashSet.html#method.extract_if
1679	/// [`HashSet`]: struct.HashSet.html
1680	#[must_use = "Iterators are lazy unless consumed"]
1681	pub struct ExtractIf<'a, K, F, A: Allocator = Global>
1682	where
1683	F: FnMut(&K) -> bool,
1684	{
1685	f: F,
1686	inner: RawExtractIf<'a, (K, ()), A>,
1687	}
1688
1689	/// A lazy iterator producing elements in the intersection of `HashSet`s.
1690	///
1691	/// This `struct` is created by the [`intersection`] method on [`HashSet`].
1692	/// See its documentation for more.
1693	///
1694	/// [`HashSet`]: struct.HashSet.html
1695	/// [`intersection`]: struct.HashSet.html#method.intersection
1696	pub struct Intersection<'a, T, S, A: Allocator = Global> {
1697	// iterator of the first set
1698	iter: Iter<'a, T>,
1699	// the second set
1700	other: &'a HashSet<T, S, A>,
1701	}
1702
1703	/// A lazy iterator producing elements in the difference of `HashSet`s.
1704	///
1705	/// This `struct` is created by the [`difference`] method on [`HashSet`].
1706	/// See its documentation for more.
1707	///
1708	/// [`HashSet`]: struct.HashSet.html
1709	/// [`difference`]: struct.HashSet.html#method.difference
1710	pub struct Difference<'a, T, S, A: Allocator = Global> {
1711	// iterator of the first set
1712	iter: Iter<'a, T>,
1713	// the second set
1714	other: &'a HashSet<T, S, A>,
1715	}
1716
1717	/// A lazy iterator producing elements in the symmetric difference of `HashSet`s.
1718	///
1719	/// This `struct` is created by the [`symmetric_difference`] method on
1720	/// [`HashSet`]. See its documentation for more.
1721	///
1722	/// [`HashSet`]: struct.HashSet.html
1723	/// [`symmetric_difference`]: struct.HashSet.html#method.symmetric_difference
1724	pub struct SymmetricDifference<'a, T, S, A: Allocator = Global> {
1725	iter: Chain<Difference<'a, T, S, A>, Difference<'a, T, S, A>>,
1726	}
1727
1728	/// A lazy iterator producing elements in the union of `HashSet`s.
1729	///
1730	/// This `struct` is created by the [`union`] method on [`HashSet`].
1731	/// See its documentation for more.
1732	///
1733	/// [`HashSet`]: struct.HashSet.html
1734	/// [`union`]: struct.HashSet.html#method.union
1735	pub struct Union<'a, T, S, A: Allocator = Global> {
1736	iter: Chain<Iter<'a, T>, Difference<'a, T, S, A>>,
1737	}
1738
1739	impl<'a, T, S, A: Allocator> IntoIterator for &'a HashSet<T, S, A> {
1740	type Item = &'a T;
1741	type IntoIter = Iter<'a, T>;
1742
1743	#[cfg_attr(feature = "inline-more", inline)]
1744	fn into_iter(self) -> Iter<'a, T> {
1745	self.iter()
1746	}
1747	}
1748
1749	impl<T, S, A: Allocator> IntoIterator for HashSet<T, S, A> {
1750	type Item = T;
1751	type IntoIter = IntoIter<T, A>;
1752
1753	/// Creates a consuming iterator, that is, one that moves each value out
1754	/// of the set in arbitrary order. The set cannot be used after calling
1755	/// this.
1756	///
1757	/// # Examples
1758	///
1759	/// ```
1760	/// use hashbrown::HashSet;
1761	/// let mut set = HashSet::new();
1762	/// set.insert("a".to_string());
1763	/// set.insert("b".to_string());
1764	///
1765	/// // Not possible to collect to a Vec<String> with a regular `.iter()`.
1766	/// let v: Vec<String> = set.into_iter().collect();
1767	///
1768	/// // Will print in an arbitrary order.
1769	/// for x in &v {
1770	/// println!("{}", x);
1771	/// }
1772	/// ```
1773	#[cfg_attr(feature = "inline-more", inline)]
1774	fn into_iter(self) -> IntoIter<T, A> {
1775	IntoIter {
1776	iter: self.map.into_iter(),
1777	}
1778	}
1779	}
1780
1781	impl<K> Clone for Iter<'_, K> {
1782	#[cfg_attr(feature = "inline-more", inline)]
1783	fn clone(&self) -> Self {
1784	Iter {
1785	iter: self.iter.clone(),
1786	}
1787	}
1788	}
1789	impl<K> Default for Iter<'_, K> {
1790	#[cfg_attr(feature = "inline-more", inline)]
1791	fn default() -> Self {
1792	Iter {
1793	iter: Default::default(),
1794	}
1795	}
1796	}
1797	impl<'a, K> Iterator for Iter<'a, K> {
1798	type Item = &'a K;
1799
1800	#[cfg_attr(feature = "inline-more", inline)]
1801	fn next(&mut self) -> Option<&'a K> {
1802	self.iter.next()
1803	}
1804	#[cfg_attr(feature = "inline-more", inline)]
1805	fn size_hint(&self) -> (usize, Option<usize>) {
1806	self.iter.size_hint()
1807	}
1808	#[cfg_attr(feature = "inline-more", inline)]
1809	fn fold<B, F>(self, init: B, f: F) -> B
1810	where
1811	Self: Sized,
1812	F: FnMut(B, Self::Item) -> B,
1813	{
1814	self.iter.fold(init, f)
1815	}
1816	}
1817	impl<K> ExactSizeIterator for Iter<'_, K> {
1818	#[cfg_attr(feature = "inline-more", inline)]
1819	fn len(&self) -> usize {
1820	self.iter.len()
1821	}
1822	}
1823	impl<K> FusedIterator for Iter<'_, K> {}
1824
1825	impl<K: fmt::Debug> fmt::Debug for Iter<'_, K> {
1826	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1827	f.debug_list().entries(self.clone()).finish()
1828	}
1829	}
1830
1831	impl<K, A: Allocator> Default for IntoIter<K, A> {
1832	#[cfg_attr(feature = "inline-more", inline)]
1833	fn default() -> Self {
1834	IntoIter {
1835	iter: Default::default(),
1836	}
1837	}
1838	}
1839	impl<K, A: Allocator> Iterator for IntoIter<K, A> {
1840	type Item = K;
1841
1842	#[cfg_attr(feature = "inline-more", inline)]
1843	fn next(&mut self) -> Option<K> {
1844	// Avoid `Option::map` because it bloats LLVM IR.
1845	match self.iter.next() {
1846	Some((k: K, _)) => Some(k),
1847	None => None,
1848	}
1849	}
1850	#[cfg_attr(feature = "inline-more", inline)]
1851	fn size_hint(&self) -> (usize, Option<usize>) {
1852	self.iter.size_hint()
1853	}
1854	#[cfg_attr(feature = "inline-more", inline)]
1855	fn fold<B, F>(self, init: B, mut f: F) -> B
1856	where
1857	Self: Sized,
1858	F: FnMut(B, Self::Item) -> B,
1859	{
1860	self.iter.fold(init, \|acc: B, (k: K, ())\| f(acc, k))
1861	}
1862	}
1863	impl<K, A: Allocator> ExactSizeIterator for IntoIter<K, A> {
1864	#[cfg_attr(feature = "inline-more", inline)]
1865	fn len(&self) -> usize {
1866	self.iter.len()
1867	}
1868	}
1869	impl<K, A: Allocator> FusedIterator for IntoIter<K, A> {}
1870
1871	impl<K: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<K, A> {
1872	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1873	let entries_iter: impl Iterator = self.iter.iter().map(\|(k: &K, _)\| k);
1874	f.debug_list().entries(entries_iter).finish()
1875	}
1876	}
1877
1878	impl<K, A: Allocator> Iterator for Drain<'_, K, A> {
1879	type Item = K;
1880
1881	#[cfg_attr(feature = "inline-more", inline)]
1882	fn next(&mut self) -> Option<K> {
1883	// Avoid `Option::map` because it bloats LLVM IR.
1884	match self.iter.next() {
1885	Some((k: K, _)) => Some(k),
1886	None => None,
1887	}
1888	}
1889	#[cfg_attr(feature = "inline-more", inline)]
1890	fn size_hint(&self) -> (usize, Option<usize>) {
1891	self.iter.size_hint()
1892	}
1893	#[cfg_attr(feature = "inline-more", inline)]
1894	fn fold<B, F>(self, init: B, mut f: F) -> B
1895	where
1896	Self: Sized,
1897	F: FnMut(B, Self::Item) -> B,
1898	{
1899	self.iter.fold(init, \|acc: B, (k: K, ())\| f(acc, k))
1900	}
1901	}
1902	impl<K, A: Allocator> ExactSizeIterator for Drain<'_, K, A> {
1903	#[cfg_attr(feature = "inline-more", inline)]
1904	fn len(&self) -> usize {
1905	self.iter.len()
1906	}
1907	}
1908	impl<K, A: Allocator> FusedIterator for Drain<'_, K, A> {}
1909
1910	impl<K: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, K, A> {
1911	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1912	let entries_iter: impl Iterator = self.iter.iter().map(\|(k: &K, _)\| k);
1913	f.debug_list().entries(entries_iter).finish()
1914	}
1915	}
1916
1917	impl<K, F, A: Allocator> Iterator for ExtractIf<'_, K, F, A>
1918	where
1919	F: FnMut(&K) -> bool,
1920	{
1921	type Item = K;
1922
1923	#[cfg_attr(feature = "inline-more", inline)]
1924	fn next(&mut self) -> Option<Self::Item> {
1925	self.inner
1926	.next(\|&mut (ref k: &K, ())\| (self.f)(k))
1927	.map(\|(k: K, ())\| k)
1928	}
1929
1930	#[inline]
1931	fn size_hint(&self) -> (usize, Option<usize>) {
1932	(`0`, self.inner.iter.size_hint().1)
1933	}
1934	}
1935
1936	impl<K, F, A: Allocator> FusedIterator for ExtractIf<'_, K, F, A> where F: FnMut(&K) -> bool {}
1937
1938	impl<T, S, A: Allocator> Clone for Intersection<'_, T, S, A> {
1939	#[cfg_attr(feature = "inline-more", inline)]
1940	fn clone(&self) -> Self {
1941	Intersection {
1942	iter: self.iter.clone(),
1943	..*self
1944	}
1945	}
1946	}
1947
1948	impl<'a, T, S, A> Iterator for Intersection<'a, T, S, A>
1949	where
1950	T: Eq + Hash,
1951	S: BuildHasher,
1952	A: Allocator,
1953	{
1954	type Item = &'a T;
1955
1956	#[cfg_attr(feature = "inline-more", inline)]
1957	fn next(&mut self) -> Option<&'a T> {
1958	loop {
1959	let elt = self.iter.next()?;
1960	if self.other.contains(elt) {
1961	return Some(elt);
1962	}
1963	}
1964	}
1965
1966	#[cfg_attr(feature = "inline-more", inline)]
1967	fn size_hint(&self) -> (usize, Option<usize>) {
1968	let (_, upper) = self.iter.size_hint();
1969	(`0`, upper)
1970	}
1971
1972	#[cfg_attr(feature = "inline-more", inline)]
1973	fn fold<B, F>(self, init: B, mut f: F) -> B
1974	where
1975	Self: Sized,
1976	F: FnMut(B, Self::Item) -> B,
1977	{
1978	self.iter.fold(init, \|acc, elt\| {
1979	if self.other.contains(elt) {
1980	f(acc, elt)
1981	} else {
1982	acc
1983	}
1984	})
1985	}
1986	}
1987
1988	impl<T, S, A> fmt::Debug for Intersection<'_, T, S, A>
1989	where
1990	T: fmt::Debug + Eq + Hash,
1991	S: BuildHasher,
1992	A: Allocator,
1993	{
1994	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1995	f.debug_list().entries(self.clone()).finish()
1996	}
1997	}
1998
1999	impl<T, S, A> FusedIterator for Intersection<'_, T, S, A>
2000	where
2001	T: Eq + Hash,
2002	S: BuildHasher,
2003	A: Allocator,
2004	{
2005	}
2006
2007	impl<T, S, A: Allocator> Clone for Difference<'_, T, S, A> {
2008	#[cfg_attr(feature = "inline-more", inline)]
2009	fn clone(&self) -> Self {
2010	Difference {
2011	iter: self.iter.clone(),
2012	..*self
2013	}
2014	}
2015	}
2016
2017	impl<'a, T, S, A> Iterator for Difference<'a, T, S, A>
2018	where
2019	T: Eq + Hash,
2020	S: BuildHasher,
2021	A: Allocator,
2022	{
2023	type Item = &'a T;
2024
2025	#[cfg_attr(feature = "inline-more", inline)]
2026	fn next(&mut self) -> Option<&'a T> {
2027	loop {
2028	let elt = self.iter.next()?;
2029	if !self.other.contains(elt) {
2030	return Some(elt);
2031	}
2032	}
2033	}
2034
2035	#[cfg_attr(feature = "inline-more", inline)]
2036	fn size_hint(&self) -> (usize, Option<usize>) {
2037	let (lower, upper) = self.iter.size_hint();
2038	(lower.saturating_sub(self.other.len()), upper)
2039	}
2040
2041	#[cfg_attr(feature = "inline-more", inline)]
2042	fn fold<B, F>(self, init: B, mut f: F) -> B
2043	where
2044	Self: Sized,
2045	F: FnMut(B, Self::Item) -> B,
2046	{
2047	self.iter.fold(init, \|acc, elt\| {
2048	if self.other.contains(elt) {
2049	acc
2050	} else {
2051	f(acc, elt)
2052	}
2053	})
2054	}
2055	}
2056
2057	impl<T, S, A> FusedIterator for Difference<'_, T, S, A>
2058	where
2059	T: Eq + Hash,
2060	S: BuildHasher,
2061	A: Allocator,
2062	{
2063	}
2064
2065	impl<T, S, A> fmt::Debug for Difference<'_, T, S, A>
2066	where
2067	T: fmt::Debug + Eq + Hash,
2068	S: BuildHasher,
2069	A: Allocator,
2070	{
2071	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2072	f.debug_list().entries(self.clone()).finish()
2073	}
2074	}
2075
2076	impl<T, S, A: Allocator> Clone for SymmetricDifference<'_, T, S, A> {
2077	#[cfg_attr(feature = "inline-more", inline)]
2078	fn clone(&self) -> Self {
2079	SymmetricDifference {
2080	iter: self.iter.clone(),
2081	}
2082	}
2083	}
2084
2085	impl<'a, T, S, A> Iterator for SymmetricDifference<'a, T, S, A>
2086	where
2087	T: Eq + Hash,
2088	S: BuildHasher,
2089	A: Allocator,
2090	{
2091	type Item = &'a T;
2092
2093	#[cfg_attr(feature = "inline-more", inline)]
2094	fn next(&mut self) -> Option<&'a T> {
2095	self.iter.next()
2096	}
2097
2098	#[cfg_attr(feature = "inline-more", inline)]
2099	fn size_hint(&self) -> (usize, Option<usize>) {
2100	self.iter.size_hint()
2101	}
2102
2103	#[cfg_attr(feature = "inline-more", inline)]
2104	fn fold<B, F>(self, init: B, f: F) -> B
2105	where
2106	Self: Sized,
2107	F: FnMut(B, Self::Item) -> B,
2108	{
2109	self.iter.fold(init, f)
2110	}
2111	}
2112
2113	impl<T, S, A> FusedIterator for SymmetricDifference<'_, T, S, A>
2114	where
2115	T: Eq + Hash,
2116	S: BuildHasher,
2117	A: Allocator,
2118	{
2119	}
2120
2121	impl<T, S, A> fmt::Debug for SymmetricDifference<'_, T, S, A>
2122	where
2123	T: fmt::Debug + Eq + Hash,
2124	S: BuildHasher,
2125	A: Allocator,
2126	{
2127	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2128	f.debug_list().entries(self.clone()).finish()
2129	}
2130	}
2131
2132	impl<T, S, A: Allocator> Clone for Union<'_, T, S, A> {
2133	#[cfg_attr(feature = "inline-more", inline)]
2134	fn clone(&self) -> Self {
2135	Union {
2136	iter: self.iter.clone(),
2137	}
2138	}
2139	}
2140
2141	impl<T, S, A> FusedIterator for Union<'_, T, S, A>
2142	where
2143	T: Eq + Hash,
2144	S: BuildHasher,
2145	A: Allocator,
2146	{
2147	}
2148
2149	impl<T, S, A> fmt::Debug for Union<'_, T, S, A>
2150	where
2151	T: fmt::Debug + Eq + Hash,
2152	S: BuildHasher,
2153	A: Allocator,
2154	{
2155	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2156	f.debug_list().entries(self.clone()).finish()
2157	}
2158	}
2159
2160	impl<'a, T, S, A> Iterator for Union<'a, T, S, A>
2161	where
2162	T: Eq + Hash,
2163	S: BuildHasher,
2164	A: Allocator,
2165	{
2166	type Item = &'a T;
2167
2168	#[cfg_attr(feature = "inline-more", inline)]
2169	fn next(&mut self) -> Option<&'a T> {
2170	self.iter.next()
2171	}
2172
2173	#[cfg_attr(feature = "inline-more", inline)]
2174	fn size_hint(&self) -> (usize, Option<usize>) {
2175	self.iter.size_hint()
2176	}
2177
2178	#[cfg_attr(feature = "inline-more", inline)]
2179	fn fold<B, F>(self, init: B, f: F) -> B
2180	where
2181	Self: Sized,
2182	F: FnMut(B, Self::Item) -> B,
2183	{
2184	self.iter.fold(init, f)
2185	}
2186	}
2187
2188	/// A view into a single entry in a set, which may either be vacant or occupied.
2189	///
2190	/// This `enum` is constructed from the [`entry`] method on [`HashSet`].
2191	///
2192	/// [`HashSet`]: struct.HashSet.html
2193	/// [`entry`]: struct.HashSet.html#method.entry
2194	///
2195	/// # Examples
2196	///
2197	/// ```
2198	/// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
2199	///
2200	/// let mut set = HashSet::new();
2201	/// set.extend(["a", "b", "c"]);
2202	/// assert_eq!(set.len(), `3`);
2203	///
2204	/// // Existing value (insert)
2205	/// let entry: Entry<_, _> = set.entry("a");
2206	/// let _raw_o: OccupiedEntry<_, _> = entry.insert();
2207	/// assert_eq!(set.len(), `3`);
2208	/// // Nonexistent value (insert)
2209	/// set.entry("d").insert();
2210	///
2211	/// // Existing value (or_insert)
2212	/// set.entry("b").or_insert();
2213	/// // Nonexistent value (or_insert)
2214	/// set.entry("e").or_insert();
2215	///
2216	/// println!("Our HashSet: {:?}", set);
2217	///
2218	/// let mut vec: Vec<_> = set.iter().copied().collect();
2219	/// // The `Iter` iterator produces items in arbitrary order, so the
2220	/// // items must be sorted to test them against a sorted array.
2221	/// vec.sort_unstable();
2222	/// assert_eq!(vec, ["a", "b", "c", "d", "e"]);
2223	/// ```
2224	pub enum Entry<'a, T, S, A = Global>
2225	where
2226	A: Allocator,
2227	{
2228	/// An occupied entry.
2229	///
2230	/// # Examples
2231	///
2232	/// ```
2233	/// use hashbrown::hash_set::{Entry, HashSet};
2234	/// let mut set: HashSet<_> = ["a", "b"].into();
2235	///
2236	/// match set.entry("a") {
2237	/// Entry::Vacant(_) => unreachable!(),
2238	/// Entry::Occupied(_) => { }
2239	/// }
2240	/// ```
2241	Occupied(OccupiedEntry<'a, T, S, A>),
2242
2243	/// A vacant entry.
2244	///
2245	/// # Examples
2246	///
2247	/// ```
2248	/// use hashbrown::hash_set::{Entry, HashSet};
2249	/// let mut set: HashSet<&str> = HashSet::new();
2250	///
2251	/// match set.entry("a") {
2252	/// Entry::Occupied(_) => unreachable!(),
2253	/// Entry::Vacant(_) => { }
2254	/// }
2255	/// ```
2256	Vacant(VacantEntry<'a, T, S, A>),
2257	}
2258
2259	impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for Entry<'_, T, S, A> {
2260	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2261	match *self {
2262	Entry::Vacant(ref v: &VacantEntry<'_, T, S, A>) => f.debug_tuple(name:"Entry").field(v).finish(),
2263	Entry::Occupied(ref o: &OccupiedEntry<'_, T, S, A>) => f.debug_tuple(name:"Entry").field(o).finish(),
2264	}
2265	}
2266	}
2267
2268	/// A view into an occupied entry in a `HashSet`.
2269	/// It is part of the [`Entry`] enum.
2270	///
2271	/// [`Entry`]: enum.Entry.html
2272	///
2273	/// # Examples
2274	///
2275	/// ```
2276	/// use hashbrown::hash_set::{Entry, HashSet, OccupiedEntry};
2277	///
2278	/// let mut set = HashSet::new();
2279	/// set.extend(["a", "b", "c"]);
2280	///
2281	/// let _entry_o: OccupiedEntry<_, _> = set.entry("a").insert();
2282	/// assert_eq!(set.len(), `3`);
2283	///
2284	/// // Existing key
2285	/// match set.entry("a") {
2286	/// Entry::Vacant(_) => unreachable!(),
2287	/// Entry::Occupied(view) => {
2288	/// assert_eq!(view.get(), &"a");
2289	/// }
2290	/// }
2291	///
2292	/// assert_eq!(set.len(), `3`);
2293	///
2294	/// // Existing key (take)
2295	/// match set.entry("c") {
2296	/// Entry::Vacant(_) => unreachable!(),
2297	/// Entry::Occupied(view) => {
2298	/// assert_eq!(view.remove(), "c");
2299	/// }
2300	/// }
2301	/// assert_eq!(set.get(&"c"), None);
2302	/// assert_eq!(set.len(), `2`);
2303	/// ```
2304	pub struct OccupiedEntry<'a, T, S, A: Allocator = Global> {
2305	inner: map::OccupiedEntry<'a, T, (), S, A>,
2306	}
2307
2308	impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for OccupiedEntry<'_, T, S, A> {
2309	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2310	f&mut DebugStruct<'_, '_>.debug_struct("OccupiedEntry")
2311	.field(name:"value", self.get())
2312	.finish()
2313	}
2314	}
2315
2316	/// A view into a vacant entry in a `HashSet`.
2317	/// It is part of the [`Entry`] enum.
2318	///
2319	/// [`Entry`]: enum.Entry.html
2320	///
2321	/// # Examples
2322	///
2323	/// ```
2324	/// use hashbrown::hash_set::{Entry, HashSet, VacantEntry};
2325	///
2326	/// let mut set = HashSet::<&str>::new();
2327	///
2328	/// let entry_v: VacantEntry<_, _> = match set.entry("a") {
2329	/// Entry::Vacant(view) => view,
2330	/// Entry::Occupied(_) => unreachable!(),
2331	/// };
2332	/// entry_v.insert();
2333	/// assert!(set.contains("a") && set.len() == `1`);
2334	///
2335	/// // Nonexistent key (insert)
2336	/// match set.entry("b") {
2337	/// Entry::Vacant(view) => { view.insert(); },
2338	/// Entry::Occupied(_) => unreachable!(),
2339	/// }
2340	/// assert!(set.contains("b") && set.len() == `2`);
2341	/// ```
2342	pub struct VacantEntry<'a, T, S, A: Allocator = Global> {
2343	inner: map::VacantEntry<'a, T, (), S, A>,
2344	}
2345
2346	impl<T: fmt::Debug, S, A: Allocator> fmt::Debug for VacantEntry<'_, T, S, A> {
2347	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
2348	f.debug_tuple(name:"VacantEntry").field(self.get()).finish()
2349	}
2350	}
2351
2352	impl<'a, T, S, A: Allocator> Entry<'a, T, S, A> {
2353	/// Sets the value of the entry, and returns an `OccupiedEntry`.
2354	///
2355	/// # Examples
2356	///
2357	/// ```
2358	/// use hashbrown::HashSet;
2359	///
2360	/// let mut set: HashSet<&str> = HashSet::new();
2361	/// let entry = set.entry("horseyland").insert();
2362	///
2363	/// assert_eq!(entry.get(), &"horseyland");
2364	/// ```
2365	#[cfg_attr(feature = "inline-more", inline)]
2366	pub fn insert(self) -> OccupiedEntry<'a, T, S, A>
2367	where
2368	T: Hash,
2369	S: BuildHasher,
2370	{
2371	match self {
2372	Entry::Occupied(entry) => entry,
2373	Entry::Vacant(entry) => entry.insert(),
2374	}
2375	}
2376
2377	/// Ensures a value is in the entry by inserting if it was vacant.
2378	///
2379	/// # Examples
2380	///
2381	/// ```
2382	/// use hashbrown::HashSet;
2383	///
2384	/// let mut set: HashSet<&str> = HashSet::new();
2385	///
2386	/// // nonexistent key
2387	/// set.entry("poneyland").or_insert();
2388	/// assert!(set.contains("poneyland"));
2389	///
2390	/// // existing key
2391	/// set.entry("poneyland").or_insert();
2392	/// assert!(set.contains("poneyland"));
2393	/// assert_eq!(set.len(), `1`);
2394	/// ```
2395	#[cfg_attr(feature = "inline-more", inline)]
2396	pub fn or_insert(self)
2397	where
2398	T: Hash,
2399	S: BuildHasher,
2400	{
2401	if let Entry::Vacant(entry) = self {
2402	entry.insert();
2403	}
2404	}
2405
2406	/// Returns a reference to this entry's value.
2407	///
2408	/// # Examples
2409	///
2410	/// ```
2411	/// use hashbrown::HashSet;
2412	///
2413	/// let mut set: HashSet<&str> = HashSet::new();
2414	/// set.entry("poneyland").or_insert();
2415	/// // existing key
2416	/// assert_eq!(set.entry("poneyland").get(), &"poneyland");
2417	/// // nonexistent key
2418	/// assert_eq!(set.entry("horseland").get(), &"horseland");
2419	/// ```
2420	#[cfg_attr(feature = "inline-more", inline)]
2421	pub fn get(&self) -> &T {
2422	match *self {
2423	Entry::Occupied(ref entry) => entry.get(),
2424	Entry::Vacant(ref entry) => entry.get(),
2425	}
2426	}
2427	}
2428
2429	impl<T, S, A: Allocator> OccupiedEntry<'_, T, S, A> {
2430	/// Gets a reference to the value in the entry.
2431	///
2432	/// # Examples
2433	///
2434	/// ```
2435	/// use hashbrown::hash_set::{Entry, HashSet};
2436	///
2437	/// let mut set: HashSet<&str> = HashSet::new();
2438	/// set.entry("poneyland").or_insert();
2439	///
2440	/// match set.entry("poneyland") {
2441	/// Entry::Vacant(_) => panic!(),
2442	/// Entry::Occupied(entry) => assert_eq!(entry.get(), &"poneyland"),
2443	/// }
2444	/// ```
2445	#[cfg_attr(feature = "inline-more", inline)]
2446	pub fn get(&self) -> &T {
2447	self.inner.key()
2448	}
2449
2450	/// Takes the value out of the entry, and returns it.
2451	/// Keeps the allocated memory for reuse.
2452	///
2453	/// # Examples
2454	///
2455	/// ```
2456	/// use hashbrown::HashSet;
2457	/// use hashbrown::hash_set::Entry;
2458	///
2459	/// let mut set: HashSet<&str> = HashSet::new();
2460	/// // The set is empty
2461	/// assert!(set.is_empty() && set.capacity() == `0`);
2462	///
2463	/// set.entry("poneyland").or_insert();
2464	/// let capacity_before_remove = set.capacity();
2465	///
2466	/// if let Entry::Occupied(o) = set.entry("poneyland") {
2467	/// assert_eq!(o.remove(), "poneyland");
2468	/// }
2469	///
2470	/// assert_eq!(set.contains("poneyland"), `false`);
2471	/// // Now set hold none elements but capacity is equal to the old one
2472	/// assert!(set.len() == `0` && set.capacity() == capacity_before_remove);
2473	/// ```
2474	#[cfg_attr(feature = "inline-more", inline)]
2475	pub fn remove(self) -> T {
2476	self.inner.remove_entry().0
2477	}
2478	}
2479
2480	impl<'a, T, S, A: Allocator> VacantEntry<'a, T, S, A> {
2481	/// Gets a reference to the value that would be used when inserting
2482	/// through the `VacantEntry`.
2483	///
2484	/// # Examples
2485	///
2486	/// ```
2487	/// use hashbrown::HashSet;
2488	///
2489	/// let mut set: HashSet<&str> = HashSet::new();
2490	/// assert_eq!(set.entry("poneyland").get(), &"poneyland");
2491	/// ```
2492	#[cfg_attr(feature = "inline-more", inline)]
2493	pub fn get(&self) -> &T {
2494	self.inner.key()
2495	}
2496
2497	/// Take ownership of the value.
2498	///
2499	/// # Examples
2500	///
2501	/// ```
2502	/// use hashbrown::hash_set::{Entry, HashSet};
2503	///
2504	/// let mut set: HashSet<&str> = HashSet::new();
2505	///
2506	/// match set.entry("poneyland") {
2507	/// Entry::Occupied(_) => panic!(),
2508	/// Entry::Vacant(v) => assert_eq!(v.into_value(), "poneyland"),
2509	/// }
2510	/// ```
2511	#[cfg_attr(feature = "inline-more", inline)]
2512	pub fn into_value(self) -> T {
2513	self.inner.into_key()
2514	}
2515
2516	/// Sets the value of the entry with the `VacantEntry`'s value.
2517	///
2518	/// # Examples
2519	///
2520	/// ```
2521	/// use hashbrown::HashSet;
2522	/// use hashbrown::hash_set::Entry;
2523	///
2524	/// let mut set: HashSet<&str> = HashSet::new();
2525	///
2526	/// if let Entry::Vacant(o) = set.entry("poneyland") {
2527	/// o.insert();
2528	/// }
2529	/// assert!(set.contains("poneyland"));
2530	/// ```
2531	#[cfg_attr(feature = "inline-more", inline)]
2532	pub fn insert(self) -> OccupiedEntry<'a, T, S, A>
2533	where
2534	T: Hash,
2535	S: BuildHasher,
2536	{
2537	OccupiedEntry {
2538	inner: self.inner.insert_entry(()),
2539	}
2540	}
2541	}
2542
2543	#[allow(dead_code)]
2544	fn assert_covariance() {
2545	fn set<'new>(v: HashSet<&'static str>) -> HashSet<&'new str> {
2546	v
2547	}
2548	fn iter<'a, 'new>(v: Iter<'a, &'static str>) -> Iter<'a, &'new str> {
2549	v
2550	}
2551	fn into_iter<'new, A: Allocator>(v: IntoIter<&'static str, A>) -> IntoIter<&'new str, A> {
2552	v
2553	}
2554	fn difference<'a, 'new, A: Allocator>(
2555	v: Difference<'a, &'static str, DefaultHashBuilder, A>,
2556	) -> Difference<'a, &'new str, DefaultHashBuilder, A> {
2557	v
2558	}
2559	fn symmetric_difference<'a, 'new, A: Allocator>(
2560	v: SymmetricDifference<'a, &'static str, DefaultHashBuilder, A>,
2561	) -> SymmetricDifference<'a, &'new str, DefaultHashBuilder, A> {
2562	v
2563	}
2564	fn intersection<'a, 'new, A: Allocator>(
2565	v: Intersection<'a, &'static str, DefaultHashBuilder, A>,
2566	) -> Intersection<'a, &'new str, DefaultHashBuilder, A> {
2567	v
2568	}
2569	fn union<'a, 'new, A: Allocator>(
2570	v: Union<'a, &'static str, DefaultHashBuilder, A>,
2571	) -> Union<'a, &'new str, DefaultHashBuilder, A> {
2572	v
2573	}
2574	fn drain<'new, A: Allocator>(d: Drain<'static, &'static str, A>) -> Drain<'new, &'new str, A> {
2575	d
2576	}
2577	}
2578
2579	#[cfg(test)]
2580	mod test_set {
2581	use super::{make_hash, Equivalent, HashSet};
2582	use crate::DefaultHashBuilder;
2583	use std::vec::Vec;
2584
2585	#[test]
2586	fn test_zero_capacities() {
2587	type HS = HashSet<i32>;
2588
2589	let s = HS::new();
2590	assert_eq!(s.capacity(), `0`);
2591
2592	let s = HS::default();
2593	assert_eq!(s.capacity(), `0`);
2594
2595	let s = HS::with_hasher(DefaultHashBuilder::default());
2596	assert_eq!(s.capacity(), `0`);
2597
2598	let s = HS::with_capacity(`0`);
2599	assert_eq!(s.capacity(), `0`);
2600
2601	let s = HS::with_capacity_and_hasher(`0`, DefaultHashBuilder::default());
2602	assert_eq!(s.capacity(), `0`);
2603
2604	let mut s = HS::new();
2605	s.insert(`1`);
2606	s.insert(`2`);
2607	s.remove(&`1`);
2608	s.remove(&`2`);
2609	s.shrink_to_fit();
2610	assert_eq!(s.capacity(), `0`);
2611
2612	let mut s = HS::new();
2613	s.reserve(`0`);
2614	assert_eq!(s.capacity(), `0`);
2615	}
2616
2617	#[test]
2618	fn test_disjoint() {
2619	let mut xs = HashSet::new();
2620	let mut ys = HashSet::new();
2621	assert!(xs.is_disjoint(&ys));
2622	assert!(ys.is_disjoint(&xs));
2623	assert!(xs.insert(`5`));
2624	assert!(ys.insert(`11`));
2625	assert!(xs.is_disjoint(&ys));
2626	assert!(ys.is_disjoint(&xs));
2627	assert!(xs.insert(`7`));
2628	assert!(xs.insert(`19`));
2629	assert!(xs.insert(`4`));
2630	assert!(ys.insert(`2`));
2631	assert!(ys.insert(-`11`));
2632	assert!(xs.is_disjoint(&ys));
2633	assert!(ys.is_disjoint(&xs));
2634	assert!(ys.insert(`7`));
2635	assert!(!xs.is_disjoint(&ys));
2636	assert!(!ys.is_disjoint(&xs));
2637	}
2638
2639	#[test]
2640	fn test_subset_and_superset() {
2641	let mut a = HashSet::new();
2642	assert!(a.insert(`0`));
2643	assert!(a.insert(`5`));
2644	assert!(a.insert(`11`));
2645	assert!(a.insert(`7`));
2646
2647	let mut b = HashSet::new();
2648	assert!(b.insert(`0`));
2649	assert!(b.insert(`7`));
2650	assert!(b.insert(`19`));
2651	assert!(b.insert(`250`));
2652	assert!(b.insert(`11`));
2653	assert!(b.insert(`200`));
2654
2655	assert!(!a.is_subset(&b));
2656	assert!(!a.is_superset(&b));
2657	assert!(!b.is_subset(&a));
2658	assert!(!b.is_superset(&a));
2659
2660	assert!(b.insert(`5`));
2661
2662	assert!(a.is_subset(&b));
2663	assert!(!a.is_superset(&b));
2664	assert!(!b.is_subset(&a));
2665	assert!(b.is_superset(&a));
2666	}
2667
2668	#[test]
2669	fn test_iterate() {
2670	let mut a = HashSet::new();
2671	for i in `0`..`32` {
2672	assert!(a.insert(i));
2673	}
2674	let mut observed: u32 = `0`;
2675	for k in &a {
2676	observed \|= `1` << *k;
2677	}
2678	assert_eq!(observed, `0xFFFF_FFFF`);
2679	}
2680
2681	#[test]
2682	fn test_intersection() {
2683	let mut a = HashSet::new();
2684	let mut b = HashSet::new();
2685
2686	assert!(a.insert(`11`));
2687	assert!(a.insert(`1`));
2688	assert!(a.insert(`3`));
2689	assert!(a.insert(`77`));
2690	assert!(a.insert(`103`));
2691	assert!(a.insert(`5`));
2692	assert!(a.insert(-`5`));
2693
2694	assert!(b.insert(`2`));
2695	assert!(b.insert(`11`));
2696	assert!(b.insert(`77`));
2697	assert!(b.insert(-`9`));
2698	assert!(b.insert(-`42`));
2699	assert!(b.insert(`5`));
2700	assert!(b.insert(`3`));
2701
2702	let mut i = `0`;
2703	let expected = [`3`, `5`, `11`, `77`];
2704	for x in a.intersection(&b) {
2705	assert!(expected.contains(x));
2706	i += `1`;
2707	}
2708	assert_eq!(i, expected.len());
2709	}
2710
2711	#[test]
2712	fn test_difference() {
2713	let mut a = HashSet::new();
2714	let mut b = HashSet::new();
2715
2716	assert!(a.insert(`1`));
2717	assert!(a.insert(`3`));
2718	assert!(a.insert(`5`));
2719	assert!(a.insert(`9`));
2720	assert!(a.insert(`11`));
2721
2722	assert!(b.insert(`3`));
2723	assert!(b.insert(`9`));
2724
2725	let mut i = `0`;
2726	let expected = [`1`, `5`, `11`];
2727	for x in a.difference(&b) {
2728	assert!(expected.contains(x));
2729	i += `1`;
2730	}
2731	assert_eq!(i, expected.len());
2732	}
2733
2734	#[test]
2735	fn test_symmetric_difference() {
2736	let mut a = HashSet::new();
2737	let mut b = HashSet::new();
2738
2739	assert!(a.insert(`1`));
2740	assert!(a.insert(`3`));
2741	assert!(a.insert(`5`));
2742	assert!(a.insert(`9`));
2743	assert!(a.insert(`11`));
2744
2745	assert!(b.insert(-`2`));
2746	assert!(b.insert(`3`));
2747	assert!(b.insert(`9`));
2748	assert!(b.insert(`14`));
2749	assert!(b.insert(`22`));
2750
2751	let mut i = `0`;
2752	let expected = [`-2`, `1`, `5`, `11`, `14`, `22`];
2753	for x in a.symmetric_difference(&b) {
2754	assert!(expected.contains(x));
2755	i += `1`;
2756	}
2757	assert_eq!(i, expected.len());
2758	}
2759
2760	#[test]
2761	fn test_union() {
2762	let mut a = HashSet::new();
2763	let mut b = HashSet::new();
2764
2765	assert!(a.insert(`1`));
2766	assert!(a.insert(`3`));
2767	assert!(a.insert(`5`));
2768	assert!(a.insert(`9`));
2769	assert!(a.insert(`11`));
2770	assert!(a.insert(`16`));
2771	assert!(a.insert(`19`));
2772	assert!(a.insert(`24`));
2773
2774	assert!(b.insert(-`2`));
2775	assert!(b.insert(`1`));
2776	assert!(b.insert(`5`));
2777	assert!(b.insert(`9`));
2778	assert!(b.insert(`13`));
2779	assert!(b.insert(`19`));
2780
2781	let mut i = `0`;
2782	let expected = [`-2`, `1`, `3`, `5`, `9`, `11`, `13`, `16`, `19`, `24`];
2783	for x in a.union(&b) {
2784	assert!(expected.contains(x));
2785	i += `1`;
2786	}
2787	assert_eq!(i, expected.len());
2788	}
2789
2790	#[test]
2791	fn test_from_map() {
2792	let mut a = crate::HashMap::new();
2793	a.insert(`1`, ());
2794	a.insert(`2`, ());
2795	a.insert(`3`, ());
2796	a.insert(`4`, ());
2797
2798	let a: HashSet<_> = a.into();
2799
2800	assert_eq!(a.len(), `4`);
2801	assert!(a.contains(&`1`));
2802	assert!(a.contains(&`2`));
2803	assert!(a.contains(&`3`));
2804	assert!(a.contains(&`4`));
2805	}
2806
2807	#[test]
2808	fn test_from_iter() {
2809	let xs = [`1`, `2`, `2`, `3`, `4`, `5`, `6`, `7`, `8`, `9`];
2810
2811	let set: HashSet<_> = xs.iter().copied().collect();
2812
2813	for x in &xs {
2814	assert!(set.contains(x));
2815	}
2816
2817	assert_eq!(set.iter().len(), xs.len() - `1`);
2818	}
2819
2820	#[test]
2821	fn test_move_iter() {
2822	let hs = {
2823	let mut hs = HashSet::new();
2824
2825	hs.insert('a');
2826	hs.insert('b');
2827
2828	hs
2829	};
2830
2831	let v = hs.into_iter().collect::<Vec<char>>();
2832	assert!(v == ['a', 'b'] \|\| v == ['b', 'a']);
2833	}
2834
2835	#[test]
2836	fn test_eq() {
2837	// These constants once happened to expose a bug in insert().
2838	// I'm keeping them around to prevent a regression.
2839	let mut s1 = HashSet::new();
2840
2841	s1.insert(`1`);
2842	s1.insert(`2`);
2843	s1.insert(`3`);
2844
2845	let mut s2 = HashSet::new();
2846
2847	s2.insert(`1`);
2848	s2.insert(`2`);
2849
2850	assert!(s1 != s2);
2851
2852	s2.insert(`3`);
2853
2854	assert_eq!(s1, s2);
2855	}
2856
2857	#[test]
2858	fn test_show() {
2859	let mut set = HashSet::new();
2860	let empty = HashSet::<i32>::new();
2861
2862	set.insert(`1`);
2863	set.insert(`2`);
2864
2865	let set_str = format!("{set:?}");
2866
2867	assert!(set_str == "{1, 2}" \|\| set_str == "{2, 1}");
2868	assert_eq!(format!("{empty:?}"), "{}");
2869	}
2870
2871	#[test]
2872	fn test_trivial_drain() {
2873	let mut s = HashSet::<i32>::new();
2874	for _ in s.drain() {}
2875	assert!(s.is_empty());
2876	drop(s);
2877
2878	let mut s = HashSet::<i32>::new();
2879	drop(s.drain());
2880	assert!(s.is_empty());
2881	}
2882
2883	#[test]
2884	fn test_drain() {
2885	let mut s: HashSet<_> = (`1`..`100`).collect();
2886
2887	// try this a bunch of times to make sure we don't screw up internal state.
2888	for _ in `0`..`20` {
2889	assert_eq!(s.len(), `99`);
2890
2891	{
2892	let mut last_i = `0`;
2893	let mut d = s.drain();
2894	for (i, x) in d.by_ref().take(`50`).enumerate() {
2895	last_i = i;
2896	assert!(x != `0`);
2897	}
2898	assert_eq!(last_i, `49`);
2899	}
2900
2901	if !s.is_empty() {
2902	panic!("s should be empty!");
2903	}
2904
2905	// reset to try again.
2906	s.extend(`1`..`100`);
2907	}
2908	}
2909
2910	#[test]
2911	fn test_replace() {
2912	use core::hash;
2913
2914	#[derive(Debug)]
2915	#[allow(dead_code)]
2916	struct Foo(&'static str, i32);
2917
2918	impl PartialEq for Foo {
2919	fn eq(&self, other: &Self) -> bool {
2920	self.0 == other.0
2921	}
2922	}
2923
2924	impl Eq for Foo {}
2925
2926	impl hash::Hash for Foo {
2927	fn hash<H: hash::Hasher>(&self, h: &mut H) {
2928	self.0.hash(h);
2929	}
2930	}
2931
2932	let mut s = HashSet::new();
2933	assert_eq!(s.replace(Foo("a", `1`)), None);
2934	assert_eq!(s.len(), `1`);
2935	assert_eq!(s.replace(Foo("a", `2`)), Some(Foo("a", `1`)));
2936	assert_eq!(s.len(), `1`);
2937
2938	let mut it = s.iter();
2939	assert_eq!(it.next(), Some(&Foo("a", `2`)));
2940	assert_eq!(it.next(), None);
2941	}
2942
2943	#[test]
2944	#[allow(clippy::needless_borrow)]
2945	fn test_extend_ref() {
2946	let mut a = HashSet::new();
2947	a.insert(`1`);
2948
2949	a.extend([`2`, `3`, `4`]);
2950
2951	assert_eq!(a.len(), `4`);
2952	assert!(a.contains(&`1`));
2953	assert!(a.contains(&`2`));
2954	assert!(a.contains(&`3`));
2955	assert!(a.contains(&`4`));
2956
2957	let mut b = HashSet::new();
2958	b.insert(`5`);
2959	b.insert(`6`);
2960
2961	a.extend(&b);
2962
2963	assert_eq!(a.len(), `6`);
2964	assert!(a.contains(&`1`));
2965	assert!(a.contains(&`2`));
2966	assert!(a.contains(&`3`));
2967	assert!(a.contains(&`4`));
2968	assert!(a.contains(&`5`));
2969	assert!(a.contains(&`6`));
2970	}
2971
2972	#[test]
2973	fn test_retain() {
2974	let xs = [`1`, `2`, `3`, `4`, `5`, `6`];
2975	let mut set: HashSet<i32> = xs.iter().copied().collect();
2976	set.retain(\|&k\| k % `2` == `0`);
2977	assert_eq!(set.len(), `3`);
2978	assert!(set.contains(&`2`));
2979	assert!(set.contains(&`4`));
2980	assert!(set.contains(&`6`));
2981	}
2982
2983	#[test]
2984	fn test_extract_if() {
2985	{
2986	let mut set: HashSet<i32> = (`0`..`8`).collect();
2987	let drained = set.extract_if(\|&k\| k % `2` == `0`);
2988	let mut out = drained.collect::<Vec<_>>();
2989	out.sort_unstable();
2990	assert_eq!(vec![`0`, `2`, `4`, `6`], out);
2991	assert_eq!(set.len(), `4`);
2992	}
2993	{
2994	let mut set: HashSet<i32> = (`0`..`8`).collect();
2995	set.extract_if(\|&k\| k % `2` == `0`).for_each(drop);
2996	assert_eq!(set.len(), `4`, "Removes non-matching items on drop");
2997	}
2998	}
2999
3000	#[test]
3001	fn test_const_with_hasher() {
3002	use core::hash::BuildHasher;
3003	use std::collections::hash_map::DefaultHasher;
3004
3005	#[derive(Clone)]
3006	struct MyHasher;
3007	impl BuildHasher for MyHasher {
3008	type Hasher = DefaultHasher;
3009
3010	fn build_hasher(&self) -> DefaultHasher {
3011	DefaultHasher::new()
3012	}
3013	}
3014
3015	const EMPTY_SET: HashSet<u32, MyHasher> = HashSet::with_hasher(MyHasher);
3016
3017	let mut set = EMPTY_SET;
3018	set.insert(`19`);
3019	assert!(set.contains(&`19`));
3020	}
3021
3022	#[test]
3023	fn rehash_in_place() {
3024	let mut set = HashSet::new();
3025
3026	for i in `0`..`224` {
3027	set.insert(i);
3028	}
3029
3030	assert_eq!(
3031	set.capacity(),
3032	`224`,
3033	"The set must be at or close to capacity to trigger a re hashing"
3034	);
3035
3036	for i in `100`..`1400` {
3037	set.remove(&(i - `100`));
3038	set.insert(i);
3039	}
3040	}
3041
3042	#[test]
3043	fn collect() {
3044	// At the time of writing, this hits the ZST case in from_base_index
3045	// (and without the `map`, it does not).
3046	let mut _set: HashSet<_> = (`0`..`3`).map(\|_\| ()).collect();
3047	}
3048
3049	#[test]
3050	fn test_allocation_info() {
3051	assert_eq!(HashSet::<()>::new().allocation_size(), `0`);
3052	assert_eq!(HashSet::<u32>::new().allocation_size(), `0`);
3053	assert!(HashSet::<u32>::with_capacity(`1`).allocation_size() > core::mem::size_of::<u32>());
3054	}
3055
3056	#[test]
3057	fn duplicate_insert() {
3058	let mut set = HashSet::new();
3059	set.insert(`1`);
3060	set.get_or_insert_with(&`1`, \|_\| `1`);
3061	set.get_or_insert_with(&`1`, \|_\| `1`);
3062	assert!([`1`].iter().eq(set.iter()));
3063	}
3064
3065	#[test]
3066	#[should_panic]
3067	fn some_invalid_equivalent() {
3068	use core::hash::{Hash, Hasher};
3069	struct Invalid {
3070	count: u32,
3071	other: u32,
3072	}
3073
3074	struct InvalidRef {
3075	count: u32,
3076	other: u32,
3077	}
3078
3079	impl PartialEq for Invalid {
3080	fn eq(&self, other: &Self) -> bool {
3081	self.count == other.count && self.other == other.other
3082	}
3083	}
3084	impl Eq for Invalid {}
3085
3086	impl Equivalent<Invalid> for InvalidRef {
3087	fn equivalent(&self, key: &Invalid) -> bool {
3088	self.count == key.count && self.other == key.other
3089	}
3090	}
3091	impl Hash for Invalid {
3092	fn hash<H: Hasher>(&self, state: &mut H) {
3093	self.count.hash(state);
3094	}
3095	}
3096	impl Hash for InvalidRef {
3097	fn hash<H: Hasher>(&self, state: &mut H) {
3098	self.count.hash(state);
3099	}
3100	}
3101	let mut set: HashSet<Invalid> = HashSet::new();
3102	let key = InvalidRef { count: `1`, other: `1` };
3103	let value = Invalid { count: `1`, other: `2` };
3104	if make_hash(set.hasher(), &key) == make_hash(set.hasher(), &value) {
3105	set.get_or_insert_with(&key, \|_\| value);
3106	}
3107	}
3108	}
3109