about summary refs log tree commit diff
path: root/src/liballoc/collections/binary_heap.rs
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-1431/+0
2020-07-19Use italics for O notationpierwill-13/+13
Co-authored-by: Guillaume Gomez <guillaume1.gomez@gmail.com>
2020-06-19`#[deny(unsafe_op_in_unsafe_fn)]` in liballocLeSeulArtichaut-5/+7
2020-05-29Add Extend::{extend_one,extend_reserve}Josh Stone-0/+20
This adds new optional methods on `Extend`: `extend_one` add a single element to the collection, and `extend_reserve` pre-allocates space for the predicted number of incoming elements. These are used in `Iterator` for `partition` and `unzip` as they shuffle elements one-at-a-time into their respective collections.
2020-04-26fix more clippy warningsMatthias Krüger-1/+1
clippy::{redundant_pattern_matching, clone_on_copy, iter_cloned_collect, option_as_ref_deref, match_ref_pats}
2020-04-24Add BinaryHeap::retain as suggested in #42849arlo-0/+28
2020-04-15don't specify log base in big-ORalf Jung-2/+2
2020-04-15big-O notation: parenthesis, multiplication and backticksRalf Jung-14/+13
2020-04-05Stop importing integer modules in liballocLinus Färnstrand-1/+0
2020-02-29simplify boolean expressionsMatthias Krüger-2/+2
2020-01-19Fix `binary_heap::DrainSorted` drop leak on panicsJonas Schievink-2/+14
2019-12-26Remove redundant link textsMatthew Kraai-1/+1
2019-12-22Format the worldMark Rousskov-33/+12
2019-10-25fix doctestHideki Sekine-10/+4
2019-10-25Simplify .drain_sorted() and its doc.Hideki Sekine-45/+40
2019-10-25Add .into_iter_sorted() and .drain_sorted()Hideki Sekine-1/+140
* `.drain_sorted()` doc change suggested by @KodrAus
2019-08-12Apply suggestions from code reviewObserver42-2/+2
Co-Authored-By: Mazdak Farrokhzad <twingoow@gmail.com>
2019-08-12Document From trait for BinaryHeapObserver42-0/+3
2019-07-02When possible without changing semantics, implement Iterator::last in terms ↵Kyle Huey-0/+5
of DoubleEndedIterator::next_back for types in liballoc and libcore. Provided that the iterator has finite length and does not trigger user-provided code, this is safe. What follows is a full list of the DoubleEndedIterators in liballoc/libcore and whether this optimization is safe, and if not, why not. src/liballoc/boxed.rs Box: Pass through to avoid defeating optimization of the underlying DoubleIterator implementation. This has no correctness impact. src/liballoc/collections/binary_heap.rs Iter: Pass through to avoid defeating optimizations on slice::Iter IntoIter: Not safe, changes Drop order Drain: Not safe, changes Drop order src/liballoc/collections/btree/map.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order Keys: Safe to call next_back, invokes no user defined code. Values: ditto ValuesMut: ditto Range: ditto RangeMut: ditto src/liballoc/collections/btree/set.rs Iter: Safe to call next_back, invokes no user defined code. IntoIter: Not safe, changes Drop order Range: Safe to call next_back, invokes no user defined code. src/liballoc/collections/linked_list.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order src/liballoc/collections/vec_deque.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order Drain: ditto src/liballoc/string.rs Drain: Safe because return type is a primitive (char) src/liballoc/vec.rs IntoIter: Not safe, changes Drop order Drain: ditto Splice: ditto src/libcore/ascii.rs EscapeDefault: Safe because return type is a primitive (u8) src/libcore/iter/adapters/chain.rs Chain: Not safe, invokes user defined code (Iterator impl) src/libcore/iter/adapters/flatten.rs FlatMap: Not safe, invokes user defined code (Iterator impl) Flatten: ditto FlattenCompat: ditto src/libcore/iter/adapters/mod.rs Rev: Not safe, invokes user defined code (Iterator impl) Copied: ditto Cloned: Not safe, invokes user defined code (Iterator impl and T::clone) Map: Not safe, invokes user defined code (Iterator impl + closure) Filter: ditto FilterMap: ditto Enumerate: Not safe, invokes user defined code (Iterator impl) Skip: ditto Fuse: ditto Inspect: ditto src/libcore/iter/adapters/zip.rs Zip: Not safe, invokes user defined code (Iterator impl) src/libcore/iter/range.rs ops::Range: Not safe, changes Drop order, but ALREADY HAS SPECIALIZATION ops::RangeInclusive: ditto src/libcore/iter/sources.rs Repeat: Not safe, calling last should iloop. Empty: No point, iterator is at most one item long. Once: ditto OnceWith: ditto src/libcore/option.rs Item: No point, iterator is at most one item long. Iter: ditto IterMut: ditto IntoIter: ditto src/libcore/result.rs Iter: No point, iterator is at most one item long IterMut: ditto IntoIter: ditto src/libcore/slice/mod.rs Split: Not safe, invokes user defined closure SplitMut: ditto RSplit: ditto RSplitMut: ditto Windows: Safe, already has specialization Chunks: ditto ChunksMut: ditto ChunksExact: ditto ChunksExactMut: ditto RChunks: ditto RChunksMut: ditto RChunksExact: ditto RChunksExactMut: ditto src/libcore/str/mod.rs Chars: Safe, already has specialization CharIndices: ditto Bytes: ditto Lines: Safe to call next_back, invokes no user defined code. LinesAny: Deprecated Everything that is generic over P: Pattern: Not safe because Pattern invokes user defined code. SplitWhitespace: Safe to call next_back, invokes no user defined code. SplitAsciiWhitespace: ditto
2019-05-22Revert "Add implementations of last in terms of next_back on a bunch of ↵Steven Fackler-15/+0
DoubleEndedIterators." This reverts commit 3e86cf36b5114f201868bf459934fe346a76a2d4.
2019-05-18Document BinaryHeap time complexityDavid Tolnay-0/+43
I went into some detail on the time complexity of `push` because it is relevant for using BinaryHeap efficiently -- specifically that you should avoid pushing many elements in ascending order when possible.
2019-05-14Rollup merge of #60130 - khuey:efficient_last, r=sfacklerMazdak Farrokhzad-0/+15
Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators Provided a `DoubleEndedIterator` has finite length, `Iterator::last` is equivalent to `DoubleEndedIterator::next_back`. But searching forwards through the iterator when it's unnecessary is obviously not good for performance. I ran into this on one of the collection iterators. I tried adding appropriate overloads for a bunch of the iterator adapters like filter, map, etc, but I ran into a lot of type inference failures after doing so. The other interesting case is what to do with `Repeat`. Do we consider it part of the contract that `Iterator::last` will loop forever on it? The docs do say that the iterator will be evaluated until it returns None. This is also relevant for the adapters, it's trivially easy to observe whether a `Map` adapter invoked its closure a zillion times or just once for the last element.
2019-05-01BinaryHeap: add min-heap exampleAlexey Shmalko-0/+24
2019-04-19Add implementations of last in terms of next_back on a bunch of ↵Kyle Huey-0/+15
DoubleEndedIterators. r?Manishearth
2019-04-05Use for_each to extend collectionsJosh Stone-3/+1
This updates the `Extend` implementations to use `for_each` for many collections: `BinaryHeap`, `BTreeMap`, `BTreeSet`, `LinkedList`, `Path`, `TokenStream`, `VecDeque`, and `Wtf8Buf`. Folding with `for_each` enables better performance than a `for`-loop for some iterators, especially if they can just forward to internal iterators, like `Chain` and `FlatMap` do.
2019-02-25Rollup merge of #58421 - nox:relax-bounds-binary-heap, r=dtolnayMazdak Farrokhzad-244/+244
Relax some Ord bounds on BinaryHeap<T> Notably, iterators don't require any trait bounds to be iterated.
2019-02-20Rollup merge of #58553 - scottmcm:more-ihle, r=Centrilkennytm-2/+2
Use more impl header lifetime elision Inspired by seeing explicit lifetimes on these two: - https://doc.rust-lang.org/nightly/std/slice/struct.Iter.html#impl-FusedIterator - https://doc.rust-lang.org/nightly/std/primitive.u32.html#impl-Not And a follow-up to https://github.com/rust-lang/rust/pull/54687, that started using IHLE in libcore. Most of the changes in here fall into two big categories: - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop`, `Debug`, and `Clone`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations [where the flipped one cannot elide the lifetime](https://internals.rust-lang.org/t/impl-type-parameter-aliases/9403/2?u=scottmcm). I also removed two lifetimes that turned out to be completely unused; see https://github.com/rust-lang/rust/issues/41960#issuecomment-464557423
2019-02-17Use more impl header lifetime elisionScott McMurray-2/+2
There are two big categories of changes in here - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop` & `Debug`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations where the flipped one cannot elide the lifetime.
2019-02-13Relax some Ord bounds on BinaryHeap<T>Anthony Ramine-244/+244
Notably, iterators don't require any trait bounds to be iterated.
2019-02-10libs: doc commentsAlexander Regueiro-1/+1
2019-02-07Rollup merge of #58123 - lnicola:binary-heap-no-bounds-checks, r=sfacklerkennytm-3/+8
Avoid some bounds checks in binary_heap::{PeekMut,Hole} Fixes #58121.
2019-02-03Avoid some bounds checks in binary_heap::{PeekMut,Hole}Laurențiu Nicola-3/+8
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-12/+8
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-7/+7
2019-02-02liballoc: elide some lifetimes.Mazdak Farrokhzad-12/+12
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-8/+12
2019-02-02liballoc: cargo check passes on 2018Mazdak Farrokhzad-2/+2
2018-12-25Remove licensesMark Rousskov-10/+0
2018-12-07Various minor/cosmetic improvements to codeAlexander Regueiro-1/+1
2018-12-02Update issue number of `shrink_to` methods to point the tracking issueHidehito Yabuuchi-1/+1
2018-06-29Move some alloc crate top-level items to a new alloc::collections moduleSimon Sapin-0/+1196
This matches std::collections
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-01-16 06:11:31 +0000