Cevap

std::vector ve std::list — farklı STL konteynerleri, uygulama ve davranışları farklıdır.

• std::vector dinamik bir dizi uygular, elemanlar bellekte sürekli olarak yer alır. İndeksleme için hızlı erişim (O(1)), sona ekleme için hızlı (amortize O(1)), ortada ekleme ve silme için pahalıdır (O(n)), çünkü elemanlar kaydırılır.
• std::list — çift yönlü bir listedir. Rastgele erişim yavaştır (O(n)), listenin herhangi bir yerinde hızlı ekleme ve silmeler (O(1)), bellek üzerindeki yük (her eleman için iki gösterici) ve sık sık yer ayrımı/serbest bırakma işlemleri vardır.

Ne zaman seçim yapılmalı:

• std::vector'ı hemen hemen her zaman kullanın, ortada sık sık ekleme/silme yapılması gerekiyorsa durum hariç.
• std::list yalnızca büyük veri setlerinde, hangi yerde olursa olsun ekleme/silmelere ihtiyaç varsa mantıklıdır, çünkü vektörün elemanlarını kaydırmak çok pahalıdır.
• Küçük koleksiyonlar için, ortada ekleme gerekse bile, std::vector genellikle veri yerelleştirmesi nedeniyle daha hızlıdır.

Örnek:

std::vector<int> v;
v.push_back(1);
v[0] = 2; // indeksle hızlı erişim

std::list<int> l;
l.push_back(1);
// l[0] = 2; // Hata: std::list'in indeksle erişimi yoktur!

Kurnaz bir soru

"Neden modern C++ projelerinde std::list neredeyse hiç kullanılmıyor, oysa ortada sıkız ekleme yapmanın teorik avantajı var?"

Cevap: Pratikte, birçok küçük yer ayrımı, veri yerelleştirmesinin kaybı (cache dostu), yapının hantallığı ve bazı işlemlerin yetersiz desteklenmesi nedeniyle std::list etkisizdir. (Hatta büyük listelerde bile yer ayrımı ve serbest bırakma için harcanan zaman kayıpları nedeniyle verimsizdir, ayrıca bellek boşlamalarının neden olduğu gecikmeler çoğu zaman asimptotik kazançları geçersiz kılar). Ayrıca modern işlemciler cache locality'ye karşı çok hassastır, bu nedenle büyük veri setleri bile işlenirken std::vector genellikle daha hızlıdır.

Bilgi eksikliğinden kaynaklanan gerçek hata örnekleri

---

Hikaye

Gerçek zamanlı sistemlerde olay kuyruklarını saklamak için std::list seçilmiştir, çünkü rastgele yerlerden hızlı silmeler gerekiyordu. Sonuç olarak sistem, bellek heap'ine sık erişim nedeniyle 10 kat yavaşladı ve veri yerelleştirmesinde kötü sonuçlar doğurdu.

---

Hikaye

Grafik işlemcisi, ekleme yapmak için std::list biçiminde komşu dizilerini sakladı. Bu, bellek kullanımında dramatik bir artışa ve L1/L2 cache'lerin bozulmasına yol açtı, buna rağmen hız konusunda gerçek bir fayda elde edilemedi.

---

Hikaye

Rapor oluşturma hizmetinde, her rapor Linked List nesnelerinden oluşturuldu. Stres testlerinde hizmet "yavaşladı" ve profil çıkarma, listelerle çalışırken yer ayrımı giderlerinde dar boğazları gösterdi. Vektöre geçildi - sonuçlar kat kat iyileşti.