الگوریتم (سی++)

الگوریتم‌های استاندارد سی++ توابعی همه منظوره هستند که یک یا چند بازه را به شکل Iterator دریافت می‌کنند و عملیات‌های متفاوتی مثل مرتب‌سازی، جستجو و … را بر روی آن بازه‌ها انجام می‌دهند.

در کتابخانه استاندارد سی++ در سرآیند <algorithm.h> حدود ۸۰ الگوریتم متفاوت وجود دارد.

 دسته‌بندی الگوریتم‌ها 
 الگوریتم‌های متوالی که تغییری در ورودی نمی‌دهند 
این دسته از الگوریتم‌های یک یا چند iterator را به عنوان ورودی دریافت می‌کنند و بدون تغییر iteratorهای ورودی صرفاً یک مقدار را برمی‌گردانند.
مثل std::find و std::search و std::count و std::for_each
مثال:
# include <iostream>
# include <vector>

int main()
{
  std::vector<int> arr = { 2, 5, 7, 2, 3, 4, 4, 5, 2 };

  std::cout << std::count(arr.begin(), arr.end(), 2); // تعداد ۲ها یعنی ۳ چاپ می‌شود
}

 الگوریتم‌های متوالی تغییر دهنده ورودی 
این دسته از الگوریتم‌ها یک یا چند بازه را به شکل Iterator دریافت می‌کنند و آن‌ها را بسته به نوع الگوریتم تغییر می‌دهند. مثل std::remove , std::reverse , std::fill ,...
مثال :
# include <iostream>
# include <string>
# include <vector>

int main()
{
  std::string str = "salam";

  std::reverse(str.begin(), str.end()); // برعکس کردن رشته

  std::cout << str; // "malas"
}

 الگوریتم‌های مرتب‌سازی 
از این الگوریتم‌ها برای مرتب‌سازی یا بررسی مرتب بودن یک بازه خاص استفاده می‌شود.چک کردن مرتب بودن، مثل std::sort, std::stable_sort , std::is_sorted
مثال :
# include <iostream>
# include <algorithm>
# include <vector>

int main()
{
  std::vector<int> arr = { 1, 5, 2, 3, 7 };

  std::cout << std::boolalpha << std::is_sorted(arr.begin(), arr.end()) << '\n'; // false چاپ می‌شود

  std::sort(arr.begin(), arr.end()); // مرتب‌سازی

  std::cout << std::boolalpha << std::is_sorted(arr.begin(), arr.end()) << '\n'; // به دلیل مرتب آرایه true نوشته می‌شود

}

 الگوریتم‌های مربوط به هیپ 
از این الگوریتم‌ها برای اعمال مثل ساختن هیپ و چک کردن این که آیا بازه مورد نظر heap است یا خیر و همچنین مرتب‌سازی هرمی (heap sort) استفاده می‌شود.
مثال :
# include <iostream>
# include <algorithm>
# include <vector>

int main()
{
  std::vector<int> arr = { 1, 5, 2, 3, 7 };
  std::make_heap(arr.begin(), arr.end()); // ایجاد هیپ
  std::sort_heap(arr.begin(), arr.end()); // مرتب‌سازی هرمی
  for (auto i : arr) // چاپ آرایه
    std::cout << i << ' ';
}

 جستجوی دودویی 
از این الگوریتم‌ها برای جستجوی دودویی در یک آٰرایه مرتب(std::binary_search) یا پیدا کردن اولین عنصر بزرگتر (std::lower_bound) یا اولین عنصر کوچیکتر(std::upper_bound) از یک عنصر خاص استفاده می‌شود.
مثال :
# include <iostream>
# include <algorithm>
# include <vector>

int main()
{
  std::vector<int> arr = { 1, 2, 4, 6, 7 };
  std::cout << *std::lower_bound(arr.begin(), arr.end(), 3); // اولین عنصر بزرگتر از ۳ یعنی ۴ چاپ می‌شود
}

 الگوریتم‌های تقسیم 
از این الگوریتم‌ها برای تقسیم یک بازه خاص به ۲ گروه متفاوت استفاده می‌شود مثل: std::partition_copy , std::partition

 الگوریتم‌های پیدا کردن بیشترین و کمترین مقدار 
الگوریتم‌های مربوط به پیدا کردن بیشترین و کمترین مقدار در یک بازه خاص مثل std::min , std::max , std::lexicographical_compare

 الگوریتم‌های مربوط به مجموعه‌ها 
الگوریتم‌هایی هستند که وظیفه اشان عملیات‌هایی مثل پیداکردن تفاوت ۲ مجموعه (std::set_difference) یا ترکیب ۲ مجموعه(std::merge) و… هست.

 الگوریتم‌های عددی 
الگوریتم‌هایی که برای محاسبات عددی روی یک بازه خاص استفاده می‌شوند مثلاً برای جمع زدن عناصر یک بازه از std::accumulate استفاده می‌شود یا برای پر کردن از std::iota استفاده می‌شود.

 منابع 

https://en.wikipedia.org/wiki/Algorithm_(C++)

https://web.archive.org/web/20141125120542/http://www.cplusplus.com/reference/algorithm/

http://en.cppreference.com/w/cpp/algorithm

 برای مطالعهٔ بیشتر 
http://stackoverflow.com/questions/662845/why-is-stdfor-each-a-non-modifying-sequence-operation

رده:کتابخانه استاندارد سی++