|
Tiplarni dinamik tarzda
|
| bet | 22/131 | | Sana | 13.05.2024 | | Hajmi | 1,83 Mb. | | #228405 |
Bog'liq Tiplarni dinamik tarzdaStatik 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
Kalitlarning qiymati bo‘yicha tartiblangan qanday to‘plamlarni bilasiz?
Bir va ikki baytli belgilar to‘plami nima deb nomlangan va
ularning formatlari bo‘yicha nimalarni bilasiz?
Iteratorlar kanday to‘plam va nima uchun ?
Har bir aniq STL sinfi uchun iteratorlar to‘plamda sinfda kanday aniqlanadi va turlari nechata? Har bir turini tushuntirib bering?
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?
Konteyner sinflar qanday sinf hisoblanadi?
Konteynerlarni nechta turga bo‘lish mumkin va qaysilar?
Har qanday konteynerlarning bo‘lishi shart bo‘lgan xususiyatlarni sanab bering?
Ixtiyoriy konteynerlarda ularning hajmi haqida maʻlumot olish uchun qanday usullari mavjud?
Iteratorda begin(), end(), cbegin(), cend(), rbegin(), rend(), crbegin() va crend() erkin funksiyalari nimalarini aniqlashi mumkin?
Chiziqli konteynerlarni belgilangan qiymatlardan qaysi funksiyasini chaqirib to‘ldirish mumkin?
Barcha konteynerlarni tenglik va tengsizlik uchun taqqoslash mumkin va ularning mazmunini qanday funksiya yordamida almashtirish mumkin?
Allocator nima uchun ishlatiladi?
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?
Bir aloqali ro‘yxatning nimalarini yaratish uchun A::rebind orqali yaratilgan allokatorday foydalaniladi?
3- MA’RUZA
MAVZU: Assosiativ va tartiblanmagan assosiativ konteynerlar
Reja:
Assosiativ konteynerlar (set, map, multiset, multimap).
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.
|
| |
