Mavzu: Assotsiativ konteynerlar Hisoblashda assotsiativ konteynerlar

Ishlash [ tahrirlash ]
Shuningdek qarang: Big O notation va Time murakkabligi
Assotsiativ konteynerlarga qo'llanilishi mumkin bo'lgan operatsiyalarning asimptotik murakkabligi quyidagicha:

Operatsiya	Murakkablik
Element qidirilmoqda	O(log n)
Yangi element kiritish	O(log n)
Iteratorni oshirish/kamaytirish	O(log n) (agar faqat o'sish yoki kamayish amalga oshirilsa, amortizatsiya qilingan O(1))
Bitta elementni olib tashlash	O(log n)

Funksiyalarning umumiy ko'rinishi [ tahrir ]
Konteynerlar konteyner nomlari bilan nomlangan sarlavhalarda aniqlanadi, masalan , to'plam sarlavhasida aniqlanadi . Barcha konteynerlar konteyner talablariga javob beradi tushunchasi , ya'ni ular begin() , end() , size() , max_size() , empty() va swap() usullariga ega.

	o'rnatish	xarita	multiset	multimap	Tavsif
	(konstruktor)	(konstruktor)	(konstruktor)	(konstruktor)	Har xil manbalardan konteyner yasaydi
	(destruktor)	(destruktor)	(destruktor)	(destruktor)	To'plam va uning tarkibidagi elementlarni yo'q qiladi
	operator =	operator =	operator =	operator =	Konteynerga qiymatlarni tayinlaydi
	get_allocator	get_allocator	get_allocator	get_allocator	Elementlar uchun xotira ajratish uchun ishlatiladigan ajratgichni qaytaradi
Elementga kirish	Yoʻq	da	Yoʻq	Yoʻq	Belgilangan elementga chegaralarni tekshirish orqali kiradi.
	Yoʻq	operator[]	Yoʻq	Yoʻq	Belgilangan elementga cheklovsiz kirish.
Iteratorlar	boshlanishi	boshlanishi	boshlanishi	boshlanishi	Iteratorni konteyner boshiga qaytaradi
	oxiri	oxiri	oxiri	oxiri	Iteratorni konteyner oxiriga qaytaradi
	rboshlang	rboshlang	rboshlang	rboshlang	Konteynerning teskari boshiga teskari iteratorni qaytaradi
	parchalash	parchalash	parchalash	parchalash	Konteynerning teskari uchiga teskari iteratorni qaytaradi
Imkoniyat	bo'sh	bo'sh	bo'sh	bo'sh	Idish bo'sh yoki yo'qligini tekshiradi
	hajmi	hajmi	hajmi	hajmi	Konteynerdagi elementlar sonini qaytaradi.
	maksimal_oʻlcham	maksimal_oʻlcham	maksimal_oʻlcham	maksimal_oʻlcham	Konteynerdagi elementlarning mumkin bo'lgan maksimal sonini qaytaradi
Modifikatorlar	aniq	aniq	aniq	aniq	Tarkibni tozalaydi.
	kiritmoq	kiritmoq	kiritmoq	kiritmoq	Elementlarni kiritadi.
	joylashtirmoq	joylashtirmoq	joylashtirmoq	joylashtirmoq	Elementlarni joyida quradi ( C++ 11 )
	emplace_shint	emplace_shint	emplace_shint	emplace_shint	Maslahat yordamida elementlarni joyida quradi ( C++ 11 )
	o'chirish	o'chirish	o'chirish	o'chirish	Elementlarni o'chiradi.
	almashtirish	almashtirish	almashtirish	almashtirish	Tarkibni boshqa idish bilan almashtiradi.
Axtarish, izlash	hisoblash	hisoblash	hisoblash	hisoblash	Muayyan kalitga mos keladigan elementlar sonini qaytaradi.
	toping	toping	toping	toping	Muayyan kalitga ega elementni topadi.
	teng_oraliq	teng_oraliq	teng_oraliq	teng_oraliq	Muayyan kalitga mos keladigan elementlar qatorini qaytaradi.
	pastki_chegara	pastki_chegara	pastki_chegara	pastki_chegara	Berilgan qiymatdan kam bo'lmagan kalit bilan iteratorni birinchi elementga qaytaradi.
	yuqori_chegara	yuqori_chegara	yuqori_chegara	yuqori_chegara	Muayyan qiymatdan kattaroq kalitga ega bo'lgan birinchi elementga iteratorni qaytaradi.
Kuzatuvchilar	key_comp	key_comp	key_comp	key_comp	Kalit taqqoslash funksiyasini qaytaradi.
	qiymat_komp	qiymat_komp	qiymat_komp	qiymat_komp	Qiymatni taqqoslash funksiyasini qaytaradi. Set va multisetda bu funksiya key_comp ga ekvivalentdir , chunki elementlar faqat kalitdan tuzilgan.

Foydalanish [ tahrirlash ]
Quyidagi kod so'zlarning takrorlanishini hisoblash uchun map dan qanday foydalanishni ko'rsatadi. U kalit sifatida so'zni va qiymat sifatida hisobni ishlatadi.
#o'z ichiga oladi
#o'z ichiga oladi
#o'z ichiga oladi

int asosiy ()

{
std :: map < std :: string, int > so'zlar soni;
std :: string s;


esa (std :: cin >> s && s != "oxiri" )
++ so'zlar soni [lar];


esa (std :: cin >> s && s != "oxiri" )
std :: cout << s << '' << so'zlar soni << '\n' ;
}
Bajarilayotganda foydalanuvchi avval boʻshliqlar bilan ajratilgan qator soʻzlarni va kiritish yakunini bildiruvchi “end” soʻzini teradi; keyin foydalanuvchi har bir so'z oldingi qatorda necha marta sodir bo'lganligini so'rash uchun so'zlarni kiritishi mumkin.
Yuqoridagi misol, agar kalit bilan bog'liq bo'lmasa, [] operatori xaritaga yangi ob'ektlarni (standart konstruktor yordamida) kiritishini ham ko'rsatadi. Shunday qilib, integral tiplar noldan boshlanadi, satrlar bo'sh satrlarga ishga tushiriladi va hokazo.
Quyidagi misolda insert funksiyasidan foydalangan holda xaritaga elementlarni kiritish va xarita iteratori va find funksiyasidan foydalanib kalitni qidirish tasvirlangan:
#o'z ichiga oladi
#o'z ichiga oladi
#o'z ichiga oladi // make_pair

int asosiy ()

{
typedef std :: map < char , int > MapType;
MapType mening_xarita;


// insert funksiyasidan foydalanib elementlarni kiritish
my_map.insert(std :: pair < char , int > ( 'a' , 1 ));
my_map.insert(std :: pair < char , int > ( 'b' , 2 ));
my_map.insert(std :: pair < char , int > ( 'c' , 3 ));
my_map.insert(MapType :: value_type( 'd' , 4 )); // barcha standart konteynerlar ushbu typedefni ta'minlaydi
my_map.insert(std :: make_pair( 'e' , 5 )); // make_pair yordamchi funksiyasidan ham foydalanishi mumkin
my_map.insert({ 'f' , 6 }); // C++ 11 boshlang'ich ro'yxati yordamida
//xarita tugmalari avtomatik ravishda pastdan yuqoriga saralanadi.
//Shunday qilib, my_map.begin() birinchi kiritilgan kalit emas, balki eng past kalit qiymatiga ishora qiladi.
MapType :: iterator iter = my_map.begin();


// o'chirish funktsiyasidan foydalangan holda birinchi elementni o'chirish
my_map.erase(iter);


// xarita hajmini chiqarish
std :: cout << "Mening_xaritamning o'lchami:" << my_map.size() << '\n' ;

std :: cout << "Qidirish uchun kalitni kiriting: " ;

char c;
std :: cin >> c;


// find, agar topilsa, mos keladigan elementga iteratorni qaytaradi
// yoki kalit topilmasa, xaritaning oxirigacha
iter = my_map.find(c);
agar (iter != my_map.end() )
std :: cout << "Qiymat:" << iter -> soniya << '\n' ;
boshqa
std :: cout << "Kalit mening xaritamda yo'q" << '\n' ;


// xaritadagi yozuvlarni tozalash
my_map.clear();
}
Yuqoridagi misolda qo'shish funksiyasi yordamida oltita element kiritiladi, so'ngra birinchi element o'chiriladi. Keyin xaritaning o'lchami chiqariladi. Keyinchalik, foydalanuvchidan qidirish uchun kalit so'raladi. Iterator yordamida find funksiyasi berilgan kalit bilan elementni qidiradi. Agar u kalitni topsa, dastur elementning qiymatini chop etadi. Agar uni topa olmasa, xaritaning oxirigacha bo'lgan iterator qaytariladi va u kalitni topib bo'lmaganligini ko'rsatadi. Nihoyat, daraxtdagi barcha elementlar o'chiriladi.
Iteratorlar [ tahrirlash ]
Xaritalar konteynerdagi muayyan elementlarga ishora qilish uchun iteratorlardan foydalanishi mumkin. Iterator elementning kalitiga ham, xaritalangan qiymatiga ham kirishi mumkin: ^[1]
map < Key,T >:: iterator bu; // xarita iteratorini e'lon qiladi
u -> birinchi; // kalit qiymati
u -> ikkinchi; // ko'rsatilgan qiymat
( * bu); // "element qiymati" turi: pair
Quyida iteratorlar yordamida barcha kalit va qiymatlarni ko'rsatish uchun xarita bo'ylab aylanish misoli keltirilgan:
#o'z ichiga oladi
#o'z ichiga oladi
#o'z ichiga oladi

int asosiy ()

{
std :: xaritasi < std :: string, int > maʼlumotlar{
{ "Bobs ball" , 10 },
{ "Martys gol" , 15 },
{ "Mehmets ball" , 34 },
{ "Rokki hisobi" , 22 },
{ "Rokki hisobi" , 23 } /*22-ning ustiga yoziladi, chunki kalitlar bir xil bo'ladi */
};
// Xaritani takrorlang va barcha kalit/qiymat juftlarini chop eting.
uchun ( konst avto & element : ma'lumotlar)
{
std :: cout << "Kim (kalit = birinchi): " << element.birinchi;
std :: cout << " Bal (qiymat = soniya): " << element.ikkinchi << '\n' ;
}


qaytish 0 ;
}
Yuqoridagi namunani GCC kompilyatorida kompilyatsiya qilish uchun maxsus standart tanlash bayrog'idan foydalanish kerak.
g ++ - std = c ++11 source.cpp - o src
Bu kalitlar bo'yicha tartiblangan butun xaritaning kalitlari va qiymatlarini chiqaradi.