summary refs log tree commit diff
path: root/src/liballoc/collections/btree/set.rs
AgeCommit message (Collapse)AuthorLines
2019-10-23proposal for access to BTreeMap/BTreeSet first/last, #62924Stein Somers-11/+99
2019-10-18BTreeSet symmetric_difference & union optimized, cleanedStein Somers-120/+119
2019-10-01BTreeSet intersection, difference & is_subnet optimizationsStein Somers-75/+155
2019-09-16Improve BTreeSet::Intersection::size_hintpcpthm-22/+22
The commented invariant that an iterator is smaller than other iterator was violated after next is called and two iterators are consumed at different rates.
2019-07-02When possible without changing semantics, implement Iterator::last in terms ↵Kyle Huey-0/+7
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-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-2/+2
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-03-29improve worst-case performance of BTreeSet difference and intersectionStein Somers-65/+233
2019-02-20Rollup merge of #58553 - scottmcm:more-ihle, r=Centrilkennytm-12/+12
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-12/+12
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-10libs: doc commentsAlexander Regueiro-2/+2
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-10/+6
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-8/+8
2019-02-02liballoc: elide some lifetimes.Mazdak Farrokhzad-16/+16
2019-02-02liballoc: prefer imports of borrow from libcore.Mazdak Farrokhzad-4/+2
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-9/+14
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-6/+6
2018-06-29Move some alloc crate top-level items to a new alloc::collections moduleSimon Sapin-0/+1153
This matches std::collections
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-09 20:19:55 +0000