STL : vector

ভেক্টর হল স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরীর একটা element. স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী হল c++ এর একটা ফিচার যেখানে অনেক Data Structure built-in দেওয়া আছে। আমরা চাইলে সেখান থেকে আমাদের পছন্দমত element নিয়ে কাজ করতে পারি। তবে শর্ত হল আমাদের ওদের operation গুলো জানতে হবে। বর্তমান সময়ের কনটেস্ট প্রোগ্রামারদের মধ্যে স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী খুবই জনপ্রিয় আর TopCoder এ প্রোগ্রামিং কনটেস্ট এর পূর্ব শর্ত হল তোমাকে অবশ্যই স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরী সম্পর্কে ধারণা থাকতে হবে।ভবিষ্যতে স্ট্যার্ন্ডাড টেমপ্লেট লাইব্রেরীর আরো element নিয়ে আলোচনা করা হবে। আজকের আলোচ্য বিষয় হল ভেক্টর।
ভেক্টর জানার আগে তোমাকে একটু টেমপ্লেট সম্পর্কে জানতে হবে। সাধারণ কথায় টেমপ্লেট হল একটা কমন ফরম্যাট যা সব কিছুতে ব্যবহার করা যাবে। ভেক্টর
এর template হল এরকম

vector< datatype > objects/variables;

এখানে datatype হল তুমি কোন type এর ডাটা ব্যবহার করতে চাও। যদি integer type এর ডাটা হয় তাহলে deceleration হবে এরকমঃ

vector< int > v;

এখানে V হল ভেক্টর ডাটা টাইপের একটা variable. ভেক্টর হল অনেকটা array এর মত। তবে এর অনেক সুবিধা আর ফিচার আছে যা ভেক্টরকে অ্যারে থেকে আলাদা করে তুলেছে।আমি যদি ভেক্টরের ভেতর ডাটা ঢুকাতে চাই তাহলে array এর মত indexing ছাড়াও আর একটা মজার বিষয় আছে সেটা হল push_back(); আমি যদি ডাট ঢুকাতে চাই আর push_back(); দিয়ে ডাটা ঢুকাই তাহলে ১ম ডাটার index হবে ০, ২য় ডাটার ১ এভাবে ডাটা ঢুকতে থাকবে।জিনিসটা হবে এরকমঃ

vector< int > v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

তাহলে আমদের ভেক্টরে ডাটা ঢুকান শেষ এবার আমরা একটু এটা নিয়ে খেলা করবো। আমাদের ডাটা ঢুকানোর পর মনে হল যে আমরা ৪ এর জায়গায় ভুল করে ২ ঢুকিয়ে ফেলেছি। কোন চিন্তা নেই। খালি লিখে দাওঃ

v[1] = 4;

ব্যস ডাটা ঠিক হয়ে গেল।
এবার মনে কর আমাদের ১০০ সাইজের একটা ভেক্টর লাগবে যাতে সবগুলো ০ থাকবে। তাহলে কোডটা হবে এরকমঃ

vector< int > v(100,0);

তুমি চাইলে -1 দিয়েও initialize করতে পার।সেক্ষেত্রে ০ এর জায়গায় -১ বসিয়ে দাও।

এবার ধরো একটা array আছে। তাকে ধরে নিয়ে ভেক্টরের ভেতর ঢুকাতে হবে। কাজটা হবে এরকমঃ

 int array [] = {5, 4, 1, 7, 9, 13, 32, 5, 71};
 unsigned int array_length=sizeof (array) /sizeof(int);
 vector <int> v ( array, array + array_length );

ব্যস কাজ হয়ে গেল।
এবার ভেক্টরের ভেতর অনেক element ঢুকে গেছে আমাদের মনে হল একটু সর্ট করা দরকার। খালি লিখে দাও।

sort(v.begin().v.end());

দেখ ম্যাজিক ডাটা সব sort হয়ে গেছে। কি মজা তাই না আগে ডাটা সর্ট অ্যালগোরিদম লিখতে হাত ব্যাথা হয়ে যেত আর complexity ছিল কত বেশি আর এখন কত মজা।
যদি ক্লান্ত হয়ে যাও তাহলে আর কষ্ট করো না খালি ভেক্টরটা পরিষ্কার করে ফেল। এভাবেঃ

v.clear();

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
    vector<int> v;
    v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);
    do{
    for(int i=0;i<5;i++)
        cout<<v[i]<<" ";
        puts("");
    }while(next_permutation (v.begin(),v.end() ));
    return 0;
}

Sample কোডটা এরকম হবে তাই না। এখানে next_permutation algorithm হেডারের একটা প্রোপার্টি।

এবার ধর ভেক্টরের মধ্যে কোন ডাটা আছে কিনা তা খুজে বের করতে হবে সেক্ষেত্রে সবচেয়ে কাজের জিনিস হল binary search. এবার আমরা একটা ভেক্টরের ভেতর binary search চালাব। আর ডাটা খুজবো। (binary search কি সেটা নিয়ে আর একদিন আলোচনা করবো)
তবে binary search চালানোর একটা শর্ত আছে। তোমার ডাটাগুলো অবশ্যই ascending অথবা descending order এ sorted অবস্থায় থাকতে হবে। তা না হলে উত্তর ভুল আসতে পারে।
কোডাটা হবে এরকমঃ

int key = 9;
    if ( binary_search ( v.begin (), v.end (), key ) )
        printf ("key : %d found\n", key);
    else
        printf ("key : %d not found\n", key);

যদি আগের ভেক্টরের ডাটা ব্যবহার করি তাহলে output হবে key : 9 not found

কেউ টিউটোরিয়ালটা বুঝে থাকলে Age sort প্রবলেমটা solve করে ফেলতে পার।

আলী আকবরকে অসংখ্য ধন্যবাদ তার মূল্যবান পরামর্শ দিয়ে পোস্টটাকে আরো সমৃদ্ধ করার জন্য।

আজ এ পর্যন্তই আগামীতে আবার দেখা হবে। সে পর্যন্ত সবাই ভাল থাকবে।
হ্যাপি ভেক্টরিং
বিঃদ্রঃ বুঝতে কারও কোন সমস্যা হলে বা গঠন মূলক সমালোচনা থাকলে মন্তব্য অংশে জানাতে অনুরোধ করছি।