کتابخانهی الگوی استاندارد (Standard Template Library) یا به اختصار STL، مجموعهای از کلاسهای الگو که ساختارهای دادهی برنامهنویسی رایج و توابعی مانند vec-tor ،lists ،stacks و غیره هستند را فراهم میکند. در این قسمت از آموزش و دیگر آموزشها در آینده به بررسی این کتابخانه خواهیم پراخت. پس تا پایان با ما همراه باشید.
ابتدا به اجزاء یا کامپوننتهای این کتابخانه خواهیم پرداخت و سپس به یک جزء آن که الگوریتمها (Algorithms) نام دارد، میپردازیم.
همانطور که در بالا گفته شد، این کتابخانه مجموعهای از کلاسهای الگو است که ساختارهای دادهی برنامهنویسی رایج و توابع را فراهم کرده است. این یک کتابخانه از کلاسهای نگهدارنده، الگوریتمها و پیمایشگرها است. این کتابخانه یک کتابخانه عمومی است و بنابراین اجزاء یا کامپوننتهایش (components) پارامتری هستند. داشتن دانش کار با کلاسهای الگو (template classes) پیشنیاز کار با STL است.
هِدر (header) الگوریتم مجموعهای از توابع ویژه طراحیشده برای استفاده روی طیفی از عناصر، تعریف میکند. آنها بر پایهی نگهدارندهها عمل میکنند و روشی را برای عملیاتها مختلف روی محتوای نگهدارنده فراهم میکنند.
1. الگوریتم (Algorithm)
2. عددی (Numeric)
نگهدارندهها یا کلاسهای نگهدارنده اشیاء و داده را ذخیره میکنند. در کُل 7 کلاس نگهدارنده طبقهاول استاندارد و 3 کلاس تطبیقدهنده نگهدارنده و تنها 7 هِدر فایل که دسترسی به این نگهدارندهها یا نگهدارندههای تطبیقدهنده را فراهم میکنند، وجود دارد.
نگهدارندههای ترتیبی (Sequence Containers): ساختارهای دادهی را پیادهسازی میکند که میتوانند در یک روش ترتیبی دسترسی داشته باشند.
تطبیقدهندههای نگهدارنده (Container Adaptors): یک رابط متفاوت را برای نگهدارندههای ترتیبی فراهم میکند.
نگهدارندههای شرکتپذیر (Associative Containers): ساختارهای دادهی مرتبشده پیادهسازی میکنند که میتوانند سریع جستجو شوند (پیچیدگی O(log n)).
نگهدارندههای شرکتپذیر نامرتبشده (Unordered Associative Containers): ساختارهای دادهی نارمرتبشده پیادهسازی میکنند که میتوانند سریع جستجو شوند.
STL شامل کلاسهایی است که تابعی به نام اُپریتور (operator) را سربارگذاری میکند. نمونههایی از چنین کلاسهایی، اشیاء توابع (function objects) یا عملکنندهها (functors). عملکنندهها امکان کار کردن تابع مربوطه سفارشیشده با کمک پارمترها ارسالشده فراهم میکند.
همانطور که از نام آن پیدا است، پیمایشگرها برای کار بر روی مقادیر ترتیبی (sequence of values) استفاده شده هستند. آنها ویژگی مهمی هستند که اجازهی عمومیت در STL را میدهد.
این کتابخانهی در هِدر <utility> تعریف شده است.
حال در ادامه به الگوریتم مرتبسازی (Sorting) خواهیم پرداخت.
مرتبسازی (Sorting) یکی از پایهترین توابع اعمال شده به داده است که به معنی مرتبکردن داده در یک روش خاص است که میتواند رو به افزایش یا کاهش باشد. یک تابع توکار در STL به نام ()sort وجود دارد. این تابع به طور داخلی از IntroSort استفاده میکند. در جزئیات بیشتر، تابع با استفاده از ترکیبی از QuickSort، HeapSort، و InsertionSort پیادهسازی شده است. در حالت پیشفرض، تابع از QuickSort استفاه میکند اما اگر QuickSort تقسیمبندی نادرست انجام دهد و بیش از N*logNبار بگیرد، تابع به HeapSort انتقال پیدا میکند و زمانی که اندازهی آرایه خیلی کوچک شود، تابع به InsertionSort انتقال پیدا میکند.
نمونهی اولیه (prototype) برای تابع sort به این صورت است:
sort(startaddress, endaddress) startaddress: the address of the first element of the array endaddress: the address of the next contiguous location of the last element of the array. So actually sort() sorts in the range of [startaddress,endaddress)
// C++ program to sort an array #include <algorithm> #include <iostream> using namespace std; void show(int a[], int array_size) { for (int i = 0; i < array_size; ++i) cout << a[i] << " "; } // Driver code int main() { int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; // size of the array int asize = sizeof(a) / sizeof(a[0]); cout << "The array before sorting is : \n"; // print the array show(a, asize); // sort the array sort(a, a + asize); cout << "\n\nThe array after sorting is :\n"; // print the array after sorting show(a, asize); return 0; }
خروجی قطعهکُد بالا به این صورت است:
The array before sorting is : 1 5 8 9 6 7 3 4 2 0 The array after sorting is : 0 1 2 3 4 5 6 7 8 9
برای جزئیات بیشتر، میتوانید به () std::sort مراجعه کنید که در ادامه به جزئيات بیشتری از این تابع خواهیم پرداخت.
دربارهی qsort() in C در زبان C صحبت کردهایم. کتابخانهی STL در زبان ++C هم یک تابع مشابه sort که یک vector یا آرایه (array) که آیتمها با دسترسی تصادفی هستند را مرتب میکند را ارائه میدهد. تابع معمولا 2 پارامتر دریافت میکند، اولین پارامتر نقطهی شروع مرتبسازی آرایه یا vector است و دومین پارامتر طولی که میخواهیم آرایه یا vector مرتب شود، است. پارامتر سوم اختیاری است و میتواند در در مواردی به عنوان مثال اگر خواستیم عناصر به صورت الفبایی (lexicographically) مرتب شوند، استفاده شود.
در حالت پیشفرض، تابع ()sort عناصر را به ترتیب صعودی مرتب میکند. قطعهکُد سادهی زیر، نشان میدهد تابع ()sort چگونه کار میکند.
// C++ program to demonstrate default behaviour of // sort() in STL. #include <bits/stdc++.h> using namespace std; int main() { int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); /*Here we take two parameters, the beginning of the array and the length n upto which we want the array to be sorted*/ sort(arr, arr + n); cout << "\nArray after sorting using " "default sort is : \n"; for (int i = 0; i < n; ++i) cout << arr[i] << " "; return 0; }
خروجی قطعهکُد بالا به این صورت است:
Array after sorting using default sort is : 0 1 2 3 4 5 6 7 8 9
تابع ()sort پارامتر سومی دریافت میکند که برای مشخصکردن ترتیب استفاده میشود که در نتیجه آن، عناصر مرتب میشوند. میتوان تابع ()greater را برای مرتبکردن در ترتیب نزولی به آن ارسال کرد. این تابع یک مقایسه انجام میدهد، به نحوی که عناصر بزرگتر را قبل قرار میدهد.
// C++ program to demonstrate descending order sort using // greater<>(). #include <bits/stdc++.h> using namespace std; int main() { int arr[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int n = sizeof(arr) / sizeof(arr[0]); sort(arr, arr + n, greater<int>()); cout << "Array after sorting : \n"; for (int i = 0; i < n; ++i) cout << arr[i] << " "; return 0; }
خروجی قطعهکُد بالا به این صورت است:
Array after sorting : 9 8 7 6 5 4 3 2 1 0
میتوان همچنین تابع مقایسهی خودمان را بنویسیم و آن را به عنوان پارامتر سوم ارسال کنیم. این تابع مقایسهگر یک مقدار برمیگرداند؛ قابل تبدیل به bool که اساسا به ما میگوید که آیا آرگومان اول ارسال شده، باید جایگذاری شود قبل از آرگومان دوم یا نه. برای مثال، در قطعهکُد زیر، فرض شده است که intervals {6,8} و {1,9} به عنوان آرگومان در تابع compareInterval (تابع مقایسهگر) ارسال شدهاند. حال، درصورتیکه i1.first (=6) < i2.first (=1) باشد، تابعمان false را برمیگرداند. که به ما میگوید آرگومان اول نباید قبل از آرگومان دوم جایگذاری شود و بنابراین مرتبسازی در ترتیبی مانند اول {1,9} و سپس {6,8} و به همین مِنوال ادامه پیدا میکند.
// A C++ program to demonstrate // STL sort() using // our own comparator #include <bits/stdc++.h> using namespace std; // An interval has a start // time and end time struct Interval { int start, end; }; // Compares two intervals // according to starting times. bool compareInterval(Interval i1, Interval i2) { return (i1.start < i2.start); } int main() { Interval arr[] = { { 6, 8 }, { 1, 9 }, { 2, 4 }, { 4, 7 } }; int n = sizeof(arr) / sizeof(arr[0]); // sort the intervals in increasing order of // start time sort(arr, arr + n, compareInterval); cout << "Intervals sorted by start time : \n"; for (int i = 0; i < n; i++) cout << "[" << arr[i].start << "," << arr[i].end << "] "; return 0; }
خروجی قطعهکُد بالا به این صورت است:
Intervals sorted by start time : [1,9] [2,4] [4,7] [6,8]
پیچیدگی زمان تابع ()std::sort به این صورت است:
Binary search یک الگوریتم جستجوی پرکاربرد است که قبل از اعمال کردن جستجو، به آرایهای که مرتبشده باشد، نیازمند است. ایدهی اصلی پشت این این الگوریتم تقسیم آرایه از وسط (تقسیم و حل) تا زمانی که عنصر پیدا شود، یا همهی عناصر تمام شوند است. تابع توسط مقایسهی آیتم وسط آرایه با عنصرمان کار میکند. اگر عنصرمان مطابقت داشت، تابع true را برمیگرداند، در غیر اینصورت اگر عنصر وسط، بزرگتر از عنصر موردنظر ما بود، جستجو در زیرآرایه چپ (left sub-array) صورت میگیرد. اگر عنصر وسط کوچکتر از عنصر موردنظرمان بود، جستجو در زیرآرایه راست (left sub-array) صورت میگیرد.
نمونهی اولیه تابع binary search به این صورت است:
binary_search(startaddress, endaddress, valuetofind) Parameters : startaddress: the address of the first element of the array. endaddress: the address of the next contiguous location of the last element of the array. valuetofind: the target value which we have to search for. Returns : true if an element equal to valuetofind is found, else false.
خروجی قطعهکُد بالا به این صورت است:
The array is : 1,5,8,9,6,7,3,4,2,0, Let's say we want to search for 2 in the array So, we first sort the array The array after sorting is : 0,1,2,3,4,5,6,7,8,9, Now, we do the binary search Element found in the array Now, say we want to search for 10 Element not found in the array
در ادامه آموزش این کتابخانه، به معرفی نگهدارندهها (Containers) خواهیم پرداخت.
در این قسمت از سری آموزش کتابخانهی STL به معرفی نگهدارندهها (Containers) خواهیم پرداخت. از اولین نگهدارنده با نام pair آشنا شروع خواهیم کرد.
نگهدارندهی pair یا جُفت برای ادغام دو مقدار با هم که ممکن است از نوعی متفاوت باشند، استفاده میشوند. pair روشی برای ذخیره دو شیء ناهمگون تحت یک واحد فراهم میکند. اساسا اگر ما بخواهیم tuples ذخیره کنیم، استفاده میشود. نگهدارندهی pair یک نگهدارندهی ساده است که در هِدر <utility> تعریف شده است که شامل 2 عنصر یا شیء داده است.
نحو (Syntax) به این صورت است:
pair (data_type1, data_type2) Pair_name
قطعهکُد زیر استفاده از pair را نشان میدهد:
// CPP program to illustrate Pair in STL #include <iostream> #include <utility> using namespace std; // Driver Code int main() { // defining a pair pair<int, char> PAIR1; // first part of the pair PAIR1.first = 100; // second part of the pair PAIR1.second = 'G'; cout << PAIR1.first << " "; cout << PAIR1.second << endl; return 0; }
خروجی قطعهکُد بالا به این صورت است:
100 G
مقداردهی اولیه به یک pair: میتوان یک pair را مقداردهی اولیه نیز کرد که نحو آن به این صورت است:
pair (data_type1, data_type2) Pair_name (value1, value2) ;
راههای متفاوت برای مقداردهی اولیه pair به این صورت است:
pair g1; //default pair g2(1, 'a'); //initialized, different data type pair g3(1, 10); //initialized, same data type pair g4(g3); //copy of g3
راه دیگر برای مقداردهی اولیه یک pair استفاده از تابع make_pair() است، به این صورت:
g2 = make_pair(1, 'a');
نحو یا syntax معتبر دیگری که میتواند برای اعلام ( declare ) pair استفاده شود به این صورت است:
g2 = {1, 'a'};
در قطعهکُد زیر میتوانید نحوهی مقداردهی اولیه pair را مشاهده کنید:
// CPP program to illustrate // Initializing of pair STL #include <iostream> #include <utility> using namespace std; // Driver Code int main() { // defining a pair pair<string, double> PAIR2("GeeksForGeeks", 1.23); cout << PAIR2.first << " "; cout << PAIR2.second << endl; return 0; }
خروجی قطعهکُد بالا به این صورت است:
GeeksForGeeks 1.23
نکته: اگر pair مقدادهی اولیه نشده باشد، اولین مقدار pair به طور خودکار مقداردهی اولیه میشود.
قطعهکُد زیر، این موضوع را نشان میدهد:
// CPP program to illustrate // auto-initializing of pair STL #include <iostream> #include <utility> using namespace std; int main() { pair<int, double> PAIR1; pair<string, char> PAIR2; // it is initialised to 0 cout << PAIR1.first; // it is initialised to 0 cout << PAIR1.second; cout << " "; // // it prints nothing i.e NULL cout << PAIR2.first; // it prints nothing i.e NULL cout << PAIR2.second; return 0; }
خروجی قطعهکُد بالا به این صورت است:
00
1. make_pair: این تابع الگو امکان ایجاد مقدار pair را بدون تعریف انواع به طور صریح فراهم میکند که نحو آن به این صورت است:
Pair_name = make_pair (value1,value2);
قطعهکُد زیر را برای درک بهتر این موضوع مشاهده کنید:
// CPP Program to demonstrate make_pair() // function in pair #include <iostream> #include <utility> using namespace std; // Driver Code int main() { pair<int, char> PAIR1; pair<string, double> PAIR2("GeeksForGeeks", 1.23); pair<string, double> PAIR3; PAIR1.first = 100; PAIR1.second = 'G'; PAIR3 = make_pair("GeeksForGeeks is Best", 4.56); cout << PAIR1.first << " "; cout << PAIR1.second << endl; cout << PAIR2.first << " "; cout << PAIR2.second << endl; cout << PAIR3.first << " "; cout << PAIR3.second << endl; return 0; }
خروجی قطعهکُد بالا به این صورت است:
100 G GeeksForGeeks 1.23 GeeksForGeeks is Best 4.56
swap: این تابع محتوای یک شیء pair را با محتوای شیء pair دیگری عوض میکند. دقت کنید که برای عوض کردن محتوای هر دو pair باید هردوی آنها از یک نوع باشند.
نحو این تابع به این صورت است:
pair1.swap(pair2) ;
2 pair با نامهای pair1 و pair2 از یک نوع وجود دارد، تابع swap محتوای pair1.first با محتوای pair2.first و به همین صورت محتوای pair1.second را با محتوای pair2.second را عوض میکند. قطعهکُد زیر را برای درک این موضوع مشاهده کنید:
// CPP Program to demonstrate swap() // function in pair #include <iostream> #include <utility> using namespace std; // Driver Code int main() { pair<char, int> pair1 = make_pair('A', 1); pair<char, int> pair2 = make_pair('B', 2); cout << "Before swapping:\n "; cout << "Contents of pair1 = " << pair1.first << " " << pair1.second; cout << "Contents of pair2 = " << pair2.first << " " << pair2.second; pair1.swap(pair2); cout << "\nAfter swapping:\n "; cout << "Contents of pair1 = " << pair1.first << " " << pair1.second; cout << "Contents of pair2 = " << pair2.first << " " << pair2.second; return 0; }
خروجی قطعهکُد بالا به این صورت است:
Before swapping: Contents of pair1 = A 1Contents of pair2 = B 2 After swapping: Contents of pair1 = B 2Contents of pair2 = A 1
3. ()tie: این تابع مشابه در tuples کار میکند. این تابع یک tuple از ارجاعهای lvalue به آرگومانهایش ایجاد میکند. به عنوان مثال، بازکردن یا به اصطلاح unpack کردن مقادیر tuple (در اینجا pair) به داخل متغیرهای جداگانه. دقیقا مانند tuples، اینجا نیز 2 tie متفاوت است، با ignore و بدون ignore. کلمهی کلیدی ignore یک عنصر tuple خاص را از tuple باز شده نادیده میگیرد. هرچند که tuples میتوانند آرگومانهای مختلفی داشته باشند اما pairها تنها 2 آرگومانت دارند. بنابراین، درمورد pair از pairها، بازشدن باید به صورت صریح مدیریت شود.
نحو این تابع به این صورت است:
tie(int &, int &) = pair1;
قطعهکُد زیر کار تابع tie را در pair نشان میدهد:
// CPP code to illustrate tie() in Pair #include <bits/stdc++.h> using namespace std; // Driver Code int main() { pair<int, int> pair1 = { 1, 2 }; int a, b; tie(a, b) = pair1; cout << a << " " << b << "\n"; pair<int, int> pair2 = { 3, 4 }; tie(a, ignore) = pair2; // prints old value of b cout << a << " " << b << "\n"; // Illustrating pair of pairs pair<int, pair<int, char> > pair3 = { 3, { 4, 'a' } }; int x, y; char z; // tie(x,y,z) = pair3; Gives compilation error // tie(x, tie(y,z)) = pair3; Gives compilation error // Each pair needs to be explicitly handled x = pair3.first; tie(y, z) = pair3.second; cout << x << " " << y << " " << z << "\n"; } // contributed by sarthak_eddy.
خروجی قطعهکُد بالا به این صورت است:
1 2 3 2 3 4 a
قطعهکُد زیر توابع در pair را نشان میدهد:
// CPP program to illustrate pair in STL #include <iostream> #include <string> #include <utility> using namespace std; int main() { pair<string, int> g1; pair<string, int> g2("Quiz", 3); pair<string, int> g3(g2); pair<int, int> g4(5, 10); g1 = make_pair(string("Geeks"), 1); g2.first = ".com"; g2.second = 2; cout << "This is pair g" << g1.second << " with " << "value " << g1.first << "." << endl << endl; cout << "This is pair g" << g3.second << " with value " << g3.first << "This pair was initialized as a copy of " << "pair g2" << endl << endl; cout << "This is pair g" << g2.second << " with value " << g2.first << "\nThe values of this pair were" << " changed after initialization." << endl << endl; cout << "This is pair g4 with values " << g4.first << " and " << g4.second << " made for showing addition. \nThe " << "sum of the values in this pair is " << g4.first + g4.second << "." << endl << endl; cout << "We can concatenate the values of" << " the pairs g1, g2 and g3 : " << g1.first + g3.first + g2.first << endl << endl; cout << "We can also swap pairs " << "(but type of pairs should be same) : " << endl; cout << "Before swapping, " << "g1 has " << g1.first << " and g2 has " << g2.first << endl; swap(g1, g2); cout << "After swapping, " << "g1 has " << g1.first << " and g2 has " << g2.first; return 0; }
خروجی قطعهکُد بالا به این صورت است:
This is pair g1 with value Geeks. This is pair g3 with value QuizThis pair was initialized as a copy of pair g2 This is pair g2 with value .com The values of this pair were changed after initialization. This is pair g4 with values 5 and 10 made for showing addition. The sum of the values in this pair is 15. We can concatenate the values of the pairs g1, g2 and g3 : GeeksQuiz.com We can also swap pairs (but type of pairs should be same) : Before swapping, g1 has Geeks and g2 has .com After swapping, g1 has .com and g2 has Geeks
میتوان اُپریتورها را با pairها نیز استفاده کرد.
1. استفاده از از اُپریتور مساوی ( = ): این اُپریتور یک شیء جدید به یک شیء pair اختصاص میدهد. نحوه آن به این صورت است:
pair& operator= (const pair& pr);
این محتوای جدید pr را به شیء pair اختصاص میدهد. اولین مقدار از اولین مقدار pr و دومین مقدار از دومین مقدار pr اختصاص داده شده است.
2. اُپریتور مقایسه ( == ) با pair: اگر 2 pair با نامهای pair1 و pair2 داشه باشیم، اُپریتور مقایسه، اولین مقدار و دومین مقدار هر دو pair را مقایسه میکند. به عنوان مثال، آیا pair1.first برابر با pair2.first هست یا نه و آیا pair1.second برابر با pair2.second است یا نه.
3. اُپریتور نامساوی ( =! ) با pair: اگر 2 pair با نامهای pair1 و pair2 داشه باشیم، اُپریتور نامساوی ( =! ) مقادیر اول هر دو pair را مقایسه میکند. به عنوان مثال، آیا pair1.first برابر با pair2.first است یا نه، اگر آنها برابر بودند، سپس مقادیر دوم هر دو pair بررسی میکند.
4. اُپریتورهای منطقی ( >=, <= ) با pair: اگر 2 pair با نامهای pair1 و pair2 داشه باشیم، اُپریتورهای = , <، میتوانند نیز با pairها استفاده شوند. این 0 یا 1 را با تنها مقایسهی مقدار اول pair برمیگرداند. برای pairهایی مانند p1=(1,20) and p2=(1,10) p2<p1 باید 0 را برگرداند (به طوری که تنها اولین عنصر را مقایسه میکند و آنها برابر هستند بنابراین آن قطعا کمتر نیست)، اما آن درست نیست. در اینجا pair عنصر دوم را مقایسه میکند و اگر برابر بود، 1 را برمیگرداند (این تنها زمانی است که اولین عنصر در هنگام استفاده از تنها یک اُپریتور رابطهای (relational operator) > یا < باشد. درغیر اینصورت این اُپریتورها همانطور که در بالا اشاره شده است کار میکنند.
منبع: وب سایت geeksforgeeks
در این قسمت، به پرسشهای تخصصی شما دربارهی محتوای مقاله پاسخ داده نمیشود. سوالات خود را اینجا بپرسید.