====== الگوریتم ها ======
همانند دربرگیرنده ها در کتابخانه $STL$ تعدادی از الگوریتم های پرکابرد نوشته شده است. برای استفاده از آن ها ابتدا باید کتابخانه زیر را $include$ کنید.
#include
حال به بررسی برخی از آنان میپردازیم
===== $sort$ =====
با استفاده از این تابع میتوانیم عناصر یک آرایه یا یک $vector$ را مرتب کنیم. توجه کنید که برای اینکه بتوان آن ها را مرتب کرد نیاز است که **کوچکتر بودن** برای آن $type$ تعریف شده باشد. برای $type$ های پیشفرض این رابطه تعریف شده است. همچنین میتوان از تابعی دلخواه برای مقایسه استفاده کرد که آن را باید به عنوان پارامتر سوم بدهیم.
sort(startPointer,endPointer) // endPointer is not included
sort(startPointer,endPointer,compareFunction)
توجه کنید که خود $endPointer$ شامل بازه مرتب سازی نمیشود.
به عنوان مثال :
int A[10];
vector V;
sort(A+2,A+5); // sorts the element number 2 to element number 4 (2 and 4 included)
sort(V.begin(),V.end()) // sorts All of Vector v
حال فرض کنید میخواهیم تابعی بنویسیم که به وسیله عناصر را صعودی مرتب کنیم :
bool cmp(int a,int b){
return (a>b);
}
sort(V.begin(),V.end(),cmp);
===== $fill$ =====
این تابع یک بازه از آرایه یا $vector$ را با مقدار داده شده پر میکند. معمولا برای $0$ کردن یا مقدار اولیه دادن به آرایه یا $vector$ کاربرد دارد.
// Format
fill(startPointer,endPointer,value);
// Example
fill(A,A+n,0);
===== $reverse$ =====
این تابع یک بازه از آرایه یا $vector$ را برعکس میکند.
// Format
reverse(startPointer,endPointer);
// Example
reverse(S.begin(),S.end());
===== $unique$ =====
این تابع روی یک بازه مرتب شده اعمال شده و عناصر آن را $unique$ میکند یعنی از هر عنصر یکی را نگه داشته و باقی تکرار هارا در انتها میگذارد و اشاره گر به انتهای عناصر یکتا را بازمیگردند. توجه کنید که عنصری که این اشاره گر به آن اشاره میکند اولین عنصر بعد از بازه یکتا شده است.
// Format
unique(startPointer,endPointer);
// Example
vector v;
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
=====$bound$ $lower/upper$=====
با استفاده ازین تابع میتوانید روی یک بازه $sort$ شده $binarysearch$ انجام داده و به دنبال مکان یک مقدار خاص بگردید.
* عملکرد $lowerBound$ : اشاره گر به اولین جایی که از مقدار داده شده **بیشتر یا مساوی** است.
* عملکرد $upperBound$ : اشاره گر به اولین جایی که از مقدار داده شده **بیشتر** است.
// Format
lower_bound(startPointer,endPointer,value);
upper_bound(startPointer,endPointer,value);
// Example
lower_bound(v.begin(),v.end(),2);
===== $permutation$ $next/prev$ =====
با استفاده از این تابع میتوانید جایگشت بعدی یا قبلی یک بازه را حساب کنید. این تابع یک مقدار $boolean$ برمیگرداند که در صورتی که برای $nextPermutation$ روی بزرگترین جایگشت اعمال شود $false$ و در غیر اینصورت $true$ است و برای $prevPermutation$ در صورتی که روی کوچکترین جایگشت اعمال شود $false$ و در غیر ایصورت $true$ است.
// Format
next_permutation(startPointer,endPointer);
prev_permutation(startPointer,endPointer);
===== مثال =====
میخواهیم برنامه ای بنویسیم که تمام جایگشت ها ${1,2,...n}$ را چاپ کند
#include
#include
#include
using namespace std;
const int MAX_N=100*1000;
void show(const vector& V){
for(int i=0;i<(int)V.size();i++)
cout< P;
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i++)
P.push_back(i);
sort(P.begin(),P.end()); // not needed here but remember to do it !
do{
show(P);
}while(next_permutation(P.begin(),P.end()));
return 0;
}