|
Konteynerlar bilan ishlash algoritmlari
|
| bet | 35/131 | | Sana | 13.05.2024 | | Hajmi | 1,83 Mb. | | #228405 |
Bog'liq Tiplarni dinamik tarzdaKonteynerlar bilan ishlash algoritmlari. Barcha konteynerlar umumiy yondashuvi tufayli, amalda qiziqtirgan asosiy algoritmlar konteynerlarning har qanday turi uchun qo‘llanilishi mumkin bo‘lgan umumiy shaklda amalga oshirilishi mumkinligi tufayli STL konteynerlar uzoq amaliy foydalanish uchun bir arzigulik ixtiro bo‘ldi.
Algoritmlar kutubxonaning eng katta va ommabop qismidir. Juda ko‘p algoritmlar mavjudki, ularning hammasini batafsil bayon qilish uchun katta kitob kerak. Quyida ularni guruhlarga ajratib, ularning nomlari bilan ataymiz (ularning hammasi emas) va ulardan faqat ayrimlari misol tariqasida keltiramiz.
for_each()algoritmi. for_each() eng ko‘p ishlatiladigan algoritmdir. Konteyner elementlar guruhi (ehtimol, barcha elementlari) uchun ketma-ket harakatni amalga oshiradi. U har qanday STL konteynerda foydalanish mumkin. Quyidagi 4.9-dasturda for_each() algoritm massiv va vektor uchun ishlatilgan.
4.9-dastur. for_each() algoritmidan foydalanish.
// Created by MBBahodir #include "stdafx.h" #include #include #include
using namespace std;
|
inline ostream& operator <<( ostream& out, const vector< unsigned > & obj ) { cout << "< ";
for( auto& p: obj ) cout << p << " ";
return out << ">";
}
void pow2( unsigned& i ) { i *= i; } int main( void ) {
const int examples = 4;
for( int i = 0; i < examples; i++ ) {
unsigned ai[] = { 1, 2, 3, 4 , 5, 6, 7, 8, 9 }, ni = sizeof( ai ) / sizeof( ai[ 0 ] );
vector< unsigned > vi( ai, ai + ni ); cout << vi;
switch( i ) { case 0:
for_each( vi.begin(), vi.end(), pow2 ); cout << " => " << vi << endl;
break; case 1:
for_each( ai, ai + ni, pow2 );
cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break;
case 2:
for( auto& i : ai ) pow2( i );
cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break;
case 3:
for_each( vi.begin() + 2, vi.end() - 2, pow2 ); cout << " => " << vi << endl;
break;
}
}
system("pause"); return 0;
}
|
4.9-dastur.Output.
|
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
|
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
< 1 2 3 4 5 6 7 8 9 > => < 1 2 9 16 25 36 49 8 9 >
|
Dasturning birinchi global (auto &x : ...) takrorlanish fragmenti ishlashini ko‘rsatilgan (C++11 standarti tomonidan joriy qilingan). Bu kabi fragmentni massivlar va konteynerlarga ham qo‘llanilishi mumkin (bu vektorni oqimga chiqarish operatori variant funksiyasida ko‘rsatilgan). Bu takrorlanish fragmenti aslida STL kutubxona yoki algoritmlarni qismi emas, lekin u for_each() algoritm bilan bir xil taʻsir ko‘rsatadi, yaʻni to‘plam barcha elementlar uchun izchil qo‘llash mumkin.
Bu yuqoridagi dastur barcha algoritmlarni berilgan interval asosida tashkiliy asosiy mantiq qismini ko‘rsatadi (shart emas, barcha konteynerlar). Boshi va oxiri bilan cheklangan iteratorga (ko‘pincha, birinchi berilgan 2 ta parametrlar) funksiya, funktor va predikat (bu funksiyalarga - qaysidir elementlari bo‘yicha saralash imkoni bo‘lsa va mantiqiy qiymat qaytaradigan funksiyalar kiradi) navbat bilan qo‘llaniladi.
Find(). Navbatdagi algoritm – bu find(). Bu nomidan maʻlumki, to‘plamdagi elementlarni qidirish funksyasidir. Eʻtibor bersak, juda ko‘p konteynerlar bunday find() – funksiyasiga ega va u obʻyekt uchun obj.find(…) sietaksisida ishlatiladi. Shu vaqtda algoritm quyidagicha funksiyani find( obj:iteator, … ) ishga tushuradi. Aslida, bu bitta algoritm emas, balki ularning butun bir katta guruhi maveud, ular to‘plam elementlarini baʻzi atribut, shart bilan tanlashlari asosida birlashtirilishi mumkin. Bu guruh predikatlariga find(), find_if(), find_if_not(), find_first_of(), find_end(), adjacent_find() funksiyalari kiradi. Shuningdek bu guruhda kengaytirilgan algoritmlar ham tegishlidir va bularga count(), count_if(), search(), binary_search(), min(), max(), minmax_element(), min_element(), max_element(), equal() kabi bir qator algoritmlar kiradi.
To‘plamga ishlov berish (aralashtirish) bir shartli guruh algoritmlar mavjud va ular joylarda elementlarni qayta tartibga soluvchi va qiymatlarni o‘zgartiruvchi
algoritmlardir: fill(), replace_copy(), reverse(), rotate(), rotate_copy(), shuffle(), random_shuffle(), transform(), replace(), replace_if() va boshqa funksiyalar.
Ikki to‘plamlar ustida bajariladigan algoritimlar guruhi ham mavjud. Bular asosan nusxalash, tarkibini ko‘chirib o‘tish (xar tipdagi konteynerlar uchun bo‘lishi mumkin. Masalan, vector<> ni set<> ga) funksiyalarini bajaradi. Bularga copy(), copy_if(), move(), swap_ranges(), remove_copy(), remove_copy_if(), merge(), set_intersection(), set_difference() va boshqa algoritmlar.
Nihoyat, juda maxsus guruh algoritmlari, to‘plam ichida elementlar turli saralash bilan bog‘liq funksiyalar sort(), stable_sort(), is_sorted(), is_sorted_until()va boshqa algoritmlar. Ushbu qiziqarli guruhni keyinroq, alohida batafsil ko‘rib chiqish kerak.
Kutubxonada vaqt o‘tishi bilan ortib borayotgan algoritmlarning ko‘pligi va ularning aksariyati adabiyotda hech qanday taʻriflanmasligiga qaramasdan, tabiiy savol tug‘iladi: bu xilma-xillikni qanday tushunish kerak? Bu qiyinchiliklar qanday engio‘ mumkin:
Barcha STL obʻyektlar (konteynerlar, algoritmlar) shablon sintaktiki bo‘yicha tasvirlangan. Shuning uchun, ularning tavsiflari, ularning header fayllarida dastur fragmentlari sifatida tuzilgan bo‘lishi kerak.
Kerakli algoritimlar uchun header fayllarni standart katalogiga o‘ting va stl_algo* kabi sarlavha fayllarini toping - uda barcha algoritm funksiyasi prototiplarini (o‘xshashlarini) topasiz. Bundan tashqari, har bir prototipi algoritm maqsadini tushuntirib va parametrlarini tushuntirishning batafsil izoh oldindan yozib ko‘yilgan.
Bir necha asosiy STL algoritmlarni foydalanishga doir misollar ko‘rib chiqing – kutubxonalar tizimida ularning ko‘pchiligi bor. O‘xshashlik bilan boshqa barcha algoritmlarni yaratish mumkin.
Shablon sinf kutubxonalar shablon jihatidan template termin bilan belgilangan, chunki o‘sha, kompilyatsiya sintaktiki xato bo‘yicha xabarlarni chiqaradi. Birinchisi yozma xabarlar fragmentlari bo‘yicha va ikkinchi xatolarni izlash uchun. Bu shablon kabi kuchli mexanizmi tomonidan qayyta ishlanidi (tekshiriladi) va dasturchi bu uchun tayyor bo‘lishi kerak.
Yuqorida aytib o‘tilganidek, misollarni o‘rganish juda ko‘p savollarga javob beradi, shuning uchun dastur keltiramiz. Endi o‘rgangan algoritmlarni diqqat bilan eslang (har birini sharhlab, kutubxona sinflaridan tashqarida bo‘lgan juda ko‘p STL algoritmlari mavjud, ammo ularning barchasi bir-biriga o‘xshab ishlaydi):
4.10-dastur. Standart algoritmlardan foydalanish.
#include "stdafx.h" #include #include #include #include |
vector suv( vs[ 0 ].size() );
copy( vs[ 0 ].begin(), vs[ 0 ].end(), suv.begin() ); cout << suv << endl;
random_shuffle( suv.begin(), suv.end() ); cout << suv << endl;
reverse( suv.begin(), suv.end() ); cout << suv << endl;
rotate( suv.begin(), suv.begin() + suv.size() / 2, suv.end() ); cout << suv << endl;
// set_intersection & set_difference set< char > sus, pns;
for( char s: vector( vs[ 0 ].begin(), vs[ 0 ].end() ) ) sus.insert( s );
for( char s: vector( vs[ 1 ].begin(), vs[ 1 ].end() ) ) pns.insert( s );
vector outi( 100 ), outd( 100 );
auto ret = set_intersection( sus.begin(), sus.end(), pns.begin(),
pns.end(), outi.begin() ); cout << "umumiy belgi " << ( ret - outi.begin() ) << " : "
<< outi << endl;
ret = set_difference( sus.begin(), sus.end(), pns.begin(),
pns.end(), outd.begin() );
cout << "unikal belgi " << ( ret - outd.begin() ) << " : "
<< outd << endl; system("pause"); return 0;
}
|
4.10-dastur. Output
|
boʻsh joylar soni: 6 (7 soʻz) belgilar uzunligi: ' ' ... 'z'
Muminov nuvmMoi ioMmvun mvunioM
umumiy belgi 2 : io
unikal belgi 5 : Mmnuv
|
Dasturda char uchun konteynerlardan foydalanilgan. Deyarli barcha berilgan konteynerlar uchun turli xil algoritmlar amalga oshirilgan. (ixcham, ammo zerikarli fragmentlar).
|
| |
