Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja

3- MA’RUZA

MAVZU: ASSOSIATIV VA TARTIBLANMAGAN ASSOSIATIV KONTEYNERLAR
Reja:

1. 
   Assosiativ konteynerlar (set, map, multiset, multimap).
   

2. Tartiblanmagan assosiativ konteynerlar (unordered_set, unordered_map, unordered_multiset, unordered_multimap).

Konteynerlar va ketma-ket konteynerlar bo‘yicha nazariy va amaliy imkoniyatlarini bilamiz. Shuning uchun konteynerlarning ikkinchi turi bo‘lgan assosiativ konteynerlarni boshqa konteynerlar farqli bo‘lishi kerak. Assosiativ konteynerlari kalit asoisda maʻlumotlarni to‘plamdan tez izlab topish uchun ishlatiladi. Tartiblangan konteynerlar muvozanatlashgan binar daraxt ustiga quriladi va qatʻiy tartibga tayanadi ("kichik" amali [<] operatori asosida hisoblangan). Ikkita element bir biridan kichik bo‘lmasa, ekvivalent hisoblanadi.
Buning kutubxonasi 4 ta asosiy set (to‘plam), multiset (multi to‘plam, ko‘p to‘plam), map (lug‘at) va multimap (mulilug‘at, ko‘p lug‘at) assosiativ konteynerlar bilan ishlashga qaratilgan. Bu konteynerlar Key kalitini o‘zlariga asosiy paramert sifatida oladi va Compare munosabati bo‘yicha tartiblaydi. Tartiblash Key paramert bilan amalsha oshiriladi. Shuningdek, map va multimap erkin T tipida Key bilan assosiativlanadigandir (sherikdir). Compare obʻyektining tipi taqqoslanaligan konteyner obʻyekti (comparison object) deb aytiladi.
Shuning uchun bu konteynerlarning umumiy xususityati va amallaridan boshlaymiz. Barcha assotsiativ konteynerlar quyidagi amallarni qo‘llab- quvvatlaydi:
count – elementlar sonini qaytaradi, belgilangan kalit bo‘yicha elementlar sonini qaytaradi;

find –elementga ko‘rsatkichga mos bo‘lgan iteratorni qaytaradi, agar bunday bo‘lmasa end() funksiyasini vazifasini bajaradi.

equal_range - berilgan intervaldigi barcha elementlar uchun iteratorlar juftligini qaytaradi.

Katitlarning tengli xaqida munosabatlarning ekvivalentligi Kalitlar uchun shartli taqqoslash va (not) operator== tahlil qilamiz.

Key1 va key2 kalitlar o‘zaro teng hisoblanadi, agar taqqoslanadigan obʻyektlar uchun comp chin qiymat qaytarsa, yaʻni:

comp(k1, k2) == false && comp(k2, k1) == false

Assosiativ konteynerlar har qanday kalit qiymat uchun bitta eng katta elementning qiymatini saqlasa, unikal (takrorlanmaydigan) kalitlarni (unique keys) qo‘llab quvvatlaydi. Aks hoda
ular teng qiymatli kalitlarni (equal keys) ham qo‘llab quvvatlaydi. set va map konteynerlar unikal kalitlarni, multiset va multimap konteynerlar teng qiymatli kalitlar bilan ishlashga mo‘ljallangan.
set va multiset konteynerlar uchun aniqlanadigan tip va kalit tipi bir xil bo‘ladi.


map va multimap konteynerlar uchun pair Key, T> jufligi bo‘ladi.
Assosiativ konteynerlarning iteratorlari ikki tomonlama iteratorlar sinfiga kiradi. Insert konteyner havolalari va iteratorlarning inkor qilmaydi. Elementlarni o‘chirishda erase faqat iterator va havolalarni inkor qiladi.
3.1-jadvalda assosiativ konteynerlarning talablari keltirilgan (konteynerlarga qo‘shimacha). Unda x bu assosiativ sinf, a – X ning qiymati, Agar X unikal kalitni ko‘llab quvvatlasa, a_uniq – X ning qiymati, Agar X bir nechta kalitni ko‘llab quvvatlasa, a_eq – X ning qiymati, i va j – iteratorning kirish talablarini qanoatlantiruvchi va value_type elementni ko‘rsatadi (beradi), [i, j) - interval, p – a uchun ruxsat berilgan iterator, q – a uchun o‘zgartiriladigan iterator, [q1, q2) - a da ruxsat berilgan interval, t - X::value_type ning qiymati, k - X::key_type ning qiymati.
3.1-jadvalda assosiativ konteynerlarning talablari.

Ifoda	Qaytarila- digan tipi	tasdiq/ oldingi yoki keyingi holatiga izox	murakkabligi
X::key_type	Key	.	Kompilyatsiya vaqti
X::key_compa re	Compare	less joriy holat	Kompilyatsiya vaqti
X::value_comp are	binar predikat turi	xuddi, key_compare uchun set va m ultiset; munosabati tartiblangan juftlik, map va multimap uchun chaqirilgan birinchi elementdek (Key)	Kompilyatsiya vaqti

X(c) X a(c);	.	Bo‘sh konteyner yaratish; taqqoslash obʻyekti sifatida foydalanish uchun.	Doimiy
X() X a;	.	Bo‘sh konteyner yaratish; taqqoslash obʻyekti sifatida Compare() dan foydalanish uchun	Doimiy
X(i,j,c) X a(i,j,c);	.	Bo‘sh konteyner yaratish [i, j) intervaldan qiymat qo‘shish; taqqoslash obʻyekti sifatida foydalanish uchun..	NlogN (N - i dan j gacha); chiziqli , agar [i, j) value_comp() bilan saralangan bo‘lsa
X(i,j) X a(i,j);	.	Bo‘sh konteyner yaratish [i, j) intervaldan qiymat qo‘shish; taqqoslash obʻyekti sifatida Compare() dan foydalanish uchun	NlogN (N - i dan j gacha); chiziqli , agar [i, j) value_comp() bilan saralangan bo‘lsa
a.key_comp()	X::key_compar e	Taqqoslash obʻyektini qaytaradi	doimiy
a.value_comp( )	X::value_comp are	Taqqoslash obʻyekti uchun yaratilgan value_compare obʻyektni qaytaradi	doimiy
a_uniq.insert(t)	pair	Agar konteynerda t kalitli element bo‘lmasa, t ni qo‘shish,	logarifmik

		juftlikda komponentning bool qiymati qo‘shish bajarilganligini, iterator t kalitli elementni ko‘rsatadi
a_eq.insert(t)	iterator	t ni qo‘shadi va iteratorni qaytaradi, qo‘shishilgan elementni ko‘rsatadi.	logarifmik
a.insert(p, t)	iterator	t ni qo‘shish, agar faqat va faqat unikal kalitli konteynerda t kalitga teng kalitli element bo‘lmasa; har doim nusxalari bilan konteynerlarga t ni qo‘shish. har doim t kalitli elementni ko‘rsatuvchi iteratorni qaytaradi. p iterator – qo‘shish qaerdan boshlanishini ko‘rsatuvchi izoh	umuman logarifmik, lekin domiyga intiladi, agar t to‘g‘ri p ni yoniga qo‘yilgan bo‘lsa.
a.insert(i, j)	Natija ishlatilmaydi	[i, j) intervaldan konteynerga elementlarni qo‘shadi;	Umuman, Nlog(size()+N) ( N – i dan j gacha); chiziqli, agar [i, j) value_comp() bilan kelishgan holda saralangan

			bo‘lsa
a.erase(k)	size_type	konteynerda k kalitga teng bo‘lgan barcha e lementlarni o‘chiradi. o‘chirilgan elementlarning sonini qaytaradi.	log(size()) + count(k)
a.erase(q)	Natijasi ishlatilmay-di	q bilan ko‘rsatilgan elementni o‘chiradi	domiyga intiladi
a.erase(ql, q2)	Natijasi ishlatilmay-di	[ql, q2) intervaldagi barcha elementlarni cho‘chiradi.	log(size())+ N, N - ql dan q2 gacha.
a.find(k)	iterator; const_iterator – a uchun o‘zgarmas	k kalitli elementni ko‘rsatuvchi iterator yoki agar bunday element topilmasa a.end() qaytaradi	logarifmik
a.count(k)	size_type	k kalitli elementlar sonini qaytaradi.	log(size()) + count(k)
a.lower_bound (k)	iterator; const_iterator a uchun o‘zgarmas	k kalitli elementdan kichik bo‘lmagan birinchi elementni ko‘rsatuvchi iteratorni qaytaradi	logarifmik
a.upper_bound (k)	iterator; const_iterator a uchun o‘zgarmas	k kalitli elementdan katta bo‘lgan birinchi elementni ko‘rsatuvchi iteratorni qaytaradi	logarifmik
a.equal_range(	pair	make_pair(lower_boud(k),	logarifmik

k)

iterator>; pair a uchun o‘zgarmas

upper_bound (k)) ga ekvivalent

Assotsiativ konteyner iteratorlarining asosiy xususiyati shundaki, ular konteynerlar orqali o‘sish tartibidagi kalitlar tartibida iteratsiyalanadi, bu yerda o‘sish tartibi ularni yaratish uchun ishlatilgan taqqoslash bilan belgilanadi.
Ikkiia ixtiyoriy o‘zguruvchan I va j iteratorlar uchun I dan j gacha masofa musbat bo‘ladi, yaʻni value_comp (*j, *i) == false. Unikal kalitli assotsiativ konteynerlar uchun kuchliroq value_comp (*i, *j) == true holat saqlanib turibdi.
Barcha tartiblangan konteynerlar ikki tomonlama iteratorlar yordamida elementlarga murojaat qilish imkonini beradi. Kalit asosida qidirishda berilgan kichik bo‘lmagan birinchi elementni lower_bound() funksiyasi va birinchi katta elementni upper_bound() funksiyasi yordamida amalga oshiriladi (3.1-jadvalga qarang). Agar mymap konteyner berilgan bo‘lsa, unda mymap.equal_range(key) funksiyasi bilan ekvivalnt bo‘ladi (3.1-dasturga qarang).
3.1-dastur. Tartiblangan konteynerlar funksiyalari.

// created by Mbbahodir #include "stdafx.h" #include #include

cout << mymap.count('c') << endl; cout << mymap.find('c')->second << endl; ret = mymap.equal_range('b'); char key = 'b'; make_ret = make_pair(mymap.lower_bound(key),mymap.upper_bound(key)); cout << "Kichik boʻlmagam element: "; cout << ret.first->first << " => " << ret.first->second << '\t'; cout << make_ret.first->first << " => " << make_ret.first->second << '\t'; itlow = mymap.lower_bound ('b'); cout << itlow->first << " => " << itlow->second << endl; cout << "katta boʻlgan birinchi element: "; cout << ret.second->first << " => " << ret.second->second << '\t'; cout << make_ret.second->first << " => " << make_ret.second->second << '\t'; itup = mymap.upper_bound ('b'); cout << itup->first << " => " << itup->second << endl; system("pause"); return 0; }

3.1-dastur. Output

1 303 Kichik boʻlmagam element: b => 202 b => 202 b => 202 katta boʻlgan birinchi element: c => 303 c => 303 c => 303

3.1-dastur tahlili. Dasturda 4 ta elementdan iborat map konteyner berilgan. ʻsʻ kalitli element soni count() funksiya bilan aniqlagan. Xuddi shu kalit bilan uning qiymati find() funksiya bilan topilgan. equal_range('b'), mymap.lower_bound('b'); mymap.upper_bound('b'); make_pair( mymap.lower_bound(key), mymap.upper_bound(key)); funksiyalarining ekvivalet ishlari ko‘rsatilgan.

Takrorlanmaydigan (unikal) tartiblangan elementlar to‘plami