হাবিজাবি হিজিবিজবিজ

ভেক্টরঃ

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

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

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

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

#include <vector>
using namespace std;

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

// 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;
}

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

#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;
}

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

#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;

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

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

#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() ফাংশন দুইটাও আইডেন্টিক্যাল। নিচের কোডে এগুলোর ব্যবহার দেখানো হলঃ

#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) এই রেঞ্জের সব আইটেম ডিলিট করে দিবে। বলাই বাহুল্য, আজগুবি ইটারেটর দিলে রানটাইম এররর খেয়ে বসে থাকতে হবে…

#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() ব্যবহার না করাই ভাল। নিচের কোডঃ

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

#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/