|
Assotsiativ konteynerlar tezkor qidiruv qobiliyatiga EGA bo'lgan buyurtma qilingan ma'lumotlar tuzilishini (O (log n) murakkabligi bilan) amalga oshiradi. Assotsiativ konteynerlar
|
| bet | 6/8 | | Sana | 17.05.2024 | | Hajmi | 2,16 Mb. | | #239109 |
Bog'liq Assotsiativ konteynerlar haqida; set va multiset sinflari; map v#include
#include
using namespace System;
using namespace std;
int main()
{ srand(time(NULL));
set s; int n;
cout<<"Elementlar sonini: "; cin>>n;
multiset M, M2;
for (int i = 0; i < n; i++)
{ int j = rand()%n+n; M.insert(j);
j = rand()%n+n; M2.insert(j);
}
auto k2 = M.begin();
set s2;
for (int i = 0; i < n; i++)
{
s2.insert(*k2); k2++;
}
cout<
for (auto i=M.begin(); i!=M.end(); i++)
{
cout<<*i<<" ";
}
cout<
cout<
for (auto i=M2.begin(); i!=M2.end(); i++)
{
cout<<*i<<" ";
}
cout<
int soni=0;
for (auto i=s2.begin(); i!=s2.end(); i++)
{
for (auto j=M2.begin(); j!=M2.end(); j++)
{
if(M2.count(*i)){
if(*i==*j) {soni++; }
}
}
if(soni>0)cout<<*i<<" -"<
else {cout<<*i<<" - qatnashmagan "<
soni = 0;
}
//cout<
auto k = M.begin();
auto l = M2.begin();
for (int i = 0; i < n; i++)
{
s.insert(*k);k++;
s.insert(*l); l++;
}
cout<
cout<
for (auto i=s.begin(); i!=s.end(); i++)
{
cout<<*i<<" ";
}
getchar(); getchar();
return 0;
}
Dastur natijasi:
Elementlar sonini: 25
M to'plam elementlari:
25 27 27 27 27 28 29 30 31 31 31 32 33 33 35 35 37 37 40 42 42 43 43 47 48
M2 to'plam elementlari:
26 27 30 31 31 31 31 34 35 37 38 39 42 43 45 45 45 46 46 46 46 47 47 49 49
M1 ning elementlari M2 to'plamda qatnashganlari soni:
25 - qatnashmagan
27 -1 marta
28 - qatnashmagan
29 - qatnashmagan
30 -1 marta
31 -4 marta
32 - qatnashmagan
33 - qatnashmagan
35 -1 marta
37 -1 marta
40 - qatnashmagan
42 -1 marta
43 -1 marta
47 -2 marta
48 - qatnashmagan
Saralangan to'plam elementlari:
25 26 27 28 29 30 31 32 33 34 35 37 38 39 40 42 43 45 46 47 48 49
|
map sinfi
map va multimap - konteyner sinf shablonlarini va ularning yordamchi shablonlarini belgilaydi.
<map> kutubxonasi, shuningdek #include direktivasidan foydalanadi.
map va multimap uchun quyidagi operatorlar qayta yuklangan:
map sinfi uchun qayta yuklanga operatorlar
map sinfi:
Har bir element ma'lumotlar qiymati va saralash kalitiga ega bo'lgan to'plamdan ma'lumotlarni saqlash va olish uchun ishlatiladi. Kalit qiymati noyobdir va ma'lumotlarni avtomatik saralash uchun ishlatiladi.
map da elementning qiymati to'g'ridan-to'g'ri o'zgartirilishi mumkin. Kalit qiymati doimiy bo'lib, uni o'zgartirib bo'lmaydi. Buning o'rniga eski elementlar bilan bog'liq bo'lgan kalit qiymatlarni o’chirish va yangi elementlarga yangi kalit qiymatlarini kiritish kerak.
map sinfining sintaksisi:
template
class Type,
class Traits = less,
class Allocator=allocator
>> class map;
map sinfining turlari va funksiyalari
map sinfining turlari va funksiyalari set sinfiniki bilan bir xil faqat ulardan foydalanish usullarida farq qilinishi mumkin.
value_type turi va at(), insert() funksiyalari:
const_iterator turi va erase () funksiysi:
typedef pair turi va begin() funksiysi:
typedef pair turi va count() funksiysi:
difference_type turi:
Iteratorlar tomonidan ko'rsatilgan elementlar orasidagi diapazonda map ning elementlar sonini ifodalash uchun ishlatilishi mumkin bo'lgan imzolangan butun son.
farq_type - bu konteyner iteratorlari yordamida kamaytirish yoki ko'paytirish orqali qaytariladigan tur. differ_type odatda birinchi va oxirgi iteratorlar orasidagi [firs, last] oralig'idagi elementlar sonini ifodalash uchun ishlatiladi.
map va multimap sinflaridan foydalanib, amaliy dasturlar yaratish
Ishning maqsadi: C++ dasturlash tilida map va mulmap sinflari va uning metodlaridan foydalanish ko’nikmalarini egallsh.
Masalaning qo’yilishi:
map va multimap asosida yaratilgan to’plam elementlarini map va mutimap ning maxsus funksiyalari yordamida qayta ishlash.
Masala:
Talabalarning haqida (familiya, ismi va stipendiyasi) string va float turidagi to’plam berilgan. Familiyasi yoki ismi to’liq yozilganlar va stipendiyasi N ga teng bo’lganlaridan 2- to’plamni hosil qiluvchi va ularni ekranga chiqaruvchi dastur tuzing.
Masalani yechish g‘oyasi:
map konteyneri to’plami yaratiladi. map ning insert(pair('a',10)) iteratoridan foydalanib, A to’plamga qiymatlar o’zlashtiriladi.
Dastur matni:
#include "stdafx.h"
#include
#include
#include
using namespace System;
using namespace std;
int main()
{ map s; int n;
cout<<"Talabalar sonini kiriting: "; cin>>n; cin.ignore();
multimap M, M2;
for (int i = 0; i < n; i++)
{ string St;
int step;
cout<
cout<<"Fam, ismi: "; getline(cin,St);
cout<<"Stipendiyasi: "; cin>>step; cin.ignore();
s.insert(pair(St,step));
M.insert(pair(St,step));
}
string S;
int N;
cout<<"Qanday stipendiya oladigan talaba haqida ma'lumot kerak?: ";
cin>>N;
int k=0;
for (auto it = M.begin(); it != M.end(); ++it){
S = it->first;
if(S.find(" ")second == N){
M2.insert(pair(S,N)); cout<<"bor"<
}
cout<<"So'rov Natijasi:"<
for (auto it = M2.begin(); it != M2.end(); ++it){
cout<first<<" "<second<
}
getchar(); getchar();
return 0;}
Dastur natijasi:
Talabalar sonini kiriting: 3
1 - talaba ma'lumotlarini kiriting:
Fam, ismi: Mallayev Oybek
Stipendiyasi: 400000
2 - talaba ma'lumotlarini kiriting:
Fam, ismi: Ishniyazov Odil
Stipendiyasi: 500000
3 - talaba ma'lumotlarini kiriting:
Fam, ismi: ABdurahmonov
Stipendiyasi: 300000
Qanday stipendiya oladigan talaba haqida ma'lumot kerak?: 400000
bor
So'rov Natijasi:
Mallayev Oybek 400000
|
4. Tartiblanmagan assotsiativ konteynerlar
Tartibga solinmagan assotsiativ konteynerlar tezda qidirish qobiliyatiga ega (buzilgan) ma'lumotlar tuzilmalarini (o'rtacha murakkabligi O (1), eng yomon holatda O (n)) tashkil etadi.
unordered_set (C++11) - Noyob kalitlar, xash-kalitlar to'plami.
unordered_map(C++11) - Kalit-qiymat juftlari to'plami, to'ldirilgan kalitlar, kalitlar noyobdir.
unordered_multiset(C++11) - Kalitlar to'plami, hash-kalitlar.
unordered_multimap(C++11) -
unordered_set sinfi:
template< class Key, class Hash = std::hash,
class KeyEqual = std::equal_to,
class Allocator = std::allocator> class unordered_set;
Tartiblanmagan to'plam bu ko'p turdagi noyob obyektlarni o'z ichiga olgan assotsiativ konteynerdir. Qidiruv, qo'shish va o'chirish o'rtacha doimiy vaqt murakkabligiga ega.
unordered_set iteratorlari:
Nomi
|
Izoh
| |
|
begin, cbegin
|
Birinchi elementga iteratorni qaytaradi.
|
end, cend
|
Iteratorni oxirgi elementga qaytaradi.
|
empty
|
Konteynerni bo’shlikka tekshirish.
|
size
|
Konteynerning elementlar sonini qaytaradi.
|
max_size
|
Konteynerning ruxsat etilgan elementlarning maksimal sonini qaytaradi.
|
unordered_set ning funksiya – a’zolari:
Nomi
|
Izoh
| |
|
at
|
Ko'rsatilgan elementga indeks tekshiruvi bilan kirishni ta'minlaydi
|
operator[]
|
Belgilangan elementga kirishni ta'minlaydi
|
front
|
Birinchi elementga kirishni ta'minlaydi
|
back
|
oxirgi elementga kirishni ta'minlaydi
|
data (C++11)
|
Massivning birinchi haqiqiy elementiga ko'rsatgichni qaytaradi
|
unordered_set ning funksiya – a’zolari
Nomi
|
Izoh
| |
|
get_allocator
|
Bog'langan ajratuvchini qaytaradi.
|
operator=
|
Konteynerdagi qiymatlarni o'rnatadi
|
unordered_set ning modifikatorlari:
Nomi
|
Izoh
| |
|
clear
|
Konteynerni tozalaydi.
|
insert
|
Konteynerga element qo’shadi.
|
emplace
|
Elementlarni "joyida" quradi va berilgan pozitsiyadan boshlab ularni joylashtiradi.
|
emplace_hint
|
Foydalanish joyidagi struktura elementlari.
|
erase
|
Konteynerdan element ochirish.
|
swap
|
Tarkibni almashtirish.
|
count
|
Muayyan kalitga mos keladigan elementlar sonini qaytaradi.
|
find
|
Ma'lum bir kalitga ega bo'lgan elementni topadi.
|
equal_range
|
Ma'lum bir kalit uchun elementlar to'plamini qaytaradi.
|
bucket_count
|
Buketlar sonini qaytaradi.
|
|
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
Assotsiativ konteynerlar tezkor qidiruv qobiliyatiga EGA bo'lgan buyurtma qilingan ma'lumotlar tuzilishini (O (log n) murakkabligi bilan) amalga oshiradi. Assotsiativ konteynerlar
|
