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

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

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

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

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

این دسته از الگوریتم‌های یک یا چند 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"
}

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

از این الگوریتم‌ها برای مرتب‌سازی یا بررسی مرتب بودن یک بازه خاص استفاده می‌شود.^[2] مثل 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 استفاده می‌شود.

منابع

1. Stroustrup, Bjarne (2012-12-09). "The C++ Programming Language (Fourth Edition)". Amazon Product Page.
2. چک کردن مرتب بودن،

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