about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2021-01-26Auto merge of #81217 - ssomers:btree_bring_back_the_slice, r=Mark-Simulacrumbors-43/+23
BTreeMap: bring back the key slice for immutable lookup Pave the way for binary search, by reverting a bit of #73971, which banned `keys` for misbehaving while it was defined for every `BorrowType`. Adding some `debug_assert`s along the way. r? `@Mark-Simulacrum`
2021-01-24BTreeMap: lightly refactor the split_off implementationStein Somers-42/+67
2021-01-23Rollup merge of #81170 - xfix:vecdeque-bug-fix, r=sfacklerJonas Schievink-3/+47
Avoid hash_slice in VecDeque's Hash implementation Fixes #80303.
2021-01-20BTreeMap: bring back the key slice for immutable lookupStein Somers-43/+23
2021-01-19BTreeMap: compile-test all borrowing interfaces and test more chaotic orderStein Somers-1/+87
2021-01-19Rollup merge of #81115 - ssomers:btree_drainy_refactor_4, r=Mark-SimulacrumGuillaume Gomez-121/+8
BTreeMap: prefer bulk_steal functions over specialized ones The `steal_` functions (apart from their return value) are basically specializations of the more general `bulk_steal_` functions. This PR removes the specializations. The library/alloc benchmarks say this is never slower and up to 6% faster. r? ``@Mark-Simulacrum``
2021-01-18Fix soundness issue for `replace_range` and `range`dylni-3/+10
2021-01-18Avoid hash_slice in VecDeque's Hash implementationKonrad Borowski-3/+47
Fixes #80303.
2021-01-18BTreeMap: prefer bulk_steal functions over specialized onesStein Somers-121/+8
2021-01-18BTreeMap: convert search functions to methodsStein Somers-83/+83
2021-01-18Auto merge of #81090 - ssomers:btree_drainy_refactor_2, r=Mark-Simulacrumbors-34/+60
BTreeMap: offer merge in variants with more clarity r? `@Mark-Simulacrum`
2021-01-17Rollup merge of #81082 - ssomers:btree_cleanup_comments, r=Mark-SimulacrumMara Bos-6/+8
BTreeMap: clean up a few more comments And mark `pop` as unsafe. r? ```@Mark-Simulacrum```
2021-01-17Auto merge of #81083 - ssomers:btree_drainy_refactor_1, r=Mark-Simulacrumbors-13/+14
BTreeMap: expose new_internal function and sanitize from_new_internal `new_internal` is the functional core of the imperative `push_internal_level`, and `from_new_internal` can easily do a proper job instead of returning a half-baked node. r? `@Mark-Simulacrum`
2021-01-16BTreeMap: offer merge in variants with more clarityStein Somers-34/+60
2021-01-16Rollup merge of #80681 - ChrisJefferson:logic-error-doc, r=m-ou-seMara Bos-1/+10
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
2021-01-16BTreeMap: expose new_internal function and sanitize from_new_internalStein Somers-13/+14
2021-01-16BTreeMap: clean up a few more commentsStein Somers-6/+8
2021-01-16Auto merge of #77435 - hanmertens:binary_heap_append, r=scottmcmbors-2/+8
Always use extend in BinaryHeap::append This is faster, see #77433. Fixes #77433
2021-01-16Clarify what the effects of a 'logic error' areChris Jefferson-1/+10
2021-01-16Auto merge of #80873 - ssomers:btree_cleanup_slices_4, r=Mark-Simulacrumbors-81/+88
BTreeMap: tougher checks on code using raw into_kv_pointers r? `@Mark-Simulacrum`
2021-01-15Change rebuild heuristic in BinaryHeap::appendHan Mertens-2/+8
See #77433 for why the new heuristic was chosen. Fixes #77433
2021-01-15Rollup merge of #80834 - bugadani:vecdeque, r=oli-obkYuki Okushi-5/+4
Remove unreachable panics from VecDeque::{front/back}[_mut] `VecDeque`'s `front`, `front_mut`, `back` and `back_mut` methods are implemented in terms of the index operator, which causes these functions to contain [unreachable panic calls](https://rust.godbolt.org/z/MTnq1o). This PR reimplements these methods in terms of `get[_mut]` instead.
2021-01-14Remove unreachable panics from VecDequeDániel Buga-5/+4
2021-01-11Add another test case for #79808Yuki Okushi-0/+15
Taken from #80293.
2021-01-10BTreeMap: tougher checks on code using raw into_kv_pointersStein Somers-81/+88
2021-01-08BTreeMap: tougher checks on most uses of copy_nonoverlappingStein Somers-26/+32
2020-12-28Rollup merge of #80448 - m-ou-se:deque-range-version, r=m-ou-seMara Bos-2/+2
Fix stabilization version of deque_range feature. See https://github.com/rust-lang/rust/pull/79022#issuecomment-751315315
2020-12-28Rollup merge of #80430 - xfix:add-length-as-doc-alias, r=steveklabnikMara Bos-0/+5
Add "length" as doc alias to len methods Currently when searching for `length` there are no results: https://doc.rust-lang.org/std/?search=length. This makes `len` methods appear when searching for `length`.
2020-12-28Rollup merge of #80390 - ssomers:btree_cleanup_slices_2, r=Mark-SimulacrumMara Bos-50/+48
BTreeMap: rename the area access methods r? `@Mark-Simulacrum`
2020-12-28Fix stabilization version of deque_range feature.Mara Bos-2/+2
2020-12-28Rollup merge of #80353 - ssomers:btree_test_split_off, r=Mark-SimulacrumDylan DPC-7/+38
BTreeMap: test split_off (and append) more thoroughly Using DeterministicRng as a poor man's property based testing rig. r? ``@Mark-Simulacrum``
2020-12-28Add "length" as doc alias to len methodsKonrad Borowski-0/+5
2020-12-26BTreeMap: rename the area access methodsStein Somers-50/+48
2020-12-26Auto merge of #79520 - ssomers:btree_cleanup_1, r=Mark-Simulacrumbors-64/+17
BTreeMap: clean up access to MaybeUninit arrays Stop exposing and using immutable access to `MaybeUninit` slices when we need and have exclusive access to the tree. r? `@Mark-Simulacrum`
2020-12-26Auto merge of #80354 - ssomers:btree_test_compact, r=Mark-Simulacrumbors-9/+33
BTreeMap: test full nodes a little more r? `@Mark-Simulacrum`
2020-12-26Auto merge of #79022 - SpyrosRoum:stabilize-deque_range, r=m-ou-sebors-6/+2
stabilize deque_range Make #74217 stable, stabilizing `VecDeque::range` and `VecDeque::range_mut`. Pr: #74099 r? `@m-ou-se`
2020-12-25BTreeMap: declare exclusive access to arrays when copying from themStein Somers-64/+17
2020-12-25Rollup merge of #80352 - ssomers:btree_test_diagnostics, r=Mark-SimulacrumDylan DPC-5/+9
BTreeMap: make test cases more explicit on failure r? `@Mark-Simulacrum`
2020-12-24BTreeMap: test full nodes a little moreStein Somers-9/+33
2020-12-24BTreeMap: test split_off (and append) more thoroughlyStein Somers-7/+38
2020-12-24BTreeMap: make test cases more explicit on failureStein Somers-5/+9
2020-12-24BTreeMap: avoid implicit use of node length in flightStein Somers-97/+81
2020-12-23Auto merge of #79521 - ssomers:btree_cleanup_2, r=Mark-Simulacrumbors-106/+108
BTreeMap: relax the explicit borrow rule to make code shorter and safer Expressions like `.reborrow_mut().into_len_mut()` are annoyingly long, and kind of dangerous for the reason `reborrow_mut()` is unsafe. By relaxing the single rule, we no longer have to make an exception for functions with a `borrow` name and functions like `as_leaf_mut`. This is largely restoring the declaration style of the btree::node API about a year ago, but with more explanation and consistency. r? `@Mark-Simulacrum`
2020-12-19Rollup merge of #78083 - ChaiTRex:master, r=m-ou-seYuki Okushi-5/+7
Stabilize or_insert_with_key Stabilizes the `or_insert_with_key` feature from https://github.com/rust-lang/rust/issues/71024. This allows inserting key-derived values when a `HashMap`/`BTreeMap` entry is vacant. The difference between this and `.or_insert_with(|| ... )` is that this provides a reference to the key to the closure after it is moved with `.entry(key_being_moved)`, avoiding the need to copy or clone the key.
2020-12-18Rollup merge of #80003 - Stupremee:fix-zst-vecdeque-conversion-panic, r=dtolnayDylan DPC-2/+6
Fix overflow when converting ZST Vec to VecDeque ```rust let v = vec![(); 100]; let queue = VecDeque::from(v); println!("{:?}", queue); ``` This code will currently panic with a capacity overflow. This PR resolves this issue and makes the code run fine. Resolves #78532
2020-12-17BTreeMap: relax the explicit borrow rule to make code shorter and saferStein Somers-106/+108
2020-12-17Rollup merge of #80022 - ssomers:btree_cleanup_8, r=Mark-SimulacrumGuillaume Gomez-2/+2
BTreeSet: simplify implementation of pop_first/pop_last …and stop it interfering in #79245. r? ```````@Mark-Simulacrum```````
2020-12-17Rollup merge of #80006 - ssomers:btree_cleanup_6, r=Mark-SimulacrumGuillaume Gomez-28/+27
BTreeMap: more expressive local variables in merge r? ```````@Mark-Simulacrum```````
2020-12-14BTreeSet: simplify implementation of pop_first/pop_lastStein Somers-2/+2
2020-12-13Auto merge of #80005 - ssomers:btree_cleanup_3, r=Mark-Simulacrumbors-10/+11
BTreeMap: declare clear_parent_link directly on the root it needs r? `@Mark-Simulacrum`
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 01:55:17 +0000