منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.
در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه بیشتر» بخوانید.
توجه: تمامی کلاس‌های بحث شده در کتابخانه قالب استاندارد (STL) تعریف شده و در فضای نام std قرار دارند.
آرایه
[برگرد بالا]
آرایه ساده‌ترین ظرف است که در عموم زبان‌های برنامه‌نویسی وجود دارد و از زبان برنامه‌نویسی C نیز به ++C ارث رسیده است. تعداد عناصر (طول) این ظرف در زمان تعریف مشخص شده و دسترسی به عناصر از طریق اندیس با شروع از صفر صورت می‌گیرد:
// type name [size];
int myArray[5] = {1, 2, 3, 0, 5};
myArray[3] = 4;
اگرچه ذخیره شدن اطلاعات در آرایه به صورت ترتیبی است، اما این ساختمان داده رابطه مستقیم با اشاره‌گرها به حافظه داشته و در حافظه به صورت یک تکه ذخیره می‌شود. از این رو کارایی آن در دسترسی تصادفی به عنصر دلخواه مناسب است. در مقابل، درج عنصر در محل دلخواه یا حذف عنصر از محل دلخواه هزینه بالایی دارد. چرا که باید عناصر موجود در بعد از آن محل جابجا شوند. راهکارهایی برای کاهش این پیچیدگی پیشنهاد می‌شود. به عنوان مثال می‌توان حذف از عنصر را با علامت‌گذاری انجام داد تا جابجایی صورت نگیرد. اما در کل آرایه برای عملیاتی که نیاز به درج و حذف زیاد دارند مناسب نیست. از سوی دیگر، تعداد عناصر قابل ذخیره‌سازی در آن ثابت بوده و امکان تغییر وجود ندارد.
کلاس array
[برگرد بالا]
کلاس array عملکردی مشابه آرایه دارد. اشیاء این کلاس به صورت زیر تعریف می‌شوند:
// array<type, size> name
array<int, 5> myArray = {1, 2, 3, 0, 5};
myArray[3] = 4;
یک تفاوت کلاس array با آرایه در آن است که امکان تعریف با طول نامشخص و تخصیص طول بر اساس مقداردهی اولیه در array وجود ندارد. همچنین کار با آرایه‌های چندبعدی ساده‌تر از کار با arrayهای تو در تو است. اما می‌توان از طریق متد data محتوای آن را به صورت اشاره‌گر به ابتدای آن دریافت کرده و مانند آرایه با آن کار کرد:
array<int, 5> myArray = {1, 2, 3, 4, 5};
int *arr = myArray.data();
for(int i = 0 ; i < 5 ; i++)
cout << arr[i] << "\t";
// output: 1 2 3 4 5
یک تفاوت شاخص دیگر array و آرایه در آن است که ارسال یک شیء از نوع array به یک تابع یک کپی از اطلاعات را منتقل می‌کند. در حالی که آرایه از طریق اشاره‌گر منتقل می‌شود و ممکن است داخل تابع مقدار عناصر آن تغییر کند.
نکته: کلاس array در نسخه C++11 اضافه شده است.
کلاس vector
[برگرد بالا]
یک وکتور را می‌توان آرایه‌ای در نظر گرفت که امکان تغییر اندازه آن به صورت پویا و حین اجرای برنامه وجود دارد. به این ترتیب می‌توان هر تعداد عنصر دلخواه (تا جایی که حافظه یاری کند) به آن push_back نمود و در نهایت به اندیس دلخواه با کارایی مناسب دسترسی داشت. البته می‌توان از ابتدا اندازه پیش‌فرض نیز برای آن مشخص کرد:
// vector<type> name(size = 0);
vector<int> myVector1 = {1, 2, 3, 4}, myVector2(5);
myVector2[2] = 3;
cout << myVector1.size() << "-" << myVector1.capacity() << endl;
// output: 4 - 4
myVector1.push_back(5);
cout << myVector1.size() << "-" << myVector1.capacity() << endl;
// output: 5 - 8
با تعریف v1 در قطعه کد فوق، آرایه‌ای به طول 4 برای آن در نظر گرفته می‌شود. زمانی که عدد 5 با استفاده از متد push_back به انتهای آن درج می‌شود، تعداد عناصر بیش از ظرفیت (capacity) آرایه شده و امکان درج وجود ندارد. بنابراین آرایه جدیدی با طول دو برابر ظرفیت قبلی ساخته شده و تمام عناصر در آن کپی می‌شوند. به همین دلیل پس از اجرای عمل درج، ظرفیت وکتور به 8 افزایش یافته و اندازه نیز به 5 تغییر می‌کند. پس از این تغییرات سه درج دیگر بدون هیچ تخصیص حافظه جدیدی می‌تواند صورت پذیرد و اگر تعداد درج بیشتر شود، مجددا آرایه جدیدی با طول دو برابر ساخته شده و عناصر در آن کپی می‌شوند. همچنین با استفاده از متد resize امکان تغییر اندازه وکتور وجود دارد. اگر این تغییر اندازه باعث افزایش طول باشد، عناصر جدید با مقدار پیش‌فرض نوع داده (مقدار صفر در مثال بالا) پر می‌شود و اگر اندازه کوچکتر شود، برخی از عناصر از انتهای آرایه حذف می‌شوند. این تغییرات تاثیری در ظرفیت آرایه نمی‌دهند؛ مگر آنکه افزایش طول بیش از ظرفیت وکتور باشد.
تذکر: در تمام ساختمان داده‌های STL که تخصیص حافظه به صورت پویا وجود دارد، عملیات مدیریت حافظه در پس‌زمینه صورت گرفته و برنامه‌نویس درگیر این موضوع نمی‌شود.
کلاس list
[برگرد بالا]
کلاس list لیست پیوندی دو طرفه را پیاده‌سازی می‌کند و با متدهای push_front و push_back می‌توان عناصری به ابتدا و انتهای آن افزود:
// list<type> name(size = 0);
list<int> myList = {2, 3, 4};
myList.push_back(5);
myList.push_front(1);
for(list<int>::iterator it = myList.begin() ; it != myList.end() ; it++)
cout << *it << "\t";
// output: 1 2 3 4 5
for(list<int>::reverse_iterator it = myList.rbegin() ; it != myList.rend() ; it++)
cout << *it << "\t";
// output: 5 4 3 2 1
با توجه به آنکه ساختمان داده این کلاس لیست پیوندی است، عملیات درج و حذف (با متدهای insert و erase) از مرتبه $O(1)$ است. اما امکان دسترسی تصادفی با استفاده از اندیس به عناصر وجود ندارد و همانگونه که در قطعه کد فوق آمده است، باید از iterator (یا reverse_iterator برای پیمایش از انتها به ابتدا) استفاده کرد. به همین دلیل نیز ممکن است برای حذف یک عنصر یا درج عنصر جدید در محل خاص، نیاز به پیمایش لیست از ابتدا یا انتها جهت مشخص کردن محل درج یا حذف باشد.
بک تفاوت آشکار دیگر list با vector آن است که در لیست‌ها تنها محدودیت طول لیست، حافظه اختصاصی از سوی سیستم عامل است و اضافه شدن یا حذف حافظه برای هر عنصر به صورت مستقل انجام می‌شود. به این ترتیب عملیات کپی کردن مقادیر در حافظه جدید در صورت اضافه شدن عناصر بسیار نیز حذف می‌شود.
توجه: در کنار متد push_back متد pop_back برای حذف از انتهای داده‌ها در هر دو کلاس vector و list وجود دارد. اما کلاس vector شامل متدهای push_front و pop_front نیست و در صورت نیاز باید از متدهای درج و حذف استفاده شود.
کلاس forward_list
[برگرد بالا]
کلاس forward_list لیست پیوندی یک‌طرفه را پیاده‌سازی می‌کند و تمام خواص کلاس list (به جز موارد مربوط به دو طرفه بودن) را دارد. در این ساختار push_front به ابتدای لیست درج می‌کند و متدهای insert_after و erase_after عمل درج و حذف پس از گره مشخص را انجام می‌دهند. برای حذف عنصر ابتدایی نیز می‌توان از pop_front استفاده کرد. در حالت کلی زمانی که تنها نیاز به پیمایش اطلاعات از ابتدا به انتها باشد، بهتر است از این کلاس استفاده شود. چرا که نسبت به list کارایی بهتری داشته و حافظه کمتری نیز مصرف می‌کند.
نکته: کلاس forward_list در نسخه C++11 اضافه شده است.
کلاس set
[برگرد بالا]
همانگونه که از عنوان کلاس set پیداست، این کلاس مفهوم مجموعه در ریاضیات را پیاده‌سازی می‌کند. به این معنی که تکرار در عناصر نداریم (صرفا موجود بودن مهم است) و ترتیب درج در مجموعه نیز لزوما حفظ نمی‌شود. در واقع set عناصر را به صورت مرتب شده ذخیره می‌کند:
// set<type> name;
set<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(set<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
cout << *it << "\t";
// output: 1 2 3 4 5
for(set<int>::reverse_iterator it = mySet.rbegin() ; it != mySet.rend() ; it++)
cout << *it << "\t";
// output: 5 4 3 2 1
متد find با دریافت یک مقدار، iterator متناظر آن مقدار را باز می‌گرداند. روی این iterator می‌توان عملیات insert یا remove را انجام داد و اگر برابر با ()end باشد به معنی موجود نبودن مقدار در مجموعه است.
در پیاده‌سازی set از درخت‌ها استفاده شده است و به همین دلیل مانند کلاس‌های مربوط به لیست پیوندی از لحاظ درج و حذف کارایی مناسبی دارد. در این ظرف عملیات درج و حذف در بدترین حالت از مرتبه لگاریتمی هستند که در مقابل مرتب بودن عناصر مقرون به صرفه است. همچنین باید توجه داشت که امکان تغییر مقادیر درج شده در مجموعه وجود نداشته و در صورت نیاز به تغییر ابتدا باید عنصر قبلی را حذف و عنصر با مقدار جدید را درج نمود.
نکته: ممکن است این سوال پیش بیاید که درج با در اختیار داشتن یک iterator در مجموعه‌ای که خود عناصر را مرتب کرده و ترتیب درج اهمیتی ندارد، چه کاربردی دارد؟ در پاسخ باید به این نکته باید توجه داشت که اگر insert بدون iterator (مانند کد فوق) فراخوانی شود، عملیاتی از مرتبه لگاریتمی برای یافتن محل مناسب درج (از لحاظ ترتیب) مورد نیاز است. اما اگر به عنوان نمونه در کد فوق محل عدد 1 را با iterator در اختیار داشتیم، عدد 2 بلافاصله در کنار آن درج می‌شد و نیاز به عملیات جستجوی محل نبود. بدیهی‌ست اگر محل عنصر جدید پس از iterator نباشد، مجددا باید عملیات جستجو صورت گیرد.
توجه: در ظرف‌هایی مانند set که بحث پیمایش عناصر به صورت مرتب وجود دارد، برای پیمایش باید عملگر > تعریف شده باشد یا متد مقایسه‌گر به عنوان پارامتری اضافه در قالب تعریف فرستاده شود.
کلاس unordered_set
[برگرد بالا]
این کلاس مانند set است. اما مرتب کردن آن مبتنی بر روش مرتب‌سازی نوع داده آن نیست و اطلاعات را بر اساس hash مرتب می‌کند. بنابراین ممکن است در زمان پیمایش ترتیب عناصر نظم خاصی (حتی نظم درج در مجموعه) نداشته باشند:
// unordered_set<type> name;
unordered_set<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(unordered_set<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
cout << *it << "\t";
// output: 2 1 4 3 5
علت این نوع ذخیره‌سازی آن است که شاید برای یک کلاس نتوان مرتب‌سازی را تعریف کرد و مرتب شدن یا بررسی تکرار تنها با عملگری مانند hash امکانپذیر است. از سوی دیگر کارایی آن نیز متفاوت است.
نکته: این کلاس پیمایش معکوس با reverse_iterator را پشتیبانی نمی‌کند.
کلاس multiset
[برگرد بالا]
کلاس multiset همانند کلاس set عمل می‌کند. با این تفاوت که امکان درج عناصر تکراری نیز وجود دارد:
// multiset<type> name;
multiset<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(multiset<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
cout << *it << "\t";
// output: 1 2 2 3 4 5
for(multiset<int>::reverse_iterator it = mySet.rbegin() ; it != mySet.rend() ; it++)
cout << *it << "\t";
// output: 5 4 3 2 2 1
در این کلاس اگر عمل حذف با استفاده از erase (مشخص بودن iterator) صورت گیرد، تنها همان عنصر حذف می‌شود. اما دستوری مانند (2)remove تمامی اعداد 2 در مجموعه را پاک می‌کند.
این کلاس مناسب برای زمانی‌ست که داده‌ها را یکی یکی دریافت می‌کنیم و نیاز داریم ترتیب عناصر به صورت مرتب شده باشند. با توجه به آنکه تکرار نیز مجاز است، هیچ کدام از عناصر نادیده گرفته نمی‌شوند.
کلاس unordered_multiset
[برگرد بالا]
این کلاس ترکیبی از خواص کلاس‌های multiset و unordered_set را دارد و ضمن امکان درج عنصر تکراری، عناصر را بدون نظم ظاهری خاص ذخیره می‌کند:
// unordered_multiset<type> name;
unordered_multiset<int> mySet = {1, 4, 3, 5, 2};
mySet.insert(2);
for(unordered_multiset<int>::iterator it = mySet.begin() ; it != mySet.end() ; it++)
cout << *it << "\t";
// output: 2 2 1 4 3 5
کلاس map
[برگرد بالا]
به زبان ساده، یک map نوعی آرایه است که به جای متناظر کردن یک عدد نامنفی (به عنوان اندیس) به یک مقدار، امکان انتخاب اندیس از هر نوع داده یا ساختار و کلاس را فراهم می‌کند:
// map<key_type, value_type> name;
map<string, double> scores;
map<char, int> cipher;
scores["std1"] = 18.2;
scores["std3"] = 17.4;
scores["std2"] = 19;
scores["std1"] = 18.1;
cipher['a'] = 246;
for(map<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: std1: 18.1 std2: 19 std3: 17.4
cout << cipher['a'] << "\t" << cipher['b'];
// output: 246 0
for(map<char, int>::iterator it = cipher.begin() ; it != cipher.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: a: 246 b: 0
هر عنصر map از زوج مرتبی به صورت <کلید، مقدار> تشکیل شده است که به ازای هر کلید یک مقدار ثبت می‌شود. همانگونه که در قطعه کد فوق نیز مشخص است، کلید نقش اندیس را بازی می‌کند. بنابراین کلیدها منحصر به فرد هستند. در صورتی که مقدار برای کلیدی که هنوز مقداری تخصیص داده نشده درخواست شود (مانند کاراکتر b در مثال فوق)، مقدار پیش‌فرض نوع داده برای آن در نظر گرفته شده و این زوج به map اضافه می‌شود. در صورتی که بخواهیم بدون اضافه شدن چنین زوجی موجود بودن آن را بررسی کنیم، می‌توان از متد find استفاده کرد.
متدهای insert و erase برای درج و حذف در این ظرف نیز وجود دارند. همچنین عناصر ظرف در پیمایش از ابتدا به انتها بر اساس کلیدها مرتب هستند.
تذکر: شبیه بودن map به آرایه دلیل بر ذخیره‌سازی مشابه نیست و تشابه آنها صرفا از بعد دسترسی تصادفی و مستقیم با اندیس است.
کلاس unordered_map
[برگرد بالا]
تفاوت این کلاس و کلاس map همان تفاوتی است که بین کلاس‌های set و unordered_set وجود دارد. در این کلاس روش ذخیره شدن نسبت به map متفاوت بوده و ترتیب عناصر نظم مشخصی ندارد:
// unordered_map<key_type, value_type> name;
unordered_map<string, double> scores;
unordered_map<char, int> cipher;
scores["std1"] = 18.2;
scores["std3"] = 17.4;
scores["std2"] = 19;
scores["std1"] = 18.1;
cipher['a'] = 246;
for(unordered_map<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: std2: 19 std3: 17.4 std1: 18.1
cout << cipher['a'] << "\t" << cipher['b'];
// output: 246 0
for(unordered_map<char, int>::iterator it = cipher.begin() ; it != cipher.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: b: 0 a: 246
کلاس multimap
[برگرد بالا]
در کلاس multimap امکان ذخیره کردن چند مقدار با یک کلید فراهم شده است. اما نمی‌توان با استفاده از عملگر = مقدار را مستقیما به کلید اختصاص داد. بلکه باید از متد insert استفاده کرد:
// multimap<key_type, value_type> name;
multimap<string, double> scores;
scores.insert(pair<string, double>("std1", 18.2));
scores.insert(pair<string, double>("std3", 17.4));
scores.insert(pair<string, double>("std2", 19));
scores.insert(pair<string, double>("std1", 18.1));
for(multimap<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: std1: 18.2 std1: 18.1 std2: 19 std3: 17.4
در کل عملگر [] برای این کلاس سربارگذاری نشده است و نمی‌توان از آن استفاده کرد. با توجه به اینکه هر کلید ممکن است چندین مقدار مختلف داشته باشد، نمی‌توان به iterator بازگشتی از متد find اکتفا کرد. متد equal_range متد دیگری‌ست که با دریافت کلید یک زوج مرتب (pair) از iteratorها باز می‌گرداند که ابتدا و انتهای بازی مقادیر با آن کلید را مشخص می‌کنند.
کلاس unordered_multimap
[برگرد بالا]
کلاس unordered_multimap ترکیبی از کلاس‌های multimap و unordered_map است. به این ترتیب که اجازه درج مقادیر مختلف با یک کلید را داده، اما لزوما به صورت مرتب شده قابل بازیابی نیستند:
// unordered_multimap<key_type, value_type> name;
unordered_multimap<string, double> scores;
scores.insert(pair<string, double>("std1", 18.2));
scores.insert(pair<string, double>("std3", 17.4));
scores.insert(pair<string, double>("std2", 19));
scores.insert(pair<string, double>("std1", 18.1));
for(unordered_multimap<string, double>::iterator it = scores.begin() ; it != scores.end() ; it++)
cout << it->first << ": " << it->second << "\t";
// output: std2: 19 std3: 17.4 std1: 18.1 std1: 18.2
توجه: تمام کلاس‌های unordered در نسخه 11++C اضافه شده‌اند.
کلاس stack
[برگرد بالا]
کلاس stack برای پیاده‌سازی پشته در زبان برنامه‌نویسی ++C استفاده می‌شود و با استفاده از متدهای push و pop می‌توان به ترتیب عملیات درج و حذف از پشته را انجام داد. همچنین متد top مقدار اولین عنصر روی پشته را بدون حذف آن از پشته باز می‌گرداند و متد empty خالی بودن پشته را بررسی می‌کند:
// stack<type> name;
stack<int> myStack;
myStack.push(1);
myStack.push(3);
myStack.push(4);
myStack.push(6);
myStack.push(5);
while(!myStack.empty()) {
cout << myStack.top() << "\t";
myStack.pop();
}
// output: 5 6 4 3 1
کلاس queue
[برگرد بالا]
از کلاس queue برای پیاده‌سازی صف استفاده می‌شود که شامل دو متد push و pop برای درج و حذف، متد front برای دریافت عنصر اول صف و empty برای بررسی خالی بودن آن است:
// queue<type> name;
queue<int> myQueue;
myQueue.push(1);
myQueue.push(3);
myQueue.push(4);
myQueue.push(6);
myQueue.push(5);
while(!myQueue.empty()) {
cout << myQueue.front() << "\t";
myQueue.pop();
}
// output: 1 3 4 6 5
کلاس priority_queue
[برگرد بالا]
کلاس priority_queue برای پیاده‌سازی صف اولویت‌دار استفاده می‌شود؛ ولی بر خلاف کلاس queue متد top را برای دریافت عنصر جلوی صف دارد. پیش‌فرض اولویت در این کلاس بزرگ بودن مقدار عنصر است و عملکردی مشابه درخت هیپ دارد:
// priority_queue<type> name;
priority_queue<int> myQueue;
myQueue.push(1);
myQueue.push(3);
myQueue.push(4);
myQueue.push(6);
myQueue.push(5);
while(!myQueue.empty()) {
cout << myQueue.top() << "\t";
myQueue.pop();
}
// output: 6 5 4 3 1
کلاس dequeue
[برگرد بالا]
این کلاس صف دو طرفه را پشتیبانی می‌کند و شامل متدهای push_front و push_back برای درج از دو طرف، pop_front و pop_back برای حذف از دو طرف، front و back برای بررسی عناصر سر صف و empty برای بررسی خالی بودن است:
// deque<type> name;
deque<int> myQueue;
myQueue.push_front(1);
myQueue.push_front(3);
myQueue.push_back(4);
myQueue.push_back(6);
myQueue.push_front(5);
while(!myQueue.empty()) {
cout << myQueue.front() << "\t";
myQueue.pop_front();
}
// output: 5 3 1 4 6
توجه: کلاس‌های مرتبط با پشته و انواع صف به خاطر نوع ورودی و خروجی کاربردهای منحصر به خود را دارند و تا حد ممکن به صورت بهینه پیاده‌سازی شده‌اند. اما در صورت نیاز می‌توان عملکرد آنها را با کلاس‌هایی مانند array و list شبیه‌سازی کرد.