[БЕЗ_ЗВУКА] Здравствуйте! На этом занятии мы с вами разберём, как помещать свои собственные типы данных в ассоциативные контейнеры. Для этого напишем какой-нибудь свой собственный тип данных, например структуру Plate, которая будет описывать автомобильный номер, который мы использовали в прошлых занятиях, и поместим его в ассоциативный контейнер, как мы и собирались. Напишем код. Напишем структуру Plate, которую мы с вами обсудили только что на слайде. Она будет содержать буквы с автомобильного номера, центральное число и код региона. И напишем сразу для этой структуры оператор помещения в поток, для того чтобы мы могли распечатывать эти автомобильные номера. Что мы с вами хотим сделать дальше? Мы хотим завести ассоциативный контейнер set и складывать в него эти автомобильные номера. Для того чтобы генерировать номера какие-нибудь случайные, а не придумывать их, мы написали генератор этих случайных чисел. Давайте посмотрим, как он устроен. В этом генераторе у нас имеется функция GetRandomPlate, которая возвращает некий случайный автомобильный номер, и описаны буквы — 12 букв - которые могут использоваться в автомобильных номерах. И эта функция возвращает, комбинируя эти буквы с цифрами, какой-то номер. Удобно. Давайте с вами сейчас вообще проверим, что это работает, то что мы сейчас сказали, что мы нигде не ошиблись. Для этого возьмём и распечатаем какой-нибудь случайный номер. Собираем программу, она выполняется успешно. Мы видим, что она напечатала какой-то автомобильный номер, то есть всё идёт по плану. В номере есть буква, число, две буквы, число — все отлично. Возвращаемся к нашему первоначальному плану. Возьмём 10 случайных автомобильных номеров и поместим их в контейнер set. Так, здесь мы чуть-чуть переделаем - вместо вывода на экран вместо вывода на экран будем помещать в контейнер. Компилируем программу — она не компилируется, сообщает нам об ошибке. Давайте разберёмся, что это за ошибка. Компилятор говорит нам, что у нас не хватает оператора сравнения < . Зачем же нам нужен этот оператор, если мы просто хотим поместить номера в контейнер? Для ответа на этот вопрос можем вспомнить слайды с наших предыдущих занятий. Вот наш контейнер set устроен внутри как двоичное дерево поиска. И элементы в этом двоичном дереве поиске упорядочены. Слева находятся меньшие, справа — большие. То есть на самом деле для построения двоичного дерева нам необходим оператор < , потому что нужно уметь сравнивать номера друг с другом. Раз нужно, то нужно. Давайте напишем этот самый оператор < . Напишем его прямо здесь там где у нас опеределена структура Plate. Вот у нас есть два номера, левый и правый. Мы хотим сравнить их друг с другом. Как мы их сравним? Наверное, в лексикографическом порядке, чтобы они у нас были отсортированы по алфавиту. Для этого нам нужно сначала сравнить первую букву: если первые буквы равны, то сравниваем центральное число, если центральные числа тоже равны, сравниваем оставшиеся буквы и код региона. Для того чтобы сравнить этот набор в нужном нам порядке, можно воспользоваться тапплами, а именно вызвать функцию tie из библиотеки, которая свяжет перечисленные поля в нужном нам порядке. И сравнить их с тем же набором тапплов из правого автомобильного номера. И такое вот у нас получится простой оператор < . Попробуем запустить программу с ним. Собираем. Что же у нас программа собралась успешно, получается, 10 автомобильных номеров попадут в контейнер. И давайте просто после этого распечатаем их — посмотрим, что в нём содержится. [ШУМ] [ШУМ] Так, собираем нашу программу, выполняем её. Мы видим 10 автомобильных номеров — мы на верном пути. И похоже, что они даже распечатаны в нужном нам порядке. Эти 10 номеров мы положили в контейнер, после этого они стали упорядочены по алфавиту. Именно так мы их видим. Первая буква у них отличается и возрастает. И даже там, где первая буква равна, номер всё равно отсортирован по возрастанию. Прекрасно! С set мы справились, давайте двигаться дальше. Решим ту же самую задачу для unordered_set. [ШУМ] Мы заводим unordered_set, в котором лежат наши автомобильные номера. И проделаем для него ровно те же операции. Мы поместим туда случайные автомобильные номера и затем распечатаем. У нас снова сообщение об ошибках от компилятора. О чём они нам говорят? Ошибка говорит о том, что у нас не хватает чего-то, связанного с хешированием. И это не удивительно, потому что, как мы помним с прошлых занятий, контейнер unordered_set представляет собой хеш-таблицу. И для того чтобы поместить туда новый элемент, нам для этого элемента нужно посчитать индекс корзины, в которую он будет помещён с помощью хеш-функций. Эту хеш-функцию никто не написал. Так давайте же её напишем. Напишем её, как мы её оформим... Это будет какая-то структура, которая будет называться Hasher. И она должна содержать в себе оператор (), который будет вызван. Это и будет наша хеш-функция. Хеш-функция должна возвращать тип size_t. Это будет номер корзины, и принимать на вход автомобильный номер. Вот такая будет сигнатура фукнции. Что мы хотим вернуть? Мы хотим вернуть какое-то число, которое будет характеризовать наш номер, который будет являться индексом для этого автомобильного номера. Сделаем так же, как на слайдах, то есть вернём центральное число этого автомобильного номера — так, как мы с вами уже сделали на примерах. Так, мы что-то забыли сделать, потому что IDE нам подсказывает, что структура PlateHasher написа серым цветом. То есть она нигде не используется - нам нужно её использовать. Давайте это сделаем. Использовать её нужно прямо там, где мы объявляем контейнер unordered_set. И указать наш хешер вторым параметром, вторым шаблонным параметром. Теперь выглядит лучше, давайте соберем. Мы продвигаемся с вами успешно, потому что сейчас компилятор нам сообщает уже о другой ошибке компиляции — он говорит, что у нас не хватает оператора сравнения. А зачем нам нужен оператор сравнения, если мы хотим просто поместить элемент в хеш-таблицу? Конечно же, он нужен, потому что, как мы с вами помним из прошлых занятий, при поиске элементов в хеш-таблицу, каждый элемент сравнивается с теми, которые уже находятся в корзине, просто по порядку перебирая их. И поэтому нам, действительно, нужен оператор == , который позволит выполнять такое сравнение. Он нам нужен, поэтому давайте его напишем. Он будет устроен очень просто, потому что мы с вами понимаем, когда равны два автомобильных номера - они равны тогда, когда все поля попарно равны друг другу. Буквы равны буквам, номер равен номеру, и регион равен региону. Никаких вопросов не вызывает такая реализация. Сейчас мы смогли с вами успешно скомпилировать эту программу, и давайте её запустим. Что мы видим в итоге? У нас вывелось 2 раза по 10 автомобильных номеров: первые 10 номеров у нас из контейнера set, и они упорядочены по алфавиту. Вторые 10 номеров — из контейнера unordered_set, они уже не упорядочены по алфавиту, потому что они и не должны быть упорядочены. Они написаны в каком-то произвольном порядке. Но самое главное, что это работает, что мы смогли поместить наш собственный тип в unordered_set. И он прекрасно себя чувствует в ней. Таким образом, на этом занятии мы с вами узнали, как помещать свои типы данных в ассоциативные контейнеры. И если мы хотим поместить свой тип в map или set, мы должны написать для него оператор сравнения < . А если мы хотим поместить свой тип в unordered_set или в unordered_map, мы должны написать, во-первых, функцию хеширования для своего типа, а во-вторых, оператор сравнения == .
