Определение, изменил ли std :: sort (начало, конец) диапазон

Question

Какой самый элегантный способ определить, действительно ли вызов std::sort(begin, end) изменил диапазон?

Вот мои две идеи:

(a) проверить, отсортированы ли уже O (n):

if (already_sorted(begin, end)) { return false; }
std::sort(begin, end);
return true;

(b) отслеживать изменения в компараторе (это безопасно?):

bool modified = false;
std::sort(begin, end, [&modified](T a, T b){ modified |= a<b; return a<b; });
return modified;

Есть ли лучший способ?

Answer 1

Я не думаю, что вы можете сделать это лучше, чем проверка O (n), если массив вернулся в другом порядке, чем тот, с которого он начинался.Взлом компаратора, чтобы увидеть, если что-то не так, если порядок не гарантированно работает, так как в теории функция сортировки может делать любые сравнения, которые ей нравятся, без необходимости что-либо перемещать.Более того, отслеживание того, были ли выполнены какие-либо перестановки, не обязательно говорит о том, изменился ли порядок, поскольку сортировка может также перемещать объекты и восстанавливать их в том же порядке в конце сортировки (например, подумать о heapsort).

Answer 2

Если вы не выполните итерацию структуры от «начала» до «конца», вы не сможете узнать, отсортирована ли она уже, поэтому лучшее, что вы можете сделать, - O (n).будет выбран первый вариант, уже отсортированный.

Answer 3

Если сортируемые объекты относятся к типу класса, вы можете ввести подобъект с перегрузкой operator =, которая будет вызываться std::swap.Тем не менее, теоретически это может разрешить ложные срабатывания, если объекты были поменяны местами, а затем поменяны местами назад.

Возможно, вам следует придерживаться already_sorted, пока вы не будете уверены, что оно занимает значительное количество общего выполнения.время.

Answer 4

Считаете ли вы диапазон измененным, если были обменены два равных значения?В этом случае уже отсортированный вариант не будет работать.

В противном случае это должен быть самый быстрый способ.