Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja


Download 127.31 Kb.
bet7/8
Sana14.04.2023
Hajmi127.31 Kb.
#1357822
1   2   3   4   5   6   7   8
Bog'liq
tl4Z0UMKrTZbC9NdE9w9eYsMfgJB5joUuJ9400gY

(*((m.insert(make_pair(k, T()))).first)).second

Assotsiativ konteynerlar asosiy xususiyatlari

Headers





Members

set

multiset

map

multimap




constructor

set

multiset

map

multimap

destructor

~set

~multiset

~map

~multimap

assignment

operator=

operator=

operator=

operator=

iterators

begin

begin

begin

begin

begin

end

end

end

end

end

rbegin

rbegin

rbegin

rbegin

rbegin

rend

rend

rend

rend

rend

const iterators

cbegin

cbegin

cbegin

cbegin

cbegin

cend

cend

cend

cend

cend

crbegin

crbegin

crbegin

crbegin

crbegin

crend

crend

crend

crend

crend

capacity


size

size

size

size

size

max_size

max_size

max_size

max_size

max_size

empty

empty

empty

empty




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.

using Entry = pair;

Lug‘at tipini aniqlash

using Dictionary = multimap;

Standart kirish va chiqish operatorlari quyidagicha aniqlaymiz.

namespace std
{
istream& operator>>(istream &is, Entry &en)
{
return is >> en.first >> en.second;
}
ostream& operator<<(ostream &os, const Entry &en)
{
return os << en.first << ' ' << en.second;
}
istream& operator>>(istream &is, Dictionary &d)
{
istream_iterator begin(is), end; d = Dictionary(begin, end); return is;
}
ostream& operator<<(ostream &os, const Dictionary &d)
{
ostream_iterator out(os, "\n"); copy(d.begin(), d.end(), out); return os;
}
}

Lug‘atga kirish uchun amal. Belgilangan lug‘at uchun yangi lug‘at chiqaradi.



Dictionary reverse(const Dictionary &d)
{

Dictionary result;
for (const auto &el : d) result.emplace(el.second, el.first); return result;
}

Lug‘at elementiga murojaat va o‘qish.

void dictionary_reverse(istream &from, ostream &to)
{
Dictionary read; from >> read; to << reverse(read);
}

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:



friend class multimap;
protected:
Compare comp; value_compare(Compare c) : comp(c) {}
public:
bool operator()(const value_type& x, const value_type& y) { return comp(x.first, y.first);
}
};

Mantiqiy operatorlari:



template
bool operator==(const multimap& x, const multimap& y);

template bool operator<(const multimap& x,


const multimap& y);

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.


Tartiblanmagan

assosiativ

konteynerlar

va

.




Tartiblanmagan

konteynerlar



, xesh – jadval asosida qurilgan (odatda bu xesh jadvallar ekvivalent elementlar ro‘yxati - bloklar) va xesh funksiyalarga (joriy holatida standart tiplar uchun
sinfidan std::hash bilan aniqlanadi) va tenglik amaliga (joriy holatda [==] operatori) tayanadi.
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:



unordered_set, E = equal_to, A = allocator>, unordered_map, E = equal_to, A = allocator
>>, unordered_multiset, unordered_multimap.

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:

#include

unordered_map va unordered_multimap sinflari ham xuddi yuqoridagidek qo‘shiladi:


#include

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 ar; unordered_set ar; unordered_map ar; unordered_map ar;

Agar hash xesh funksiya yozilmagan bo‘lsa, joriy holat bo‘yicha hash funksiyasi ishlatiladi.


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:


unordered_set ar(other); unordered_map ar(other);

Iteratorlar asosida qo‘shish:

unordered_set ar(first, last); unordered_set ar(first, last); unordered_map ar(first, last);
unordered_map ar(first, last);

Ro‘yxat bo‘yicha initsializatsiya qilish:



unordered_set ar {init}; unordered_set ar(init); unordered_set ar(init); unordered_map ar {init}; unordered_map ar(init);
unordered_map ar(init);

unordered_set va unordered_map sinf obʻyektlarini o‘chirish uchun destruktorlar:



ar.~unordered_set(); ar.~unordered_map();

Download 127.31 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling