lower_bound ve Upper_bound yerleşik ikili arama işlevleridir.
lower_bound - logaritmik zamanda, sıralanmış bir dizideki verilen k değerinden büyük veya ona eşit olan en küçük öğeyi bulan bir işlev.
Argüman olarak dizinin sınırlarını ve k değerini alır.
Bulunan öğeye veya böyle bir öğe yoksa dizinin sonuna (dahil değildir) bir yineleyici döndürür.
belgelerde daha fazla bilgi edinebilirsiniz.
Upper_bound - sıralanmış bir dizide logaritmik zamanda verilen k değerinden kesinlikle büyük olan en küçük öğeyi bulan bir işlev.
Argüman olarak dizinin sınırlarını ve k değerini alır.
Bulunan öğeye veya böyle bir öğe yoksa dizinin sonuna (dahil değildir) bir yineleyici döndürür.
belgelerde daha fazla bilgi edinebilirsiniz.
Yukarıdaki rasgele erişim koleksiyonlarında yineleyicilerin olmaması nedeniyle bu işlevlerin bir küme veya çoklu küme üzerinde kullanımının logaritmik zamanda çalışmadığını açıklığa kavuşturmakta fayda var.
Ancak, bu koleksiyonların karşılık gelen yerleşik yöntemleri vardır (yani, bunları "nokta aracılığıyla" kullanmanız gerekir).
Örnekler:
vektör a = { 0, 1, 3, 5, 7 };
vektör::iterator it;
o = lower_bound(a.begin(), a.end(), 4);
// *it == 5
o = lower_bound(a.begin(), a.end(), 5);
// *it == 5
o = lower_bound(a.begin(), a.end(), 8);
// o == a.end()
o = üst_sınır(a.begin(), a.end(), 4);
// *it == 5
o = üst_sınır(a.begin(), a.end(), 5);
// *it == 7
o = üst_sınır(a.begin(), a.end(), -1);
// *it == 0
// yineleyicileri çıkararak bulunan öğenin dizinini elde edebilirsiniz
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// ind == 3
// set ve benzeri koleksiyonlar için fonksiyonlar yerine metodların kullanılması gerekiyor
set s{ 1, 3, 5 };
set::yineleyici sit;
otur = s.lower_bound(3);
// *otur == 3
otur = s.upper_bound(3);
// *otur == 5
|
benzersiz - aynı ardışık öğelerin tüm dizilerini doğrusal zamanda bire sıkıştıran bir işlev.
Argüman olarak, içinde sıkıştırma uygulanması gereken dizinin sınırları iletilir.
Dizinin yeni sonuna (dahil değil) bir yineleyici döndürülür. Tanımsız bir değere sahip olacağından, yeni sondan sonra eskisinden önceki öğelere dikkat etmelisiniz.
Daha fazla bilgiyi belgelerde okuyabilirsiniz.
Bu işlevi bir vektör üzerinde kullanıyorsanız, döndürülen sonucu kullanarak yeniden boyutlandırmak uygundur (bununla ilgili daha fazlası aşağıda).
Örnekler:
vektör a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
unique(a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// benzersiz işlevi kullanmak uygundur
// koordinat sıkıştırma için yardımcı dizi
bir = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
sort(a.begin(), a.end());
// bir = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(benzersiz(a.begin(), a.end()) - a.begin());
// bir = [10, 41, 235, 500]
|
birleştirme - iki sıralanmış diziyi birleştiren bir işlev, yani lineer zamanda birinci ve ikinci dizinin öğelerinden oluşan sıralanmış bir dizi alır.
5 bağımsız değişken alır: her dizi için iki sınır ve hedefin sol sınırı (sonuçta elde edilen dizinin öğelerinin yerleştirileceği yer).
Daha fazla ayrıntıyı belgelerde bulabilirsiniz.
Örnekler:
// kaynak dizileri sıralanmalıdır
vektör a = { 1, 3, 5, 7 };
vektör b = { 2, 4, 6 };
// hedefin yeterince büyük olması gerekiyor
vektör c(7);
birleştirme(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// elemanlar tekrarlanabilir
bir = {1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4 };
c.boyutlandır(10);
birleştirme(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Bu işlev, birleştirme sıralaması bağlamında çok kullanışlıdır.
|
nth_element, bir dizideki n'inci elemanı lineer zamanda sıralanmış şekilde bulmanızı sağlayan bir fonksiyondur.
İşlev, dizinin sol ucunu, sıralı düzende değeri bulunacak konuma bir yineleyici ve dizinin sağ ucunu alır.
İşlevi uyguladıktan sonra, yineleyici tarafından belirtilen yerde gerekli değer bulunacak, geri kalan değerler kaotik bir düzen elde edecek ancak n'incinin solunda ondan daha fazla olmayan değerler olacak ve sağda daha az değil. Yani bu fonksiyonun elemanların orijinal sırasını bozduğu anlaşılmalıdır.
Belgelerde daha fazlasını okuyabilirsiniz (https://www.cplusplus.com/reference/algorithm/nth_element/).
Örnek:
vektör a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// 4. indekste öğeyi ara
// bağımsız değişkenlerin sırasına dikkat edin
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// burada # <= 4 ve 4 <= $
|
n uzunluğundaki bir permütasyon, 1, 2, ..., n sayılarının tekrarı olmayan sıralı bir koleksiyondur. Örneğin, [3, 1, 2] ve [5, 4, 3, 2, 1] permütasyondur ancak [1, 2, 1, 3] ve [1, 2, 4] değildir.
Görev, n uzunluğundaki tüm permütasyonları yinelemenin gerekli olduğu gerçeğine indirgenirse, C++'da "sonraki_permütasyon" adı verilen uygun bir mekanizma kullanabilirsiniz.
Bununla ilgili daha fazla bilgiyi belgelerde okuyabilirsiniz, ancak önemli olan nokta, bu işlevin geçen diziyi değiştirmesidir sözlük sırasına göre müteakip permütasyona (ki bu genellikle açıktır ve adıdır).
next_permutation'ı kullanmak için algoritma kitaplığını eklemeniz gerekir (yani, programın başına #include <algorithm> yazın)
Örnekler:
vektör dizi;
dizi = { 1, 2, 3 }; // dizi [1, 2, 3]
next_permutation(arr.begin(), dizi.end()); // tüm diziyi işleve iletin
// dizi artık [1, 3, 2]
dizi = { 2, 3, 1 }; // dizi [2, 3, 1]
next_permutation(arr.begin(), dizi.end()); // tüm diziyi işleve iletin
// dizi artık [3, 1, 2]
next_permutation(arr.begin() + 1, dizi.begin() + 3); // bir dizinin bir bölümüne bir işlev uygulamak mümkündür, ancak pratikte buna nadiren ihtiyaç duyulur
// dizi artık [3, 2, 1]
Bu durumda, işlev, bir sonraki permütasyon oluşturulduysa true ve sonraki permütasyon yoksa false olan bir boolean dönüş değerine sahiptir (sözlük sırasına göre maksimum permütasyonun işleve iletildiği durum).
Bu, işlevi bir döngüde kullanmayı mümkün kılar, bu da tüm permütasyonları aynı anda yinelememize izin verir. Bir permütasyon resmi olarak 1'den n'ye kadar sayılar içermesine rağmen, 0 indeksleme nedeniyle pratikte 0'dan n - 1'e kadar sayıların bir permütasyonu ile çalışmak genellikle daha uygundur. Ancak neyse ki bu, kodda ek bindirmelere yol açmaz, çünkü next_permutation işlevi, 0 dizinli permütasyonlara (ve hatta bir dizideki yinelenen öğelere) uyarlanmıştır, ancak daha fazlasını kendi başınıza öğrenebilirsiniz).
Genel olarak, tüm permütasyonları yineleme kodu şöyle görünür:
int; // permütasyon boyutu
vektörperm(n); // perm, "permütasyon"un kısaltmasıdır, yani "permütasyon"
için (int ben = 0; ben
Bu kod O(n! * f(n)) şeklinde çalışır, burada f(n), belirli bir permütasyonu işlemeniz için geçen süredir.
|