Неверно & lt; утверждение оператора в виде

Question

Неверно & lt; утверждение оператора в виде

Я пытаюсь реализовать простой компаратор для сортировки индексов на основе значений в массиве «_vec». Я получаю «недействительным < оператор «сообщение об ошибке во время выполнения. Я не понимаю, что не так со следующим кодом:

class Compare{
vector<int>& _vec;
public:
Compare(vector<int>& vec) : _vec(vec) {}
bool operator()(size_t i, size_t j){
if(_vec[i] != _vec[j])
return _vec[i] < _vec[j];
else
return (double)rand()/RAND_MAX < 0.5;
}
};

Я использую следующий вызов функции:

sort(inds.begin(),inds.end(),Compare(vals));

где inds — это просто массив, содержащий индексы от 1 до 15 (скажем), а vals — это массив длиной 15 с некоторыми значениями, чьи отсортированные индексы я хочу вычислить. Общая цель состоит в том, чтобы рандомизировать порядок сортировки, когда две (или более) записи в значениях равны. Любая помощь?

6

assertion c++operator-keyword sorting

Решение

Другие решения

std::sort ожидает, что ваш менее чем оператор предоставит переходный отношения, т.е. когда сортировка видит A < B это правда и B < C это правда, это подразумевает тот A < C также верно.

В вашей реализации правило транзитивности не выполняется: когда два элемента равны, вы случайным образом говорите, что один из них больше другого. Это вызывает утверждение отладки.

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

3

Источник

Accepted Answer

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

C ++ 03 25.3 / 4 «Сортировка и связанные с ней операции» гласит:

Если мы определим эквивалент (a, b) как! Comp (a, b) && ! comp (b, a), то
требования состоят в том, чтобы comp и эквивалентные оба были транзитивными отношениями:

комп (а, б) && comp (b, c) подразумевает comp (a, c)

экв (а, б) && экв (б, в) подразумевает экв (а, в)

[Примечание: при этих условиях можно показать, что

эквив отношение эквивалентности

comp индуцирует четко определенное отношение к классам эквивалентности, определенным

Индуцированное отношение является строгим полным упорядочением.

—Конечная записка]

И для пояснения, Таблица 28 определяет отношение эквивалентности:

== является отношением эквивалентности, то есть удовлетворяет следующему
свойства:

Для всех а, == а.

Если a == b, то b == a.

Так что ваши Compare() операция не даст отношения эквивалентности.

Довольно приятно получить утверждение, а не потерять данные в случайном порядке.

Один из способов решить проблему рандомизации порядка сортировки, когда две (или более) записи в _vec равны, чтобы составить случайное значение для этих индексов и отслеживать эти случайные значения в карте индекса => случайное значение или что-то еще. Просто убедитесь, что вы отслеживаете и используете эти случайные значения таким образом, чтобы переходные и эквивалентные свойства Compare() держать.

7