Sequence Container'lar

Sequence container'lar, elemanları senin eklediğin sırada tutan veri yapılarıdır. Bir alışveriş listesi gibi düşün — ilk yazdığın madde en üstte, son yazdığın en altta kalır. Kimse sıranı değiştirmez.

Bu derste C++ STL'in dört temel sequence container'ını tanıyacağız: vector, deque, list ve forward_list. Her birinin farklı güçlü yönleri var ve doğru zamanda doğru container'ı seçmek, programının performansını dramatik şekilde etkiler.

std::vector — Dinamik Dizi

vector, C++ dünyasının en çok kullanılan container'ıdır. Eğer hangi container'ı kullanacağından emin değilsen, vector ile başla — çoğu zaman doğru cevap odur.

Bir elastik çorap çekmecesi gibi düşün: başlangıçta belli bir kapasitesi var, ama doldukça otomatik olarak büyür. Elemanlar bellekte yan yana (contiguous) durur — bu da CPU cache'i ile mükemmel uyum sağlar.

Temel Kullanım

#include <vector>
#include <iostream>

int main() {
    // Oluşturma yolları
    std::vector<int> v1;                    // Boş vector
    std::vector<int> v2(5, 0);              // 5 eleman, hepsi 0
    std::vector<int> v3 = {1, 2, 3, 4, 5}; // Initializer list

    // Eleman ekleme — sona
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);

    // Erişim
    std::cout << "Ilk: " << v1.front() << "\n";    // 10
    std::cout << "Son: " << v1.back() << "\n";      // 30
    std::cout << "v1[1]: " << v1[1] << "\n";        // 20
    std::cout << "v1.at(1): " << v1.at(1) << "\n";  // 20 (sınır kontrolü yapar)

    // Boyut ve kapasite
    std::cout << "Size: " << v1.size() << "\n";
    std::cout << "Capacity: " << v1.capacity() << "\n";

    return 0;
}

Kapasite ve Büyüme

Vector dolduğunda yeni, daha büyük bir bellek bloğu ayırır ve tüm elemanları oraya taşır. Bu yeniden tahsis (reallocation) işlemi maliyetlidir.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;

    std::cout << "Baslangic kapasitesi: " << v.capacity() << "\n";

    for (int i = 0; i < 20; ++i) {
        v.push_back(i);
        std::cout << "Size: " << v.size()
                  << " | Capacity: " << v.capacity() << "\n";
    }

    // Eğer eleman sayısını biliyorsan, önceden yer ayır
    std::vector<int> v2;
    v2.reserve(1000);  // 1000 eleman için yer ayır — reallocation olmaz
    std::cout << "Reserve sonrasi capacity: " << v2.capacity() << "\n";

    return 0;
}

💡 `reserve()` ile `resize()` farkı: reserve(100) sadece bellek ayırır, size değişmez. resize(100) ise gerçekten 100 elemanlık vector oluşturur (varsayılan değerle doldurur).

Eleman Silme

#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};

    // Sondan sil
    v.pop_back();  // 5 gitti

    // Belirli pozisyondan sil
    v.erase(v.begin() + 1);  // 2 gitti → {1, 3, 4}

    // Belirli değeri sil (remove-erase idiom)
    v = {1, 2, 3, 2, 4, 2, 5};
    v.erase(std::remove(v.begin(), v.end(), 2), v.end());
    // Tüm 2'ler silindi → {1, 3, 4, 5}

    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

⚠️ Vector'ün ortasından eleman silmek yavaştır — silinen noktadan sonraki tüm elemanlar bir pozisyon kaydırılır. Çok fazla ortadan silme yapıyorsan list düşün.

Vector Ne Zaman Kullanılır?

• Elemanlara indeks ile hızlı erişim lazımsa (O(1))

• Genellikle sona ekleme yapıyorsan (O(1) amortized)

• Cache-friendly performans istiyorsan

• Eleman sayısı büyük ölçüde tahmin edilebiliyorsa

std::deque — Çift Uçlu Kuyruk

deque (double-ended queue, "dek" diye okunur) hem baştan hem sondan O(1) ekleme ve silme yapabilir. Vector'dan farkı bu — vector'de başa ekleme O(n) maliyetindedir.

Bir akordeon gibi düşün: hem sağdan hem soldan genişleyebilir. İç yapısı, birbirine bağlı bellek bloklarından oluşur.

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {3, 4, 5};

    // Başa ekleme — vector'de bu yavaş, deque'te hızlı
    dq.push_front(2);
    dq.push_front(1);

    // Sona ekleme
    dq.push_back(6);
    dq.push_back(7);

    // İndeks ile erişim — vector gibi
    std::cout << "dq[0]: " << dq[0] << "\n";  // 1
    std::cout << "dq[3]: " << dq[3] << "\n";  // 4

    // Baştan ve sondan silme
    dq.pop_front();  // 1 gitti
    dq.pop_back();   // 7 gitti

    for (int x : dq) std::cout << x << " ";
    // Çıktı: 2 3 4 5 6
    std::cout << "\n";

    return 0;
}

Deque Ne Zaman Kullanılır?

• Hem baştan hem sondan ekleme/silme yapıyorsan

• Kuyruk (queue) veya çift uçlu kuyruk ihtiyacın varsa

• İndeks erişimi de lazımsa

Deque vs Vector

std::list — Çift Bağlı Liste

list, klasik çift bağlı liste (doubly linked list) yapısıdır. Her eleman, kendinden önceki ve sonraki elemana bir pointer tutar. Bellekte elemanlar dağınık durur.

Bir tren gibi düşün: her vagon (eleman) bağımsız, aralarında kancalar (pointer'lar) var. Ortaya yeni bir vagon eklemek çok kolay — sadece kancaları yeniden bağlarsın. Ama 5. vagona gitmek istersen, baştan sayarak gitmek zorundasın.

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 3, 5, 7, 9};

    // Başa ve sona ekleme
    lst.push_front(0);
    lst.push_back(10);

    // Ortaya ekleme — iterator ile
    auto it = lst.begin();
    std::advance(it, 3);  // 3. pozisyona ilerle
    lst.insert(it, 4);    // 4'ü ekle

    for (int x : lst) std::cout << x << " ";
    // Çıktı: 0 1 3 4 5 7 9 10
    std::cout << "\n";

    // Ortadan silme — O(1) (iterator varsa)
    it = lst.begin();
    std::advance(it, 2);
    lst.erase(it);  // 3'ü sil

    for (int x : lst) std::cout << x << " ";
    // Çıktı: 0 1 4 5 7 9 10
    std::cout << "\n";

    return 0;
}

List'in Özel Fonksiyonları

list'in STL algoritmalarından bağımsız, kendi üye fonksiyonları var. Bunlar listenin iç yapısından faydalandığı için daha verimlidir.

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {5, 3, 8, 1, 9, 3, 2};

    // Sıralama — list'in kendi sort'u
    lst.sort();
    // Çıktı: 1 2 3 3 5 8 9

    // Ardışık tekrarları sil
    lst.unique();
    // Çıktı: 1 2 3 5 8 9

    // Belirli değeri sil
    lst.remove(5);
    // Çıktı: 1 2 3 8 9

    // Koşula göre sil
    lst.remove_if([](int x) { return x > 5; });
    // Çıktı: 1 2 3

    for (int x : lst) std::cout << x << " ";
    std::cout << "\n";

    // İki sıralı listeyi birleştirme
    std::list<int> a = {1, 3, 5};
    std::list<int> b = {2, 4, 6};
    a.merge(b);  // b boşalır, a = {1, 2, 3, 4, 5, 6}

    for (int x : a) std::cout << x << " ";
    std::cout << "\n";

    return 0;
}

List Ne Zaman Kullanılır?

• Ortadan çok fazla ekleme/silme yapıyorsan

• Eleman sırasını korurken ekleme/silme önemliyse

• İndeks erişimine ihtiyacın yoksa

• Iterator'ların geçersizleşmemesi (invalidation) önemliyse

std::forward_list — Tek Bağlı Liste

forward_list, tek bağlı liste (singly linked list) yapısıdır. Her eleman sadece sonraki elemana pointer tutar — geriye gidemezsin. list'e göre daha az bellek kullanır (her eleman bir pointer yerine iki pointer tutmak zorunda değil).

#include <forward_list>
#include <iostream>

int main() {
    std::forward_list<int> fl = {1, 2, 3, 4, 5};

    // Sadece başa ekleme var — push_back YOK
    fl.push_front(0);

    // Belirli bir elemandan sonra ekleme
    auto it = fl.begin();
    std::advance(it, 2);
    fl.insert_after(it, 99);  // 2'den sonra 99 ekle

    for (int x : fl) std::cout << x << " ";
    // Çıktı: 0 1 2 99 3 4 5
    std::cout << "\n";

    // Belirli bir elemandan sonra silme
    it = fl.begin();
    fl.erase_after(it);  // Baştan sonraki elemanı sil (1'i)

    for (int x : fl) std::cout << x << " ";
    // Çıktı: 0 2 99 3 4 5
    std::cout << "\n";

    return 0;
}

⚠️ forward_list'te size() fonksiyonu yoktur — bu kasıtlıdır çünkü boyut tutmak ekstra maliyet getirir. Boyut gerekiyorsa std::distance(fl.begin(), fl.end()) kullanabilirsin ama bu O(n) maliyetindedir.

Forward List Ne Zaman Kullanılır?

• Minimum bellek kullanımı kritikse

• Sadece ileri yönde gezinme yeterliyse

• C tarzı bağlı liste davranışı istiyorsan

• Çok büyük veri setlerinde bellek tasarrufu önemliyse

Pratik gerçek: forward_list günlük C++ programlamada nadiren kullanılır. Ama gömülü sistemler veya bellek kısıtlı ortamlarda değerlidir.

Performans Karşılaştırma Tablosu

Bu tablo, hangi işlemin hangi container'da ne kadar hızlı olduğunu gösterir. Doğru container seçiminin anahtarı bu tablodur.

\* Amortized — reallocation olursa O(n) olabilir ama ortalamada O(1). \** Iterator zaten o konumda ise O(1). Konumu bulmak ayrı maliyet (O(n)).

Pratik Karar Rehberi

Container seçimi bazen kafa karıştırıcı olabilir. İşte hızlı bir karar ağacı:

Hangi container'ı kullanayım?
│
├── İndeks erişimi lazım mı?
│   ├── Evet → Başa ekleme yapıyor musun?
│   │   ├── Hayır → vector ✅
│   │   └── Evet → deque
│   └── Hayır ↓
│
├── Ortadan çok ekleme/silme var mı?
│   ├── Evet → Geri gezinme lazım mı?
│   │   ├── Evet → list
│   │   └── Hayır → forward_list
│   └── Hayır → vector ✅
│
└── Emin değil misin? → vector ✅

Altın kural: Şüphen varsa vector kullan. Çoğu durumda en hızlı olan odur — bellekte bitişik durması sayesinde modern CPU'lar onu çok sever.

Container Adaptörleri (Kısa Bakış)

STL'de sequence container'lar üzerine inşa edilmiş üç adaptör vardır. Bunlar yeni bir veri yapısı değil, mevcut container'ları farklı bir arayüzle sunarlar.

#include <stack>
#include <queue>
#include <iostream>

int main() {
    // Stack — LIFO (Last In, First Out)
    // Varsayılan: deque üzerine kurulu
    std::stack<int> stk;
    stk.push(1);
    stk.push(2);
    stk.push(3);
    std::cout << "Stack top: " << stk.top() << "\n";  // 3
    stk.pop();
    std::cout << "Stack top: " << stk.top() << "\n";  // 2

    // Queue — FIFO (First In, First Out)
    // Varsayılan: deque üzerine kurulu
    std::queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    std::cout << "Queue front: " << q.front() << "\n";  // 1
    q.pop();
    std::cout << "Queue front: " << q.front() << "\n";  // 2

    // Priority Queue — en büyük eleman her zaman üstte
    // Varsayılan: vector üzerine kurulu (max-heap)
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    std::cout << "PQ top: " << pq.top() << "\n";  // 4

    return 0;
}

Bu adaptörler doğrudan iterator sunmaz — sadece push, pop, top/front/back gibi kısıtlı arayüzler sunar. Bu kasıtlıdır: stack'te ortadaki elemana erişmek "mantıksal olarak" yanlış olur.

Gerçek Dünya Senaryosu

Bir öğrenci kayıt sistemi yazalım. Farklı ihtiyaçlar için farklı container'lar kullanalım:

#include <vector>
#include <deque>
#include <list>
#include <iostream>
#include <string>

struct Student {
    std::string name;
    int id;
    double gpa;
};

int main() {
    // Tüm öğrenciler — sık erişim, nadiren silme → vector
    std::vector<Student> allStudents = {
        {"Ali", 101, 3.5},
        {"Ayse", 102, 3.8},
        {"Mehmet", 103, 2.9},
        {"Zeynep", 104, 3.2}
    };

    // Bekleme kuyruğu — baştan çıkarma, sona ekleme → deque
    std::deque<Student> waitingQueue;
    waitingQueue.push_back(allStudents[2]);  // Mehmet sıraya girdi
    waitingQueue.push_back(allStudents[0]);  // Ali sıraya girdi

    // İşleme — ilk giren ilk çıkar
    Student next = waitingQueue.front();
    waitingQueue.pop_front();
    std::cout << "Sira: " << next.name << "\n";  // Mehmet

    // Aktif düzenleme listesi — sürekli ekleme/silme → list
    std::list<Student> editList(allStudents.begin(), allStudents.end());
    auto it = editList.begin();
    std::advance(it, 2);
    editList.erase(it);  // Mehmet'i listeden çıkar — O(1)

    std::cout << "Edit listesi:\n";
    for (const auto& s : editList) {
        std::cout << "  " << s.name << " (GPA: " << s.gpa << ")\n";
    }

    return 0;
}

emplace vs push

Modern C++'ta push_back yerine emplace_back kullanmak daha verimli olabilir. emplace_back nesneyi doğrudan container içinde oluşturur — gereksiz kopyalama veya taşıma olmaz.

#include <vector>
#include <string>
#include <iostream>

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {
        std::cout << "Point olusturuldu: " << x << ", " << y << "\n";
    }
};

int main() {
    std::vector<Point> points;

    // push_back — önce geçici nesne oluşur, sonra taşınır/kopyalanır
    points.push_back(Point(1.0, 2.0));

    // emplace_back — doğrudan container içinde oluşturulur
    points.emplace_back(3.0, 4.0);  // Constructor argümanları doğrudan

    std::cout << "Toplam: " << points.size() << " point\n";

    return 0;
}

💡 Kural: Yeni nesne oluşturuyorsan emplace_back, var olan nesneyi ekliyorsan push_back kullan. Ama pratikte modern derleyiciler farkı çoğu zaman optimize eder.

Özet

• `vector` en çok kullanılan container'dır — bellekte bitişik, indeks erişimi O(1), sona ekleme O(1). Şüpheye düşersen vector seç.

• `deque` hem baştan hem sondan O(1) ekleme/silme yapar — kuyruk yapıları için ideal.

• `list` çift bağlı listedir — ortadan ekleme/silme O(1) ama indeks erişimi O(n). Iterator invalidation riski düşüktür.

• `forward_list` tek bağlı listedir — minimum bellek kullanır, sadece ileri gezinir. Gömülü sistemlerde tercih edilir.

• Performans farkları genellikle cache locality'den kaynaklanır — vector bellekte bitişik durduğu için CPU cache'ten en çok faydalanan container'dır.

• emplace_back, push_back'e göre gereksiz kopyalama/taşımayı önler — yeni nesne oluştururken tercih et.