A more efficient insert_all

[steveklabnik]

Originally rust-lang/rust#15435 by @pnkfelix , who asked me to move it here. I don't have the script handy, so by hand:

---

The Vec type currently provides an push method that allows one to insert a single element at the end of the vector, as well as push_all and push_all_move methods that allow inserting many elements at the end of the vector more efficiently than would happen if the client code called push in a loop (because it avoids repeatedly re-growing the vector).

Vec also offers an insert method that allows inserting a single element somewhere in the innards of the vector.

I believe we could usefully add insert_all and insert_all_move methods that insert a sequence of elements at once. These methods would:

1. Reserve the necessary space,
2. Shift over all of the pre-existing elements to make room,
3. Copy in the new values.

Caveat: we would need to ensure that fail! does not occur between steps 2 and 3.

Much like with push_all/push_all_move, the advantage would be avoiding repeatedly re-growing the vector, the way that calling insert in a loop will do.

(The insert_all and insert_all_move may have to have their own dedicated implementations, rather than being layed atop an iterator-based abstraction the way that push_all/push_all_move are atop Extendable::extend, because of the caveat given above (we cannot call out to arbitrary iterator code during step 3 because we cannot allow failure while the vector is in an intermediate state where it has partially blank innards).

I am filing this mostly as a note because while I was working on #15418, I found a potential need for methods like these to avoid quadratic asymptotic runtimes. But it is probably not a high priority.

Likewise repeated element removal (via pop or remove) is another operation that we might consider optimizing. pop probably does not need it right now since it does not seem like we currently resize the vector when elements are removed (via pop or via remove). But remove still needs to shift elements over, so a variant that removes a range of values could still be potentially useful. (Of course there is still the issue of whether it would return the removed values in their own Vec, or just drop them itself, or if we would need both variants supported in some way.)

I'm largely just noting this here so that I can use the same ticket number in all of the FIXME notes I am adding a number to. :)

[Gankra]

Note that remove_all is just drain_range which was accepted in an RFC but is unsound due to requiring guaranteed dtor execution. insert_all could be made sound with IntoIterator as long as long as we can rely on dtors during panics or are ok with leaking tons of items during a panic.

[aidanhs]

Anyone who stumbles across may be interested in this SO question - http://stackoverflow.com/a/28687253

Edit: or splice from the odds crate - http://bluss.github.io/arrayvec/doc/odds/vec/trait.VecExt.html#tymethod.splice

[mbrubeck]

RFC #1432 adds a Vec::splice method that does efficient (non-quadratic) insertion of multiple elements in the middle.