Haftalık C++ – 1 (“Erase-remove idiom”)

Merhaba sevgili Yazılımperver dostlarım. Bu yazım ile birlikte yeni bir yazı serisine (Haftalık C++) yelken açıyoruz. Bu yazılar, daha önce Modern C++ başlığı ile yoğun bir şekilde işlediğimiz C++ 11 yazılarına nazaran çok daha kısa kod parçaları veya konular içeriyor olacak. Bu kodların büyük kısmını, benim kullandığım kodlardan, ya da kitap veya internette gördüğüm kütüphane veya benzeri kaynaklardan derliyor olacağım. Günlük geliştirdiğiniz yazılımlarda karşılaştığınız problemleri çözmesi dileğiyle ilk yazımıza başlayalım.

İlk yazımızın konusu “Erase-remove idiom” olacak. Peki ne demek bu kavram ve nereden geliyor. C++’da belirli kriterleri sağlayan elemanların konteynerlerden verimli bir şekilde silinmesi tekniğine “Erase-remove idiom“, deniliyor. Bu elemanlar bir for döngüsü kullanarak bunları silinebilse de, bu yöntem ile bu iş daha verimli bir şekilde gerçekleştirilebiliyor.

Bunun için de C++ 17 ile birlikte STL’e dahil edilen std::remove metotlarını ve ilgili konteynerlerde bulunan erase metodunu kullanacağız.

erase ile remove metotları arasındaki temel farklılık: erase ilgili elemanı sildiği durumda kalan bütün elemanlar kopyalanıyor. Bunun yanında remove metodu ise ilgili elemanları silmek yerine yerlerini değiştiriyor. Bu durumda for loopu kullanarak sadece erase metodu ile silmek O(N^2) ‘lik bir algoritma olsa da , bu yaklaşım ile O(N)‘lık bir algoritma elde edebiliyoruz. Tabi bu kullanımın tek tek silmelerde bize çok bir şey kazandırmayacağı aşikar.

Peki erase metodu burada ne yapıyor (aşağıda kanlı canlı bir örnek de var): silinemeyecek olan elemanları, silinecek olan elemanların önünde olacak şekilde sırayı ayarlıyor. Silinecek olan elemanlara ulaşılabilse de bunların değerleri tanımlı değil (örneğin aşağıdaki örnekte son iki eleman, daha önceki elemanlar ile dolduruluyor). Yani aslında konteynerin boyu değişmiyor ve bu metot sonucu dönülen iteratör de bu elemanlardan ilkini işaret ediyor ve çoğunlukla da bu erase metoduna geçirilerek fiziksel silme gerçekleştiriliyor.

Son bir not: bu yaklaşım const_iterator dönen set/map gibi konteynerler ile kullanılamıyor.

Bir sonraki yazımda görüşmek üzere. Sonrakiler daha kısa olacak yalnız 😉

Kaynaklar:

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

Bu site, istenmeyenleri azaltmak için Akismet kullanıyor. Yorum verilerinizin nasıl işlendiği hakkında daha fazla bilgi edinin.