Как правильно поменять значения?

Question

[egorggegor]

Есть следующий код:

for (auto it = vector.begin(); it != vector.end(); it++) {
            (*it).update();
            auto new_pos = std::lower_bound(vector.begin(), it, (*it));
            std::swap((*new_pos).value, (*it).value);
        }

Здесь берется итератор от начала массива до конца, каждый раз достается элемент, обновляется и ищется новая позиция для него, но нельзя вставлять на места элементов, которые не обновлены.
То есть берем 1-ый элемент, обновляем, а дальше, так как всего один элемент обновлен, то можем рассматривать только одну позицию для вставки.

Мой код только циклически сдвигает элементы, как исправить, чтобы работало все правильно?

Comments

[Wataru]

Как работает операция сравнения? Что значит: циклический сдвиг? Пример работы с числами помог бы.

Answer 1

[Wataru]

Судя по коду, вы хотите, чтобы массив был отсортирован. Но тогда просто менять новый элемент с чем-то в массиве неправильно - его надо туда вставлять, сдвигая все элементы.

Вот пример: уже обновленная и отсортированная часть {1, 2, 3, 5, 6, 7}. Только что обновленный элемент имеет значение 4. lower_bound вернет итератор на 5. Вы поменяете 5 и 4 и получите {1, 2, 3, 4, 6, 7, 5} - не отсортировано уже.

Можно удалить элемент в it и вставить на новое место через insert, но тогда могут быть проблемы с итератором цикла. Можно ручками через swap сдвигать элементы в цикле:

T tmp = it->value;
for (auto cur = std::lower_bound(vector.begin(), it, (*it)); cur < it; ++cur) {
   swap(tmp, cur->value);
}
it->value = tmp;

Это, фактически, будет сортировкой вставкой за O(N^2). lower_bound за логарифм тут на самом деле даже лишнее и только замедляет сортировку. Лучше одним циклом сразу и swap-ать и сравнивать элементы.

Но еще быстрее будет отдельно пройтись по массиву и обновить его целиком и потом вызвать std::sort для сортировки по value.