STL Algoritmaları

Aşağıda kullandığım STL algoritmaları ile ilgili aldığım notlar var. C++ Notlarım başlıklı yazıda ise C++ ile ilgili konuları not aldım.

Algoritmalar
Tüm algoritmalar iterator ile çalışıyorlar. Şekilde bunu görmek mümkün. Iterator aynı zamanda bir GoF Davranışsal Örüntüsü (Behavioral Pattern) Açıklaması ile aşağıda:

"This pattern provides a way to access the elements of an aggregate object sequentially without exposing its underlying representation"

Kendi yazdığımız algoritmalara da iterator geçmek daha doğru, ancak bazen algoritma size() gibi container'a mahsus metodlara ihtiyaç duyabilir. Bu durumda mecburen container geçmek gerekiyor.

Algoritma denilince aşağıdaki gibi içine bir çok parametre alan ve bir çıktı veren metod değil, bir veri yapısı üzerinden yürümeyi gerektiren metodlar akla gelmeli. 

accumulate
accumulate ile bir aralığın ortalaması bulunabilir. Örnek:

adjacent_find
Yanyana elemanlara verilen metodu uygular. false dönen ilk elemanı döner. Bir dizinin sıralı (sorted) olup olmadığını anlamak dışında kullanıldığını görmedim. Örnek:

auto it = std::adjacent_find(begin(tab), end(tab),  std::greater<int>() );

advance
Advance verilen iterator parametresini belirtilen sayı kadar ileri veya geri oynatır. Verilen iterator'ün tipine göre pointer arithmetic veya döngü kullanabilir. Örnek:

auto it = my_vector.begin(); // std::vector has random access iterators
std::advance(it, 4);         // NOT a loop, will call it += 4;

veya

auto it = my_map.begin();    // std::map has bidirectional iterators
std::advance(it, 4);         // for (auto i = 0; i < 4; ++i) ++it;

C++11'de sadece 1 adım ileri veya geri oynamak için next() veya prev() metodları da tanımlı. next() ve prev() metodları advance() metodundan farklı olarak verilen iterator'ün kopyasını alır ve sonuç olarak döndürürler.

Dikkat edilmesi gereken nokta advance() metodu iterator'ün nerede bittiğini bilmediği için, yanlış bir sayı verilirse veriyapısının dışına taşabilme ihtimali var.

distance
İki iterator arasındaki mesafeyi ölçer. Elimizde sadece begin() end() iteratorleri varsa, veriyapısının büyüklüğünü öğrenmek için kullanabiliriz.Örnek:

Bir başka örnekte iki iterator arasındaki mesafenin index'i verdiği gösterilmiş.

equal_range
Bu algoritmayı kullanırken aranan ve değer tipleri aynı ise sadece tek bir karşılaştırma metodu yeterli olur. Ancak tipleri farklı ise algoritma iki farklı imzalı metoda ihtiyaç duyar.
fill
fill ile verilen aralığı doldurmak mümkün. Örneğin bir array'i doldurmak için aşağıdaki örneği kullanabiliriz.

Kullanım olarak Java'daki Collections.fill() metoduna benziyor.
 
fill_n
fill_n ile sadece verilen aralık doldurulur.

#define SIZE (100*1000*1000)
char arr[SIZE];
std::fill_n(arr, SIZE/12, 0); //yarısını doldur 

find
Aşağıdaki örnekte find lineer arama yapıyor. Maliyeti O(N)

i = std::find(C.begin(), C.end(), "foo");

find işlemim için == operatörü tanımlı olmalı. Buradaki açıklamada find algoritmasının sırayla her bir nesneyi karşılaştırırken "loop unwinding" yani "döngü açma" yöntemi kullandığı gösterilmiş.

find_if
find_if ile UnaryPredicate kullanarak verilen koşulun sağlanıp sağlanmadığını bulmak mümkün. Örnek:

Veya functor predicate kullanılabilir. Örnek:

 
Eğer istenirse find_if içine lambda da geçilebilir. Örnek:

Bir başka lambda örneği

 
for_each
for_each ile her bir eleman için verilen functor çağırılır ve en sonunda funtor döndürülür. Örnek:

 

function
function'a point eden nesneler yaratabilmemizi sağlar. 

!operator
! operatörü ile function nesnesinin dolu olup olmadığı anlaşılabilir. Örnek:

std::function<int (int)> pInit;
std::cout << !pInit << std::endl;

Diğer
Hatta bu nesnelere geçilecek parametreleri bile bağlayabiliriz. Örnek:

inplace_merge
Sıralı olan iki farklı diziyi yine sıralı olacak şekilde birleştirir. Örnek'te başı sıralı ancak sonu sıralı olmayab tab vector'ü verilmiş. Sıralı olan n tane eleman atlandıktan sonra, geri kalan elemanlar kendi aralarında sıralanıyor. Daha sonra aynı vector'ün içindeki iki farklı sıralı dizi birleştiriliyor.

void foo( std::vector<int> & tab, int n ) {
     std::sort( begin(tab)+n, end(tab));
     std::inplace_merge(begin(tab), begin(tab)+n, end(tab));
}

inner_product

inner_product ile dot product aynı şeyler. Hiç bir zaman kullanmaya ihtiyacım olmadı. Tek işe yaradığını okuduğum yer iki vektörün birbirlerine dik olup olmadığını anlamaya yaramaları. Birbirine dik iki vektörün inner_product sonucu sıfırdır.
 
is_same
Bu metodu hiç kullanmam gerekmedi. Örnek:

std::cout << std::is_same<unsigned char, uint8_t>::value;

iter_swap
İki iteratör'ün değerlerini yer değiştirir.  Örnek:

auto ita = std::find(a.begin(), a.end(), 56);
auto itb = std::find(b.begin(), b.end(), 2);
if (ita != a.end() && itb != b.end())
  std::iter_swap(ita, itb);

lower_bound
Verilen değerden >= olan ilk değeri döndürür.
Bu method Java'daki  NavigableSet.ceiling() metoduna benziyor. Aradaki fark verilen iterator aralığının sıralı olması gerekmez.

lower_bound sıralı bir diziye yeni eleman eklemek için kullanılabilir.

upper_bound
Verilen değerden > olan ilk değeri döndürür.

max
max iki sayının en büyüğünü bulmak için kullanılır.

min
min iki sayının en küçüğünü bulmak için kullanılır.  

merge
merge ile sıralı olan iki dizi yeni bir dizi olarak birleştirilir. Pseudo kod için buraya bakılabilir.

move
Nasıl çalıştığını tam anlamadım, ancak std::move() bir şekilde move constructor'ın çağırılmasını sağlıyor. Yani metoda verilen parametreyi static_cast<T&&> haline getiriyor.

next 
advance() metoduna bakabilirsiniz. Örnek:

auto it = my_map.begin();
auto it4 = std::next(it, 4); // copies it, then advances and returns that copy

partition
Verilen koşulu sağlayanlar ve sağlamayanlar diye iki gruba ayırır.
Örnek:

 
placeholders
Verilen metoda iteratordeki elemanı geçer. Örnek:

prev
advance() metoduna bakabilirsiniz.
 
remove_if
koşulu sağlayan elemanlar [begin, middled) arasında bir yere doldurulurlar. Bu metod koşulu sağlamayan elemanların başladığı yeri iteratör olarak döndürür. Koşulu sağlamayan elemanların tanımsız olduğunu kabul etmek gerekir.

Dolayısıyla remove_if genelde erase ile beraber kullanılır. 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.
Örnek:

set_intersection

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. Ortak küme aşağıdaki şekle benzer. 

shuffle
Bu metod verilen aralığı rastgele karıştırır. Java'daki Collections.shuffle() metoduna benzer. Bu metoddan farklı olarak, C++ metodu sadece RandomAccessIterator ile çalışır. Java'daki metod ise gerekirse verilen listenin bir kopyasını alır ve karıştırıp geri verir.

  
sort
Bazı veri yapıları kendi sort metodlarına sahip. Örneğin list gibi. Kendi sort metoduna sahip olmayan veri yapıları için genel sort metodu kullanılabilir.

sort ile kullanılacak sıralama metodu nasıl çalışır
Sıralama metodu her zaman a,b şeklinde iki tane eleman alır ve her zaman a < b'nin sonucunu true veya false olarak döndürür. Buradaki yazı bilgilendirici. Konuyla ilgili olarak std::set'e verilen kendi sıralama metodumuzu da okuyabilirsiniz.

sort için strick weak ordering kullanmak lazım. Bu cümle antisymmetry kuralı yüzünden a < b ise true, a <= b ise false dönmek anlamına geliyor. Daha detaylı bir açıklama ise aşağıda.


Birden fazla alana göre sıralamak

Birden fazla alana göre sıralama için örnek: 

Bir başka örnekte ise std::tie kullanarak bir std::tuple döndürülmesi tavsiye edilmiş. std::tuple yukarıdaki karşılaştırmanın aynısını yapıyor.

Büyükten küçüğe göre sıralamak
Örnek
Sadece sıralama değiştiriliyor.

bool operator()(ps1, ps2) const
{
    return ps2 < ps1;//sıralamayı değiştir
} 

sort ile yeni bir comparator sınıfı kullanmak
Yukarıdaki strict weak ordering'i anlatan örnekte bir struct tanımlandığı ve struct'ın operator()'ü override ettiği farz edilmiş. Örnek:

struct cmp
{
    bool operator()(const Person &K , const Person &K1)
    {
    }
} 

sort ile global bir metod kullanmak
Örnek:

bool comp(const File& a, const File& b) {
}

std::sort(vec.begin(), vec.end(), comp);

sort ile sınıfın metodunu kullanmak
Buradaki örnekte sort metoduna geçilen metod comparator boost::bind ile beraber kullanılarak comparator haline getiriliyor.

sort ve elemanların yer değiştirmesi
sort stable bir algoritma değildir.  Eşit elemanların yerleri değişebilir. Buradaki soruda da aynı cevap verilmiş.

sort ve iterator
sort algoritması random access iterator kullanır. Örnek:

sort için copy constructor ve assignment operatorleri
sort algoritması dizinin uzunluğuna göre copy constructor veya assignment operator kullanıyor. Her ikisinin de yazılması iyi olabilir.
 
sort algoritmasının içi
Buradaki soruda sort algoritmasının küçük diziler için Insertion Sort kullandığı yazılı. Insertion Sort iki elemanı yer değiştirdiği için copy constructor ve assignment operatorlerine ihtiyaç duyar. Insertion Sort ile ilgili bilgi almak için Veri Yapıları başlıklı yazıya göz atabilirsiniz.  
 
swap
swap ile iki tane değişkenin değerlerinin yer değiştirmesini sağlar.

transform
transform unary veya binary operator ile çalışabilir.

unary operator örneği
Bu örnekte bir vector veri yapısı kendisini değiştirmek için kullanılıyor.

binary operatör örneği
Örnekte binary operatör verilen 2 input dizisi için çağırılıyor.

transform ve ostream_iterator
STL algoritması ile stream iterator sınıfını birleştiren bir cevap ise aşağıda.

std::transform(std::begin(data), std::end(data)
                     std::ostream_iterator<uint32_t>(cout,"\n"),
                     [](const uint32_t& value) -> uint32_t {return my_function(value);
                   );

unique
unique ile bir collection içindeki ardışık ve eşit olan değerlerden sadece bir tanesi bırakılır, diğerleri silinir. Bu algoritmayı kullanabilmek için ya eşitliği ölçen bir comparator verilmeli ya da elemanların == operatorü olmalı.
comparator 
Örnekte liste sıralandıktan sonra comparator ile eşit elemanlar siliniyor. Silinen elemanlar std::unique() metodunun döndürdüğü iterator'ün sonunda bir yere taşınıyorlar.



std::unique() metodunu kullanırken dikkat edilmesi gereken koşul, collection'ın sıralı olmuş olması değil ancak eşit değerlerin ardışık olarak gelmesi. Bu işi sağlamanın en kolay yolu da aslında collection'ı sıralamak. Örneğin aşağıdaki collection sıralı değil ancak eşsizlik koşulunu sağlayacak değerler ardışıklar.


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:

new []{1,3,2,2,3,1}.Distinct().Dump(); //1,3,2 verir

Veri Yapıları
Array
Array aşağıdaki gibi tanımlanıyor.

std::array<int, 10> stdArr;

Array aslında aşağaıdakine benzer basit bir sınıf.

List 
sort
List veriyapısı kendi sort metodun sahip.Örnek

Map
Map'i Dolaşmak
Iterator ve auto ile map'i dolaşma örneğini buradan aldım.

erase
STL içindeki bazı veri yapıları kendisine ait erase() metoduna geçilen iterator nesnesini otomatik olarak ilerletiyor. Ancak map bu veri yapılarından değil. erase() metodu void dönüyor. Dolayısıyla döngü içinde bir şey silmek istiyorsak aşağıdakine benzer bir kod parçası kullanmamız gerekli.

 
lower_bound
Bu metod yukarıdaki lower_bound ile aynı. Verilen değerden >= olan ilk değeri döndürür.Map veri yapısı daha verimli olmak için kendisi içinde aynı metodu tanımlamış.

Multimap
comparator kullanmak
Anahtar değerleri comparator kullanarak sıralamak mümkün. Örnek:

struct MyComp
{
   bool operator() (const MultiKey& lhs, const MultiKey& rhs)
   {
       return lhs.ExpiryDate < rhs.ExpiryDate ;
   }
};

std::multimap<MultiKey, Value,MyComp> multimapType;

 
equal_range
Multimap'in bir metodu olan equal_range ile aynı SQL'deki group by ifadesi gibi kullanabilme imkanı var. Örnek aşağıda. :

Bir diğer örnekte ise lambda kullanılmış.

Unordered Map
Kendi hash metodumuz
Örnek:

find
find() metodu verilen anahtar değerine göre arar ve bir itetator döndürür. Örnek:

std::unordered_map<std::string,double> mymap = {
     {"mom",5.4},
     {"dad",6.1},
     {"bro",5.9} };
std::unordered_map<std::string,double>::const_iterator got = mymap.find ("mom"); 

Optional
bool converter
Optional sınıfının dolu olup olmadığını anlamak için kullanılır. Örnek:

Priority Queue   
Pririty Queue her zaman en büyük elemanı almak için kullanılır. top() metodu  O(1) ile çalışır.
Bu veri yapısını kullanmak için eklenen verinin < operatörü ile sıralanabiliyor olması lazım. Örnek:

#include <queue>

typedef struct cell_s {
    unsigned int x;
    unsigned int y;
    unsigned int ambiguity = 9;
} cell_t;

// so the priority_queue can sort the structs:
bool operator<(const cell_t &a, const cell_t &b) {
    return a.ambiguity < b.ambiguity;
}
priority_queue<cell_t> blankCellQueue;
cell_t cell;
cell.x = x;
cell.y = y;
blankCellQueue.push(cell); 

Ya da karşılaştırma metodu tanımlanmalı. Örnek:

struct Event
{
    string name;
    int time;
    int pid;
};
class CompareEvent
{
public:
    bool operator()(Event& event1, Event& event2)
    {
        if (event1.time > event2.time)
            return true;
        return false;
    }
};
priority_queue<Event, vector<Event>, CompareEvent> eventList;
Event newEvent;
newEvent.name = eventName;
newEvent.time = time;
newEvent.pid = pid;
eventList.push(newEvent);
eventList.pop(); 

Queue
STL queue konusuna sonra değineceğim.

Pair
< operator
std::pair < operatörünü overload eder. Önce firt elemanı karşılaştırır. Eğer aynı ise second elemanı karşılaştırır. Dolayısıyla sort algoritmalarında kullanılabilir. Örnek:

std::vector<std::pair<std::string,bool>> v;
std::sort(v.begin(),v.end());

Set 
Set veri yapısı elemanları küçükten büyüğe doğru sıralayarak saklar. Setin içindeki veriyi döndürdüğü metodların bir çoğu const şeklinde tanımlanmış. Böylece kullanıcının veriyle oynayıp sıralamayı bozması engellenmiş.

set ve kendi sıralama metodumuz
Eğer istenirse kendi sıralama metodumuzu da tanımlayabiliriz. Kendi sıralama metodumuz yukarıdaki sort() metoduna geçilen sıralama metodu ile aynı mantıkta çalışır.

Kendi sıralama metodumuzun bool döndürdüğüne dikkat etmek lazım. Amaç ilk değerin ikincisinden küçük olup olmadığını anlamak. Eğer iki anahtar eşitse id_compare(key1,key2) == false ve id_compare(key2,key1) == false olmak zorundadır. Aşağıdaki cümle de aynı şeyi söylüyor.

That is, two keys k1 and k2 are considered to be equivalent if for the comparison object comp, comp(k1, k2) == false && comp(k2, k1) == false.

Item 21: Always have comparison functions return false for equal values başlıklı yazı da bilgilendirici.

Yanlış comparator kullanılırsa, eşit olmayan iki anahtar eşit gibi görünebilir.

find
find ile verilen eşitliği sağlayan bir eleman olup olmadığı bulunur. Örnekte std::set'in find metodu kullanılıyor ancak verilen nesnenin karşılaştırma (Comparator) operatörünün de tanımlı olması gerekiyor çünkü set sıralı bir veriyapısı ve verilen elemanı aramak için binary seach (ikili arama) kullanılıyor. set'in find metodu  O(log N ) maliyetinde.

insert
Bu metod bir pair dönüyor. Pair'in ilk kısmı, eklenen elemanı gösteren bir iterator. Bu iterator const ve değiştirilemez.

int main() {
  set<int> set;
  cout << set.insert(5).first << endl;//5
  return 0;
} 

Stack
En cins veri yapılarından birisi.

top ve pop
Bu iki metod beraber kullanılır. top() ile en üstteki elemanın referansı alınır. Metodun imzası şöyledir.

value_type& top();

pop() ile de veri yapısından silinir. Aynı anda en üstteki elemanı alma ve silme işini yerine getiren bir metod yoktur. Örnek:

stack<Gadget> gadgets;
Gadget gadget = gadgets.top();
gadgets.pop();

Vector
Vector Visual Studio'da kalıtım kullanıyor. Şöyle :
class vector : public _vector_alloc

Sıralı Bellek Alanı
Vector, aynı bir array gibi sıralı yani bitişik bellek alanı sunar. Açıklama burada.

constructor
Vector veriyapısını bir InputIterator vererek doldurmak mümkün. InputIterator ile vector'ün sakladığı veri tipleri farklı şeyler olabilirler. Örnek:

 

capacity
Veriyapısının kapasitesi contructor ile verilebilir. Aşağıdaki şekil durumu özetliyor.

Örnek:

clear
Bu metodun en hızlı nasıl çalışabileceğine dair açıklama burada.
 
erase
erase() metodu silinen elemendan bir sonraki elemanı gösteren bir iterator döner. Örnek:

front
front() ilk elemana referans döndüğü için, elemanı değiştirebilmek mümkün. Örnek:

 
[] operatörü
Bu  operatörün const ve olmayan iki çeşidi var.

const reference döndüren metod const vector ile kullanılıyor ve vector'ün içinin değiştirilmesini engelliyor.
Örnek:

insert
Insert metodu vector veri yapısının vermiş olduğu tüm iterator ve reference'ları geçersiz hala getirir. Iterator invalidation rules yazısı durumu özetliyor. Örnek:

push_back
Burada ilginç bir soru var. Vektör'ün içindeki bir elemanı tekrar push_back() ile eklersek ne olur diye soruyor.
 
resize - Kapasite ayır ve değer ile doldur
Metodun imzası aşağıda.

void resize( size_type count, T value = T() );

Buradaki soruda resize metodunun ne işe yaradığı çok iyi açıklanmış. Eğer verilen uzunluk mevcut uzunluktan küçükse,vektör kısalır ve sondaki elemanlar silinir. Eğer verilen uzunluk mevcut uzunluktan az ise vektör uzatılır. Eğer vektörün uzaması gerekiyorsa ucuna default constructed ya da 0 olarak başlatılmış elemanlar eklenir. İşlem bitince default constructed nesne yok edilir. Vöktörün uzaması ve doldurulması yüzünden resize metodu, reserve metoduna göre biraz daha verimsiz olabilir.

Dikkat edilmesi gereken nokta, vector içindeki bir düğüm diğer düğümlere'lere pointer tutuyorsa, resize pointerların geçerliliğini bozabilir.

Bir diğer fark ise, reserve tam olarak verilen kapasite kadar yer ayırır. resize biraz daha fazla ayırır/ayırabilir.


reserve - Kapasite ayır
İstenilen yer kadar kapasite ayırır.

swap
İki vektörün içlerini değiş tokuş edilmesini sağlar.

Iteratörler 
Konuyu STL Iteratörleri başlıklı yazıya taşıdım.

Initializer List
STL ile gelen initializer_list hangi kategoriye giriyor bilmiyorum ancak bir nesneyi
nesne = {...} şeklinde ilklememizi sağlıyor. Örnek:

template<typename T>
class ExampleContainer
{

private:       
    std::map<T, int> _objects;
public:
    ExampleContainer(std::initializer_list<typename std::map<T, int>::value_type> l) :
    _objects(l)
    {
    }
};
ExampleContainer<string> _rarities =
{
    { "One", 600 },     // Each of these entires will cause the creation of
    { "Two", 200 },    // a temporary object of type:
    { "Three", 50 },    // std::pair<string const, int>
    { "Four", 10 },     // that will become an element of the initializer
    { "Five", 1 },        // list received by the constructor.
};

Bir başka örnek:

Bir başka örnek:

 shared_ptr kullanan örnek ise

Initializer List üzerinde for döngüsü ile dolaşılabilir. Örnek:

 
reference_wrapper
Örnek:

shared_ptr
shared_ptr iki şekilde tanımlanabilir. İlk yöntemde make_ptr metodu kullanılır. İkincisinde ise new ile yaratılan nesne shared_ptr'nin constructor metoduna geçilir. İlk yöntemin daha verimli olduğu söyleniyor. Örnek: