С++, std::map пакости неосведомлённым. Немного об опасностях

Во время использования map новички или неопытные программисты могут столкнуться с некоторыми трудностями.

Для понимания темы необходимо знать:

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

Затруднение может возникнуть при использовании своего класса (class, struct) в качестве ключа.
  • Чтобы использовать свой класс (class, struct) в качестве ключа — необходимо сделать так, чтобы данные класса могли сравниваться между собой.
По умолчанию для map определена операция сравнения <, которая перегружена во многих классах STL и доступна неклассовым типам, поэтому не требует своего явного написания, но как только дело касается собственных наших типов, то по умолчанию собственные наши типы не умеют сравнивать собственные элементы между собой, поэтому в качестве ключа наш тип должен или иметь встроенную функцию сравнения собственных данных, или быть связан внешней функцией сравнения (см. тему перегрузка операций).
Я пока что часто встречал внешнюю подгрузку операции сравнения. Внешняя используется, когда есть класс, который либо невозможно переписать, либо не имеет смысла дописывать, а в нём не предполагается операций сравнения. С такой подгрузкой видной проблемы нет (на самом деле есть (точнее, может возникнуть), но об этом позднее).
Небольшая проблема может возникнуть с написанием класса под map, когда используется встроенная операция сравнения. Во-первых — это должна быть операция <, а во вторых, у map ключи константные. С константностью ключей вообще связано несколько сложностей у новичков (например, некоторые пытаются отсортировать данные структуры по ключам, но ключи в map невозможно перезаписать, т. е. нельзя их поменять местами).
Если в #2.2 сделать метод неконстантным (убрать const), то код просто не скомпилируется.
Основная проблема, которая сейчас возникла — это то, что наш map воспринимает структуры, что мы пытаемся вставить в качестве ключей, как эквивалентные, хоть среди этих структур (t1, t2, t3) нет ни одной одинаковой. Такой момент действительно может удивить неопытного человека. Дело в том, что на ключи map наложены ограничения: операция сравнения должна обеспечивать строгое сравнение (strict weak ordering), в противном случае ключи будут восприниматься как эквивалентные. А поскольку map — структура, предполагающая уникальные ключи, то любые значения ключей, воспринимаемых как эквивалентные, добавлены не будут. Кроме того, может даже произойти ub.
  • При нарушении обеспечения строгого сравнения (strict weak ordering) поведение программы не определено (ub)
Что такое strict weak ordering? — это математический термин для определения отношений между двумя объектами. Его определение таково:
  • Два объекта x и y эквивалентны, если оба сравнения f(x, y) и f(y, x) являются ложными. Обратите внимание, что объект всегда (инвариантен по нерефлексивности) эквивалентен самому себе.
Не каждый поймёт такое определение... Поэтому имейте в виду, что наша самодельная операция сравнения должна обладать такими вот свойствами:
  • Два ключа не могут быть меньше друг друга.
  • При (k1 < k2) && (k2 < k3) должно быть гарантировано, что (k1 < k3).
  • Если есть два ключа и ни один из них не меньше другого, то ключи эквиваленты. При (k1 eq k2) && (k2 eq k3) должно быть гарантировано, что (k1 eq k3).
Во вторых листингах (#2.1, #2.2) получается, что сравниваемые элементы взаимно меньше друг друга, поэтому вставляемые ключи считаются эквивалентными, отсюда и происходит ошибка:
Сначала в map вставляется первый ключ, поскольку нет никаких других ключей. После этого по ключам ищется позиция вставки. Для поиска позиции используется операция сравнения. Если мы взаимно сравним первые две структуры: {1, 2, 3} < {3, 2, 1}? То получим следующий результат:
(1 < 3) && (2 < 2) && (3 < 1) ==> false;
(3 < 1) && (2 < 2) && (1 < 3) ==> false;
Если вы хоть немного дружите с логикой, то можете видеть, что результат сравнения на больше и на меньше одинаковый, что само по себе довольно странное обстоятельство.
  • Один из наиболее простых способов быстро определять эквивалентность — это использование формулы !cmp(a, b) && !cmp(b, a): если результат её true, то эквивалентность есть. Здесь cmp — это функция сравнения.
  • Для того, чтобы коректно вставлять ключи при групповых сравнениях, необходимо использовать лексикографическое сравнение. Для групповых сравнений можно использовать кортежи tuple.
Проще использовать кортежи. С ними код получается более лакончиный. Примеры взяты с форума. Чем больше внутренних переменных к сравнению, тем очевиднее, что кортежи удобны.

Остальные проблемы имеют мелкий масштаб, но могут иметь значение. Например, к map обычно не применяются обобщённые алгоритмы. Так, попытка использовать sort приведёт к ошибке компиляции:
Дело в том, что sort пытается перезаписать константные ключи. Но кроме того сама операция сортировки для map не имеет смысла.
При этом часть обобщённых алгоритмов, не посягающая на изменение ключей map и не специфическая для каких-то других структур данных — с map работать умеет.
  • К ассоциативным контейнерам применимы только такие обобщённые алгоритмы, которые читают элементы (алгоритм поиска, алгоритм копирования и др.).
С листингом #4.1 связана одна важная техническая формальность: значения для map — это не значения second из пары, а непосредственно сами пары, а значения second лучше называть как-то иначе: вторичные значения, поля second, значения second — так вас легче поймут опытные товарищи, если возникнут трудности.
Вы часто можете слышать, что есть алгоритмы общие и есть встроенные в класс, что встроенные в класс оптимизированы для работы конкретными классами. Это можно легко принять, но иногда, особенно в начале пути, сложно понять, как это работает. На примере map можно показать один из примеров: есть обобщённый алгоритм find и встроенный в map.
В листинге #6.1 пришлось немного помочь разобраться нашему классу, как должны сравниваться элементы. Алгоритм поиска использует операцию сравнения, и, если класс не умеет выполнять сравнение, то для использования алгоритма классу нужно показать, как надо элементы сравнивать, что и было проделано. Минус использованного алгоритма в том, что при использовании обобщённого find (использован первым) все ключи перебираются последовательно, когда сама структура map — это такая структура, которая организована для эффективного, именно что для непоследовательного перебора. Встроенная функция поиска (использована второй) ищет элементы не последовательно, а специальным алгоритмом обхода map. Обычно map строятся на красно-черных деревьях, но могут быть и другие фундаменты, и для любого из способов организации map встроенная функция обхода практически всегда будет означать, что часть элементов затронута не будет (сработает во всех смыслах как молния), а это скорость работы.
Так уж вышло, что в #6.1 пришлось написать аж две перегрузки: первая перегрузка сравнивает пару pair<Test, int> и наш написанный класс Test, а вторая перегрузка, поверх этой, сравнивает объекты Test между собой.
  • Если есть два однотипных алгоритма: обобщённый и встроенный в объект, выбирайте всегда встроенный — встроенные алгоритмы, как правило, производительнее и умеют управлять памятью
Вообще, последнее касается не только map, но и вообще любых структур данных. Ведь если в структуру встроен какой-то алгоритм, то встроен он не просто так. Такой алгоритм знает структуру изнутри, поэтому обычно и эффективнее.

Ещё один из не сложных, но не очень понятных моментов связан с тем, что если обращаться к не существующему ключу key, то может создаваться видимость, что ключ существует:
Это может вызывать недоумение, из-за этого могут возникать ошибки. Но почему так происходит? Дело в том, что алгоритм find, выполняя обход, достигает позиции m.end(), а на этой позиции лежит какое-то мусорное значение, которое и получается вытащить. Мы разыменовываем мусорную область памяти — это ub.
Чтобы этого избегать, при использовании find нужно всегда выполнять проверку, что не была достигнута конечная позиция. Для этого зачастую удобно использовать итераторы.
  • Предпочитайте итераторы циклам.

Ещё один из нюансов работы с map связан с использованием операции индексирования (квадратные скобки). Совсем новичкам может казаться очень удобно использовать операцию индексирования всегда, но использование квадратных скобок черевато тем, что в map могут добавляться пары, не предназначенные для вставки, т. е. могут возникнуть разные сложности: может не скомпилироваться код, map может резко разбухнуть на пустом месте, можно словить неправильные результаты:
В листинге #8.2 есть массив слов (например, это фильтруемый слова) и общий массив слов. Программой выполняется подсчёт в общем массиве количества фильтруемых слов
В некотором смысле это упущение может напоминать утечку памяти. Но подобная неосмотрительность может влиять не только на память, но и на результаты работы программы:
Подобное #8.3 легко может написать новичок, не понимающий итераторов. Насколько помню себя, в первую пору я итераторов избегал, но использование итераторов уберегает от возникновения таких проблем, как в #8.2 и в #8.3. Понимание того, что операция индексации для map записывающая, может помочь избежать нелепых ошибок. В тех случаях, когда не нужно изменять map, следует использовать вместо операции [] встроенный в map алгоритм find.
  • Операция [], применяемая к map, не только ищет значение, но и вставляет его, если его в map нет.
  • Если map не должен дополняться несуществующими ключами, для поиска значения используйте встроенный в map алгоритм find
  • Активно используйте итераторы.
Чтобы исправить #8.2, нужно использовать итераторы и алгоритм find:
Уникализация не то, чтобы обязательна, просто у меня в arr два раза встречается "dwa", вот чтобы исключить поиск того, что уже искали, массив был мной уникализирован.
Листинг #8.3 можно легко исправить, если делать обход итераторами:

Добавить комментарий

Ваш адрес email не будет опубликован.

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/oleg-zelenyak/praktikum-programmirovaniya-na-turbo-pascal-zadachi-algoritmy-i-resheniya/?lfrom=15589587
Яндекс.Метрика