C++ unordered_map: Hızlı Hash Map Arama Anlatımı

Sıranın Önemli Olmadığı Durumlar

Az önce, anahtarlarını dengeli bir ağaç kullanarak sıralı tutan ve sana O(log n) işlemler veren std::map'i gördün. Ancak sıralamanın bir bedeli vardır ve çoğu zaman anahtarların hangi sırayla geldiği umurunda olmaz - tek istediğin "bu anahtar burada mı ve değeri nedir?" diye olabildiğince hızlı sormaktır.

İşte std::unordered_map bunun içindir. Bir hash tablosudur: her anahtarı nereye saklayacağına karar vermek için bir hash fonksiyonundan geçirir; bu da ekleme, arama ve silmeyi O(log n) yerine ortalama O(1) yapar. Bunun karşılığında iterasyon sırası belirtilmemiştir - anahtarlar, bucket'ların onları tuttuğu sırayla gelir.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> stock = {
        {"apple", 12},
        {"banana", 7},
        {"cherry", 30}
    };

    cout << "bananas: " << stock["banana"] << "\n";
    stock["apple"] += 5;
    cout << "apples now: " << stock["apple"] << "\n";
}

Arayüz bilerek map'inkiyle neredeyse aynıdır - çoğu zaman yalnızca tipi değiştirerek birini diğeriyle değiştirebilirsin. <map> değil, <unordered_map> dahil et; anahtarlar sırasız çıkar.

Ekleme ve Güncelleme

Girdileri eklemenin birkaç yolu vardır ve hepsi aynı şekilde davranmaz. En çok kullanacağın ikisi operator[] ve insert'tür:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> votes;

    votes["alice"] = 3;              // oluştur ya da üzerine yaz
    votes["alice"] = 5;              // üzerine yazar -> 5
    votes.insert({"bob", 2});        // yalnızca "bob" yoksa ekler
    votes.insert({"bob", 99});       // yok sayılır, "bob" zaten var

    cout << "alice: " << votes["alice"] << "\n";   // 5
    cout << "bob:   " << votes["bob"] << "\n";      // 2, 99 değil
}

Temel fark: operator[] mevcut bir değerin üzerine yazar, oysa insert zaten var olan bir anahtara dokunmaz. C++17 kullanıyorsan, insert_or_assign(key, value) sana "ne olursa olsun bunu ayarla" anlamını verir ve try_emplace(key, args...), değeri yalnızca anahtar yeni olduğunda yerinde oluşturur - oluşturulması maliyetli değerler için kullanışlıdır.

operator[] Tuzağı: Okurken Ekler

Bu, unordered_map ile yapılan en yaygın hatadır, bu yüzden kendi bölümünü hak ediyor. m[key] saf bir okuma değildir. Anahtar eksikse onu varsayılan olarak oluşturup ekler (bir int, 0 olur; bir string, "" olur), ardından bir referans döndürür. Yani bir aramaya benzeyen kod, map'i sessizce büyütür:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen;
    seen["x"] = 1;

    // Yalnızca "y"yi KONTROL etmek istedik ama [] onu ekledi:
    if (seen["y"] == 0) {
        cout << "y looked missing...\n";
    }

    cout << "size is now " << seen.size() << "\n";   // 2, 1 değil!
}

seen["y"], yalnızca anılmasıyla bir "y" -> 0 girdisi oluşturdu. Map'i değiştirmeden üyeliği test etmek için count (0 ya da 1 döndürür) veya find kullan:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> seen{{"x", 1}};

    if (seen.count("y")) {
        cout << "found y\n";
    } else {
        cout << "no y, size still " << seen.size() << "\n";   // 1
    }

    // C++20: contains() count()'tan daha temiz okunur
    if (seen.contains("x")) cout << "x is here\n";
}

Pratik kural: []'yi yalnızca oluşturmak ya da güncellemek niyetindeysen kullan. Saf okumalar için count, contains (C++20) ya da find kullan.

find ve at: Güvenli Aramalar

find, girdiye bir yineleyici döndürür ya da anahtar yoksa end() döndürür. Asla eklemez ve tek bir aramada hem anahtara hem de değere it->first ve it->second üzerinden ulaşmanı sağlar:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> prices = {{"pen", 2}, {"mug", 9}};

    auto it = prices.find("mug");
    if (it != prices.end()) {
        cout << it->first << " costs " << it->second << "\n";
    } else {
        cout << "not found\n";
    }
}

Anahtarın var olması gerektiğini bildiğin ve yoksa kesin bir hata istediğin durumlarda at kullan. []'nin aksine at eklemez - eksik bir anahtar için std::out_of_range fırlatır:

int p = prices.at("pen");   // sorun yok
int q = prices.at("hat");   // std::out_of_range fırlatır - anahtar yok

Yani üç arama stilin var: [] (ekler), at (fırlatır) ve find/count (map'e dokunmadan varlığı bildirir). Hata davranışı niyetinle örtüşeni seç.

İterasyon ve Silme

Structured binding'lerle aralık tabanlı bir for döngüsü, her girdiyi dolaşmanın temiz yoludur. Sıranın rastgele olduğunu unutma - asla ona güvenme:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 7}, {"green", 2}};

    for (const auto& [team, score] : wins) {
        cout << team << ": " << score << "\n";   // sıra belirtilmemiştir
    }
}

Bir girdiyi kaldırmak için erase doğrudan bir anahtar alır ve kaçının kaldırıldığını döndürür (0 ya da 1). Önemli bir tuzak: bir unordered_map'te iterasyon sırasında silmek yalnızca silinen öğenin yineleyicisini geçersiz kılar, bu yüzden güvenli ilerlemek için erase(it)'in döndürdüğü değeri kullan:

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int main() {
    unordered_map<string, int> wins = {{"red", 4}, {"blue", 1}, {"green", 2}};

    // Puanı 3'ün altında olan her takımı çıkar
    for (auto it = wins.begin(); it != wins.end(); ) {
        if (it->second < 3)
            it = wins.erase(it);   // erase, bir sonraki geçerli yineleyiciyi döndürür
        else
            ++it;
    }

    cout << "remaining entries: " << wins.size() << "\n";
}

wins.erase(it++) tarzı yazmak ya da düz bir erase(it)'ten sonra ++it yapmak klasik sarkan yineleyici tuzağıdır - silinen yineleyici ölüdür, bu yüzden her zaman erase'in döndürdüğü yineleyiciyi al.

map mı, unordered_map mı?

Her ikisi de benzer bir API ile anahtar-değer çiftlerini saklar, dolayısıyla seçim neye ihtiyacın olduğuna iner:

// std::map            -> sıralı anahtarlar, O(log n), aralık sorguları (lower_bound)
// std::unordered_map  -> sırasız,           O(1) ort., en hızlı düz arama

Yalnızca anahtarla hızlı aramaya ihtiyacın olduğunda ve sıra önemsizse (kelime frekanslarını sayma, önbellekleme, yinelenenleri ayıklama) unordered_map'e yönel. Anahtarlara sıralı düzende ihtiyacın olduğunda, sıralı iterasyon yapmak istediğinde ya da aralık sorguları yaptığında map'i seç. unordered_map için iki uyarı: O(1)'i bir ortalamadır - kötü bir hash onu düşürebilir - ve özel bir anahtar tipi bir hash özelleştirmesine ya da bir hash functor'ına ihtiyaç duyarken, map yalnızca operator<'a ihtiyaç duyar.

Sırada: Set

Artık anahtar-değer konteynerinin her iki türünü de gördün. Ancak bazen bir değere hiç ihtiyacın olmaz - yalnızca bir şeyin mevcut olup olmadığı umurundadır; benzersiz etiketlerden ya da ziyaret edilmiş ID'lerden oluşan bir koleksiyon gibi. Sırada, yalnızca anahtarları saklayan ve onları otomatik olarak benzersiz tutan std::set'e (ve onun hash tabanlı kuzeni unordered_set'e) bakacağız.