Haftalık C++ - 1 ("Erase-remove idiom") - Yazılımperver'in Dünyası

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.

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

void printList(const auto& list)
{
    for(const auto& element : list)
        cout << element << " ";

    cout << endl;
}

int main()
{
    // Geleneksel yontem
    // Ornek vektor
    vector<int> list {10, 20, 30, 40, 40, 50, 60, 70, 80};
    vector<int> secondList = list;
    vector<int> thirdList = list;

    // Simdi bu listeden 40 sayilarini silelim
    list.erase(begin(list) + 3, begin(list) + 5);

    // Listeye bakalim. Gorulecegi uzere elemanlar fiziksel olarak siliniyor
    printList(list);
    
    // Simdi std::remove durumunda ne olduguna bakalim
    std::remove(secondList.begin(), secondList.end(), 40);
    
    // Silinen elemanlar yerine kalanlarin kaydirildigina dikkat edin, fakat boyut degismiyor
    // Son iki elemanda, bir onceki listedeki son iki eleman olarak degisitine dikkat edin(tanimsiz davranis dedigimiz bu aslinda)
    printList(secondList);

    // Son olarak Erase - remove idiom" kullanimina bakalim. Tek satir ile olayi cozuyoruz.
    printList(thirdList);
    thirdList.erase(std::remove(thirdList.begin(), thirdList.end(), 40), thirdList.end());
    printList(thirdList);

    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void printList(const auto& list)

{

for(const auto& element : list)

cout << element << " ";

cout << endl;

}

int main()

{

// Geleneksel yontem

// Ornek vektor

vector<int> list {10, 20, 30, 40, 40, 50, 60, 70, 80};

vector<int> secondList = list;

vector<int> thirdList = list;

// Simdi bu listeden 40 sayilarini silelim

list.erase(begin(list) + 3, begin(list) + 5);

// Listeye bakalim. Gorulecegi uzere elemanlar fiziksel olarak siliniyor

printList(list);

// Simdi std::remove durumunda ne olduguna bakalim

std::remove(secondList.begin(), secondList.end(), 40);

// Silinen elemanlar yerine kalanlarin kaydirildigina dikkat edin, fakat boyut degismiyor

// Son iki elemanda, bir onceki listedeki son iki eleman olarak degisitine dikkat edin(tanimsiz davranis dedigimiz bu aslinda)

printList(secondList);

// Son olarak Erase - remove idiom" kullanimina bakalim. Tek satir ile olayi cozuyoruz.

printList(thirdList);

thirdList.erase(std::remove(thirdList.begin(), thirdList.end(), 40), thirdList.end());

printList(thirdList);

return 0;

}

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

Kaynaklar:

Paylaşmak güzeldir.

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

Bir cevap yazın Cevabı iptal et