খোঁজ করুন

জাবেদের হালখাতা :: JAVEDER HALKHATA

আগডুম_বাগডুমের জগৎ

আমার কিউয়ের হাতেখড়ি – Codeforces – 546C

প্রবলেম নাম্বার : http://bit.ly/1VqOsAJ

এই প্রব্লেম দিয়ে আমি আমার STL কন্টেইনার Queue এর ব্যবহার করা শুরু করেছি। সব STL Container তুলনা করলে আমার কাছে মনে হয় সব চেয়ে সহজ হচ্ছে Queue এর ব্যবহার।Queue এর ব্যসিক জানা না থাকলে এই লিংক থেকে আগে কিউয়ের ব্যসিক ক্লিয়ার করে আসলে ভালো হবে,বুজতেও সহজ হবে।প্রবলেম টি মোটামুটি সহজ কিন্তু কোড করতে জানলে সহজ,এটাকে আমি ভেক্টর দিয়েও করেছি তবে কিউ দিয়ে করলে ভালো।প্রব্লেম টি এরকম যে দুই জন সলজার আছে তারা কারড খেলবে ,প্রত্যেকের কাছে কত গুলো কারড আছে তা আগে থেকেই দেয়া থাকবে।আর প্রত্যের কারডের একটা মান দেয়া থাকবে।

তো আমরা ধরে নি যে প্রথম স্লজারের নাম হচ্ছে a আর অপর সলজারের নাম হচ্ছে b।

প্রবলেম ডিস্কাশনঃ এখন শুরুটা হবে এরকম , দুই সলজারের উভয়ের উপরের কারড এর উপর ডিপেন্ড করবে কে জয়ি।দুইজনের উপরে মানে Front এ  যে কারড থাকবে সে দুইটা কারডের সাথে কম্পেয়ার করতে হবে যদি দেখা যায় প্রথম সলজারের মানে a এর কারড এর মান বড়, তাহলে সে তার অপজিট সলজারের b এর কারড নিয়ে সে নিজের নিকট নিয়ে নিবে।তবে এখানে নেয়ার ক্ষেত্রে যে সিস্টেম সেটাই একটু বড় ব্যপার,সেটা হচ্ছে যদি দেখা যায় a এর প্রথম কারড(যেহেতু আমাদের এই প্রবলেম ডিপেন্ড করবে উভয়ের উপরের কারড এর উপর) এর মান b এর প্রথম কারড থেকে বড় তাহলে প্রথমে a   ,  b এর উপরের কারড তার একেবারে নিচে রাখবে এর পরে সে তার উপরে যে কারড ছিলো সেটা একেবারে নিচে রাখবে ,এভাবেই খেলা চলতে থাকবে।কোন এক সময় দেখা যাবে যে কোন এক জনের একটা কারডও থাকবে না শেষ পরযন্ত, তখন খেলা শেষ। আমাদের প্রিন্ট করতে হবে মোট কতবার এই ফাইট হয়েছে আর জয়ি কে হয়েছে।

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

Capture

এখানের Sample Input :

4
2 1 3
2 4 2

আর Sample Output :

6 2

4 হচ্ছে মোট কারডের সংখ্যা।এর পরের লাইন হচ্ছে a আর b এর কারড সংখ্যা আর এর মান। a এর কারডের মান হচ্ছে 1,3 আর b এর কারডের মান হচ্ছে 4,2।এখন আমরা যদি a আর b এর উপরের কারডের মান নিয়ে চিন্তা করি তাহলে দেখা যাবে a এর উপরে কারড=1 আর b এর উপরেটা =4 । মানে b এর টা বড়।এর মানে এখন b ,a এর উপরেটা টা প্রথমে তার নিচে পুশ করে এর পরে তার নিজের উপরেটা নিচে পুশ করবে যা ২ নাম্বার প্রসেসের মাধ্যমে বুঝানো হয়েছে।তাহলে এখন a এর কারড=3 আর b এর কারড = 2,1,4। সাথে সাথে আমরা ফাইট Count ও  করবো,তাহলে এখন Count=1 । এর পরে আবার এভাবে চলবে এখন a এর উপরে যেটা আছে(বেচারার মাত্র একটাই আছে,তাই অইটাই ভাইয়ের উপর) তা b এর উপরে যে টা আছে (b  এর উপরে আছে এখন 2) তার থেকে বড়।তাই এখন a ,b এর উপরেটা প্রথমে তার নিচে রাখবে (2 রাখবে) এর পরে a তার উপরেটাকে নিচে পাঠিয়ে দিবে(3 কে নিচে পাঠাবে)।তাহলে এখন count=2।এখন শেষ ধাপে চলে যাই যখন a এর কারড =2 আর  b এর কারড=4,1,3 ।দেখা যাচ্ছে b এর উপরেটা বড় তাই a এর উপরেটা (2) সে টার নিচে পুশ করবে এর পরে তার নিজের উপরেটা ।তাহলে এখন a এর কারড=0। খেল খতম।b জয়ি আর কাউন্ট =6।আর একটা কথা while loop যতবার ঘুরবে ততবার বুজতে হবে ততবার ফাইত হয়েছে তাই লপের ভিতরে আমরা count++ করে দিবো।

কোড এর সলুশনঃ

মুল প্রসেস্টি তাহলে এভাবে হবে আমরা উভয়ের কারড কে দুইটা কিউতে পুশ করব তাই দুইটা কিউ ডিগলিয়ার করে দিবো

 queue<LL int>c1,c2;

এর পরে কিউতে তাদের কারডের মান গুলো পুশ করবো

    cin>>n1;
    for(i=0;i<n1;i++){    
        cin>>a;
        c1.push(a);
    }
    cin>>n2;
    for(i=0;i<n2;i++){    
        cin>>b;
        c2.push(b);
    }

এর পরে একটা আমরা while loop চালাবো উভয় কিউয়ের সাইজের কন্ডিশনের উপরে,যদি দেখা যায় কখনো কোন একটা কিউ এর সাইজ 0 হবে এর মানে যে কোন এক জনের আর কোন কারড নেই।তার মানে খেলা শেষ, লুপ থেকে বাহির হয়ে যাবে আর কাউন্ট আর জয়ির নাম্বার প্রিন্ট করবে, এক নাম্বার হলে 1 এর দুইনাম্বার জন হলে 2।আর যদি দেখা যায় খেলা টি চলতেই আছে তাহলে বুজতে হবে খেলা ড্র প্রিন্ট করতে হবে -1।তবে -1 মানে খেলা ড্র যে হলো এটাবুঝার জন্য যে কন্ডিশন হবে তা আপনারা নিজেদের লজিক ব্যবহার করে বাহির করবেন,জিনিসটা ইজি কনচেপশন 🙂

    while(cnt<=10000&&sz(c1)>0&&sz(c2)>0){  //sz(c1)==c1.size()
        cnt++;
        if(c1.front()>c2.front()){
            c1.push(c2.front());
            c1.push(c1.front());
            c1.pop();
            c2.pop();
        }
        else if(c2.front()>c1.front()){
            c2.push(c1.front());
            c2.push(c2.front());
            c1.pop();
            c2.pop();
        }
    }

while এর ভিতরে আমরা দুইজনের জন্য if else কন্ডিশন এপ্লাই করবো। if কন্ডিশনের মাধ্যমে আমরা উভয়ের front এ যে আছে তাদের মধ্যে বড় ছোট কম্পেয়ার করতেছি।এর পরে যে কন্ডিশনে মিলে যাবে সাথে সাথে অপজিশনেরটা সহ নিজেরটাও পুশ করবে।কিউ এর পুশ করার ক্ষেত্রে এটা নিচে নিচে মানকে পুশ করে।যেহেতু আমরা উভয়ের উপরের গুলোকে নিচে পাঠাচ্ছি তাহলে উভয়ের উপরে যা আছে সেগুলোকে ইরেজ বলেন ডিলিট বলেন তা করতে হবে,আর queue তে এটাকে pop দিয়ে সমাধান করা হয়।pop কাজ করে কিউ এর উপরের ইলিমেন্ট কে নিয়ে, প্রতিবার pop এর কারনে উভয় কিয় (মানে উভয় সলজারের) এর উপরের ইলিমেন্টকে সে কেটে দিবে আর পুশ এর মাধ্যমে সে ফ্রন্টে এ যে আছে তাকে নিচে পাঠিয়ে দিবে।

আশা করি while loop এর ভিতর থেকে বের হওয়ার পরে কে জয়ী হয়েছে সেটা বের করার জন্য কন্ডিশন কি দিবেন তা মাথায় এসে গেছে । সবার শেষে কন্ডিশনের লজিক হবে এভাবে if ধারা আমরা চেক করব কার queue এর সাইজ জিরো(0)  ,যার সাইজ জিরো হবে size==0 , জয়ী হবে তার অপজিট সলজার বা এভাবেও দিতে পারেন যার কিউয়ের সাইজ জিরো না size!=0 বা এভাবেও হতে পারে সাইজের মান জিরো থেকে বড় size>0 সে হবে জয়ী।

আর ড্র হলে চেক করবেন এভাবে যেহেতু ড্র মানে লুপটি ইনফিনিট ভাবে চলচে থামবে না তাহলে ড্র এর জন্য while lop এ আপনি কাউন্ট এর যে আনুমানিক মান ধরেছেন যে বেশি হলে x বার ফাইট হতে পারে ।

তাহলে যদি দেখা যায় count এর মান x থেকে বড় বা তার সমান তাহলে বুজতে হবে লুপটি থামবে না খেলা ড্র ,প্রিন্ট করে দিবে -1;

    if(cnt>=10000){
        cout<<"-1"<<endl;
    }
    else{
        cout<<cnt<<" ";
        if(sz(c1)>0){
            cout<<"1"<<endl;
        }
        else if(sz(c2)>0){
            cout<<"2"<<endl;
        }
    }

আশা করি আমার লেখার মাধ্যমে কিউয়ের বেসিক কিছুটা হলেও ক্লিয়ার হবে আপনাদের,আর কিছু না বুজলে আমাকে না জিজ্ঞাস করে যদি গুগল করেন তাহলে আপনার জন্য ভালো তাহলে শিখা টা বেশি হয়।আমি নিজেও যা শিখি তা গুগল করেই শিখি।আর শিখার জন্য http://www.cplusplus.com/ এই সাইট অনেক অপকারী।

না
Advertisements

কিছু সাইট

ভেক্টর (STL – Vector)

লেখাটি আনা হয়েছে অনিন্দ্য ভাইয়ের ব্লগ থেকে :

সম্ভবত C++ Standard Template Library (STL) এর সবথেকে বেশি ব্যবহৃত কনটেইনারটি হল ভেক্টর। খুবই কাজের একটা জিনিস। খুব সাধারনভাবে বলতে গেলে, এটা অনেকটা অ্যারের মত। অ্যারেতে যেমন একটার পর একটা ভেরিয়েবল থাকে, তেমনি ভেক্টরেও তাই। একটার পর একটা সাজানো থাকে। আবার অ্যারেতে যেমন ইন্ডেক্স থাকে যেটা ব্যবহার করে সরাসরি ঐ ইন্ডেক্সের ভেরিয়েবল পাওয়া যায়, তেমনি ভেক্টরেও ইন্ডেক্স আছে এবং তা ঠিক একইভাবে অ্যারের মত করেই কাজ করে।

তাহলে স্বভাবতই প্রশ্ন আসে, ভেক্টর আর অ্যারের মধ্যে পার্থক্য কি? পার্থক্য হচ্ছে, অ্যারের সাইজ নির্দিষ্ট কিন্তু ভেক্টর resizable। আমরা যখন একটা অ্যারে ডিক্লেয়ার করি, তখন সেটার সাইজ বলে দিতে হয়। তাহলে সেই সাইজের একটা অ্যারে তৈরি হয়ে যায়। কিন্তু পরবর্তিতে সেটার সাইজ বড় বা ছোট করা যায় না। সেখানে যদি আমরা ভেক্টর ব্যবহার করি, তাহলে সহজেই সেটার সাইজ বড় ছোট করা যায়।

এখন প্রশ্ন হল, সাইজ ছোট বড় করে আমার লাভ কি? লাভটা বিভিন্ন প্রবলেম সলভ করতে গেলে বোঝা যায়। বেশির ভাগ ক্ষেত্রেই আমরা প্রয়োজনের চেয়ে বেশি সাইজের অ্যারে ডিক্লেয়ার করে রাখি। এতে অনেক মেমরি অপচয় হয়। এখন মনে হতে পারে, সলিউশন accepted হলেই হল, মেমরি অপচয় দিয়ে আমার কি? এটার উত্তর হল, অনেক প্রবলেমে 2D/3D অ্যারে লাগতে পারে। প্রবলেমটা এরকম হতে পারে যে দুইটা ডাইমেনশনে সর্বোচ্চ 20,000 টা করে এলিমেন্ট থাকবে। কিন্তু একই সাথে কখনও সব মিলিয়ে 30,000 এর বেশি এলিমেন্ট থাকবে না। তাহলে আমরা যদি [20000][20000] একটা অ্যারে ডিক্লেয়ার করতে যাই, সেটা কখনই সম্ভব না! তাই আমরা যদি 2D ভেক্টর ব্যবহার করি, তাহলে যেই ডাইমেনশনে যতগুলো এলিমেন্ট দরকার, সেটা তত বড় হবে। ফলে মোট 30000 টা এলিমেন্ট সহজেই রাখা সম্ভব! এভাবে ব্যাপারটা বোঝাতে আমার নিজেরই আসলে কষ্ট হচ্ছে। এধরনের প্রবলেম সামনে না এসে থাকলে আসলে এটা বোঝাটা মুশকিল। তবে এটা ধরে নিলেই চলবে যে ভেক্টর দিয়ে আমরা এফিসিয়েন্টভাবে মেমরি ব্যবহার করতে পারি।

অনেক ক্ষেত্রেই ভেক্টর দিয়ে সহজেই ডাটা ম্যানেজ করা যায়, যেখানে অ্যারে ব্যবহার করলে তুলনামূলক ঝামেলা বেশি। দেখা যায় আমরা অনেকগুলো এলিমেন্টের অ্যারে ডিক্লেয়ার করে রেখেছি। এখন সেখানে কত পর্যন্ত আমাদের ডাটা রাখা আছে তার জন্য আরেকটা ভেরিয়েবল রাখতে হয়। আবার যখন নতুন কোন ডাটা সেখানে রাখতে যাই তখন মোট ডাটার সংখ্যা, অর্থাৎ কত ইন্ডেক্সে ডাটা রাখা আছে সেটাকে 1 বাড়িয়ে দিতে হয়। আপাতদৃষ্টিতে এটা তেমন কিছু মনে না হলেও, অনেক বড় ডাটাসেট নিয়ে কাজ করতে গেলে এটা বেশ ঝামেলাদায়ক হয়ে যায়। সেখানে যদি পুরো ব্যাপারটা আপনা থেকেই ম্যানেজ হত তাহলে অনেক সহজ হয়ে যেত। আর আপনা থেকে ম্যানেজ করার এই কাজটা করে নিতে পারে ভেক্টর! এছাড়া STL এর অন্যান্য কন্টেইনার এবং এলগোরিদমিক ফাংশনের সাথে একে সহজেই ব্যবহার করা যায়।

অনেক হল ভেক্টরের গুণগান! নিজে থেকে কয়েকবার ব্যবহার করলেই আসলে বোঝা যাবে যে এটা ব্যবহার করে প্রবলেম সলভ করলে কত সুবিধা। এখন এটা কিভাবে ব্যবহার করতে হয় তা দেখা যাক।

ভেক্টর ব্যবহার করার জন্য প্রথমেই যেটা করতে হবে তা হল, <vector> হেডার ফাইল ইনক্লুড করে নিতে হবে। এরপর অবশ্যই using namespace std; লিখতে হবে। ফাইলটা যেন .cpp extension এর হয় সেটাও খেয়াল রাখতে হবে। এখন ভেক্টর কিভাবে ডিক্লেয়ার করা হবে দেখা যাক

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector <int> myVector;
    return 0;
}

ভেক্টর চাইলে globally-ও ডিক্লেয়ার করা যাবে, সিন্ট্যাক্স একই থাকবে। এখানে  ৮ নাম্বার লাইনে ভেক্টরটি ডিক্লেয়ার করা হয়েছে। প্রথমে vector লিখতে হবে। এরপর <> এর মধ্যে ডাটা টাইপ লিখতে হবে। int, double, float, char, unsigned ইত্যাদি যেকোনকিছুই সেটি হতে পারে। শুধু তাই নয়, নিজের ডিক্লেয়ার করা যেকোন struct বা class এরও ভেক্টর হতে পারে। যেমন vector <myClass> myVector; এটাও হতে পারে! ডাটা টাইপের পর ভেক্টরটির নাম দিতে হয়, যেমনটি আমরা ভেরিয়েবল ডিক্লেয়ার করার সময় ভেরিয়েবলের একটা নাম দেই, তেমনি।

এখন ভেক্টর ক্লাসের অন্তর্গত প্রায়ই ব্যবহৃত হয় এমন কিছু ফাংশন দেখা যাক।

push_back( DATA_TYPE value )

এই ফাংশনটি ভেক্টরের মধ্যে value পুশ করবে। এটি ব্যবহার করে আমরা ডাটা insert করব।

size()

ফাংশনটি কল করার মুহূর্ত পর্যন্ত ভেক্টরে কতগুলো এলিমেন্ট আছে তা রিটার্ন করে। কিছু না থাকলে 0 রিটার্ন করবে।

empty()

ভেক্টরটি যদি empty হয়, অর্থাৎ কোন এলিমেন্ট নেই, সাইজ 0, তাহলে এটি true রিটার্ন করবে, অন্যথায় false রিটার্ন করবে।

begin(), end()

begin() ফাংশনটি ভেক্টরের শুরুর iterator রিটার্ন করে, আর end() তার উলটা অর্থাৎ শেষের iterator রিটার্ন করে। iterator অনেকটা পয়েন্টারের মত।

নিচে এই ফাংশনগুলোর ব্যবহার দেখানো হলঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int value, inputSize;
vector <int> myVector;
cin >> inputSize;
if(myVector.empty()) cout << "Vector is empty." << endl;
cout << "Size before insertion: " << myVector.size() << endl;
for(int i = 0; i < inputSize; i++) {
    cin >> value;
    myVector.push_back(value);  // Inserts the value
}
cout << "Insertion complete." << endl;
if(!myVector.empty()) cout << "Vector is not empty." << endl;
cout << "Size after insertion: " << myVector.size() << endl;
for(int i = 0; i < myVector.size(); i++) {
    cout << myVector[i] << ' ';
}
cout << endl;
sort(myVector.begin(), myVector.end());
for(int i = 0; i < myVector.size(); i++) {
    cout << myVector[i] << ' ';
}
cout << endl;
Input:
10
8 9 4 1 3 5 0 2 6 7
Output:
Vector is empty.
Size before insertion: 0
Insertion complete.
Vector is not empty.
Size after insertion: 10
8 9 4 1 3 5 0 2 6 7
0 1 2 3 4 5 6 7 8 9

মূলত এই কয়টি ফাংশনই অনেক বেশি ব্যবহৃত হয়। এছাড়া আরো অনেক ফাংশন আছে, constructor আছে, এগুলো অনেক বিস্তারিতভাবে এই লিংক থেকে জানা যাবে।

আরেকটি বিষয় বেশ কাজের, সেটি হল bool টাইপের ভেক্টর। true/false রাখার জন্য আমরা bool অ্যারে ডিক্লেয়ার করে থাকি। সে জায়গায় যদি আমরা ভেক্টর ডিক্লেয়ার করি তাহলে অনেক মেমরি বেঁচে যায়। কারণ যদিও bool ডাটা টাইপটা 8 bit সাইজের, bool ভেক্টর প্রতি এলিমেন্টের জন্য 1 bit জায়গা ব্যবহার করে। অর্থাৎ মেমরি ব্যবহার ৮ ভাগের ১ ভাগ হয়ে যাচ্ছে।

যদি 2D অ্যারের বিকল্প হিসেবে আমরা ভেক্টর ব্যবহার করতে চাই, তখন সিন্ট্যাক্সটা একটু অন্যরকম হবে।

vector < vector <int> > myVector;

অর্থাৎ int টাইপের ভেক্টরের ভেক্টর! myVector একটা ভেক্টর, যার প্রতিটি এলিমেন্ট হল vector <int>, আরেকটি ভেক্টর, যার প্রতিটি এলিমেন্ট হল int! এখন myVector এ push_back করতে হলে একটা ভেক্টরকে আর্গুমেন্ট হিসেবে পাঠাতে হবে। ঝামেলা মনে হচ্ছে? যদি ঝামেলা মনে হয় তাহলে এটার বিকল্প হিসেবে যেটা করা যায় তা হল ভেক্টরের অ্যারে ডিক্লেয়ার করা যায়। vector <int> myVector[10]; এভাবে। এখন myVector[0], myVector[1], … এগুলো প্রত্যেকে একেকটা ভেক্টর।

এই হল ভেক্টরের প্রাথমিক খুটিনাটি। আরো বিস্তারিত পাওয়া যাবে cplusplus.com এ!

C++ STL :: pair

লেখাটি আনা হয়েছে জুবায়ের ভাইয়ের ব্লগ থেকে

কিছু কথাঃ

যারাই কিনা সি/সি++ নিয়ে বেশকিছুদিন নাড়াচাড়া করছেন, তারা প্রায় সবাই সি এর একটা দারুন জিনিস স্ট্রাকচার-এর সাথে পরিচিত, আর, আরেকটু অ্যাডভান্সডরা তো মনে হয় অলরেডি সি++ এর ক্লাস নামের জিনিসটা মোয়া বানিয়ে ফেলেছে।

সি একটা ফাটাফাটি ল্যাঙ্গুয়েজ আর সি++ এর কথা তো বলাই বাহুল্য। যারা অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং এর সুবাতাস পেয়েছেন তারা এটা আরো ভাল করে জানেন। আমরা জানি, সি++ এ কিছু প্রিমিটিভ ডাটা টাইপ ডিফাইন করা আছে, যাদের উপরে আমরা খুব সহজেই বিভিন্ন অপারেশন চালাতে পারি, কিন্তু মাঝে মাঝে এই রকমের ডাটা টাইপের ব্যবহার আমাদের কে ঝামেলায় ফেলতে পারে। যেমন, মনে করা যাক আমাকে একটা 2D গ্রিডের কিছু পয়েন্ট স্টোর করতে হবে। শুধু int টাইপের অ্যারে দিয়ে এটা মেইনটেইন করাটা বেশ মুশকিলের ব্যাপার। কিন্তু যদি এরকম একটা ডাটা টাইপ থাকতো ‘point’ নামে, যা কিনা (x, y) আকারে কো-অর্ডিনেট রাখতে পারতো!!! সি এ সেই ব্যাবস্থা করেই দেয়া আছে, যেন প্রোগ্রামাররা চাইলেই ইচ্ছা মতো ডাটা টাইপ বানিয়ে নিতে পারেন, আর সি++ এটাকে আরেক ডিগ্রি এগিয়ে নিয়ে গেছে। এখানে প্রোগ্রামার চাইলে তার বানানো ডাটা টাইপের আচার আচরণও বলে দিতে পারেন।

কিন্তু, প্রশ্ন হল, এটা কন্টেস্ট প্রোগ্রামিং এর জন্য কতটা সুইটেবল?

পেয়ার কি?

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

আমাকে একগাদা 2D পয়েন্ট থাকবে, আমাকে সেগুলা সর্ট করতে হবে। এখন, আমি চাইলেই একটা স্ট্রাকচার বানাতে পারিঃ

1
struct point { int x, y; } P[128];

অর্থাৎ, P[] হল একটা পয়েন্ট টাইপের অ্যারে, এখন এটাকে সর্ট করতে হবে। কাজ তো সোজাই, অ্যালগোরিদমের হেডারটা ইনক্লুড করে sort() মেরে দিলেই হয়… কিন্তু আসলে এটা এত সিম্পল না, কারন, sort() একটা টেমপ্লেট ফাংশন, মানে যে কোন ডাটাটাইপের জন্য কাজ করবে, কিন্তু তার আগে তাকে ডাটাটাইপের ভাবগতি জানাতে হবে। আমি ‘struct point’ দিয়ে কি বুঝাতে চাই, এটা তার বুঝার কোন কারনই নাই যদি না আমি বলে দেই। তার মানে খালি sort() কে ডাকলেই চলবে না, তার সাথে অপারেটর ওভারলোড বা কম্পেয়ার ফাংশন লিখে বুঝিয়ে দিতে হবে যে আমি আসলে কি চাই। আর এখানেই std::pair এর প্লাস পয়েন্ট।

std::pair জিনিশটা তেমন কিছুই না, জাস্ট দুইটা ভ্যালু কে একসাথে করে রাখে, যেখানে ভ্যালু দুইটা যে কোন টাইপের হতে পারে, ডিফারেন্ট টাইপেরও হতে পারে। পেয়ার ক্লাসটা ডিফাইন করা থাকে std <utility> নামের হেডারে।

1
2
#include <utility>
using namespace std;

pair ক্লাসের ডেফিনিশনঃ

1
2
3
4
5
6
7
template <class T1, class T2> struct pair {
    T1 first;
    T2 second;
    pair(): first(T1()), second(T2()) {}
    pair(const T1 &x, const T2 &y): first(x), second(y) {}
    template <class U, class V> pair(const pair<U, V> &p): first(p.first), second(p.second) {}
};

যাদের টেমপ্লেট সম্পর্কে আইডিয়া নাই, তাদের জন্য অল্প কথায়, টেমপ্লেট একটা সিস্টেম যেখানে কোন অ্যাকচুয়াল টাইপের জন্য ডিজাইন থাকে না, বরং যে কোন টাইপের জন্য তার একটা ইন্সট্যান্স তৈরি করা যায়। টেমপ্লেট শিখতে হলে এই পেজটি দেখা যেতে পারে।

pair এর সুবিধা হল, এটা টেমপ্লেট টাইপ, তাই STL algorithm এর ফাংশন গুলার জন্য সাধারনতঃ pair অবজেক্ট গুলার আলাদা করে কোন পরিচয় দেওয়ার দরকার পড়ে না। যেমন আগের প্রবলেমে জাস্ট sort() কল দিলেই চলে, সে অটমেটিক প্রথমে পেয়ারের প্রথম মেম্বার, তার পর ২য় টা, তার পর ৩য় টা, এভাবে বাকি গুলা কম্পেয়ার করে দেখবে। প্রোগ্রামারকে এর জন্য কিছুই বলতে হবে না।

কিভাবে ব্যবহার করে?

pair নিয়ে কাজ করতে চাইলে <utility> হেডার ইনক্লুড করা উচিৎ, অবশ্য যে কোন STL হেডার ইনক্লুড করলেই pair ব্যবহারের সুবিধা পাওয়া যায়। আর pair টাইপের অবজেক্ট সহজে ক্রিয়েট করার জন্য <utility> হেডারের make_pair() ফাংশন ব্যবহার করা যায়। আর pair-এর ১ম আর ২য় এলিমেন্টকে যথাক্রমে .first আর .second মেম্বার দিয়ে অ্যাক্সেস করা যায়। নিচে একটা উদাহরন দেখানো হলঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <utility>
using namespace std;
int main() {
    // simple constructions
    pair< int, int > px, py;
    pair< int, int > p1(23, 43);
    pair< int, int > p2 = pair< int, int >(234, 534);
    px = p1;
    py.first = p2.first * px.second, py.second = p2.second * px.first;
    cout << "py: (" << py.first << ", " << py.second << ")\n";
    
    // bit more complex
    pair< pair< int, int >, pair< int, int > > p3;
    p3 = pair< pair<int, int>, pair< int, int > > (px, py);
    cout << "p3: ((";
    cout << p3.first.first << ", " << p3.first.second << "), (";
    cout << p3.second.first << ", " << p3.second.second << "))\n";
    
    // using make_pair()
    pair< double, pair< string, int > > p4;
    p4 = make_pair(3.14159, make_pair("pi", 5) );
    cout << "this is " << p4.second.first << ", value: " << p4.first;
    cout << " precision: " << p4.second.second << " digits\n";
    return 0;
}

pair নিয়ে সবচেয়ে বেশি যে কথাটা শোনা যায় তা হল, মানুষজন নাকি .first.second.second.first…. এরকম চেইন লিখতে লিখতে টায়ার্ড হয়ে যায়। কিন্তু একটু কাজ করেই এইটাকে সহজ করে ফেলা যায়, যেমন, নিচের কোডে pair কে #define করে নেওয়া হয়েছেঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
#define pii pair< int, int >
#define ppi pair< pii, int >
#define ff first
#define ss second
int main() {
    ppi p1;
    pii p2;
    cin >> p2.ff >> p2.ss;
    p1 = ppi( p2, p2.ss * p2.ff );
    cout << "entry: " << p1.ff.ff << ", " << p1.ff.ss << endl;
    cout << "product: " << p1.ss << endl;
    return 0;
}

অন্যান্য STL কন্টেইনারের ডাটা টাইপ হিসাবেও pair ব্যবহার করা যায়। যেমন, বি.এফ.এস. অ্যালগরিদমে প্রায়ই কিউতে একজোড়া নাম্বার রাখতে হতে পারে, অথবা ডায়াকস্ট্রার অ্যালগরিদমে পুরা একটা এজকে প্রাইওরিটি কিউতে রাখার ব্যাবস্থা করতে হয়। এটাও খুব সহজেই করা যায়ঃ

1
2
3
4
5
6
7
8
#include <queue>
using namespace std;
#define pii pair< int, int >
#define edge pair< int, pii >
// edge.first is weight, edge.second is a pair indicating endpoints
queue< pii > Q;
priority_queue< edge, vector< edge >, greater< edge > > PQ;

সতর্কতাঃ

অন্যান্য সব STL অবজেক্টের মত, এখানেও একটা ব্যাপার খেয়াল করতে হবে তা হলঃ উপরের উদাহরন গুলাতে দেখা যায় কন্সট্রাকশন শেষ করার সময় মাঝে মাঝে পর পর দুইটা > ব্যবহার করতে হয়, (যেমন প্রাইওরিটি কিউ এর উদাহরনে শেষে ……greater< edge > >, এখানে শেষ ২টা > এর মাঝখানে একটা স্পেস ব্যবহার করা হয়েছে, এটা কিন্তু সৌন্দর্য বর্ধনের জন্য না। এটা না দিলে অনেক সময় কম্পাইলারের মাথা গরম হয়ে যায়। কারন সি++ এ >> আরো কয়েকটা অপারেটরের কাজ করে। আর যেসব যায়গায় দেখা যায় pair ইউজ করলে আরো ঝামেলা হয়, সেখানে নরমাল স্ট্রাকচার ব্যবহার করাটাই বেশি ভাল। এটা জেনে রাখা ভাল, আর জানলেই যে বসাতে হবে এমনও কোন কথা নাই।

ব্যবহারঃ

সাধারনতঃ STL এর টেমপ্লেট ক্লাসগুলোর ওভারলোডিং সুবিধা নেওয়ার জন্য এবং ছোটো খাটো স্ট্রাকচারের শর্টহ্যান্ড হিসাবে pair ব্যবহার করা হয়ে থাকে। এছাড়া std::map এ হাশিং এর সময় pair ব্যবহার করা হয়। প্রোগ্রামিং প্রবলেমগুলাতে গ্রাফ আর জিওমেট্রিক রিপ্রেজেন্টেশনে pair অনেক ব্যবহার করা হয়।

আশা করি যারা আগ্রহি হবে তারা এটাকে নিয়ে আরো কিছুক্ষন ঘাটাঘাটি করবে, কারন ঘাটাঘাটি খোচাখুচি করাই প্রোগ্রামিং শেখার সবচেয়ে ভাল টেকনিক।

বিস্তারিতঃ http://www.cplusplus.com/reference/std/utility/pair/

C++ STL :: vector

লেখাটি আনা হয়েছে জুবায়ের ভাইয়ের ব্লগ থেকে

ভেক্টর :

অ্যারে আমাদের সবারই বিশেষভাবে পরিচিত, এবং সবার খুবই প্রিয় একটা ডাটা-স্ট্রাকচার হল অ্যারে। কোন কোডে অ্যারে ব্যবহার করতে পারলেই কেমন যেন শান্তি শান্তি লাগে… অ্যারের সবচেয়ে আকর্ষনীয় ফিচার মনে হয় তার ইন্ডেক্সিং (মানে র‍্যান্ডম অ্যাকসেস)। কিন্তু যতই দিন যায়, সব কেমন যেন কঠিন হয়ে যায়… তাইতো আজকাল অ্যারে নিয়েও মাঝে মাঝে ঝামেলায় পড়তে হয়, বিশেষতঃ যখন কিনা অ্যারের আকার আকৃতি রানটাইমে পরিবর্তন করার দরকার হয়। কারন, অ্যারে একবার ডিক্লেয়ার করলে রানটাইমে C++ এ তা আর ছোট-বড় করা যায় না। আর এখানেই ভেক্টরের আবির্ভাব।

ভেক্টরকে বলা যেতে পারে একটা ডায়নামিক অ্যারে, দরকার মত যেটার সাইজ বাড়ানো কমানো যায়। আবার অ্যারের মত মাল্টি ডাইমেনশন এবং ইন্ডেক্সিং সুবিধাগুলো ব্যবহার করা যায়।

কিভাবে ব্যবহার করবো?

ভেক্টর C++ STL এর একটা কন্টেইনার ক্লাস। অর্থাৎ এটাও একটা টেমপ্লেট ক্লাস, যার কারনে এটাকে অন্য টেমপ্লেটের সাথে সহজেই ব্যবহার করা যায়। তবে সবার প্রথমে দরকার স্ট্যান্ডার্ড হেডার vector ইনক্লুড করাঃ

1
2
#include <vector>
using namespace std;

এর পরের কাজ হল ভেক্টর ডিক্লারেশন, সেটাও আবার কয়েকভাবে করা যায়, তবে সাধারন স্টাইল হলঃ vector < type > Var; এখানে type হতে পারে যে কোন টাইপ, অন্য কোন ইউজার ডিফাইনড টাইপ, টেমপ্লেট ক্লাস টাইপ, বেসিক টাইপগুলো। ভেক্টর ডিক্লেয়ার করার সাধারন সিন্ট্যাক্সগুলো নিচে দেখানো হলঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// constructing vectors
#include <iostream>
#include <vector>
using namespace std;
int main () {
    // constructors used in the same order as described above:
    vector<int> first;                                // empty vector of ints
    vector<int> second (4,100);                       // four ints with value 100
    vector<int> third (second.begin(),second.end());  // iterating through second
    vector<int> fourth (third);                       // a copy of third
    
    // the iterator constructor can also be used to construct from arrays:
    int myints[] = {16,2,77,29};
    vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );
    cout << "The contents of fifth are:";
    for (unsigned i=0; i < fifth.size(); i++) cout << " " << fifth[i]; cout << endl;
    
    return 0;
}

ভেক্টর ডিক্লেয়ার করার সময় [] আর () অপারেটরের মধ্যে পার্থক্যটা খেয়াল করা উচিতঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
#include <vector>
using namespace std;
int main () {
    // use of [] and ()
    vector<int> v1[100]; // creates an array of vectors, i.e. 100 vectors
    vector<int> v2(100); // creates 1 vector of size 100
    // creating a 2D array 100x2 where each element is a vector,
    // so in total, it is a 3D structure, as vector itself is 1D
    vector<int> v3[100][2];
    return 0;
}

উপরের কোডে যেমন দেখা গেল… চাইলেই আমরা ভেক্টরের অ্যারে তৈরি করতে পারি (এটা ভেক্টরের অন্যতম একটা গুরুত্বপূর্ন ব্যবহার)। কিন্তু এছাড়াও ভেক্টরে দিয়ে মাল্টিডাইমেনশনাল স্ট্রাকচার তৈরি করা যায়, যেখানে প্রতিটা ডাইমেনশনই ডায়নামিকঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
int main () {
    // multidimentional vector
    vector< vector< int > > V2D;
    // the above is basically a vector where each element is a vector,
    // we can also increase the level of nesting if needed.
    // demonstrate a triangular structure..
    vector< int > temp;
    for(int i = 0; i < 10; i++) {
        temp.clear();
        for(int j = 0; j <= i; j++) {
            temp.push_back(i+1);
        }
        V2D.push_back(temp);
    }
    return 0;
}

হুম, তো আমরা খালি একটা ভেক্টরের মধ্যে আরেকটা ভেক্টর পুশ করলাম, ফলাফল 2D ভেক্টর। আগেই বলা হয়েছে, ভেক্টর একটা টেমপ্লেট ক্লাস, তাই, যে কোন টাইপ নিয়ে এটা বানানো যায়। যেমন চাইলেই আমরা কিউএর একটা ভেক্টর বানাতে পারিঃ vector< queue > Vq;

ভেক্টর অ্যাকসেসঃ

ভেক্টর দুইভাবে অ্যাকসেস করা যায়, ইটারেটরের সাহায্যে, ইন্ডেক্সিং-এর সাহায্যে। ইটারেটরের সাহায্যে করলে কিঞ্চিত ফাস্ট হয়, ভেক্টরের ইটারেটর একটা র‍্যান্ডম অ্যাকসেস ইটারেটর।

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <vector>
using namespace std;
int main () {
    vector< vector< int > > V2D;
    
    // creating a 2D triangular structure
    for(int i = 0; i < 10; i++) {
        vector< int > temp;
        for(int j = 0; j <= i; j++) {
            temp.push_back(i);
        }
        V2D.push_back(temp);
    }
    // using iterator
    cout << "using iterator:\n";
    vector< vector< int > > :: iterator outer;
    vector< int > :: iterator inner;
    for(outer = V2D.begin(); outer != V2D.end(); outer++) {
        for(inner = outer->begin(); inner != outer->end(); inner++) {
            cout << *inner << ' ';
        }
        cout << '\n';
    }
    // using index
    cout << "\nusing indexes:\n";
    for(unsigned i = 0; i < V2D.size(); i++) {
        for(unsigned j = 0; j < V2D[i].size(); j++) {
            cout << V2D[i][j] << ' ';
        }
        cout << '\n';
    }
    return 0;
}

সাধারনত কেউ ভেক্টরে ইটারেটর ব্যবহার করে না, কারন ইন্ডেক্সের ব্যবহার অনেক সহজ, এবং অধিকাংশ C++ কোডারের পয়েন্টারের প্রতি আজন্মের ভয়। কিন্তু ইটারেটরের ব্যবহার আরো বেশি সিগ্নিফিক্যান্ট, এবং অর্থবহ। অবশ্য কিভাবে ব্যবহার করতে হবে সেটা কোডারের ব্যক্তিগত ইচ্ছা। যার যেটায় সুবিধা সেটাই ব্যবহার করা উচিত। উপরের কোডে ভ্যালুগুলো চাইলে অ্যারের মত করে মডিফাইও করা যাবে, যেমন, V2D[i][j] = 100; লিখে দিলেই ওই পজিশনটার মান ১০০ হয়ে যাবে।

পুশব্যাক, পপব্যাক, সাইজ, এম্পটি

আগের কোডটায় আমরা দেখলাম পুশব্যাক দিয়ে ভেক্টরে ভ্যালু ইন্সার্ট করা হচ্ছে, তাই আর নতুন করে সেটা দেখনোর কিছু নাই, push_back() ফাংশনের সাহায্যে ভেক্টরের শেষে একি ধরনের একটা আইটেম অ্যাড করা যায়, আর pop_back() দিয়ে ভেক্টরের শেষ থেকে একটা আইটেম হাওয়া করে দেওয়া যায়। অন্যান্য STL মেম্বারের মত ভেক্টরের size() আর empty() ফাংশন দুইটাও আইডেন্টিক্যাল। নিচের কোডে এগুলোর ব্যবহার দেখানো হলঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
using namespace std;
int main () {
    vector< int > simple;
    for(int i = 1; i < 10; i++) {
        simple.push_back(i*100);
        cout << "inserting: " << simple.back() << endl;
    }
    cout << "-------------------\n";
    while(!simple.empty()) {
        cout << "size: " << simple.size();
        cout << " last element: " << simple.back() << endl;
        simple.pop_back();
    }
    cout << "vector empty\n";
    return 0;
}

রিসাইজ, ইরেজ, ক্লিয়ার এবং রিসাইজ নিয়ে কিছু কাহিনীঃ

ভেক্টরের সাইজ মডিফায় করা যায় এরকম কিছু মেম্বার হল resize(), erase(), clear(), এদের মধ্যে clear() এর ব্যবহার অন্য যে কোন কন্টেইনার ক্লাসের মতই, সব এলিমেনত ডিলিট করে দেয়, ফলাফম সাইজ ০ হয়ে যায়। আর resize() ফাংশন দিয়ে ভেক্টরের সাইজ পরিবর্তন করা যায়। erase() এর কাজ কোন এলিমেন্ট বা একটা রেঞ্জ ডিলিট করা যায়। erase() এর দুইটা ফরম্যাট আছে, erase(iterator pos), erase(iterator first, iterator last), অর্থাৎ কোন ভ্যালুর সাপেক্ষে ডিলিট করা যায় না, তার ইটারেটর পজিশন দিতে হবে, আর দ্বিতীয় ধরনে ভেক্টরের [first, last) এই রেঞ্জের সব আইটেম ডিলিট করে দিবে। বলাই বাহুল্য, আজগুবি ইটারেটর দিলে রানটাইম এররর খেয়ে বসে থাকতে হবে…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>
using namespace std;
int main () {
    unsigned int i;
    vector<unsigned int> myvector;
    // set some values (from 1 to 10)
    for (i=1; i<=10; i++) myvector.push_back(i);
    // erase the 6th element
    myvector.erase (myvector.begin()+5);
    // erase the first 3 elements:
    myvector.erase (myvector.begin(),myvector.begin()+3);
    cout << "myvector contains:";
    for (i=0; i<myvector.size(); i++)
        cout << " " << myvector[i];
    cout << endl;
    // clear all
    myvector.clear();
    cout << "size: " << myvector.size() << endl;
    // resize and then check size
    myvector.resize(10);
    cout << "size: " << myvector.size() << endl;
    return 0;
}

কিছু বিষয়ে এখানে সতর্ক হতে হবে, যেমনঃ resize() ফাংশনটা ভেক্টরের আগের অবস্থাত কোন তোয়াক্কা না করেই তার সাইজ চেঞ্জ করবে, ফলে কিছু এলিমেন্ট বাদও পড়তে পারে, আবার কিছু জায়গা খালিও থাকতে পারে। কিন্তূ ভেক্টরের সাইজ চেক করলে নতুন সাইজ এ পাওয়া যাবে, যদিও, সেটা হয়তো একটা খালি ভেক্টর ছিল। তাই, resize() এর পরে push_back() ব্যবহার করলে কোডার যাই আশা করুক না কেন, সে রিসাজকৃত স্পেসের পরেই পুশ করবে। যেমন, মনে করি, ভেক্টরে ছিল ১৮ টা আইটেম, আমি সেটাকে রিসাইজ করলাম ৫০ এ। তখন push_back() করলে সে ১৯ তম পজিশনে করবে না, করবে ৫১ তম পজিশনে (মানে ইন্ডেক্স ৫০)। একই ভাবে যদি ১২ রে রিসাইজ করতাম, তাহলেও সে ১৯ এ না করে ১৩ তে পুশ করতো। সাধারনত clear() এর অল্টারনেট হিসাবে resize() ব্যবহার করা যায়, তবে এর সাথে push_back() ব্যবহার না করাই ভাল। নিচের কোডঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <vector>
using namespace std;
int main () {
    int n, a;
    vector< int > v;
    while(cin >> n) {
        v.resize(n);
        for(a = 0; a < n; a++) {
            cin >> v[a];
        }
        for(a = 0; a < n; a++) {
            cout << v[a] << endl;
        }
    }
    return 0;
}

erase() এর ব্যাপারেও একটা কথা আছে, তা হল, এর কমপ্লেক্সিটি লিনিয়ার, তাই রান্ডম ইনসার্ট আর ডিলিটের জন্য ভেক্টর সুবিধাজনক না। x.clear() করা আর x.erase(x.begin(), x.end()) একই কথা। তাই কোডে খুব বেশি clear না মারাই ভাল।

ভেক্টরের ইটারেটর পাব কিভাবে?

উপরের কোডগুলোতে প্রায়ই দেখা গেছে begin() আর end() নামের দুটি ফাংশন। এরা যথা ক্রমে ভেক্টরের শুরু আর শেষের ইটারেটর রিটার্ন করে। মনে রাখতে হবে, STL এর যে কোন মেম্বারই একটা কমন রুল ফলো করে, তা হল, এখানে রেঞ্জ ডিফাইন করা হয় [first, last) দিয়ে, তার মানে last টা ইনক্লুডেড না। একই ভাবে end() ইটারেটর হল লাস্ট আইটেমের পরের ইটারেটর টা। এদের উলটা ফাংশন ২টা হলঃ rbegin(), rend(), যথাক্রমে রিভার্স বিগিন আর রিভার্স এন্ড ইটারেটর রিটার্ন করে।

অনেক হল…

ভেক্টর আসলে অনেক বিশাল একটা ব্যাপার, এটা কিভাবে C++ এ ইমপ্লিমেন্ট করা হয়, সেটাও আরেক মজার ব্যাপার। এক পোস্টে সব বলা সম্ভব না, আর দরকারও নাই, গুগল আছে কি করতে… তবে এই ফাংশন গুলার বাইরে কোনটাই লাগে না। এগুলার এক্সপার্ট মানেই ভেক্টরের এক্সপার্ট, তাও শেষে ভেক্টরের একটা বহুল ব্যবহার দেখাই, সেটা হল, অ্যাডজাসেনসি লিস্ট দিয়ে গ্রাফ রিপ্রেজেন্টেশনঃ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
using namespace std;
const int MAX = 100;
typedef pair< int, int > Edge; // to, weight
int main () {
    int n, e, i, j, u, v, w;
    vector< Edge > G[MAX]; // adjacency list for MAX vertices
    while(cin >> n >> e) {
        // n nodes in range [0,n), e edges
        for(i = 0; i < n; i++) G[i].clear(); // forget previous info
        for(i = 0; i < e; i++) {
            // directed edge from u to v with cost w
            cin >> u >> v >> w;
            G[u].push_back(Edge(v, w));
        }
        // now show the graph
        for(i = 0; i < n; i++) {
            cout << "Degree of " << i << ": " << G[i].size() << endl;
            cout << "Adjacents:\n";
            for(j = 0; j < (int)G[i].size(); j++) {
                cout << ' ' << G[i][j].first << "(" << G[i][j].second << ")\n";
            }
            cout << endl;
        }
    }
    return 0;
}

রেফারেন্সঃ

ভেক্টরের কারনে কাজ অনেক সহজ হয়ে যায়, তবে ভেক্টর কিছুটা স্লো আর বেশি মেমরি নেয়। যারা অপ্টিমাইজেশন পছন্দ করেন তাদের জন্য এটা খুব একটা মজার কিছু না।

ডিটেইলসঃ http://www.cplusplus.com/reference/stl/vector/

C++ STL :: queue

লেখাটি আনা হয়েছে জুবায়ের ভাইয়ের ব্লগ থেকে

কিউ:

আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (FIFO)। এটা C++ STL এর সবচেয়ে বেশি ব্যবহৃত কন্টেইনার ক্লাস। queue এর সামনের দিক থেকে ডাটা এক্সট্র্যাক্ট করা হয়, আর ইনসার্ট করা হয় তার বিপরীত দিক থেকে। তাই, যে সব STL কন্টেইনার push_back() আর pop_front() সাপোর্ট করে সেগুলো দিয়ে কিউ ইমপ্লিমেন্ট করা যায়, যেমন list আর deque. অবশ্য queue এর ডিফল্ট কন্টেইনার হল deque, যদি কিছু বলে না দেয়া হয়। stack এর মত queue ও একটা অ্যাডাপ্টার ক্লাস।queue ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ

#include <queue>
using namespace std;

কন্সট্রাকশনঃ

অন্যান্য কন্টেইনার ক্লাসের মত queue এর সাধারণ কন্সট্রাক্টর queue< type_t > myqueue; এই ধরনের। এছাড়া এক্সপ্লিসিট কন্টেইনার ডিক্লেয়ার করেও queue কন্সট্রাক্ট করা যায়, যেমনঃ

// constructing queues
#include <deque>
#include <list>
#include <queue>
using namespace std;
int main ()
{
    deque< int > mydeck(3,100); // deque with 3 elements
    list< int > mylist(2,200); // list with 2 elements
    
    // implicit declaration
    queue< int > first; // empty queue
    queue< int > second(mydeck); // from a mydeck
    queue< int > third(second); // from another queue
    
    // explicit declaration
    queue< int, list< int > > fourth; // empty queue
    queue< int, list< int > > fifth(mylist); // from mylist
    queue< int, deque< int > > sixth; // empty queue
    queue< int, deque< int > > seventh(mydeck); // from mydeck
    
    // initialization with operator=
    queue< int > eighth = first; // initialized with first
    return 0;
}

কমপ্লেক্সিটিঃ কন্সট্রাক্টরের সাপেক্ষে কন্সট্যান্ট, অর্থাৎ কন্টেইনারের উপরে নির্ভর করে।

পুশ আর পপঃ

queue এ ডাটা ইন্সার্ট আর এক্সট্র্যাক্ট করার জন্য ২ টা মেম্বার ফাংশন আছে, push() আর pop()। push() এর কাজ হল queue এর শেষে এলিমেন্ট ইন্সার্ট করা আর pop() এর সাহায্যে queue এর সামনে থেকে কোন এলিমেন্ট বের করে দেয়া। যেমনঃ

// queue::push/pop
#include <iostream>
#include <queue>
using namespace std;
int main()
{
    queue< int > Q;
    
    // push 5 integers
    for(int i=1; i<=5; i++) Q.push(i);
    
    // pop 5 integers
    // will be popped in the same order they were pushed
    for( ; !Q.empty() ; )
    {
        cout << Q.front() << endl;
        Q.pop();
    }
    
    return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

ফ্রন্ট আর ব্যাক

queue তে এলিমেন্ট এক্সেসের জন্য ২ টা ফাংশন হল front() আর back(); front() দিয়ে queue এর ফার্স্ট এলিমেন্ট এক্সেস করা যায়, আর back() দিয়ে লাস্ট ইন্সার্ট করা এলিমেন্ট কে পাওয়া যায়। front() আর back() এর এলিমেন্ট কে স্ট্যান্ডার্ড অপারেটর গুলর সাহায্যে মডিফাই করা যায়। যেমনঃ

// queue::front/back
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
    queue<int> myqueue;
    
    myqueue.push(77);
    myqueue.push(16);
    cout << "myqueue.front() = " << myqueue.front() << endl;
    cout << "myqueue.back() = " << myqueue.back() << endl;
    
    // modify front element
    myqueue.front() -= myqueue.back();
    cout << "myqueue.front() is now " << myqueue.front() << endl;
    
    // modify back element
    myqueue.back() += myqueue.front();
    cout << "myqueue.back() is now " << myqueue.back() << endl;
    return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

কিউ কি খালি?

queue এ এই মুহূর্তে কত গুলা এলিমেন্ট আছে সেটা জানা যায় size() ফাংশনের মাধ্যমে, আর empty() ফাংশন টা boolean, queue খালি থাকলে true দেয়, না হলে false; queue খালি কি না, সেটা চেক করা হয় empty() দিয়ে, কখনই size() এর ভ্যালু ০ কিনা এটা দেখে queue খালি কিনা, সেই টেস্ট করা উচিৎ না, আর queue তে pop() করার আগে আবশ্যই দেখে নিতে হবে queue এ কোন এলিমেন্ট আছে কিনা, তা না হলে run-time error হতে পারে। নিচের কোডে size() আর empty() এর প্রয়োগ দেখানো হলঃ

// queue::size/empty
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
    queue<int> Q;
    
    // just push some elements
    for(int i = 0; i < 5; i++) Q.push(i*i);
    
    cout << "Queue has " << Q.size() << " elements" << endl;
    
    Q.pop(); // not a good way, first check for Q.empty()
    
    if(!Q.empty()) Q.pop(); // this is the porper way
    
    while(!Q.empty()) Q.pop(); // pop all element
    
    if(Q.size()==0) cout << "Q is empty" << endl; // not a good way
    if(Q.empty()) cout << "Q is empty" << endl; // this is the proper way
    
    return 0;
}

কমপ্লেক্সিটিঃ কন্সট্যান্ট।

Create a free website or blog at WordPress.com.

Up ↑