rust-lang / rust-lang/hashbrown

Add a `take_any` method

Open
#382 9 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
3k
Forks
358
Avg merge
11h 57m
Merged PRs (30d)
2

Description

It is not the first time I'm missing a method to remove an arbitrary element from a set or map. This issue has been solved in the standard library for BTreeSet and BTreeMap with the recent introduction of the pop_first and pop_last methods, but there is no equivalent for HashMap/HashSet.

What I'm looking for is as simple as that:

/// Removes an arbitrary element from the set.
fn take_any(&mut self) -> Option

It is currently impossible to remove an element from a HashMap/HashSet through remove or take without a preexisting reference to an element/key of the set/map. So to have such reference the only way is to clone one beforehand:

fn take_any<T: Clone>(set: &mut HashSet<T>) -> Option<T> {
  let result = set.iter().next()?.clone();
  set.remove(&result);
  result
}

It is possible without the Clone bound with the drain_filter that allows to drain the first item and keep the rest, but it seems expansive to me.

fn take_any<T>(set: &mut HashSet<T>) -> Option<T> {
  let mut taken = false;
  set.drain_filter(|_| {
    let take = !taken;
    taken = true;
    take
  }).next()
}

As for the name, it could also be named pop_any to reflect the pop_first and pop_last methods on BTreeSet and BTreeMap.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Review the HashMap and HashSet APIs alongside BTreeSet and BTreeMap's pop_first and pop_last methods, and compare the proposed drain_filter approach. Decide whether take_any or pop_any is the appropriate API, then implement support for removing an arbitrary element without a Clone bound. Done means both collections expose the requested behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
tooling
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
38/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.