In `BTreeMap::eq`, do not compare the elements if the sizes are different.
Reverts rust-lang/rust#147101 in library/alloc/src/btree/
rust-lang/rust#147101 replaced some instances of code like `a.len() == b.len() && a.iter().eq(&b)` with just `a.iter().eq(&b)`, but the optimization that PR introduced only applies for `TrustedLen` iterators, and `BTreeMap`'s itertors are not `TrustedLen`, so this theoretically regressed perf for comparing large `BTreeMap`/`BTreeSet`s with unequal lengths but equal prefixes, (and also made it so that comparing two different-length `BTreeMap`/`BTreeSet`s with elements whose `PartialEq` impls that can panic now can panic, though this is not a "promised" behaviour either way (cc rust-lang/rust#149122))
Given that `TrustedLen` is an unsafe trait, I opted to not implement it for `BTreeMap`'s iterators, and instead just revert the change. If someone else wants to audit `BTreeMap`'s iterators to make sure they always return the right number of items (even in the face of incorrect user `Ord` impls) and then implement `TrustedLen` for them so that the optimization works for them, then this can be closed in favor of that (or if the perf regression is deemed too theoretical, this can be closed outright).
Example of theoretical perf regression: https://play.rust-lang.org/?version=beta&mode=release&edition=2024&gist=a37e3d61e6bf02669b251315c9a44fe2 (very rough estimates, using `Instant::elapsed`).
In release mode on stable the comparison takes ~23.68µs.
In release mode on beta/nightly the comparison takes ~48.351057ms.
BTreeMap: Don't leak allocators when initializing nodes
Memory was allocated via `Box::leak` and thence intended to be tracked and deallocated manually, but the allocator was also leaked, not tracked, and never dropped. Now it is dropped immediately.
According to my reading of the `Allocator` trait, if a copy of the allocator remains live, then its allocations must remain live. Since the B-tree has a copy of the allocator that will only be dropped after the nodes, it's safe to not store the allocator in each node (which would be a much more intrusive change).
Fixes: rust-lang/rust#106203
Memory was allocated via `Box::leak` and thence intended to be tracked
and deallocated manually, but the allocator was also leaked, not
tracked, and never dropped. Now it is dropped immediately.
According to my reading of the `Allocator` trait, if a copy of the
allocator remains live, then its allocations must remain live. Since
the B-tree has a copy of the allocator that will only be dropped after
the nodes, it's safe to not store the allocator in each node (which
would be a much more intrusive change).
Stabilize `btree_entry_insert` feature
This stabilises `btree_map::VacantEntry::insert_entry` and `btree_map::Entry::insert_entry`, following the FCP in [tracking issue](https://github.com/rust-lang/rust/issues/65225).
New stable API:
```rust
impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> {
pub fn insert_entry(self, value: V) -> OccupiedEntry<'a, K, V, A>;
}
impl<'a, K: Ord, V, A: Allocator + Clone> VacantEntry<'a, K, V, A> {
pub fn insert_entry(mut self, value: V) -> OccupiedEntry<'a, K, V, A>;
}
```
(FCP ended almost a year ago, so if it's needed for process we could rerun it)
Closes: https://github.com/rust-lang/rust/issues/65225
The method `BTreeSet::from_sorted_iter` was introduced in 49ccb7519f,
but it was not consistently used throughout the codebase. As a result, some code redundantly reimplemented its logic.
This commit fixes the problem.
This also seems like a small mistake: the first main sentence is put in
the same paragraph as the other two following ones while other
equivalents all have it split. Therefore, do the same here.
Signed-off-by: Paul Mabileau <paul.mabileau@harfanglab.fr>
I found these by grepping for `&[a-z_\.]*\.clone()`, i.e. expressions
like `&a.b.clone()`, which are sometimes unnecessary clones, and also
looking at clones nearby to cases like that.
Use `std::mem::{size_of, size_of_val, align_of, align_of_val}` from the
prelude instead of importing or qualifying them.
These functions were added to all preludes in Rust 1.80.
Some miscellaneous edition-related library tweaks
Some library edition tweaks that can be done separately from upgrading the whole standard library to edition 2024 (which is blocked on getting the submodules upgraded, for example)
