এই আর্টিকেলে আমরা C++ STL-এ নন-ইনক্রিজিং অর্ডারে সর্ট করা একটি অ্যারে বা ভেক্টরের জন্য vector::upper_bound() এবং vector::lower_bound() ফাংশন সম্পর্কে আলোচনা করব।
ভেক্টর হলো ডাইনামিক অ্যারের মতো; যখন কোনো ভ্যালু কন্টেইনারে ইনসার্ট বা রিমুভ করা হয়, তবে এটি অটোমেটিক্যালি নিজের সাইজ পরিবর্তন করতে পারে।
একটি ভেক্টরে, লোয়ার বাউন্ড সেই প্রথম এলিমেন্টের तरफ ইটেরেটর রিটার্ন করে যা দেওয়া ভ্যালুর চেয়ে কম নয় (অর্থাৎ ওই ভ্যালুর চেয়ে বড় বা সমান)। আপার বাউন্ড সে এলিমেন্টের দিকে ইটেরেটর রিটার্ন করে যা দেওয়া ভ্যালুর চেয়ে স্ট্রিক্টলি ছোট (non-increasing order-এ)।
ইনপুট
30 30 30 20 20 20 10 10
আউটপুট
Lower bound of 20 = 3 Upper bound of 20 = 6
ইনপুট
9 9 8 8 8 7 7 7 6 6 6 6
আউটপুট
Lower bound of 7 = 5 Upper bound of 7 = 8
রিটার্ন ভ্যালু
এটি রেঞ্জের প্রথম এলিমেন্টের দিকে একটি ইটেরেটর এবং রেঞ্জের শেষ এলিমেন্টের দিকে একটি ইটেরেটর রিটার্ন করে।
অনুসরণযোগ্য পদ্ধতি
- প্রথমে ভেক্টরটি ইনিশিয়ালাইজ করুন।
- তারপর ভেক্টরের এলিমেন্টগুলো নন-ইনক্রিজিং অর্ডারে সর্ট করুন।
- তারপর এর লোয়ার বাউন্ড খুঁজুন।
- তারপর এর আপার বাউন্ড খুঁজুন।
- শেষে দুটি বাউন্ড প্রিন্ট করুন।
উপরোক্ত পদ্ধতি ব্যবহার করে যেকোনো ভেক্টরের লোয়ার ও আপার বাউন্ড বের করা যায়। বাউন্ড খুঁজতে হলে ভেক্টরটি সর্ট করা আবশ্যক; অনসর্টেড ভেক্টরের বাউন্ড বের করা যায় না।
উদাহরণ ১
// C++ প্রোগ্রাম লোয়ার বাউন্ড ও আপার বাউন্ড প্রদর্শন করার জন্য
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int vect[] = {13, 13, 13, 16, 16, 16, 17, 17, 17, 17, 18, 18};
vector<int> v(vect, vect + 12);
sort(v.begin(), v.end(), greater<int>());
cout << "\n Sorted Vector: ";
for (auto i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
vector<int>::iterator low, up;
low = lower_bound(v.begin(), v.end(), 17, greater<int>());
up = upper_bound(v.begin(), v.end(), 17, greater<int>());
cout << "\n Lower bound: " << (low - v.begin()) << "\n";
cout << " Upper bound: " << (up - v.begin()) << "\n";
return 0;
}আউটপুট
Sorted Vector: 18 18 17 17 17 17 16 16 16 13 13 13 Lower bound = 2 Upper bound = 6
উদাহরণ ২
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int vect[] = {5, 5, 5, 5, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10};
vector<int> v(vect, vect + 16);
sort(v.begin(), v.end(), greater<int>());
cout << "\n Sorted Vector: ";
for (auto i = v.begin(); i != v.end(); ++i)
cout << *i << " ";
vector<int>::iterator low, up;
low = lower_bound(v.begin(), v.end(), 8, greater<int>());
up = upper_bound(v.begin(), v.end(), 8, greater<int>());
cout << "\n Lower bound: " << (low - v.begin()) << "\n";
cout << " Upper bound: " << (up - v.begin()) << "\n";
return 0;
}আউটপুট
Sorted Vector: 10 10 9 9 9 8 8 8 8 7 7 7 5 5 5 5 Lower bound = 5 Upper bound = 9
