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

Template Specialization - Member Function

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

.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 - 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
    }
  }
};

std::prev metodu

Giriş
Açıklaması şöyle

std::prev doesn't modify itr. So, it is better when itr shouldn't or couldn't be modified. --itr and std::advance do modify itr, so they are better when itr must be modified.

Bu metod std::next() çağrısının tersini yapar.

std::prev - iterator + int
Örnek
Elimizde 2'dan fazla eleman içeren bir liste olsun. Sondan ikinci elemanı almak için şöyle yaparız.

if (foo.size() >= 2){
    double value = *std::prev(foo.end(), 2)}

Diğer
Açıklaması şöyle.

Although the expression --c.end() often compiles, it is not guaranteed to do so: c.end() is an rvalue expression, and there is no iterator requirement that specifies that decrement of an rvalue is guaranteed to work. In particular, when iterators are implemented as pointers, --c.end() does not compile, while std::prev(c.end()) does.

std::prev() bazı durumlarda mecburi olabiliyor. Şu kod derlenmez.

std::vector<double> vec({1,2});
std::array<double, 2> arr({{1,2}});
auto vecIt = --vec.end(); // OK
auto arrIt = --arr.end(); // error: lvalue required as decrement operand

Mecburen şöyle yaparız.

auto it = std::prev(arr.end());