C++ STL & Tricks-1


C++ এ কিছু build in লাইব্রেরী আছে, যাদেরকে বলা হয় standard template library. এইসব STL ব্যবহার করে অনেক প্রবলেম অনেক সহজে করে ফেলা যায়। যেমন কোন প্রবলেমে যদি stack,queue এইগুলা ব্যবহার করা লাগে, এইগুলার জন্য নতুন করে কোড লেখার প্রয়োজন পরে না। stack,queue stl ব্যবহার করেই প্রবলেম সল্ভ করা যায়।

vector:

ভেক্টর নরমাল এ্যারের মতই। এর সুবিধা হল যখন ইচ্ছে সাইজ পরিবর্তন করা যায়।

vector declare:

vector ব্যবহার করার জন্য header file vector include করতে হবে।
vector < type > Name;

Vector capacity, element access, modifiers:

ভেক্টরের সাইজ জানার জন্য ব্যবহার করা হয়, size() public member function. এটি ভেক্টরের সাইজ রিটার্ন করে। complexity O(1)

ভেক্টর empty কিনা, তা জানার জন্য ব্যহহার করা হয় empty() public member function. এটি বুলিয়ান ভ্যালু রির্টান করে। ভেক্টর empty হলে true otherwise false রির্টান করে। complexity O(1)

ভেক্টরের element নরমাল এ্যারের মত [] অপারেটর দিয়ে access করা যায়। তাছাড়া at() public member function দিয়েও যেকোন পজিশনের ভ্যালু এ্যাকসেস ও পরিবর্তন করা যায়।

STL container যেগুলোতে begin() & end() public member function আছে, সেইগুলা iterator ব্যবহার করেও element access করা যায়।
vector iterator declare:
vector< Type >::iterator Name;

ভেক্টরে সরাসরি ইনপুট নেয়ার কোন উপায় নেই। এর জন্য আলাদাভাবে ভ্যালু ইনপুট নিয়ে ভেক্টর modifier দিয়ে ভেক্টরে ভ্যালু assign করতে হয়। সাধারণত push_back use করে এ্যাসাইন করা হয়। এর কাজ হল ভেক্টর লিস্টের শেষে একটি এলিমেন্ট যোগ করে দেয়া।
v.push_back(x); এর মানে হল ‘x’ ভেক্টরের শেষে যোগ হয়ে যাবে।

vector এ ইনপুট নেয়ার আরেকটি উপায় হল, নির্দিষ্ট সাইজের ভেক্টর declare করে তাঁতে, scanf/cin use করে ইনপুট নেয়া।

pop_back use করে ভেক্টরের শেষের element রিমুভ করে দেয়া হয়।
insert
ভেক্টরের একটি নির্দিষ্ট পজিশনে ভ্যালু insert করা।
erase
ভেক্টর থেকে নির্দিষ্ট পজিশনের ভ্যালু মুছে দেয়া বা একটা নির্দিষ্ট পজিশনের রেঞ্জের ভ্যালু মুছে দেয়ার জন্য ব্যবহার করা হয়। Complexity Linear.
clear
পুরো ভেক্টর empty করে দিতে ব্যবহার করা হয়।

এখানে v.begin() vector এর শুরুর iterator. এইটা অনেকটা পয়েন্টারের মত।
Line 27 এ v.begin() মানে ভেক্টরের প্রথমে ভ্যালু insert করা হচ্ছে।
Line 32 এ v.begin() মানে হচ্ছে ভেক্টরের 3rd position এ ভ্যালু insert করা হচ্ছে।
Line 42 এ v.erase(v.begin()+2,v.begin()+4) মানে হচ্ছে ভেক্টরের 3rd to 4th পজিশন পর্যন্ত সব এলিমেন্ট রিমুভ করে দেয়া। এখানে রেঞ্জ [2 , 4) এইভাবে কাজ করছে। including first limit, excluding last limit. (x<=i<y)

Some advance operation in vector:

Size define করে ভেক্টর declare করা ও initial value set করে ভেক্টর declare করা যায়।
vector< type >Name( Size );
vector< type >Name( Size , InitialValue );

size define করে initial value ছাড়া ভেক্টর declare করলে initially vector এর সব এলিমেন্ট zero থাকে।

vector এর সাইজ পরিবর্তন করার জন্য resize()  member function use করা হয়।

accumulate(), min_element(), max_element() দিয়ে ভেক্টর থেকে সহজে যোগফল, মিনিমাম ও ম্যাক্সিমাম নাম্বার বের করে ফেলা যায় এবং sort() function দিয়ে সর্ট করা যায়। এইগুলা জন্য algorithm header file include করতে হবে।

Make vector  element unique:

List:

ভেক্টরের মত লিস্ট ও এক ধরনের ডাইনামিক কনটেইনার।

List declare:

List container এর জন্য list header file include করতে হবে।
list< Type >Name;
list< int >List;

List capacity, element access, modifiers:

vector এর মত list প্রায় সকল অপারেশন একই রকমের। list এর element vector মত [] অপারেটর দিয়ে access করা যায় না। list এর সকল element access এর জন্য iterator ব্যবহার করতে হয়। list resize করার জন্য কিছু নেই। তবে push_front(), pop_front() দুইটি public member function আছে, যা দিয়ে list এর প্রথমে element add করা যায় ও প্রথম থেকে element remove করা যায়।

Some advance operation in list:

list এর কিছু public member function হল sort(), remove(), unique(). sort এর time complexity O(nlogn), remove(), unique() এর time complexity linear O(n).

বিদ্রঃ list/vector এর সকল element unique করার জন্য আগে sort করে নিতে হবে। কারণ unique ফাংশন পাশাপাশি দুইটি ভ্যালু সেম হলে একটি সেভ করে। এইজন্য আগে সর্ট করে নিলে সবগুলো element unique হবে।

list এর মধ্যে সবচেয়ে কার্যকরী অপারেশন হল, দুইটি লিস্ট O(1) time complexity তে সংযুক্ত করা। এর জন্য list এর splice() public member function ব্যবহার করা হয়।


বিদ্রঃ splice অপারেশনে time complexity সবসময় O(1) নয়। যখন কোন লিস্টের মাঝে ইটারেটর দিয়ে আরেকটি লিস্ট সংযুক্ত করা হয় তখন time complexity O(n) হয়ে যায়। n হল number of element of list. কিন্তু কোন লিস্টের প্রথমে বা শেষে অন্য লিস্ট সংযুক্ত করতে সবসময় O(1). 

String:

string নরমাল স্ট্রিং এর মতই। তবে এর কিছু ফিচার আছে, যার জন্য string ব্যবহার করা অনেক সহজ। string class ব্যবহারের জন্য string header file include করতে হবে।

string capacity, element access, modifiers:

string এর প্রতিটি character [] অপারেটর দিয়ে access করা যায়।
দুইটি string কম্পেয়ার করার জন্য ‘==’ অপারেটর ব্যবহার করা হয়।
string concat করার জন্য ব্যবহার করা হয় ‘+’
string append করার জন্য ‘+=’ ব্যবহার করা যায়।
vector এর মত string এর push_back(), pop_back(), erase(), size() public member function আছে।

string এ ইনপুট নেয়ার জন্য cin/getline() ব্যবহার করা লাগে। আউটপুটের জন্য cout, আর যদি printf() দিয়ে প্রিন্ট করা লাগে তাহলে c_str() public member function দিয়ে c string এ কর্নভাট করে নেয়া লাগে।

Some advance operation in string:

min(),max() function দিয়ে দুইটি string A ও B এর মধ্যে lexicographically smallest ও largest স্ট্রিং বের করা যায়।
find() public member function দিয়ে string এ অন্য একটি প্যার্টান খুঁজে বের করা যায়। এটি প্রথম থেকে খুঁজে পাওয়া প্যার্টানের পজিশন রির্টান করে। শেষে থেকে প্যার্টান স্ট্রিং খুঁজে বের করার জন্য rfind() ব্যবহার করা হয়।
String এর যেকোন পজিশন থেকে যেকোন সাইজের sub string এর জন্য substr() public member function ব্যবহার করা হয়।

Stack:

stack হল এমন একধরনের ডাটাস্ট্রাকচার যা, “last in, first out” প্রপার্টি মেনে চলে। এরমানে হল এমন একটি লিস্ট, যেই লিস্টে যে সবার পরে insert হবে সে সবার আগে বের হবে। linked list দিয়ে স্ট্যাক implement করা যায়। কিন্তু stl stack ব্যবহার করলে সেই জিনিস আর করা লাগে না।

Stack declare:

stack ব্যবহারের জন্য header file stack include করতে হবে।
stack< Type >Name;
stack< int >Name;

Stack operation:

stack এর প্রধান অপারেশন হল, push(), pop(), top() public member function. push() দিয়ে stack এর শেষে নতুন element যোগ করা হয়। pop() দিয়ে stack এর শেষে যোগ হওয়া element ফেলে দেয়া হয়। top() দিয়ে stack এর সবার শেষে বা সবার উপরের element access করা হয়। stack এর কোন begin(), end() iterator return করে এমন public member function নেই। তাই পুরো stack একসাথে iterate করার কোন উপায় নেই।

তাছাড়াও stack এর আরও দুইটি কার্যকরী public member function হল, size(), empty().

Queue:

queue ডাটাস্ট্রাকচার “first in first out” প্রোপার্টি মেনে চলে। মানে লিস্টে যে element সবার আগে add হবে, সেই element সবার আগে বের হবে।

Queue declare:

queue ব্যবহারের জন্য header file queue include করতে হবে।
queue< Type >Name;
queue< int >Name;

Queue operation:

queue এর অপারেশন গুলা হল, push(), front(), pop(). push() public member function দিয়ে queue তে element এ্যাড করা হয়। front() দিয়ে সবার সামনের (যে আগে এ্যাড হয়েছিল) সেইটা access করা হয়। pop() দিয়ে সবার উপরের element ডিলিট করে/ ফেলে দেয়া হয়। স্ট্যাকের মতও queue তে public member function begin(), end() না থাকায় সকল element iterate করা যায় না।

queue এর সাইজ এর জন্য size() এবং empty কিনা তা জানার জন্য empty() member function ব্যবহার করা হয়।

Deque:

Double ended queue. এর front ও back উভয় দিকে থেকে ভ্যালু add করা যায় ও remove করা যায়।

deque declare:

deque ব্যবহারের জন্য header file deque include করতে হবে।
deque< Type >Name;
deque< int >Name;

deque operation:

deque এর কিছু অপারেশন queue এর মতই। front থেকে element add এবং remove করার জন্য push_front()pop_back() ব্যবহার করা হয়। Back থেকে element add এবং remove করার জন্য push_back()pop_back() ব্যবহার করা হয়।
তাছাড়া deque [] operator দিয়ে access করা যায়। এর size(), erase(), clear() public member function আছে।

Priority Queue:

priority queue এমন এক ধরনের কিউ যেখানে front element সবসময় বড়টা থাকে, বা যার priority বেশি সে থাকে। priority queue এর property চেঞ্জ করে ছোট element সবসময় front এ রাখা যায়।

Priority queue declare:

Priority queue ব্যবহারের জন্য header file queue include করতে হবে।
priority_queue< Type >Name;
priority_queue< int >Name;

Priority queue operation:

priority queue অপারেশন গুলো queue এর অপারেশনের মতই। তবে এখানে front() এর পরিবর্তে আছে top(), যা সবসময় priority queue তে থাকা বড় ভ্যালু (by default) রির্টান করে।

Set:

set হল এমন এক ধরনের লিস্ট যেখানে সব element একবার করে থাকবে। মানে একটি value যতবারেই insert করা হোক না কেন, থাকবে একবার। set সকল element কে sorted আকারে রাখে।

Set declare:

set ব্যবহারের জন্য header file set include করতে হবে।
set< Type >Name;
set< int >Name;

Set operation:

set উল্লেখযোগ্য অপারেশনগুলো হল, insert(), erase(), clear(), find(), size(), empty(). set এ begin()end() public member function থাকায় iterator দিয়ে পুরো set iterate করা যায়।


set এর insert(),find(),erase() সবগুলার time complexity O(log2(n))

Map:

কোন কিছুকে কী-ভ্যালু দিয়ে ম্যাপ করে রাখার জন্য map stl ব্যবহার করা হয়। ম্যাপের ব্যবহারের একটি বড় সুবিধা হল, ডাইনামিক হওয়াতে যেকোন class,string, variable ম্যাপিং করা যায়।

map declare:

map ব্যবহারের জন্য header file map include করতে হবে।
mapkey_Type , value_type >Name;
map< int, char >Name;

map operation:

map ভ্যালু assign করতে হয় Map[key]=value এইভাবে। একটা নির্দিষ্ট key এর ভ্যালু পাওয়া জন্য value=Map[key] নরমাল এ্যারে index এর মত access. map এ সকল element তার key value দিয়ে sorted আকারে থাকে। map এর সকল element iterator দিয়ে iterate করা যায়। find() public function দিয়ে যেকোন key map এ আছে কিনা তা খুঁজে বের করা যায়। erase() public member function দিয়ে যেকোন key remove করে দেয়া যায়।


map এ সকল অপারেশনের time complexity logarithmic in size. O(log2(N)).

Caution:

map  এ specific key আছে কিনা তা দুইভাবে চেক করা যায়। প্রথম উপায় হল Map[key]==0 তাহলে সেই key ম্যাপে নেই আরেকটা উপায় হল find() public member function use করে।


এখানে উপরে দুই ধরনের সার্চ technique এ প্রথম technique এ একটু ঝামেলা আছে। প্রথম পদ্ধতিতে প্রত্যেকবার সার্চ করার সময় ম্যাপে specific key value না থাকলেও ওই key value দিয়ে নতুন একটি স্লট map এ allocate করে নিচ্ছে এইভাবে Map[key]=0. এতে করে ম্যাপের সাইজ প্রত্যেক সার্চে বেরে যাচ্ছে। প্রোগ্রামিং কন্টেস্ট এ এই টেকনিক memory limit exceed error এর একটা কারণ হতে পারে। তাই সবসময় key search করার জন্য দ্বিতীয় technique use করা ভাল।

নিচের কোডটুকু দেখলে সমস্যাটা আরও ভাল করে বুঝা যাবেঃ


এখানে দেখা যাচ্ছে সার্চ করার আগে ম্যাপের সাইজ ছিল 10, সার্চ করার পর বেড়ে হয়েছে 26.

iterator:

C++ এর iterator অনেকটা পয়েন্টারের মত, যা কোন container object এর পয়েন্টার নিয়ে একটা নির্দিষ্ট রেঞ্জের মধ্যে প্রতিটা element iterate করতে পারে। যেসব stl গুলাতে begin(),end() public member function আছে সেইগুলা iterator দিয়ে iterate করা যায়।

iterator declare এর নিয়ম হলঃ
container::iterator name;

যেমনঃ set এর iterator declare করতে হলে, set::iterator it; এইভাবে করতে হবে।

upper bound & lower bound:

C++ এর lower_bound() function sorted container এর  রেঞ্জ [first,last) এর মধ্যে এমন একটি iterator position return করে যেখানে সব element range এর প্রথম থেকে ওই পর্যন্ত  < val থাকে।

C++ এর upper_bound() function sorted container এর রেঞ্জ [first,last) এর মধ্যে এমন একটি iterator position return করে যেখানে সব element range এর প্রথম থেকে ওই পজিশন পর্যন্ত <=val থাকে।

upper_bound, lower_bound algorithm header file এ আছে। এদের time complexity O(log2(N)).
uppper_bound(), lower_bound() use করে sorted container এর রেঞ্জ এর মধ্যে একটা নির্দিষ্ট রেঞ্জ এর নাম্বার কতগুলো আছে তা সহজে বের করে ফেলা যায়।


একই রকম কাজ set, map stl এ কাজ করা যায়।

বিদ্রঃ কোন প্রকার ভুল বা সংশোধন থাকলে কমেন্ট করে জানানোর জন্য অনুরোধ করছি। 🙂 

               ~ Happy coding ~

Advertisements

About Tanvir Hasan Anick

I can read and write code, :)
This entry was posted in C++, Contest and tagged , . Bookmark the permalink.

7 Responses to C++ STL & Tricks-1

  1. mukitmkbs says:

    Nice one… 🙂

    Liked by 1 person

  2. shishir says:

    ভাল লাগল 😀 😀

    Liked by 1 person

  3. Sifat says:

    onek valo laglo…apni ki training koran? cont num diben plz?

    Like

  4. _mHm_ says:

    Vaia…..rand () function ta bujhteci na….

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s