lower_bound(elem) - Mavzu: Konteynerlar bilan ishlaydigan algoritimlar

lower_bound(elem) element qo‘yish mumkin bo‘lgan birinchi pozitsiyani to‘padi
upper_bound(elem) element qo‘yish mumkin bo‘lgan oxirgi pozitsiyani to‘padi
equal_range(elem) element qo‘yish mumkin bo‘lgan birinchi va oxirgi pozitsiyalarni to‘padi
Assotsiativ usullar
operator[](k) k kalitli elementga ruxsat;
find(k) k kalitli element pozitsiyasini topadi;
lower_bound(k) k kalitli elementning birinchi pozitsiyasini topadi;
upper_bound(k) kdan katta bo‘lgan kalitli birinchi elementni to‘padi;
equal_range(k) k kalitli elementni lower_bound (kuyi chegarasini) va upper_bound (yuqori chegarasini) topadi.
Boshqa usullar
size() elementlar soni;
empty() konteyner bo‘shmi?
capacity() vektor uchun ajratilgan xotira (faqat vektorlar uchun);
reserve(n) n elementdan iborat bo‘lgan konteyner uchun xotira ajratadi;
swap(x) ikkita konteynerlarni joyini almashtirish;
==, !=, < solishtirish operatorlari
2. Shablon (template) tushunchasi va ularning qo‘llanilishi. Funksiya shablonlarini, sinf shablonlarini yaratish usullari va ularning qo‘llanilishi. Ishning maqsadi: C++ dasturlash tilida shablon funksiya va ularni overload qilish ko‘nikmalarini shakllantirish. Masalaning qo‘yilishi: Tur xil to‘plamlarni qayta ishlovchi funksiya shablonlarini yaratish. Masala: Har – xil turdagi to‘plamlar berilgan. Agar to‘plam int turida bo‘lsa, uning elementlarini max va min larini o‘rtasidagi elementlarni aniqlovchi, agar to‘plam string turida bo‘lsa, uning toq uzunlikdagi elementlarini o‘chiruvchi funksiya shablonini tuzing. Masalani yechish g‘oyasi: 1 ta funksiya shabloni tuziladi. Standart turlar bilan Funksiyaga parameter sifatida kirib keledigan to‘plamni tur 9 Har-xil turdagi to‘plamlar berilgan. Agar to‘plam float turida bo‘lsa, uni elementlarining raqamlari teskasini (a=123; natija a=321) aniqlovchi, agar to‘plam char turida bo‘lsa, uning elementlari nechta so‘zdan iborat ekanligini aniqlovchi funksiya shablonini tuzing. #include #include char* cstrdup(const char* src) { return std::strcpy(new char[std::strlen(src) + 1] , src); } // -------------- class product { private: char* name_; int count_; float price_; public: product(const char* name, int count, float price) : name_(cstrdup(name)), count_(count), price_(price) { } product(const product& rhs) : name_(cstrdup(rhs.name_)), count_(rhs.count_), price_(rhs.price_) { } product& operator=(const product& rhs) { if(&rhs != this) { delete[] name_; name_ = cstrdup(rhs.name_); count_ = rhs.count_; price_ = rhs.price_; } return *this; } ~product() { delete[] name_; } void print(std::ostream& stream = std::cout) const { stream << "name: " << name_ << "\n" "count: " << count_ << "\n" "price: " << price_ << "\n"; } }; int main() { product some_product("some product", 100, 1.5); some_product.print();
}
3. Funktsiyalar va sinflar samarali dasturlash uchun kuchli va moslashuvchan vositalar bo'lsa-da, ular ba'zi hollarda C++ ning foydalaniladigan barcha parametrlarning turlarini belgilash talabi tufayli cheklangan. Masalan, ikkita sonning eng kattasini hisoblash uchun funksiya yozishimiz kerak deylik:
Agar biz butun sonlar bilan ishlasak, hamma narsa yaxshi. Ammo agar biz ikki tomonlama qiymatlar bilan ishlashimiz kerak bo'lsa-chi? Ehtimol, ikki turdagi bilan ishlash uchun max() funksiyasini ortiqcha yuklashga qaror qilasiz:
Endi bizda char, int, double va > operatorini haddan tashqari yuklasak, hatto sinflar bilan ishlaydigan bir xil funktsiyaning ikkita versiyasi mavjud! Biroq, C++ bizdan o'zgaruvchilarning turlarini ko'rsatishni talab qilganligi sababli, biz bir xil funktsiyaning bir nechta versiyasini yozishimiz kerak, bu erda faqat parametrlar turi o'zgaradi. Va bu, o'z navbatida, dasturchilar uchun bosh og'rig'i, chunki bunday kodni saqlash kuch va vaqt jihatidan oson emas. Va eng muhimi, bu samarali dasturlash tushunchalaridan birini buzadi - kodlarning takrorlanishini minimallashtirish. Har qanday turdagi parametrlar bilan ishlaydigan max() funksiyasining bitta versiyasini yozish yaxshi emasmi?
Bu mumkin. Shablonlar dunyosiga xush kelibsiz!
Agar lug‘atdagi “shablon” so‘zining ta’rifiga e’tibor qaratsangiz, biz quyidagilarni ko‘ramiz: “Shablon – shunga o‘xshash mahsulotlar tayyorlanadigan namunadir”. Misol uchun, shablon stencil - chizma / naqsh / belgi kesilgan ob'ekt (masalan, plastinka). Agar biz boshqa ob'ektga trafaret yopishtirib, bo'yoq purkasak, biz minimal kuch bilan bir xil naqshni olamiz, tez va eng muhimi, biz o'nlab bu naqshlarni turli rangda yasay olamiz! Bunday holda, bizga faqat bitta stencil kerak va biz rasmning rangini oldindan aniqlashimiz shart emas (stencilni ishlatishdan oldin).
C++ tilida funksiya shablonlari boshqa shunga o'xshash funksiyalarni yaratish uchun shablon bo'lib xizmat qiladigan funksiyalardir. Asosiy g'oya - ba'zi yoki barcha o'zgaruvchilarning aniq turini (turlarini) ko'rsatmasdan funktsiyalarni yaratish. Buning uchun har qanday ma'lumotlar turi o'rniga qo'llaniladigan shablon parametrining turini ko'rsatuvchi funktsiyani aniqlaymiz. Shablon parametr turiga ega funktsiyani yaratganimizdan so'ng, biz samarali tarzda "funktsiya trafaretini" yaratadi.
Funksiya shablonini chaqirganda, kompilyator funksiya uchun shablon sifatida "trafaret" dan foydalanadi, shablon parametri turini funktsiyaga uzatilgan o'zgaruvchilarning haqiqiy turi bilan almashtiradi! Shunday qilib, biz faqat bitta shablon yordamida funktsiyaning 50 ta "soyasini" yaratishimiz mumkin
Hozircha siz C++ da funksiya shablonlari qanday yaratilganiga qiziqayotgandirsiz. Bu unchalik qiyin emasligi ma'lum bo'ldi. max() funksiyasining butun son versiyasini yana bir bor ko'rib chiqing:
Bu erda biz ma'lumotlar turini uch marta aniqlaymiz: a, b parametrlarida va funktsiyaning qaytish turida. Bu funksiya uchun shablon yaratish uchun int turini funksiya shablon parametri turiga almashtirishimiz kerak. Bu holatda faqat bitta ma'lumot turi (int) ishlatilganligi sababli, biz shablon parametrlarining faqat bitta turini ko'rsatishimiz kerak.
Biz bu turni har qanday nomlashimiz mumkin, agar u zaxiralangan/kalit so'z bo'lmasa. C++ tilida bosh T harfi bilan shablon parametrlari turlariga murojaat qilish odatiy holdir (“Type” so‘zining qisqartmasi).
Mana bizning o'zgartirilgan max() funksiyamiz:
Lekin bu hammasi emas. Dastur ishlamaydi, chunki kompilyator T nima ekanligini bilmaydi!
Buni amalga oshirish uchun biz kompilyatorga ikkita narsani aytishimiz kerak:
Funktsiya shablonining ta'rifi.
T funksiya shablon parametrining turi ekanligini ko'rsatadi.
Biz buni bitta kod qatorida shablon deklaratsiyasini (aniqrog'i, shablon parametrlari deklaratsiyasini) bajarish orqali amalga oshirishimiz mumkin:
Keling, shablon parametrlari deklaratsiyasini batafsil ko'rib chiqaylik:
Birinchidan, biz shablon kalit so'zini yozamiz, bu esa kompilyatorga shablon parametrlarini keyingi e'lon qilishimizni aytadi.
Funktsiya shablonining parametrlari burchakli qavslarda ko'rsatilgan.
Typename va class kalit so'zlari shablon parametr turlarini yaratish uchun ishlatiladi. Funktsiya shablonlarini ishlatishning asosiy holatlarida tip nomi va sinf o'rtasida farq yo'q, shuning uchun siz ikkalasidan birini tanlashingiz mumkin. Agar siz class kalit so'zidan foydalansangiz, parametrlarning haqiqiy turi sinf bo'lishi shart emas (bu asosiy ma'lumotlar turining o'zgaruvchisi, ko'rsatgich yoki boshqa narsa bo'lishi mumkin).
Keyin shablon parametrining turini nomlaymiz (odatda T).
Agar bir nechta shablon parametrlari kerak bo'lsa, ular vergul bilan ajratiladi:
Agar bir nechta parametrlar mavjud bo'lsa, ular odatda T1, T2 yoki boshqa harflar deb ataladi: T, S.
Eslatma: T turiga o'tkazilgan funktsiya argumentining turi sinf bo'lishi mumkinligi va sinflar odatda qiymat bo'yicha o'tkazilishi tavsiya etilmaganligi sababli, bizning funktsiya shablonimiz parametrlari va qaytish qiymatini doimiy havolalar qilish yaxshiroqdir, masalan:
shablon
const T& max (const T& a, const T& b)
{ Qaytish (a > b) ? a : b; .}
Funktsiya shablonlaridan foydalanish
Funktsiya shablonlaridan foydalanish oddiy funktsiyalardan foydalanishga o'xshaydi:
E'tibor bering, max() funksiyasiga uchta qo'ng'iroq ham har xil turdagi parametrlarga ega! Biz max() funksiyasini uch xil turdagi parametrlar bilan chaqirayotganimiz sababli, kompilyator max() funksiyasining uch xil versiyasini yaratish uchun funksiya shablonidan foydalanadi:
int tipidagi parametrlarga ega versiya (max).
Double tipidagi parametrlarga ega versiya (max).
tartipidagi parametrlarga ega versiya (max).
O'tkazilayotgan qiymatlar turini (max ning qismi) aniq ko'rsatishning hojati yo'q, kompilyator buni o'zi aniqlaydi.
Funktsiya shablonlari ko'p vaqtni tejaydi, chunki biz shablonni faqat bir marta yozamiz va biz uni har xil turdagi ma'lumotlar bilan ishlatishimiz mumkin. Funktsiya shablonlarini yozishga odatlanganingizdan so'ng, oddiy funktsiyani yozish uchun ko'proq vaqt talab qilinmasligini bilib olasiz (muntazam funktsiyaning bitta versiyasi). Funktsiya shablonlari kodni keyinchalik saqlashni ancha osonlashtiradi va ular xavfsizroqdir, chunki kodni nusxalash orqali funktsiyani qo'lda ortiqcha yuklashingiz shart emas va faqat yangi ma'lumotlar turini qo'llab-quvvatlashingiz kerak bo'lganda ma'lumotlar turlarini o'zgartirishingiz shart emas.
Funktsiya shablonlarining bir nechta kamchiliklari bor va agar ular haqida gapirmasak, kechirib bo'lmaydi:
1. Birinchidan, ba'zi eski kompilyatorlar funksiya shablonlarini qo'llab-quvvatlamasligi mumkin yoki ular mumkin, lekin cheklovlar bilan. Biroq, bu endi avvalgidek muammo emas.
2. Ikkinchidan, funktsiya shablonlari ko'pincha aqldan ozgan xato xabarlarini ishlab chiqaradi, bu oddiy funktsiya xatolaridan ko'ra shifrlash qiyinroq.
3. Uchinchidan, funksiya shablonlari kompilyatsiya vaqtini va kod hajmini oshirishi mumkin, chunki bitta shablonni bir nechta fayllarda “amalga oshirish” va qayta kompilyatsiya qilish mumkin.
Funktsiya shablonlarining kuchi va moslashuvchanligi bilan solishtirganda, bu kamchiliklar juda kichikdir!
Shablonlar ba'zi parametrlarga (masalan, ma'lumotlar turlari, bufer o'lchamlari, standart qiymatlar) bog'lanmagan holda umumlashtirilgan algoritmlarni kodlash uchun mo'ljallangan C++ tili vositasidir.
C++ da funksiya va sinf shablonlarini yaratish mumkin.
Shablonlar parametrlangan sinflar va funksiyalarni yaratishga imkon beradi. Parametr har qanday turdagi yoki ruxsat etilgan turlardan birining qiymati bo'lishi mumkin (integer, enum, global kirish mumkin bo'lgan nomga ega har qanday ob'ektga ko'rsatgich, mos yozuvlar). Masalan, bizga qandaydir sinf kerak:
Bitta aniq maqsadda biz ushbu sinfdan foydalanishimiz mumkin. Ammo, to'satdan, maqsad biroz o'zgardi va boshqa sinf kerak. Endi bizga SomeArray massivining 30 ta elementi va SomeArray elementlarining haqiqiy turi SomeValue kerak. Keyin biz aniq turlardan mavhum bo'lishimiz va parametrlarga ega shablonlardan foydalanishimiz mumkin. Sintaksis: boshida, sinfni e'lon qilishdan oldin, biz shablonni, ya'ni shablonni e'lon qilamiz va burchakli qavslar ichida parametrlarni belgilaymiz. Bizning misolimizda:
Keyin birinchi holat uchun (20 ta elementdan iborat SomeValue va SomeArray butun soni bilan) biz yozamiz:
SomeClass < 20, int > SomeVariable;
ikkinchisi uchun:
SomeClass < 30, double > SomeVariable2;
Shablonlar kod bo'lagi uchun stenografiya taqdim etsa-da, ulardan foydalanish bajariladigan kodni qisqartirmaydi, chunki kompilyator har bir variant to'plami uchun funksiya yoki sinfning alohida nusxasini yaratadi. Natijada, umumiy kutubxonalar ichida kompilyatsiya qilingan kodni almashish imkoniyati yo'qoladi.
Shablon tavsifi sintaksisi
Funktsiya shabloni shablon kalit so'zidan boshlanadi, undan keyin burchakli qavslar ichidagi parametrlar ro'yxati keladi. Keyin funksiya deklaratsiyasi keladi:
shablon
bekor tartiblash ( T massivi [], int o'lchami ); // prototip: tartiblash shabloni e'lon qilingan, lekin aniqlanmagan
shablon
void sort( T array[], int size ) // deklaratsiya va ta'rif
{
Tt;
uchun (int i = 0; i < hajmi - 1; i++)
uchun (int j = o'lcham - 1; j > i; j--)
agar (massiv[j]
{
t = massiv[j];
massiv[j] = massiv[j-1];
massiv[j-1] = t;
}
}
shablon< int BufferSize > // butun son parametri
char * o'qish ()
{
char *Bufer = yangi belgi[ BufferSize ];
/* maʼlumotlarni oʻqish */
qaytarish buferi;
}
Typename kalit so'zi nisbatan yangi, shuning uchun standart[1] typename o'rniga sinfdan foydalanishga imkon beradi:
shablon
T o'rniga har qanday boshqa identifikator qabul qilinadi.
Foydalanish misoli
Eng oddiy misol - minimal ikki miqdorni aniqlash.
Agar a b dan kichik bo'lsa, a, aks holda b ni qaytaring
Shablonlar bo'lmasa, dasturchi foydalanilgan har bir ma'lumot turi uchun alohida funktsiyalarni yozishi kerak. Garchi ko'pgina dasturlash tillari elementar turlar (masalan, butun sonlar va haqiqiy sonlar) uchun o'rnatilgan minimal funktsiyani aniqlasa ham, bunday funktsiya murakkab (masalan, "vaqt" yoki "string") va juda murakkab ("" uchun" kerak bo'lishi mumkin. o'yinchi" onlayn o'yinda)
XULOSA :
3. Funktsiyalar va sinflar samarali dasturlash uchun kuchli va moslashuvchan vositalar bo'lsa-da, ular ba'zi hollarda C++ ning foydalaniladigan barcha parametrlarning turlarini belgilash talabi tufayli cheklangan. Masalan, ikkita sonning eng kattasini hisoblash uchun funksiya yozishimiz kerak deylik:
Agar biz butun sonlar bilan ishlasak, hamma narsa yaxshi. Ammo agar biz ikki tomonlama qiymatlar bilan ishlashimiz kerak bo'lsa-chi? Ehtimol, ikki turdagi bilan ishlash uchun max() funksiyasini ortiqcha yuklashga qaror qilasiz:
Endi bizda char, int, double va > operatorini haddan tashqari yuklasak, hatto sinflar bilan ishlaydigan bir xil funktsiyaning ikkita versiyasi mavjud! Biroq, C++ bizdan o'zgaruvchilarning turlarini ko'rsatishni talab qilganligi sababli, biz bir xil funktsiyaning bir nechta versiyasini yozishimiz kerak, bu erda faqat parametrlar turi o'zgaradi. Va bu, o'z navbatida, dasturchilar uchun bosh og'rig'i, chunki bunday kodni saqlash kuch va vaqt jihatidan oson emas. Va eng muhimi, bu samarali dasturlash tushunchalaridan birini buzadi - kodlarning takrorlanishini minimallashtirish. Har qanday turdagi parametrlar bilan ishlaydigan max() funksiyasining bitta versiyasini yozish yaxshi emasmi?
Bu mumkin. Shablonlar dunyosiga xush kelibsiz!
Agar lug‘atdagi “shablon” so‘zining ta’rifiga e’tibor qaratsangiz, biz quyidagilarni ko‘ramiz: “Shablon – shunga o‘xshash mahsulotlar tayyorlanadigan namunadir”. Misol uchun, shablon stencil - chizma / naqsh / belgi kesilgan ob'ekt (masalan, plastinka). Agar biz boshqa ob'ektga trafaret yopishtirib, bo'yoq purkasak, biz minimal kuch bilan bir xil naqshni olamiz, tez va eng muhimi, biz o'nlab bu naqshlarni turli rangda yasay olamiz! Bunday holda, bizga faqat bitta stencil kerak va biz rasmning rangini oldindan aniqlashimiz shart emas (stencilni ishlatishdan oldin).
C++ tilida funksiya shablonlari boshqa shunga o'xshash funksiyalarni yaratish uchun shablon bo'lib xizmat qiladigan funksiyalardir. Asosiy g'oya - ba'zi yoki barcha o'zgaruvchilarning aniq turini (turlarini) ko'rsatmasdan funktsiyalarni yaratish. Buning uchun har qanday ma'lumotlar turi o'rniga qo'llaniladigan shablon parametrining turini ko'rsatuvchi funktsiyani aniqlaymiz. Shablon parametr turiga ega funktsiyani yaratganimizdan so'ng, biz samarali tarzda "funktsiya trafaretini" yaratadi.
Funksiya shablonini chaqirganda, kompilyator funksiya uchun shablon sifatida "trafaret" dan foydalanadi, shablon parametri turini funktsiyaga uzatilgan o'zgaruvchilarning haqiqiy turi bilan almashtiradi! Shunday qilib, biz faqat bitta shablon yordamida funktsiyaning 50 ta "soyasini" yaratishimiz mumkin
Hozircha siz C++ da funksiya shablonlari qanday yaratilganiga qiziqayotgandirsiz. Bu unchalik qiyin emasligi ma'lum bo'ldi. max() funksiyasining butun son versiyasini yana bir bor ko'rib chiqing:
Bu erda biz ma'lumotlar turini uch marta aniqlaymiz: a, b parametrlarida va funktsiyaning qaytish turida. Bu funksiya uchun shablon yaratish uchun int turini funksiya shablon parametri turiga almashtirishimiz kerak. Bu holatda faqat bitta ma'lumot turi (int) ishlatilganligi sababli, biz shablon parametrlarining faqat bitta turini ko'rsatishimiz kerak.
Biz bu turni har qanday nomlashimiz mumkin, agar u zaxiralangan/kalit so'z bo'lmasa. C++ tilida bosh T harfi bilan shablon parametrlari turlariga murojaat qilish odatiy holdir (“Type” so‘zining qisqartmasi).
Foydalanilgan adabiyotlar:
1.Умаров, Ш. (2023). Выражение вторичных многочленов спектральными
2.Ziyonet.net web sayti
3.Fayillar.org Veb sayti
|