| Age | Commit message (Collapse) | Author | Lines |
|---|
|
Add #[must_use] to alloc constructors
Added `#[must_use]`. to the various forms of `new`, `pin`, and `with_capacity` in the `alloc` crate. No extra explanations given as I couldn't think of anything useful to add.
I figure this deserves extra scrutiny compared to the other PRs I've done so far. In particular:
* The 4 `pin`/`pin_in` methods I touched. Are there legitimate use cases for pinning and not using the result? Pinning's a difficult concept I'm not very comfortable with.
* `Box`'s constructors. Do people ever create boxes just for the side effects... allocating or zeroing out memory?
Parent issue: #89692
r? ``@joshtriplett``
|
|
|
|
|
|
Consistent big O notation
This makes the big O time complexity notation in places with markdown support more consistent.
Inspired by #89210
|
|
|
|
|
|
|
|
same search
|
|
Stabilize Vec<T>::shrink_to
This PR stabilizes `shrink_to` feature and closes the corresponding issue. The second point was addressed already, and no `panic!` should occur.
Closes #56431.
|
|
|
|
Stabilize `impl From<[(K, V); N]> for HashMap` (and friends)
In addition to allowing HashMap to participate in Into/From conversion, this adds the long-requested ability to use constructor-like syntax for initializing a HashMap:
```rust
let map = HashMap::from([
(1, 2),
(3, 4),
(5, 6)
]);
```
This addition is highly motivated by existing precedence, e.g. it is already possible to similarly construct a Vec from a fixed-size array:
```rust
let vec = Vec::from([1, 2, 3]);
```
...and it is already possible to collect a Vec of tuples into a HashMap (and vice-versa):
```rust
let vec = Vec::from([(1, 2)]);
let map: HashMap<_, _> = vec.into_iter().collect();
let vec: Vec<(_, _)> = map.into_iter().collect();
```
...and of course it is likewise possible to collect a fixed-size array of tuples into a HashMap ([but not vice-versa just yet](https://github.com/rust-lang/rust/issues/81615)):
```rust
let arr = [(1, 2)];
let map: HashMap<_, _> = std::array::IntoIter::new(arr).collect();
```
Therefore this addition seems like a no-brainer.
As for any impl, this would be insta-stable.
|
|
|
|
|
|
|
|
|
|
|
|
It now doesn't fully rebuild the heap, but only the parts that are
necessary.
|
|
alloc: Added `as_slice` method to `BinaryHeap` collection
I initially asked about whether it is useful addition on https://internals.rust-lang.org/t/should-i-add-as-slice-method-to-binaryheap/13816, and it seems there were no objections, so went ahead with this PR.
> There is [`BinaryHeap::into_vec`](https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#method.into_vec), but it consumes the value. I wonder if there is API design limitation that should be taken into account. Implementation-wise, the inner buffer is just a Vec, so it is trivial to expose as_slice from it.
Please, guide me through if I need to add tests or something else.
UPD: Tracking issue #83659
|
|
|
|
|
|
Improve sift_down performance in BinaryHeap
Replacing `child < end - 1` with `child <= end.saturating_sub(2)` in `BinaryHeap::sift_down_range` (surprisingly) results in a significant speedup of `BinaryHeap::into_sorted_vec`. The same substitution can be done for `BinaryHeap::sift_down_to_bottom`, which causes a slight but probably statistically insignificant speedup for `BinaryHeap::pop`. It's interesting that benchmarks aside from `bench_into_sorted_vec` are barely affected, even those that do use `sift_down_*` methods internally.
| Benchmark | Before (ns/iter) | After (ns/iter) | Speedup |
|--------------------------|------------------|-----------------|---------|
| bench_find_smallest_1000<sup>1</sup> | 392,617 | 385,200 | 1.02 |
| bench_from_vec<sup>1</sup> | 506,016 | 504,444 | 1.00 |
| bench_into_sorted_vec<sup>1</sup> | 476,869 | 384,458 | 1.24 |
| bench_peek_mut_deref_mut<sup>3</sup> | 518,753 | 519,792 | 1.00 |
| bench_pop<sup>2</sup> | 446,718 | 444,409 | 1.01 |
| bench_push<sup>3</sup> | 772,481 | 770,208 | 1.00 |
<sup>1</sup>: internally calls `sift_down_range`
<sup>2</sup>: internally calls `sift_down_to_bottom`
<sup>3</sup>: should not be affected
|
|
|
|
Because child > 0, the two statements are equivalent, but using
saturating_sub and <= yields in faster code. This is most notable in the
binary_heap::bench_into_sorted_vec benchmark, which shows a speedup of
1.26x, which uses sift_down_range internally. The speedup of pop (that
uses sift_down_to_bottom internally) is much less significant as the
sifting method is not called in a loop.
|
|
|
|
|
|
|
|
|
|
Clarify what the effects of a 'logic error' are
This clarifies what a 'logic error' is (which is a term used to describe what happens if you put things in a hash table or btree and then use something like a refcell to break the internal ordering). This tries to be as vague as possible, as we don't really want to promise what happens, except "bad things, but not UB". This was discussed in #80657
|
|
|
|
See #77433 for why the new heuristic was chosen.
Fixes #77433
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Avoid useless sift_down when std::collections::binary_heap::PeekMut is never mutably dereferenced
If `deref_mut` is never called then it's not possible for the element to be mutated without internal mutability, meaning there's no need to call `sift_down`.
This could be a little improvement in cases where you want to mutate the biggest element of the heap only if it satisfies a certain predicate that needs only read access to the element.
|
|
r=jyn514
Move to intra-doc links in library/alloc/src/collections/binary_heap.rs
Helps with #75080.
@rustbot modify labels: T-doc, A-intra-doc-links
|
|
|
|
|
|
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
|
|
|
|
|
|
|
|
|
