Associative Container'lar

Sequence container'lar elemanları senin eklediğin sırada tutuyordu. Associative container'lar ise farklı bir mantıkla çalışır: elemanları bir kurala göre organize ederler. Bu kural ya sıralama (ordered) ya da hash (unordered) tabanlıdır.

Bir kütüphane analojisi düşün: kitaplar rastgele raflara konmaz. Ya alfabetik sırayla dizilirler (ordered) ya da bir katalog numarasıyla doğrudan bulunurlar (hash tabanlı). Her iki yöntemin amacı aynı — aradığını hızlı bulmak.

Bu derste set, map, multiset, multimap ve bunların unordered_ versiyonlarını öğreneceğiz.

std::set — Benzersiz Sıralı Küme

set, benzersiz elemanlardan oluşan bir kümedir. Her eleman en fazla bir kez bulunur ve elemanlar otomatik olarak sıralı tutulur (varsayılan: küçükten büyüğe).

İç yapısı kırmızı-siyah ağaç (red-black tree) — dengeli bir ikili arama ağacıdır. Bu sayede ekleme, silme ve arama hep O(log n) maliyetindedir.

#include <set>
#include <iostream>

int main() {
    std::set<int> numbers = {5, 3, 8, 1, 3, 9, 1};

    // Tekrar eden elemanlar otomatik elenir
    // Elemanlar sıralı tutulur
    for (int x : numbers) {
        std::cout << x << " ";
    }
    // Çıktı: 1 3 5 8 9
    std::cout << "\n";

    // Eleman ekleme
    auto [it, inserted] = numbers.insert(4);
    std::cout << "4 eklendi mi? " << (inserted ? "Evet" : "Hayir") << "\n";

    auto [it2, inserted2] = numbers.insert(3);
    std::cout << "3 eklendi mi? " << (inserted2 ? "Evet" : "Hayir") << "\n";
    // Zaten var olduğu için eklenmez

    // Arama
    if (numbers.count(5)) {
        std::cout << "5 set'te var\n";
    }

    // C++20 — contains() daha okunabilir
    if (numbers.contains(5)) {
        std::cout << "5 set'te var (contains)\n";
    }

    return 0;
}

Set'te Arama ve Silme

#include <set>
#include <iostream>

int main() {
    std::set<int> s = {10, 20, 30, 40, 50};

    // find() — iterator döner
    auto it = s.find(30);
    if (it != s.end()) {
        std::cout << "Bulundu: " << *it << "\n";
    }

    // Silme — değer ile
    s.erase(20);

    // Silme — iterator ile
    it = s.find(40);
    if (it != s.end()) {
        s.erase(it);
    }

    // Alt ve üst sınır
    s = {10, 20, 30, 40, 50, 60, 70};
    auto low = s.lower_bound(25);   // 25'ten >= ilk eleman → 30
    auto high = s.upper_bound(50);  // 50'den > ilk eleman → 60

    std::cout << "lower_bound(25): " << *low << "\n";   // 30
    std::cout << "upper_bound(50): " << *high << "\n";   // 60

    // Aralık yazdırma: [30, 60)
    for (auto it = low; it != high; ++it) {
        std::cout << *it << " ";
    }
    // Çıktı: 30 40 50
    std::cout << "\n";

    return 0;
}

Custom Sıralama

Varsayılan olarak set küçükten büyüğe sıralar. Bunu değiştirebilirsin:

#include <set>
#include <string>
#include <iostream>

int main() {
    // Büyükten küçüğe sıralama
    std::set<int, std::greater<int>> descending = {3, 1, 4, 1, 5, 9};

    for (int x : descending) {
        std::cout << x << " ";
    }
    // Çıktı: 9 5 4 3 1
    std::cout << "\n";

    // Custom comparator ile
    auto byLength = [](const std::string& a, const std::string& b) {
        return a.length() < b.length();
    };

    std::set<std::string, decltype(byLength)> words(byLength);
    words.insert("elma");
    words.insert("armut");
    words.insert("muz");

    for (const auto& w : words) {
        std::cout << w << " ";
    }
    // Çıktı: muz elma armut (uzunluğa göre)
    std::cout << "\n";

    return 0;
}

std::multiset — Tekrara İzin Veren Küme

set'in tekrar eden elemanlara izin veren versiyonu. Aynı iç yapı (kırmızı-siyah ağaç), aynı sıralama — ama aynı değer birden fazla kez bulunabilir.

#include <set>
#include <iostream>

int main() {
    std::multiset<int> ms = {5, 3, 8, 3, 1, 5, 3};

    for (int x : ms) {
        std::cout << x << " ";
    }
    // Çıktı: 1 3 3 3 5 5 8
    std::cout << "\n";

    // count() — kaç tane var?
    std::cout << "3 kac tane: " << ms.count(3) << "\n";  // 3

    // Tüm 3'leri bul
    auto [first, last] = ms.equal_range(3);
    std::cout << "3'ler: ";
    for (auto it = first; it != last; ++it) {
        std::cout << *it << " ";
    }
    // Çıktı: 3 3 3
    std::cout << "\n";

    // Sadece bir tanesini sil
    auto it = ms.find(3);
    if (it != ms.end()) {
        ms.erase(it);  // Sadece ilk 3'ü siler
    }
    std::cout << "3 kac tane: " << ms.count(3) << "\n";  // 2

    return 0;
}

std::map — Anahtar-Değer Çiftleri

map, her anahtarı (key) bir değere (value) eşler. Anahtarlar benzersiz ve sıralı tutulur. Bir telefon rehberi gibi — her isim (anahtar) bir numaraya (değer) karşılık gelir.

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

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

    // Eleman ekleme yolları
    ages["Ali"] = 25;
    ages["Ayse"] = 30;
    ages.insert({"Mehmet", 28});
    ages.emplace("Zeynep", 22);

    // Erişim
    std::cout << "Ali: " << ages["Ali"] << "\n";

    // Gezinme — anahtara göre sıralı
    for (const auto& [name, age] : ages) {
        std::cout << name << " -> " << age << "\n";
    }
    // Çıktı (alfabetik):
    // Ali -> 25
    // Ayse -> 30
    // Mehmet -> 28
    // Zeynep -> 22

    return 0;
}

⚠️ `operator[]` tuzağı: Eğer olmayan bir anahtar ile [] kullanırsan, map o anahtarı otomatik oluşturur (varsayılan değerle). Sadece okuma yapmak istiyorsan at() veya find() kullan.

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

int main() {
    std::map<std::string, int> scores = {{"Ali", 85}, {"Ayse", 92}};

    // Tehlikeli — "Veli" yoksa oluşturulur (değer: 0)
    int s = scores["Veli"];  // Artık scores'ta Veli var!
    std::cout << "Veli: " << s << "\n";  // 0
    std::cout << "Size: " << scores.size() << "\n";  // 3!

    // Güvenli — at() fırlatır, find() kontrol sağlar
    try {
        int x = scores.at("Burak");  // std::out_of_range fırlatır
    } catch (const std::out_of_range& e) {
        std::cout << "Burak bulunamadi\n";
    }

    auto it = scores.find("Ali");
    if (it != scores.end()) {
        std::cout << "Ali: " << it->second << "\n";  // 85
    }

    return 0;
}

Map ile Sık Yapılan İşlemler

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

int main() {
    std::map<std::string, int> wordCount;
    std::string text[] = {"elma", "armut", "elma", "muz", "elma", "armut"};

    // Kelime sayma — klasik pattern
    for (const auto& word : text) {
        wordCount[word]++;  // Yoksa 0 ile oluşturur, sonra artırır
    }

    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << "\n";
    }
    // armut: 2
    // elma: 3
    // muz: 1

    // Silme
    wordCount.erase("muz");

    // Eleman sayısı kontrolü
    std::cout << "contains armut: " << wordCount.contains("armut") << "\n";

    return 0;
}

std::multimap — Tekrarlı Anahtarlı Map

multimap'te aynı anahtar birden fazla değere sahip olabilir. Bir öğrencinin birden fazla dersi olması gibi.

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

int main() {
    std::multimap<std::string, std::string> studentCourses;

    studentCourses.insert({"Ali", "Matematik"});
    studentCourses.insert({"Ali", "Fizik"});
    studentCourses.insert({"Ali", "Kimya"});
    studentCourses.insert({"Ayse", "Biyoloji"});
    studentCourses.insert({"Ayse", "Matematik"});

    // Ali'nin tüm derslerini bul
    auto [first, last] = studentCourses.equal_range("Ali");
    std::cout << "Ali'nin dersleri:\n";
    for (auto it = first; it != last; ++it) {
        std::cout << "  " << it->second << "\n";
    }

    // Toplam kayıt sayısı
    std::cout << "Ali ders sayisi: " << studentCourses.count("Ali") << "\n";

    return 0;
}

💡 multimap'te `operator[]` yoktur — çünkü bir anahtar birden fazla değere sahip olabilir, hangisini döndüreceği belirsiz olurdu. find() veya equal_range() kullan.

std::unordered_set ve std::unordered_map

Ordered versiyonlar kırmızı-siyah ağaç kullanıyordu (O(log n)). Unordered versiyonlar ise hash tablosu kullanır — ortalama O(1) ekleme, silme ve arama.

Sıralama garantisi yok ama hız çok daha fazla. Eğer elemanların sıralı olmasını umursamıyorsan, unordered versiyonları tercih et.

unordered_set

#include <unordered_set>
#include <iostream>

int main() {
    std::unordered_set<int> us = {5, 3, 8, 1, 9};

    // Ekleme ve arama — ortalama O(1)
    us.insert(4);

    if (us.contains(3)) {
        std::cout << "3 bulundu\n";
    }

    // Sıra garanti değil!
    for (int x : us) {
        std::cout << x << " ";
    }
    std::cout << "\n";

    // Hash tablosu istatistikleri
    std::cout << "Bucket sayisi: " << us.bucket_count() << "\n";
    std::cout << "Load factor: " << us.load_factor() << "\n";

    return 0;
}

unordered_map

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

int main() {
    std::unordered_map<std::string, double> prices = {
        {"elma", 12.5},
        {"armut", 15.0},
        {"muz", 35.0},
        {"portakal", 8.5}
    };

    // Erişim — ortalama O(1)
    std::cout << "Elma: " << prices["elma"] << " TL\n";

    // Ekleme
    prices["cilek"] = 45.0;

    // Gezinme — sıra belirsiz
    for (const auto& [fruit, price] : prices) {
        std::cout << fruit << ": " << price << " TL\n";
    }

    // Arama
    if (auto it = prices.find("muz"); it != prices.end()) {
        std::cout << "Muz fiyati: " << it->second << " TL\n";
    }

    return 0;
}

Custom Hash Fonksiyonu

Kendi türlerini unordered container'larda kullanmak istersen, bir hash fonksiyonu sağlamalısın:

#include <unordered_set>
#include <string>
#include <iostream>

struct Point {
    int x, y;

    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// Custom hash
struct PointHash {
    size_t operator()(const Point& p) const {
        auto h1 = std::hash<int>{}(p.x);
        auto h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 1);  // Hash birleştirme
    }
};

int main() {
    std::unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});  // Tekrar — eklenmez

    std::cout << "Unique points: " << points.size() << "\n";  // 2

    return 0;
}

Ordered vs Unordered Performans Karşılaştırması

"En kötü durum" ne demek? Hash tablosunda tüm elemanlar aynı bucket'a düşerse (hash collision), arama O(n) olur. Ama iyi bir hash fonksiyonu ile bu pratikte neredeyse hiç olmaz.

Hangi Container'ı Ne Zaman Kullanmalıyım?

Bu karar tablosu, pratik ihtiyaçlara göre doğru container'ı seçmeni sağlar:

Container seçimi:
│
├── Anahtar-değer çifti var mı?
│   ├── Evet → Sıralama lazım mı?
│   │   ├── Evet → Tekrarlı anahtar?
│   │   │   ├── Evet → multimap
│   │   │   └── Hayır → map
│   │   └── Hayır → unordered_map
│   └── Hayır ↓
│
├── Sadece benzersiz eleman kümesi mi?
│   ├── Evet → Sıralama lazım mı?
│   │   ├── Evet → set
│   │   └── Hayır → unordered_set
│   └── Hayır → multiset

⚠️ Küçük veri setleri için dikkat: 100 elemanın altında unordered_map ile map arasında fark hissetmezsin. Hatta bazen vector ile lineer arama bile hash tablosundan hızlı olabilir (cache locality etkisi).

Gerçek Dünya Örneği: Öğrenci Not Sistemi

#include <map>
#include <unordered_map>
#include <set>
#include <string>
#include <iostream>
#include <vector>
#include <numeric>

int main() {
    // Öğrenci notları: isim → notlar listesi
    std::unordered_map<std::string, std::vector<int>> studentGrades;

    studentGrades["Ali"] = {85, 90, 78, 92};
    studentGrades["Ayse"] = {95, 88, 91, 97};
    studentGrades["Mehmet"] = {70, 65, 80, 75};

    // Ortalama hesapla ve sıralı map'e ekle
    std::map<double, std::string, std::greater<>> ranking;

    for (const auto& [name, grades] : studentGrades) {
        double avg = std::accumulate(grades.begin(), grades.end(), 0.0)
                     / grades.size();
        ranking[avg] = name;
        std::cout << name << " ortalama: " << avg << "\n";
    }

    // Sıralama (yüksekten düşüğe)
    std::cout << "\nSiralama:\n";
    int rank = 1;
    for (const auto& [avg, name] : ranking) {
        std::cout << rank++ << ". " << name << " (" << avg << ")\n";
    }

    // Benzersiz not değerleri
    std::set<int> uniqueGrades;
    for (const auto& [name, grades] : studentGrades) {
        uniqueGrades.insert(grades.begin(), grades.end());
    }

    std::cout << "\nBenzersiz not degerleri: ";
    for (int g : uniqueGrades) {
        std::cout << g << " ";
    }
    std::cout << "\n";

    return 0;
}

Özet

• `set` benzersiz elemanları sıralı tutar (kırmızı-siyah ağaç, O(log n)). Aralık sorguları için idealdir.

• `map` anahtar-değer çiftlerini sıralı tutar. operator[] olmayan anahtarı otomatik oluşturur — dikkatli ol, güvenli erişim için find() veya at() kullan.

• `multiset` ve `multimap` tekrarlı elemanlara/anahtarlara izin verir. equal_range() ile aynı değerdeki tüm elemanları alabilirsin.

• `unordered_set` ve `unordered_map` hash tablosu kullanır — ortalama O(1) ama sıralama garantisi yok. Sıra önemli değilse bunları tercih et.

• Ordered container'lar aralık sorguları (lower_bound, upper_bound) destekler, unordered'lar desteklemez.

• Küçük veri setlerinde (< 100 eleman) container seçimi performansı nadiren etkiler — okunabilirlik ve anlam daha önemlidir.