Saturday, February 17, 2018

ইটারেটর(Iterator)

ইটারেটর(Iterator)

ইটারেটর আসলে সি এর পয়েন্টার এর মত কাজ করে। পয়েন্টার একটি অ্যাড্রেসকে পয়েন্ট করে থাকে যা থেকে আমরা পরবর্তীতে সেই অ্যাড্রেস এর ডাটা নিয়ে কাজ করতে পারি। সি++ এর ইটারেটর এর কাজ ও ঠিক ওরকম। STL ফাংশনগুলি অনেক ক্ষেত্রে অ্যাড্রেস পাঠায় আমরা যে ডাটাকে খুঁজছি, তা কোথায় আছে তার। ইটারেটর ডিক্লার করে এভাবে-->

vector< int > :: iterator it ;
আমরা ভেক্টর এর একটি ইটারেটর it ডিক্লার করলাম।
এখন ভেক্টর এর সব এলেমেন্ট দেখতে চাইলে আমরা এটা করবো-->

for ( it = v.begin(); it != v.end(); it++ )   // v নামের একটি ইন্টিজার এর ভেক্টর নিলাম।
       cout << *it << endl;                        // *it দিয়ে আমরা it অ্যাড্রেস যাকে পয়েন্ট করে আছে, তার ভ্যালু প্রিন্ট করলাম।

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

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

ঠিক কিউ এর মতই, তবে এর একটি সুন্দর দিক হচ্ছে এটি প্রোগ্রামারের প্রায়োরিটি অনুযায়ী কাজ করে।
ধরি কোন একটি জিনিস নিলামের জন্য ডাকা হল। এখন ক্রেতা অনেক। একেকজন একেক দাম হাঁকছে। ধরলাম ক্রেতা আবির, কালাম, হাসান, মমতাজ যথাক্রমে ১০, ৩০, ১২, ১৪ টাকা দাম ডাকলো। এখন আবির আগে ১০ টাকা ডাকলেও, কালাম কিন্তু ৩০ টাকা ডাকার কারনে তার প্রায়োরিটি বেশি হবে বিক্রেতার কাছে। তাই বিক্রেতা চাবে কালামকে জিনিসটি দিতে। এরপরে কালাম চলে গেলে বেশি প্রায়োরিটি পাবে মমতাজ। প্রায়োরিটি কিউ ঠিক এরকম বিক্রেতার মত আচরন করে। default প্রায়োরিটি কিউ বড় থেকে ছোট ভ্যালু প্রসেস করে। কাজেই এক্ষেত্রে ৩০, ১৪, ১২, ১০ এভাবে ভ্যালুগুলি সাজানো থাকবে কিউতে।
প্রায়োরিটি কিউ এর হেডার ফাইলঃ #include <priority_queue>

Capture
এখন আমরা যদি ছোট থেকে বড় প্রায়োরিটি অনুসারে সাজাতে চাই? তাহলে ব্যাপারটা কি হবে? একটি হিনটস দেইঃ আমরা ইনসার্ট এর সময় ভ্যালুগুলিকে মাইনাস ১ ( -1 ) দিয়ে গুন করে ইনসার্ট করতে পারি। এছাড়াও সর্টিং, কম্পেয়ারিং এর আরো কিছু মেথড আছে, সেগুলা আমরা পরে অন্য কোন জায়গায় আলোচনা করবো।

ম্যাপ ( Map )

ম্যাপ ( Map )

ম্যাপ খুব দরকারি একটি ডাটা স্ট্রাকচার। আমরা অ্যাারে এর কনসেপ্ট থেকে ম্যাপ কে বুঝার চেষ্টা করবো। আমরা অ্যাারে এর ব্যাপার গুলি থেকে যা জানি, অ্যাারে তে 0 থেকে n সংখ্যক কিছু ইনডেক্স থাকে, সেসব ইনডেক্স এ আমরা আমাদের ডাটা টাইপ অনুযায়ী ডাটা রাখি। অতঃপর আমরা অ্যাারে এর ইনডেক্স কে কল করলে, সে ইনডেক্স এ রাখা ডাটা কে খুব সহজে পেয়ে যাই। এটা মোটামুটি অ্যাারে এর ব্যাসিক আইডিয়া। এখন আমরা অ্যাারে এর ইনডেক্স এর জন্য কেবল মাত্র ইন্টিজার নম্বর ব্যবহার করি, অর্থাৎ কোন একটি ইন্টিজার নম্বর এর সাপেক্ষে আমরা ঐ ইনডেক্স এর ভ্যালু পাবো। এক্ষেত্রে এই ইন্টিজার নম্বরগুলি হচ্ছে key or index, আর এরমধ্যে রাখা জিনিসগুলি হচ্ছে value or data.
এখন একটি গল্প দেখা যাক-->

ধরি কোন এক রাজ্যে কোন এক রাজা আছে। রাজার প্রায় ১০০+ বউ আছে, এবং ৩০০+ বাচ্চাকাচ্চাও আছে !! আচ্ছা ব্যাপারটা একটু কেমন দাঁড়ায়। আসলে ইনি রাজা নন, এনাকে আমরা মহারাজা বলবো এখন থেকে :D । তো, মহারাজার নাম হচ্ছে সেন্টিনো। সেন্টিনোর মন্ত্রীর নাম লুসিফার। প্রতি মাসের প্রাইম নম্বর এর দিনগুলিতে মহারাজা সেন্টিনো, লুসিফার এর কাছে তার বউ বাচ্চার খবর জানতে চায়। আসলে খবর বলতে সেন্টিনো খালি জানতে চায় অমুক নামের মানুষটি কি তার বউ? নাকি বাচ্চা? ( অনেক বাচ্চাকাচ্চা, বউ, পাইক - পেয়াদা, সৈন্য সবার নাম, পদবী তার মনে থাকেনা, এজন্য মন্ত্রী মশাইয়ের কাছে উনি একেটটি নাম দিয়ে তার পজিশন জিজ্ঞাসা করেন  :P )। এখন সেন্টিনো খুব বদমেজাজী রাজা। পান থেকে চুন খসলেই গর্দান ফালায়ে দিবে এরকম টাইপ। লুসিফার এর ভয় ,যদি সে উলটাপালটা কোন ইনফরমেশন দেয়, তাহলে তার জীবন ঐদিন ই শেষ :( । তো লুসিফার অন্য এক সাম্রাজ্য থেকে তোমাকে ডেকে নিয়ে আসলো এবং মহারাজার এই ব্যাপারটায় সাহা্য্য করতে বললো। সাহায্য না করলে তোমার গর্দান যাবে বলে হুমকিও দিল। মজার কথা হচ্ছে, তুমি যদি ম্যাপ জানো, তাহলে তোমার জন্য এটা পুরা পান্তা ভাত, আর না জানলে তো গর্দান যাবে বুঝতেই পারছো।

এখন মহারাজা একটি একটি করে নাম বলে, এবং তোমাকে বলতে হবে ঐ নামধারী ব্যাক্তি আসলে মহারাজার কি হয়? বউ? বাচ্চা? নাকি অন্য কিছু। যেমন সেন্টিনো জানতে চাইলো, মর্জিনা আমার কি হয়? উত্তর ঃ বউ। এখন তুমি যদি উত্তর দেও যে মর্জিনা আপনার বাচ্চা হয়, এবং মর্জিনা কে ডেকে আনার পর যখন মহারাজা বুঝবে যে তুমি মিথ্যা বলেছো, তুমি ওইখানেই শেষ। ( ধরি হিসাবের সুবিধার্থে, কোন বাচ্চা, বউ, সৈন্য কারো নামের ডুপ্লিকেট কেউ থাকবে না )।

এখন আসি সমাধানে -->
এখন ম্যাপ জানা থাকলে তুমি একটি নাম কে, আরেকটি নাম দিয়ে রিপ্রেসেন্ট করবে। যেমন এখানে মর্জিনা হচ্ছে 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 হয়ে যাবে।

ম্যাপ নিয়ে আপাতত এটুকুই। আরো ডিটেইলস জানতে চাইলে তোমরা গুগল করে শিখে নিলে সেটা ভালো হয়।
মহারাজার আজগুবি কাহিনী পড়ার জন্য ধন্যবাদ :P 

কিউ ( Queue )

কিউ(Queue)

কিউ পুরোপুরি স্ট্যাক এর উলটা। এর কাজ করার সিস্টেম হল ঃ First In First Out ( FIFO ).

আমরা কিউ এর উদাহরন এভাবে দিতে পারি, ধরি আমরা বসুন্ধরায় "ভালোবাসা দিবি কিনা বল" মুভি দেখতে গেলাম। আমরা n সংখ্যক বন্ধু বান্ধব মিলে লাইন এ দাড়ালাম টিকেট কিনার জন্য। এই লাইনটিই কিন্তু একটি কিউ। ধরি আমাদের দাড়ানোর সিরিয়ালটি এরকম ঃ তারেক->আমি->জামি->আহানাফ->ইসলাম।
তাহলে কিউ এর একদম প্রথমে আছে তারেক। যখন ওর টিকেট কিনা হয়ে যাবে, ও সামনে দিয়ে লাইন থেকে বের হয়ে যাবে। প্রোগ্রাম এর ভাষায় একে বলে পপ ( pop() ). তাহলে তারেক পপ হবার পরে কিউ এর সামনে থাকবো এখন আমি। এভাবে যে আগে কিউ তে প্রবেশ করবে, সে আগে বের হবে, এটা হল আসল কথা।

#include<queue>
using namespace std;
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).

স্ট্রিং ( String )

  স্ট্রিং(String)

স্ট্রিং একটি বেশ মজার এবং কাজের ডাটা স্ট্রাকচার। এর কাজ নরমাল ক্যারেক্টার অ্যারে এর মতই, কিন্তু এর ব্যবহার খুব সহজ এবং অনেক কাজ অনেক সহজে করা যায়। স্ট্রিং এর জন্য হেডার ফাইল : #include<string>
একটি কোড দেখা যাক -->


#include<string>

using namespace std;
int main()

{
                string a; // স্ট্রিং টাইপ একটি ভ্যারিয়েবল 'a' ডিক্লার করলাম
                cin >> a; // user থেকে ইনপুট নিলাম
                cout << a << endl; // ইনপুট এর স্ট্রিং প্রিন্ট করলাম
                return 0;
}


স্ট্রিং এর ক্ষেত্রে এভাবে নিয়ে আমরা স্ট্রিং প্রিন্ট করতে পারি। কিন্তু এখানে স্পেস এর পরে কোন ক্যারেক্টার প্রিন্ট হবেনা। তোমরা ইনপুট নিয়ে দেখতে পারো। এরকম ক্ষেত্রে আমরা তাহলে কি করবো? আমাদের দরকার পুরা একটি লাইন ইনপুট নেয়া। এরজন্য ইনপুট নিতে হবে এভাবে-->


getline ( cin, a );


getline() ফাংশন এর কাজ হচ্ছে লাইন শেষ না হওয়া পর্যন্ত ইনপুট নিবে। এখন আমরা স্পেস সহ ইনপুট নিতে পারবো। উপরের কোড এ cin>>a এর বদলে getline (cin,a) লিখে তোমরা ব্যাপারটা দেখতে পারো।


স্ট্রিং এর মজার ব্যাপার হচ্ছে স্ট্রিং কে আরেক স্ট্রিং এ সরাসরি কপি, অ্যাড করা যায়।


string a,b,c;
a = "I eat rice";
b = " and I eat pizza.";
c = a + b;
cout << c << endl;          // এখানে আউটপুট হবে : "I eat rice and I eat pizza"

সুন্দরভাবে concatanation হয়ে গেলো!! সি তে char array নিয়ে করতে গেলে ব্যাপারটা এত সহজ না।

string.size() ফাংশন স্ট্রিং এর সাইজ রিটার্ন করে (integer).
কোন একটি স্ট্রিং কে উলটা করে লিখার জন্য আমরা এভাবে for loop ব্যবহার কতে পারি-->

string a;
cin >> a;
int len = a.size();
string b = "";                 // একটি empty string ডিক্লার করলাম
for ( int i = len-1, pos = 0; i >= 0; i--, pos++ )
b [ pos ] = a [ i ];
cout << b << endl;       // রিভার্স করা স্ট্রিংটি 'b' এর মধ্যে আছে এখন।

সি++ এ আমরা reverse() ফাংশন ব্যবহার করে স্ট্রিং কে কোন লুপ কোড লিখা ছাড়াই রিভার্স করতে পারি এভাবেঃ
reverse ( a.begin(), a.end() );    // a = string variable

স্ট্রিং অনেকগুলি ক্যারেক্টার এর একটি অ্যারে। তাই নরমাল সি এর char array এর মত স্ট্রিং কেও ইনডেক্স অনুযায়ী এক্সেস করা যায়, প্রসেস করা যায়। যেমন, স্ট্রিং a এর 0th ইনডেক্স এর ক্যারেক্টার হবেঃ a [ 0 ]

স্ট্রিং একটি নরমাল ডাটা টাইপ (like int,float,double), কাজেই এটাকে আমরা অন্যান্য ডাটা টাইপ লিখার জন্য যেভাবে লিখি, সেভাবে লিখতে পারবো।
স্ট্রিং এর ভেক্টর: vector < string > string_vec;
স্ট্রিং এর স্ট্যাক: stack < string > string_stack;  এরকম।

স্ট্রিং এর জিনিসগুলি ভালোভাবে রপ্ত করার জন্য তোমরা নিচের সমস্যাগুলি চেষ্টা করতে পারোঃ

১। একটি স্ট্রিং প্যালিন্ড্রম কিনা চেক কর।
example :
hello -> not palindrome
1234321 -> palindrome
wecanacwe ->not palindrome

২। একটি স্ট্রিং দেয়া হবে। যেখানে কেবলমাত্র 0 এবং 1থাকবে। একে ডেসিমাল ভ্যালুতে প্রকাশ কর
example :
00000010 -> the decimal value is 2
111 -> the decimal value is 7

৩। একটি স্ট্রিং এ মোট কতটি ওয়ার্ড আছে এবং কিকি লিখ।
example :
Hello, how are you ?
--> there are 4 words. They are : Hello, how, are, you.