25 Nisan 2018 Çarşamba

STL Heap Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor. Aşağıdaki algoritmalar heap kullanımını gösteriyor. Heap bir grup içinde en büyük veya en küçük değere sahip olan nesneyi bulabilmek için kullanılır. Genellikle priority queue gibi veri yapılarında işe yarar.

make_heap metodu
Verilen veri yapısını en büyük/en küçük eleman en önde olacak şekilde sıralar. Metodun imzası şöyledir.
template <class RandomAccessIterator>
  void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
Yani sadece vector veya array gibi yapılarda kullanılabilir.Sıralama için comparator da kullanılabilir. Binary Search Tree'den  farklı olarak en öndeki elemanın ardından gelenlerin sıralı olması beklenmemelidir!
"Heaps are a sort of binary tree that is normally stored in an array (vector). A heap is not actually maintained sorted; the element at the front is always the min (or it could be max); and there is an operation normally called re-heapify that takes log n time to restore the heap property after an element is added or removed. Removal is only from the front."
make_heap(), priority_queue'dan farklı olarak birkaç işlemin arka arkaya yapılmasına müsade ettiği için daha verimli olabilir. Şöyle yaparız.
vector<int> v{4,3,7,1,5};
make_heap(v.rbegin(), v.rend(), greater<int>());

q.pop_back();
q.push_back (9);

make_heap(v.rbegin(), v.rend(), greater<int>());
Örnek 1
En küçük eleman iterator'ün başladığı yerde olsun istersek şöyle yaparız.
vector<int> v{4,3,7,1,5};
make_heap(v.begin(), v.end(), greater<int>());
En sonda olsun istersek rbegin(),rend() kullanırız. Şöyle yaparız.
vector<int> v{4,3,7,1,5};
make_heap(v.rbegin(), v.rend(), greater<int>());
Örnek 2
Bir dizi şöyle heap yapılır.
struct MyComparator
{
    bool operator()(const&... lhs, const& ...rhs) const
    {
        return ...;
    }
};

std::vector<...>>    heap;
heap.push_back(...);


// Make a heap so the smallest value is on top.
std::make_heap(std::begin(heap), std::end(heap), MyComparator());
pop_heap metodu
Yukarıdaki örnekten devam edersek
std::push_heap(std::begin(heap), std::end(heap), MyComparator());

push_heap metodu
Yukarıdaki örnekten devam edersek
std::pop_heap(std::begin(heap), std::end(heap), countTester);
sort_heap metodu
Açıklaması şöyle
std::sort_heap requires ValueSwappable. In other words, it should be able to modify elements in-place through the iterator

23 Nisan 2018 Pazartesi

Template Specialization

Giriş
Template specialization belirli bir tip için algoritmanın farklı çalışmasını sağlamak için kullanılabilir. Ayrıca debug için de faydalıdır.

Tanımlama
Template kodları normalde .h dosyasında olmalı. Template Specialization kullanarak cpp dosyasında tanımlamak ta mümkün.

Tanımlama Sırası
Sıranın önemi yoktur. Şöyle olabilir
// specialization A
...
// specialization B
...
veya şöyle olabilir.
// specialization B
...
// specialization A
...
Örnek
Bu yöntemi çok fazla mesajın dispatch edildiği bir template sınıfında kullandım. .h dosyasında şöyle yaparız.
template <class T>
void doSomething(const T& * msg);
Daha sonra .cpp dosyasında ortak metodu yazarız.
template <class T>
void TClass::doSomething(const T& v) {
  ...
}
Her tip için farklı bir specialization metodunu ortak metodun altına tanımlarız. int için şöyle yaparız.
template void TClass::doSomething<int>(const int& v);
long için şöyle yaparız.
template void TClass::doSomething<long>(const long& v);
Örnek
Boost Serializaiton için A.h dosyasında şöyle yaparız.
class A {
public:
  ...
private:
  friend class boost::serialization::access;
  template <class Archive> void serialize(Archive&, unsigned);
};
A.cpp dosyasında şöyle yaparız.
// A.cpp
#include "A.h"

template <class Archive>
void A::serialize(Archive &ar, unsigned) 
{
    ar & bpt; 
}

#include <boost/archive/text_iarchive.hpp>
#include <boost/archive/text_oarchive.hpp>
#include <boost/serialization/shared_ptr.hpp>
#include "B.h" // required at point of instatiation
template void A::serialize(boost::archive::text_iarchive&, unsigned);
template void A::serialize(boost::archive::text_oarchive&, unsigned);
Örnek
.h dosyasında şöyle yaparız.
template <>
void TClass<int>::doSomething(std::vector<int> * v);
Daha sonra .cpp dosyasında metodları yazarız (implementation). Şöyle yaparız.
template <>
void TClass<int>::doSomething(std::vector<int> * v) {
 // Do somtehing with a vector of int's
}
Template Specialization - Farklı Template Tipleri
Örnek
Farklı tipler için şöyle yaparız.
template<typename T>
Function (const T *in, T *out)     {...}

template<>
void Function (const UINT8 *in, UINT8 * out) {...}

template<>
void Function (const INT8 *in, INT8 * out)   {...}
Şöyle yaparız.
template <class T>
int HelloFunction(const T& a)
{...}

template <>
int HelloFunction(const double & a)
{...}

HelloFunction(1);
HelloFunction(1.0);
Ancak bu yöntem yerine template olmadan direkt overload tercih edilmeli deniyor. Şöyle yaparız.
template <class T>
int HelloFunction(const T &a) {...}

int HelloFunction(const double &a) {...}

HelloFunction(1);
HelloFunction(1.0);
Örnek
Elimizde şöyle bir kod olsun
template <class T> 
T foo<T>(T val) { return someFunc(val); }

template <>
bool foo<bool>(bool val) { return otherFunc(val); };
T alan foo metodunun Bar için derlenmemesini isteyelim. Şöyle yaparız.
template <>
Bar foo<Bar>(Bar val) = delete;
Template Specialization - Generic Parametrenin Farklı Tipleri
Şöyle yaparız.
template<typename T>
struct ABC {
    T type;
    ABC(T inType) : type(inType) {}
};

template <class T>
int HelloFunction(ABC<T>& a)
{
    std::cout << "Hello: " << a.type << std::endl;
    return 0;
}

template <>
int HelloFunction(ABC<const char*> & a)
{
    std::cout << "Hello: " << a.type << std::endl;
    return 0;
}

HelloFunction(ABC<int>(1));
HelloFunction(ABC<const char*>("char"));
Template Specialization - Tag
Farklı tag'ler için şöyle yaparız.
enum class Mode
{
   Slow,
   Fast,
   Default
};

template<Mode T = Mode::Default>
int foo() { ...}

template<> 
int foo<Mode::Fast>() { ...}
Nested Template Specialization
Şöyle yaparız.
template<typename T>
class A
{
public:
  void foo()
  {
    foo_impl<T,void>::exec();
  }

private:
  template<typename T, typename DUMMY>
  struct foo_impl
  {
    static void exec()
    {
      //Default impl
    }
  };

  template<typename DUMMY>
  struct foo_impl<int,DUMMY>
  {
    static void exec()
    {
      int i = 0; //Breakpoint here
    }
  }
};