about summary refs log tree commit diff
path: root/library/std/src/collections
AgeCommit message (Collapse)AuthorLines
2023-11-02Add insta-stable std::hash::{DefaultHasher, RandomState} exportsltdk-6/+6
2023-11-02Move RandomState and DefaultHasher into std::hash, but don't export for nowltdk-154/+10
2023-10-20s/generator/coroutine/Oli Scherer-1/+1
2023-10-07Auto merge of #109214 - tosti007:std_collection_hash_new_rework, ↵bors-1/+1
r=workingjubilee Use `HashMap::with_capacity_and_hasher` instead of using base Cleans up the internal logic for `HashMap::with_capacity` slightly.
2023-08-07Increase clarity about Hash - Eq consistency in HashMap and HashSet docsEasyoakland-5/+8
2023-07-12avoid ambiguous wordTshepang Mbambo-1/+1
See https://github.com/rust-lang/rust/pull/113618#pullrequestreview-1526295432
2023-07-12update ancient noteTshepang Mbambo-2/+2
2023-06-29make HashMap::or_insert_with example more simpleTshepang Mbambo-4/+4
2023-06-15Auto merge of #104455 - the8472:dont-drain-on-drop, r=Amanieubors-73/+76
Don't drain-on-drop in DrainFilter impls of various collections. This removes drain-on-drop behavior from various unstable DrainFilter impls (not yet for HashSet/Map) because that behavior [is problematic](https://github.com/rust-lang/rust/issues/43244#issuecomment-641638196) (because it can lead to panic-in-drop when user closures panic) and may become forbidden if [this draft RFC passes](https://github.com/rust-lang/rfcs/pull/3288). closes #101122 [ACP](https://github.com/rust-lang/libs-team/issues/136) affected tracking issues * #43244 * #70530 * #59618 Related hashbrown update: https://github.com/rust-lang/hashbrown/pull/374
2023-06-14Rollup merge of #107619 - stepancheg:hash-set-insert, r=AmanieuMatthias Krüger-1/+23
Specify behavior of HashSet::insert `HashSet::insert` does not replace the value with equal value. Fixes #107581.
2023-06-14update hashbrown and replace Hash{Set,Map}::DrainFilter with ExtractIfThe 8472-73/+76
2023-04-16rm const traits in libcoreDeadbeef-4/+2
2023-04-14Rollup merge of #110244 - kadiwa4:unnecessary_imports, r=JohnTitorMatthias Krüger-4/+0
Remove some unneeded imports / qualified paths Continuation of #105537.
2023-04-14Rollup merge of #110047 - skaunov:patch-1, r=ChrisDentonYuki Okushi-2/+5
Add link to `collections` docs to `extend` trait I believe it would be useful here.
2023-04-14Add links to docs to `Iterator`Sergey Kaunov-2/+5
and couple of its methods
2023-04-12remove some unneeded importsKaDiWa-4/+0
2023-04-08std: Mark two reexports that should be inlined as `doc(inline)`Vadim Petrochenkov-0/+2
2023-03-29Use with_capacity_and_hasher instead of using basetosti007-1/+1
2023-03-20Remove outdated commentsMaybe Waffle-7/+0
2023-02-05Fix typo in HashMap::with_capacityKiran Shila-1/+1
2023-02-03Specify behavior of HashSet::insertStiopa Koltsov-1/+23
`HashSet::insert` does not replace the value with equal value. Fixes #107581.
2023-01-08Auto merge of #104658 - thomcc:rand-update-and-usable-no_std, r=Mark-Simulacrumbors-4/+5
Update `rand` in the stdlib tests, and remove the `getrandom` feature from it. The main goal is actually removing `getrandom`, so that eventually we can allow running the stdlib test suite on tier3 targets which don't have `getrandom` support. Currently those targets can only run the subset of stdlib tests that exist in uitests, and (generally speaking), we prefer not to test libstd functionality in uitests, which came up recently in https://github.com/rust-lang/rust/pull/104095 and https://github.com/rust-lang/rust/pull/104185. Additionally, the fact that we can't update `rand`/`getrandom` means we're stuck with the old set of tier3 targets, so can't test new ones. ~~Anyway, I haven't checked that this actually does allow use on tier3 targets (I think it does not, as some work is needed in stdlib submodules) but it moves us slightly closer to this, and seems to allow at least finally updating our `rand` dep, which definitely improves the status quo.~~ Checked and works now. For the most part, our tests and benchmarks are fine using hard-coded seeds. A couple tests seem to fail with this (stuff manipulating the environment expecting no collisions, for example), or become pointless (all inputs to a function become equivalent). In these cases I've done a (gross) dance (ab)using `RandomState` and `Location::caller()` for some extra "entropy". Trying to share that code seems *way* more painful than it's worth given that the duplication is a 7-line function, even if the lines are quite gross. (Keeping in mind that sharing it would require adding `rand` as a non-dev dep to std, and exposing a type from it publicly, all of which sounds truly awful, even if done behind a perma-unstable feature). See also some previous attempts: - https://github.com/rust-lang/rust/pull/86963 (in particular https://github.com/rust-lang/rust/pull/86963#issuecomment-885438936 which explains why this is non-trivial) - https://github.com/rust-lang/rust/pull/89131 - https://github.com/rust-lang/rust/pull/96626#issuecomment-1114562857 (I tried in that PR at the same time, but settled for just removing the usage of `thread_rng()` from the benchmarks, since that was the main goal). - https://github.com/rust-lang/rust/pull/104185 - Probably more. It's very tempting of a thing to "just update". r? `@Mark-Simulacrum`
2023-01-07docs: make `HashSet::retain` doctest more clearEzra Shaw-1/+1
2023-01-04Update rand in the stdlib tests, and remove the getrandom feature from itThom Chiovoloni-4/+5
2022-11-06Added `const_hash` tracking issue idonestacked-3/+3
2022-11-06Made `Sip` const `Hasher`onestacked-3/+6
2022-10-29fix typo in hashmap and hashset try_reserve methodjoseLuís-2/+2
2022-10-02Make Hash{Set,Map}::with_hasher unstably constNixon Enraght-Moony-2/+16
2022-09-26remove cfg(bootstrap)Pietro Albini-2/+0
2022-09-02Fix `std::collections::HashSet::drain` documentationWojciech Kordalski-1/+1
2022-08-22Move error trait into coreJane Losare-Lusby-0/+11
2022-08-18make many std tests work in MiriRalf Jung-10/+14
2022-06-23Rollup merge of #96173 - jmaargh:jmaargh/with-capacity-doc-fix, r=Dylan-DPCMichael Goulet-23/+37
Fix documentation for `with_capacity` and `reserve` families of methods Fixes #95614 Documentation for the following methods - `with_capacity` - `with_capacity_in` - `with_capacity_and_hasher` - `reserve` - `reserve_exact` - `try_reserve` - `try_reserve_exact` was inconsistent and often not entirely correct where they existed on the following types - `Vec` - `VecDeque` - `String` - `OsString` - `PathBuf` - `BinaryHeap` - `HashSet` - `HashMap` - `BufWriter` - `LineWriter` since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked `BufReader`, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well.
2022-06-20Fix typo in `HashMap::drain` docsnils-1/+1
It's a map, not a vector.
2022-06-19Fix documentation for with_capacity and reserve families of methodsjmaargh-23/+37
Documentation for the following methods with_capacity with_capacity_in with_capacity_and_hasher reserve reserve_exact try_reserve try_reserve_exact was inconsistent and often not entirely correct where they existed on the following types Vec VecDeque String OsString PathBuf BinaryHeap HashSet HashMap BufWriter LineWriter since the allocator is allowed to allocate more than the requested capacity in all such cases, and will frequently "allocate" much more in the case of zero-sized types (I also checked BufReader, but there the docs appear to be accurate as it appears to actually allocate the exact capacity). Some effort was made to make the documentation more consistent between types as well. Fix with_capacity* methods for Vec Fix *reserve* methods for Vec Fix docs for *reserve* methods of VecDeque Fix docs for String::with_capacity Fix docs for *reserve* methods of String Fix docs for OsString::with_capacity Fix docs for *reserve* methods on OsString Fix docs for with_capacity* methods on HashSet Fix docs for *reserve methods of HashSet Fix docs for with_capacity* methods of HashMap Fix docs for *reserve methods on HashMap Fix expect messages about OOM in doctests Fix docs for BinaryHeap::with_capacity Fix docs for *reserve* methods of BinaryHeap Fix typos Fix docs for with_capacity on BufWriter and LineWriter Fix consistent use of `hasher` between `HashMap` and `HashSet` Fix warning in doc test Add test for capacity of vec with ZST Fix doc test error
2022-06-15Add examples using `add_modify` to HashMapKarlWithK-2/+4
Updated the HashMap's documentation to include two references to add_modify. The first is when the `Entry` API is mentioned at the beginning. I was hesitant to change the "attack" example (although I believe that it is perfect example of where `add_modify` should be used) because both uses work equally, but one is more idiomatic (`add_modify`). The second is with the `entry` function that is used for the `Entry` API. The code example was a perfect use for `add_modify`, which is why it was changed to reflect that.
2022-06-13[perf] std: add missing `#[inline]` to `DefaultHasher::{new,default}`.Eduard-Mihai Burtescu-0/+2
2022-06-06Apply suggestions from code reviewnzrq-2/+3
Co-authored-by: David Tolnay <dtolnay@gmail.com>
2022-06-04Update library/std/src/collections/hash/set.rsnzrq-1/+1
Co-authored-by: David Tolnay <dtolnay@gmail.com>
2022-06-03Update set.rsnzrq-6/+4
2022-06-03Add note to documentation of HashSet::intersectionnzrq-0/+7
2022-06-01Rollup merge of #97611 - azdavis:master, r=Dylan-DPCYuki Okushi-2/+3
Tweak insert docs For `{Hash, BTree}Map::insert`, I always have to take a few extra seconds to think about the slight weirdness about the fact that if we "did not" insert (which "sounds" false), we return true, and if we "did" insert, (which "sounds" true), we return false. This tweaks the doc comments for the `insert` methods of those types (as well as what looks like a rustc internal data structure that I found just by searching the codebase for "If the set did") to first use the "Returns whether _something_" pattern used in e.g. `remove`, where we say that `remove` "returns whether the value was present".
2022-06-01Rollup merge of #94647 - Urgau:hash-map-many-mut, r=AmanieuYuki Okushi-0/+113
Expose `get_many_mut` and `get_many_unchecked_mut` to HashMap This pull-request expose the function [`get_many_mut`](https://docs.rs/hashbrown/0.12.0/hashbrown/struct.HashMap.html#method.get_many_mut) and [`get_many_unchecked_mut`](https://docs.rs/hashbrown/0.12.0/hashbrown/struct.HashMap.html#method.get_many_unchecked_mut) from `hashbrown` to the standard library `HashMap` type. They obviously keep the same API and are added under the (new) `map_many_mut` feature. - `get_many_mut`: Attempts to get mutable references to `N` values in the map at once. - `get_many_unchecked_mut`: Attempts to get mutable references to `N` values in the map at once, without validating that the values are unique.
2022-05-31Tweak insert docsAriel Davis-2/+3
2022-06-01Expose get_many_mut and get_many_unchecked_mut to HashMapLoïc BRANSTETT-0/+113
2022-05-23Put a bound on collection misbehaviorChristopher Durham-8/+10
As currently written, when a logic error occurs in a collection's trait parameters, this allows *completely arbitrary* misbehavior, so long as it does not cause undefined behavior in std. However, because the extent of misbehavior is not specified, it is allowed for *any* code in std to start misbehaving in arbitrary ways which are not formally UB; consider the theoretical example of a global which gets set on an observed logic error. Because the misbehavior is only bound by not resulting in UB from safe APIs and the crate-level encapsulation boundary of all of std, this makes writing user unsafe code that utilizes std theoretically impossible, as it now relies on undocumented QOI that unrelated parts of std cannot be caused to misbehave by a misuse of std::collections APIs. In practice, this is a nonconcern, because std has reasonable QOI and an implementation that takes advantage of this freedom is essentially a malicious implementation and only compliant by the most langauage-lawyer reading of the documentation. To close this hole, we just add a small clause to the existing logic error paragraph that ensures that any misbehavior is limited to the collection which observed the logic error, making it more plausible to prove the soundness of user unsafe code. This is not meant to be formal; a formal refinement would likely need to mention that values derived from the collection can also misbehave after a logic error is observed, as well as define what it means to "observe" a logic error in the first place. This fix errs on the side of informality in order to close the hole without complicating a normal reading which can assume a reasonable nonmalicious QOI. See also [discussion on IRLO][1]. [1]: https://internals.rust-lang.org/t/using-std-collections-and-unsafe-anything-can-happen/16640
2022-05-20Add complexity estimation of iterating over HashSet and HashMapAngelicosPhosphoros-0/+50
It is not obvious (at least for me) that complexity of iteration over hash tables depends on capacity and not length. Especially comparing with other containers like Vec or String. I think, this behaviour is worth mentioning. I run benchmark which tests iteration time for maps with length 50 and different capacities and get this results: ``` capacity - time 64 - 203.87 ns 256 - 351.78 ns 1024 - 607.87 ns 4096 - 965.82 ns 16384 - 3.1188 us ``` If you want to dig why it behaves such way, you can look current implementation in [hashbrown code](https://github.com/rust-lang/hashbrown/blob/f3a9f211d06f78c5beb81ac22ea08fdc269e068f/src/raw/mod.rs#L1933). Benchmarks code would be presented in PR related to this commit.
2022-05-09Use Rust 2021 prelude in std itself.Mara Bos-2/+2
2022-05-09Auto merge of #95960 - jhpratt:remove-rustc_deprecated, r=compiler-errorsbors-1/+1
Remove `#[rustc_deprecated]` This removes `#[rustc_deprecated]` and introduces diagnostics to help users to the right direction (that being `#[deprecated]`). All uses of `#[rustc_deprecated]` have been converted. CI is expected to fail initially; this requires #95958, which includes converting `stdarch`. I plan on following up in a short while (maybe a bootstrap cycle?) removing the diagnostics, as they're only intended to be short-term.
2022-05-06Add a dedicated length-prefixing method to `Hasher`Scott McMurray-0/+8
This accomplishes two main goals: - Make it clear who is responsible for prefix-freedom, including how they should do it - Make it feasible for a `Hasher` that *doesn't* care about Hash-DoS resistance to get better performance by not hashing lengths This does not change rustc-hash, since that's in an external crate, but that could potentially use it in future.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-01-14 08:55:23 +0000