Mavzu: assosiativ va tartiblanmagan assosiativ konteynerlar reja

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).
va doir masalalr va dasturlarni keltiramiz.

1. 
   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 #include #include #include #include using namespace std;
int main() {

default_random_engine rnd(time(0)); uniform_int_distribution g(10, 50); vector myVektor;

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 mySet;

for (int i=1; i<=5; ++i) mySet.insert(i*10); cout << endl;

3.3(a)-dastur. Output

n = 255 47 50 18 29 44 47 31 31 25 19 40 32 43 29 38 22 10 39 47 10 43 46 26 47 18 50 30 24 34 47 31 13 35 41 29 26 25 26 19 46 18 17 23 32 18 47 37 14 13 13 32 28 14 42 41 29 21 19 23 38 12 31 26 48 34 44 20 21 34 13 43 42 30 26 44 10 34 22 15 26 23 26 30 22 44 41 44 12 36 33 29 37 20 17 10 28 33 26 19 12 50 31 49 33 50 41 32 42 38 35 27 23 18 25 28 31 12 36 18 42 36 44 24 37 10 34 49 26 29 11 39 33 31 15 11 42 37 40 49 34 41 20 50 39 19 29 30 24 38 47 14 41 37 21 49 21 42 14 37 45 12 40 17 46 17 10 45 43 37 19 25 39 11 49 33 17 11 12 10 22 19 26 12 47 34 16 21 33 25 44 26 40 28 38 35 15 31 26 10 32 40 42 45 32 17 20 41 30 36 13 23 24 44 19 23 29 21 38 30 26 20 23 33 31 39 20 22 50 34 18 24 21 30 21 42 13 22 41 19 35 40 14 34 37 16 14 35 17 44 40 13 37 28 45 24 34 ta element topildi.

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.

// Created by MBBahodir #include "stdafx.h" #include #include #include #include #include #include #include using namespace std; int main() { int n; default_random_engine rnd(time(0)); uniform_int_distribution g(1, 10000); cout << "n = "; cin >> n; const int k = 100; int a = n;

auto start = chrono::system_clock::now(); vector ar1; while (a--) ar1.push_back(g(rnd)); auto result1 = find(ar1.begin(), ar1.end(), k); auto end = chrono::system_clock::now(); auto elapsed = end - start; cout << "vector => " << elapsed.count() << endl; a = n; start = chrono::system_clock::now(); set ar2; while (a--) ar2.insert(g(rnd)); auto result2 = ar2.find(k); end = chrono::system_clock::now(); elapsed = end - start; cout << "set => " << elapsed.count() << endl; system("pause"); return 0; }

3.3(b)-dastur. Output

n = 10000 vector => 289989 set => 1160000

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 foydasiga o‘zgaradi:

3.3(c)-dastur. Output

n = 10000 vector => 70042 set => 20044

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:

pair p1; pair p2(val1, val2); pair p3(p1);

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.

// Created by MBBahodir #include "stdafx.h" #include using namespace std; int main() { int a1 = 16, b1 = 11; int a2 = 18, b2 = 03; pair par1(a1, b1); pair *par2 = new pair(a2, b2); cout << par1.first << '.' << par1.second << endl; cout << par2->first << '.' << par2->second << endl; system("pause"); return 0; }

3.4-dastur. Output

16.11 18.3

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):

#include

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 ar; yoki map ar(Comp);
Nusxalash uchun konstruktor: map ar(other);
Iteratorlar yordamida qo‘shish uchun konstruktorlar: map ar(first, last); yoki map ar(first, last, Somp);
Ro‘yxat asosida initsializatsiya qilish konstruktorlari: map ar {init}; yoki map ar(init); yoki map ar(init, Comp); Eslatma. Ro‘yxatni initsializatsiya qilishda har bir juftlik alohida figurali qavs ichiga olinishi kerak!

map ar {{"a1", 10}, {"www", 17}, {"j8", 100}};

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.

// Created by MBBahodir #include "stdafx.h" #include #include #include #include #include

rat.insert(pair("d3", -15)); rat.insert(pair("d3", 6)); //=============================3==============================// // birinchi va ikkinchi kalit orasidagi elementlarni chiqarish// //============================================================// string el_l, el_r; cout << "kalitlarni kirit:\n"; cout << "1-kalit: "; cin >> el_l; cout << "2-kalit: "; cin >> el_r; auto fst = rat.lower_bound(el_l); auto lst = rat.upper_bound(el_r); while (fst != lst) { cout << fst -> first << " => " << fst -> second << endl; fst++; } //==============================4==============================// // kalitga mos eng katta elementni aniqlash // //=============================================================// string tmp; cout << "Kalit kirit: "; cin >> tmp; auto first = rat.equal_range(tmp).first; auto last = rat.equal_range(tmp).second; if (first == last) cout << 0 << endl; else while (first != last) { auto r = first -> second; if (r >= 10) cout << r << " "; first++; } system("pause"); return 0; }

3.5-dastur. Birinchi sinov Output

Lugʻat elementlari sonini kirit: 10

a2 => 14 a3 => 13 b2 => -8 b3 => 3 c2 => -4 c3 => -7 d1 => 10 d3 => -15 kalitlarni kirit: 1-kalit: a1 2-kalit: c2 a2 => 14 a3 => 13 b2 => -8 b3 => 3 c2 => -4 Kalit kirit: c4 0

3.5-dastur. Ikkinchi sinov Output

Lugʻat elementlari sonini kirit: 9 a1 => 11 a2 => 10 b1 => 2 b2 => -10 c1 => 3 c2 => 9 d1 => 10 d3 => -15 kalitlarni kirit: 1-kalit: a1

2-kalit: c2 a1 => 11 a2 => 10 b1 => 2 b2 => -10 c1 => 3 c2 => 9 Kalit kirit: d3

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:

map rat; try { rat.at("U"); } // istesnoni ushlab olish catch (std::out_of_range) { // uni qayta ishlash

rat["U"] = 15; }

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:

rat["b1"]=1980; cout << rat["b1"] << endl; rat["b1"] +=1; cout << rat["b1"] << endl; --rat["b1"]; cout << rat["b1"] << endl;

map, A = allocator
>> to‘plam pair tipidagi qiymatni saqlaydi. Bunda K kalit, tanlash imkonini beradi va T saqlanadigan qiymat. Shuning uchun iteratordan foydalangannimizda first kalit qiymatni va second saqlangan qiymatni qaytaradi, o‘zgartirish imkonini beradi. Yuqorida aytib o‘tilgandek operator[] asosiy amallardan hisoblanadi (vazifasini bilsangiz kerak). Agar map m bo‘lsa va m[k] = t maʻno jihatidan quyidagi fragmentga teng:

m.insert(make_pair(k, T())).first->second = t

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:

template , template class Allocator = allocator>

Map sinfining operatorlari, xususiyatlari, funksiyalari va usullarini qo‘rib chiqamiz.

Typedef operatorlari :

typedef Key key_type; typedef pair value_type; typedef Compare key_compare; class value_compare : public binary_function { friend class map; 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); } }; typedef iterator; typedef const_iterator; typedef Allocator::pointer pointer; typedef Allocator::reference reference; typedef Allocator::const_reference const_reference; typedef size_type; typedef difference_type; typedef reverse_iterator; typedef const_reverse_iterator;

Xotirani ajratish va bo‘shatish (xolli qilish) operatorlari (allocation/deallocation):

map(const Compare& comp = Compare()); template

map(InputIterator first, InputIterator last, const Compare& comp = Compare()); map(const map& x); ~map(); map& operator=(const map& x); void swap(map& x);

Ruxsat etish vositalari (accessors):

key_compare key_comp() const; value_compare value_comp() const; iterator begin() const_iterator begin() const; iterator end(); const_iterator end() const; reverse_iterator rbegin(); const_reverse_iterator rbegin(); reverse_iterator rend(); const_reverse_iterator rend(); bool empty() const; size_type size() const; size_type max_size() const; Allocator::reference operator[](const key_type& x);

Qo‘shish va o‘chirish funksiyalar (insert/erase):

pair insert(const value_type& x); iterator insert(iterator position, const value_type& x); template void insert(InputIterator first, InputIterator last); void erase(iterator position); size_type erase(const key_type& x);

void erase(iterator first, iterator last);

Map sinf usulari:

iterator find(const key_type& x); const_iterator find(const key_type& x) const; size_type count(const key_type& x) const; iterator lower_bound(const key_type& x); const_iterator lower_bound(const key_type& x) const; iterator upper_bound(const key_type& x); const_iterator upper_bound(const key_type& x) const; pair equal_range(const key_type& x); pair equal_range(const key_type& x)const;

Mantiqiy operatorlari:

template bool operator==(const map& x, const map& y); template bool operator<(const mapr T, Compare, Allocator>& x, const map& 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.

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: