Блог

Предположим, у меня есть sorted std::vector<int> called 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 amp;amp; j < v.size()) {
        std::swap(v[j-1], v[j])
        j  ;
    }
}
  

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

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

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

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

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