در برگیرنده ها $Containers$

به منظور راحتی برنامه نویسان بسیاری از داده ساختار های پرکاربرد در قالب کلاس های آماده در کتابخانه $STL$ نوشته شده است که در اینجا به معرفی برخی از آن ها میپردازیم.

این داده ساختار در واقع یک زوج مرتب میباشد که از داده ساختار map تخصیص یافته و در آن عناصر دارای کلید های منحصر به فرد هستند . از زوج مرتب برای ترکیب دو مقدار که ممکن است از نظر نوع متفاوت باشند نیز استفاده می شود.

pair.cpp

#include <utility>       //  کتابخانه مورد نیاز
pair<Type1,Type2> pairName;  //  pair تعریف 
piarName = {Value1, Value2}; //  pair مقداردهی
pairName.first           // دسترسی به عنصر اول
pairName.second          // دسترسی به عنصر دوم

این داده ساختار همچون یک آرایه با سایز متغیر است که امکان دسترسی مستقیم به اعضا و همچنین درج عنصر در انتها و یا حذف آخرین عنصر مهیا است. حال به نحوه تعریف و استفاده از آن میپردازیم

vector.cpp

# include<vector>        // کتابخانه مورد نیاز
vector<Type> vectorName; //  vector تعریف
vectorName[i];           // ام i دسترسی به عنصر  
vectorName.push_back(x); // به انتها x اضافه کردن 
vectorName.pop_back();   // vector حذف عنصر انتهای
vectorName.back();       // vector برگرداندن آخرین عضو
vectorName.front();       // vector برگرداندن اولین عضو
vectorName.size();       // vector برگرداندن اندازه 
vectorName.empty();      // خالی است vector برگرداندن اینکه 
vectorName.clear()       // vector خالی کردن

این داده ساختار در واقع همان داده ساختار پشته است که از قاعده $LIFO(LastInFirstOut)$ پیروی میکند.

stack.cpp

# include<stack>       // کتابخانه مورد نیاز
stack<Type> stackName; // تعریف پشته
stackName.push(x);     // روی پشته x گذاشتن  
stackName.top()        // برگرداندن عنصر روی پشته
stackName.pop();       // برداشتن بالاترین عنصر پشته
stackName.size();      // برگرداندن اندازه پشته
stackName.empty();     // برگرداندن اینکه پشته خالی است 

این کلاس همان داده ساختار صف است که از قاعده $FIFO(FirstInFirstOut)$ پیروی میکند.

queue.cpp

# include<queue>       // کتابخانه مورد نیاز
queue<Type> queueName; // تعریف صف
queueName.push(x);     // انتها صف x گذاشتن  
queueName.front()      // برگرداندن عنصر ابتدای صف
queueName.pop();       // برداشتن اولین عنصر صف
queueName.size();      // برگرداندن اندازه صف
queueName.empty();     // برگرداندن اینکه صف خالی است
queueName.clear();     // خالی کردن صف 

این کلاس داده ساختار درخت دودویی جست جو بهینه است که با الگوریتم $RedBlackTree$ پیاده سازی شده است.

set.cpp

# include<set>       //  کتابخانه مورد نیاز
set<Type> setName; //  set تعریف 
setName.insert(x);   //  set به x افزودن   
setName.find(x)      //  و در صورت پیدا شدن set در x پیدا کردن عنصر 
                     //  برگرداندن اشاره گر به آن و در غیر اینصورت برگرداندن
		     //  setName.end() اشاره گر
setName.erase(x);    //  set در صورت وجود از x حذف عنصر 				 
setName.size();      //  set برگرداندن اندازه 
setName.empty();     //  خالی است  set برگرداندن اینکه 
setName.clear();     //  set خالی کردن 

این داده ساختار در واقع همچون جدولی میماند که که یک سری کلید را به عنصر مربوطه مرتبط میکند در پیاده سازی آن در واقع از همان $set$ استفاده شده است که عناصر آن زوج مرتبی از کلید و مقدار هستند. توجه کنید که عنصر مربوط به هر کلید یکتاست در نتیجه دو زوج مرتب با مولفه اول یکسان در درخت موجود نیستند.

map.cpp

# include<map>       //  کتابخانه مورد نیاز
map<KeyType,ValueType> mapName; //  map تعریف 
mapName[key];        //  key دسترسی به مقدار مربوط به کلید   
mapName.find(key)    //  و در صورت پیدا شدن map در key پیدا کردن عنصر با کلید 
		     //  برگرداندن اشاره گر به آن و در غیر اینصورت برگرداندن
		     //  mapName.end() اشاره گر				 
mapName.size();      //  map برگرداندن اندازه 
mapName.empty();     //  خالی است  map برگرداندن اینکه 
mapName.clear();     //  map خالی کردن 

با استفاده از پشته میخواهیم برنامه ای بنویسیم که تشخیص دهد یک پرانتز گذاری معتبر است یا نه برای هرکس اندیس جفت آن را بدست آورد.

balanced.cpp

#include <iostream>
#include <stack>
using namespace std;
const int MAX_N=100*1000;
int match[MAX_N];
string P;
stack<int> S;
bool notBalanced;
int main()
{
	cin >> P;
	for(int i=0;i<(int)P.size();i++)
	{
		if(P[i]=='(')
			S.push(i);
		else{
			if(S.empty()){
				notBalanced=true;
				break;
			}
			match[i]=S.top();
			match[match[i]]=i;
			S.pop();
		}
	}
	if(!S.empty())
        notBalanced=true;
	if(notBalanced)
		cout<<"The Input String is not Balanced !";
	else
		for(int i=0;i<(int)P.size();i++)
			cout<<match[i]+1<<" ";
	cout<<endl;
}

در مثال دوم میخواهیم ببنیم که جمع اعضای زیر مجموعه های یک مجموعه حداکثر $20$ عضوی چند عدد متمایز تولید میکنند.

subsetSum.cpp

# include <iostream>
# include <vector>
# include <set>
using namespace std;
int N;
vector<int> V;
set<int> S;
int main()
{
	cin >> N;
	for(int i=0;i<N;i++){
        int temp;
        cin >> temp;
        V.push_back(temp);
	}
	for(int mask=0;mask<(1<<N);mask++){
        int sum=0;
        for(int j=0;j<N;j++)
            if((mask>>j)&1)
                sum+=V[j];
        S.insert(sum);
	}
	cout<<S.size()<<endl;
	return 0;
}