İmzası
sort metodu random access iterator ile çalışır. Metodun imzası şöyledir.
Comparator'un imzası şöyledir. Burada a ve b parametreleri farklı tiplere sahip olabilir gibi görünüyor. Ancak bu kullanımla hiç karşılaşmadım
Elimizde hiyerarşi içeren şöyle bir kod olsun.
Bazı veri yapıları random access iterator sağlayamaz. Bu yüzden kendi sort metodlarına sahiptirler.
sort algoritmasının içi
Sort algoritmasının nasıl olacağı kullanılan runttime kütüphanesine göre değişir. Bir çok runtime dizinin uzunluğuna göre farklı çalışan Introsort algoritmasını kullanıyor. Bu algoritma küçük diziler için için Insertion Sort kullanır.
Insertion Sort iki elemanı yer değiştirdiği için, C++11 kullanıyorsak move constructor yazmakta fayda var. Kullanmıyorsak copy constructor ve assignment operatorlerine ihtiyaç duyar.
Microsoft sort Algoritmasının İçi
Microsoft'un sort algoritması şöyle.
sort stable bir algoritma değildir. Eşit elemanların yerleri değişebilir.
comparator 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.
sort için strick weak ordering kullanılır.Daha detaylı bilgi için Strict Weak Ordering yazısına bakabilirsiniz.
Sıralama Sonucunda Sadece İndeksi Almak
Girdi olan veri yapısını bozmadan sadece indeksleri elde etmek için şöyle yaparız.
sort metodu random access iterator ile çalışır. Metodun imzası şöyledir.
template< class RandomIt, class Compare >
void sort( RandomIt first, RandomIt last, Compare comp );
ComparatorComparator'un imzası şöyledir. Burada a ve b parametreleri farklı tiplere sahip olabilir gibi görünüyor. Ancak bu kullanımla hiç karşılaşmadım
bool cmp(const Type1 &a, const Type2 &b);
ÖrnekElimizde hiyerarşi içeren şöyle bir kod olsun.
struct Animal {};
struct Cat : Animal {};
struct Dog : Animal {};
struct Hound : Dog {};
bool cmp(const Animal &a, const Animal &b);
Comparator hep ata sınıfa göre yazılır. Şöyle yaparız.std::vector<Hound> hounds;
... // fill hounds
std::sort(hounds.begin(), hounds.end(), cmp);
Bazı Veri YapılarıBazı veri yapıları random access iterator sağlayamaz. Bu yüzden kendi sort metodlarına sahiptirler.
Örneğin list gibi. Aşağıdaki kod derlenmez.
std::list<int> lst = { 1, 7, 5, 12 };
sort(lst);
Kendi sort metoduna sahip olmayan veri yapıları için genel sort metodu kullanılabilir.
sort algoritmasının içi
Sort algoritmasının nasıl olacağı kullanılan runttime kütüphanesine göre değişir. Bir çok runtime dizinin uzunluğuna göre farklı çalışan Introsort algoritmasını kullanıyor. Bu algoritma küçük diziler için için Insertion Sort kullanır.
Insertion Sort iki elemanı yer değiştirdiği için, C++11 kullanıyorsak move constructor yazmakta fayda var. Kullanmıyorsak copy constructor ve assignment operatorlerine ihtiyaç duyar.
Microsoft sort Algoritmasının İçi
Microsoft'un sort algoritması şöyle.
const int ISORT_MAX = 32; // maximum size for insertion sort
template<class RanIt, class Diff, class Pr>
void Sort(RanIt First, RanIt Last, Diff Ideal, Pr Pred)
{
Diff Count;
for (; ISORT_MAX < (Count = Last - First) && 0 < Ideal; )
{ // divide and conquer by quicksort
pair<RanIt, RanIt> Mid = Unguarded_partition(First, Last, Pred);
// ...
}
if (ISORT_MAX < Count)
{ // heap sort if too many divisions
Make_heap(First, Last, Pred);
Sort_heap(First, Last, Pred);
}
else if (1 < Count)
Insertion_sort(First, Last, Pred); // small
}
Açıklaması şöyle.When the range to be sorted has 32 elements or less, Sort uses insertion sort. Insertion sort doesn't use swap in its implementation. Otherwise, divide-and-conquer quick sort is used. In the implementation it calls iter_swap (inside Unguarded_partition), which in turn calls swap:32 elemandan uzun diziler için kullanılan Heap Sort'un içi şöyle. std::swap() metodunu çağırıyor.
template<class FwdIt1, class FwdIt2>
void iter_swap(FwdIt1 Left, FwdIt2 Right)
{ // swap *Left and *Right
swap(*Left, *Right);
}
Elimizde şöyle bir kod olsun. Sort edilmeye çalışılan dizi 32'den büyük olduğu için swap metodumuzun çağrıldığını görebiliiriz.class A
{
public:
A(int);
A(const A&);
A& operator=(const A&);
~A();
private:
friend bool operator<(const A&, const A&);
friend void swap(A&, A&);
};
A::A(){...}
A::A(const A& rhs){...}
A& A::operator = (const A & rhs){...}
A::~A(){...}
bool operator<(const A& lhs, const A& rhs){...}
void swap(A& lhs, A& rhs)
{
cout << "swap(A&, A&)" << endl;
using std::swap;
swap(lhs.ptr_, rhs.ptr_);
}
int main()
{
std::vector<A> v{ 33,32,31,30,29,28,27,26,25,24,23,22, 21,20,19,18,17,16,15,14,13,12,
11,10,9,8,7,6,5, 4,3,2,1 };
std::sort(v.begin(), v.end());
}
sort ve elemanların yer değiştirmesisort stable bir algoritma değildir. Eşit elemanların yerleri değişebilir.
comparator 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.
sort için strick weak ordering kullanılır.Daha detaylı bilgi için Strict Weak Ordering yazısına bakabilirsiniz.
1 Comparator
1.1 Struct comparator
Bir struct tanımlanır ve struct operator()'ü gerçekleştirilir. Kullanılması gereken metod imzası şöyle tanımlı. Metodun kendisinin const olması gerekmiyor ancak bence böyle yapılırsa daha iyi.
Şöyle global bir metod tanımlarız.
Şöyle yaparız.
C++11 ile sıralama metodu olarak lambda da kullanılabilir. Şöyle yaparız.
Bir çok yöntem kullanılabilir. Benim en kolay anlaşılır bulduğum kod şöyle.1.1 Struct comparator
Bir struct tanımlanır ve struct operator()'ü gerçekleştirilir. Kullanılması gereken metod imzası şöyle tanımlı. Metodun kendisinin const olması gerekmiyor ancak bence böyle yapılırsa daha iyi.
yani () operatörü, parametreleri const olarak almalıdır. Şöyle yaparız.The signature of the comparison function should be equivalent to the following:bool cmp(const Type1 &a, const Type2 &b);
The signature does not need to haveconst &
, but the function object must not modify the objects passed to it.
struct cmp
{
bool operator()(const Person &K , const Person &K1)
{
...
}
}
1.2 Global Metod ComparatorŞöyle global bir metod tanımlarız.
bool compare(Foo obj1, Foo obj2) {
...
}
Şöyle yaparız.std::sort(data.begin(), data.end(), compare);
1.3 Üye Metod ComparatorŞöyle yaparız.
class Foo {
public:
bool compare(const int& a, const int& b){
....
}
void sort(){
std::sort (data.begin() ,
data.end() ,
std::bind<bool>(&Foo::compare,this, _1 , _2 )
);
}
std::vector<int> data;
}
Eğer üye metod static ise bind kullanmaya gerek kalmaz. Üye metod tanımlamak için şöyle yaparız.static bool compare(Foo obj1, Foo obj2);
Şöyle yaparız.std::sort(data.begin(), data.end(), &Foo::compare);
1.4 Lambda ComparatorC++11 ile sıralama metodu olarak lambda da kullanılabilir. Şöyle yaparız.
std::sort(test.begin(), test.end(), [](const node* pa, const node* pb) {
return pb->frequency < pa->frequency;
});
2. Operator <
< operatörünü gerçekleştiren bir metod tanımlanır. Metod parametreleri const almalıdır. Şöyle yaparız
pointer içeren veri yapıların sıralarken biraz daha dikkatli olmak lazım. Comparator veya lambda pointer ile çalışmak için kodlanmalı. Örnekte node* nesnelerinin < operatörleri çağrılarak sıralama gerçekleşiyor.bool operator< (const Person & other) const
{
...
}
Diğer
sort ve pointerstd::sort(test.begin(), test.end(), [](const node* pa, const node* pb) {
return (*pb) < (*pa);
});
Birden fazla alana göre sıralamakif (lhs.first != rhs.first)
return lhs.first < rhs.first;
if (lhs.second != rhs.second)
return lhs.second< rhs.second;
return lhs.third < rhs.third;
Ya da şöyle yazılabilir.bool operator<(const Key& rhs) const
{
if (a < rhs.a)
return true;
if (a > rhs.a)
return false;
if (b < rhs.b)
return true;
if (b > rhs.b)
return false;
return (c < rhs.c);
};
Şöyle kodları sevmiyorum. Bence okuması çok zor.if (a1 < b1)
return true;
if (b1 < a1)
return false;
// a1==b1: continue with element 2
if (a2 < b2)
return true;
if (b2 < a2)
return false;
// a2 == b2: continue with element 3
if (a3 < b3)
return true;
return false; // early out
std::tie kullanan örnekler de var. std::tie a,b,c, elemanlarını teker teker karşılaştırır. Şöyle yaparız.bool operator<(const My_Struct& lhs, const My_Struct& rhs)
{
return std::tie(lhs.a_, lhs.b_, lhs.c_) < std::tie(rhs.a_, rhs.b_, rhs.c_);
}
Girdi olan veri yapısını bozmadan sadece indeksleri elde etmek için şöyle yaparız.
int arr[4] = { 2, 7, 3, 4 };//Array of values
int indexofarr[4] = { 0, 1, 2, 3 };//Array indices
std::sort(indexofarr, indexofarr+ 4, [arr](int l, int r) { return arr[l] < arr[r]; });
Hiç yorum yok:
Yorum Gönder