Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja
Download 127.31 Kb.
|
tl4Z0UMKrTZbC9NdE9w9eYsMfgJB5joUuJ9400gY
- Bu sahifa navigatsiya:
- Tartiblanmagan assosiativ konteynerlar va
(*((m.insert(make_pair(k, T()))).first)).second
Assotsiativ konteynerlar asosiy xususiyatlari
Tartiblangan unikal kalitga ega bo‘lmagan map – multimap sinfi hisoblanadi. Bu sinf operator[] standart operatorni qo‘llab quvvatlamaydi, va multiset juftligini eslatadi. Bunda qidirish faqat birinchi maydon, yaʻni kalit maydon bilan amalga oshiriladi. multimap sinfini o‘rganib chiqish uchun, misol sifatida matnli faylga yozilgan lug‘atga murojaat amallarini ko‘rsatamiz. Faraz qilaylik lug‘at so‘zlar juftligidan tashkil topgan va birinchi so‘z kalit bo‘lsin va takrorlanishi mumkin. “so‘z - tarjimasi” tipini aniqlash. Bunda so‘z juftligini olamiz va lug‘al element deb qaraymiz.
Lug‘at tipini aniqlash
Standart kirish va chiqish operatorlari quyidagicha aniqlaymiz.
Lug‘atga kirish uchun amal. Belgilangan lug‘at uchun yangi lug‘at chiqaradi.
Lug‘at elementiga murojaat va o‘qish.
Std sinfida aniqlangan istream_iterator va ostream_iterator tiplaridan foydalanganlik uchun [<<] va [>>] operatorlari shu fazoaga moslab yaratilgan. Bu foydalanuvchiga kirish va chiqish operatorlari va standart tiplardan foydalanish ruhiyatiga taʻsir qilmaydi. Multimar sinfning konstruktori map sinfiniki bilan bir xil. Multimar sinfning map sinfinikidan farf qiladigan operatorlari:
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.
Ikkita element uchun xeshlari teng bo‘lsa va tenglik amali chin (true) qiymat qaytarsa, ular ekvivalent hisoblanadi. Tartiblanmagan konteynerlari bir tomolama iteratorlar bilan elementlariga murojaat qilish kerak. Tartiblanmagan standart assosiativ konteynerlarga quyidagi shablon sinflar kiradi:
Bularning funksionalligi tartiblangan assosiativ konteynerlarga o‘xshaydi. Tartiblanmagan konteynerlarda xesh jadvalni shakllantirishning o‘ziga xosligi lower_bound va upper_bound funksiyalariga egamasligidir. Ammo, berilgan kalitga mos bir intervaldagi elementlarni olish uchun equal_range funksiyasi ishlatiladi. O‘rtacha tariblanmagan konteynerlarda elemetnlarni qo‘shish, qidirish va o‘chirish o‘rtacha doimiy vaqt talab va tartiblanganlarga nisbatan sezilarli darajada tezroq bo‘lishi mumkin. Biroq, eng yomon holatda ham vaqtga chiziqli erishish mumkin. Samaradorligi hesh funksiyasini amalga oshirish sifatiga bog‘liq, lekin butunlay bunday vaqt ajratishni oldini olish mumkin emas. Shuning uchun, interaktiv dasturlarda (masalan, o‘yinlar), tartibga solinmagan konteynerlar davriy kechikishlar tufayli tartiblanganlardan ko‘ra yomonroq bo‘lishi mumkin. Katta sondagi elementlar qo‘shish uchun, kerakli vaqtda bir qator kiritishda "rehash"ga oshirish mumkin (ko‘p vaqt oladigan ajratilgan saqlash va qayta tarqatish elementlar hajmini oshirish) rehash funksiyasini chaqirib to‘g‘ri hisoblanadi (vektor uchun reserve funksiyasiga o‘xshaydi). Ayrim vazifalarda saralash uchun vaqt ko‘p ajratilsa avtomatik saralashni muhim kamchilik deb hisoblash mumkin. Bu holda, tartiblangan to‘plam va lug‘atlar sinflarini tartiblanmagan assotsiativ konteynerlar sinflar (unordered_set, unordered_multiset, unordered_map va unordered_multimap) tomonidan o‘zgartirilishi mumkin. Tartiblanmagan konteynerlarda qidirish, qo‘shish va o‘chirish amallari o‘rtacha doimiy vaqt murakkabligiga ega va u O (1) ga tengdir. Tartiblanmagan konteynerlar xesh jadvallar sifatida amalga oshiriladi. Xesh- jadvalda amalni bajarish xesh-funksiyada (xeshlash) kalitdan boshlanadi. Olingan xesh qiymati (shuningdek, xesh yoki xesh kodi) massivda indeks rolini bajaradi. Xesh jadvali oddiy lug‘atga o‘xshaydi, unda tom maʻnoda xesh qiymati deb hisoblash mumkin. Tartiblanmagan konteynerlarning xesh jadvallarida yacheykalari bor va ular cheksiz ko‘p elementlarni o‘z ichiga olishi mumkin. Bu yacheeykani segment deb ataymiz. Aslida, segment (xesh bilan bog‘liq) ulangan ro‘yxatdir. To‘plam hajmiga nisbatan saqlanadigan elementlar soni mos kelsa, (xesh funksiyasi uchun mumkin bo‘lgan elementlar soni) xesh jadvalni to‘ldirish (load factor) koeffitsienti deb yuritiladi va o‘rtacha amal ijro vaqt belgilaydigan muhim parametr hisoblanadi. Unordered_set va unordered_multiset sinflari bilan ishlashni boshlash uchun unordered_set sarlavhasini (ikkala sinf bilan birgalikda) quyidagicha qo‘shish kerak:
unordered_map va unordered_multimap sinflari ham xuddi yuqoridagidek qo‘shiladi:
Tartiblanmagan konteynerlarning tiplari quyidagi shablon parametrlarini o‘z ichiga oladi: const Key – kalit tipi (unordered_set, unordered_multiset, unordered_map, unordered_multimap). T – qiymatning tipi (unordered_map, unordered_multimap). alloc –allokator funksiya (majburiy emas, erkin). size_type bucket_count – initsializatsiya qilishda foydalanish uchun minimal yacheykalar soni (agar ko‘rsatilmagan bo‘lsa, joriy holat bo‘yicha olinadi). hash – xesh-funksiya (erkin). equal – taqqoslash fueksiyasi, kalitlarni solishtirish uchun ishlatiladi (erkin). Quyidagi konstruktorlar asosida unordered_set va unordered_map sniflarining obʻyektini quradi: unordered_set Agar hash xesh funksiya yozilmagan bo‘lsa, joriy holat bo‘yicha hash Agar equal taqqoslash funksiyasi yozilmagan bo‘lsa, joriy holat bo‘yicha equal_to<> (operator==) funksiyasi ishlatiladi. Soddaligi uchun Allocator () va bucket_count yozilmaydi. Nusxalash konstruktrlari:
Iteratorlar asosida qo‘shish:
Ro‘yxat bo‘yicha initsializatsiya qilish:
unordered_set va unordered_map sinf obʻyektlarini o‘chirish uchun destruktorlar:
Download 127.31 Kb. Do'stlaringiz bilan baham: |
ma'muriyatiga murojaat qiling