Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja

(*((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();