Suggest pulling collections creation out of loops

In some cases Clippy could suggest ways to write faster Rust code. One common way to optimize Rust code is to pull out of loops the creation of a collection, and just clear it after the loop entry. (An even better solution for this problem is to improve the compiler, to let it recognize and optimize this patter).

A code example:

fn gcd(mut u: u32, mut v: u32) -> u32 {
    if v == 0 { return u; }
    loop {
        u %= v;
        if u == 0 { return v; }
        v %= u;
        if v == 0 { return u; }
    }
}

fn euler_problem_143() -> usize {
    const LIMIT: u32 = 120_000;
    const LIMIT_SQ: u32 = 347;
    let mut pairs = vec![];

    for u in 1 .. LIMIT_SQ {
        for v in 1 .. u {
            if gcd(u, v) != 1 { continue; }
            if (u - v) % 3 == 0 { continue; }

            let a = 2 * u * v + v * v;
            let b = u * u - v * v;

            if a + b > LIMIT { break; }
            let mut k = 1;
            while k * (a + b) < LIMIT {
                pairs.push((k * a, k * b));
                pairs.push((k * b, k * a));
                k += 1;
            }
        }
    }

    pairs.sort_unstable();

    const EMPTY: u32 = std::u32::MAX;
    let mut index = vec![EMPTY; LIMIT as usize];

    for (i, &(p0, _)) in pairs.iter().enumerate() {
        if index[p0 as usize] == EMPTY {
            index[p0 as usize] = i as u32;
        }
    }

    let mut sums = vec![false; LIMIT as usize];

    for &(a, b) in &pairs {
        let (mut va, mut vb) = (vec![], vec![]);

        for &(n0, n1) in &pairs[index[a as usize] as usize ..] {
            if n0 != a { break; }
            va.push(n1);
        }

        for &(n0, n1) in &pairs[index[b as usize] as usize ..] {
            if n0 != b { break; }
            vb.push(n1);
        }

        for &v in &va {
            if vb.iter().any(|&x| x == v) && a + b + v < LIMIT {
                sums[(a + b + v) as usize] = true;
            }
        }
    }

    (0 .. sums.len()).filter(|&i| sums[i]).sum()
}

fn main() {
    println!("{}", euler_problem_143() == 30_758_397);
}

The optimized version:

fn gcd(mut u: u32, mut v: u32) -> u32 {
    if v == 0 { return u; }
    loop {
        u %= v;
        if u == 0 { return v; }
        v %= u;
        if v == 0 { return u; }
    }
}

fn euler_problem_143() -> usize {
    const LIMIT: u32 = 120_000;
    const LIMIT_SQ: u32 = 347;
    let mut pairs = vec![];

    for u in 1 .. LIMIT_SQ {
        for v in 1 .. u {
            if gcd(u, v) != 1 { continue; }
            if (u - v) % 3 == 0 { continue; }

            let a = 2 * u * v + v * v;
            let b = u * u - v * v;

            if a + b > LIMIT { break; }
            let mut k = 1;
            while k * (a + b) < LIMIT {
                pairs.push((k * a, k * b));
                pairs.push((k * b, k * a));
                k += 1;
            }
        }
    }

    pairs.sort_unstable();

    const EMPTY: u32 = std::u32::MAX;
    let mut index = vec![EMPTY; LIMIT as usize];

    for (i, &(p0, _)) in pairs.iter().enumerate() {
        if index[p0 as usize] == EMPTY {
            index[p0 as usize] = i as u32;
        }
    }

    let mut sums = vec![false; LIMIT as usize];
    let (mut va, mut vb) = (vec![], vec![]);

    for &(a, b) in &pairs {
        va.clear();
        vb.clear();

        for &(n0, n1) in &pairs[index[a as usize] as usize ..] {
            if n0 != a { break; }
            va.push(n1);
        }

        for &(n0, n1) in &pairs[index[b as usize] as usize ..] {
            if n0 != b { break; }
            vb.push(n1);
        }

        for &v in &va {
            if vb.iter().any(|&x| x == v) && a + b + v < LIMIT {
                sums[(a + b + v) as usize] = true;
            }
        }
    }

    (0 .. sums.len()).filter(|&i| sums[i]).sum()
}

fn main() {
    println!("{}", euler_problem_143() == 30_758_397);
}

clear() is usable similarly for other collections to reduce the number of heap allocations inside loops.

Start by reviewing the issue's two Rust examples and the proposed collection-reuse pattern. Determine the cases a Clippy lint could identify without changing behavior, then validate the suggestion against equivalent loop examples and confirm that the optimized form preserves the shown result.