std::set_intersection metodu

Giriş
Açıklaması şöyle. İki kümenin kesişimini verir. Kesişim kümesi şeklen şöyledir.

set_intersection is an algorithm that produces a set of elements which are common to both sets. It is commutative, meaning that even the 2 sets are switched places, the algorithm returns the same result.

Bu metod sıralı olarak verilen iki collection için kesişim kümesini bulur. Java'daki retainAll metoduna benzer. Yalnız retainAll metodu collection'ların sıralı olmasını şart koşmaz ve kaynak collection'ı değiştirir. set_intersection ise collection'ları değiştirmez, kesişimi başka bir yere yazar. Kitaplarda gösterilen ve anlaması daha kolay olan standart algoritma şöyle.

if a[i] < b[j] then i++
if a[i] > b[j] then j++
else: add a[i] to intersection, i++, j++

Örnek
Bir sürü vector'ün kesişimini bulmak için şöyle yaparız.

std::vector<int> intersection (const std::vector<std::vector<int>> &vecs) {

  auto last_intersection = vecs[0];
  std::vector<int> curr_intersection;

  for (std::size_t i = 1; i < vecs.size(); ++i) {
    std::set_intersection(last_intersection.begin(), last_intersection.end(),
      vecs[i].begin(), vecs[i].end(),
      std::back_inserter(curr_intersection));
    std::swap(last_intersection, curr_intersection);
    curr_intersection.clear();
  }
  return last_intersection;
}

Örnek
Nesnenin < operatörünü kullandığımızda şöyle yaparız. Şöyle kullanılır. Bu kod v1 ve v2'nin kesişimini verir.

set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(), back_inserter(result));

Lamda ile kullanımda şöyle yaparız.

auto mycomparator = ( const MyClass& lhs,  const MyClass& rhs)
{
  return lhs.getNumber() < rhs.getNumber();
};

std::vector<A> result;
std::set_intersection(v1.begin(), v1.end(),
                      v2.begin(), v2.end(),
                      std::back_inserter(result), mycomparator);

Örnek
Diyelimki iki dosyayı karşılaştırmak istiyoruz. Aynı olan satırları, solda dosya ve sağ dosyadaki farklı satırları renkli göstermek istiyoruz. Bu durumda önce set_intersection ile aynı satırlar bulunur. Daha sonra set_difference (soldosya, kesişim) ve set_difference (sağdosya, kesişim) ile farklı satırlar bulunur.

Diğer
has_overlap uzantısı
set_intersection tüm ortak nesneleri bulur. Eğer amacımız sadece bir tane kesişim olduğunu bulmak ise şu kodu kullanabiliriz. Bu kod set_intersection gibi dizilerin sıralı olmasını ister ve aynı mantıkta çalışır. Tek farkı, kesişimleri bir başka diziye yazmak yerine boolean bir sonuç dönmesidir.

template<class InputIt1, class InputIt2>
bool has_overlap(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            ++first1;
            continue;
        } 
        if (*first2 < *first1) {
            ++first2;
            continue;
        } 
        return true;
    }
    return false;
}

Bir başka yöntem ise şöyle olabilirdi.

#include <algorithm>
template<class InputIt1, class InputIt2>
bool has_overlap(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2){
    while (first1 != last1)
        if (std::binary_search(first2, last2, *first1++))
            return true;
    return false;
}

Java
std::inserseting metodunu Java ile kodlasaydık şöyle yaparız.

static <T extends Comparable<T>> List<T> intersect(List<T> list1, List<T> list2) {
  final int size1 = list1.size();
  final int size2 = list2.size();
  final List<T> result = new ArrayList<>(Math.min(size1, size2));

  int i = 0;
  int j = 0;
  while (i < size1 && j < size2) {
    T a = list1.get(i);
    int compare = a.compareTo(list2.get(j));
    if (compare < 0)
      i++;
    else if (compare > 0)
      j++;
    else {
      result.add(a);
      i++;
      j++;
    }
  }
  return result;
}