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 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
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 Keyparamert bilan amalsha oshiriladi. Shuningdek, mapva multimaperkin T tipida Key bilan assosiativlanadigandir (sherikdir). Compareobʻ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. setva mapkonteynerlar unikal kalitlarni, multisetva multimapkonteynerlar teng qiymatli kalitlar bilan ishlashga mo‘ljallangan.
setva multisetkonteynerlar uchun aniqlanadigan tip va kalit tipi bir xil bo‘ladi.
mapva multimapkonteynerlar uchun pairKey,T>jufligi bo‘ladi.
Assosiativ konteynerlarning iteratorlari ikki tomonlama iteratorlar sinfiga kiradi. Insert konteyner havolalari va iteratorlarning inkor qilmaydi. Elementlarni o‘chirishda erasefaqat 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.
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
cout << mymap.count('c') << endl;
cout << mymap.find('c')->second << endl; ret = mymap.equal_range('b');
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.