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 | |