Краткий ответ

В std::set два ключа считаются эквивалентными, если компаратор не считает один ключ меньше другого в обе стороны: !comp(a, b) && !comp(b, a). Это не обязано совпадать с результатом operator==: именно такое отношение определяет уникальность элементов, результат find и возможность вставки.

Исторический контекст

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

Такой подход позволяет хранить структуры, для которых естественного operator== нет, а также задавать разные критерии порядка: например, сортировку строк по длине или объектов по определённому полю.

Постановка проблемы

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

Компаратор обязан задавать строгое слабое упорядочивание. Нарушение требований, например зависимость результата от изменяемого состояния или несогласованные результаты сравнений, приводит к некорректному поведению операций контейнера.

Подробное решение

Для ключей a и b контейнер проверяет их взаимное отношение через компаратор comp:

если comp(a, b) истинно, a находится раньше b;
если comp(b, a) истинно, b находится раньше a;
если оба результата ложны, ключи эквивалентны.

Условие эквивалентности записывается как !comp(a, b) && !comp(b, a). При такой эквивалентности второй ключ не добавляется в std::set, а insert сообщает, что вставка не была выполнена; методы поиска также рассматривают оба ключа как одну позицию.

Компаратор не обязан проверять полное равенство объектов. Например, сравнение только по длине делает строки одинаковой длины эквивалентными для контейнера:

#include <iostream>
#include <set>
#include <string>

struct ByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size();
    }
};

int main() {
    std::set<std::string, ByLength> s;
    s.insert("cat");
    auto result = s.insert("dog");
    std::cout << result.second << ' ' << s.size();
}

Обе строки имеют длину три, поэтому вторая вставка не выполняется: выводом будет 0 1. Это не означает, что строки равны в обычном смысле; они эквивалентны только относительно выбранного порядка.

Компаратор должен быть транзитивным и непротиворечивым: порядок не должен меняться во время работы контейнера, а сравнения должны формировать согласованную структуру эквивалентных классов. Изменение ключа так, чтобы он перестал соответствовать своему месту в контейнере, также недопустимо; для изменения ключ обычно удаляют и вставляют заново.

Ситуация из практики

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

Нормализовать имя перед вставкой — например, привести его к единому регистру. Это упрощает сравнение и поиск, но исходное написание придётся хранить отдельно.
Использовать std::set с регистронезависимым компаратором. Исходное написание можно сохранить, однако все операции поиска и вставки будут определяться этим компаратором, а его корректность станет критичной.
Использовать std::unordered_set с согласованными хеш-функцией и сравнением. Это обычно даёт ожидаемую константную сложность поиска, но не сохраняет порядок элементов и требует корректной пары hash и key_equal.

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

Что кандидаты часто упускают

Совпадает ли эквивалентность в std::set с operator==?

Нет. std::set использует только свой компаратор. Два объекта могут быть неравны через operator==, но эквивалентны, если компаратор не различает их в обе стороны. И наоборот, равенство через operator== само по себе не гарантирует эквивалентность ключей для контейнера.

Что произойдёт, если компаратор сравнивает только часть состояния объекта?

Все объекты с одинаковым значением этой части станут эквивалентными, даже если остальные поля различаются. Это допустимо, если именно такое правило уникальности требуется. Однако нельзя затем ожидать, что std::set сохранит несколько таких объектов или найдёт их как различные элементы.

Почему опасен компаратор, результат которого зависит от внешнего изменяемого состояния?

Позиции элементов в упорядоченном контейнере строятся на основе прежних результатов сравнений. Если правило изменилось, дерево может перестать соответствовать своему порядку: поиск начнёт идти по неверным ветвям, а вставка и удаление могут работать некорректно. Компаратор должен оставаться согласованным на протяжении операций с контейнером; изменение критерия требует построить контейнер заново или перенести элементы в контейнер с новым компаратором.