মডিউল ২৩-৭ঃ কিভাবে STL set কাজ করে

এবার আমরা দেখব সি++ এর সেট। সেট বিহাইন্ড দ্যা সিন ব্যালেন্সড বাইনারি সার্চ ট্রি ফলো করে। ব্যালেন্সড ট্রি হলো যেই ট্রি এর লেফট সাবট্রি এবং রাইট সাবট্রি এর মধ্যে হাইট ডিফারেন্স ১ এর বেশি থাকে না। সেটে যেকোন ডাটা টাইপের ভেলু রাখা যায়। সেটে ভেলু ইনসার্ট করলে সেট নিজে থেকেই ভেলুগুলো সর্ট করে দেয় এবং ডুপ্লিকেট রিমুভ করে দেয় কারন সেট বিহাইন্ড দ্যা সিন ব্যালেন্সড বাইনারি সার্চ ট্রি ফলো করে। এবং এক্ষেত্রে সবগুলো অপারেশন এর কমপ্লেক্সিটি O(logN)

আমাদের এতদিন কখনো ডুপ্লিকেট রিমুভ করার প্রয়োজন হলে আমরা শুরুতে ফ্রিকুয়েন্সি কাউন্ট করতাম, তারপর ফ্রিকুয়েন্সি ১ এর বেশি হলে সেগুলো রিমুভ করতাম। এখন আমাদের কখনো ডুপ্লিকেট রিমুভ করার কোন প্রবলেম আসলে আমরা চোখ বন্ধ করে সেট ব্যবহার করে ফেলতে পারব। সেটে কোন ভেলু রাখা হলে সেট এসেন্ডিং অর্ডারে সর্ট করে স্টোর করে। এক্ষেত্রে লক্ষণীয় হচ্ছে, আমরা চাইলেও সেটকে রিভার্স করে ডিসেন্ডিং অর্ডারে সর্ট করতে পারব না। সেট রিভার্স করা যায় না। আমাদের যদি খুব বেশি প্রয়োজন হয় তখন আমরা সেট থেকে ভেলু একটি ভেক্টরে রেখে তারপর সেটিকে রিভার্স করে দিতে পারব।

#include <bits/stdc++.h>
using namespace std;
int main()
{
    set<int> s;          // একটি সেট নেওয়া হচ্ছে। 
    int n;
    cin >> n; 
    while (n--)
    {
        int x;
        cin >> x;          // সংখ্যা ইনপুট নিয়ে 
        s.insert(x);       // সেটে ইনসার্ট করা হচ্ছে। যার কমপ্লেক্সিটি O(logN)। 
    }
    
    for (auto it = s.begin(); it != s.end(); it++)  // সেটের শুরু থেকে শেষ পর্যন্ত লুপ চালিয়ে
    {
         cout << *it << endl;      // এলিমেন্ট প্রিন্ট করা হচ্ছে।
    }
    return 0;
}

কোডটি রান করে কিছু ইনপুট দিয়ে দেখব সেট এসেন্ডিং অর্ডারে সর্ট করে এবং ডুপ্লিকেট রিমুভ করে প্রিন্ট করছে।