فایل سرآیند algorithm

معرفی فایل سرآیند 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) {

    return (x % 2);

}

  

void print(int x) {

    cout << x << " ";

}

  

int main()

{

    const int len = 5;

    int arr1[] = {7, 3, 4, 2, 3};

    array<int, len> arr2{{8, 2, 0, 4, 6} };

    list<int> arr3(arr2.begin(), arr2.end());

    shuffle(arr2.begin(), arr2.end(), default_random_engine(time(NULL)));

    cout << "arr2 after shuffle: ";

    for_each(arr2.begin(), arr2.end(), print);

    // arr2 after shuffle: 0 8 2 4 6

    cout << endl;

    if(all_of(arr1, arr1 + len, isOdd))

        cout << "All the elements of arr1 are odd." << endl;

    else

        cout << "At least one of the elements in arr1 is not odd." << endl;

    // At least one of the elements in arr1 is not odd.

    if(any_of(arr1, arr1 + len, isOdd))

        cout << "At least one of the elements in arr1 is odd." << endl;

    else

        cout << "All the elements of arr1 are even." << endl;

    //  At least one of the elements in arr1 is odd.

    if(none_of(arr2.begin(), arr2.end(),isOdd))

        cout << "All the elements of arr2 are even." << endl;

    else

        cout << "At least one of the elements in arr2 is odd." << endl;

      //  All the elements of arr2 are even.

    auto v1 = find_if(arr1, arr1 + len, isOdd);

    cout << "The first odd element in arr1 is " << *v1 << "." << endl;

    // The first odd element in arr1 is 7.

    auto v2 = find_first_of(arr1, arr1 + len, arr2.begin(), arr2.end());

    cout << "The first element of arr2 in arr1 is " << *v2 << "." << endl;

    //  The first element of arr2 in arr1 is 4.

    cout << "#3 in arr1 is " << count(arr1, arr1 + len, 3) << "." << endl;

    //  #3 in arr1 is 2.

    cout << "#Odd_Numbers in arr1 is " << count_if(arr1, arr1 + len, isOdd) << "." << endl;

    // #Odd_Numbers in arr1 is 3.

    if(is_permutation(arr1, arr1 + len, arr3.begin()))

        cout << "arr3 is a permutation of arr1." << endl;

    else

        cout << "arr3 is not a permutation of arr1." << endl;

    // arr3 is not a permutation of arr1.

    if(is_permutation(arr3.begin(), arr3.end(), arr2.begin()))

        cout << "arr3 is a permutation of arr2." << endl;

    else

        cout << "arr3 is not a permutation of arr2." << endl;

    //  arr3 is a permutation of arr2.

    cout << "arr3 before copy: ";

    for_each(arr3.begin(), arr3.end(), print);

    //  arr3 before copy: 8 2 0 4 6

    copy(arr1 + 1, arr1 + 3, arr3.begin());

    cout << endl << "arr3 after copy: ";

    for_each(arr3.begin(), arr3.end(), print);

    // arr3 after copy: 3 4 0 4 6

    cout << endl;

    swap(*arr1, *(arr1+1));

    cout << "arr3 after swap: ";

    for_each(arr3.begin(), arr3.end(), print);

    // arr3 after swap: 3 4 0 4 6

    cout << endl;

    replace(arr3.begin(), arr3.end(), 4, 7);

    cout << "arr3 after replace: ";

    for_each(arr3.begin(), arr3.end(), print);

    // arr3 after replace: 3 7 0 7 6

    cout << endl;

    fill(arr1, arr1 + 3, 5);

    cout << "arr1 after fill: ";

    for_each(arr3.begin(), arr3.end(), print);

    // arr1 after fill: 3 7 0 7 6

    cout << endl;

    auto newEnd1 = unique(arr3.begin(), arr3.end());

    cout << "arr3 after unique: ";

    for_each(arr3.begin(), newEnd1, print);

    // arr3 after unique: 3 7 0 7 6

    cout << endl;

    auto newEnd2 = remove(arr3.begin(), newEnd1, 7);

    cout << "arr3 after remove 7: ";

    for_each(arr3.begin(), newEnd2 , print);

    // arr3 after remove 7: 3 0 6

    cout << endl;

    cout << "arr2 before reverse: ";

    for_each(arr2.begin(), arr2.end(), print);

    // arr2 before reverse: 0 8 2 4 6

    cout << endl;

    reverse(arr2.begin(), arr2.end());

    cout << "arr2 after reverse: ";

    for_each(arr2.begin(), arr2.end(), print);

    // arr2 after reverse: 6 4 2 8 0

    cout << endl;

    sort(arr2.begin(), arr2.end());

    cout << "arr2 after sort: ";

    for_each(arr2.begin(), arr2.end(), print);

    // arr2 after sort: 0 2 4 6 8

    cout << endl;

    cout << "Min(arr1) = " << *min_element(arr1, arr1 + len) << endl;

    // Min(arr1) = 2

    cout << "Max(arr1) = " << *max_element(arr1, arr1 + len) << endl;

    // Max(arr1) = 5

    return 0;

}


تا کنون ۶ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spcv4jb

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• ali
۱۹ آبان ۱۳۹۹، ساعت ۱۲:۲۷

سلام میخواستم یه راهنمایی ازتون بخوام که تو مسابقات ICPC دقیقا از چه هدری میشه استفاده کرد؟