Rust std::collections: BTreeMap, HashSet, BTreeSet, VecDeque ve BinaryHeap Ne Zaman Kullanılır?

Dört grup, sekiz koleksiyon

Belge koleksiyonları dört gruba ayırır: diziler (Vec, VecDeque, LinkedList), sözlükler (HashMap, BTreeMap), kümeler (HashSet, BTreeSet) ve diğerleri (BinaryHeap). Kümeler, değeri olmayan sözlükler gibi düşünülebilir; nitekim HashSet belgede değeri () olan bir HashMap olarak tanımlanır. Bu yüzden bir sözlük için söylenen performans ve anahtar kuralları, aynı ailedeki küme için de geçerlidir.

BTreeMap: anahtar sırasını koruyan sözlük

BTreeMap, adından da anlaşılacağı gibi B-ağacı (B-Tree) üzerine kurulu sıralı bir sözlüktür. Anahtarların Ord trait'ini uygulaması, yani her zaman birbiriyle karşılaştırılabilmesi gerekir; sayılar ve metinler bu şartı sağlar. iter, keys ve values elemanları anahtar sırasıyla verir. API'si büyük ölçüde HashMap ile aynıdır (insert, get, remove, entry), ama sıralı olmanın getirdiği ek metotlar vardır:

use std::collections::BTreeMap;

fn main() {
    let mut satis = BTreeMap::new(); // yıl -> örnek satış adedi
    satis.insert(2024, 410);
    satis.insert(2021, 250);
    satis.insert(2023, 380);
    satis.insert(2022, 300);

    for (yil, adet) in &satis {
        println!("{yil}: {adet}");
    }
    println!("ilk: {:?}", satis.first_key_value());
    println!("son: {:?}", satis.last_key_value());

    let aralik: Vec<_> = satis.range(2022..2024).collect();
    println!("2022..2024: {aralik:?}");
    println!("2023 ve sonrası: {:?}", satis.range(2023..).map(|(y, _)| *y).collect::<Vec<_>>());

    let mut harf = BTreeMap::new();
    for c in "kelebek".chars() {
        *harf.entry(c).or_insert(0) += 1;
    }
    println!("{harf:?}");
}
// çıktı: 2021: 250
// çıktı: 2022: 300
// çıktı: 2023: 380
// çıktı: 2024: 410
// çıktı: ilk: Some((2021, 250))
// çıktı: son: Some((2024, 410))
// çıktı: 2022..2024: [(2022, 300), (2023, 380)]
// çıktı: 2023 ve sonrası: [2023, 2024]
// çıktı: {'b': 1, 'e': 3, 'k': 2, 'l': 1}

Elemanları 2024, 2021, 2023, 2022 sırasıyla eklememize rağmen döngü onları yıl sırasıyla yazdı. range(2022..2024) başlangıcı dahil, bitişi hariç bir aralıktaki çiftleri verir; 2023.. gibi açık uçlu aralıklar da çalışır. first_key_value ve last_key_value en küçük ve en büyük anahtarlı çifti Option içinde döndürür; pop_first ve pop_last ise bu çifti çıkarır. Son örnekte harf sayımı da sıralı çıktı: HashMap ile aynı kod her çalıştırmada farklı sırada yazdırabilirdi.

Belgeye göre BTreeMap'te arama, ekleme ve silme logaritmik süre alır, HashMap'te ise beklenen süre sabittir. Yani yalnızca anahtarla arama yapıyor ve sıraya ihtiyaç duymuyorsanız HashMap genellikle iyi bir başlangıçtır; sıralı gezme, aralık sorgusu ya da "şundan büyük en küçük anahtar" gibi sorular gerekiyorsa BTreeMap doğru seçimdir. Anahtar tipinizi sıralanabilir yapmak için #[derive(PartialEq, Eq, PartialOrd, Ord)] kullanabilirsiniz; ayrıntılar Rust derive yazısında.

Metin anahtarlarda sıralamanın Türkçe alfabe kurallarına göre yapılmadığını da bilmeniz gerekir. Aşağıdaki örnekte "çay" anahtarı "simit"ten sonra, en sona yerleşti; "börek" ise "ayran" ile "simit" arasına girdi çünkü ilk harfi ASCII'dir. pop_first en küçük anahtarlı çifti çıkarıp döndürdü:

use std::collections::BTreeMap;

fn main() {
    let mut fiyat = BTreeMap::new();
    fiyat.insert("simit", 15);
    fiyat.insert("ayran", 20);
    fiyat.insert("çay", 10);
    fiyat.insert("börek", 40);
    println!("{fiyat:?}");
    println!("en küçük anahtar: {:?}", fiyat.pop_first());
    println!("kalan: {fiyat:?}");
}
// çıktı: {"ayran": 20, "börek": 40, "simit": 15, "çay": 10}
// çıktı: en küçük anahtar: Some(("ayran", 20))
// çıktı: kalan: {"börek": 40, "simit": 15, "çay": 10}

Kullanıcıya Türkçe alfabe sırasıyla liste göstermeniz gerekiyorsa, anahtar olarak metnin kendisi yerine harfleri Türkçe sıraya göre karşılaştıran kendi tipinizi (Ord uygulayarak) kullanmanız gerekir. Modül belgesi bir uyarı daha yapar: karmaşık anahtarlarda insert değeri günceller ama anahtarı güncellemez; yalnızca bir alana göre karşılaştırılan bir struct anahtarı ikinci kez eklendiğinde map ilk eklenen anahtarı korur.

HashSet ve BTreeSet: kümeler

Bir değerin yalnızca var olup olmadığıyla ilgileniyorsanız ve ona eşlik eden anlamlı bir değer yoksa küme kullanılır. insert bir bool döndürür: değer kümede yoksa true, zaten varsa false. Bu dönüş değeri "bunu ilk kez mi görüyorum?" sorusunun cevabıdır ve aşağıdaki örneğin son satırında tekilleştirme için kullanılıyor. Kümeler matematikteki küme işlemlerini de sunar:

use std::collections::{BTreeSet, HashSet};

fn main() {
    let mut gorulen = HashSet::new();
    println!("{}", gorulen.insert("ankara"));
    println!("{}", gorulen.insert("ankara"));
    println!("{} {}", gorulen.len(), gorulen.contains("ankara"));

    let a: BTreeSet<i32> = [1, 2, 3, 4].into_iter().collect();
    let b: BTreeSet<i32> = [3, 4, 5].into_iter().collect();
    println!("kesişim: {:?}", a.intersection(&b).collect::<Vec<_>>());
    println!("birleşim: {:?}", a.union(&b).collect::<Vec<_>>());
    println!("fark: {:?}", a.difference(&b).collect::<Vec<_>>());
    println!("simetrik fark: {:?}", a.symmetric_difference(&b).collect::<Vec<_>>());

    let x: HashSet<&str> = HashSet::from(["kedi", "köpek"]);
    let y: HashSet<&str> = HashSet::from(["kedi", "kuş"]);
    let mut ortak: Vec<_> = x.intersection(&y).collect();
    ortak.sort();
    println!("ortak: {ortak:?}");

    let mut liste = vec![3, 1, 3, 2, 1, 4];
    let mut tekil = HashSet::new();
    liste.retain(|n| tekil.insert(*n));
    println!("sırayı koruyan tekilleştirme: {liste:?}");
}
// çıktı: true
// çıktı: false
// çıktı: 1 true
// çıktı: kesişim: [3, 4]
// çıktı: birleşim: [1, 2, 3, 4, 5]
// çıktı: fark: [1, 2]
// çıktı: simetrik fark: [1, 2, 5]
// çıktı: ortak: ["kedi"]
// çıktı: sırayı koruyan tekilleştirme: [3, 1, 2, 4]

intersection, union, difference ve symmetric_difference yeni küme oluşturmaz, elemanlara referans veren birer iterator döndürür; sonucu saklamak isterseniz collect ile toplarsınız. BTreeSet elemanları sıralı tuttuğu için bu iterator'lar da sıralı sonuç verir. HashSet'te sıra belirsiz olduğundan örnekte sonucu ayrıca sıraladık. Ayrıca is_subset, is_superset ve is_disjoint metotları iki küme arasındaki ilişkiyi bool olarak verir.

BTreeSet, BTreeMap'in sıralı olmaktan gelen yeteneklerini kümeye taşır: range ile bir aralıktaki elemanları, first ve last ile en küçük ve en büyük elemanı alabilirsiniz. Aşağıdaki örnek, dolu randevu saatlerini tutan bir kümeden öğleden sonraki dolu saatleri ve gün içindeki boş saatleri çıkarıyor:

use std::collections::BTreeSet;

fn main() {
    let dolu_saatler: BTreeSet<u32> = [9, 10, 13, 14, 16].into_iter().collect();
    let ogleden_sonra: Vec<_> = dolu_saatler.range(12..).collect();
    println!("{ogleden_sonra:?}");
    println!("ilk: {:?}, son: {:?}", dolu_saatler.first(), dolu_saatler.last());
    let bos = (9..18).filter(|s| !dolu_saatler.contains(s)).collect::<Vec<_>>();
    println!("boş saatler: {bos:?}");
}
// çıktı: [13, 14, 16]
// çıktı: ilk: Some(9), son: Some(16)
// çıktı: boş saatler: [11, 12, 15, 17]

Son satırdaki desen, pratikte sık işe yarayan bir hiledir. Vec yazısında gördüğümüz dedup yalnızca art arda gelen tekrarları siler ve sırasız veride önce sıralamayı gerektirir; bu da ilk görülme sırasını bozar. retain içinde HashSet::insert kullanmak ise her değerin ilk görüldüğü yeri korur, sonraki tekrarları siler. retain elemanları orijinal sırayla ve her birini tam bir kez ziyaret ettiği için bu yöntem güvenilirdir.

VecDeque: iki uçlu kuyruk

VecDeque büyüyebilen bir halka tampon (ring buffer) üzerine kuruludur ve hem başa hem sona sabit sürede ekleme ve çıkarma yapabilir. Belgenin tarif ettiği varsayılan kuyruk kullanımı push_back ile arkaya eklemek, pop_front ile önden almaktır. Vec::remove(0) her çağrıda bütün elemanları kaydırırken VecDeque::pop_front bunu yapmaz; Vec belgesi de baştan çıkarma için VecDeque'i önerir.

use std::collections::VecDeque;

fn main() {
    let mut kuyruk = VecDeque::new();
    kuyruk.push_back("müşteri 1");
    kuyruk.push_back("müşteri 2");
    kuyruk.push_front("acil müşteri");
    println!("{kuyruk:?}");

    while let Some(siradaki) = kuyruk.pop_front() {
        println!("hizmet: {siradaki}");
    }

    let mut son_uc = VecDeque::with_capacity(3);
    for olcum in [10, 20, 30, 40, 50] {
        if son_uc.len() == 3 {
            son_uc.pop_front();
        }
        son_uc.push_back(olcum);
    }
    println!("son üç ölçüm: {son_uc:?}");
    println!("ön: {:?}, arka: {:?}, [1]: {}", son_uc.front(), son_uc.back(), son_uc[1]);
    let dilim = son_uc.make_contiguous();
    dilim.sort_by(|a, b| b.cmp(a));
    println!("tersten sıralı: {son_uc:?}");
}
// çıktı: ["acil müşteri", "müşteri 1", "müşteri 2"]
// çıktı: hizmet: acil müşteri
// çıktı: hizmet: müşteri 1
// çıktı: hizmet: müşteri 2
// çıktı: son üç ölçüm: [30, 40, 50]
// çıktı: ön: Some(30), arka: Some(50), [1]: 40
// çıktı: tersten sıralı: [50, 40, 30]

İkinci örnek, son N değeri tutan kayan pencere desenidir: pencere dolunca en eski değer önden atılır, yenisi arkaya eklenir. VecDeque indeksle erişimi (son_uc[1]) ve front/back ile uçlara bakmayı da destekler. Halka tampon olduğu için elemanlar bellekte her zaman tek parça durmaz; sort gibi bir dilim metodu kullanmak istediğinizde belgenin önerdiği make_contiguous elemanları tek parça hâline getirip değiştirilebilir bir dilim döndürür. Kuyrukların iş parçacıkları arasında kullanılması ise farklı bir konudur; bunun için Rust mpsc kanalları yazısına bakın.

BinaryHeap: öncelik kuyruğu

BinaryHeap ikili yığın (binary heap) ile gerçeklenmiş bir öncelik kuyruğudur ve belgede açıkça belirtildiği gibi bir max-heap'tir: pop her zaman en büyük elemanı verir, peek çıkarmadan ona bakar. En küçüğü almak istediğinizde belge iki yol önerir: değerleri std::cmp::Reverse ile sarmak ya da kendi Ord uygulamanızı yazmak. Tuple'lar ilk alandan başlayarak karşılaştırıldığı için (öncelik, iş) çiftleri basit bir görev kuyruğu kurmanın kısa yoludur:

use std::cmp::Reverse;
use std::collections::BinaryHeap;

fn main() {
    let mut yigin = BinaryHeap::from([3, 9, 1, 7]);
    println!("peek: {:?}", yigin.peek());
    yigin.push(5);
    while let Some(en_buyuk) = yigin.pop() {
        print!("{en_buyuk} ");
    }
    println!();

    let mut min = BinaryHeap::new();
    for n in [3, 9, 1, 7] {
        min.push(Reverse(n));
    }
    if let Some(Reverse(en_kucuk)) = min.pop() {
        println!("en küçük: {en_kucuk}");
    }

    let mut gorevler = BinaryHeap::new();
    gorevler.push((2, "rapor yaz"));
    gorevler.push((5, "sunucu çöktü"));
    gorevler.push((1, "kahve al"));
    while let Some((oncelik, is)) = gorevler.pop() {
        println!("{oncelik}: {is}");
    }

    let sirali = BinaryHeap::from([4, 1, 3]).into_sorted_vec();
    println!("{sirali:?}");
}
// çıktı: peek: Some(9)
// çıktı: 9 7 5 3 1
// çıktı: en küçük: 1
// çıktı: 5: sunucu çöktü
// çıktı: 2: rapor yaz
// çıktı: 1: kahve al
// çıktı: [1, 3, 4]

Dikkat edilmesi gereken bir nokta: for x in &heap ile gezdiğinizde belge elemanların rastgele bir sırayla geleceğini söyler; sıralı sonuç yalnızca art arda pop çağırarak ya da into_sorted_vec ile alınır (bu metot artan sırada bir vektör döndürür). Ayrıca yığın içindeyken bir elemanın diğerlerine göre sırasını değiştirecek şekilde değiştirilmesi, HashMap'teki anahtar kuralına benzer bir mantık hatasıdır.

LinkedList hakkında

LinkedList düğümleri ayrı ayrı ayrılan çift bağlı bir listedir. Modül belgesi onu üç durumda önerir: boyutu bilinmeyen ve amortize maliyete tahammül edilemeyen bir dizi gerektiğinde, listeleri verimli şekilde bölüp birleştirmek istediğinizde ve gerçekten çift bağlı liste istediğinizden kesinlikle emin olduğunuzda. Aynı belge, eşit karmaşıklıktaki işlemlerde Vec'in genellikle VecDeque'ten, VecDeque'in de LinkedList'ten daha hızlı olacağını not eder. Pratikte ilk tercihiniz neredeyse her zaman Vec ya da VecDeque olmalıdır.

Performans karşılaştırması

Aşağıdaki tablo modül belgesindeki maliyet tablosunun özetidir. n koleksiyonun boyutu, i indeks, m eklenen ikinci koleksiyonun boyutudur. Yıldız (*) amortize maliyeti, tilde (~) beklenen maliyeti gösterir. Amortize maliyet, arada bir yapılan büyütmenin uzun bir işlem dizisine yayılmış ortalamasıdır; tek bir işlem bu değerden yavaş olabilir. HashMap'in beklenen maliyeti ise olasılığa dayanır: belge kuramsal olarak çok daha kötü performansın mümkün ama çok olası olmadığını söyler. Kümeler, karşılık gelen sözlükle aynı maliyete sahiptir.

Belgenin hatırlattığı iki genel kural daha var. Birincisi, Rust koleksiyonları kendiliğinden küçülmez; bu yüzden silme işlemleri amortize değildir ve belleği geri vermek için shrink_to_fit çağırmanız gerekir. İkincisi, kaç eleman geleceğini biliyorsanız with_capacity ile, büyük bir eleman akışı bekliyorsanız reserve ile koleksiyona önceden ipucu verebilirsiniz. Bir koleksiyondan diğerine geçmenin en kolay yolu ise iterator'lardır: let kuyruk: VecDeque<_> = vec.into_iter().collect(); gibi bir satır, veriyi taşıyarak dönüşümü yapar. Ayrıntılar Rust iterator yazısında.

Hangi koleksiyonu seçmeliyim? Kısa bir karar listesi

• Elemanları sırayla toplayıp sonra işleyecekseniz ya da yalnızca sona ekleyip sondan çıkarıyorsanız: Vec.
• İlk giren ilk çıkar (FIFO) kuyruğu, iki uçtan ekleme ya da son N değer penceresi: VecDeque.
• Anahtarla değer bulmak ve sıra önemli değil: HashMap.
• Anahtarlar sıralı gezilecek, aralık sorgusu ya da en küçük/en büyük anahtar lazım: BTreeMap.
• Yalnızca "var mı yok mu" bilgisi, tekilleştirme ya da kesişim/birleşim: HashSet, sıralı sonuç gerekiyorsa BTreeSet.
• Her adımda en büyük ya da en acil elemanı işlemek: BinaryHeap, en küçük için Reverse ile.

Sık yapılan hatalar

• HashSet çıktısının sıralı olacağını beklemek: Küme işlemlerinin sonucu da belirsiz sırayla gelir; sıra gerekiyorsa BTreeSet kullanın ya da sonucu sıralayın.
• BinaryHeap'i döngüyle gezip sıralı sanmak: for ile gezme sırası belirsizdir; sıralı sonuç için pop ya da into_sorted_vec kullanın.
• Kuyruk için Vec::remove(0) kullanmak: Her çağrıda bütün elemanlar kayar. Baştan çıkarma için VecDeque::pop_front var.
• BTreeMap anahtarı olarak Ord uygulamayan bir tip kullanmak: f64 gibi tipler Ord uygulamaz; derleyici bunu bir trait sınırı hatası olarak bildirir. Bu tür hatalar E0277 ve E0308 tip hataları yazısında.
• Gereksiz yere LinkedList seçmek: Belge bile bunu yalnızca gerçekten gerektiğinde önerir; çoğu durumda Vec ya da VecDeque daha hızlıdır.

Sık Sorulan Sorular

HashSet ile Vec::contains arasında ne fark var?

Vec::contains elemanları tek tek karşılaştırır, yani süresi eleman sayısıyla artar. HashSet::contains ise beklenen sabit sürede çalışır. Az elemanlı ve nadiren aranan bir liste için vektör yeterlidir; çok sayıda arama yapılacaksa küme tercih edilir.

BTreeMap'te belirli bir değerden büyük ilk anahtarı nasıl bulurum?

map.range(x..).next(), x'e eşit ya da ondan büyük ilk çifti verir. Kesin olarak büyük olanı istiyorsanız std::ops::Bound ile dışlayıcı alt sınır kullanabilirsiniz. Modül belgesi bu tür sorguları BTreeMap'in tipik kullanım alanı olarak sayar.

Kendi struct'ımı BinaryHeap'te nasıl sıralarım?

Struct'ın Ord uygulaması gerekir. Önceliğe göre sıralamak için Ord'u elle yazıp yalnızca öncelik alanını karşılaştırabilir ya da alanların sırasını önceliği en başa koyacak şekilde düzenleyip derive kullanabilirsiniz. Trait uygulama ayrıntıları Rust trait tanımlama yazısında.

Bu koleksiyonlar iş parçacıkları arasında paylaşılabilir mi?

Hepsi sıradan sahipli değerlerdir; paylaşılan değiştirilebilir erişim için Arc<Mutex<...>> gibi bir sarmalayıcı gerekir. Bu konu Rust Arc ve Mutex yazısında.

Marka adları sahiplerine aittir. Bu yazı bağımsız bir teknik rehberdir; adı geçen kuruluşlarla bayilik veya ortaklık ilişkisi bulunduğu anlamına gelmez.

İlgili içerikler: Rust öğrenme rehberi · Vec kullanımı · HashMap kullanımı · Iterator · Derive · Arc ve Mutex