الگوریتم های STL

low_bound و upper_bound توابع جستجوی باینری داخلی هستند.

low_bound - تابعی که در زمان لگاریتمی کوچکترین عنصر را در یک آرایه مرتب شده پیدا می کند که بزرگتر یا مساوی با مقدار داده شده k است.
مرزهای آرایه و مقدار k را به عنوان آرگومان می گیرد.
اگر چنین عنصری وجود نداشته باشد، یک تکرارکننده را به عنصر پیدا شده برمی‌گرداند یا به انتهای آرایه (شامل نمی‌شود).
می‌توانید اطلاعات بیشتری را در اسناد بخوانید.

upper_bound - تابعی است که در زمان لگاریتمی در یک آرایه مرتب شده کوچکترین عنصر را پیدا می کند که به شدت بزرگتر از مقدار داده شده k است.
مرزهای آرایه و مقدار k را به عنوان آرگومان می گیرد.
اگر چنین عنصری وجود نداشته باشد، یک تکرارکننده را به عنصر پیدا شده برمی‌گرداند یا به انتهای آرایه (شامل نمی‌شود).
می‌توانید اطلاعات بیشتری را در اسناد بخوانید.

شایان ذکر است که استفاده از این توابع در یک مجموعه یا چند مجموعه در زمان لگاریتمی به دلیل عدم وجود تکرارکننده در مجموعه‌های دسترسی تصادفی فوق کار نمی‌کند.
با این حال، این مجموعه ها دارای روش های داخلی متناظر هستند (یعنی باید از آنها "از طریق یک نقطه" استفاده کنید).

مثال‌ها:
  بردار a = { 0, 1, 3, 5, 7 }; vector::iterator it; it = low_bound(a.begin(), a.end(), 4); // *it == 5 it = low_bound(a.begin(), a.end(), 5); // *it == 5 it = low_bound(a.begin(), a.end(), 8); // it == a.end() it = upper_bound(a.begin(), a.end(), 4); // *it == 5 it = upper_bound(a.begin(), a.end(), 5); // *it == 7 it = upper_bound(a.begin(), a.end(), -1); // *it == 0 // با کم کردن تکرار کننده ها، می توانید شاخص عنصر پیدا شده را بدست آورید int ind = low_bound(a.begin(), a.end(), 4) - a.begin(); // ind == 3 // نیاز به استفاده از متدها به جای توابع برای مجموعه ها و مجموعه های مشابه است set s{ 1, 3, 5 }; set::iterator sit; sit = s.lower_bound(3); // *نشین == 3 sit = s.upper_bound(3); // *نشین == 5  

منحصر به فرد - تابعی که تمام دنباله های عناصر متوالی یکسان را در یک زمان خطی فشرده می کند.
به عنوان یک آرگومان، از مرزهای آرایه عبور می کند که در آن باید فشرده سازی اعمال شود.
یک تکرار کننده به انتهای جدید (غیر شامل) آرایه برگردانده می شود. شما باید مراقب عناصر بعد از پایان جدید اما قبل از قدیمی باشید، زیرا آنها مقدار نامشخصی خواهند داشت.
می‌توانید در اسناد بیشتر بخوانید.

اگر از این تابع در یک بردار استفاده می کنید، تغییر اندازه با استفاده از نتیجه برگشتی راحت است (در ادامه در مورد آن بیشتر توضیح می دهیم).

مثال‌ها:
  بردار a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; منحصر به فرد(a.begin()، a.end()); // a = [3، 2، 3، 1، 4، 5، ?، ?، ?، ?، ?] // استفاده از تابع منحصر به فرد برای انجام راحت است // آرایه کمکی برای فشرده سازی مختصات a = { 235، 10، 41، 10، 41، 41، 235، 500، 500 }; sort(a.begin()، a.end()); // a = [10، 10، 41، 41، 41، 235، 235، 500، 500] a.resize(unique(a.begin()، a.end()) - a.begin()); // a = [10، 41، 235، 500]  

merge - تابعی که دو آرایه مرتب شده را ادغام می کند، یعنی در زمان خطی یک آرایه مرتب شده دریافت می کند که از عناصر آرایه اول و دوم تشکیل شده است.
این 5 آرگومان نیاز دارد: دو کران برای هر آرایه و کران سمت چپ مقصد (جایی که عناصر آرایه حاصل قرار می گیرند).
جزئیات بیشتر را می‌توانید در اسناد پیدا کنید.

مثال ها: // آرایه های منبع باید مرتب شوند بردار a = { 1, 3, 5, 7 }; بردار b = { 2, 4, 6 }; // باید مقصد به اندازه کافی بزرگ باشد vector c(7); merge(a.begin()، a.end()، b.begin()، b.end()، c.begin()); // c = [1، 2، 3، 4، 5، 6، 7] // عناصر را می توان تکرار کرد a = {1، 2، 4، 4}؛ b = { 2، 3، 3، 3، 4، 4 }; c.resize(10); merge(a.begin()، a.end()، b.begin()، b.end()، c.begin()); // c = [1، 2، 2، 3، 3، 3، 4، 4، 4، 4]  این تابع در زمینه مرتب سازی ادغام بسیار مفید است.

nth_element تابعی است که به شما امکان می دهد عنصر n را در یک آرایه به ترتیب مرتب شده در زمان خطی پیدا کنید.
این تابع انتهای سمت چپ آرایه، یک تکرار کننده به موقعیتی که مقدار آن به ترتیب مرتب شده باید پیدا شود و انتهای سمت راست آرایه را می گیرد.
پس از اعمال تابع، مقدار مورد نیاز در مکانی که توسط تکرار کننده مشخص شده است قرار می گیرد، در حالی که مقادیر باقی مانده نظم آشفته ای به دست می آورند، اما در سمت چپ n ام مقادیری بیشتر از آن وجود نخواهد داشت و به سمت راست نه کمتر یعنی باید فهمید که این تابع ترتیب اصلی عناصر را از بین می برد.
می توانید اطلاعات بیشتری را در اسناد (https://www.cplusplus.com/reference/algorithm/nth_element/) بخوانید.

مثال: بردار a = { 4، 0، 3، 9، 2، 1، 8، 5، 6، 7 }; // به دنبال عنصر در شاخص 4 بگردید // به ترتیب آرگومان ها دقت کنید nth_element(a.begin(), a.begin() + 4, a.end()); // a = [#، #، #، #، 4، $، $، $، $، $] // که در آن # <= 4 و 4 <= $  

جایگشتی به طول n مجموعه ای مرتب شده بدون تکرار اعداد 1، 2، ...، n است. برای مثال، [3، 1، 2] و [5، 4، 3، 2، 1] جایگشت هستند، اما [1، 2، 1، 3] و [1، 2، 4] جایگشت نیستند.

اگر کار به این واقعیت کاهش یابد که لازم است روی همه جایگشت‌های طول n تکرار شود، می‌توانید از مکانیزم مناسبی در C ++ استفاده کنید که به آن "next_permutation" می‌گویند.

می‌توانید در مستندات اطلاعات بیشتری در مورد آن بخوانید، اما نکته اینجاست که این تابع آرایه ارسال شده را تغییر می‌دهد. به جایگشت بعدی به ترتیب واژگانی (که عموماً مشخص است و نام آن مشخص است).

برای استفاده از next_permutation، باید کتابخانه الگوریتم را اضافه کنید (یعنی در ابتدای برنامه #include <algorithm> بنویسید)

مثال ها: vector arr; arr = { 1, 2, 3 }; // آرایه [1، 2، 3] است next_permutation(arr.begin()، arr.end()); // کل آرایه را به تابع منتقل کنید // آرایه اکنون [1، 3، 2] است arr = { 2, 3, 1 }; // آرایه [2، 3، 1] است next_permutation(arr.begin()، arr.end()); // کل آرایه را به تابع منتقل کنید // آرایه اکنون [3، 1، 2] است next_permutation(arr.begin() + 1, arr.begin() + 3); // می توان یک تابع را به بخشی از یک آرایه اعمال کرد، اما در عمل به ندرت به این مورد نیاز است // آرایه اکنون [3، 2، 1] است
در این حالت، تابع دارای یک مقدار بازگشتی بولی است که اگر جایگشت بعدی ایجاد شده باشد درست است و اگر جایگشت بعدی وجود نداشته باشد نادرست است (موردی که حداکثر جایگشت به ترتیب واژگانی به تابع منتقل می شود).
این امکان استفاده از تابع را در یک حلقه فراهم می کند، که به ما امکان می دهد روی همه جایگشت ها به طور همزمان تکرار کنیم. به دلیل نمایه سازی 0، در عمل اغلب کار با جایگشت اعداد از 0 تا n - 1 راحت تر است، اگرچه یک جایگشت به طور رسمی شامل اعداد 1 تا n است. اما خوشبختانه، این منجر به همپوشانی اضافی در کد نمی شود، زیرا تابع next_permutation با جایگشت های 0-index شده سازگار است (و حتی عناصر تکراری در یک آرایه، اما شما می توانید بیشتر به تنهایی بیابید).

به طور کلی، کد تکرار روی همه جایگشت ها به این صورت است:   intn; // اندازه جایگشت vectorperm(n); // perm مخفف "جایگشت" است، یعنی. "جایگزینی" برای (int i = 0; i < n; i++) perm[i] = i; // جایگشت اولیه 0، 1، ...، n - 1 را مقداردهی کنید انجام دادن { // در داخل حلقه، جایگشت فعلی را پردازش می کنیم } while (next_permutation(perm.begin()، perm.end())); // اگر جایگشت بعدی وجود ندارد، حلقه را پایان دهید

این کد در O(n! * f(n)) اجرا می شود، که در آن f(n) زمانی است که برای پردازش یک جایگشت خاص طول می کشد.