4-MA’RUZA
MAVZU: Konteynerlarning adapterlari.
Reja:
Stack, queue, priority_queue, deque.
Konteynerlar bilan ishlash algoritmlari.
Funktorlarning qo‘llanilishi.
Kalit so‘zlar: . Konteyner, adapter, shablon, sinf, moslashtirish, stack,(stek), queue
(navbat), priority_queue (ustuvor bilan navbat), deque (ikki
tomonlama navbat), maʻlumotlar tuzilmasi, push_back, pop_back, pop_front, LIFO, FILO, LIFO, for_each(), find(), funksional obʻyektlar, Operator(), Standart ML va funktor, Haskell va funktor.
KIRISh
Adapterlar standarti shablon kutubxonasining alohida toifasidir (vakilidir). Adapterlar yangi tushunchalar yoki ilovalar emas, balki mavjud kutubxona tushunchalarining o‘ziga xos, tez-tez ishlatiladigan maqsadlar uchun moslashtirishlari. Bu moslashtirish (adaptatsiyalash) ko‘pincha adapterning so‘rovlarnnig asosiy tushunchasiga asoslanib, funksiyalarini cheklash orqali amalga oshiriladi. Kutubxona konteynerlarning adapterlari, iteratorlar va funksiyalarni o‘z ichiga oladi.
Konteynerlarning adapterlari. Konteynerlarning adapterlari asosida adapterlarni hosil qilishning eng oson yo‘li misol orqali tushuntirishdir. Bular stack (stek), queue (navbat), priority_queue (ustuvor bilan navbat) misol bo‘ladi. Bu misollardan tushunarli bo‘ldiki, adapterlar:
juda keng va tez-tez ishlatiladigan maʻlumotlar tuzilmalari;
har qanday realizatsiyani alohida bajarilishi kerak emas. Ularning funksiyalarini taʻminlash uchun STL standart konteyneri har qanday moslashtirishda tayanch sifatida push_back, pop_back, yoki pop_front amallardan (adapter turiga qarab) foydalanish mumkin;
adapter uchun tayanch konteynerning to‘plamidan qo‘shimcha amallar chiqarib tashlanishi kerak (vahimalar yaratmaslik uchun, masalan, indekslash amali uchun, konteyner vektor bo‘lsa, stek moslashtirish ishlatiladi);
Konteynerlarning adapterlari uchun sintaktik taʻriflar misollar orqali qarab chiqish yaxshi natija beradi, shuning uchun misollar bilan tushntirib o‘tamiz. Birinchi navbvtda konteynerlarning adapterlari uchun <stack>, kabi sinflarni dasturga qo‘shish lozim.
Stek (stack, maʻlumotlar yig‘indisi): stekda uning elementlariga faqat bir uchidan murojaat qilish mumkinligi bilan xarakterlanadi va stekning yuqori qismi deb ataladi. Bu LIFO (Last In — First Out , birinchi kirgan oxiri chiqadi) tamoyili bo‘yicha faoliyat ko‘rsatuvchi maʻlumotlar to‘plamidir.
Stack elementlari satr bo‘lgan o‘zgaruvchini eʻlon qiladi. String obʻyektlar o‘zlari STL konteynerlar ekanligiga eʻtibor bering. Shunday qilib, stekkonteynerlarning har qanday elementlarini o‘z ichiga olgan konteynerlarni olishi mumkin (bu boshqa STL konteynerlari uchun xosdir).
stack eʻlon qilishni misollarning ko‘pchiligida stekka tavsif sifatida ko‘rish mumkin. Ko‘pchilik dasturchi buni boshqa bo‘lishi bilmasligi va tassafur qilmasligi mumkin. Lekin bir xil taʻrif mavjud stack> satrlari bir steki, bunda tayanch sinf vector tanlab olingan. Masalan, vector, list va deque yoki hatto dasturchining konteyner sinfi tayanch sinflar sifatida foydalanish. Baʻzan so‘rashdi, nima uchun stack< vektor> yozish mumkin emas (birinchi stringni o‘chirgan holda)? Chunki stack konstruktorini amalga oshirishda bu yo‘l belgilangan va bu juda mumkin. Ammo, butunlay boshqa turdagi tavsif bo‘ladi: string vektorlari to‘plami stack< vektor> umuman boshqa stek bo‘ladi (konteynerlarning tarkibiy joylashtirish haqidagi eslatma).
Juda ko‘p holarda stekni vektor ko‘rinishida initsializatsiya qilinda, ammo bu faqat C++11 variantida mavjud. 4.1-dasturda emplace() funksiyasidan stekka element qo‘shish uchun foydalanilgan.
Keyingi fragmentlarda, deyarli barcha amallarni (usullarini) ko‘rish mumkin: stack:push() – stekka bitta element qo‘shish, top() – stekning eng yuqorida turgan elementiga ko‘rsatkich olish, pop() – yuqori elementini chiqarib tashlash, size() – stekning joriy hajmi, empty() – stekning bo‘shligini tekshirish, swap() – ikki stekning almashtirish, operatop= stekni qiymat qilib boshqa bir tekka berish (o‘zlashtirish).
Dasturdan ko‘rish mumkinki, stek adapteri tayanch konteynerga xos usullarni yo‘qotdi (at(), operator[] va hokazo.), lekin push(), pop() funksiyalarni qayta aniqlash orqali orttirilgan hisoblanadi.
Stekni tushinib olib, o‘xshash funksiyalarni navbatga joriy qilish qiyin masala emas. Stekdan farqli o‘laroq, navbat FIFO (First In — First Out birinchi kirgan birinchi chiqadi) tamoyili bo‘yicha faoliyat yuritadigan maʻlumotlar to‘plamidir. (Bu usulni bir uchiga oqib kirish, keyin boshqa uchidan oqib chiqadigan quvurga o‘xshatish mumkin).
4.1- dasturda til semantikasi talabi bo‘yicha tahrirlarni qilib navbat uchun deyarli o‘zgarishsiz qoldiramiz va 4.2 dasturni olamiz.
4.2-dastur. Navbat sinfining funksiyalari.
// Created by MBBahodir #include "stdafx.h"
#include #include #include #include #include using namespace std;
int main() {
queue st, st_one, st_two; queue> vst;
vst.emplace("str1"); vst.emplace("str2"); vst.push("eostr");
for (int i=0; i<5; ++i) st.push(i);
for (int i = 0; i < 15; i++) st_one.emplace(i*10); st_two = st;
st.swap(st_one);
cout << st.size() << " " << st_one.size() << " " << st_two.size() << " " << vst.size() << endl;
while (!vst.empty()) {
cout << vst.front() << " : stack dagi oʻrni " << vst.size() << endl; vst.pop();
}
int size = st.size(); while (size--) {
cout << st.front() << " : stack dagi oʻrni " << st.size() << endl; st.pop();
}
|
while (st.size() != 0){
cout << st_two.front() << " : stack dagi oʻrni " << st_two.size() << endl; st_two.pop();
}
while (!st.empty()) {
cout << st.front() << " : stack dagi oʻrni " << st.size() << endl; st.pop();
}
cout << st.size() << " " << st_one.size() << " " << st_two.size() << " " << vst.size()
<< endl;
cout << " stack st " << (st.empty() ? "" : "not ") << " empty" << endl; cout << " stack vst" << (vst.empty() ? "" : "not ") << " empty" << endl;
cout << " stack st_one " << (st_one.empty() ? "" : "not ") << " empty" << endl; system("pause");
return 0;
}
|
navbatda pop_front() usuli vektor konteyner ustiga qurib bo‘lmaydi, , lekin uni ro‘yxat konteyner uchun qurish mumkin.
Deque sinfi uchun front(), push_back(), pop_front()), usullari har qanday konteynerlarda ishlatiladi (faqat pop_front() usuli borlarida).
shuning uchun navbat uchun yasaladigan obʻyektda, yaʻni deque sinfida top() usuli o‘rniga front() usuli ishlatiladi.
Maʻlum bir tartibda qayta ishlanishi kerak maʻlumotlarni uchun umumiy maʻlumotlar tuzilishiga asoslangan to‘plami bu – stek va navbatdir (stack, deque). Masalan, biror funksiya o‘z navbatida uchinchi funksiyani chaqiradigan boshqa funksiyani chaqirsa, uchinchi funksiya birinchi funksiyani emas, ikkinchi funksiyaga qaytishi muhimdir.
Bu maʻlumotlarni qayta ishlash tartibini amalga oshirish uchun dasturchi o‘zining navbat funksiyasi tashkil qilish lozim. Stekka qo‘shilgan oxirgi qiymat birinchi bajariladi va aksincha, stekka qo‘shilgan birinchi qiymat oxirgi bajariladi. Shunday qilib, maʻlumotlar tuzilmasining o‘zi chaqirishlarning to‘g‘ri belgilangan tartibda berilishini taʻminlaydi.
Konseptual, maʻlumotlar tuzilishi - stek juda oddiy: u maʻlumotlarni kiritish yoki chiqarish uchun maʻlum bir tartibni belgilaydi Har safar bir element qo‘shiladi, bu stekka yuqori element bo‘lib tugaydi. Stekdan olib tashlanadigan yagona element stekning yuqori qismida joylashgan elementdir. Shunday qilib, stekka “birinchi kirish, oxirgi chiqish — FILO” yoki “oxiri kirish, birinchi chiqish
— LIFO” deb ham aytiladi. Demak, Stekka qo‘shilgan birinchi element undan oxirgi chiqariladi.
Xo‘sh, bu nima? Nima uchun stek kerak? Yuqorida aytib o‘tganimizdek, funksiyalarni (qiymatlarni) chaqirishni tashkil qilish uchun qulay yo‘lidir. Aslida, stek chaqirish (call stack) tez-tez ishlaydigan yoki boshqa funksiyalarning qaytish qiymatini kutayotgan funksiyalar ro‘yxatiga murojaat qilish uchun ishlatiladigan atamadir.
Shuningdek, stek informatika faning fundametntal tilining bir qismidir. Agar birinchi kelib, oxirish ketish tamoyili asosida fikrlasangiz, unda stek terminini ishlatish lozim.
Bundan tashqari, bunday (stek kabi) navbatlar ko‘p jarayonlarda ishtirok etadi, nazariy informatikadan tortib, bunday push-down funksiyalari va juda ham ko‘p bag usullarida.
Stek assosiativ usullarga ega:
Push – stekka element qo‘shish.. Pop – stekdan element o‘chirish Top – elementni ko‘rish.
LIFO - stek xarakati.
FILO - stek xarakati (ekvivalet LIFO ga).
Stack (stek) maʻlumotlar tuzilmasini amalga kutubxona yaratish masalani qaraymiz. Umumlashgan dasturlash usuliga mos keladigan umumiy stack, yaʻni Stack sinfi uchun shablon yaratish degani. Agar shablonlar bilan tanish bo‘lmasangiz, funksiya shablonlariga oid nazariy maʻlumotlarga qarang, shablonlar bilan ishlash mexanizmi batafsil bilish lozim. Agar shablonlar bilan tanish, lekin sinf shablonlari bilan ishlashni unutgan bo‘lsangiz, sinf shablonlari haqida nazariy materiallarni o‘qib o‘rganing.
Bu stack shablonlari bilan amalga oshirildigan kutubxonani deyarli har qanday maʻlumotlar tipi uchun foydalanish mumkin. Bundan tashqari, stack hajmi dastur ijrosi davomida jadal belgilanadi. Stackga qo‘shimcha funksiya ham qo‘shildi peek(), bu stackning yuqori qismidan n- elementini qaytaradi.
4.3-dastur. Stack shablon sinfi
#ifndef STACK_H #define STACK_H
// Created by MBBahodir #include #include
#include
template class Stack{
private:
T *stackPtr; // stackka koʻsatkich
const int size; // stackdagi maksimal elementlar soni
int top; // stackning joriy elementi public:
Stack(int = 10); // stackning joriy holatda elementlar soni 10 ta Stack(const Stack &); // nusxalsh konstruktori
~Stack(); // destruktor
inline void push(const T & ); // elementni stackning yuqori qismiga joylashtirish
inline T pop(); // stack ichidan eng yuqoridagi elementni oʻchirish
inline void printStack(); // stackni ekranga chiqarish
inline const T &Peek(int ) const; // stackning yuqorisidagidam keyingi n-element inline int getStackSize() const; // stack oʻlchamini olish
inline T *getPtr() const; // stackka koʻrsatkich olish inline int getTop() const; // joriy elementni olish
};
// Stack sinfi shablon funksiyalarini realizatsiyz qilish
// konstruktor Steka template
Stack::Stack(int maxSize): size(maxSize) // oʻzgarmaslarni initsalizatsiyalash
{
stackPtr = new T[size]; // xotira ajratish top = 0; // joriy elementno 0 bilan toldirish;
}
|
// nusxalsh konstruktori template
Stack::Stack(const Stack & otherStack) : size(otherStack.getStackSize()) // oʻzgarmaslarni initsalizatsiyalash
{
stackPtr = new T[size]; // yangi xotira ajratish top = otherStack.getTop();
for(int ix = 0; ix < top; ix++) stackPtr[ix] = otherStack.getPtr()[ix];
}
// destruktor template Stack::~Stack()
{
delete [] stackPtr; // ochirish
}
// element qoʻshish template
inline void Stack::push(const T &value)
{
// oʻlchamni oʻzgartirish
assert(top < size); // joriy element soni oʻlchamdan kichik boʻlishi kerak
stackPtr[top++] = value; // elementni joylashtirish
}
// elementni oʻchirish template inline T Stack::pop()
{
// oʻlchamni tekshirish
assert(top > 0); // joriy element 0 katta boʻlishi kerak
stackPtr[--top]; // elementni oʻchirish return 0;
}
// yuqori elementdan n-elementni qaytaradi template
|
inline const T &Stack::Peek(int nom) const
{
//
assert(nom <= top);
return stackPtr[top - nom]; // n-elementni qaytarish
}
// ekranga chiqarish template
inline void Stack::printStack()
{
for (int ix = top - 1; ix >= 0; ix--)
cout << "|" << setw(4) << stackPtr[ix] << endl;
}
// oʻlchamni qaytarish template
inline int Stack::getStackSize() const
{
return size;
}
// koʻrsatkich qaytarish (nusxalash konstruktori uchun) template
inline T *Stack::getPtr() const
{
return stackPtr;
}
// oʻlchamni qaytarish template
inline int Stack::getTop() const
{
return top;
}
#endif // STACK_H
|
Stack shablon sinfi *.h (header) faylda yaratildi. Shablon sinf interfeysi va amalga oshirish ham bir xil faylda bo‘lishi kerak, bo‘lmasa, shunga o‘xshash mazmun bilan xato berishi mumkin.
error undefined reference to "method of a class template»
|
Yaʻni, xatolik, shablon sinf usullari havolalarda aniqsizlik.
Shablon sinf interfeysining fragmentlarida 9 -dan 28gacha yangilandi. Sinfning barcha usullari izohlarni o‘z ichiga oladi va mening fikrimcha, ularning funkiyalarini alohida taʻriflash mantiqiy to‘g‘ri emas. Stack shablon sinfning barcha usullari inline funksiyalari sifatida eʻlon qilinadi. Bu sinf ishini tezlashtirish maqsadida amalga oshiriladi. Sinfning ajralmas funksiyalari tashqi funsiyalarga qaraganda tezroq ishlaydi.
Shablon interfeysidan so‘ng, stack sinf usullari amalga oshiriladi, kutubxona fragmentlarida 32-117gacha yangilandi. Agar stack sinf, shablonlar va sinflar usullarini amalga oshirish haqida bilsangiz shablon sinfni yaratishda murakkab hech narsa yo‘q. Sinfda ikkita konstrkutor bor, birinchisi fragmentning 32-33 qatorlarida - bu standart konstruktor hisoblanadi. Fragmentning 41-50 qatordagi nusxa konstruktor hisoblanadi. Bir obʻyektni boshqasiga nusxalash uchun kerak. Peek usuli (funksiyasi), fragmentning 80-88 fatorlarida stack elementlarni ko‘rish imkonini beradi. Faqat element raqamini kiritishingiz kerak, hisoblash stack yuqorisidagi elementdan boshlanadi va keraklisini qaytaradi. Boshqa funksiyalari xizmatchi funksiyalar hisoblanadi, ular tashqi sinfdna foydalanish uchun mo‘ljallangan, yaʻni prinstack() funksiyasidan tashqari, bu funksiya stack elementlarini ekranga chiqaradi.
Endi stack shablon sinf uchun dastur tuzaylik va har doimgidek, stack sinf shablonni sinov bo‘ladi hamda asosiy funksiyalaridan foydalanishni ko‘ramiz.
4.4-dastur. Shablon sinfdan foydalanish.
// Created by MBBahodir include "stdafx.h"
#include using namespace std; #include "stack.h"
int main()
|
{
Stack stackSymbol(5); int ct = 0;
char ch;
while (ct++ < 5){ cin >> ch;
stackSymbol.push(ch); // element qoʻshish
}
cout << endl;
stackSymbol.printStack(); // ekranga chiqarish
cout << "\n\n Element oʻchirish\n"; stackSymbol.pop();
stackSymbol.printStack(); // ekranga chiqarish Stack newStack(stackSymbol);
cout << "\n\nNusxalash konstruktori!\n"; newStack.printStack();
cout << "2 tartibdagi element: "<< newStack.Peek(2) << endl; system("pause");
return 0;
}
|
4.4-dastur. Output.
|
b a h o q
| q
| o
| h
| a
| b
Element oʻchirish
|
| o
| h
| a
| b
Nusxalash konstruktori!
| o
| h
| a
| b
2 tartibdagi element: h
|
4.4-dasturda Bir stack obʻyektini yaratilgan, stack hajmi 5ga teng va stack ko‘pi o‘z ichiga olishi mumkin bo‘lgan elementlar soni 5 ga teng. stackni while takrorlanish operatori bilan to‘ldiriladi. Ekranda stack elementlarini chiqariladi, keyin stackdan bir elementi o‘chiriladi va yana ekranda stack elementlarini chiqariladi. Natija asosida u o‘zgardi, aniq bir element o‘chirildi.
Shuningdek, dasturda nusxa konstruktor ishlatiladi. Peek() funksiyasi stackning ikkinchi elementini qaytardi.
Stack shablon sinf yaxshi yaratildi va to‘g‘ri ishlamoqda. uni, masalan, int maʻlumotlar turida sinab ko‘rcangiz bo‘ladi. Ishonchim komilki, hamma narsa to‘g‘ri ishlaydi.
Navbat (queue). Navbat maʻlumotlar tuzilmasi bo‘lib (yuqorida aytib o‘tilganidek) bu LILO tamoyilini qo‘llab quvvatlaydi (last in-last out: oxirgi kirgan oxirgi chiqadi). C++ allaqachon tayyor STL konteyner-navbat (queue) mavjud.
Navbatda, birinchi elment kiritilgan bo‘lsa, u ham birinchi chiqariladi. 4 ta elementni qo‘shsangiz, birinchi qo‘shilgan element birinchi, ikkinchi qo‘shilgan element ikkinchi chiqadi.
Navbat qanday ishlashini tushunish uchun do‘kon navbatini tasavvur qilishingiz mumkin. Siz esa uning o‘rtasida turibsiz, shunda kassaning oldida turibsiz, avval oldingizdagi barcha odamlarga xizmat qilinishi. Lekin oxirgi navbatda o‘tgan kishi uchun, o‘zi tashqari barcha odamlarga xizmat qilish kerak emas.
Bu yuqorida keltirilgan ro‘yxatga qarang. Bulardan birortasini chiqarish uchun shu ketma-ketlik asosida chiqarib, keraklisiga to‘xtaladi. Masalan, 0 sonnini chiqarish, uchun avvl 3 ta son chiqariladi so‘ng kerakli son.
Stack shablon sinfida bir peek() (bu indeks bo‘yicha elementni qaytaradi), bu navbat shablonida muayyan elementni ko‘rish mumkin emas.
Agar barcha navbat elementlarga kirish kerak bo‘lsa, lekin, navbatda buni amalga oshirish mumkin. Keyinroq bu qanday amalga oshirishni ko‘rsatib o‘tamiz.
C++da navbat yaratish. Agar C++ da navbat shablonini ishlatmoqchi bo‘lsangiz, avval kutubxonasini ulashingiz kerak.
Keyin navbatni eʻlon qilish uchun quyidagi sintaktikni ishlatishingiz kerak:
Birinchi queue so‘zini yozishimiz kerak.
Type ga navbatni to‘ldirish uchun kerakli tipni ko‘rsatishimiz lozim. Navbat obʻyektining nomini ko‘rsatishamiz kerak.
Masalan,
Navbat usullari va funksiyalari:
Navbatda funksiya bu bir xil funksiyadir, lekin u faqat STL konteynerlari bilan ishlaydi. Bu funksiyalarga push(), pop(), front(), back(), empty() funksiyalar kiradi.
push() – navbatga yangi element qo‘shish.
pop() – navbatdan birinchi elementni o‘chirish, ikkinchi element birinchi element o‘rniga suriladi.
front() – navbatdagi birinchi elemeniga murojaat back() - navbatdagi birinchi elemeniga murojaat
empty() – navbat bo‘sh yoki bo‘shmasligini tekshiradi. Agar bo‘sh bo‘lsa true, aks holda false qiymat qaytaradi.
Bu keltirilgan funksiyalarga doir 4.5-dasturini keltiramiz.
4.5-dastur. Navbat funksiyalaridan foydalanish.
// Created by MBBahodir #include "stdafx.h" #include #include
using namespace std;
int main() { queue q;
for (int h = 0; h < 7; h++) { q.push(rand()%100);
}
cout << "Navbatdigi birinchi element " << q.front() << endl; cout << "Navbatdigi oxirgi element " << q.back() << endl; q.pop();
cout << "Navbatdigi birinchi element (oʻchirishdan soʻng): " << q.front() << endl; cout << "Navbat boʻsh " << (q.empty()?"":"emas") << endl;
system("pause"); return 0;
}
|
4.5-dastur.Output.
|
Navbatdigi birinchi element 41 Navbatdigi oxirgi element 78
Navbatdigi birinchi element (oʻchirishdan soʻng): 67
Navbat boʻsh emas
|
|
