Tiplarni dinamik tarzda



Yüklə 1,83 Mb.
səhifə22/131
tarix16.05.2023
ölçüsü1,83 Mb.
#114156
1   ...   18   19   20   21   22   23   24   25   ...   131
Tiplarni dinamik tarzda

Statik massiv < array>. array iteratorning tasodifiy kirishi orqali elementlarga kirish imkonini beradi va statik array T[N] to‘plami hisoblanadi, kerakli manzili data funksiyasi tomonidan olinishi mumkin. T[N] massivdan farqli ravishda array - qiymatlari ko‘chirilishi (qiymat bo‘yicha funksiyalarga o‘tishi) mumkin bo‘lgan va qiymatlari avtomatik ravishda ko‘rsatgichlarga aylantirilmaydigan to‘la huquqli tipdir. array < T, N> dan tayanch sinf sifatida foydalanish mumkin (lekin ehtiyotkorlik bilan, faqat har qanday konteyner kabi, standart konteynerlar bu maqsad uchun mo‘ljallangan emas, chunki, xususan, virtual funksiyalarni o‘z ichiga olmaydi). deque va vector kabi bir xil tarzda indeksi tomonidan elementlarga murojaat kilish mumkin. Elementlar sonini o‘zgartirish mumkin emas, shuning uchun array elementlarni kiritish yoki o‘chirish uchun hech qanday funksiyalar aniqlanmaydi. fill funksiyasi massivni qiymat nusxalari bilan to‘ldiradi.
2.4-jadval. Ketma-ket konteynerlar uchun asosiy funksiyalar


Headers











Members

array

vector

deque

forward_list

list




constructor

implicit

vector

deque

forward_list

list

destructor

implicit

~vector

~deque

~forward_list

~list

operator=

implicit

operator=

operator=

operator=

operator=

iterators

begin

begin

begin

begin

begin before_begin

begin




end

end

end

end

end

end

rbegin

rbegin

rbegin

rbegin




rbegin

rend

rend

rend

rend




rend


const iterators

cbegin

cbegin

cbegin

cbegin

cbegin cbefore_begin

cbegin

cend

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

max_size

empty

empty

empty

empty

empty

empty

resize




resize

resize

resize

resize

shrink_to_fit




shrink_to_fit

shrink_to_fit







capacity




capacity










reserve




reserve












element access

front

front

front

front

front

front

back

back

back

back




back

operator[]

operator[]

operator[]

operator[]







at

at

at

at







modifiers

assign




assign

assign

assign

assign

emplace




emplace

emplace

emplace_after

emplace

insert




insert

insert

insert_after

insert

erase




erase

erase

erase_after

erase

emplace_back




emplace_back

emplace_back




emplace_back

push_back




push_back

push_back




push_back

pop_back




pop_back

pop_back




pop_back

emplace_front







emplace_front

emplace_front

emplace_front

push_front







push_front

push_front

push_front

pop_front







pop_front

pop_front

pop_front

clear




clear

clear

clear

clear

swap

swap

swap

swap

swap

swap


list operations

splice










splice_after

splice

remove










remove

remove

remove_if










remove_if

remove_if

unique










unique

unique

merge










merge

merge

sort










sort

sort

reverse










reverse

reverse

observers

get_allocator




get_allocator

get_allocator

get_allocator

get_allocator

data

data

data












Nazorat savollari

      1. Kalitlarning qiymati bo‘yicha tartiblangan qanday to‘plamlarni bilasiz?

      2. Bir va ikki baytli belgilar to‘plami nima deb nomlangan va

      3. ularning formatlari bo‘yicha nimalarni bilasiz?

      4. Iteratorlar kanday to‘plam va nima uchun ?

      5. Har bir aniq STL sinfi uchun iteratorlar to‘plamda sinfda kanday aniqlanadi va turlari nechata? Har bir turini tushuntirib bering?

      6. STL kutubxonasi to‘plamlari bilan ishlash imkonini beradigan, mashhur algoritmlarni optimal tatbiqlari va katta majmuini o‘z ichiga oladi. Bu algoritmlar necha guruhga bo‘linadi va qaysilar?

      7. Konteyner sinflar qanday sinf hisoblanadi?

      8. Konteynerlarni nechta turga bo‘lish mumkin va qaysilar?

      9. Har qanday konteynerlarning bo‘lishi shart bo‘lgan xususiyatlarni sanab bering?

      10. Ixtiyoriy konteynerlarda ularning hajmi haqida maʻlumot olish uchun qanday usullari mavjud?

      11. Iteratorda begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() va crend() erkin funksiyalari nimalarini aniqlashi mumkin?

      12. Chiziqli konteynerlarni belgilangan qiymatlardan qaysi funksiyasini chaqirib to‘ldirish mumkin?

      13. Barcha konteynerlarni tenglik va tengsizlik uchun taqqoslash mumkin va ularning mazmunini qanday funksiya yordamida almashtirish mumkin?

      14. Allocator nima uchun ishlatiladi?

      15. Allocator xotirani boshqarishning minimal birligini belgilaydigan va bir qator yordamchi taʻriflarni taqdim etadigan element tipiga bog‘liqdir. Bu vazifa nechta va qanday asosiy funksiyalari yordamida amalga oshiriladi?

      16. Bir aloqali ro‘yxatning nimalarini yaratish uchun A::rebind orqali yaratilgan allokatorday foydalaniladi?

3- MA’RUZA
MAVZU: Assosiativ va tartiblanmagan assosiativ konteynerlar

Reja:


  1. Assosiativ konteynerlar (set, map, multiset, multimap).

  2. Tartiblanmagan assosiativ konteynerlar (unordered_set, unordered_map, unordered_multiset, unordered_multimap).

Konteynerlar va ketma-ket konteynerlar bo‘yicha nazariy va amaliy imkoniyatlarini bilamiz. Shuning uchun konteynerlarning ikkinchi turi bo‘lgan assosiativ konteynerlarni boshqa konteynerlar farqli bo‘lishi kerak. Assosiativ konteynerlari kalit asoisda maʻlumotlarni to‘plamdan tez izlab topish uchun ishlatiladi. Tartiblangan konteynerlar muvozanatlashgan binar daraxt ustiga quriladi va qatʻiy tartibga tayanadi ("kichik" amali [<] operatori asosida hisoblangan). Ikkita element bir biridan kichik bo‘lmasa, ekvivalent hisoblanadi.
Buning kutubxonasi 4 ta asosiy set (to‘plam), multiset (multi to‘plam, ko‘p to‘plam), map (lug‘at) va multimap (mulilug‘at, ko‘p lug‘at) assosiativ konteynerlar bilan ishlashga qaratilgan. Bu konteynerlar Key kalitini o‘zlariga asosiy paramert sifatida oladi va Compare munosabati bo‘yicha tartiblaydi. Tartiblash Key paramert bilan amalsha oshiriladi. Shuningdek, map va multimap erkin T tipida Key bilan assosiativlanadigandir (sherikdir). Compare obʻyektining tipi taqqoslanaligan konteyner obʻyekti (comparison object) deb aytiladi.
Shuning uchun bu konteynerlarning umumiy xususityati va amallaridan boshlaymiz. Barcha assotsiativ konteynerlar quyidagi amallarni qo‘llab- quvvatlaydi:
count – elementlar sonini qaytaradi, belgilangan kalit bo‘yicha elementlar sonini qaytaradi;
find –elementga ko‘rsatkichga mos bo‘lgan iteratorni qaytaradi, agar bunday bo‘lmasa end() funksiyasini vazifasini bajaradi.
equal_range - berilgan intervaldigi barcha elementlar uchun iteratorlar juftligini qaytaradi.
Katitlarning tengli xaqida munosabatlarning ekvivalentligi Kalitlar uchun shartli taqqoslash va (not) operator== tahlil qilamiz.
Key1 va key2 kalitlar o‘zaro teng hisoblanadi, agar taqqoslanadigan obʻyektlar uchun comp chin qiymat qaytarsa, yaʻni:

comp(k1, k2) == false && comp(k2, k1) == false

Assosiativ konteynerlar har qanday kalit qiymat uchun bitta eng katta elementning qiymatini saqlasa, unikal (takrorlanmaydigan) kalitlarni (unique keys) qo‘llab quvvatlaydi. Aks hoda ular teng qiymatli kalitlarni (equal keys) ham qo‘llab quvvatlaydi. set va map konteynerlar unikal kalitlarni, multiset va multimap konteynerlar teng qiymatli kalitlar bilan ishlashga mo‘ljallangan.
set va multiset konteynerlar uchun aniqlanadigan tip va kalit tipi bir xil bo‘ladi.
map va multimap konteynerlar uchun pair Key, T> jufligi bo‘ladi.
Assosiativ konteynerlarning iteratorlari ikki tomonlama iteratorlar sinfiga kiradi. Insert konteyner havolalari va iteratorlarning inkor qilmaydi. Elementlarni o‘chirishda erase faqat iterator va havolalarni inkor qiladi.
3.1-jadvalda assosiativ konteynerlarning talablari keltirilgan (konteynerlarga qo‘shimacha). Unda x bu assosiativ sinf, a – X ning qiymati, Agar X unikal kalitni ko‘llab quvvatlasa, a_uniq – X ning qiymati, Agar X bir nechta kalitni ko‘llab quvvatlasa, a_eq – X ning qiymati, i va j – iteratorning kirish talablarini qanoatlantiruvchi va value_type elementni ko‘rsatadi (beradi), [i, j) - interval, p – a uchun ruxsat berilgan iterator, q – a uchun o‘zgartiriladigan iterator, [q1, q2) - a da ruxsat berilgan interval, t - X::value_type ning qiymati, k - X::key_type ning qiymati.
3.1-jadvalda assosiativ konteynerlarning talablari.



Ifoda

Qaytarila- digan tipi

tasdiq/ oldingi yoki keyingi holatiga izox


murakkabligi


X::key_type


Key

.


Kompilyatsiya vaqti

X::key_compa re


Compare

less joriy holat



Kompilyatsiya vaqti



X::value_comp are

binar predikat turi



xuddi, key_compare uchun set va m
ultiset; munosabati tartiblangan juftlik, map va multimap uchun chaqirilgan birinchi
elementdek (Key)



Kompilyatsiya vaqti


X(c)
X a(c);

.


Bo‘sh konteyner yaratish; taqqoslash obʻyekti sifatida foydalanish uchun.



Doimiy



X()
X a;

.


Bo‘sh konteyner yaratish; taqqoslash obʻyekti sifatida Compare() dan foydalanish uchun


Doimiy


X(i,j,c)
X a(i,j,c);

.


Bo‘sh konteyner yaratish [i, j) intervaldan qiymat qo‘shish; taqqoslash obʻyekti sifatida foydalanish uchun..



NlogN (N - i dan j gacha); chiziqli , agar [i,
j) value_comp() bilan saralangan
bo‘lsa


X(i,j)
X a(i,j);

.

Bo‘sh konteyner yaratish [i, j) intervaldan qiymat qo‘shish; taqqoslash obʻyekti sifatida Compare() dan foydalanish uchun


NlogN (N - i dan j gacha); chiziqli , agar [i,
j) value_comp() bilan saralangan
bo‘lsa


a.key_comp()

X::key_compar e

Taqqoslash obʻyektini qaytaradi


doimiy


a.value_comp(
)


X::value_comp are

Taqqoslash obʻyekti uchun yaratilgan value_compare obʻyektni qaytaradi



doimiy



a_uniq.insert(t)


pair

Agar konteynerda t kalitli element bo‘lmasa, t ni qo‘shish,



logarifmik









juftlikda komponentning bool qiymati qo‘shish bajarilganligini,
iterator t kalitli elementni ko‘rsatadi






a_eq.insert(t)



iterator

t ni qo‘shadi va iteratorni qaytaradi, qo‘shishilgan elementni ko‘rsatadi.



logarifmik

a.insert(p, t)




iterator

t ni qo‘shish, agar faqat va faqat unikal kalitli konteynerda t kalitga teng kalitli element bo‘lmasa; har doim nusxalari bilan konteynerlarga t ni qo‘shish. har doim t kalitli elementni ko‘rsatuvchi iteratorni qaytaradi. p iterator – qo‘shish qaerdan boshlanishini ko‘rsatuvchi izoh



umuman logarifmik, lekin domiyga intiladi,
agar t to‘g‘ri p ni yoniga qo‘yilgan bo‘lsa.

a.insert(i, j)




Natija ishlatilmaydi

[i, j) intervaldan konteynerga elementlarni qo‘shadi;



Umuman, Nlog(size()+N) ( N – i dan j gacha);
chiziqli, agar [i,
j) value_comp() bilan kelishgan holda saralangan












bo‘lsa


a.erase(k)


size_type

konteynerda k kalitga teng bo‘lgan barcha e lementlarni o‘chiradi. o‘chirilgan elementlarning sonini qaytaradi.

log(size()) + count(k)




a.erase(q)

Natijasi ishlatilmay-di

q bilan ko‘rsatilgan elementni o‘chiradi

domiyga intiladi



a.erase(ql, q2)




Natijasi ishlatilmay-di

[ql, q2) intervaldagi barcha elementlarni cho‘chiradi.



log(size())+
N, N - ql dan q2 gacha.


a.find(k)

iterator; const_iterator
– a uchun o‘zgarmas

k kalitli elementni ko‘rsatuvchi iterator yoki agar bunday element topilmasa a.end() qaytaradi


logarifmik


a.count(k)


size_type

k kalitli elementlar sonini qaytaradi.

log(size()) + count(k)



a.lower_bound (k)

iterator; const_iterator a uchun o‘zgarmas

k kalitli elementdan kichik bo‘lmagan birinchi elementni ko‘rsatuvchi iteratorni qaytaradi


logarifmik



a.upper_bound (k)

iterator; const_iterator a uchun o‘zgarmas

k kalitli elementdan katta bo‘lgan birinchi elementni ko‘rsatuvchi iteratorni qaytaradi


logarifmik

a.equal_range(

pair

make_pair(lower_boud(k),

logarifmik



k)

iterator>; pair a uchun o‘zgarmas

upper_bound (k)) ga ekvivalent




Assotsiativ konteyner iteratorlarining asosiy xususiyati shundaki, ular konteynerlar orqali o‘sish tartibidagi kalitlar tartibida iteratsiyalanadi, bu yerda o‘sish tartibi ularni yaratish uchun ishlatilgan taqqoslash bilan belgilanadi.
Ikkiia ixtiyoriy o‘zguruvchan I va j iteratorlar uchun I dan j gacha masofa musbat bo‘ladi, yaʻni value_comp (*j, *i) == false. Unikal kalitli assotsiativ konteynerlar uchun kuchliroq value_comp (*i, *j) == true holat saqlanib turibdi.
Barcha tartiblangan konteynerlar ikki tomonlama iteratorlar yordamida elementlarga murojaat qilish imkonini beradi. Kalit asosida qidirishda berilgan kichik bo‘lmagan birinchi elementni lower_bound() funksiyasi va birinchi katta elementni upper_bound() funksiyasi yordamida amalga oshiriladi (3.1-jadvalga qarang). Agar mymap konteyner berilgan bo‘lsa, unda mymap.equal_range(key) funksiyasi bilan ekvivalnt bo‘ladi (3.1-dasturga qarang).
3.1-dastur. Tartiblangan konteynerlar funksiyalari.


// created by Mbbahodir #include "stdafx.h"

#include #include


using namespace std; int main ()


{
map mymap; map::iterator itlow,itup;
pair::iterator,map::iterator> ret, make_ret;

mymap ['a']=101; mymap ['c']=303; mymap ['f']=404; mymap ['b']=202;





cout << mymap.count('c') << endl;

cout << mymap.find('c')->second << endl; ret = mymap.equal_range('b');


char key = 'b';
make_ret = make_pair(mymap.lower_bound(key),mymap.upper_bound(key));

cout << "Kichik boʻlmagam element: ";


cout << ret.first->first << " => " << ret.first->second << '\t';
cout << make_ret.first->first << " => " << make_ret.first->second << '\t'; itlow = mymap.lower_bound ('b');
cout << itlow->first << " => " << itlow->second << endl;

cout << "katta boʻlgan birinchi element: ";


cout << ret.second->first << " => " << ret.second->second << '\t';
cout << make_ret.second->first << " => " << make_ret.second->second << '\t'; itup = mymap.upper_bound ('b');
cout << itup->first << " => " << itup->second << endl;

system("pause"); return 0;
}




3.1-dastur. Output

1
303
Kichik boʻlmagam element: b => 202 b => 202 b => 202 katta boʻlgan birinchi element: c => 303 c => 303 c => 303

3.1-dastur tahlili. Dasturda 4 ta elementdan iborat map konteyner berilgan. ʻsʻ kalitli element soni count() funksiya bilan aniqlagan. Xuddi shu kalit bilan uning qiymati find() funksiya bilan topilgan. equal_range('b'), mymap.lower_bound('b'); mymap.upper_bound('b'); make_pair( mymap.lower_bound(key), mymap.upper_bound(key)); funksiyalarining ekvivalet ishlari ko‘rsatilgan.



Yüklə 1,83 Mb.

Dostları ilə paylaş:
1   ...   18   19   20   21   22   23   24   25   ...   131




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin