Обновление одной записи отсортированного вектора

Предположим, у меня есть отсортированный std::vector<int> с именем v. Я увеличиваю значение v[i] и хочу пересортировать вектор. Предположим, я рассчитываю увеличить v[i] лишь немного. Следующее, безусловно, неверно.

// (WRONG)
int x = v[i]; // the new v[i], that is
v.erase(v.begin() + i);
v.insert(
    std::upper_bound(v.begin() + i, v.end(), x),
    x
);

Это неправильно, потому что я перемещаю почти весь массив назад, когда я удаляю, и вперед, когда я вставляю, и я могу только немного увеличить v[i], что требует только перемещения нескольких записей. Другая мысль может быть:

int x = v[i]; // the new v[i], that is
if (/* new v[i] is > old v[i] */) {
    size_t j = i + 1;
    while (v[j] < x && j < v.size()) {
        std::swap(v[j-1], v[j])
        j++;
    }
}

и аналогично, если бы я уменьшил v[i] вместо увеличения. Это лучшее?

Предположим, у меня нет доступа к boost::flat_set. (Не уверен, сможет ли это сделать легко или нет.) Приносим извинения, если на это был дан ответ; поиск не нашел ответа.