Rust: Tracking issue for Vec::remove_item

[madseagames]

Implemented in https://github.com/rust-lang/rust/pull/40325

```rust
impl Vec {
pub fn remove_item(&mut self, item: &T) -> Option { /…/ }
}

[clarfonthey]

PR moved to #40325 due to reasons

[clarfonthey]

Comments from original thread:

1. I think that we should add this method to VecDeque too.
2. Is remove_last_item desired?

[madseagames]

@clarcharr for remove_last_item you can simply do vec.remove(vec.len() - 1))

[clarfonthey]

@madseagames I meant specifically a method that searches for the item from the end of the vec instead of the beginning

[oberien]

What do you think about adding remove_swap_item? Just as remove_swap reduces the runtime complexity from O(n) to O(1) compared to remove, remove_swap_item would reduce it from O(n + (n-m)) to O(n).

[clarfonthey]

I like swap_remove_item.

[MarkSwanson]

It would be nice if this was more generic.
let v: Vec = Vec::new();
v.remove_item("s"); <-- fails because &str is not a &String

we really want the remove_item "item: &T" to be "something that we can compare equality with the type in the container". This would let remove_item() walk the T items, compare equality, and remove if equal.

[sfackler]

Seems reasonable to change the signature to fn remove_item<U>(&mut self, item: &U) -> Option<T> where T: PartialEq<U> + ?Sized

[leoyvens]

Reviewing the naming used in method names and the docs, it would seem that iterators yield _items_ while vecs contain _elements_. Considering that we insert elements then we should also remove elements and the method should be called remove_element. That name is a bit long so I'd propose simply remove_eq. However I wonder if we should favor a more general remove_by, or have both.

fn remove_by<F: FnMut(&T) -> bool>(&mut self, f: F)

[zbraniecki]

Any plan to stabilize this?

[SimonSapin]

This has been in nightly for a year with no issue reported on the method itself. There are proposals for additional methods, but that shouldn’t block this one. Please submit separate PRs or RFCs.

@rfcbot fcp merge

[rfcbot]

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged team members:

• [x] @Kimundi
• [x] @SimonSapin
• [ ] @alexcrichton
• [x] @aturon
• [x] @dtolnay
• [x] @sfackler
• [x] @withoutboats

Concerns:

• rationale-and-vecdeque resolved by https://github.com/rust-lang/rust/issues/40062#issuecomment-465694305

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[sfackler]

Are we switching to a V: PartialEq<T> bound?

[SimonSapin]

Oops, sorry I missed that. Yes, let’s.

[gnzlbg]

Again here, as a maintainer of collections that offer the Vec and VecDeque APIs I'd like at least a summary comment explaining what this method does, why this design was followed, alternatives, and addressing the issues mentioned here that have received zero replies:

• should this method be added to VecDeque?
• @sfackler :

Seems reasonable to change the signature to fn remove_item<U>(&mut self, item: &U) -> Option<T> where T: PartialEq<U> + ?Sized

• @leodasvacas naming issue: why items instead of elements? why remove_items instead of remove_by, etc.

[alexcrichton]

@rfcbot concern rationale-and-vecdeque

Just gonna formally register @gnzlbg's concern above

[kornelski]

Not an issue with the method per se, but it may need to be very clearly documented that the reference is not supposed to be to an item that is in the Vec already, as it creates impossible borrow-checker conundrum.

Users coming from the C world of pointers but no proper equality comparison, may be confused by this method, e.g. https://users.rust-lang.org/t/difficult-borrowing-situation/16794

The remove_eq name mentioned previously would help.

[alexcrichton]

@SimonSapin as the proposer for FCP, do you have thoughts on @gnzlbg's concern?

[droundy]

My thinking is that the remove_by suggested by @leodasvacas would sidestep most of the issues here.

[Centril]

cc @SimonSapin re. https://github.com/rust-lang/rust/issues/40062#issuecomment-389903127

[SimonSapin]

I don’t have a strong desire for this particular feature myself, I proposed FCP as an effort to reduce the number of features in "unstable limbo". That said:

Regarding VecDeque, sure, I don’t see a reason not to add it there as well.

remove_by as proposed in https://github.com/rust-lang/rust/issues/40062#issuecomment-323403342 sounds good to me. It is more general, and goes with precedent of Iterator::position also taking a boolean callable predicate rather than relying on PartialEq. (Even further, the precedent of Iterator not having a method like position that would rely on PartialEq.)

[withoutboats]

I notice two things:

1. There are a lot of methods similar to this we could add, and its not obvious to me which set of those methods is the ideal set.
2. This has sat in FCP concern limbo for 8 months without anyone complaining.

I think we should not stabilize this just because it exists, but instead someone should come up with a well justified explanation of exactly what the best "find and remove" set of methods of vec-likes would be.

[SimonSapin]

Good points.

drain (which is stable) and drain_filter https://github.com/rust-lang/rust/issues/43244 also fit the "find and remove" description, and we had a similar concern https://github.com/rust-lang/rust/issues/43244#issuecomment-376886108 about the combinations of filtering v.s. non-filtering and self-exhausting on drop (https://github.com/rust-lang/rfcs/pull/2369) v.s. not.

[alexcrichton]

@rfcbot resolve rationale-and-vecdeque

I don't want to personally be on the hook for blocking this any more

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period, with a disposition to merge, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

The RFC will be merged soon.

[leoyvens]

I still think this should be called remove_eq instead of remove_item.

[mathstuf]

My problem with that name is that it only removes the first matching item, not all that are eq (though I haven't read the relevant RFC to know whether the name has been hashed out already; I assume it has been).

[kornelski]

I don't think the naming issue has been resolved. The implementation is still using the confusing remove_item name.

@mathstuf remove_first_eq then?

[Centril]

@rust-lang/libs Can someone clarify what the status of this is wrt. the conversation above?

[Boiethios]

I notice two things:

1. There are a lot of methods similar to this we could add, and its not obvious to me which set of those methods is the ideal set.

2. This has sat in FCP concern limbo for 8 months without anyone complaining.

I think we should not stabilize this just because it exists, but instead someone should come up with a well justified explanation of exactly what the best "find and remove" set of methods of vec-likes would be.

An example: I'm writing a proc macro attribute, and amongst the tokens, I expect other attribute to be there. This would be useful to add:

if let Some(attr) = attrs.remove_item(|item| attr.path.is_ident("foo")) {
    // Handle the `foo` attribute case...
}

[SimonSapin]

@Boiethios Until we sort this out, you can use attrs.iter().position(|item| some_boolean(item)).map(|i| attrs.remove(i))

[lzutao]

Ping. What's the status of this? Could we stabilize something?

[gilescope]

@mathstuf remove_first ? Given we already have drain_filter for accepting a predicate, it would be nice to have a method that removed a single object from the vector (if there). Removing something from a vec is exceedingly common code. Getting the position and then removing that position is longwinded for such a common operation.

(Btw, I think _first bit of naming is excellent as it highlights that there may be others still in the vec - a method name that prompts one to think is a good thing.)

[droundy]

I use retain for this, and haven't found it too cumbersome. It differs in that it removes all copies of a given item, but is very easy for many purposes.

[gilescope]

Retain everything but the object? As work-arounds go that's shorter, but it's not ideal for expressing intent. Still keen on remove_first and swap_remove_first.

[LukasKalbertodt]

Just to bring up a different opinion: how about removing this method instead of stabilizing it? While yes, it would be convenient to have, it might not be worth it.

For one, remove_item is not a good name, as many already said. The name doesn't imply that the first item from the start is removed. remove_first is better in that regard, but still doesn't feel completely right.

More importantly, if we have remove_first, we should certainly also have remove_last. Having one but not the other feels arbitrary to me and makes for a surprising API (that's bad). Similarly, we would also want to add the swap_remove variant of both of those methods. Potentially, we also want to add a variant that removes all items equal to the given needle. And as also already mentioned, we can also add all those methods to VecDeque. And why not LinkedList (without the swap_remove versions)? Consequently, we would have to add 10 or 15 new methods. Adding fewer would make the API inconsistent IMO.

All the functionality can be implemented with very little extra code with iterators.

[jonhoo]

@LukasKalbertodt How do you propose this be implemented with iterators?

How about this signature:

impl<T: PartialEq> Vec<T> {
    fn remove_eq(&mut self, item: &T, limit: Option<usize>) -> impl Iterator<Item = T>;
}

This uses remove_eq to make it clear exactly what is removed. The limit argument and the return type makes it clear that we remove many items. The user has the option of how many to remove (None means all). The returned iterator can be implemented efficiently by shifting the items and then pulling a similar trick (using Vec::set_len) to Drain to yield the removed items.

[LukasKalbertodt]

How do you propose this be implemented with iterators?

@SimonSapin already mentioned this above:

v.iter().position(|&n| n == 2).map(|i| v.remove(i))

How about this signature:

I think that one is too complex. Especially when considering the call site, I think it's fairly hard to understand. And the name still does not imply that the search begins at the beginning, which is a big nono for me.

[gilescope]

Removing an item from a vec is a _very_ common codepath. Somehow it needs
to be a one liner. Having swap_remove_first() and not having remove_first()
would be nudging people in the direction of great performance. That seems
quite rustic to me.

swap_remove_last is interesting as there maybe no swap needed if it happens
to be the last item - cute.

Just have those two functions. That’s the 80% case covered. People who wish
to maintain order will just have to have slightly more code.

On Fri, 15 Nov 2019 at 19:20, Lukas Kalbertodt [e-mail]
wrote:

How do you propose this be implemented with iterators?

@SimonSapin https://github.com/SimonSapin already mentioned this above
https://github.com/rust-lang/rust/issues/40062#issuecomment-480060761:

v.iter().position(|&n| n == 2).map(|i| v.remove(i))

How about this signature:

I think that one is too complex. Especially when considering the call
site, I think it's fairly hard to understand. And the name still does not
imply that the search begins at the beginning, which is a big nono for me.

—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
https://github.com/rust-lang/rust/issues/40062?email_source=notifications&email_token=AAGEJCHYNLO4ZKAMVMA5BOTQT3Y6RA5CNFSM4DBIVPY2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEEGOGDA#issuecomment-554492684,
or unsubscribe
https://github.com/notifications/unsubscribe-auth/AAGEJCA4CI3ECYCCXJLCDODQT3Y6RANCNFSM4DBIVPYQ
.

[ssomers]

I don't understand the focus on removing here. Vec has a lot more members taking an index than remove and swap_remove, and only a few to get hold of an index value (binary_search variants and len, sort of). Most of the complication in the "workaround" for this remove_item is finding the first index of something:

v.iter().position(|&n| n == 2)

Not too bad, the iter reminds you it's a linear search, but could be easier. Worse for the last index:

v.iter().rev().position(|&x| x == 2).map(|i| v.len() - i - 1)

Contrast to the find and rfind in that famous vector called string that infiltrated Rust (ugly names but at least they convey that a search is involved).

I've vary rarely needed this, I don't advocate making linear searches easy, it just seems more useful to try to make searching easier, before making search-and-removing easier.

[Pauan]

@ssomers rposition already exists (so does rfind). And even if it didn't exist, that has no relevance to whether remove_item should exist or not, they're separate features, so they can both exist, it isn't either/or.

(I personally have had many cases where remove_item would have been useful, it's a common operation in any language.)

[kornelski]

Waaait! It's getting stabilized without fixing the confusing name!

Please please don't call it remove_item, as this is the same name as in other languages that can remove item from an array by presenting an item from the same array. Rust's version can't do that due to borrow checker and it's a trap for users.

[Lokathor]

I absolutely wouldn't call it a trap.

[LukasKalbertodt]

It seems like many people agree that the name should at least be up for debate again. Really unfortunate how the name discussion was somehow forgotten during FCP. So I guess we should revert stabilization as soon as possible so it won't end up in beta?

[gnzlbg]

So I guess we should revert stabilization as soon as possible so it won't end up in beta?

Sounds reasonable. Maybe someone wants to volunteer to lead the process about settling on a name for this ?

[Amanieu]

The next release is scheduled for Jan 30th. So we have about 3 weeks to figure out a new name.

[LukasKalbertodt]

I went through the thread again and it seems like the following names are suggestions for the method as it currently exists:

• remove_element (iterators have "items", Vec has "elements")
• remove_eq
• remove_first_eq
• remove_first

Personally, I would absolutely include first, as that's an important information and it makes the user think. I have no preference between remove_first and remove_first_eq.

---

However, from reading the thread again it seems there are plenty of other concerns and suggestions that haven't been resolved yet:

• Adding similar methods:
  
  
  
  • remove_last_item?
  
  
  • swap_remove_*?
  
  
• Replace the method with:
  
  
  
  • fn remove_by<F: FnMut(&T) -> bool>(&mut self, f: F) (although I don't understand that one. Is it just a retain with flipped predicate? In that case I don't think it's useful. If it just removes the first element, then first absolutely needs to be in the name IMO.)
  
  
  • Only swap_remove_* versions to nudge people to better performance
  
  
• Do not stabilize this method at all: comment 1, comment 2

[gnzlbg]

@withoutboats mentioned here:

I think we should not stabilize this just because it exists, but instead someone should come up with a well justified explanation of exactly what the best "find and remove" set of methods of vec-likes would be.

@SimonSapin also raised some more concerns here, and I raised some concerns here.

I don't see where these concerns have been resolved. From re-reading this whole discussion, it isn't clear to me what the goal of adding this method is nor what problem does this method solve or whether this is a problem worth solving. What's more or less clear to me is that there is at least some design work to be done to at least ensure that libstd exposes a consistent API, and that sounds like this would warrant an RFC to me. The current discussion about using a _by method hints that these APIs might not only want to be consistent for the ordered collections (Vec, VecDeque, List) for which a notion of a "first" element makes sense, but might also want to be consistent with the e.g. _by and _by_key methods of slices.

The main arguments for FCPing this appear to be that this has sit on nightly for too long without anybody complaining, and the main argument for stabilizing this has been that this has been in FCP for too long. I think it would be better to just encourage and support those that want to land this feature to write a small RFC for it. If somebody is interested in doing that, I would be able to help and give feedback.

[Pauan]

Unless a concern is made with @rfcbot concern by a relevant team member, then it won't stop FCP. And it won't go into FCP unless the majority of team members have voted for it (and there aren't any formal concerns listed).

So the fact it passed FCP means that all relevant team members explicitly and intentionally marked that they were okay with the current design and did not have any outstanding concerns at the time. Things do not go into FCP simply because it's been "sitting around too long".

Of course if any team members do have any concerns, now would be the best time to make them.

[LukasKalbertodt]

@Pauan

So the fact it passed FCP means that all relevant team members explicitly and intentionally marked that they were okay with the current design and did not have any outstanding concerns at the time.

Mistakes happen. And to me this thread clearly looks like many concerns were overlooked accidentally and no one explicitly marked them as concerns for rfcbot. Luckily those mistakes were caught.

[nagisa]

Reopening because #68089

[dtolnay]

The current signature is missing a ?Sized bound. Could I ask for a PR to fix the bound and add a test that covers remove_item("...") on a Vechttps://github.com/rust-lang/rust/pull/67727#issuecomment-570660301 and https://github.com/rust-lang/rust/issues/40062#issuecomment-305978259.

#![feature(vec_remove_item)]

fn main() {
    let mut v = vec![String::new()];
    v.remove_item("");
    println!("{:?}", v);
}

error[E0277]: the size for values of type `str` cannot be known at compilation time
 --> src/main.rs:5:19
  |
5 |     v.remove_item("");
  |                   ^^ doesn't have a size known at compile-time
  |
  = help: the trait `std::marker::Sized` is not implemented for `str`
  = note: to learn more, visit <https://doc.rust-lang.org/book/ch19-04-advanced-types.html#dynamically-sized-types-and-the-sized-trait>

[dtolnay]

Separately: I am leaning toward removing remove_item. I agree with https://github.com/rust-lang/rust/issues/40062#issuecomment-554486688 and https://github.com/rust-lang/rust/issues/40062#issuecomment-560309989. The currently design involves:

• start with a reference to a value not in the vec,
• use its PartialEq impl to
• do a linear scan,
• remove the first found,
• shift everything after the removed element.

To generalize almost all of the discussion above, people are questioning whether the conjunction of all 5 of these decisions is really as common as a name like remove_item would suggest, whether a different permutation of choices might be more widely applicable, and how to adjust naming to leave room for all the other equally or more common permutations:

• ones where the ref we want to remove is a ref to a vec element,
• or we want to remove by FnMut instead of PartialEq,
• or we want a binary search,
• or we want to remove the last, or all matches,
• or we want the more efficient swap_remove behavior.

Fortunately Vec already supports all permutations of these use cases equally well, with nice independent APIs for searching and removing.

Many people have voiced opinions equivalent to "removing an item from a vec is so common that there absolutely must be a function for it". I think what they mean is that the union of all permutations of the above 5 choices is common, which is true; they don't necessarily mean the specific choices that go into remove_item as it exists would justify a method specific to those choices. https://github.com/rust-lang/rust/issues/40062#issuecomment-554486688 points out that satisfying the set of use cases which all together are common would take a much larger number of new methods.

[dtolnay]

Per https://github.com/rust-lang/rust/issues/40062#issuecomment-583911228, I think we should go ahead and remove Vec::remove_item.

@rfcbot fcp close

[Pauan]

@dtolnay Many people have voiced opinions equivalent to "removing an item from a vec is so common that there absolutely must be a function for it". I think what they mean is that the union of all permutations of the above 5 choices is common

That is not what I meant. When I said that I need remove_item in my code, I meant exactly that: that I could take my existing code and replace it with remove_item and it would have exactly the same behavior, because I really do need remove_item specifically, not the other fancier methods.

I'm perfectly fine with changing the name so that we can accommodate other fancier methods in the future, but why would that mean that we shouldn't have remove_item at all?

[dtolnay]

@rfcbot fcp cancel

[rfcbot]

@dtolnay proposal cancelled.

[dtolnay]

@rust-lang/libs: Per https://github.com/rust-lang/rust/issues/40062#issuecomment-583911228, I think we should go ahead and remove Vec::remove_item.

@rfcbot fcp close

[rfcbot]

Team member @dtolnay has proposed to close this. The next step is review by the rest of the tagged team members:

• [x] @Amanieu
• [x] @KodrAus
• [x] @SimonSapin
• [x] @dtolnay
• [ ] @sfackler
• [x] @withoutboats

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[SimonSapin]

Checking KodrAus’ checkbox per https://github.com/rust-lang/team/commit/45013d114d89480c33cab2a1a99828e4aacb8aee

[rfcbot]

:bell: This is now entering its final comment period, as per the review above. :bell:

[rfcbot]

The final comment period, with a disposition to close, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

[KodrAus]

Since we've merged the deprecation would we like to close this tracking issue now? Or keep it open until the unstable deprecated method is removed entirely?

[LukasKalbertodt]

I think keeping this open until we removed the method is a good idea. How long do we want to wait with that by the way? I guess a couple of cycles is sufficient?

[AgarwalPragy]

Before closing, it would be great if someone could suggest a "one clean and obvious" way to remove the first/last occurance of an item from a Vector.

Irrespective of the arguments made here, a method removing the first/last occurance of an item is provided across all major programming languages, and is to be "expected"

Anyone new to rust is bound to google "remove from vec rust" and end up on this discussion which would only leave them more confused.

[LukasKalbertodt]

This StackOverflow Q&A should answer those questions. But here is a copy of my answer for convenience:

---

Remove first element equal to needle

// Panic if no such element is found
vec.remove(vec.iter().position(|x| *x == needle).expect("needle not found"));

// Ignore if no such element is found
if let Some(pos) = vec.iter().position(|x| *x == needle) {
    vec.remove(pos);
}

You can of course handle the None case however you like (panic and ignoring are not the only possibilities).

Remove last element equal to needle

Like the first element, but replace position with rposition.

Remove all elements equal to needle

vec.retain(|x| *x != needle);

... or with swap_remove

Remember that remove has a runtime of O(n) as all elements after the index need to be shifted. Vec::swap_remove has a runtime of O(1) as it swaps the to-be-removed element with the last one. If the order of elements is not important in your case, use swap_remove instead of remove!

[LukasKalbertodt]

It might be worth adding more examples (maybe all of the ones above) to the Vec::remove docs.

[nrabulinski]

I'd like to add those to the docs, should they go along the example that we currently have?

[LukasKalbertodt]

@nrabulinski What examples are you referring to? I could imagine those "remove examples" either going on the type (as a new section "Removing elements" or something like that) or directly on the Vec::remove method (below the existing docs). And by the way, feel free to add (parts of) my text/examples verbatim.

[nrabulinski]

Thank you. I was referring to those "remove examples" as to whether I should append them to what we currently have in docs for Vec::remove, put them somewhere else or perhaps modify examples for Vec::remove to include removal of specific element

[LukasKalbertodt]

append them to what we currently have in docs for Vec::remove

That sounds fine to me. Feel free to just open a PR and we can still see about the specifics then :)