C++ set: std::set ile benzersiz, sıralı elemanlar

Benzersiz ve Sıralı Değerlerden Oluşan Bir Torba

unordered_map'in anahtar-değer çiftlerini hızlı karma tabanlı aramayla nasıl sakladığını görmüştün. Bir std::set ise daha sade bir kuzendir: yalnızca değerleri saklar — ilişkili veri yoktur — ve iki kuralı otomatik olarak uygular. Her eleman benzersizdir (yinelenenler sessizce atılır) ve elemanlar her zaman sıralı düzende tutulur.

Bu da set'i "bunu daha önce gördüm mü?" ya da "bana farklı öğeleri sıralı ver" gibi sorular için doğal bir tercih yapar. Yinelenenleri dert etmeden eklersin ve önce sıralamadan dolaşırsın.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // yinelenen - yok sayılır

    for (int x : s) cout << x << " ";   // 10 30 40 (sıralı, tekrarsız)
}

10'u iki kez ve sırasız eklediğimize dikkat et; yine de çıktı sıralı ve 10 bir kez görünüyor. Defter tutmayı set senin yerine yaptı.

Ekleme ve Silme

insert, bir değer henüz yoksa onu ekler. Ekleme işleminin gerçekten gerçekleşip gerçekleşmediğini söyleyen, .second'ı bir bool olan bir pair döndürür — bir değerin yeni olup olmadığını bilmek istediğinde işe yarar:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Bir değeri silmek için erase'i değerin kendisiyle çağır; silinen eleman sayısını döndürür (bir set için 0 ya da 1). Olmayan bir şeyi silmek zararsızdır, hata değildir:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // 3'ü siler
    s.erase(99);         // hiçbir şey yapmaz, 0 döndürür

    for (int x : s) cout << x << " ";   // 1 2 4
}

Üyeliği Kontrol Etme

Bir set'in tüm amacı hızlı "bu burada mı?" testleridir. En açık yol, 1 ya da 0 döndüren count'tur:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

C++20'den beri daha da okunabilir bir seçenek var: doğrudan bool döndüren contains:

if (primes.contains(7)) { /* ... */ }   // C++20

Yaygın bir hata, bir map'te yapacağın gibi operator[]'e başvurmaktır. Bir set'in operator[]'i yoktur: getirilecek bir değer yoktur, yalnızca test edilecek bir varlık vardır. s[7] değil, count ya da contains kullan.

Gerçek konuma ihtiyacın varsa (silmek ya da komşulara bakmak için), bir yineleyici veya end() döndüren find'ı kullan:

#include <iostream>
#include <set>
using namespace std;

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

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // yineleyiciyle sil - ikinci bir arama yok
    }
    cout << "size now " << s.size() << "\n";
}

Sıralı Dolaşma ve Aralık Sorguları

Bir set sıralı olduğundan, dolaşma her zaman elemanları küçükten büyüğe verir ve sıralı konteyner numaralarını bedavaya elde edersin. lower_bound(x), x'ten küçük olmayan ilk elemanı; upper_bound(x) ise x'ten kesinlikle büyük olan ilk elemanı verir — birlikte, her elemanı kontrol etmeden sayısal bir aralığı taramana izin verirler:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // [12, 31] aralığındaki her şeyi yazdır
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

İnce ama önemli bir kural: set elemanları değiştirilemez. Yineleyici sana bir const referans verir, bu yüzden bir elemanı yerinde değiştiremezsin — bunu yapmak, konteynerin dayandığı sıralamayı bozabilir. Bir değeri "değiştirmek" için eskisini sil ve yenisini ekle.

Varsayılan olarak sıralama artandır (std::less). Azalan sıra için ikinci şablon argümanı olarak farklı bir karşılaştırıcı ver:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set, üç yakın akrabadan biridir ve doğru olanı seçmek önemlidir:

set<int>            // benzersiz değerler, sıralı, O(log n)
multiset<int>       // yinelenenlere izin verir, sıralı, O(log n)
unordered_set<int>  // benzersiz değerler, SIRASIZ, ortalama O(1)

Yalnızca üyelik testlerine ihtiyacın olduğunda ve sıra önemli değilse unordered_set'e başvur — karma tabanlı aramaları, ortalamada set'in ağaç tabanlı O(log n)'inden daha hızlıdır. Elemanları sıralı düzende, lower_bound/upper_bound ile aralık sorguları ya da kararlı yineleyici davranışı istediğinde set'i seç. multiset'i yalnızca yinelenenler anlamlıysa kullan (örneğin, tekrarlanan değerlerin bir histogramı): bir multiset'te count(x) 1'den fazlasını döndürebilir ve tek bir yineleyiciyle silmediğin sürece erase(x) tüm kopyaları kaldırır.

set'in klasik bir kullanımı: bir vector'ü tek hamlede hem yinelenenlerden arındır hem sırala.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Set'i vector'ün yineleyicilerinden oluşturmak her yineleneni atar ve geri kalanı sıralar — elle döngü yok, std::sort artı std::unique dansı yok.

Sıradaki: pair ve tuple

insert'in döndürdüğü pair üzerinde .first ve .second'ın belirdiğini ve yapısal bağların (auto [it, inserted]) onu temizce açtığını gördün. "Birkaç değeri bir araya getiren" bu hafif tipler, STL'in her yerinde. Sırada pair ve tuple'a doğrudan bakacağız: onları nasıl oluşturacağını, açacağını ve koca bir struct tanımlamadan bir fonksiyondan birden çok değeri nasıl döndüreceğini.