this method is equivalent to section of Vec::extract_if seems incorrect #142482
Description
Location
https://doc.rust-lang.org/stable/std/vec/struct.Vec.html#method.extract_if
Summary
The document says Vec::extract_if is equivalent to
let mut i = range.start; while i < min(vec.len(), range.end) { if some_predicate(&mut vec[i]) { let val = vec.remove(i); // your code here } else { i += 1; } }, but I believe this is incorrect as the condition (i.e. i < min(vec.len(), range.end)) in while is re-evaluated in each iteration.
When vec.remove() is called, vec.len() is changed but range.end does not change, so the implementation can remove elements outside the given range.
Probably this is a correct version:
let mut i = range.start; let mut end_exclusive = range.end; while i < min(vec.len(), end_exclusive) { if some_predicate(&mut vec[i]) { end_exclusive -= 1; let val = vec.remove(i); // your code here } else { i += 1; } }Testing
use std::{cmp::min, ops::Range}; fn main() { let l = vec![0, 1, 2, 3, 4, 5]; //`Vec::extract_if` { let mut l = l.clone(); l.extract_if(0..1, |_| true).for_each(|_| ()); println!("{:?}", l); //=> [1, 2, 3, 4, 5]; } //"equivalent" version (incorrect) { fn f<T>( vec: &mut Vec<T>, range: Range<usize>, mut some_predicate: impl FnMut(&mut T) -> bool, ) { //the body is copy&paste-ed from the doc as it is let mut i = range.start; while i < min(vec.len(), range.end) { if some_predicate(&mut vec[i]) { let val = vec.remove(i); // your code here } else { i += 1; } } } let mut l = l.clone(); f(&mut l, 0..1, |_| true); println!("{:?}", l); //=> [] } //"equivalent" version (correct?) { fn f<T>( vec: &mut Vec<T>, range: Range<usize>, mut some_predicate: impl FnMut(&mut T) -> bool, ) { let mut i = range.start; let mut end_exclusive = range.end; while i < min(vec.len(), end_exclusive) { if some_predicate(&mut vec[i]) { end_exclusive -= 1; let val = vec.remove(i); // your code here } else { i += 1; } } } let mut l = l.clone(); f(&mut l, 0..1, |_| true); println!("{:?}", l); //=> [1, 2, 3, 4, 5]; } }