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:
- Reserve the necessary space,
- Shift over all of the pre-existing elements to make room,
- 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.
The
Vectype currently provides anpushmethod that allows one to insert a single element at the end of the vector, as well aspush_allandpush_all_movemethods that allow inserting many elements at the end of the vector more efficiently than would happen if the client code calledpushin a loop (because it avoids repeatedly re-growing the vector).Vecalso offers aninsertmethod that allows inserting a single element somewhere in the innards of the vector.I believe we could usefully add
insert_allandinsert_all_movemethods that insert a sequence of elements at once. These methods would: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 callinginsertin a loop will do.(The
insert_allandinsert_all_movemay have to have their own dedicated implementations, rather than being layed atop an iterator-based abstraction the way thatpush_all/push_all_moveare atopExtendable::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.