Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja
Hajmlar va o‘lcham bilan ishlash usullari
Download 127.31 Kb.
|
tl4Z0UMKrTZbC9NdE9w9eYsMfgJB5joUuJ9400gY
- Bu sahifa navigatsiya:
- Qidirish usullari
Hajmlar va o‘lcham bilan ishlash usullari: empty() – true qaytaradi, agar to‘plam bo‘sh bo‘lsa false, size() - to‘plamdagi elementlar sonini qaytaradi, max_size() – mumkin bo‘lgan elementlar sonini qaytaradi.
Modifikatorlari: clear() – konteynerni tozalaydi, insert() – element qo‘shish, erase() – elemeni o‘chirish, swap() – o‘rin almashtirish, emplace() – joydi elementni yaratish. Qidirish usullari: set to‘plam bilan ishlaganda qidirish muhim xisoblanadigan aspekt bo‘lib hisoblanadi. Qidirishni samarali tashkil qilish uchun bir nechta o‘zning usullariga ega: count(key), find(key), equal_range(key), lower_bound(key), upper_bound(key) Taqqoslash va birlashtirish amallari: set to‘plam uchun barcha taqqoslash amallari amal qiladi. ning ketma-ket konteynerlarga amal qilgan barcha amal o‘rinli. [=] (operator=) operatorni elementlar to‘plamini olish uchun ishlatiladi. Masalan, other to‘plamning nusxasini yangi bir other_one to‘plamga nusxalash uchun ishlatiladi (other_one = other). Semantik nusxalashni amalga oshirish usuli other to‘plamning nusxasini yangi bir other_one to‘plamga to‘liq nusxalash uchun ishlatiladi va other to‘plami o‘chirilmaydi, ammo uning holatini aniqlab bo‘lmaydi other_one = move(other). masala. [10, 50] intervalda N ta ketma- ket sonlar tasofidiy berilgan. {10, 20, 30, 40, 50} berilan sonlardan joriy ketma-ketlikda nechtadan bor. 3.3(a)-dastur. 1-masalaning dasturi. #include "stdafx.h" #include int main() { default_random_engine rnd(time(0)); uniform_int_distribution int n, k = 0; cout << "n = "; cin >> n; for (int i = 0; i < n; i++) { int d = g(rnd); myVektor.push_back(d); cout << myVektor[i] << " "; }
set for (int i=1; i<=5; ++i) mySet.insert(i*10); cout << endl;
Oldinroq juda tez-tez elementlarni kiritish va o‘chirish algoritmlarni foydalanish kerak emas deb aytgan. Vektor va to‘plam bilan ishlash samaradorligini taqqoslaylik. To‘plam va vektorning massivlarini tasodifiy sonlar bilan to‘ldiradigan va belgilangan qiymatni qidiradigan dastur yarataylik. 3.3(b) – dastur. Vektor va to‘plam bilan ishlash samaradorligini taqqoslash.
To‘plamning ishlashi vektordan sezilarli darajada past bo‘ladi. Shuni yodda tutingki, to‘plamni to‘ldirish amali saralash bilan amalga oshiriladi va bu albatta, qimmatbaho amal. Lekin, faqat qidirish uchun, har ikki konteynerlarni ishlash solishtiradigan bo‘lsa, vaziyat
Bundan qanday xulosa chiqarish mumkin? set yordamida (yoki multiset) takrorlanish jarayonlarini dasturlashda ketma ketlikdan elementlarni olish, yoki tez-tez o‘chirish va elementlar kiritish bu noto‘g‘riyondashuv hisoblanadi. Set to‘plam obʻyektini yaratish uchun takrorlanish jarayonlari asosida shakllantirilgan ketmk ketlik foydalanish kerak yoki tayyor to‘plam uchun insert funksiyasidan foydalanish maqsadga muvofiq. Ammo, dastur tez-tez elementlarni qidirish ishlatilsa, set raqobatga chiqa olmaydi. pair - yordamchi sinfi. Boshqa assotsiativ konteynerlar bilan ishlashni yanada ko‘rib chiqish uchun pair yordamchi shablon sinfi bilan tanishishimiz kerak. Bu sinf birlik sifatida ikkita obʻyektlarni saqlash imkoniyatini beradi. pair STD ning turli joylarida, xususan minmax() algoritmida, set equal_range() sinfining usulida, shuningdek juft (key, value) bo‘lgan assosiativ konteynerlar elementlari bilan ishlash uchun ishlatiladi. pair - bir juft obʻyekt yaratish uchun quyidagi konstruktor sintaktiki ishlatiladi:
Amalari: p.first – havola bo‘yicha juftlikning birinchi elementiga murojaat. p.second – havola bo‘yicha juftlikning ikkinchi elementiga murojaat. p->first – ko‘rsatkich bo‘yicha juftlikning birinchi elementiga murojaat. p->second – ko‘rsatkich bo‘yicha juftlikning ikkinchi elementiga murojaat. p = other_p – qiymat qilib berish (C++ qoidasiga asosan oshkormas tip almatirish yordamida). p.swap(other_p) yoki swap(p, other_p) –p va other_p lar uchun o‘rin almashtirish. <, <=, >, >=, ==, != – taqqoslash amallari make_pair(val1, val2) – juftlikni beradi. 3.4-dastur. Pair konstruktori va amallarini ishlatish.
Assosiativ konreynerlar uchun map va multimap sinflari. map assotsiativ konteyneri (xarita, lug‘at) o‘z-o‘zini muvozanatlovchi daraxtga (qizil-qora daraxt) asoslangan to‘plamlar bilan bir xil tarzda amalga oshiriladi. To‘plam va lug‘at o‘rtasidagi asosiy farq shundaki, map massivi kalitlardan tashkil topgan elementlar juftlarining tartibli assotsiativ massivi (konteyneri) va ularning mos qiymatlaridan iborat. Lug‘atda kalitlari unikal (takrorlanmaydigan) va multimap bir nechta nusxadagi kalitlari bo‘ladi. Lug‘atlarda kalit va qiymat turlari fundamental tip yoki abstrakt tip bo‘lishi mumkin. Agar kalit tipi abstrakt tip bo‘lsa, uning uchun saralash yo‘nalishini belgilovchi komparator funksiyasi (taqqoslash funksiyasi) aniqlanishi kerak. Kalit doimiy qiymatga ega va kalit qiymatini o‘zgartirish mumkin emas. Juftlikning ikkinchi element qiymatini (asosiy qiymatini) o‘zgartirish mumkin. Map (yoki multimap) sinflari bilan ishlashni boshlash uchun dastur sarlavhasiga (ikkala sinf bilan birgalikda) quyidagi dastur fragmenti yozildi (bu oldin ham barcha assosiativ konteynerlar uchun aytilgan edi):
Konstruktorlar. Lug‘at obʻyektlari shablon parametrlarini: kalit tipi va kalitning qiymati tipi (key va T), taqqoslash (comp)funksiyasini o‘z ichiga oladi. Agar bunday funksiya bo‘lmasa, u oshkormas less <> funksiya (operation <) tomonidan o‘rnatiladi. Quyidagi konstruktorlar yordamida map sinf obʻyektlarini yaratiladi: Oddiy map konreyner konstruktorlari: map Nusxalash uchun konstruktor: map Iteratorlar yordamida qo‘shish uchun konstruktorlar: map Ro‘yxat asosida initsializatsiya qilish konstruktorlari: map
Bu yerda Comp konteyner kalitlari solishtirish uchun funksiyasi (ixtiyoriy). Bundan tashqari, taqqoslash funksiyaning yonida konstruktor ixtiyoriy Allocator() vazifasini o‘z ichiga oladi (soddaligi uchun yozilmaydi), dasturchi uning allocator vazifasini ham belgilaydi. Map sinfining destruktori: ar.~map(); Lug‘at usullari. Lug‘at usullari set to‘plam usullari bilan bir xil bo‘lganligi uchun ularni takrorlab keltirmaymiz. Bu usullar qanday ishlashini misol yordamida ko‘rsatamiz. Aytaylik, quyidagicha lug‘at yaratishimiz kerak: kalitga tasodifiy (string), qiymatga tasodifiy (integer) o‘rnatiladi. So‘ngra key1 va key2 orasidagi barcha key = > qiymat juftliklarining chiqishi talab qilinsin. Dastur oxirida key 3 kalit uchun maksimal qiymatni chiqarish talab qilinadi (dasturning o‘zidagi izohlarga qarang). 3.5-dastur. Lug‘at usullaridan foydalanish.
Elementlarga murojaat. Lug‘atlarda elementlarga kirishning yana ikkita usuli mavjud (iteratorlar bilan ishlashdan tashqari). Birinchi usul at(key) usulini qo‘llashdir (bilsangiz kerak). Biroq, indeksni argument sifatida qabul qilmaydi, lekin kalitning qiymatini qabul qiladi. Bu usul kalitga ekvivalent bo‘lgan kalit bilan mos elemeni qiymatiga mos yozuvlar qaytaradi. Agar bu element mavjud bo‘lmasa, out_of_range istisno funksiyasining qiymati qaytariladi. Boshqacha aytganda, massivda bunday kalit bor-yo‘qligini tekshiradi. Ikkinchi usul overloaded[] funksiyadan foydalanishga asoslangan. Lekin quyidagi sabablarga ko‘ra ehtiyotkorlik bilan foydalanish zarur. ar(key) mavjud bo‘lmasa, standart konstruktor yordamida kalit bilan yangi element qator qo‘shiladi. Aks holda elementga ko‘rsatkich qaytariladi. Eslattb o‘tamizki, indekslash funksiyasini assotsiativ konteyner sinflarning ikki turga (map va unordered_map) foydalanish mumkin. Ushbu usullarni ishlab chiquvchilar tomonidan qo‘shilishining sabablari aniq: dastur juda qisqa va chiroyli bo‘ladi. at() funksiyasi istisno qaytargani uchun try - catch funksiyasi bilan quyidagicha boshqarish mumkin:
Dastur fragmentida "U" kalitli juftlik topilmasa, uni yaratib, yangi qiymat beradi. rat["U"] = 15; (hiyla, ruscha fishka) indekslash amali u faqat asosiy qiymatini olish emas, balki bu qiymatini o‘zgartirish mumkin degan maʻnoni anglatadi, bir qiymatini qaytaradi. Boshqacha qilib aytganda, ushbu dastur fragmenidagi amallarini bajarish mumkin:
map >> to‘plam pair
Bu kabi elementlarni qo‘shish samarali hisoblanib, T obʻyektni yaratishga imkon bermaydi (yuqoridagi fragmentda aniq T() konstruktor chaqirilgan). Agar operator[] noqulay va samarasiz deb hisoblasangiz, yana unga ikkita alternativ variantlar bor. Birinchisi find funksiyasidan foydalanib,kalit bo‘yicha (key, value) juftligiga mos iteratorni olish yoki kalit lug‘atda bo‘lmasa, end() funksiyadan foydalanish mumkin. Ikkinchisi at() funksiyasidan, yaʻni kalit asosida qiymatni qaytaradi. Agar kalit bo‘lmasa, istisno holatga o‘tadi. Map sinfining umumiy shabloni quyidagicha:
Map sinfining operatorlari, xususiyatlari, funksiyalari va usullarini qo‘rib chiqamiz. Typedef operatorlari :
Xotirani ajratish va bo‘shatish (xolli qilish) operatorlari (allocation/deallocation):
Ruxsat etish vositalari (accessors):
Qo‘shish va o‘chirish funksiyalar (insert/erase):
Map sinf usulari:
Mantiqiy operatorlari:
iterator- ikki tomonlama iterator bo‘lib value_type ishora beradi. Aniq tipi amalga oshirish bilan bog‘liq va Allocator asosila belgilanadi. const_iterator- doimiy ikki tomonlama iterator bo‘lib const value_type ishora beradi. Aniq tipi amalga oshirish bilan bog‘liq va Allocator asisida belgilanadi. Bunda iterator va const_iterator uchun konstruktor bor, bu kafolatlanadi. size_type – butun ishorasiz tip. Aniq tipi amalga oshirish bilan bog‘liq va Allocator asisida belgilanadi. difference_type - butun ishorali tip. Aniq tipi amalga oshirish bilan bog‘liq va Allocator asisida belgilanadi. Assotsiativ konteynerlar uchun standart usullar to‘plamidan tashqari, lug‘at Allocator::reference operator[](const key_type&) amalini taʻminlaydi. Masalan, m lug‘atda k kalit yuilan m[k] kuyidagi fragment bilan ekvmvalent:
Download 127.31 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling