Add a "shrink-if-excessive" API to `Vec`

Proposal

Problem statement

Stealing from steffahn in https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/31?u=scottmcm:

I think Vec is at least missing some sort of generic shrink()/garbage_collect()/... function with good asymptotics, so that if you called it after every potentially-len-shrinking operation it wouldn’t make your program accidentally-quadratic the way that overuse of shrink_to_fit can.

If it isn't the default, it should at least be easy to manually use Vec as a dynamic array with (only) a constant factor memory overhead, if you want to.

Motivating examples or use cases

After a .collect() or .retain(…), where you know you're not going to be pushing for a while so you'd like to not be wasting too much capacity, but aren't worried about it being exactly anything (since reallocating to save one or two items is probably a waste of time, and doesn't actually reduce memory usage).

Having something to write after the warning in https://doc.rust-lang.org/std/vec/struct.Vec.html#impl-FromIterator%3CT%3E-for-Vec%3CT%3E, as something like "You can call the ______ method after doing the operation if you want to avoid excessive remaining capacity".

Solution sketch

// in alloc::vec

impl<T, A: Allocator> Vec<T, A> {
    /// If this vector's `.capacity()` is much larger than its `.len()`,
    /// then `.shrink_to_fit()` it, otherwise do nothing.
    /// 
    /// For example, you might want to call this after doing a `retain`
    /// on a particularly-large vector that has a chance of removing
    /// most of the elements, but where you wouldn't want to 
    /// `.shrink_to_fit()` unconditionally since that's a waste of
    /// CPU if only a few items were removed.
    /// 
    /// Note that "much larger" is intentionally unspecified here,
    /// just like how `reserve` does not specify its growth strategy.
    /// **Do not** use it in any situation where you need a particular
    /// capacity exactly.
    /// 
    /// Beware calling this in a loop, as if that loop sometimes adds
    /// things to the container, this can cause quadratic complexity
    /// for things that would otherwise have been linear.
    /// 
    /// For now, only a few basic things are guaranteed:
    /// - This is *idempotent*: calling it multiple times (without otherwise
    ///   changing the vector between the calls) does the same as
    ///   calling it just once would do.
    /// - If *all* you do on an empty, zero-capacity vector is a sequence
    ///   of `push`es, then there's no need to call this as it'd do nothing.
    /// - In a loop that *monotonically decreases* the length of a vector,
    ///   calling this every iteration will not itself cause quadratic behaviour.
    fn shrink(&mut self) {
        if self.capacity() ⋙ self.len() {
            self.shrink_to_fit();
        }
    }
}

Alternatives

• shrink might be too short a name for something that can still be very costly if misused, so shrink_to_reasonable or shrink_if_profitable or something might be better. But at the same time since it's less risky than a full shrink_to_fit, giving it a more convenient name might be better.
• We could give more or fewer guarantees.

Links and related work

https://github.com/rust-lang/rust/issues/120091

https://internals.rust-lang.org/t/vec-is-asymmetric-with-memory-handling/22449/31?u=scottmcm

What happens now?

This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.

Possible responses

The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):

• We think this problem seems worth solving, and the standard library might be the right place to solve it.
• We think that this probably doesn't belong in the standard library.

Second, if there's a concrete solution:

• We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
• We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.

Start with the alloc::vec::Vec API and the proposed shrink_to_fit behavior described here. Review issue #120091 and the linked internals discussion before deciding whether the API name and guarantees are sufficient. Done requires a libs-api decision on the problem and a concrete approved design.