بستن پنجره
فرادرس - مجموعه آموزش‌های ویدئویی  مهندسی کامپیوتر - طراحی الگوریتم - ساختمان داده
بستن پنجره     از آخرین نوشته‌ها

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

فایل سرآیند algorithm - الگوریتمستان
الگوریتمستان
515.005.00
  »  

       

معرفی فایل سرآیند algorithm از کتابخانه قالب استاندارد زبان برنامه‌نویسی ++C به همراه نمونه کد

فایل سرآیند (هدر فایل) algorithm از جمله فایل‌های سرآیند تعاریف کتابخانه‌ قالب استاندارد (STL) زبان برنامه‌نویسی ++C‌ است که به طور عمده شامل توابعی برای کار با مجموعه‌ای از داده‌ها (آرایه‌ها و لیست‌ها) است. با استفاده از این توابع به راحتی می‌توان با تنها یک خط کد عملیات جستجو، مرتب‌سازی، شمارش و بررسی یک خاصیت در تمامی داده‌های یک بازه‌ی مشخص را انجام داد.

    در استفاده از این توابع باید به این نکته توجه داشت که هر کدام از آنها فرآیندهایی داخلی دارند که اگرچه از مرتبه‌ی زمانی بهینه است، اما لزوما قابل چشم‌پوشی نیست. به عبارت دیگر، دلیل استفاده از این توابع، حذف مرتبه‌ی زمانی برخی الگوریتم‌های مورد نیاز در برنامه نیست؛ بلکه تنها کدنویسی آنها را ساده می‌کند. در ادامه تعریف و عملکرد برخی از این توابع آمده است.

      

bool all_of(InputIterator first, InputIterator last, UnaryPredicate pred)

    خروجی تابع all_of زمانی برابر true است که تابع pred به ازای تک تک عناصر بازه‌ی (first,last] خروجی true داشته باشد. این تابع برقراری شرط خاصی را به ازای تمامی عناصر بازه بررسی می‌کند.

      

bool any_of(InputIterator first, InputIterator last, UnaryPredicate pred)

    خروجی تابع any_of زمانی برابر true است که تابع pred به ازای حداقل یکی از عناصر بازه‌ی (first,last] خروجی true تولید کند.

      

bool none_of(InputIterator first, InputIterator last, UnaryPredicate pred)

    خروجی تابع none_of زمانی برابر true است که تابع pred به ازای تک تک عناصر بازه‌ی (first,last] خروجی false داشته باشد. به عبارت دیگر، این تابع برقرار نبودن شرط خاصی را به ازای تمامی عناصر بازه بررسی می‌کند و عملکرد آن معادل any_of! است.

  

Function for_each(InputIterator first, InputIterator last, Function fn)

    تابع foreach عملیات fn را به ازای تک تک عناصر بازه‌ی (first,last] انجام می‌دهد.

      

InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred)

    تابع find_if بازه‌ی (first,last] را با شروع از first پیمایش کرده و iterator اولین محلی را که خروجی تابع pred مقدار true باشد به عنوان نتیجه باز می‌گرداند اگر چنین عنصری یافت نشود مقدار last برگشت داده می‌شود.

      

InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2)

    تابع find_first_of اولین محل از بازه‌ی (first1,last1] را که شامل یکی از عناصر بازه‌ی (first2,last2] به عنوان خروجی برمی‌گرداند. اگر چنین مکانی وجود نداشته باشد، خروجی تابع مقدار last1 خواهد بود. عملگر مورد استفاده برای مقایسه در این تابع عملگر == مربوط به عناصر است.

      

typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T &val)

    تابع count تعداد تکرارهای مقدار val در بازه‌ی (first,last] را بازمی‌گرداند. معیار برابری در این تابع عملگر == تعریف شده برای عناصر است.

      

typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, UnaryPredicate pred)

    تابع count_if تعداد عناصر بازه‌ی (first,last] را محاسبه می‌کند که تابع pred به ازای آنها خروجی true بازمی‌گرداند.

      

bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)

    تابع is_permutation بررسی می‌کند که آیا عناصر بازه‌ی (first1,last1] در محلی از حافظه با شروع از first2 بدون در نظر گفتن ترتیب تکرار شده‌اند یا نه؟

      

OutputIterator copy(InputIterator first, InputIterator last, OutputIterator result)

    تابع copy عملی کپی عناصر موجود در بازه‌ی (first,last] را با شروع از محل result انجام می‌دهد.

      

void swap(T &a, T &b)

    تابع swap مقدار دو متغیر a و b را تعویض می‌کند.

      

void replace(ForwardIterator first, ForwardIterator last, const T &old_value, const T &new_value)

    تابع replace مقادیر تمام عناصر موجود در بازه‌ی (first,last] با مقدار old_value را با مقدار جدید new_value جایگزین می‌کند.

      

void fill(ForwardIterator first, ForwardIterator last, const T &val)

    تابع fill مقدار val را در تمامی عناصر بازه‌ی (first,last] قرار می‌دهد.

      

ForwardIterator unique(ForwardIterator first, ForwardIterator last)

    تابع unique تمام تکرارهای عناصر در بازه‌ی (first,last] را حذف می‌کند. این تابع پس از انتقال تمام عناصر غیر تکراری به ابتدای بازه، مقدار جدید انتهای بازه را باز می‌گرداند. به عبارت دیگر، اگر مقدار بازگشتی تابع را newEnd در نظر بگیریم، مقادیر بازه‌ی [newEnd, last) اگرچه جزئی از لیست هستند، اما محتوای آنها فاقد ارزش است.

      

ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T &val)

    تابع remove تمامی عناصر بازه‌ی (first,last] با مقدار val را از مجموعه حذف کرده و محل انتهای جدید برای بازه را باز می‌گرداند. عملکرد این تابع به این ترتیب است که از ابتدای بازه بررسی کرده و اگر مقدار عنصری برابر val باشد، مقدار بعدی را جایگزین آن می‌کند. به این ترتیب در انتهای تمامی مقادیری از بازه که برابر val نیستند به سمت ابتدای آن منتقل شده و به اندازه‌ی عناصر حذف شده در انتهای بازه‌ی قدیم فضای بدون معنی باقی می‌ماند این بازه همچنان در اختیار متغیر لیست است و از طول آن کم نمی‌شود با توجه به مقدار بازگشتی تابع remove می‌توان انتهای واقعی پس از حذف را تشخیص داد.

      

void reverse(BidirectionalIterator first, BidirectionalIterator last)

    تابع reverse عناصر بازه‌ی (first,last] را به صورت معکوس (آخر به اول) در همان محل می‌نویسد.

      

void shuffle(RandomAccessIterator first, RandomAccessIterator last, URNG& &g)

    تابع shuffle بازه‌ی (first,last] را بر اساس تابع تولید اعداد تصادفی g به هم می‌ریزد. به عبارت دیگر، عناصر بازه را به صورت تصادفی جابجا می‌کند.

      

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)

    تابع sort عناصر بازه‌ی (first,last] را بر اساس تابع comp مرتب می‌کند. مرتبه‌ی زمانی این تابع برای مرتب کردن N عنصر (O(N log N است و لزوما پایدار نیست؛ یعنی ممکن است محل عناصر با اندازه‌ی یکسان نیز جابجا شود. اگر تابع comp‌ وارد نشود (تابع تنها با دو پارامتر فراخوانی شود) داده‌ها با علامت < مقایسه شده و به صورت صعودی (کوچک به بزرگ) مرتب می‌شوند.

      

ForwardIterator max_element(ForwardIterator first, ForwardIterator last)

    تابع max_element محل عنصر با بزرگترین مقدار در بازه‌ی (first,last] را بازمی‌گرداند. اگر عنصری با مقدار بیشینه بیش از یکی باشد، اولین محل حاوی مقدار بازگردانده می‌شود.

      

ForwardIterator min_element(ForwardIterator first, ForwardIterator last)

    تابع min_element محل عنصر با کمترین مقدار در بازه‌ی (first,last] را بازمی‌گرداند. اگر عنصری با مقدار کمینه بیش از یکی باشد، اولین محل حاوی مقدار بازگردانده می‌شود.

  

توجه: برخی از توابع شامل چندین نسخه با تعداد پارامترهای متفاوت هستند که در اینجا تنها به یکی از نسخه‌ها اشاره شده است. برخی از این توابع نیز تنها در نسخه‌ی C++11 و بالاتر موجود هستند.

      

#include <iostream>
#include <algorithm>
#include <array>
#include <list>
#include <ctime>
  
using namespace std;
  
bool isOdd(int x) {
10     return (x % 2);
11 }
12   
13 void print(int x) {
14     cout << x << " ";
15 }
16   
17 int main() {
18     const int len = 5;
19     int arr1[] = {7, 3, 4, 2, 3};
20     array<int, len> arr2{{8, 2, 0, 4, 6} };
21     list<int> arr3(arr2.begin(), arr2.end());
22     shuffle(arr2.begin(), arr2.end(), default_random_engine(time(NULL)));
23     cout << "arr2 after shuffle: ";
24     for_each(arr2.begin(), arr2.end(), print);
25     // arr2 after shuffle: 0 8 2 4 6
26     cout << endl;
27     if(all_of(arr1, arr1 + len, isOdd))
28         cout << "All the elements of arr1 are odd." << endl;
29     else
30         cout << "At least one of the elements in arr1 is not odd." << endl;
31     // At least one of the elements in arr1 is not odd.
32     if(any_of(arr1, arr1 + len, isOdd))
33         cout << "At least one of the elements in arr1 is odd." << endl;
34     else
35         cout << "All the elements of arr1 are even." << endl;
36     //  At least one of the elements in arr1 is odd.
37     if(none_of(arr2.begin(), arr2.end(),isOdd))
38         cout << "All the elements of arr2 are even." << endl;
39     else
40         cout << "At least one of the elements in arr2 is odd." << endl;
41       //  All the elements of arr2 are even.
42     auto v1 = find_if(arr1, arr1 + len, isOdd);
43     cout << "The first odd element in arr1 is " << *v1 << "." << endl;
44     // The first odd element in arr1 is 7.
45     auto v2 = find_first_of(arr1, arr1 + len, arr2.begin(), arr2.end());
46     cout << "The first element of arr2 in arr1 is " << *v2 << "." << endl;
47     //  The first element of arr2 in arr1 is 4.
48     cout << "#3 in arr1 is " << count(arr1, arr1 + len, 3) << "." << endl;
49     //  #3 in arr1 is 2.
50     cout << "#Odd_Numbers in arr1 is " << count_if(arr1, arr1 + len, isOdd) << "." << endl;
51     // #Odd_Numbers in arr1 is 3.
52     if(is_permutation(arr1, arr1 + len, arr3.begin()))
53         cout << "arr3 is a permutation of arr1." << endl;
54     else
55         cout << "arr3 is not a permutation of arr1." << endl;
56     // arr3 is not a permutation of arr1.
57     if(is_permutation(arr3.begin(), arr3.end(), arr2.begin()))
58         cout << "arr3 is a permutation of arr2." << endl;
59     else
60         cout << "arr3 is not a permutation of arr2." << endl;
61     //  arr3 is a permutation of arr2.
62     cout << "arr3 before copy: ";
63     for_each(arr3.begin(), arr3.end(), print);
64     //  arr3 before copy: 8 2 0 4 6
65     copy(arr1 + 1, arr1 + 3, arr3.begin());
66     cout << endl << "arr3 after copy: ";
67     for_each(arr3.begin(), arr3.end(), print);
68     // arr3 after copy: 3 4 0 4 6
69     cout << endl;
70     swap(*arr1, *(arr1+1));
71     cout << "arr3 after swap: ";
72     for_each(arr3.begin(), arr3.end(), print);
73     // arr3 after swap: 3 4 0 4 6
74     cout << endl;
75     replace(arr3.begin(), arr3.end(), 4, 7);
76     cout << "arr3 after replace: ";
77     for_each(arr3.begin(), arr3.end(), print);
78     // arr3 after replace: 3 7 0 7 6
79     cout << endl;
80     fill(arr1, arr1 + 3, 5);
81     cout << "arr1 after fill: ";
82     for_each(arr3.begin(), arr3.end(), print);
83     // arr1 after fill: 3 7 0 7 6
84     cout << endl;
85     auto newEnd1 = unique(arr3.begin(), arr3.end());
86     cout << "arr3 after unique: ";
87     for_each(arr3.begin(), newEnd1, print);
88     // arr3 after unique: 3 7 0 7 6
89     cout << endl;
90     auto newEnd2 = remove(arr3.begin(), newEnd1, 7);
91     cout << "arr3 after remove 7: ";
92     for_each(arr3.begin(), newEnd2 , print);
93     // arr3 after remove 7: 3 0 6
94     cout << endl;
95     cout << "arr2 before reverse: ";
96     for_each(arr2.begin(), arr2.end(), print);
97     // arr2 before reverse: 0 8 2 4 6
98     cout << endl;
99     reverse(arr2.begin(), arr2.end());
100     cout << "arr2 after reverse: ";
101     for_each(arr2.begin(), arr2.end(), print);
102     // arr2 after reverse: 6 4 2 8 0
103     cout << endl;
104     sort(arr2.begin(), arr2.end());
105     cout << "arr2 after sort: ";
106     for_each(arr2.begin(), arr2.end(), print);
107     // arr2 after sort: 0 2 4 6 8
108     cout << endl;
109     cout << "Min(arr1) = " << *min_element(arr1, arr1 + len) << endl;
110     // Min(arr1) = 2
111     cout << "Max(arr1) = " << *max_element(arr1, arr1 + len) << endl;
112     // Max(arr1) = 5
113     return 0;
114 }

این نوشته آخرین بار در تاریخ یکشنبه، ۳ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
پیوندها برای مطالعه‌ی بیشتر
نوشته‌های مرتبط
        معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C
        آشنایی با مفهوم سربارگذاری عملگرها در زبان ++C
        آشنایی با کلاس‌های حافظه و کاربرد آنها در زبان ++C
        معرفی متغیرهای مرجع در زبان برنامه‌نویسی ++C و آشنایی با مهمترین کاربردهای آنها
        آشنایی با حلقه‌های تکرار در زبان برنامه‌نویسی ++C و دستورات کنترلی مورد استفاده در آن
        آموزش استفاده از آرایه‌ی پویای دو بعدی در زبان ++C
        پنج نکته‌ی آموزنده در مورد برنامه‌نویسی به زبان برنامه‌نویسی ++C
        آشنایی با مفهوم و عملکرد اشاره‌گرها در زبان برنامه‌نویسی ++C و ارائه مثالهایی از کاربرد آن
        آشنایی با توابع دوست کلاس در زبان برنامه‌نویسی ++C و کاربرد آنها در سربارگذاری عملگرها
        آشنایی با قالب‌ها به عنوان یکی از امکانات متمایز ++C از C
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left