summary refs log tree commit diff
path: root/src/libstd/collections/hash/set.rs
AgeCommit message (Collapse)AuthorLines
2016-12-18Implement `fmt::Debug` for all structures in libstd.Corey Farwell-0/+77
Part of https://github.com/rust-lang/rust/issues/31869. Also turn on the `missing_debug_implementations` lint at the crate level.
2016-12-06Smarter HashMap/HashSet extendarthurprs-7/+3
2016-10-06Auto merge of #36753 - srinivasreddy:hash, r=nrcbors-76/+159
run rustfmt on libstd/collections/hash folder
2016-10-03Auto merge of #36766 - nnethercote:hash-span-capacity, r=blussbors-5/+28
Clarify HashMap's capacity handling. HashMap has two notions of "capacity": - "Usable capacity": the number of elements a hash map can hold without resizing. This is the meaning of "capacity" used in HashMap's API, e.g. the `with_capacity()` function. - "Internal capacity": the number of allocated slots. Except for the zero case, it is always larger than the usable capacity (because some slots must be left empty) and is always a power of two. HashMap's code is confusing because it does a poor job of distinguishing these two meanings. I propose using two different terms for these two concepts. Because "capacity" is already used in HashMap's API to mean "usable capacity", I will use a different word for "internal capacity". I propose "span", though I'm happy to consider other names.
2016-09-29Clarify HashMap's capacity handling.Nicholas Nethercote-5/+28
This commit does the following. - Changes the terminology for capacities used within HashMap's code. "Internal capacity" is now consistently "raw capacity", and "usable capacity" is now consistently just "capacity". This makes the code easier to understand. - Reworks capacity and raw capacity computations. Raw capacity computations are now handled in a single place: `DefaultResizePolicy::raw_capacity()`. This function correctly returns zero when given zero, which means that the following cases now result in a capacity of zero when they previously did not. * `Hash{Map,Set}::with_capacity(0)` * `Hash{Map,Set}::with_capacity_and_hasher(0)` * `Hash{Map,Set}::shrink_to_fit()`, when used with a hash map/set whose elements have all been removed - Strengthens the language used in the comments describing the above functions, to make it clearer when they will result in a map/set with a capacity of zero. The new language is based on the language used for the corresponding functions in `Vec`. - Adds tests for the above zero-capacity cases. - Removes `test_resize_policy` because it is no longer useful.
2016-09-28Rollup merge of #36740 - frehberg:apidoc, r=steveklabnikJonathan Turner-0/+14
Document init of HashSet/HashMap from vector
2016-09-27Update set.rsFrank Rehberger-0/+2
2016-09-27run rustfmt on libstd/collections/hash folderSrinivas Reddy Thatiparthy-76/+159
2016-09-26Update set.rsFrank Rehberger-1/+1
2016-09-26Update set.rsFrank Rehberger-4/+2
2016-09-26Document init of HashSet/HashMap from vectorFrank Rehberger-0/+14
2016-09-26Don't allocate during default HashSet creation.Nicholas Nethercote-8/+19
The following `HashMap` creation functions don't allocate heap storage for elements. ``` HashMap::new() HashMap::default() HashMap::with_hasher() ``` This is good, because it's surprisingly common to create a HashMap and never use it. So that case should be cheap. However, `HashSet` does not have the same behaviour. The corresponding creation functions *do* allocate heap storage for the default number of non-zero elements (which is 32 slots for 29 elements). ``` HashMap::new() HashMap::default() HashMap::with_hasher() ``` This commit gives `HashSet` the same behaviour as `HashMap`, by simply calling the corresponding `HashMap` functions (something `HashSet` already does for `with_capacity` and `with_capacity_and_hasher`). It also reformats one existing `HashSet` construction to use a consistent single-line format. This speeds up rustc itself by 1.01--1.04x on most of the non-tiny rustc-benchmarks.
2016-09-11Documentation for default types modifiedathulappadan-1/+1
2016-09-11Documentation of what does for each typeathulappadan-0/+1
2016-08-24Use `#[prelude_import]` in `libstd`.Jeffrey Seyfried-2/+0
2016-08-18Add a FusedIterator trait.Steven Allen-1/+27
This trait can be used to avoid the overhead of a fuse wrapper when an iterator is already well-behaved. Conforming to: RFC 1581 Closes: #35602
2016-08-04Made vec_deque::Drain, hash_map::Drain, and hash_set::Drain covariantThomas Garcia-0/+1
2016-04-22Make HashSet::Insert documentation more consistentBrayden Winterton-2/+2
2016-04-11std: Stabilize APIs for the 1.9 releaseAlex Crichton-5/+4
This commit applies all stabilizations, renamings, and deprecations that the library team has decided on for the upcoming 1.9 release. All tracking issues have gone through a cycle-long "final comment period" and the specific APIs stabilized/deprecated are: Stable * `std::panic` * `std::panic::catch_unwind` (renamed from `recover`) * `std::panic::resume_unwind` (renamed from `propagate`) * `std::panic::AssertUnwindSafe` (renamed from `AssertRecoverSafe`) * `std::panic::UnwindSafe` (renamed from `RecoverSafe`) * `str::is_char_boundary` * `<*const T>::as_ref` * `<*mut T>::as_ref` * `<*mut T>::as_mut` * `AsciiExt::make_ascii_uppercase` * `AsciiExt::make_ascii_lowercase` * `char::decode_utf16` * `char::DecodeUtf16` * `char::DecodeUtf16Error` * `char::DecodeUtf16Error::unpaired_surrogate` * `BTreeSet::take` * `BTreeSet::replace` * `BTreeSet::get` * `HashSet::take` * `HashSet::replace` * `HashSet::get` * `OsString::with_capacity` * `OsString::clear` * `OsString::capacity` * `OsString::reserve` * `OsString::reserve_exact` * `OsStr::is_empty` * `OsStr::len` * `std::os::unix::thread` * `RawPthread` * `JoinHandleExt` * `JoinHandleExt::as_pthread_t` * `JoinHandleExt::into_pthread_t` * `HashSet::hasher` * `HashMap::hasher` * `CommandExt::exec` * `File::try_clone` * `SocketAddr::set_ip` * `SocketAddr::set_port` * `SocketAddrV4::set_ip` * `SocketAddrV4::set_port` * `SocketAddrV6::set_ip` * `SocketAddrV6::set_port` * `SocketAddrV6::set_flowinfo` * `SocketAddrV6::set_scope_id` * `<[T]>::copy_from_slice` * `ptr::read_volatile` * `ptr::write_volatile` * The `#[deprecated]` attribute * `OpenOptions::create_new` Deprecated * `std::raw::Slice` - use raw parts of `slice` module instead * `std::raw::Repr` - use raw parts of `slice` module instead * `str::char_range_at` - use slicing plus `chars()` plus `len_utf8` * `str::char_range_at_reverse` - use slicing plus `chars().rev()` plus `len_utf8` * `str::char_at` - use slicing plus `chars()` * `str::char_at_reverse` - use slicing plus `chars().rev()` * `str::slice_shift_char` - use `chars()` plus `Chars::as_str` * `CommandExt::session_leader` - use `before_exec` instead. Closes #27719 cc #27751 (deprecating the `Slice` bits) Closes #27754 Closes #27780 Closes #27809 Closes #27811 Closes #27830 Closes #28050 Closes #29453 Closes #29791 Closes #29935 Closes #30014 Closes #30752 Closes #31262 cc #31398 (still need to deal with `before_exec`) Closes #31405 Closes #31572 Closes #31755 Closes #31756
2016-03-30Test that HashMap, HashSet, and their iterators are properly covariantJonathan S-0/+15
2016-03-30Fix the variances of HashMap and HashSet iteratorsJonathan S-9/+7
2016-03-30Remove no longer necessary coercions to fn pointer types.Corey Farwell-4/+0
Originally added in 8fe9e4dff6d9d0fdd940835ae377edcb3754f8c1. Everything appears to build fine without the coercions, so they can presumably be removed.
2016-03-28style: Use `iter` for IntoIterator parameter namesKamal Marhubi-4/+4
This commit standardizes the codebase on `iter` for parameters with IntoIterator bounds. Previously about 40% of IntoIterator parameters were named `iterable`, with most of the rest being named `iter`. There was a single place where it was named `iterator`.
2016-03-12std: Clean out deprecated APIsAlex Crichton-20/+0
Removes all unstable and deprecated APIs prior to the 1.8 release. All APIs that are deprecated in the 1.8 release are sticking around for the rest of this cycle. Some notable changes are: * The `dynamic_lib` module was moved into `rustc_back` as the compiler still relies on a few bits and pieces. * The `DebugTuple` formatter now special-cases an empty struct name with only one field to append a trailing comma.
2016-02-11Add a public hasher function for HashSet and HashMapRyan Thomas-0/+7
2016-01-26std: Stabilize custom hasher support in HashMapAlex Crichton-41/+54
This commit implements the stabilization of the custom hasher support intended for 1.7 but left out due to some last-minute questions that needed some decisions. A summary of the actions done in this PR are: Stable * `std::hash::BuildHasher` * `BuildHasher::Hasher` * `BuildHasher::build_hasher` * `std::hash::BuildHasherDefault` * `HashMap::with_hasher` * `HashMap::with_capacity_and_hasher` * `HashSet::with_hasher` * `HashSet::with_capacity_and_hasher` * `std::collections::hash_map::RandomState` * `RandomState::new` Deprecated * `std::collections::hash_state` * `std::collections::hash_state::HashState` - this trait was also moved into `std::hash` with a reexport here to ensure that we can have a blanket impl to prevent immediate breakage on nightly. Note that this is unstable in both location. * `HashMap::with_hash_state` - renamed * `HashMap::with_capacity_and_hash_state` - renamed * `HashSet::with_hash_state` - renamed * `HashSet::with_capacity_and_hash_state` - renamed Closes #27713
2015-12-17Remove unused importsJeffrey Seyfried-1/+0
2015-12-05std: Stabilize APIs for the 1.6 releaseAlex Crichton-3/+1
This commit is the standard API stabilization commit for the 1.6 release cycle. The list of issues and APIs below have all been through their cycle-long FCP and the libs team decisions are listed below Stabilized APIs * `Read::read_exact` * `ErrorKind::UnexpectedEof` (renamed from `UnexpectedEOF`) * libcore -- this was a bit of a nuanced stabilization, the crate itself is now marked as `#[stable]` and the methods appearing via traits for primitives like `char` and `str` are now also marked as stable. Note that the extension traits themeselves are marked as unstable as they're imported via the prelude. The `try!` macro was also moved from the standard library into libcore to have the same interface. Otherwise the functions all have copied stability from the standard library now. * The `#![no_std]` attribute * `fs::DirBuilder` * `fs::DirBuilder::new` * `fs::DirBuilder::recursive` * `fs::DirBuilder::create` * `os::unix::fs::DirBuilderExt` * `os::unix::fs::DirBuilderExt::mode` * `vec::Drain` * `vec::Vec::drain` * `string::Drain` * `string::String::drain` * `vec_deque::Drain` * `vec_deque::VecDeque::drain` * `collections::hash_map::Drain` * `collections::hash_map::HashMap::drain` * `collections::hash_set::Drain` * `collections::hash_set::HashSet::drain` * `collections::binary_heap::Drain` * `collections::binary_heap::BinaryHeap::drain` * `Vec::extend_from_slice` (renamed from `push_all`) * `Mutex::get_mut` * `Mutex::into_inner` * `RwLock::get_mut` * `RwLock::into_inner` * `Iterator::min_by_key` (renamed from `min_by`) * `Iterator::max_by_key` (renamed from `max_by`) Deprecated APIs * `ErrorKind::UnexpectedEOF` (renamed to `UnexpectedEof`) * `OsString::from_bytes` * `OsStr::to_cstring` * `OsStr::to_bytes` * `fs::walk_dir` and `fs::WalkDir` * `path::Components::peek` * `slice::bytes::MutableByteVector` * `slice::bytes::copy_memory` * `Vec::push_all` (renamed to `extend_from_slice`) * `Duration::span` * `IpAddr` * `SocketAddr::ip` * `Read::tee` * `io::Tee` * `Write::broadcast` * `io::Broadcast` * `Iterator::min_by` (renamed to `min_by_key`) * `Iterator::max_by` (renamed to `max_by_key`) * `net::lookup_addr` New APIs (still unstable) * `<[T]>::sort_by_key` (added to mirror `min_by_key`) Closes #27585 Closes #27704 Closes #27707 Closes #27710 Closes #27711 Closes #27727 Closes #27740 Closes #27744 Closes #27799 Closes #27801 cc #27801 (doesn't close as `Chars` is still unstable) Closes #28968
2015-11-20Rename result variable in HashSet's intersection and union examplesFlorian Hahn-4/+4
2015-11-18Add missing annotations and some testsVadim Petrochenkov-0/+5
2015-11-16Fix docs for HashSet::insertSebastian Hahn-4/+1
insert() returns bool, but it was wrongly stated that if the set had the key already present, that key would be returned (this was probably copied from the HashMap docs). Also remove a reference to the module-level documentation, which doesn't make sense as it doesn't give any more context.
2015-11-06Remove stability annotations from trait impl itemsVadim Petrochenkov-1/+0
Remove `stable` stability annotations from inherent impls
2015-10-22Document replacement behavior in some collectionsSteve Klabnik-2/+8
{BTree,Hash}{Map,Set} will not update their key if it already exists, which can matter with more complex keys. This behavior is now documented. Fixes #26888
2015-08-31Implement RFC 839 for `{HashMap, HashSet}`Andrew Paseltiner-0/+38
It appears that these impls were left out of #25989 by mistake.
2015-08-28implement RFC 1194Andrew Paseltiner-0/+64
2015-08-15std: Add issues to all unstable featuresAlex Crichton-3/+6
2015-07-27Show appropriate feature flags in docsSteve Klabnik-2/+4
2015-06-17std: Split the `std_misc` featureAlex Crichton-6/+8
2015-06-10Removed many pointless calls to *iter() and iter_mut()Joshua Landau-5/+5
2015-05-17Make debug builders take &mut self, add entries methodSteven Fackler-1/+1
[breaking-change]
2015-05-03Fix Derive Notice for HashSetPascal Hertleif-2/+2
2015-05-03Clean up HashSet ExamplesPascal Hertleif-5/+5
2015-05-03HashSet Docs: Split First ParagraphPascal Hertleif-4/+6
This way, the module index renders only the first sentence as a short description.
2015-04-21rollup merge of #24541: alexcrichton/issue-24538Alex Crichton-29/+24
This is an implementation of [RFC 1030][rfc] which adds these traits to the prelude and additionally removes all inherent `into_iter` methods on collections in favor of the trait implementation (which is now accessible by default). [rfc]: https://github.com/rust-lang/rfcs/pull/1030 This is technically a breaking change due to the prelude additions and removal of inherent methods, but it is expected that essentially no code breaks in practice. [breaking-change] Closes #24538
2015-04-21Model lexer: Fix remaining issuesPiotr Czarnecki-2/+0
2015-04-17std: Add Default/IntoIterator/ToOwned to the preludeAlex Crichton-29/+24
This is an implementation of [RFC 1030][rfc] which adds these traits to the prelude and additionally removes all inherent `into_iter` methods on collections in favor of the trait implementation (which is now accessible by default). [rfc]: https://github.com/rust-lang/rfcs/pull/1030 This is technically a breaking change due to the prelude additions and removal of inherent methods, but it is expected that essentially no code breaks in practice. [breaking-change] Closes #24538
2015-04-14Positive case of `len()` -> `is_empty()`Tamir Duberstein-1/+1
`s/(?<!\{ self)(?<=\.)len\(\) == 0/is_empty()/g`
2015-04-13pluralize doc comment verbs and add missing periodsAndrew Paseltiner-5/+5
2015-04-07std: Deny most warnings in doctestsAlex Crichton-8/+0
Allow a few specific ones but otherwise this helps ensure that our examples are squeaky clean! Closes #18199
2015-03-31std: Remove #[old_orphan_check] from PartialEqAlex Crichton-1/+1
This is a deprecated attribute that is slated for removal, and it also affects all implementors of the trait. This commit removes the attribute and fixes up implementors accordingly. The primary implementation which was lost was the ability to compare `&[T]` and `Vec<T>` (in that order). This change also modifies the `assert_eq!` macro to not consider both directions of equality, only the one given in the left/right forms to the macro. This modification is motivated due to the fact that `&[T] == Vec<T>` no longer compiles, causing hundreds of errors in unit tests in the standard library (and likely throughout the community as well). cc #19470 [breaking-change]
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-07 21:53:34 +0000