C++ std::map: Anahtarlar, Değerler, Arama ve Ekleme

Anahtara Göre Arama Yapma

vector, konuma göre indeksleme yaptığında harikadır: 0. eleman, 1. eleman vesaire. Ama çoğu zaman bir konumun yoktur; bir adın vardır ve ona bağlı şeyi istersin: bir kullanıcı ve puanı, bir kelime ve kaç kez geçtiği, bir ülke kodu ve başkenti. Eşleşme bulmak için bir vector'ü taramak O(n)'dir ve hızla yavaşlar.

std::map bunu çözer. Anahtar-değer çiftleri saklar, onları anahtara göre sıralı tutar ve bir değeri anahtarına göre O(log n) zamanda bulmana izin verir. Kullanmak için <map> ekle:

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

int main() {
    map<string, int> scores;

    scores["Ada"] = 90;
    scores["Grace"] = 100;
    scores["Linus"] = 75;

    cout << "Grace scored " << scores["Grace"] << "\n";
}

map<string, int> "string anahtarlardan int değerlere bir map" diye okunur. Anahtarlar benzersizdir: aynı anahtara iki kez atarsan ikinci değer kazanır. İçinde bir map dengeli bir ikili arama ağacıdır; her şeyin sıralı kalmasının ve aramaların sabit değil de logaritmik olmasının nedeni budur.

Eleman Ekleme

Giriş eklemenin birkaç yolu vardır ve aralarındaki fark önemlidir. En yaygın olanı, anahtar yoksa onu oluşturan ve atayabileceğin bir referans döndüren operator[]'tir:

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

int main() {
    map<string, int> inventory;

    inventory["apples"] = 12;     // oluştur + ata
    inventory["apples"] += 3;     // oku-değiştir-yaz, şimdi 15

    cout << "apples: " << inventory["apples"] << "\n";
}

Mevcut bir anahtarın üzerine yazmayı reddeden bir ekleme istiyorsan insert veya emplace kullan. Her ikisi de .second üyesi, eklemenin gerçekten gerçekleşip gerçekleşmediğini söyleyen bir bool olan bir pair döndürür:

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

int main() {
    map<string, int> ages;
    ages["Ada"] = 36;

    auto result = ages.insert({"Ada", 99});   // Ada zaten var
    cout << "inserted? " << result.second << "\n";   // 0 (false)
    cout << "Ada is still " << ages["Ada"] << "\n";  // 36, değişmedi
}

"Son yazma kazanır" istediğinde [] kullan; mevcut bir anahtarın el değmeden kalması gerektiğinde insert/emplace kullan.

operator[] Tuzağı: Okurken Ekler

Bu, en yaygın map hatasıdır. operator[] saf bir okuma değildir: anahtar yoksa, onu varsayılan olarak oluşturulmuş bir değerle (int için 0, string için "" vb.) sessizce ekler ve ona bir referans döndürür. Yani bir anahtarı yalnızca [] ile kontrol etmek bile map'i değiştirir:

map<string, int> m;
if (m["maybe"] == 0) {   // HATA: bu az önce "maybe" -> 0 oluşturdu
    // ...
}
cout << m.size();        // 0 değil 1 - yanlışlıkla bir anahtar ekledin

Bu, const map ile de seni ısırır; orada operator[] ekleme yapması gerekebileceği için derlenmez bile. Eklemeden okumak için find, count/contains veya at kullan:

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

int main() {
    map<string, int> m = {{"a", 1}, {"b", 2}};

    // find: bir yineleyici döndürür, yoksa == end()
    auto it = m.find("c");
    cout << "found c? " << (it != m.end()) << "\n";   // 0

    // contains (C++20) veya count (her sürüm)
    cout << "has a? " << m.contains("a") << "\n";      // 1
    cout << "count z: " << m.count("z") << "\n";       // 0

    // at: yoksa std::out_of_range fırlatır - asla eklemez
    cout << "a = " << m.at("a") << "\n";
}

Pratik kural: niyetin okumaksa asla []'e başvurma. Anahtarın var olması gerektiğinde at, var olmayabileceği durumda find/contains kullan.

Sıralı Dolaşma

Bir map ağaca dayalı olduğundan, onu dolaşmak anahtarları her zaman ve bedavadan artan sıralı düzende ziyaret eder. Her eleman bir pair<const Key, Value>'dir; bu yüzden anahtar ile değeri temiz bir şekilde açmak için bir yapısal bağlama kullan:

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

int main() {
    map<string, int> wordCount;
    for (const string& w : {"sky", "blue", "sky", "sea", "blue", "sky"}) {
        wordCount[w]++;   // eksik anahtarlar 0'dan başlar, sonra ++
    }

    for (const auto& [word, count] : wordCount) {
        cout << word << ": " << count << "\n";
    }
}

Bağlamadaki anahtarın const olduğuna dikkat et: bir değeri döngü içinde auto& ile değiştirebilirsin ama bir anahtarı yerinde asla değiştiremezsin (bu sıralamayı bozar). Çıktı, hiçbir sıralama adımı olmadan alfabetik sırada (blue, sea, sky) gelir; insanların sıralı gezinme önemli olduğunda bir hash tablosu yerine map'i seçmesinin nedeni tam olarak budur.

O wordCount[w]++ deyimi, erişimde-ekleme davranışının en tipik kullanımıdır: burada eksik bir anahtarın 0'dan başlamasını istersin, dolayısıyla [] doğru araçtır.

Eleman Silme ve Boyut

Anahtara göre erase ile sil; bu, kaç elemanın kaldırıldığını döndürür (bir map için 0 ya da 1). find'dan gelen bir yineleyiciyle de silebilirsin. Konteynerin durumunu size() ve empty() ile kontrol et:

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

int main() {
    map<string, int> m = {{"x", 1}, {"y", 2}, {"z", 3}};

    cout << "removed: " << m.erase("y") << "\n";   // 1
    cout << "removed: " << m.erase("q") << "\n";   // 0 (orada değildi)

    cout << "size: " << m.size() << "\n";          // 2
    cout << "empty? " << m.empty() << "\n";        // 0

    for (const auto& [k, v] : m) cout << k << " ";  // x z
    cout << "\n";
}

Bir döngü içinde silerken bir tuzak: m.erase(it), it'yi geçersiz kılar; bu yüzden sonrasında ++it yapamazsın. C++11'den beri güvenli desen, bir sonraki elemana bir yineleyici döndüren it = m.erase(it)'dir. Tüm map boyunca tek seferlik koşullu kaldırma için std::erase_if(m, predicate) (C++20) daha temizdir.

Sıradaki: unordered_map

std::map sana sıralı anahtarlar ve öngörülebilir O(log n) işlemler verir ama bu sıralamanın bedelini her aramada ödersin. Anahtar sırasını umursamayıp yalnızca mümkün olan en hızlı aramaları istediğinde, unordered_map sıralı ağacı bir hash tablosuyla değiştirir: ortalama O(1) erişim. Sıradaki bölümde nasıl çalıştığını, ortalama sabit zamanının map'in logaritmasını ne zaman geçtiğini ve beraberinde gelen hashleme tuzaklarını (özel anahtar türleri, en kötü durumdaki çakışmalar) göreceğiz.