Set

সেট (Set)

সেট বলতে আমরা ইউনিক জিনিস বুঝে থাকি। যেমন আমার কাছে অনেকগুলি চকলেট আছে, ২ টি মার্স, ১০ টি স্নিকার্স, ৭ টি কিটক্যাট, ১৮ টি সাফারী। এখন আমি যদি আমার চকলেট এর সেট করতে চাই, তাহলে
s = { Mars, Snikers, Kitkat, Safari };
এখানে কিন্তু কোন চকলেট কতবার আছে তা জানার কোন দরকার নেই। আমার খালি দরকার আমার কাছে ইউনিক কি আছে। সেট এই কাজটা করে। STL এর সেট ভ্যালুগুলিকে ইউনিক আকার এবং একই সাথে সর্টেড আকারেও রাখে।
#include <set>
int main(){
set < int > s;
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 1 );
s.insert ( 10 );
s.insert ( 10 );
s.insert ( 2 );
s.insert ( 2 );
set < int > :: iterator it; // সেট এর ভ্যালু পয়েন্ট করার জন্য ইটারেটর ডিক্লার
for ( it = s.begin(); it != s.end(); it++ )
cout << *it << endl;  // সেট এর ভ্যালুগুলি প্রিন্ট করলাম
cout << s.size() << endl; //সেট এর সাইজ প্রিন্ট করলাম
}
ধরি আমাকে অনেকগুলি নম্বর দেয়া হল। আমাকে বলতে হবে এর মধ্যে ইউনিক কতটি নম্বর আছে। এর জন্য আমরা খালি সেট এর মধ্যে ইনসার্ট করতে থাকবো এবং সেট এর সাইজটি প্রিন্ট করে দিবো।

Upper_Bound & Lower_Bound

আপার_বাউন্ড এবং লোয়ার_বাউন্ড(upper_bound & lower_bound)

আপার_বাউন্ড এবং লোয়ার_বাউন্ড খুব গুরুত্বপুর্ণ  একটি টপিক। এখন একটি কাহিনী দেখা যাকঃ
আসিফ এবং আসফি ২ যমজ ভাই। তাদের বয়স ধরি ২১। অর্থাৎ তাদের বিয়ের বয়স হয়েছে। তারা আবার খুব হ্যান্ডসাম এবং একই সাথে ব্রিলিয়ান্ট এবং তাদের আগে কোন ফুল-গার্লফ্রেন্ড, হাফ-গার্লফ্রেন্ড কিছুই ছিলনা। কাজেই তাদের বিয়ে করার কথা শুনে মেয়েরা পাগলপ্রায়। এখন আসিফ এর পছন্দ তার থেকে কম বা তার সমান বয়স্ক মেয়েদের (বউ হিসেবে)। অন্যদিকে আসফি এর পছন্দ তার থেকে বেশি বয়স্ক মেয়েদের। এখন ধরি প্রায় ১০০ জন মেয়ে তাদেরকে বিয়ে করার জন্য আগ্রহী। আমাদের কাজ হবে আসিফ এবং আসফি এর জন্য সঠিক বয়সের পাত্রী খুঁজে বের করা। কিভাবে করবো কাজটা? প্রথমেই আমরা পাত্রীদের কে তাদের বয়সের ক্রমানুসারে কম থেকে বেশি আকারে সাজাই। এই সংখ্যাগুলি ধরে একটি ভেক্টর এর মধ্যে রাখি। ধরি আমাদের ভেক্টরটি দেখতে এরকমঃ
int v [ ] = { 10, 12, 14, 21, 21, 21, 21, 30, 32 };
এখন আমরা এই v ভেক্টর এর উপর লোয়ার_বাউন্ড চালালে পাবো ২১, যা ৩ তম ইনডেক্স। আর আপার_বাউন্ড চালালে পাবো ৩০, যা ২১ থেকে ঠিক বড়।CaptureOutput :
lower_bound at position 3
upper_bound at position 6
upper_bound & lower_bound ফাংশন এর জন্য সি++ এর <algorithm> হেডার ফাইল ব্যবহার করা হয়।
ভেক্টর এর ইনিশিয়াল এবং এনডিং অ্যাড্রেস এবং কোন ভ্যালুর সাপেক্ষে আমরা বাউন্ড বের করতে চাই এগুলি প্যারামিটার হিসেবে দিতে হবে।

Iterator

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে–>
vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো–>
for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;  // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

Searching Algo

লিনিয়ার সার্চ(Linear Search)

লিনিয়ার সার্চ সবচেয়ে ব্যাসিক সার্চ টেকনিক। ধরি আমাদের n টি নম্বর এর একটি অ্যাারে দেয়া আছে। এখন আরেকটি নম্বর a দিয়ে আমাকে জিজ্ঞাসা করা হল, এই a , আগের n টি নম্বর এর মাঝে আছে কিনা। স্বাভাবিকভাবে আমরা 0 থেকে n (অ্যাারে এর ঘর বিবেচনা করলে) পর্যন্ত একটি লুপ চালায়ে নম্বরটিকে বের করার চেষ্টা করবো।

int arr [ ] = { 1, 2, 4, 12, 14, 78, 21, -90, 111, 1467};
int a = 111;
for ( int i = 0; i < 10; i++ ){
          if ( arr [ i ] == a ){
                cout << ” Found the number 😀 ” << endl;
                break;
}
}
সার্চিং এর ক্ষেত্রে লিনিয়ার সার্চ ছোট রেঞ্জ এর মধ্যে কাজ করবে কিন্তু রেঞ্জ বড় হয়ে গেলে TLE দিবে। আমরা লিনিয়ারি একটি পজিশন থেকে আরেকটি পজিশন এ যাচ্ছি ( n তম এলেমেন্ট পাওয়ার জন্য আমাদের শুরু থেকে n পর্যন্ত যেতে হবে), কাজেই লিনিয়ার সার্চের কমপ্লেক্সিটি O ( n )  [ Order of n ] যেখানে n হল কতটি এলেমেন্ট এর মাঝে সার্চিংটি চলছে।

বাইনারি সার্চ(Binary Search)

বাইনারি সার্চ সবচেয়ে জনপ্রিয় সার্চ টেকনিক এবং এর ব্যবহার ও খুব মজার। বাইনারি সার্চের জন্য প্রথমেই আমাদের নম্বরগুলিকে কোন একটি অর্ডার এ সাজাতে হবে ( Ascending or Descending )। এরপরে আমরা ২টি পজিশন সেট করবো low এবং high নামে। low  হবে আমাদের অ্যাারে এর 0th ইনডেক্স এবং high হবে (n-1)th ইনডেক্স। এখন আমরা এই high এবং low এর মাঝে থেকে middle ইনডেক্স বের করার চেষ্টা করবো এবং চেক করবো ঐ middle ইনডেক্স এর ভ্যালুটা আমাদের কাঙ্ক্ষিত ভ্যালুর সাথে মিলে গেছে কিনা। যদি মিলে যায়, তাহলে আমরা আমাদের ভ্যালু পেয়ে গেছি। যদি না মিলে, তবে ২টি কন্ডিশন হতে পারে।
১ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে বড়।
২ঃ মিড ভ্যালুটি আমাদের কাঙ্ক্ষিত ভ্যালুর চেয়ে ছোট।
ধরি আমাদের অ্যাারেটি ছোট থেকে বড় আকারে সাজানো আছে। এখন ১ এর জন্য মিড ভ্যালুটি বড়, কাজেই আমাদের কাঙ্ক্ষিত ভ্যালুটি মিড ইনডেক্স এর অবশ্যই আগে আছে। কাজেই তখন আমাদের high হয়ে যাবে middle – 1 এবং low এর কোন চেঞ্জ হবেনা। ২ঃ এর খেত্রেও একই ব্যাপার। তখন low হবে middle + 1 এবং high এর কোন চেঞ্জ হবেনা। একটি উদাহরন দেখিঃ আমাদের ২০ কে খুঁজে বের করতে হবে। binary-search
টাইম কমপ্লেক্সিটি ঃ আমরা প্রতিবার সার্চিং এর জন্য একটি অংশ নিচ্ছি এবং অন্যটি বাদ দিয়ে দিচ্ছি। কাজেই worst case এর জন্য আমাদের কমপ্লেক্সিটি হবে O ( N * logN )।
স্যাম্পল কোড ঃ Capture
আমরা ভ্যালু পেয়ে গেলে ভ্যালুটির ইনডেক্স রিটার্ন করবো, আর না পেলে -1 রিটার্ন করবো। লক্ষ্য করলে দেখবে যে বাইনারি সার্চ এর টারমিনেট কন্ডিশন যখন high এর চেয়ে low এর ইনডেক্স বড় হয়ে যাবে। এই ব্যাপারগুলি ভালোভাবে খেয়াল না রাখলে ইনফিনিট লুপ এ পরবে প্রোগ্রাম। কোড করার সময় তাই আমাদের মাথায় রাখতে হবে আসলে কখন কোথায় কি হচ্ছে এবং কখন কোন কন্ডিশন দিলে ঠিকমতন প্রোগ্রাম রান করবে।

 

Priority Queue

প্রায়োরিটি কিউ (Priority Queue)

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
Captureএখন আমরা যদি ছোট থেকে বড় প্রায়োরিটি অনুসারে সাজাতে চাই? তাহলে ব্যাপারটা কি হবে? একটি হিনটস দেইঃ আমরা ইনসার্ট এর সময় ভ্যালুগুলিকে মাইনাস ১ ( -1 ) দিয়ে গুন করে ইনসার্ট করতে পারি। এছাড়াও সর্টিং, কমপ্যারিং এর আরো কিছু মেথড আছে, সেগুলা আমরা পরে অন্য কোন জায়গায় আলোচনা করবো।

Map

ম্যাপ ( Map )

ম্যাপ খুব দরকারি একটি ডাটা স্ট্রাকচার। আমরা অ্যাারে এর কনসেপ্ট থেকে ম্যাপ কে বুঝার চেষ্টা করবো। আমরা অ্যাারে এর ব্যাপার গুলি থেকে যা জানি, অ্যাারে তে 0 থেকে n সংখ্যক কিছু ইনডেক্স থাকে, সেসব ইনডেক্স এ আমরা আমাদের ডাটা টাইপ অনুযায়ী ডাটা রাখি। অতঃপর আমরা অ্যাারে এর ইনডেক্স কে কল করলে, সে ইনডেক্স এ রাখা ডাটা কে খুব সহজে পেয়ে যাই। এটা মোটামুটি অ্যাারে এর ব্যাসিক আইডিয়া। এখন আমরা অ্যাারে এর ইনডেক্স এর জন্য কেবল মাত্র ইন্টিজার নম্বর ব্যবহার করি, অর্থাৎ কোন একটি ইন্টিজার নম্বর এর সাপেক্ষে আমরা ঐ ইনডেক্স এর ভ্যালু পাবো। এক্ষেত্রে এই ইন্টিজার নম্বরগুলি হচ্ছে key or index, আর এরমধ্যে রাখা জিনিসগুলি হচ্ছে value or data.
এখন একটি গল্প দেখা যাক–>
ধরি কোন এক রাজ্যে কোন এক রাজা আছে। রাজার প্রায় ১০০+ বউ আছে, এবং ৩০০+ বাচ্চাকাচ্চাও আছে !! আচ্ছা ব্যাপারটা একটু কেমন দাঁড়ায়। আসলে ইনি রাজা নন, এনাকে আমরা মহারাজা বলবো এখন থেকে 😀 । তো, মহারাজার নাম হচ্ছে সেন্টিনো। সেন্টিনোর মন্ত্রীর নাম লুসিফার। প্রতি মাসের প্রাইম নম্বর এর দিনগুলিতে মহারাজা সেন্টিনো, লুসিফার এর কাছে তার বউ বাচ্চার খবর জানতে চায়। আসলে খবর বলতে সেন্টিনো খালি জানতে চায় অমুক নামের মানুষটি কি তার বউ? নাকি বাচ্চা? ( অনেক বাচ্চাকাচ্চা, বউ, পাইক – পেয়াদা, সৈন্য সবার নাম, পদবী তার মনে থাকেনা, এজন্য মন্ত্রী মশাইয়ের কাছে উনি একেটটি নাম দিয়ে তার পজিশন জিজ্ঞাসা করেন  😛 )। এখন সেন্টিনো খুব বদমেজাজী রাজা। পান থেকে চুন খসলেই গর্দান ফালায়ে দিবে এরকম টাইপ। লুসিফার এর ভয় ,যদি সে উলটাপালটা কোন ইনফরমেশন দেয়, তাহলে তার জীবন ঐদিন ই শেষ 😦 । তো লুসিফার অন্য এক সাম্রাজ্য থেকে তোমাকে ডেকে নিয়ে আসলো এবং মহারাজার এই ব্যাপারটায় সাহা্য্য করতে বললো। সাহায্য না করলে তোমার গর্দান যাবে বলে হুমকিও দিল। মজার কথা হচ্ছে, তুমি যদি ম্যাপ জানো, তাহলে তোমার জন্য এটা পুরা পান্তা ভাত, আর না জানলে তো গর্দান যাবে বুঝতেই পারছো।
এখন মহারাজা একটি একটি করে নাম বলে, এবং তোমাকে বলতে হবে ঐ নামধারী ব্যাক্তি আসলে মহারাজার কি হয়? বউ? বাচ্চা? নাকি অন্য কিছু। যেমন সেন্টিনো জানতে চাইলো, মর্জিনা আমার কি হয়? উত্তর ঃ বউ। এখন তুমি যদি উত্তর দেও যে মর্জিনা আপনার বাচ্চা হয়, এবং মর্জিনা কে ডেকে আনার পর যখন মহারাজা বুঝবে যে তুমি মিথ্যা বলেছো, তুমি ওইখানেই শেষ। ( ধরি হিসাবের সুবিধার্থে, কোন বাচ্চা, বউ, সৈন্য কারো নামের ডুপ্লিকেট কেউ থাকবে না )।
এখন আসি সমাধানে –>
এখন ম্যাপ জানা থাকলে তুমি একটি নাম কে, আরেকটি নাম দিয়ে রিপ্রেসেন্ট করবে। যেমন এখানে মর্জিনা হচ্ছে key, আর বউ হচ্ছে তার value. এখন মর্জিনা, বউ এগুলা তো স্ট্রিং টাইপ, কাজেই আমরা ম্যাপ এভাবে ডিক্লার করতে পারি।
#include <map>
map < string, string > m;
এখানে ম্যাপ আসলে এভাবে থাকে ঃ map < key, value >
তাহলে আমরা m নামের একটি ম্যাপ ডিক্লার করলাম।
এখন আমরা এই ম্যাপ এ ভ্যালু ইনসার্ট করবো।
m [ “Morjina” ] = “Bou“;  // এরমানে হচ্ছে, “Morjina” নামের একটি ইনডেক্স এ “Bou” কে ইনসার্ট করলাম।
cout << m [ “Morjina” ] << endl; // এখানে আউটপুট আসবে ঃ “Bou
আশা করি ব্যাপারটা বুঝে গেছো সবাই। এভাবে আমরা ম্যাপিং এর মাধ্যমে যেকোন ডাটা টাইপ কে যে কোন টাইপ দিয়ে রিপ্রেসেন্ট করতে পারি।
m [ “Sokhina” ] = “Bachcha“;
m [ “Anika” ] = “Bou“;
m [ “Solayman” ] = “Soldier“;
m [ “Lucifer” ] = “Minister“;
m [ “Keka Ferdousi” ] = “Radhuni“;
এরকম ইনসার্ট করার পরে আমরা মহারাজা সেন্টিনোর কথা অনুযায়ী ম্যাপ থেকে খুব সহজেই ডাটা রিট্রিভ করতে পারবো।
যদি ম্যাপ এর সবকিছু আমরা আগের অবস্থায় আনতে চাই, তাহলে map.clear() লিখলে ম্যাপ একদম empty হয়ে যাবে।
ম্যাপ নিয়ে আপাতত এটুকুই। আরো ডিটেইলস জানতে চাইলে তোমরা গুগল করে শিখে নিলে সেটা বেটার হয়।
মহারাজার আজগুবি কাহিনী পড়ার জন্য ধন্যবাদ 😛 

Queue

কিউ(Queue)

কিউ পুরোপুরি স্ট্যাক এর উলটা। এর কাজ করার সিস্টেম হল ঃ First In First Out ( FIFO ).
আমরা কিউ এর উদাহরন এভাবে দিতে পারি, ধরি আমরা বসুন্ধরায় “ভালোবাসা দিবি কিনা বল” মুভি দেখতে গেলাম। আমরা n সংখ্যক বন্ধু বান্ধব মিলে লাইন এ দাড়ালাম টিকেট কিনার জন্য। এই লাইনটিই কিন্তু একটি কিউ। ধরি আমাদের দাড়ানোর সিরিয়ালটি এরকম ঃ তারেক->আমি->জামি->আহানাফ->ইসলাম।
তাহলে কিউ এর একদম প্রথমে আছে তারেক। যখন ওর টিকেট কিনা হয়ে যাবে, ও সামনে দিয়ে লাইন থেকে বের হয়ে যাবে। প্রোগ্রাম এর ভাষায় একে বলে পপ ( pop() ). তাহলে তারেক পপ হবার পরে কিউ এর সামনে থাকবো এখন আমি। এভাবে যে আগে কিউ তে প্রবেশ করবে, সে আগে বের হবে, এটা হল আসল কথা।
কিউ এর জন্য হেডার ফাইল : #include<queue>
int main(){

queue <string> q;
q.push(“Tarek”);  // কিউ তে insert এর জন্য push() ফাংশন
q.push(“Shishir”);
q.push(“Jami”);
q.push(“Ahanaf”);
q.push(“Islam”);

 while ( !q.empty() ){
 cout << q.front() << endl;  // কিউ এর প্রথম এলেমেন্ট প্রিন্ট করলাম
q.pop(); // কিউ এর প্রথম এলেমেন্ট রিমুভ করলাম
}

return 0;
}
প্র্যাকটিস এর জন্য কিছু প্রব্লেম ঃ

১। একটি কিউ এ ১ থেকে ১০০ পর্যন্ত নম্বর পুশ কর এবং এর মধ্যে থেকে কেবল মাত্র জোড় সংখ্যাগুলো প্রিন্ট কর।
২। কিউ তে কতগুলি স্ট্রিং পুশ কর এবং তাদেরকে LIFO আকারে প্রিন্ট কর। (using queue, print the values like stack).