الگوریتم‌های جادویی در کتابخانه‌ی STL در ++C

در این قسمت از آموزش کتابخانه‌ی STL‌ در زبان ++C به معرفی الگوریتم‌های جادویی STL خواهیم پرداخت.

برای همه‌ی آن‌هایی که به دنبال برتری در برنامه‌نویسی رقابتی هستند، تنها داشتن دانش درمورد نگه‌دارنده‌های STL  کافی نیست و باید بدانند کل STL چه چیزی برای ارائه دارد. STL اقیانوسی از الگوریتم دارد، تمامی توابع در کتابخانه‌ی < algorithm > قرار دارد، در اینجا می‌توانید به آن‌ها دسترسی داشته باشید.

برخی از کاربردی‌ترین الگوریتم‌ها در بردار‌ها و مفید‌ترین‌ ‌‌آن‌ها در برنامه‌نویسی رقابتی در زیر آمده‌اند:

الگوریتم‌های بدون دستکاری

• sort(first_iterator, last_iterator): برای مرتب‌سازی بردار
• reverse(first_iterator, last_iterator): برای معکوس کردن یک بردار
• max_element (first_iterator, last_iterator)*:‌ برای پیدا کردن بزرگترین ععنصر در بردار
• min_element (first_iterator, last_iterator)*: برای پیدا‌کردن کوچترین عنصر در بردار
• accumulate(first_iterator, last_iterator, initial value of sum): عملیات جمع را روی عناصر بردار انجام می‌دهد

// A C++ program to demonstrate working of sort(),
// reverse()
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric> //For accumulate operation
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {10, 20, 5, 23 ,42 , 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    cout << "Vector is: ";
    for (int i=0; i<n; i++)
        cout << vect[i] << " ";
 
    // Sorting the Vector in Ascending order
    sort(vect.begin(), vect.end());
 
    cout << "\nVector after sorting is: ";
    for (int i=0; i<n; i++)
       cout << vect[i] << " ";
 
    // Reversing the Vector
    reverse(vect.begin(), vect.end());
 
    cout << "\nVector after reversing is: ";
    for (int i=0; i<6; i++)
        cout << vect[i] << " ";
 
    cout << "\nMaximum element of vector is: ";
    cout << *max_element(vect.begin(), vect.end());
 
    cout << "\nMinimum element of vector is: ";
    cout << *min_element(vect.begin(), vect.end());
 
    // Starting the summation from 0
    cout << "\nThe summation of vector elements is: ";
    cout << accumulate(vect.begin(), vect.end(), 0);
 
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

Vector is: 10 20 5 23 42 15 
Vector after sorting is: 5 10 15 20 23 42 
Vector after reversing is: 42 23 20 15 10 5 
Maximum element of vector is: 42
Minimum element of vector is: 5
The summation of vector elements is: 115

• count(first_iterator, last_iterator,x): تعداد موارد x در بردار مشخص می‌کند.
• find(first_iterator, last_iterator, x): یک پیمایشگر به اولین مورد از x در بردار برمی‌گرداند و اگر عنصر در بردار وجود نداشت، به آخرین آدرس از بردار ((name_of_vector).end()) اشاره می‌کند.

// C++ program to demonstrate working of count()
// and find()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {10, 20, 5, 23 ,42, 20, 15};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    cout << "Occurrences of 20 in vector : ";
 
    // Counts the occurrences of 20 from 1st to
    // last element
    cout << count(vect.begin(), vect.end(), 20);
 
    // find() returns iterator to last address if
    // element not present
    find(vect.begin(), vect.end(),5) != vect.end()?
                         cout << "\nElement found":
                     cout << "\nElement not found";
 
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

Occurrences of 20 in vector : 2
Element found

• binary_search(first_iterator, last_iterator, x): بررسی اینکه‌ آیا x در بردار مرتب‌شده وجود دارد یا نه.
• lower_bound(first_iterator, last_iterator, x): یک پیمایشکر که به اولین عنصر در طیف [first,last) اشاره می‌کند که مقداری کوچکتر از x ندارد را برمی‌گرداند.
• upper_bound(first_iterator, last_iterator, x): یک پیمایشگر که به اولین عنصر در طیف [first,last) اشاره می‌کند که یک مقدار بزرگتر از x دارد را برمی‌گرداند.

// C++ program to demonstrate working of lower_bound()
// and upper_bound().
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {5, 10, 15, 20, 20, 23, 42, 45};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    // Sort the array to make sure that lower_bound()
    // and upper_bound() work.
    sort(vect.begin(), vect.end());
 
    // Returns the first occurrence of 20
    auto q = lower_bound(vect.begin(), vect.end(), 20);
 
    // Returns the last occurrence of 20
    auto p = upper_bound(vect.begin(), vect.end(), 20);
 
    cout << "The lower bound is at position: ";
    cout << q-vect.begin() << endl;
 
    cout << "The upper bound is at position: ";
    cout << p-vect.begin() << endl;
 
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

The lower bound is at position: 3
The upper bound is at position: 5

برخی از الگوریتم‌های دستکاری

• arr.erase(position to be deleted): این الگوریتم، عنصر انتخاب‌شده در بردار را پاک می‌کند و  انتقال و تغییر‌اندازه عناصر بردار را به این ترتیب انجام می‌دهد.
• arr.erase(unique(arr.begin(),arr.end()),arr.end()): این الگوریتم، موارد تکراری در بردار مرتب‌شده را در تنها یک خط پاک می‌کند.

// C++ program to demonstrate working of erase()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {5, 10, 15, 20, 20, 23, 42, 45};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    cout << "Vector is :";
    for (int i=0; i<6; i++)
        cout << vect[i]<<" ";
 
    // Delete second element of vector
    vect.erase(vect.begin()+1);
 
    cout << "\nVector after erasing the element: ";
    for (int i=0; i<vect.size(); i++)
        cout << vect[i] << " ";
 
    // sorting to enable use of unique()
    sort(vect.begin(), vect.end());
 
    cout << "\nVector before removing duplicate "
             " occurrences: ";
    for (int i=0; i<vect.size(); i++)
        cout << vect[i] << " ";
 
    // Deletes the duplicate occurrences
    vect.erase(unique(vect.begin(),vect.end()),vect.end());
 
    cout << "\nVector after deleting duplicates: ";
    for (int i=0; i< vect.size(); i++)
        cout << vect[i] << " ";
 
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

Vector is :5 10 15 20 20 23 
Vector after erasing the element: 5 15 20 20 23 
Vector before removing duplicate  occurrences: 5 15 20 20 23 
Vector after deleting duplicates: 5 15 20 23 42 45

• next_permutation(first_iterator, last_iterator): این الگوریتم بردار را به جایگزینی بعدی‌اش ویرایش می‌کند.
• prev_permutation(first_iterator, last_iterator): این الگوریتم، بردار را به جایگزینی قبلی‌اش ویرایش می‌کند.

// C++ program to demonstrate working
// of next_permutation()
// and prev_permutation()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {5, 10, 15, 20, 20, 23, 42, 45};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    cout << "Given Vector is:\n";
    for (int i=0; i<n; i++)
        cout << vect[i] << " ";
 
    // modifies vector to its next permutation order
    next_permutation(vect.begin(), vect.end());
    cout << "\nVector after performing
                   next permutation:\n";
    for (int i=0; i<n; i++)
        cout << vect[i] << " ";
 
    prev_permutation(vect.begin(), vect.end());
    cout << "\nVector after performing prev
                               permutation:\n";
    for (int i=0; i<n; i++)
        cout << vect[i] << " ";
 
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

Given Vector is:
5 10 15 20 20 23 42 45 
Vector after performing next permutation:
5 10 15 20 20 23 45 42 
Vector after performing prev permutation:
5 10 15 20 20 23 42 45

• distance(first_iterator,desired_position): این الگوریتم، فاصله‌ی موقعیت مطلوب از اولین پیمایشگر را برمی‌گرداند. این تابع در هنگام پیدا کردن شاخص (index) بسیار مفید است.

// C++ program to demonstrate working of distance()
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    // Initializing vector with array values
    int arr[] = {5, 10, 15, 20, 20, 23, 42, 45};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector<int> vect(arr, arr+n);
 
    // Return distance of first to maximum element
    cout << "Distance between first to max element: ";
    cout << distance(vect.begin(),
                     max_element(vect.begin(), vect.end()));
    return 0;
}

خروجی قطعه‌کُد بالا به این صورت است:

Distance between first to max element: 7

منبع: وب سایت geeksforgeeks