ভেক্টরঃ
অ্যারে আমাদের সবারই বিশেষভাবে পরিচিত, এবং সবার খুবই প্রিয় একটা ডাটা-স্ট্রাকচার হল অ্যারে। কোন কোডে অ্যারে ব্যবহার করতে পারলেই কেমন যেন শান্তি শান্তি লাগে… অ্যারের সবচেয়ে আকর্ষনীয় ফিচার মনে হয় তার ইন্ডেক্সিং (মানে র্যান্ডম অ্যাকসেস)। কিন্তু যতই দিন যায়, সব কেমন যেন কঠিন হয়ে যায়… তাইতো আজকাল অ্যারে নিয়েও মাঝে মাঝে ঝামেলায় পড়তে হয়, বিশেষতঃ যখন কিনা অ্যারের আকার আকৃতি রানটাইমে পরিবর্তন করার দরকার হয়। কারন, অ্যারে একবার ডিক্লেয়ার করলে রানটাইমে C++ এ তা আর ছোট-বড় করা যায় না। আর এখানেই ভেক্টরের আবির্ভাব।ভেক্টরকে বলা যেতে পারে একটা ডায়নামিক অ্যারে, দরকার মত যেটার সাইজ বাড়ানো কমানো যায়। আবার অ্যারের মত মাল্টি ডাইমেনশন এবং ইন্ডেক্সিং সুবিধাগুলো ব্যবহার করা যায়।
কিভাবে ব্যবহার করবো?
ভেক্টর C++ STL এর একটা কন্টেইনার ক্লাস। অর্থাৎ এটাও একটা টেমপ্লেট ক্লাস, যার কারনে এটাকে অন্য টেমপ্লেটের সাথে সহজেই ব্যবহার করা যায়। তবে সবার প্রথমে দরকার স্ট্যান্ডার্ড হেডার vector ইনক্লুড করাঃ
1
2
| #include <vector>using namespace std; |
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;} |
ভেক্টর অ্যাকসেসঃ
ভেক্টর দুইভাবে অ্যাকসেস করা যায়, ইটারেটরের সাহায্যে, ইন্ডেক্সিং-এর সাহায্যে। ইটারেটরের সাহায্যে করলে কিঞ্চিত ফাস্ট হয়, ভেক্টরের ইটারেটর একটা র্যান্ডম অ্যাকসেস ইটারেটর।
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;} |
পুশব্যাক, পপব্যাক, সাইজ, এম্পটি
আগের কোডটায় আমরা দেখলাম পুশব্যাক দিয়ে ভেক্টরে ভ্যালু ইন্সার্ট করা হচ্ছে, তাই আর নতুন করে সেটা দেখনোর কিছু নাই, 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;} |
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;} |
ভেক্টরের ইটারেটর পাব কিভাবে?
উপরের কোডগুলোতে প্রায়ই দেখা গেছে 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, weightint 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 :: pair
অক্টোবর 1, 2010
8 comments
কিছু কথাঃ
যারাই কিনা সি/সি++ নিয়ে বেশকিছুদিন নাড়াচাড়া করছেন, তারা প্রায় সবাই সি এর একটা দারুন জিনিস স্ট্রাকচার-এর সাথে পরিচিত, আর, আরেকটু অ্যাডভান্সডরা তো মনে হয় অলরেডি সি++ এর ক্লাস নামের জিনিসটা মোয়া বানিয়ে ফেলেছে।সি একটা ফাটাফাটি ল্যাঙ্গুয়েজ আর সি++ এর কথা তো বলাই বাহুল্য। যারা অবজেক্ট ওরিয়েন্টেড প্রোগ্রামিং এর সুবাতাস পেয়েছেন তারা এটা আরো ভাল করে জানেন। আমরা জানি, সি++ এ কিছু প্রিমিটিভ ডাটা টাইপ ডিফাইন করা আছে, যাদের উপরে আমরা খুব সহজেই বিভিন্ন অপারেশন চালাতে পারি, কিন্তু মাঝে মাঝে এই রকমের ডাটা টাইপের ব্যবহার আমাদের কে ঝামেলায় ফেলতে পারে। যেমন, মনে করা যাক আমাকে একটা 2D গ্রিডের কিছু পয়েন্ট স্টোর করতে হবে। শুধু int টাইপের অ্যারে দিয়ে এটা মেইনটেইন করাটা বেশ মুশকিলের ব্যাপার। কিন্তু যদি এরকম একটা ডাটা টাইপ থাকতো ‘point’ নামে, যা কিনা (x, y) আকারে কো-অর্ডিনেট রাখতে পারতো!!! সি এ সেই ব্যাবস্থা করেই দেয়া আছে, যেন প্রোগ্রামাররা চাইলেই ইচ্ছা মতো ডাটা টাইপ বানিয়ে নিতে পারেন, আর সি++ এটাকে আরেক ডিগ্রি এগিয়ে নিয়ে গেছে। এখানে প্রোগ্রামার চাইলে তার বানানো ডাটা টাইপের আচার আচরণও বলে দিতে পারেন।
কিন্তু, প্রশ্ন হল, এটা কন্টেস্ট প্রোগ্রামিং এর জন্য কতটা সুইটেবল?
পেয়ার কি?
কন্টেস্ট প্রোগ্রামিং-এ সাধারনতঃ খুব কমপ্লেক্স ডাটা টাইপ বানাতে হয় না। সেখানে বেশি প্রয়োজন খুব দ্রুত আর নির্ভুল কোডিং। যেমন, প্রায়ই দেখা যায়, একটা গ্রাফের এজ গুলো স্টোর করতে হবে, বা জিয়োমেট্রির প্রবলেমের জন্য কো-অর্ডিনেট নিয়ে কাজ করতে হবে, কখনো বা দেখা যায় কিছু স্ট্রিং-এর জন্য কিছু নাম্বার দিতে হবে, অথবা একগাদা ডাটা বিভিন্ন ক্রাইটেরিয়ার ভিত্তিতে সর্ট বা সার্চ করতে হবে। সাধরনতঃ এসব ক্ষেত্রে প্রোগ্রামার যদি নিজে থেকে ডাটাটাইপ বানাতে যায়, কোন সন্দেহ নাই তাতে তার মূল্যবান কিছু সময় নষ্ট হবে। যেমন, নিচের প্রবলেমটা দেখিঃআমাকে একগাদা 2D পয়েন্ট থাকবে, আমাকে সেগুলা সর্ট করতে হবে। এখন, আমি চাইলেই একটা স্ট্রাকচার বানাতে পারিঃ
1
| struct point { int x, y; } P[128]; |
std::pair জিনিশটা তেমন কিছুই না, জাস্ট দুইটা ভ্যালু কে একসাথে করে রাখে, যেখানে ভ্যালু দুইটা যে কোন টাইপের হতে পারে, ডিফারেন্ট টাইপেরও হতে পারে। পেয়ার ক্লাসটা ডিফাইন করা থাকে std <utility> নামের হেডারে।
1
2
| #include <utility>using namespace std; |
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;} |
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 secondint 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;} |
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 endpointsqueue< 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 :: priority_queue
অগাষ্ট 17, 2010
3 comments
প্রায়োরিটি কিউঃ
সব ডাটা-স্ট্রাকচারই যে ধোয়া তুলসি পাতা, এইটা বলা যায় না, বিশেষতঃ যখন “জোর যার মুল্লুক তার” টাইপের এই ডাটা-স্ট্রাকচারটা প্রায়ই ব্যবহার করতে হয়, C++ STL এর priority_queue, এটা একটা বাইনারি হিপ ডাটা-স্ট্রাকচার (ডিফল্টঃ ম্যাক্স হিপ)। সহজ বাংলায়, হিপ হল এমন একটা ট্রি ডাটা-স্ট্রাকচার যেখানে সবচেয়ে বড় (ম্যাক্স হিপ) বা সবচেয়ে ছোট (মিন হিপ) এলিমেন্টটা সবসময় রুটে থাকবে। তাই, যদি এমন একটা ঘটনা ঘটে যে, একদল লোক লাইন দিছে কাঙ্গালি ভোজে, এমন টাইমে মাস্তান টাইপের এক ফকির আসছে, আর লোকজন ভয় পেয়ে তাকে লাইনের সামনে দাঁড়া করায় দিবে, তখন প্রায়রিটি কিউ ছাড়া উপায় নাই, অর্থাৎ খালি আগে আসলেই হবে না, যথেষ্ট পরিমানে ভাব নিয়ে আসতে হবে।এইটা খুব সহজেই করা যায়, বার বার চেক করে যে নেক্সট কার প্রায়রিটি বেশি, কিন্তু এইভাবে করাটা আন-এফিসিয়েন্ট, তার চেয়ে হিপের মত একটা ট্রি ডাটা-স্ট্রাকচার ব্যবহার করে অনেক কম সময়ে এই কাজ করা যায়, আর সেই কাজটাকে আর সহজ করে দেওয়ার জন্যই আছে priority_queue, queue এর মত এটাও একটা অ্যাডাপ্টার ক্লাস, তার মানে হল, যে সব STL কন্টেইনার front(), push_back(), pop_back() এই অ্যাকসেস দেয়, তাদেরকে priority_queue এর ইন্টারনাল কন্টেইনার হিসাবে ব্যবহার করা যাবে। আর এটা ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ
1
2
| #include <queue>using namespace std; |
কনস্ট্রাকশনঃ
priority_queue বেশ কয়েকভাবে বানানো যায়, বাই ডিফল্ট এটা ম্যাক্স হিপ ইম্পলিমেন্ট করে আর এলিমেন্ট কম্পেয়ার (ছোট-বড় বুঝার জন্য) করার জন্য <queue> এর less<type_t> ক্লাস ব্যাবহার করে। চাইলে এটাকে অন্য কোন কন্টেইনার যেমন vector কে ইন্টারনাল কন্টেইনার হিসাবে ডিফাইন করে দেওয়া যায়, আর বিল্ট ইন বা ওভারলোডেড টেমপ্লেট টাইপ ছাড়াও এটা বানানো যায়, সেক্ষেত্রে ডাটার নিজের ডিফল্ট কম্পেয়ারিজন ক্লাস ব্যবহার করতে হবেঃ < কে ওভারলোড করে, অথবা এক্সপ্লিসিট কম্পেয়ারিজন ক্লাসে () কে ওভারলোড করে। আর, মিন হিপ বানানোও সহজ, <queue> এ ডিফাইন করা greater<type_t> ক্লাস ব্যবহার করে খুব সহজেই করা যায়। যেমনঃ
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
| // constructing priority queues#include <iostream>#include <queue>using namespace std;class mycomparison { bool reverse;public: mycomparison(const bool& revparam=false) { reverse = revparam; } bool operator() (const int& lhs, const int&rhs) const { if (reverse) return (lhs>rhs); else return (lhs<rhs); }};int main () { int myints[]= {10,60,50,20}; // default construction priority_queue<int> first; priority_queue<int> second (myints,myints+3); // using greater<> to create min heap priority_queue< int, vector<int>, greater<int> > third (myints,myints+3); // using "mycomparison" comparison class priority_queue< int, vector<int>, mycomparison > fourth; typedef priority_queue<int,vector<int>,mycomparison> mypq_type; mypq_type fifth (mycomparison()); mypq_type sixth (mycomparison(true)); return 0;} |
পুশ, পপ, টপঃ
priority_queue এর এলিমেন্ট কে অ্যাকসেস করার জন্য ৩ টা ফাংশন ডিফাইন করা আছে, push(), pop() আর top(). কিউতে কোন এলিমেন্ট অ্যাড করতে চাইলে push() ফাংশনটা ব্যবহার করতে হয়, top() হিপের বর্তমান রুটকে রিটার্ন করে, আর pop() সেটা ট্রি থেকে ডিলিট করে। অর্থাৎ top() আর pop() একত্রে ম্যাক্স হিপের জন্য extract_max() আর মিন হিপের জন্য extract_min() [see: Introduction To Algorithms — CLRS — MIT Press] এর কাজ করে। নিচে উদাহরণ দেওয়া হলঃ
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
| // priority_queue::push/pop/top#include <iostream>#include <queue>#include <ctime>#include <cstdlib>using namespace std;int main () { priority_queue<int> mypq; srand(time(NULL)); cout << "Pushing some random values...\n"; for(int n, i = 0; i < 10; i++) { n = rand(); cout << " " << n; mypq.push(n); } cout << endl; cout << "Popping out elements...\n"; while (!mypq.empty()) { cout << " " << mypq.top(); mypq.pop(); } cout << endl; return 0;} |
কিউ এর সাইজ চেক করাঃ
priority_queue এর বর্তমান এলিমেন্ট কতগুলা আছে বা, কিউ খালি কিনা এটা টেস্ট করার জন্য ২ টা ফাংশন ডিফাইন করা আছে, size() আর empty(). কিউ থেকে top() আর pop() ব্যবহার করার আগে অবশ্যই কিউ খালি কিনা চেক করা উচিৎ, তা না হলে রান টাইম এরর জেনারেট হতে পারে। আর, কিউ খালি কিনা এটা empty() মেথড দিয়েই চেক করা উচিত, soze()==0 দিয়ে নয়। STL এর সব কন্টেইনার ক্লাসেই এদের ব্যবহার একি রকমঃ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| // priority_queue ::size/empty#include <iostream>#include <queue>using namespace std;int main () { priority_queue<int> myints; cout << "0. size: " << (int) myints.size() << endl; for (int i=0; i<10; i++) myints.push(i); cout << "1. size: " << (int) myints.size() << endl; myints.pop(); cout << "2. size: " << (int) myints.size() << endl; while(!myints.empty()) myints.pop(); cout << "3. size: " << (int) myints.size() << endl; return 0;} |
ব্যবহারঃ
বাইনারি হিপ তৈরিতে, ডায়াকস্ট্রা আর প্রিম অ্যালগরিদমে ব্যবহার করা হয়, টেমপ্লেট ক্লাস হওয়ায় যে কোন ডাটা টাইপের জন্য খুব দ্রুত কোড ইমপ্লিমেন্ট করা যায়।বিস্তারিতঃ http://www.cplusplus.com/reference/stl/priority_queue/
C++ STL :: queue
জুলাই 30, 2010
১টি মন্তব্য
কিঊঃ
আগে আসলে আগে পাবেন, এই রকমের একটা ডাটা স্ট্রাকচার হল কিউ, যাকে আমরা বলি ফার্স্ট ইন ফার্স্ট আউট (FIFO)। এটা C++ STL এর সবচেয়ে বেশি ব্যবহৃত কন্টেইনার ক্লাস। queue এর সামনের দিক থেকে ডাটা এক্সট্র্যাক্ট করা হয়, আর ইনসার্ট করা হয় তার বিপরীত দিক থেকে। তাই, যে সব STL কন্টেইনার push_back() আর pop_front() সাপোর্ট করে সেগুলো দিয়ে কিউ ইমপ্লিমেন্ট করা যায়, যেমন list আর deque. অবশ্য queue এর ডিফল্ট কন্টেইনার হল deque, যদি কিছু বলে না দেয়া হয়। stack এর মত queue ও একটা অ্যাডাপ্টার ক্লাস।queue ব্যবহার করতে চাইলে std <queue> হেডারটা প্রোগ্রামে ইনক্লুড করতে হবেঃ
1
2
| #include <queue>using namespace std; |
কন্সট্রাকশনঃ
অন্যান্য কন্টেইনার ক্লাসের মত queue এর সাধারণ কন্সট্রাক্টর queue< type_t > myqueue; এই ধরনের। এছাড়া এক্সপ্লিসিট কন্টেইনার ডিক্লেয়ার করেও queue কন্সট্রাক্ট করা যায়, যেমনঃ
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
| // 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 এর সামনে থেকে কোন এলিমেন্ট বের করে দেয়া। যেমনঃ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| // 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() এর এলিমেন্ট কে স্ট্যান্ডার্ড অপারেটর গুলর সাহায্যে মডিফাই করা যায়। যেমনঃ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| // 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() এর প্রয়োগ দেখানো হলঃ
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
| // 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;} |
ব্যবহারঃ
FIFO ডাটা স্ট্রাকচার হিসাবে, BFS ট্রাভার্সাল, বিভিন্ন গ্রাফ এলগরিদমে queue ইম্পলিমেন্ট করা হয়।বিস্তারিতঃ http://www.cplusplus.com/reference/stl/queue/
C++ STL :: stack
জুলাই 29, 2010
12 comments
স্ট্যাকঃ
STL কন্টেইনারদের মধ্যে সম্ভবত সবচেয়ে সিম্পল ডাটা স্ট্রাকচার হল stack, এটা একটা লাস্ট ইন ফার্স্ট আউট (LIFO) ডাটা স্ট্রাকচার, মানে হল যে সবার শেষে আসবে, সে সবার আগে ভাগবে… সোজা কথায় এই কন্টেইনারের শুধুমাত্র একটা দিকেই ডাটা ইন্সার্ট বা এক্সট্র্যাক্ট করা হয়। আর STL এ stack তার ডিফল্ট ইন্টার্নাল ডাটা স্ট্রাকচার হিসাবে ব্যবহার করে STL এরই deque কন্টেইনার, তবে চাইলে vector বা list ও ব্যবহার করা যেতে পারে। যে সব কন্টেইনার push_back() আর pop_back() মেথড ২ টা সাপোর্ট করে সেগুলোকেই stack এর কন্টেইনার ক্লাস হিসাবে ব্যবহার করা যায়। stack আসলে একটা অ্যাডাপ্টার ক্লাস, অর্থাৎ, এটা তৈরি করা হয় এর ইন্টারনাল কন্টেইনারের স্পেসিফিক কিছু ফাংশনকে এলিমেন্ট একসেসের অনুমতি দিয়ে।stack ব্যবহার করতে চাইলে সর্বপ্রথম কাজটা হল std <stack> হেডারটা প্রোগ্রামে ইনক্লুড করাঃ
1
2
| #include <stack>using namespace std; |
কন্সট্রাক্টরঃ
অন্যান্য STL কন্টেইনার ক্লাসের মত stack এরও সাধারণ কন্সট্রাক্টর stack< type_t > myStack; এই রকমের, তবে আরো অনেকভাবে ডিক্লেয়ার করা যায়। যেমনঃ
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
| // constructing stacks#include <list>#include <vector>#include <deque>#include <stack>using namespace std;int main (){ // using default container deque stack< int > first; // empty stack deque< int > mydeque(3, 100); // deque with 3 elements stack< int > second(mydeque); // from mydeque stack< int > third(second); // from another stack second // explicit container declarations stack< int, deque< int > > fourth; // empty stack using deque deque< int > newdeque(10, 100); // deque with 10 elements stack< int, deque< int > > fifth(newdeque); // from newdeque stack< int, vector< int > > sixth; // empty stack using vector vector< int > myvector(2, 200); // vector with 2 elements stack< int, vector< int > > seventh(myvector); // from myvector stack< int, list< int > > eighth; // empty srack using list list< int > mylist(4, 100); // list with 4 elements stack< int, list< int > > ninth(mylist); // from mylist // can refer to some other stack stack< int > tenth = first; // declaration time initialization return 0;} |
এলিমেন্ট একসেসঃ
stack ক্লাসের এলিমেন্ট গুলাকে একসেস করার জন্য ৩ টা মেম্বার ফাংশন আছেঃ- top()
- push()
- pop()
আর, stack এর এলিমেন্ট কাউন্ট করার জন্য ২ টা ফাংশন আছেঃ
- size()
- empty()
নিচে এই ফাংশন গুলার কাজ দেখানো হলঃ
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
| // stack::push/pop/top/size/empty#include <iostream>#include <stack>using namespace std;int main (){ stack< int > mystack; // lets push and pop some values for (int i=0; i<5; i++) mystack.push(i); cout << "Popping out elements..."; while (!mystack.empty()) { cout << " " << mystack.top(); mystack.pop(); } cout << endl; // changing the value of top mystack.push(100); mystack.top() += 1000; cout << "Now top is: " << mystack.top() << endl; mystack.pop(); // not a good way to check if stack is empty if(mystack.size() == 0) cout << "Stack is empty" << endl; // better we do this if(mystack.empty()) cout << "Stack is empty" << endl; return 0;} |
ব্যবহারঃ
সাধারণত এক্সপ্রেশন / গ্রামার প্রসেসিং, রিকারসিভ এলগরিদমের নন রিকারসিভ প্রয়োগ, DFS ট্রাভার্সাল, LIFO অপারেশনে stack ব্যবহার করা হয়। STL এর stack একটা টেমপ্লেট ক্লাস, তাই যে কোন ডাটা টাইপের জন্য খুব দ্রুত stack ইম্পলিমেন্ট করা যায় STL ব্যবহার করে।বিস্তারিতঃ http://www.cplusplus.com/reference/stl/stack/
No comments:
Post a Comment