about summary refs log tree commit diff
path: root/src/liballoc/collections/btree/set.rs
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-1574/+0
2020-07-18Use more intra-doc links in BTreeSetManish Goregaokar-3/+3
2020-07-17Use intra-doc links in BTreeSet docsManish Goregaokar-15/+7
2020-06-26Shortcuts for min/max on ordinary BTreeMap/BTreeSet iteratorsStein Somers-0/+35
2020-05-29Add Extend::{extend_one,extend_reserve}Josh Stone-0/+10
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-05-03Make BTreeMap::new and BTreeSet::new constLuca Gladiator-1/+2
2020-04-06Remove the Ord bound that was plaguing drain_filter, and superfluous lifetimesStein Somers-16/+9
2020-03-29BTreeMap/BTreeSet: implement and test drain_filterStein Somers-3/+98
2020-01-30Rollup merge of #66648 - crgl:btree-clone-from, r=AmanieuDylan DPC-1/+12
Implement clone_from for BTreeMap and BTreeSet See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns: 1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this. 2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable. ~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~
2019-12-26Remove redundant link textsMatthew Kraai-1/+1
2019-12-23Implement clone_from for BTree collectionsCharles Gleason-1/+12
2019-12-22Format the worldMark Rousskov-147/+100
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-02-25 04:26:55 +0000