сортировка — C ++: почему функтор для порядка следования, который возвращает ложь, позволяет только одному элементу быть добавленным к набору?

Question

сортировка — C ++: почему функтор для порядка следования, который возвращает ложь, позволяет только одному элементу быть добавленным к набору?

Я написал следующий функтор, ожидая, что все элементы в наборе будут добавлены в обратном порядке их вставки:

struct cmp {
bool operator () (int a, int b) {
return false;
}
};

и когда я проверил это, как показано ниже, единственное значение, добавленное к набору, это 1.

int main() {
set<int, cmp > combos;

combos.insert(1);
combos.insert(4);
combos.insert(7);
combos.insert(5);
combos.insert(9);
combos.insert(1);

for (int a : combos) {
cout << a << endl;
}
return 0;
}

Однако, когда я менял функтор, чтобы он возвращал true каждый раз, все значения добавляются в набор в том порядке, в котором они были вставлены. [1, 4, 7, 5, 9, 1], Я думал, что когда компаратор возвращается true, он обрабатывается так, как будто первый элемент меньше, чем второй элемент, а значение false означает, что первый элемент считается более тертом, чем второй элемент? Кажется, это тот случай, когда я сделал return (a < b); а также return (a > b); в операторной функции.

2

c++icomparable set sorting std

Решение

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

Функция сравнения должна определять строгий слабый порядок элементов. То есть эти три условия должны соблюдаться для всех элементов, a, b, c:

a < a является false (Irreflexitivity)
a < b являющийся true подразумевает b < a является false (Асимметрия)
a < b а также b < c и то и другое true подразумевает a < c это также true (Транзитивность)

При использовании объекта сравнения cmp вышеуказанные условия должны применяться с x < y заменено на cmp(x, y),

Ваша первая функция сравнения (всегда возвращается false) на самом деле строгий слабый порядок, однако, подразумевающий, что все элементы эквивалентны. Нет никакого способа различить два элемента. В частности, ни a < b ни b < a доходность true, Если оба эти условия false два объекта явно эквивалентны. В результате в наборе только один элемент.

Вторая функция сравнения (всегда возвращать true) не является строгим слабым порядком, так как нарушает первое условие (неразрешенность). Все, что происходит в наборе, является неопределенным поведением.

7

Источник

Accepted Answer

В этом случае, std::set использования !(a < b) && !(b < a) определить равенство двух элементов: a а также b,

!(false) && !(false) будет уступать true каждый раз при проверке на дубликаты, тем самым не позволяя std::set содержать более одного элемента. Это плохое обращение с std::set,

2