Контракти ключів: operator< для map, hash + == для unordered_map

1. std::map: ключ у світі порядку

Уявіть, що контейнер — це бібліотекар. Ви приходите й кажете: «Знайдіть мені книжку за назвою». Бібліотекар запитує: «А як порівнювати назви? За абеткою? Без урахування регістру? За довжиною рядка?» Якщо правило не визначене, він може почати шукати книжку… за кольором обкладинки. І формально він не винен: ви не домовилися про правила.

У C++ асоціативні контейнери працюють майже так само: вони можуть бути дуже швидкими, але лише тоді, коли ви задаєте їм чіткий контракт ключа — правило, за яким контейнер визначає, «це той самий ключ» чи ні, і вирішує, куди його покласти. У стандарті навіть є формулювання на кшталт «контейнер відсортований відносно comp» — тобто саме компаратор задає порядок.

Дві родини контейнерів вимагають різних «домовленостей»:

• std::map (і std::set) вимагають правила порядку: зазвичай через operator< або компаратор.
• std::unordered_map (і std::unordered_set) вимагають рівності та хешу: == і hash() (плюс їхню узгодженість).

map використовує компаратор, а не ==

Коли ви вперше бачите std::map, легко подумати: «А, це словник, отже порівняння ключів — це ==». Але map влаштований інакше: він упорядкований. Це означає, що контейнер підтримує структуру даних (логічно — дерево), яка постійно тримає ключі «в порядку», щоб швидко знаходити елементи.

Тут важливо розуміти таке: std::map за замовчуванням використовує std::less<Key>, а для більшості звичайних типів std::less<Key> просто викликає operator<. Тому, коли ми говоримо «контракт ключа map», то майже завжди маємо на увазі таке: для ключа має бути коректно визначене строге порівняння «менше».

Спрощена картинка може бути такою:

flowchart TD
    A[Ключ] --> B{"comp(a,b)?"}
    B -->|так| L[a йде лівіше за b]
    B -->|ні| R[a не йде лівіше за b]

Фраза «контейнер відсортований відносно comp» — саме про це правило.

Що map вважає «однаковими ключами»

Ось момент, який часто ламає звичне уявлення: map може взагалі не використовувати operator==. Він вирішує, «однакові ключі чи ні», саме через компаратор.

Інтуїтивне правило таке: два ключі вважаються еквівалентними, якщо жоден не є «меншим» за інший за компаратором. Тобто:

• a не менше за b
• і b не менше за a

Простими словами це означає так: «компаратор не зміг розставити їх у порядку, отже для контейнера вони однакові».

Це дає дуже практичний ефект: якщо ваш компаратор порівнює лише частину полів, map почне «склеювати» різні ключі в один. І контейнер буде абсолютно впевнений, що має рацію: ви самі задали таке правило.

Мініприклад: телефонна книга на map

Продовжімо наш навчальний мініпроєкт. Нехай у нас є проста «телефонна книга», і ми хочемо зберігати контакти за імʼям. Для map ключем буде std::string, у якого вже є коректний operator<.

#include <iostream>
#include <map>
#include <string>

struct Contact {
    std::string phone;
};

int main() {
    std::map<std::string, Contact> book;

    book.emplace("Ann", Contact{"111-11"});
    book.emplace("Bob", Contact{"222-22"});

    for (const auto& [name, c] : book) {
        std::cout << name << ": " << c.phone << '\n';
        // Ann: 111-11
        // Bob: 222-22
    }
}

Тут контейнер сам підтримує порядок ключів, і обхід виходить «відсортованим за імʼям». І це не просто «приємний бонус», а фундаментальна частина контракту map: він зберігає елементи впорядковано відносно компаратора.

Пастка: компаратор через <=

Дуже хочеться написати компаратор як «не пізніше» (<=) або «не більше». Логіка здається залізобетонною: якщо a <= b, то a раніше за b. Але компаратор у map має відповідати на інше запитання: «строго раніше?».

Якщо використовувати <=, ви ламаєте «строгість». У результаті компаратор може сказати, що a «раніше» a (адже a <= a — істинно). Це руйнує внутрішні очікування контейнера: він розраховує на те, що ключ не менший за самого себе.

Покажемо правильний стиль на простому компараторі «за довжиною рядка», де строгість легко побачити:

#include <map>
#include <string>

struct ByLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.size() < b.size(); // строге <
    }
};

int main() {
    std::map<std::string, int, ByLength> m;
    m["cat"] = 1;
    m["lion"] = 2;
}

Так, це дивний порядок — за довжиною, але він строгий: рядок не є «меншим» за самого себе, і контейнеру від цього спокійніше.

Пастка: «склейка» ключів через неповне порівняння

Тепер зробімо приклад ближчим до реальності. Контакт у нас може мати прізвище та імʼя. І ми хочемо зберігати людей за парою (прізвище, імʼя). Якщо порівнювати лише прізвище, то дві різні людини з однаковим прізвищем стануть «одним ключем» для map.

#include <iostream>
#include <map>
#include <string>

struct PersonKey {
    std::string last;
    std::string first;
};

struct ByLastOnly {
    bool operator()(const PersonKey& a, const PersonKey& b) const {
        return a.last < b.last; // поле first ігноруємо
    }
};

int main() {
    std::map<PersonKey, int, ByLastOnly> ids;

    ids.emplace(PersonKey{"Smith", "Ann"}, 1);
    ids.emplace(PersonKey{"Smith", "Bob"}, 2);

    std::cout << ids.size() << '\n'; // 1 (і це не «баг map», а ваш контракт)
}

Контейнер зробив рівно те, що ви йому дозволили: за вашим правилом усі "Smith" еквівалентні. На побутовому рівні це схоже на ситуацію: «у картотеці сортуємо людей лише за прізвищем, а імʼя взагалі не записуємо». Так, пошук буде швидким. Але користуватися таким індексом буде… сміливо.

2. std::unordered_map: ключ у світі хешу та рівності

Як unordered_map шукає елементи

Тепер переходимо до другої родини контейнерів. std::unordered_map не обіцяє порядку. Він обіцяє інше: «я швидко знайду значення за ключем, використовуючи хешування».

Спрощена картинка:

flowchart TD
    K[Ключ] --> H["hash(key)"]
    H --> B[кошик (bucket)]
    B --> C{перевірка: key == candidate}
    C -->|так| F[знайшли значення]
    C -->|ні| N[шукаємо далі в кошику]

Тобто unordered_map спочатку обчислює число (хеш), за ним обирає «кошик», а потім уже порівнює ключі на рівність, щоб відрізнити колізії.

У стандарті окремо підкреслено, що у unordered_* є вимоги до обʼєктів Hash і Pred (предиката рівності). Навіть якщо вам не важливі формальні формулювання, сам факт корисний: це справді контракт, а не «як пощастить».

Головний закон: якщо a == b, то hash(a) зобовʼязаний дорівнювати hash(b)

Сформулюймо найважливіше правило ключа для unordered_map так, щоб його можна було повісити на стіну (поруч із «не пишіть using namespace std; у заголовку», але це буде пізніше).

Якщо два ключі вважаються рівними (a == b), то їхні хеші зобовʼязані збігатися: hash(a) == hash(b).

Чому так строго? Тому що контейнер спочатку йде в кошик за hash(a). Якщо b дорівнює a, але має інший хеш, то b опиниться в іншому кошику. І тоді пошук за ключем a може не знайти b, хоча «за змістом» це той самий ключ. Тобто контейнер стає логічно некоректним.

Колізії (коли a != b, але hash(a) == hash(b)) дозволені й цілком нормальні. Контейнер потім розрізнить їх за допомогою ==. А от зворотна ситуація — рівні ключі, але різні хеші — ламає базову механіку.

Мініприклад: телефонна книга за id на unordered_map

Повернімося до нашого застосунку. Припустімо, у контакту є числовий id. Для int уже є std::hash<int> і коректний operator==, тому такий ключ ідеально підходить для unordered_map.

#include <iostream>
#include <string>
#include <unordered_map>

struct Contact {
    int id{};
    std::string name;
    std::string phone;
};

int main() {
    std::unordered_map<int, Contact> book;

    book.emplace(1, Contact{1, "Ann", "111-11"});
    book.emplace(2, Contact{2, "Bob", "222-22"});

    if (auto it = book.find(2); it != book.end()) {
        std::cout << it->second.name << '\n'; // Bob
    }
}

Зверніть увагу: тут ключ — int, і ми не змушуємо контейнер нічого сортувати. Тому обхід у unordered_map не варто сприймати як «упорядкований список» (сьогодні він такий, завтра — інший). Зате пошук за ключем дуже прямолінійний: «дай контакт за id».

Колізії: однаковий хеш — не кінець світу

Слово «колізія» звучить так, ніби зараз буде вибух сервера й сумний адміністратор у кутку. Насправді колізія — це нормально: різні ключі можуть мати однаковий хеш. Контейнер після потрапляння в кошик однаково перевіряє ==.

Щоб побачити це на практиці, можна навмисно створити поганий хешер, який завжди повертає 0. Це буде жахливо з погляду швидкості, але коректно за змістом: усі елементи потраплять в один кошик, а розрізняти їх буде ==.

#include <iostream>
#include <string>
#include <unordered_map>

struct AlwaysZeroHash {
    std::size_t operator()(const std::string&) const {
        return 0;
    }
};

int main() {
    std::unordered_map<std::string, int, AlwaysZeroHash> cnt;

    cnt["apple"] += 1;
    cnt["banana"] += 1;

    std::cout << cnt["apple"] << '\n';  // 1
    std::cout << cnt["banana"] << '\n'; // 1
}

Так робити в реальному коді не треба (хіба що ви пишете підручник зі страждань), але цей приклад добре показує логіку: колізії допустимі, бо фінальне рішення ухвалює ==.

Підступна помилка: змінили рівність, забули змінити хеш

Зараз буде ситуація, яка на практиці ламає проєкти частіше, ніж друкарська помилка в імені змінної. Припустімо, ви вирішили, що ключі-рядки потрібно порівнювати без урахування регістру: "Ann" і "ann" — це той самий користувач.

У unordered_map це можливо: можна передати власний KeyEqual (предикат рівності). Але контракт вимагає узгодженості: якщо "Ann" і "ann" рівні за вашим KeyEqual, то й хеш має бути однаковим. Інакше контейнер почне «не знаходити» те, що «за змістом» у ньому є.

Покажемо погану версію: рівність без урахування регістру, а хеш — звичайний, залежний від регістру. Це приклад того, як порушується контракт.

#include <cctype>
#include <string>
#include <unordered_map>

struct CaseInsensitiveEq {
    bool operator()(const std::string& a, const std::string& b) const {
        if (a.size() != b.size()) return false;
        for (std::size_t i = 0; i < a.size(); ++i) {
            if (std::tolower((unsigned char)a[i]) != std::tolower((unsigned char)b[i]))
                return false;
        }
        return true;
    }
};

int main() {
    // Хеш залишився стандартним (залежним від регістру) — контракт порушено.
    std::unordered_map<std::string, int, std::hash<std::string>, CaseInsensitiveEq> m;

    m.emplace("Ann", 10);

    // У реальності такий код може почати поводитися «дивно»:
    // find("ann") може не знайти "Ann", хоча CaseInsensitiveEq вважає їх рівними.
}

Важливий момент: я спеціально не показую, як правильно зробити хеш без урахування регістру, бо це вже тема наступної лекції про користувацькі ключі та std::hash<Key>. Сьогодні вам важливо винести головне: у unordered_map рівність і хеш зобовʼязані дивитися на ключ однаковими очима. Вимоги до Hash і Pred — частина контракту контейнера.

3. Як вибрати: map чи unordered_map

Коли ви обираєте контейнер, корисно думати не «що швидше у вакуумі», а «який контракт простіший і природніший для мого ключа». Іноді порядок вам справді потрібен: наприклад, ви хочете друкувати контакти за абеткою без окремого сортування. Іноді порядок не важливий, і вам потрібен просто швидкий пошук за id.

Ось таблиця, яка допомагає ухвалити рішення без ворожіння на кавовій гущі:

std::map

std::unordered_map

std::map

std::unordered_map

4. Типові помилки

Помилка № 1: думати, що map використовує == для унікальності.
Новачок часто очікує, що контейнер «порівняє ключі на рівність», як у звичайній логіці. Але map живе у світі порядку: якщо компаратор не може розрізнити два ключі (жоден не менший за інший), ключі вважаються еквівалентними. У підсумку різні обʼєкти можуть «склеїтися» в один елемент, і це виглядає як містика, доки ви не згадаєте про контракт.

Помилка № 2: писати компаратор через <= або робити його нестрогим.
Компаратор у map/set — це «строго раніше», а не «раніше або дорівнює». Коли ви використовуєте <=, контейнер може отримати суперечливу картину світу: ключ виявляється «меншим за самого себе», і внутрішні припущення руйнуються. Навіть якщо код «якось працює», це не той випадок, коли варто радіти.

Помилка № 3: порівнювати не всі поля, які визначають унікальність ключа.
Якщо ключ — це кілька полів (наприклад, прізвище + імʼя), а компаратор враховує лише прізвище, то контейнер почне вважати всіх людей з однаковим прізвищем одним і тим самим ключем. Це не «помилка STL», а неправильно сформульований контракт, який призводить до втрати даних.

Помилка № 4: у unordered_map змінювати правило рівності й забувати про хеш.
Найпідступніша пастка: ви робите «рівність без урахування регістру» (або порівняння лише частини полів), але залишаєте старий хеш. Контейнер починає поводитися нелогічно: find() не знаходить елемент, який ви «точно додавали». Причина в тому, що за контрактом рівні ключі зобовʼязані мати однаковий хеш, інакше елементи потрапляють у різні кошики. Вимоги до Hash і Pred якраз про це.

Помилка № 5: очікувати, що unordered_map зберігає елементи у стабільному порядку.
Іноді хочеться «просто надрукувати словник» і щоразу отримувати один і той самий порядок, як у map. Але unordered_map не обіцяє порядку обходу: він залежить від хешів, кошиків, внутрішньої організації і навіть від того, як саме ви додавали або видаляли елементи. Якщо порядок важливий — обирайте map або сортуйте окремо, але не будуйте логіку на порядку unordered_map.