18 Eylül 2017 Pazartesi

STL Remove Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor.

Remove işlemlerinde == operatörünü gerçekleştirmemiz gerekebilir.

remove
Verilen değeri çıkarır. İmzası şöyledir. Çıkarılan eleman referans ile metoda geçilir. Metod çıkarma işleminden sonra kalan yeni aralığın sonunu döner.
template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator f, ForwardIterator l, const T& val);
Metod, elemanların eşitliğini kontrol etmek için == işlemi yapar. Dolayısıyla elemanımız için == operatörünü gerçekleştirmemiz gerekebilir.

Aşağıda doğruluğundan çok emin olmadığım bir remove algoritması var.
template <class ForwardIterator, class T>
ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator result = first;
  while (first!=last) {
    if (!(*first == val)) {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
 }

Vector'ün kendi içinden bir elemanı çıkartmaya çalışan bu kod, tüm elemanlar invalidate edildiği için yanlıştır.
vector<int> a = {1,2,3,7,1,5,4};
a.erase(remove(a.begin(),a.end(),a[0]),a.end());
Düzeltmek için şöyle yapılır.
int toberemoved = a[0];
a.erase(remove(a.begin(),a.end(),toberemoved),a.end());

remove_if
Metodun imzası şöyle
template< class ForwardIt, class UnaryPredicate >
ForwardIt remove_if( ForwardIt first, ForwardIt last, UnaryPredicate p );
Verilen koşulu sağlayan elemanlar [begin, middle) arasında bir yere doldurulurlar. 

C++11'den önce
C++11'den önce move semantics kullanmayan kod şöyleydi. Yani assignment kullanıyordu.
template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, 
                          UnaryPredicate p)
{
  ForwardIt result = first;
  for (; first != last; ++first) {
    if (!p(*first)) {
      *result++ = *first;
    }
  }
  return result;
}
C++11'den sonra
C++11'den sonra move semantics kullanılır
template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
  first = std::find_if(first, last, p);
  if (first != last)
    for(ForwardIt i = first; ++i != last; )
      if (!p(*i))
        *first++ = std::move(*i);
  return first;
}
Koşulu Sağlamayanlar
Koşulu sağlamayan elemanların ise middle'dan sonraki alanlara yerleştirilirler. Bu elemanların tanımsız olduğunu kabul etmek gerekir. Eğer remove_if basit bir std::swap kullansaydı bu tanımsızlık ortadan kalkabilirdi.
std::vector<std::string> vec = { "0", "1", "5", "0", "3", "6", "0", "1" };
std::remove_if(std::begin(vec), std::end(vec), [](const std::string& val)
{
    return val == "0";
});
Çağrı sonucu vector şu hale gelir.
1 5 3 6 1 ? ? ?
remove_if ve erase'in beraberliği
Metod koşulu sağlamayan elemanların başladığı yeri iteratör olarak döndürür.
Dolayısıyla remove_if genelde erase ile beraber kullanılır
myList.erase(std::remove_if(myList.begin(), myList.end(),
    [](int& element) 
    { 
        return element > 5;
    } 
    ),myList.end());
Not 1 : std::list'in kendi remove_if metodu vardır.
Not 2  : remove_if koşulu sağlayanlar ve sağlamayanlar diye iki kısma ayırmak için uygun değildir. Bu iş için partition() algortiması kullanılabilir.

Eğer kaç tane eleman silindi diye bulmak istersek şöyle yaparız.
auto old_size = list.size();
auto new_end = std::remove_if(list.begin(), list.end(), ...);
auto new_size = std::distance(list.begin(), new_end);
auto deletions = old_size - new_size;

remove_copy
Örnek ver

remove_copy _if
Örnek
Elimizde şu kod olsun.
typedef struct mystruct {
  int id;
  std::string name;
};

std::vector<mystruct> v= {{151, "test1"}, {154, "test4"}, {152, "test2"}, {151, "test1"},
  {151, "test1"}, {153, "test3"}};
std::vector<int> bad_ids = {151, 152};
std::vector<mystruct> filter_items;
151 ve 152 değerlerini içermeye yeni bir dizi yaratmak için şöyle yaparız
std::remove_copy_if(
  v.begin(), 
  v.end(), 
  std::back_inserter(filter_items),
  [&bad_ids](const mystruct& item)
  { return std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end(); });
Eğer ilk diziyi değiştirmek istersek şöyle yaparız.
all_items.erase(
  std::remove_if(
    v.begin(), 
    v.end(), 
    [&bad_ids](const mystruct& item) 
    { return std::find(bad_ids.begin(), bad_ids.end(), item.id) != bad_ids.end(); }), 
  v.end());

Hiç yorum yok:

Yorum Gönder