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