lower_bound dan upper_bound ialah fungsi carian binari terbina dalam.
lower_bound - fungsi yang, dalam masa logaritma, mencari elemen terkecil dalam tatasusunan diisih yang lebih besar daripada atau sama dengan nilai k yang diberikan.
Ia mengambil sempadan tatasusunan dan nilai k sebagai argumen.
Mengembalikan lelaran kepada elemen yang ditemui, atau ke penghujung (tidak termasuk) tatasusunan jika tiada unsur sedemikian wujud.
Anda boleh membaca lebih lanjut dalam dokumentasi.
upper_bound - fungsi yang dalam masa logaritma dalam tatasusunan yang diisih mencari elemen terkecil yang lebih besar daripada nilai k yang diberikan.
Ia mengambil sempadan tatasusunan dan nilai k sebagai argumen.
Mengembalikan lelaran kepada elemen yang ditemui, atau ke penghujung (tidak termasuk) tatasusunan jika tiada unsur sedemikian wujud.
Anda boleh membaca lebih lanjut dalam dokumentasi.
Perlu dijelaskan bahawa penggunaan fungsi ini pada set atau multiset tidak berfungsi dalam masa logaritma kerana kekurangan iterator dalam koleksi akses rawak di atas.
Walau bagaimanapun, koleksi ini mempunyai kaedah terbina dalam yang sepadan (iaitu, anda perlu menggunakannya "melalui titik").
Contoh:
vektor a = { 0, 1, 3, 5, 7 };
vektor::iterator it;
it = lower_bound(a.begin(), a.end(), 4);
// *ia == 5
it = lower_bound(a.begin(), a.end(), 5);
// *ia == 5
ia = lower_bound(a.begin(), a.end(), 8);
// ia == a.end()
it = upper_bound(a.begin(), a.end(), 4);
// *ia == 5
it = upper_bound(a.begin(), a.end(), 5);
// *ia == 7
it = upper_bound(a.begin(), a.end(), -1);
// *itu == 0
// dengan menolak iterator, anda boleh mendapatkan indeks elemen yang ditemui
int ind = lower_bound(a.begin(), a.end(), 4) - a.begin();
// ind == 3
// perlu menggunakan kaedah dan bukannya fungsi untuk koleksi set dan serupa
set s{ 1, 3, 5 };
set::iterator sit;
sit = s.lower_bound(3);
// *duduk == 3
sit = s.upper_bound(3);
// *duduk == 5
|
unik - fungsi yang memampatkan semua jujukan unsur berturutan yang sama menjadi satu dalam masa linear.
Sebagai hujah, ia melepasi sempadan tatasusunan, yang mana ia perlu menggunakan pemampatan.
Iterator dikembalikan ke hujung baharu (tidak termasuk) tatasusunan. Anda harus berhati-hati dengan elemen selepas hujung baharu tetapi sebelum elemen lama, kerana ia akan mempunyai nilai yang tidak ditentukan.
Anda boleh membaca lebih lanjut dalam dokumentasi.
Jika anda menggunakan fungsi ini pada vektor, adalah mudah untuk mengubah saiz menggunakan hasil yang dikembalikan (lebih lanjut mengenainya di bawah).
Contoh:
vektor a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 };
unique(a.begin(), a.end());
// a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?]
// menggunakan fungsi unik adalah mudah dilakukan
// tatasusunan tambahan untuk pemampatan koordinat
a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 };
sort(a.begin(), a.end());
// a = [10, 10, 41, 41, 41, 235, 235, 500, 500]
a.resize(unique(a.begin(), a.end()) - a.begin());
// a = [10, 41, 235, 500]
|
merge - fungsi yang menggabungkan dua tatasusunan yang diisih, iaitu, dalam masa linear ia mendapat tatasusunan yang diisih, yang terdiri daripada elemen tatasusunan pertama dan kedua.
Ia memerlukan 5 argumen: dua sempadan untuk setiap tatasusunan dan sempadan kiri destinasi (di mana elemen tatasusunan yang terhasil akan diletakkan).
Butiran lanjut boleh didapati dalam dokumentasi.
Contoh:
// tatasusunan sumber mesti diisih
vektor a = { 1, 3, 5, 7 };
vektor b = { 2, 4, 6 };
// memerlukan destinasi yang cukup besar
vektor c(7);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 3, 4, 5, 6, 7]
// elemen boleh diulang
a = {1, 2, 4, 4};
b = { 2, 3, 3, 3, 4, 4};
c.resize(10);
merge(a.begin(), a.end(), b.begin(), b.end(), c.begin());
// c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]
Fungsi ini sangat berguna dalam konteks isihan gabungan.
|
nth_element ialah fungsi yang membolehkan anda mencari elemen ke-n dalam tatasusunan dalam susunan disusun dalam masa linear.
Fungsi ini mengambil hujung kiri tatasusunan, satu lelaran ke kedudukan yang nilainya dalam tertib yang boleh ditemui dan hujung kanan tatasusunan.
Selepas menggunakan fungsi, nilai yang diperlukan akan terletak di tempat yang ditunjukkan oleh iterator, manakala nilai yang selebihnya akan memperoleh susunan huru-hara, tetapi di sebelah kiri ke-n akan terdapat nilai tidak lebih daripada itu, dan ke kanan tidak kurang. Iaitu, perlu difahami bahawa fungsi ini memusnahkan susunan asal unsur-unsur.
Anda boleh membaca lebih lanjut dalam dokumentasi (https://www.cplusplus.com/reference/algorithm/nth_element/).
Contoh:
vektor a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 };
// cari elemen pada indeks 4
// perhatikan susunan hujah
nth_element(a.begin(), a.begin() + 4, a.end());
// a = [#, #, #, #, 4, $, $, $, $, $]
// di mana # <= 4 dan 4 <= $
|
Pilih atur panjang n ialah koleksi tertib tanpa ulangan nombor 1, 2, ..., n. Contohnya, [3, 1, 2] dan [5, 4, 3, 2, 1] ialah pilih atur, tetapi [1, 2, 1, 3] dan [1, 2, 4] bukan.
Jika tugas itu dikurangkan kepada fakta bahawa ia adalah perlu untuk mengulangi semua pilih atur panjang n, maka anda boleh menggunakan mekanisme yang mudah dalam C ++, yang dipanggil "next_permutation".
Anda boleh membaca lebih lanjut mengenainya dalam dokumentasi, tetapi maksudnya ialah fungsi ini mengubah tatasusunan yang diluluskan kepada pilih atur seterusnya dalam susunan leksikografi (yang umumnya jelas dan namanya).
Untuk menggunakan next_permutation, anda perlu memasukkan perpustakaan algoritma (iaitu tulis #include <algorithm> pada permulaan program)
Contoh:
vektor arr;
arr = { 1, 2, 3}; // tatasusunan ialah [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // lulus keseluruhan tatasusunan ke fungsi
// array kini [1, 3, 2]
arr = { 2, 3, 1}; // tatasusunan ialah [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // lulus keseluruhan tatasusunan ke fungsi
// array kini [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // adalah mungkin untuk menggunakan fungsi pada sebahagian daripada tatasusunan, tetapi dalam amalan ini jarang diperlukan
// array kini [3, 2, 1]
Dalam kes ini, fungsi mempunyai nilai pulangan boolean yang benar jika pilih atur seterusnya dijana dan palsu jika tiada satu lagi (kes apabila pilih atur maksimum dalam susunan leksikografi diserahkan kepada fungsi).
Ini memungkinkan untuk menggunakan fungsi dalam gelung, yang akan membolehkan kami mengulangi semua pilih atur sekali gus. Disebabkan oleh pengindeksan 0, dalam praktiknya selalunya lebih mudah untuk bekerja dengan pilih atur nombor dari 0 hingga n - 1, walaupun pilih atur secara rasmi mengandungi nombor dari 1 hingga n. Tetapi mujurlah, ini tidak membawa kepada tindanan tambahan dalam kod, kerana fungsi next_permutation disesuaikan dengan pilih atur 0-indeks (dan juga elemen pendua dalam tatasusunan, tetapi anda boleh mengetahui lebih lanjut sendiri).
Secara umum, kod untuk lelaran ke atas semua pilih atur kelihatan seperti ini:
intn; // saiz pilihatur
vektorperm(n); // perm ialah singkatan untuk "permutation", i.e. "permutasi"
untuk (int i = 0; i < n; i++)
perm[i] = i; // mulakan pilih atur awal 0, 1, ..., n - 1
lakukan {
// di dalam gelung kita memproses pilih atur semasa
} manakala (next_permutation(perm.begin(), perm.end())); // jika tiada pilih atur seterusnya, maka tamatkan gelung
Kod ini berjalan dalam O(n! * f(n)), dengan f(n) ialah masa yang anda perlukan untuk memproses satu pilihatur tertentu.
|