Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for HashMap::extract_if and HashSet::extract_if #59618

Open
DutchGhost opened this issue Apr 1, 2019 · 16 comments
Open

Tracking issue for HashMap::extract_if and HashSet::extract_if #59618

DutchGhost opened this issue Apr 1, 2019 · 16 comments
Labels
A-collections Area: `std::collection` C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@DutchGhost
Copy link
Contributor

DutchGhost commented Apr 1, 2019

The feature gate for the issue is #![feature(hash_extract_if)] (previously hash_drain_filter)

Currently only Vec and LinkedList have a drain_filter method, while other collections such as HashMap and HashSet do not.

This means that currently, removing items from a collection, and getting ownership of those items is fairly...unidiomatic and cumbersome.

For references, see rust-lang/rfcs#2140

Implementation History

@jonas-schievink jonas-schievink added T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. C-feature-request Category: A feature request, i.e: not implemented / a PR. A-collections Area: `std::collection` labels Apr 1, 2019
@hellow554
Copy link
Contributor

Related #42849

@mbrubeck
Copy link
Contributor

mbrubeck commented Jul 9, 2020

This may be easy to implement since drain_filter was added to the underlying hashbrown types in rust-lang/hashbrown#135 and rust-lang/hashbrown#179. (Requires hashbrown 0.8.1 or later; see #70052.)

@mbrubeck mbrubeck changed the title Add drain_filter to HashMap, HashSet, and other collections Add drain_filter to HashMap and HashSet Aug 11, 2020
@mbrubeck
Copy link
Contributor

mbrubeck commented Aug 11, 2020

I have implemented this on a branch, but it will need to wait for a new release of the hashbrown crate because it depends on rust-lang/hashbrown#185, rust-lang/hashbrown#187, and rust-lang/hashbrown#188:

master...mbrubeck:hash_drain_filter

mbrubeck added a commit to mbrubeck/rust that referenced this issue Sep 9, 2020
tmandry added a commit to tmandry/rust that referenced this issue Sep 10, 2020
Add drain_filter method to HashMap and HashSet

Add `HashMap::drain_filter` and `HashSet::drain_filter`, implementing part of rust-lang/rfcs#2140.  These new methods are unstable.  The tracking issue is rust-lang#59618.

The added iterators behave the same as `BTreeMap::drain_filter` and `BTreeSet::drain_filter`, except their iteration order is arbitrary.  The unit tests are adapted from `alloc::collections::btree`.

This branch rewrites `HashSet` to be a wrapper around `hashbrown::HashSet` rather than `std::collections::HashMap`.
 (Both are themselves wrappers around `hashbrown::HashMap`, so the in-memory representation is the same either way.)  This lets `std` re-use more iterator code from `hashbrown`.  Without this change, we would need to duplicate much more code to implement `HashSet::drain_filter`.

This branch also updates the `hashbrown` crate to version 0.9.0.  Aside from changes related to the `DrainFilter` iterators, this version only changes features that are not used in libstd or rustc.  And it updates `indexmap` to version 1.6.0, whose only change is compatibility with `hashbrown` 0.9.0.
@mbrubeck mbrubeck changed the title Add drain_filter to HashMap and HashSet Tracking issue for HashMap::drain_filter and HashSet::drain_filter (hash_drain_filter) Sep 10, 2020
@mbrubeck
Copy link
Contributor

This is now implemented in nightly behind the unstable hash_drain_filter feature:

@benesch
Copy link
Contributor

benesch commented Dec 29, 2020

Any reason not to stabilize this @mbrubeck?

@mbrubeck
Copy link
Contributor

There are some open questions about naming and API design; see the summary in #43244 (comment) for some details.

@OfekShochat
Copy link

OfekShochat commented Apr 7, 2022

when do you estimate for this be stable? this is an amazing feature

@the8472
Copy link
Member

the8472 commented Jan 15, 2023

Hashbrown PR to remove the drain-on-drop behavior: rust-lang/hashbrown#374

@JakobDegen
Copy link
Contributor

I'd like to suggest an alternative API that is significantly more powerful than this one: entries(&mut self) -> impl Iterator<Item = OccupiedEntryRef>. The API can quite obviously be used to replace drain_filter:

for entry in map.entries() {
    if entry.get().satisfies_condition() {
        entry.remove();
    }
}

However, it is much more powerful and ergonomic for any non-trivial use cases. As far as I can tell these advantages fall into a few categories:

  1. Not forcing the use of a closure. Closures are great, but they're not always the most ergonomic thing in the world. Specifically, using a closure interferes with the ability to use the standard effects (try, async) which is a bit of a loss for more complicated conditions.
  2. drain_filter() can be very approximately seen as acting like .entries().filter() - essentially this means that it's going to have a tough time supporting any use of .entries() that doesn't look quite like that.
  3. VacantEntryRefs are useful. With the .drain_filter() as implemented above, I could still get out a VacantEntryRef, which I could stash somewhere and then use again later if I change my mind about wanting to remove that element.

The obvious problem with this API is that OccupiedEntryRef is not a type that exists in std. That type would have to be added before (or together with) this API. It is my understanding that std is interested in an alternative API to fix the weaknesses of the Entry API we have now anyway, so possibly this could be wrapped up in there?

A second, less obvious problem with this API is that it significantly restricts the space of possible implementations for the std HashMap. Allowing multiple entries into the map to coexist is a non-trivial requirement.

@blagowtf
Copy link

any update here? this API is essential for my use case where having ownership of the removed elements would save me from unnecessary clones / allocations...

@the8472
Copy link
Member

the8472 commented May 30, 2023

Currently waiting for a hashbrown release so that drain_filter can be replaced with extract_if.

@blagowtf
Copy link

@the8472 Nice. How often are these releases (and do they automatically land in std?) Is the vision ultimately to stabilize the extract_if version in std::collections::HashMap.

@Folyd
Copy link
Contributor

Folyd commented Jun 4, 2023

The new version of hashbrown will be released soon. 🎉
rust-lang/hashbrown#434

bors added a commit to rust-lang-ci/rust that referenced this issue Jun 15, 2023
Don't drain-on-drop in DrainFilter impls of various collections.

This removes drain-on-drop behavior from various unstable DrainFilter impls (not yet for HashSet/Map) because that behavior [is problematic](rust-lang#43244 (comment)) (because it can lead to panic-in-drop when user closures panic) and may become forbidden if [this draft RFC passes](rust-lang/rfcs#3288).

closes rust-lang#101122

[ACP](rust-lang/libs-team#136)

affected tracking issues
* rust-lang#43244
* rust-lang#70530
* rust-lang#59618

Related hashbrown update: rust-lang/hashbrown#374
@Nemo157 Nemo157 changed the title Tracking issue for HashMap::drain_filter and HashSet::drain_filter (hash_drain_filter) Tracking issue for HashMap::extract_if and HashSet::extract_if Jun 16, 2023
@saiintbrisson
Copy link
Contributor

saiintbrisson commented Sep 14, 2023

Is this ready for the FCP? hashbrown released Jun 5.

@the8472
Copy link
Member

the8472 commented Sep 14, 2023

On the companion Vec issue some people are asking for a mapped version (passing an owned value) instead so if we implemented that it might make sense to do that for hashmap too.

But that could be discussed as part of the FCP.

@Dylan-DPC Dylan-DPC added C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. and removed C-feature-request Category: A feature request, i.e: not implemented / a PR. labels Dec 4, 2023
@esemeniuc
Copy link

Would love to use this feature in stable!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: `std::collection` C-tracking-issue Category: A tracking issue for an RFC or an unstable feature. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests