Tartiblanmagan konteynerlarda ishlatilmaydigan usullar

|
Tartiblanmagan konteynerlarda ishlatilmaydigan usullar
|
bet | 30/143 | Sana | 20.07.2024 | Hajmi | 0,81 Mb. | | #268096 |
Bog'liq Tiplarni dinamik tarzda-fayllar.orgTartiblanmagan 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
|
|
|
| |