Порада 19
Порада 19. Пам'ятайте про відмінності між рівністю та еквівалентністю
Алгоритм find і функція set::insert є типовими представниками сімейства функцій, які перевіряють збіг двох величин, але роблять це по-різному. Для find збігом вважається рівність двох величин, що перевіряється оператором =. Функція set:: insert перевіряє ставлення еквівалентності, зазвичай засноване на операторі true, отже, х і мають однакові значення, і якщо false — різні. У цілому визначення дуже прямолінійне, хоча слід пам'ятати про те, що з рівності значень не слід рівність всіх полів даних. Припустимо, клас Widget зберігає внутрішні дані про час останнього звернення:
Для класу Widget можна визначити оператор ==, що ігнорує значення поля:
bool operator=(const Widgets Ihs, const Widgets rhs)
// Поле lastAccessed ігнорується
У цьому випадку два об'єкти Widget будуть вважатися рівними навіть у тому випадку, якщо їхні поля в останнійAccessed містять різні значення.
Еквівалентність ґрунтується на відносному порядку значень об'єктів у відсортованому інтервалі. Найпростіше розглядати її у контексті порядку сортування, що є частиною будь-якого стандартного асоціативного контейнера (тобто set, multiset, map та multimap). Два об'єкти х і у вважаються еквівалентними по відношенню до порядку сортування, використовуваного асоціативним контейнером, якщо жоден з них не передує іншому в порядку сортування с. На перший погляд таке формулювання здається заплутаним, але на практиці все просто. Візьмемо контейнер set s. Два об'єкти Widge t, w1 і w2 мають еквівалентні значення по відношенню до s, якщо жоден з них не передує іншому в порядку сортування s. Стандартна функція порівняння для set t> - Less - позамовчуванням просто викликає operator для об'єктів Widge t, тому wl і w2 будуть мати значення, еквівалентні по відношенню до operator якщо істинно такий вираз:
Все цілком логічно: два значення еквівалентні (стосовно деякого критерію впорядкування), якщо жодне з них не передує іншому відповідно до даного критерію.
У загальному випадку функцією порівняння для асоціативного контейнера є не оператор key_comp тому два об'єкти х і у мають еквівалентні значення по відношенню до критерію сортування асоціативного контейнера с, якщо виконується наступна умова:
!c.key_comp()(x.y) && !c.key_comp()(y,x) // x не передує у
// У порядку сортування,
// а у не передує х
Вираз !c.key_comp()(x,y) виглядає жахливо, але варто зрозуміти, що c.key_comp() повертає функцію (або об'єкт функції), як усі труднощі зникають. Перед нами простий виклик функції (або об'єкта функції), що повертається key_comp , якій передаються аргументи х і у. Потім обчислюється логічне заперечення результату. Функція с.keycomp ()(х, у) повертає true тільки в тому випадку, якщо х передує у порядку сортування, тому вираз !с.key_comp()(х, у) істинно тільки в тому випадку, якщо х не передує у у порядку сортування с.
Щоб краще усвідомили принциповий характер відмінностей між рівністю і еквівалентністю, розглянемо приклад — контейнер set без урахування регістру символів, тобто контейнер set , у якому функція порівняння ігнорує регістр символів у рядках. З погляду такої функції рядки "STL" і "stL" еквівалентні. Приклад реалізації функції ciStringCompare, що ігнорує регістр символів, наведено в раді 35, проте набір потрібен тип функції порівняння, а не сама функція. Щобзаповнити цю прогалину, ми пишемо клас функтора з оператором (), що викликає ciStringCompare:
struct CiStringCompare:// Клас порівняння рядків
public// без урахування регістру символів;
// наведено у раді 40
bool operator() (const string&lh
const string& rhs) const
return ciStringCompare(lhs,rhs); // Реалізація ciStringCompare
// наведено у раді 35
За наявності CiStringCompare контейнер set, що ігнорує регістр символів, створюється дуже просто:
Тепер при вставці рядків «Persephone» і «persephone» до множини буде включено лише перший рядок, оскільки другий вважається еквівалентним:
ciss.insert("Persephone"); // До множини включається новий елемент
ciss.insert("persephone"); // Еквівалентний елемент не включається
Якщо тепер провести пошук рядка "persephone" функцією set::find, результат буде успішним:
if(ciss.find("persephone")! = ciss.end()). // Елемент знайдено
Але якщо скористатися зовнішнім алгоритмом find, пошук завершується невдачею:
"persephone")! = ciss.end ()). // Елемент відсутній
Справа в тому, що рядок "persephone" еквівалентна "Persephone" (по відношенню до функтора порівняння CIStringCompare), але не дорівнює їй (оскільки string ("persephone")! = string ("Persephone")). Наведений приклад пояснює одну з причин, з якої відповідно до поради 44 рекомендується використовувати функції контейнерів (set:: find) замість зовнішніх аналогів (find).
Постає питання — чому ж у роботі стандартних асоціативних контейнерів використовується поняття еквівалентності, а чи не рівності? Адже більшості програмістів рівність здається інтуїтивно більш зрозумілою, ніж еквівалентність (інакше ця порада була б зайвою). наперший погляд відповідь здається простою, але чим довше розмірковуєш над цим питанням, тим менш очевидним він стає.
Стандартні асоціативні контейнери сортуються, тому кожен контейнер повинен мати функцію порівняння (за умовчанням less), що визначає порядок сортування. Еквівалентність визначається контексті функції порівняння, тому клієнтам стандартних асоціативних контейнерів залишається лише задати єдину функцію порівняння. Якби асоціативні контейнери при порівнянні об'єктів використовували критерій рівності, то кожному асоціативному контейнеру, крім використовуваної при сортуванні функції порівняння, довелося б визначати другу функцію перевірки рівності. Ймовірно, за умовчанням функція порівняння викликала б equal_to, але цікаво помітити, що функція equal_to STL не використовується як стандартна функція порівняння. Коли STL виникає необхідність перевірки рівності, за замовчуванням просто викликається оператор =. Зокрема, саме так чинить зовнішній алгоритм find.
Контейнер s здійснює внутрішнє сортування рядків без урахування регістру, але з використанням інтуїтивного критерію рівності: два рядки вважаються рівними при збігу їхнього вмісту. Припустимо, в s вставляються два варіанти написання рядка «Persephone»:
Як вчинити у цьому випадку? Якщо контейнер зрозуміє, що "Persephone" != "persephone", і вставить обидва рядки s, в якому порядку вони повинні слідувати?
Нагадаю, що функція сортування ці рядки не розрізняє. Чи слід вставити рядки у довільному порядку, добровільно відмовившись від детермінованого порядку перебору вмісту контейнера? Недетермінований порядок перебору вже притаманний асоціативним контейнерам multiset та multimap, оскільки Стандарт не встановлює жодних обмеженьна відносний порядок проходження еквівалентних значень (multiset) або ключів (multimap). Чи слід нам наполягти на детермінованому порядку вмісту s і проігнорувати другу спробу вставки (для рядка «persephone»)? А якщо буде обрано цей варіант, що відбудеться при виконанні наступної команди:
if (s.find("persephone")! = s.end()). // Яким буде результат перевірки?
Функція find використовує перевірку рівності, але якщо проігнорувати другий виклик insert для збереження детермінованого порядку елементів s, перевірка дасть негативний результат - хоча рядок "persephone" був відкинутий як дублікат!
Мораль: використовуючи одну функцію порівняння та приймаючи рішення про «збіг» двох значень на підставі їхньої еквівалентності, ми уникаємо численних труднощів, що виникають при використанні двох функцій порівняння. Спочатку такий підхід виглядає дещо дивно (особливо коли ви бачите, що внутрішня та зовнішня версії find повертають різні результати), але в перспективі він позбавляє всіляких труднощів, що виникають при змішаному використанні рівності та еквівалентності у стандартних асоціативних контейнерах.
Але варто відійти від сортованих асоціативних контейнерів, як ситуація змінюється, і проблему рівності та еквівалентності доводиться вирішувати наново. Існують дві загальноприйняті реалізації для нестандартних (але широко поширених) асоціативних контейнерів на базі хеш-таблиць. Одна реалізація полягає в рівності, іншу — на еквівалентності. У раді 25 наводиться додаткова інформація про ці контейнери і ті принципи, на яких вони засновані.