17 Aralık 2020 Perşembe

std::unique metodu

Giriş
Açıklaması şöyle
Removes all but the first element from every consecutive group of equivalent elements in the range [first,last).
std::unique() ile bir collection içindeki ardışık ve eşit olan değerlerden sadece bir tanesi bırakılır, diğerleri silinir. std::unique() metodunu kullanırken dikkat edilmesi gereken koşul, collection'ın sıralı olmuş olması değil, eşit değerlerin ardışık olarak gelmesi. Tabii ki bu işi sağlamanın en kolay yolu da aslında collection'ı sıralamak :)

Silme işlemi elemanları kaydırarak yapılır. Açıklaması şöyle
Removing is done by shifting the elements in the range in such a way that elements to be erased are overwritten.
Eğer Collection Sıralı Değilse
- Eğer elimizdeki collection sıralı değilse std::map veya türevi rahatlıkla kullanılabilir.
Örnek
Şöyle yaparız
std::vector<int> c{1,2,2,4,5,5,6};
std::unordered_multiset<int> unique( c.begin(), c.end() );
c.erase(std::remove_if(c.begin(),c.end(),
[&](const auto& e){return unique.count(e)>1;}),c.end());
Örnek
std::remove_if() kullanarak şöyle yaparız. Bu yöntem verimsiz!
std::vector<int> V {1,2,2,4,5,5,6};

auto it = std::remove_if(V.begin(), V.end(), [&](const auto& val) 
{ 
  return std::count(V.begin(), V.end(), val) > 1;
});

V.erase(it, V.end());
Örnek
std::find() kullanarak şöyle yaparız. Bu yöntem verimsiz!
void keep_unique(std::vector<int>& v){
  auto it = v.begin();
  auto w = v.begin();
  while (it != v.end())
  {
    auto next = std::find_if(it, v.end(), [&](int e){ return e != *it; });
    if (std::distance(it, next) == 1) {
      if (w != it) {
        *w = std::move(*it);
      }
      ++w;
    }
    it = next;
  }
  v.erase(w, v.end());
}
Klasik kullanım şablonu
Bu kullanıma ben erase-unique idiom diyorum. Aynı erase-remove idiom gibi kullanılıyor.
Silinen elemanlar std::unique() metodunun döndürdüğü iterator'ün sonunda bir yere taşınıyorlar. Bu elemanları silmek için de erase() veya resize() gibi bir metod kullanılır. Dolayısıyla klasik kullanımı şöyledir.
Bir vector nesnemiz olsun.
std::vector<int> gid; 
Bu nesne içindeki eşit olanları silmek için önce sort() ile sıralarız. Daha sonra unique() ile eşit olanları sona taşırız. unique() işleminin sonucundan itibaren olanları sileriz.
std::sort(gid.begin(),gid.end());
std::vector<int>::iterator itv(std::unique(gid.begin(),gid.end()));
gid.erase(itv,gid.end());
unique metodu - ForwardIt first + ForwardIt last
Bu metod nesneleri == operator ile karşılaştırıyor. Algoritma şuna benziyor. Önce 3 iterator tanımlanır.
In = Out = First
Daha sonra baştan itibaren yürürüz. Eğer In, şu anki Out'tan farklıysa, Out bir artırılır ve In'in değeri Out'a kopyalanır.
while (++In != Last)
{
  if !(*In == *Out)
  {
    ++Out;
    *Out = *In;
  }
}
Örnek
== operatörü genellikle birden çok alan için kullanılır. En kolay kodlanma şekli şöyledir.
bool Packet::operator==(const Packet& rhs) const
{
  if (getFilingTime() != rhs.getFilingTime())
    return false;
  if (getSpid() != rhs.getSpid())
    return false;
  return true;
}
Bir sürü şeyi and'lemek zorunda kaldığımız kodları sevmiyorum
bool operator==(const Packet& p) const {
  return fillingTime == p.fillingTime && recordID == p.recordID;
}
unique metodu - ForwardIt first + ForwardIt last + BinaryPredicate comparator
Örnek
Şöyle bir sınıfımız olsun. X ve Y değerleri aynı olanları silmek istiyor olalım.
// Sample coordinate class 
class P {
public:
    int x;
    int y;
    P() : x(0), y(0) {}
    P(int i, int j) : x(i), y(j) {}
};
Önce sıralama işlemi için bir comparator tanımlanır. Bu comparator sort() algoritması için gerekir.
// Tells us if one P is less than the other
bool less_comp(const P& p1, const P& p2) {

  if(p1.x > p2.x)
    return false;
  if(p1.x < p2.x)
    return true;

  // x's are equal if we reach here.
  if(p1.y > p2.y)
    return false;
  if(p1.y < p2.y)
    return true;

  // both coordinates equal if we reach here.
  return false;
}
Daha sonra eşitlik işlemi için bir başka comparator kullanılır. Bu comparator unique() algoritması için gerekir.
// Self explanatory
bool equal_comp(const P& p1, const P& p2) {

  if(p1.x == p2.x && p1.y == p2.y) 
    return true;

  return false;
}
Sonuncu  işlemde
int main()
{
  vector<P> v;
  v.push_back(P(1,2));
  v.push_back(P(1,3));
  v.push_back(P(1,2));
  v.push_back(P(1,4));

  // Sort the vector. Need for std::unique to work.
  std::sort(v.begin(), v.end(), less_comp);

  // Collect all the unique values to the front.
  std::vector<P>::iterator it;
  it = std::unique(v.begin(), v.end(), equal_comp);
  // Resize the vector. Some elements might have been pushed to the end.
  v.resize( std::distance(v.begin(),it) );

  // Print out.
  std::copy(v.begin(), v.end(), ostream_iterator<P>(cout, "\n"));

}
Örnek - lambda
Aslında lambda ile comparator aynı. Ancak yine de yazmak istedim. Elimizde arka arkaya "" karakteri içeren bir string olsun. Bu çift karakteri tek bir " karakteri ile değiştirmek istersek şöyle yaparız.
std::string msg("\"Date\"\":1481200838,\"\"Message\"\":\"");
msg.resize(distance(begin(msg),
           unique(begin(msg), end(msg),
  [](const auto& a, const auto& b){ return a == '"' && b == '"'; })));
Örnek - Yanlış kullanım
Bir çok yerde < karşılaştırması yapan comparator hem sort hem de unique işlemi için kullanılıyor. Önce şöyle bir comparator tanımlanıyor.
bool compare(strcOfPoints const & lhs, strcOfPoints const & rhs) {
    return std::tie(lhs.p, lhs.c) < std::tie(rhs.p, rhs.c);
}
Daha sonra sort yapılıyor.
vector<strcOfPoints> strpts = { s1, s2, s3, s4, s5, s6, s7 };
std::sort(strpts.begin(), strpts.end(), compare);
En son olarak çiftler siliniyor.
strpts.erase(
  std::unique(strpts.begin(), strpts.end(), compare),
  strpts.end());
Diğer Notlar
Bu algoritma C#taki Enumerable.Distinct ile benzer işi yapıyor. Aradaki fark ise C# verilen IEnumerable dizisinde eşit değerlerin ardışık gelmesini şart koşmaması

Örnek
Şöyle yaparız
new []{1,3,2,2,3,1}.Distinct().Dump(); //1,3,2 verir

Hiç yorum yok:

Yorum Gönder