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 Vec::remove_item #40062

Open
madseagames opened this issue Feb 23, 2017 · 72 comments
Open

Tracking issue for Vec::remove_item #40062

madseagames opened this issue Feb 23, 2017 · 72 comments

Comments

@madseagames
Copy link
Contributor

@madseagames madseagames commented Feb 23, 2017

Implemented in #40325

impl<T: PartialEq> Vec<T> {
    pub fn remove_item(&mut self, item: &T) -> Option<T> { /*…*/ }
}
@clarfonthey
Copy link
Contributor

@clarfonthey clarfonthey commented Mar 8, 2017

PR moved to #40325 due to reasons

@clarfonthey
Copy link
Contributor

@clarfonthey clarfonthey commented Mar 8, 2017

Comments from original thread:

  1. I think that we should add this method to VecDeque too.
  2. Is remove_last_item desired?
@madseagames
Copy link
Contributor Author

@madseagames madseagames commented Mar 8, 2017

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

@clarfonthey
Copy link
Contributor

@clarfonthey clarfonthey commented Mar 8, 2017

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

@oberien
Copy link
Contributor

@oberien oberien commented Mar 15, 2017

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
Copy link
Contributor

@clarfonthey clarfonthey commented Mar 15, 2017

I like swap_remove_item.

@MarkSwanson
Copy link

@MarkSwanson MarkSwanson commented Jun 3, 2017

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
Copy link
Member

@sfackler sfackler commented Jun 3, 2017

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

@leoyvens
Copy link
Contributor

@leoyvens leoyvens commented Aug 18, 2017

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
Copy link

@zbraniecki zbraniecki commented Jan 29, 2018

Any plan to stabilize this?

@SimonSapin
Copy link
Contributor

@SimonSapin SimonSapin commented Mar 17, 2018

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
Copy link

@rfcbot rfcbot commented Mar 17, 2018

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

Concerns:

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
Copy link
Member

@sfackler sfackler commented Mar 17, 2018

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

@SimonSapin
Copy link
Contributor

@SimonSapin SimonSapin commented Mar 17, 2018

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

@gnzlbg
Copy link
Contributor

@gnzlbg gnzlbg commented Mar 18, 2018

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
Copy link
Member

@alexcrichton alexcrichton commented Mar 19, 2018

@rfcbot concern rationale-and-vecdeque

Just gonna formally register @gnzlbg's concern above

@kornelski
Copy link
Contributor

@kornelski kornelski commented Apr 11, 2018

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
Copy link
Member

@alexcrichton alexcrichton commented May 17, 2018

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

@droundy
Copy link
Contributor

@droundy droundy commented Sep 3, 2018

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

@Centril
Copy link
Contributor

@Centril Centril commented Dec 29, 2018

@SimonSapin
Copy link
Contributor

@SimonSapin SimonSapin commented Dec 29, 2018

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 #40062 (comment) 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
Copy link
Contributor

@withoutboats withoutboats commented Dec 29, 2018

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
Copy link
Contributor

@SimonSapin SimonSapin commented Dec 29, 2018

Good points.

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

@alexcrichton
Copy link
Member

@alexcrichton alexcrichton commented Feb 20, 2019

@rfcbot resolve rationale-and-vecdeque

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

@Pauan
Copy link

@Pauan Pauan commented Feb 24, 2020

@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

This comment has been minimized.

@rfcbot

This comment has been minimized.

@dtolnay
Copy link
Member

@dtolnay dtolnay commented Feb 24, 2020

@rust-lang/libs: Per #40062 (comment), I think we should go ahead and remove Vec::remove_item.

@rfcbot fcp close

@rfcbot
Copy link

@rfcbot rfcbot commented Feb 24, 2020

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

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
Copy link
Contributor

@SimonSapin SimonSapin commented Apr 15, 2020

Checking KodrAus’ checkbox per rust-lang/team@45013d1

@rfcbot
Copy link

@rfcbot rfcbot commented Apr 15, 2020

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

@rfcbot
Copy link

@rfcbot rfcbot commented Apr 25, 2020

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.

LukasKalbertodt added a commit to LukasKalbertodt/rust that referenced this issue May 2, 2020
kornelski added a commit to kornelski/rust that referenced this issue May 7, 2020
RalfJung added a commit to RalfJung/rust that referenced this issue Jun 20, 2020
…e-item, r=Mark-Simulacrum

Deprecate `Vec::remove_item`

In rust-lang#40062 we decided to remove that method. In rust-lang#71834 it was said that we want to deprecate it for a few cycles before removing it. That's what this PR does.
@KodrAus
Copy link
Contributor

@KodrAus KodrAus commented Jul 29, 2020

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
Copy link
Member

@LukasKalbertodt LukasKalbertodt commented Jul 29, 2020

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
Copy link

@AgarwalPragy AgarwalPragy commented Aug 10, 2020

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
Copy link
Member

@LukasKalbertodt LukasKalbertodt commented Aug 10, 2020

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
Copy link
Member

@LukasKalbertodt LukasKalbertodt commented Aug 10, 2020

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

@nrabulinski
Copy link
Contributor

@nrabulinski nrabulinski commented Aug 20, 2020

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

@LukasKalbertodt
Copy link
Member

@LukasKalbertodt LukasKalbertodt commented Aug 26, 2020

@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
Copy link
Contributor

@nrabulinski nrabulinski commented Aug 29, 2020

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
Copy link
Member

@LukasKalbertodt LukasKalbertodt commented Aug 30, 2020

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 :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

You can’t perform that action at this time.