В документации перечислены сложности для всех стандартных коллекций и операций :
Во всей документации мы будем придерживаться нескольких соглашений.Для всех операций размер коллекции обозначается n.Если в операции участвует другая коллекция, она содержит m элементов.К операциям с амортизированной стоимостью добавляется *.К операциям с ожидаемой стоимостью добавляется суффикс ~.
get(i) insert(i) remove(i) append split_off(i)
Vec O(1) O(n-i)* O(n-i) O(m)* O(n-i)
. Документация для Vec::insert поясняет подробности, выделено мое:
Вставляет элемент в положение index внутри вектора, , смещая все элементы после него вправо .
Насколько эффективно вставить элемент вначало ОЧЕНЬ большого вектора с миллиардами элементов?
ОЧЕНЬ плохая идея, так как все должно быть перемещено.Возможно, VecDeque будет лучше (или найти другой алгоритм).