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

Question

Предположим, у меня есть сортировка 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.(Не уверен, может ли это сделать это легко или нет.) Извиняюсь, если на это был дан ответ;поиск не нашел ответа.

Answer 1

Используйте std::rotate, чтобы переместить элемент на новую позицию.Если вы действительно думаете, что он не продвинется далеко, возможно, будет быстрее выполнить линейный поиск новой позиции (или примените гибридный подход, проверив удвоение расстояния от старой позиции, чтобы найти границу для upper_bound).

Answer 2

Вы не должны erase, а затем insert элементы, когда вам это не нужно. Если вы увеличиваете элемент на итераторе pos, вам нужно только найти место для вставки и поворота элементов на единицу:

 auto new_pos = std::lower_bound(pos,end,*pos);
 std::rotate(pos,pos+1,new_pos);