نکات فصل ۱۵ دایتل – کتابخانه استاندارد

توی این فصل سه بخش از کتابخانه استاندارد سی++ که بهش STL هم میگن رو بررسی می‌کنیم. container ها، iterator ها و algorithm ها. فصل بسیار مهمیه چراکه این کتابخونه بسیاری از کار های مارو راحت تر می‌کنه و اگر خوب بلد باشیم ازش استفاده کنیم، دهن خودمون رو برای پیاده سازی کردن خیلی از چیز ها صاف نمی‌کنیم.

کانتینرها

کانتینر ها یک ساختمان داده ای هستند که تقریبا میشه همه نوع داده ای روتوشون ذخیره کرد. درکل سه نوع کانتینر داریم که به شکل زیر دسته بندی میشن:

• first class containers
• container adapters
• near containers

یک نوع دسته بندی دیگه هم وجود داره که کانتینر هارو به ۴ بخش تقسیم می‌کنه:

• Sequence containers
• Ordered associative containers
• unordered associative containers
• container adapters

بخش sequence containers و associative containers درواقع به عنوان first class container در نظر گرفته میشن.

container adapter در اصل همون first class container ها هستن که عملیات هاشون محدود شده. این کانتینر شامل استک، صف و … هست.

یک نوع کانتینر دیگه هم داریم که بهشون میگن near containers. دلیل اینکه اسمشون رو به این شکل انتخاب کردن اینه که این کانتینر ها بعضی از قابلیت های first-class container هارو دارن و بخش دیگه ایشون رو ندارن. مثالی که میشه از این کانتینر ها زد؟ built-in array ها، کلاس های مربوط بهbitset و valarray ها(که برای انجام عملیات های سریع ریاضی روی وکتور ها* بکار میره) و …

*اون وکتور، با vector ای که توی کانتینر ها داریم فرق داره.

توی جدول زیر میتونیم لیست کانتینر ها و ویژگی‌هاشون رو ببینیم که خیلی جالبه:

نکاتی درباره پرفورمنس کانتینر ها

• اضافه/حذف کردن به/از آخر vector ها سریعه. اما اضافه/حذف کردن به/از اول و یا وسط vector ها به صرفه نیست
• اگرنیاز داریم که صورت مفرط به ابتدا/انتها کانتینرمون المان اضافه(یا حذف) بکنیم بهتره از deque (تلفظ میشه دِکْ) استفاده بکنیم چرا که عملیات هاش در ابتدا و انتهای کانتینر سریعن
• در آخر اگه نیاز داریم که در وسط کانتینر هم چیزی رو حذف کنیم یا اضافه کنیم، بهتره از list استفاده بکنیم.

Sequence Container ها:

وکتور ها (vector)

وکتور کانتینری هست که از خونه های متوالی حافظه استفاده میکنه. در واقعدر لایه های زیرین وکتور میاد و با یک اندازه ثابت یک آرایه تخصیص میده. بعد از پر شدن آرایه، یک آرایه با اندازهٔ بیشتر از حافظه میگیره و اطلاعاتآرایه قبلی رو در آرایه جدید کپی میکنه(یا move میکنه) و آرایه قبلی رو حذف می‌کنه. در واقع این قابلیت آرایه بودن این امکان رو بهش میده که بشه به صورت آنی به المان های وکتور دسترسی پیدا کرد.

اگر می‌دونیم که حدودا قراره چه مقدار داده به وکتور اضافه کنیم، بهتره با استفاده از توابع resize یا reserve اون حافظه رو برای وکتور بگیریم تا از تخصیص و حذف پی در پی حافظه جلوگیری کنیم.

اینکه چطور یک وکتور اقدام به افزایش حافظه میکنه بستگی به پیاده سازی داره و ممکنه توی کامپایلر های مختلف، نتیجهٔ متفاوتی داشته باشه. در حالت کلی این یک time-space tradeoff هست.

فرق بین clear و erase

فرق این دو این هست که تابع clear کل اعضای وکتور رو پاک میکنه اما erase این قابلیت رو داره که تک عضو و یا یک رنج از عضو ها رو از وکتور پاک کنه.

لیست ها (list)

لیست که درواقع یک لیست دو پیوندی هست (doubly linked list) اجازهٔ اضافه و حذف کردن سریع در هر جای کانتینر رو میده اما در حالت کلی اگر بیشتر عملیات هامون قراره در دو انتهای کانتینر باشه، بهتره که از دِک (deque) استفاده کنیم.

تابع unique

این تابع عناصر تکراری یه کانتینر رو حذف می‌کنه. البته برای اینکه درستکار کنه کانتینر ما از قبل باید سورت شده باشه تا عناصر تکراری کنار هم قرار بگیرن.

دِک ها (deque)

کلاس دک درواقع نکات مثبت وکتور و لیست رو توی خودش جمع کرده. کلمهٔ deque کوتاه شدهٔ double-ended queue هست. این کلاس قابلیت دسترسی سریع و مستقیم به عناصر داره و همچنین عملیات هایی که در دو سمت انتهایی این کانتینر انجام میشن سریعن.

از اونجایی که از random-access iterator ها ساپورت میکنه بنابراین همهٔالگوریتم های کتابخونه استاندارد میتونن روی این کلاس اعمال بشن.

در حالت کلی دک سربار بیشتری از وکتور داره و همچنین حذف و اضافه کردن در وسط دک ها بهینه تر از وکتوره(همچنان کند تر از لیست ها)

حالا که یک دید کلی از Sequence container ها داریم، به Associative Container ها می‌پردازیم:

این کانتینر ها قابلیت این رو به ما میدن که با استفاده از یک کلید بتونیم به صورت مستقیم به مقادیر مورد نظرمون دسترسی داشته باشیم. ۸ نوع کلاس وجود داره که ۴ تای اول کلید هارو به صورت مرتب ذخیره میکنن و ۴ تای دوم، ترتیب کلید ها براشون مهم نیست.

• multiset, set, multimap, map
• unordered_multiset, unordered_set, unordered_multimap, unordered_map

کلاس های set و multiset به ما یه مجموعه ای از مقادیر رو میدن که خود اون مقدار ها، کلید هم هستن. فرق اصلی این دو کلاس اینه که کلاس set اجازه نمیده مقادیر تکراری به مجموعه اضافه بشن اما کلاس multiset این اجازه رو میده.

کلاس های map و multimap یه مجموعه به ما میدن که هر کلید، به یک مقدار وصله. فرقشون هم اینه که در کلاس map نمیشه یک کلید چند مقدار متفاوت داشته باشه اما این امر توی multimap امکان پذیره.

کلاس multiset

این کلاس که از هدر <set> میتونیم بهش دسترسی داشته باشیم به ما قابلیت ذخیره سازی و بازیابی سریع مقادیر رو میده همچنین قابلیت این رو داره مقادیر تکراری رو ذخیره کنه. این کلاس برای مرتب کردن عناصرش از چیزی به نام comparator function object استفاده می‌کنه که توی فصل بعد بهش می‌پردازیم. اگر ترتیب مقدار ها مهم نیست بهتره که از unordered_multiset استفاده بکنیم چراکه سربار کمتری داره(هدر<unordered_set>) . مثال برای استفاده از multiset:

std::multiset <int, less<int>> values;

که در اینجا اون less<int> یک comparator function object هست(اختیاری) و باعث میشه مقادیر ما به صورت صعودی مرتب بشن.

کلاس set

این کلاس تنها فرقی که با multiset داره اینه که عناصر تکراری رو ignore میکنه و درواقع همهٔ عناصر موجود در اون، یکتا هستن.

کلاس multimap

این نوع از associative container  که از طریق هدر map میشه بهش دسترسی داشت به ما این قابلیت رو میده که مقادیر رو به صورت «جفت»(pair) ذخیره کنیم. یعنی اینکه به ازای هر مقدار، یک کلید وجود داره. اینکه کلید ها به چه ترتیبی مرتب بشن رو میشه از طریق comparator function ها تعیین کرد. کلاس multimap اجازه میده که کلید های تکراری داشته باشیم یعنی یک کلید میتونه چندین مقدار داشته باشه که بهش میگن one-to-many relationship و احتمالا بخاطر همینه که برای این کلاس random-access iterator نذاشتن.

کلاس map

این کلاس شبیه multimap عه تنها با این تفاوت که امکان وجود کلید تکراری نیست. یعنی هر کلید فقط به یک مقدار اشاره میکنه (one-to-one mapping) و همچنین این قابلیت وجود داره که به مقدار هر کلید به صورت آنی دسترسی داشته باشیم. ( با استفاده از اوپراتور []).

هردو کلاس قبلی که گفته شد دارای یک نسخه غیر مرتب هم هستند که سربار کمتری داره و برای استفاده ازشون کافیه یه unordered_ پشت اسم کلاس بذاریم.

نکاتی درباره Container Adapter ها:

این کانتینر ها در اصل همون first class container ها هستند که عملیات هاشون محدود شده و از iterator پشتیبانی نمی‌کنن. بنابراین لایه زیرین کلاسهای این کانتینر از کلاس های first class container ها تشکیل میشه.

• کلاس stack که یک استک رو میسازه، به صورت پیشفرض از deque استفاده می‌کنه.
• کلاس queue که یک صف رو میسازه، به صورت پیشفرض از deque استفاده می‌کنه.
• کلاسpriority_qeueu که یک صف اولویت دار رو میسازه(صفی که مقادیر داخلش معمولا با استفاده از تکنیک heap، مرتب شده‌ند)، به صورت پیش‌فرض از کلاس vector به عنوان لایه زیرین خودش استفاده می‌کنه comparator function هم داره.

پیمایش کننده ها (Iterators)

ایتریتور ها چیزی شبیه به پوینتر ها هستند که قابلیت های بیشتری دارن و برای دسترسی و تغییر المان های یک کانتینر بکار میرن. مکانیسم دسترسی و پیمایش در یک کانتینر رو کپسوله میکنن و این به الگوریتم ها اجازه میده که بدون وابستگی به پیاده سازی لایه کانتینر، بتونن کار خودشون رو انجام بدن.

چند تابع داریم که میتونن برامون یک iterator برای یک کانتینر و یا حتی یک آرایه بسازن.

توابع begin و end که یک اشاره گر به اعضاء کانتینر میسازن( از سی++ ۱۱ به بعد میتونن یک پوینتر از built-in array ها بسازن حتی) و توابع cbeing, cend که یک ایتریتور const میسازن و rbegin, rend, crbegin, crend که قابلیت پیمایش برعکس روی یک آرایه رو میدن(از سی++ ۱۴ به بعد).

الگوریتم ها

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

خب این فصل تقریبا طولانی هم تموم شد. هرچند مثل همیشه خیلی روش تمرکز نداشتم. اما تازگی دارم از تکنیک پومودورو استفاده می‌کنم و فعلا که جواب داده. فصل بعد هم درباره کتابخانه استاندارد صحبت می‌کنیم و بیشتر تمرکزمونروی بخش الگوریتم های این کتابخونه هست. بوس.