std :: map Требования к ключам (проектное решение)

Question

Когда я делаю std::map<my_data_type, mapped_value>, C ++ ожидает от меня, что my_data_type имеет свои operator<.

struct my_data_type
{
    my_data_type(int i) : my_i(i) { }

    bool operator<(const my_data_type& other) const { return my_i < other.my_i; }

    int my_i;
};

Причина в том, что вы можете получить operator> и operator== с operator<. b подразумевает a> b , поэтому есть operator>.! (A означает, что a не меньше, чем b , и не больше его, поэтому они должны быть равны.

Вопрос в том, почему конструктор C ++ не требует явного определения operator==?Очевидно, что operator== неизбежно для std::map::find() и для удаления дубликатов из std::map.Зачем реализовывать 5 операций и дважды вызывать метод, чтобы не заставлять меня явно реализовывать operator==?

Answer 1

operator== неизбежно для std::map::find()

Это то место, где вы ошибаетесь. map вообще не использует operator==, это не «неизбежно». Две клавиши x и y считаются эквивалентными для целей карты, если !(x < y) && !(y < x).

map не знает или не заботится, внедрили ли вы operator==. Даже если это так, не обязательно, чтобы все эквивалентные ключи в заказе были равны согласно operator==.

Причина всего этого заключается в том, что везде, где С ++ опирается на порядки (сортировка, карты, множества, бинарный поиск), он основывает все, что он делает, на хорошо понятой математической концепции «строгого слабого порядка», которая также определяется в стандарте. Нет особой необходимости в operator==, и если вы посмотрите на код для этих стандартных функций, вы не очень часто будете видеть что-то вроде if (!(x < y) && !(y < x)), которое выполняет оба теста близко друг к другу.

Кроме того, все это не обязательно основано на operator<. Компаратором по умолчанию для map является std::less<KeyType>, который по умолчанию использует operator<. Но если вы специализировали std::less для KeyType, вам не нужно определять operator<, и если вы указываете другой компаратор для карты, то он может иметь или не иметь никакого отношения к operator< или std::less<KeyType>. Итак, где я сказал x < y выше, на самом деле это cmp(x,y), где cmp - строгий слабый порядок.

Эта гибкость - еще одна причина, почему бы не перетащить operator== в нее. Предположим, что KeyType равно std::string, и вы указываете свой собственный компаратор, который реализует какие-то правила сортировки, не зависящие от локали, без учета регистра. Если map использовал operator== некоторое время, то это полностью игнорировало бы тот факт, что строки, отличающиеся только регистром, должны считаться одним и тем же ключом (или в некоторых языках: с другими различиями, которые считаются несущественными для целей сопоставления). ). Таким образом, сравнение на равенство также должно быть настраиваемым, но будет только один «правильный» ответ, который может дать программист. Это не очень хорошая ситуация, вы никогда не хотите, чтобы ваш API предлагал что-то похожее на настройку, но на самом деле это не так.

Кроме того, концепция заключается в том, что, как только вы исключили участок дерева, который меньше, чем ключ, который вы ищете, и участок дерева, для которого ключ меньше, чем он, то остается либо пусто (совпадение не найдено) или есть ключ (совпадение найдено). Итак, вы уже использовали current < key, а затем key < current, не оставляя другого выбора, кроме эквивалентности. Ситуация точно:

if (search_key < current_element)
    go_left();
else if (current_element < search_key)
    go_right();
else
    declare_equivalent();

и вы предлагаете:

if (search_key < current_element)
    go_left();
else if (current_element < search_key)
    go_right();
else if (current_element == search_key)
    declare_equivalent();

что явно не нужно. На самом деле, это ваше предложение, которое менее эффективно!

Answer 2

Ваши предположения не верны.Вот что на самом деле происходит:

std::map - это шаблон класса, который принимает четыре параметра шаблона: тип ключа K, сопоставленный тип T, компаратор Comp и распределитель Alloc (имена не имеют значенияРазумеется, и только местный на этот ответ).Для этого обсуждения важно, что объект Comp comp; можно вызывать с двумя ключевыми ссылками, comp(k1, k2), где k1 и k2 равны K const &, и в результате получается логическое значение, которое подразумевает строгий слабое упорядочение .

Если вы не укажете третий аргумент, то Comp будет типом по умолчанию std::less<K>, и этот (без сохранения состояния) класс выполняет двоичную операцию как k1 < k2.Неважно, является ли этот < -оператор членом K, или бесплатной функцией, или шаблоном, или чем-то еще.

И это также завершает историю.Тип компаратора - это только данные, необходимые для реализации упорядоченной карты.Равенство равно , определено как !comp(a, b) && !comp(b,a), и карта хранит только один уникальный ключ в соответствии с этим определением равенства.

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

Хорошая библиотека предъявляет минимально необходимые требования и предлагает максимально возможную гибкость, и это именно то, что делает std::map.

Answer 3

Чтобы найти элемент i на карте, мы перешли к элементу e, поиск по дереву уже проверил i < e, что вернуло бы false.

Так что либо вы звоните i == e, либо вы звоните e < i, оба из которых подразумевают одно и то же, учитывая предварительное условие нахождения e в дереве. Поскольку у нас уже должен быть operator<, мы не полагаемся на operator==, так как это увеличит требования ключевой концепции.

Answer 4

У вас ошибочное предположение:

!(a < b) && !(b < a) означает, что a не меньше, чем b, и не больше его, поэтому они должны быть равны.

Itозначает, что они эквивалентны , но необязательно равны .Вы можете реализовать operator< и operator== таким образом, что два объекта могут быть эквивалентными, но не равными.

Почему конструктор C ++ не требует явного определения operator==?

Чтобы упростить реализацию типов, которые можно использовать в качестве ключей, и позволить использовать один собственный компаратор для типов без перегруженных операторов.Единственное требование - предоставить компаратор (либо operator<, либо пользовательский функтор), который определяет частичное упорядочение.Ваше предложение потребует как дополнительной работы по выполнению сравнения на равенство, так и дополнительного ограничения на требование эквивалентных объектов для сравнения равных.

Answer 5

Причина, по которой нужен оператор сравнения, заключается в том, как реализована карта: как двоичное дерево поиска , которое позволяет вам искать, вставлять и удалять элементы в O(log n).Чтобы построить это дерево, для набора ключей должен быть определен строгий слабый порядок .Вот почему требуется только одно определение оператора.