Tartiblanmagan konteynerlarda ishlatilmaydigan usullar:
[>], [<,] [>=], [<=] taqqoslash amallari ( [==]va [!=]amallarni qo‘llab quvvatlaydi)
lower_bound va upper_bound
Ikki tomonlama iteratorlar: rbegin, crbegin, rend, crend Tartiblanmagan konteynerlarning usullari:
Xeshlash uslubi (Bu usullar tartibsiz konteynerlarning ishlashini boshqarish imkonini beradi):
load_factor() – to‘ldirish koeffitsentini qaytaradi (yuqoriga qarang)
max_load_factor() – Agar argumentsiz foydalanilsa, maksimal to‘ldirish qiymati uchun float tipini qaytaradi, agar argument sifatida float tipi foydalanilsa, maksimal to‘ldirish qiymati uchun o‘rnatiladi . Agar terminator omili ushbu chegaradan oshsa, konteyner avtomatik ravishda segmentlar sonini oshirishi mumkin.
rehash(size_type count) – konteyner uchun qayta xeshlash o‘tkazadi, yaʻni yacheykalarni sonini (backet_count) backet_count >= count va backet_count > size/max_load_factor bo‘lishi uchun.
reserve(size_type count) – songa yacheykalar sonni o‘rnatadi, konteynerni qayta xeshlash o‘kazmaslik va maksimal to‘ldirish koeffitsienti uchun, oxirgi yacheykaning count hisoblanadi.
Maksimal samaradorlikka erishish uchun har doim maksimal yacheykalar sonini aniq belgilash kerak. Tavsiya etilgan qiymatlar 0.7 dan 0.8 gacha oraliqda bo‘ladi. Element qidirish uchun standart maksimal yacheykalar soni o‘rnatiladi (
ga teng) va dastuochilar tomonidan 0.7 o‘rnatiladi.
Xesh funksiyasining o‘zi konteyner faoliyatini yaxshilashi mumkin, ammo bu mavzu doirasidan chiqib ketishga olib keladi.
Interfeys segmentlari. Segment elementlari bilan bevosita ishlash uchun (bog‘langan ro‘yxat sifatida) quyidagi usullardan foydalaniladi:
begin(), end(), cbegin(), cend() – iteratorla. Eʻtibor bering, bular segmentlar uchun, massiv uchun emas! Konteynerlar uchun shularning anologlari yaratilgan.
size_type bucket_count() – massivdagi segmentlar sonini qaytaradi.
size_type max_bucket_count() – muuumkin bo‘lgan maksimal elementlar soni (tizimga va joriy qilishga bog‘liq).
size_type bucket_size(size_type n) –n indeksli segmentdagi elementlar soni.
size_type bucket(Key) – kalit asosida segment sonini qaytaradi.
Bu usullar asosida xesh jadvalni vizual ko‘rinishini tasavvur qilish mumkin. 3.6-dastur. Tartiblanmagan konteynerlardan foydalanish.
#include "stdafx.h"
#include #include #include #include #include #include
using namespace std;
int main() {
default_random_engine rnd(time(0)); uniform_int_distribution g(100, 999); unordered_multiset unm;
size_t n = 60; unm.reserve(n); while (n--) unm.emplace(g(rnd));
cout << "Konteynerdagi segmentlar soni: "
<< unm.bucket_count()
<< "\n"
<< "Maksimal toʻldirishlar ko'ffitsenti: "
<< unm.max_load_factor()
<< endl;
auto start = chrono::system_clock::now(); auto res = unm.find(200); auto end = chrono::system_clock::now(); auto elapsed = end - start; cout << "Natija => "
<< elapsed.count()
<< endl;
// Oʻzimiz tomondam Maksimal toʻldirishlar ko'ffitsenti oʻrnatamiz unm.max_load_factor(0.7);
unm.rehash(200);
cout << "Konteynerdagi segmentlar soni: "
<< unm.bucket_count()
<< "\n"
<< "Maksimal toʻldirishlar ko'ffitsenti: "
<< unm.max_load_factor()
<< endl;
start = chrono::system_clock::now(); res = unm.find(200);
|
end = chrono::system_clock::now(); elapsed = end - start; cout << "Natija => "
<< elapsed.count()
<< endl;
cout << " Hash tuzilmasi " << endl;
for (size_t i = 0; i < unm.bucket_count(); i++) { cout << "Segment N:" << setw(3) << i << "
=> ";
// Iteratorga lokal segmentlarni olish auto first = unm.cbegin(i); auto last = unm.cend(i); while (first != last) {
cout << *first++ << " ";
}
cout << endl;
}
system("pause"); return 0;
}
|
3.6-dastur. Output
|
Konteynerdagi segmentlar soni: 32 Maksimal toʻldirishlar ko'ffitsenti: 1 Natija => 30023 Konteynerdagi segmentlar soni: 256 Maksimal toʻldirishlar ko'ffitsenti: 0.7 Natija => 10004 Segment N: 0 => Segment N: 1 => Segment N: 2 => Segment N: 3 => Segment N: 4 =>
Segment N: 5 => Segment N: 6 => Segment N: 7 => Segment N: 8 => Segment N: 9 => 646
Segment N: 10 => Segment N: 11 => Segment N: 12 => Segment N: 13 => Segment N: 14 =>
Segment N: 15 => Segment N: 16 => Segment N: 17 => Segment N: 18 => Segment N: 19 =>
Segment N: 20 => Segment N: 21 => Segment N: 22 => Segment N: 23 => Segment N: 24 => 940
Segment N: 25 => Segment N: 26 => Segment N: 27 => Segment N: 28 => Segment N: 29 =>
Segment N: 30 => 717 Segment N: 31 => Segment N: 32 => Segment N: 33 => Segment N: 34 =>
Segment N: 35 => Segment N: 36 => Segment N: 37 => Segment N: 38 => Segment N: 39 =>
|
Segment N: 40 => Segment N: 41 => Segment N: 42 => Segment N: 43 => Segment N: 44 =>
Segment N: 45 => 841 738
Segment N: 46 => Segment N: 47 => Segment N: 48 => Segment N: 49 => Segment N: 50 => Segment N: 51 => Segment N: 52 => 768 Segment N: 53 => Segment N: 54 => Segment N: 55 => Segment N: 56 => Segment N: 57 => Segment N: 58 => Segment N: 59 => Segment N: 60 => 631 Segment N: 61 => Segment N: 62 => 316 Segment N: 63 => Segment N: 64 => Segment N: 65 => Segment N: 66 => Segment N: 67 => Segment N: 68 => Segment N: 69 => Segment N: 70 => Segment N: 71
=> Segment N: 72 => Segment N: 73 => Segment N: 74 => Segment N: 75 => Segment N: 76 => Segment N: 77 => Segment N: 78 => Segment N: 79 => Segment N: 80 => Segment N: 81 => Segment N: 82 => Segment N: 83 => Segment N: 84
=> Segment N: 85 => Segment N: 86 => Segment N: 87 => Segment N: 88 => Segment N: 89 => Segment N: 90 => Segment N: 91 => Segment N: 92 => 498 Segment N: 93 => Segment N: 94 => 187 476
Segment N: 95 => Segment N: 96 => Segment N: 97 => Segment N: 98 => 280 Segment N: 99 => Segment N:100 => 225 Segment N:101 => Segment N:102 => Segment N:103 => Segment N:104 => Segment N:105 => 973 Segment N:106 => Segment N:107 => Segment N:108 => Segment N:109 => Segment N:110 => Segment N:111 => Segment N:112 => Segment N:113 => Segment N:114 => Segment N:115 => Segment N:116 => 960 Segment N:117 => Segment N:118 => Segment N:119 => Segment N:120 => Segment N:121 => 630 Segment N:122 => Segment N:123 => Segment N:124 => 567 Segment N:125 => Segment N:126 => Segment N:127 => Segment N:128 => Segment N:129 => Segment N:130 => Segment N:131 => Segment N:132 => Segment N:133 => 351 Segment N:134 => 227 Segment N:135 => Segment N:136 => Segment N:137 => Segment N:138 => Segment N:139 => Segment N:140 => Segment N:141 => Segment N:142 => Segment N:143 => Segment N:144 => Segment N:145 => Segment N:146 => 761 Segment N:147 => Segment N:148 => 145 Segment N:149 => Segment N:150 => Segment N:151 => Segment N:152 => Segment N:153 => Segment N:154 => Segment N:155 => Segment N:156 => Segment N:157 => Segment N:158 => Segment N:159 => Segment N:160 => Segment N:161 => Segment N:162 => Segment N:163 => Segment N:164 => Segment N:165 => Segment N:166 => Segment N:167 => 242 Segment N:168 => Segment N:169 => Segment
N:170 => Segment N:171 => Segment N:172 => Segment N:173 => Segment
|
N:174 => Segment N:175 => Segment N:176 => Segment N:177 => Segment N:178 => Segment N:179 => Segment N:180 => 458 Segment N:181 => Segment N:182 => Segment N:183 => Segment N:184 => Segment N:185 => Segment N:186 => Segment N:187 => Segment N:188 => Segment N:189 => Segment N:190 => Segment N:191 => Segment N:192 => 852 Segment N:193 => Segment N:194 => Segment N:195 => Segment N:196 => Segment N:197 => 287 Segment N:198 => Segment N:199 => Segment N:200 => Segment N:201 => Segment N:202 => Segment N:203 => Segment N:204 => Segment N:205 => Segment N:206 => Segment N:207 => Segment N:208 => Segment N:209 => 483 Segment N:210 => 697
Segment N:211 => Segment N:212 => Segment N:213 => Segment N:214 =>
|
Segment N:215 => 967 Segment N:216 => Segment N:217 => Segment N:218 => Segment N:219 => Segment N:220 => Segment N:221 => Segment N:222 => Segment N:223 => Segment N:224 => Segment N:225 => Segment N:226 => Segment N:227 => Segment N:228 => Segment N:229 => 666 Segment N:230 => 484 Segment N:231 => Segment N:232 => 603 Segment N:233 => Segment N:234 => Segment N:235 => 254 Segment N:236 => Segment N:237 => Segment N:238 => Segment N:239 => Segment N:240 => Segment N:241 => Segment N:242 => Segment N:243 => Segment N:244 => Segment N:245 => Segment N:246 => Segment N:247 => Segment N:248 => Segment N:249 => Segment N:250 => Segment N:251 => Segment N:252 => Segment N:253 => Segment N:254 =>
Segment N:255 =>
|
Tartiblanmagan konteynerlarning sinflari murakkab tuzilishga ega, ammo standart vositalar bilan ham tartiblangan konteynerlardan kam bo‘lmagan mukammal ishlashni ko‘rsatadi. Tartiblangan konteynerlar yoki tartiblanmagan konteynerlar orasidagi tanlov vazifaga bog‘liq bo‘ladi. Assotsiativ konteynerlarning asosiy usullari keng tarqalganligi sababli, dasturning bir bajarilishidan boshqasiga o‘tish oson va testlarni o‘tkazganingizdan so‘ng tanlovingizni bir yoki bir nechta turli konteynerda amalga oshirib, tanlov qilishingiz mumkn.
Tartiblanmagan konteynerlarning sinflari xususiyatlari.
Headers
|
|
|
Members
|
unordered_ set
|
unordered_ multiset
|
unordered_ map
|
unordered_ multimap
|
|
constructor
|
unordered_ set
|
unordered_ multiset
|
unordered_ map
|
unordered_ multimap
|
destructor
|
~unordered_ set
|
~unordered_ multiset
|
~unordered_ map
|
~unordered_ multimap
|
assignment
|
operator=
|
operator=
|
operator=
|
operator=
|
iterators
|
begin
|
begin
|
begin
|
begin
|
begin
|
end
|
end
|
end
|
end
|
end
|
rbegin
|
|
|
|
|
rend
|
|
|
|
|
const iterators
|
cbegin
|
cbegin
|
cbegin
|
cbegin
|
cbegin
|
cend
|
cend
|
cend
|
cend
|
cend
|
|
crbegin
|
|
|
|
|
crend
|
|
|
|
|
capacity
|
size
|
size
|
size
|
size
|
size
|
max_size
|
max_size
|
max_size
|
max_size
|
max_size
|
empty
|
|
Qanday konteynerlar uchun aniqlanadigan tip va kalit tipi bir xil bo‘ladi?
Assosiativ konteynerlarning iteratorlari necha tomonlama iteratorlar sinfiga kiradi?
Kalit asosida qidirishda berilgan kichik bo‘lmagan birinchi elementni qanday funksiya va birinchi katta elementni qanday funksiya yordamida amalga oshiriladi?
Set to‘plamda qiymatni o‘zgartirish uchun avval nima funksiyani bajarib, so‘ng yangi qiymatni yoki o‘zgartirilgan varianti qo‘shiladi?
Xotirani ajratish va bo‘shatish operatorlari set sinfi uchun sanab bering?
Ishorali butun tip, aniq tipni belgilash realizatsiya qilishga bog‘liq va Allocatorda aniqlanadi. Gap qaysi funksiya haqida.
To‘plam - assosiativ konteynet bo‘lib, teng qiymatli kalitlarni saqlaydi (mumkin qadar bir kalit qiymatli elmentlar to‘plamini saqlaydi) va kalit orqali tez qidirish imkonini beradi. Gap qaysi to‘plam haqida bormoqda.
set va multiset sinflarining obʻyektlarining tipi kalit bilan yonma-yon bitta shablonli
parametr olishi mumikn. Bu shablon qaysi funksiya?
12.[=] (operator=) operatorni nima uchun ishlatiladi?
To‘plam va vektorning massivlarini tasodifiy sonlar bilan to‘ldiradigan va belgilangan qiymatni qidiradigan dastur tuzing.
Pair qanday sinf va nima uchun kerak?
15.p.first – havola bo‘yicha juftlikning nechanchi elementiga murojaat? 16.Lug‘atda kalitlari unikal (takrorlanmaydigan) va qaysi sinfda bir nechta
nusxadagi kalitlari bo‘ladi.
Oddiy map konreyner konstruktorlari: map ar; va map ar(Comp); ni ishlash tartibini tushuntirib bering.
Ro‘yxatni initsializatsiya qilishda har bir juftlik alohida qanday qavs ichiga olinishi kerak.
Lug‘atlarda elementlarga kirishning yana ikkita usuli mavjud (iteratorlar bilan ishlashdan tashqari). Birinchi va ikkinchi usularni tushuntirib bering.
Indekslash funksiyasini assotsiativ konteyner sinflarning qaysi sinflariga foydalanish mumkin.
at() funksiyasi istisno qaytargani uchun try - catch funksiyasi bilan boshqarish mumkinmi?
operator[] noqulay va samarasiz deb hisoblasangiz, yana unga ikkita alternativ variantlar bor. Bu variantlarni ayting.
Qaysi to‘plamda qidirish faqat birinchi maydon, yaʻni kalit maydon bilan amalga oshiriladi.
Qanday konteynerlar xesh – jadval asosida qurilgan va xesh funksiyalarga va tenglik amaliga tayanadi.
Ayrim vazifalarda saralash uchun vaqt ko‘p ajratilsa avtomatik saralashni muhim kamchilik deb hisoblash mumkin. Bunda dasturchi qanday yo‘l tutadi.
Tartiblanmagan konteynerlarning xesh jadvallarida nima bor va ular cheksiz ko‘p elementlarni o‘z ichiga olishi mumkin.
Do'stlaringiz bilan baham: |
