فصل ۱۶ دایتل: الگوریتم های موجود در کتابخانه استاندارد

در این فصل قراره که یاد بگیریم چطور با استفاده از iteratorها و algorithm(الگوریتم)های موجود در کتابخانه استاندارد سی++ یا همون STL کارهامون رو پیش ببریم. یاد میگیریم که توابع لاندا چی هستن و چطور ازشون استفاده بکنیم، اشاره‌گر به تابع چیه و چطور میشه ازش استفاده کرد و چیزهای دیگه.

نکاتی درباره پیمایش‌گر ها (Iterators)

اینکه یه کانتینر از چه iterator هایی پشتیبانی میکنه مشخص کنندهٔ اینه که از چه الگوریتم هایی میشه برای این کانتینر استفاده کرد. به عنوان مثال کانتینر های vector و array. این دو کانتینر از random-access iterator پشتیبانی میکنن(وقتی از این نوع پشتیبانی میکنن یعنی از بقیه انواع پیمایش کننده ها هم پشتیبانی میکنن) و این یعنی همهٔ الگوریتم های موجود رو میشه براشون استفاده کرد. البته نکته اینجاست که الگوریتم هایی که سایز کانتینر رو تغییر میدن برای array قابل استفاده نیستن. بنابراین مهم نیست که کانتینر چیه، اگه اون کانتینر، حداقل نوع iterator مورد نیاز برای یه الگوریتم رو ساپورت بکنه، میشه از اون الگوریتم براش استفاده کرد.

باطل شدن پیمایش ها (iterator invalidation)

ایتریتور ها درواقع یک اشاره گر کپسوله شدن هستند که به عناصر کانتینر اشاره میکنن بنابراین ممکنه در صورت بروز یک سری تغییرات در کانتینر (که بهکانتینر بستگی داره)، این اشاره گر اعتبارشو از دست بده و باطل بشه. پروسهinvalidate شدن اشاره گر ها، رفرنس ها و ایتریتور ها در بخش 23 استاندارد سی++ موجوده و ما اینجا فقط خلاصه ای از اونها رو بررسی می‌کنیم.

اضافه کردن یه عنصر به کانتینر:

• در vector ها، اگر اضافه کردن عنصر ما باعث بشه که وکتور اقدام به درخواست فضای بیشتر و در نتیجه reallocate شدن بکنه، تمام iterator هایی که مربوط به این وکتور بودن باطل میشن. در غیر این صورت، هر iterator ای که به فضای بین مکان عنصری که تازه اضافه شده و مکان آخرین عنصر موجود اشاره میکنه باطل میشه.
• در deque ها، همه iterator ها باطل میشن.
• در list, forward_list و ordered associative container ها هیچ تغییری در iterator ها بوجود نمیاد
• در unordered associative container ها تنها اگر عمل reallocation انجام بگیره، همه iterator ها باطل میشن.

حذف کردن یک عنصر از کانتینر باعث میشه iterator ای که به اون عنصر اشاره می‌کنه باطل بشه. علاوه بر اون:

• در وکتور ها از اونجایی که عنصر حذف شده تا آخرین عنصر هر پیمایش‌گری وجود داشته باشه غیر فعال میشه
• در deque ها اگر حذفی که رخ داده در جایی غیر از ابتدا یا انتهای کانتینر باشه باعث میشه کل پیمایشگر ها باطل بشن.

توابع لاندا

خیلی از الگوریتم های موجود در STL میتونن یک تابع‌‌‌‌‌‌رو به عنوان ورودی خودشون داشته باشن. همونطور که قبلا می‌دونیم، اسم یک تابع به صورت ضمنی یک اشاره گر به ابتدای کد اون تابع هست. اما یک راه هم وجود داره که تابع خودمون رو منحصرا برای اون الگوریتمی که داریم ازش استفاده میکنیم بنویسیم و اون رو دقیقا کنار بقیه آرگومان ها بنویسیم! برایاینکار یک مفهوم به اسم توابع لاندا به کارمون میاد که در واقع توابعی هستند که اسم ندارند و اصطلاحا بهشون میگن anonymous function.

برای اینکه دقیق تر متوجه بشیم، در ادامه یک مثال رو بررسی می‌کنیم.

یکی از الگوریتم های جالبی که در STL وجود داره، اسمش for_eachهست. این تابع میاد بازه ای از یک کانتینر رو میگیره و تابعی که ما بهش میدیم رو برای تمام عناصر موجود در اون بازه اجرا میکنه. بهتره که کد رو ببینیم:

خب همونطور که می‌بینیم، تابع for_each برای دوتا آرگومان اولش دوتا iterator میگیره و آرگومان سومش یه تابع رو به عنوان ورودی دریافت می‌کنه. توی این مثال ما دوتا for_each زدیم که اولی میاد و صرفا عناصر رو ضربدر ۲ میکنه و چاپ می‌کنه و دومی میاد جمع همهٔ عنصر هارو محاسبه می‌کنه. چجوریش رو میگم حالا.

سینتکس توابع لاندا

خب آرگومان اول و دوم که واضحن. میمونه آرگومان سوم که یه تابع لانداست. سینتکس توابع لاندا این شکلی ان:

[introducer](input arguments) {function  body}

خب همونطور که می‌بینید توابع لاندا با یک [] شروع میشن که اصطلاحا بهشون میگن lambda introducer. بقیه‌ش تقریبا مثل تابع معمولیه و  لیست پارامتر های ورودی میاد و در ادامه بدنه تابع قرار داره.

توابع لاندا میتونن به متغییر های محلی(local) جایی که دارن داخلش تعریفمیشن دسترسی داشته باشن. مثلا توی مثال بالا تابع های لاندای ما میتونن بهمتغییر هایی که داخل main تعریف شده دسترسی داشته باشن. اینجاست که lambdaintroducer به کار میاد. درواقع lambda introducer به ما اجازه میده که مشخص کنیم از کدوم متغییر های موجود میخوایم استفاده کنیم. به اینکار اصطلاحا میگن capture کردن متغییر ها.

توی اولین for_each می‌بینیم که lambda introducer خالیه واین یعنی تابع لاندای ما نمیخواد از هیچ متغییری استفاده کنه. و توی دومی ما این رو می‌بینیم: ‎[&sum] و این یعنی رفرنسی از متغییر sum رو در دسترس تابع قرار میده که ازش استفاده بکنه. دلیل اینکه از رفرنس استفاده شده هم اینه که بتونیم متغییر اصلی که داخل main قرار داره رو modify کنیم.

برگردوندن مقدار در توابع لاندا

تا الآن تابع های لاندای ما هیچ مقدار بازگشتی ای نداشتن و بنابراین به صورت پیشفرض مقدار بازگشتیشون به عنوان void مشخص میشد. اما اگر داخل تابع لاندامون یه return داشته باشیم نیاز داریم که نوع مقدار بازگشتی رو از طریق سینتکس trailing return type مشخص کنیم.

اینطوریه :

-> type

که اگر بخوام توی کد نشون بدم اینطوری میشه:

[] () -> int {return 2}

همونطور که می‌بینیم، جاش بین لیست پارامتر ها و بدنه تابع‌ست.

الگوریتم ها

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

mismatch

وظیفهٔ این تابع اینه که بین دوتا کانتینر بگرده و اونجایی که دوتا خونهمتناظر باهم یک مقدار مساوی نداشته باشن، می‌ایسته و اطلاعات اون مکان رو (به شکل یک pair از iterator های هردو کانتینر) بهمون برمیگردونه. این تابع ۴ تا ورودی داره(اونی که توی کتاب نشون داده اینطوریه) که دوتای اول بازه رو برای کانتینر اول مشخص میکنن و دوتای دوم بازه رو برای کانتینر دوم مشخص میکنن.

inserter ها

بیاین تابع merge رو باهم ببینیم:

vector<int> a1{1, 2, 3};
vector<int> a2{4, 5, 6};
vector<int> result;
std::merge(a1.begin(), a1.end(), a2.begin(), a2.end(), result.begin());

توی مثال بالا، وکتور result باید حتما به اندازه ۶ تا خونه جا داشته باشه تا a1 و a2 داخلش ذخیره بشن. بنابراین باید قبل از اجرای تابع merge، باید تخصیص حافظه صورت بگیره.

اما زمانی هست که ما نمی‌خوایم از قبل حافظه ای تخصیص بدیم و میخوایم یککلاسی مثل وکتور، خودش اینکار رو به ازای اضافه شدن عناصر جدید انجام بده.اینجاست که inserter ها (از هدر iterator) به کمک ما میان. مثال بالا اگر اجرا بشه به مشکل میخوره چراکه result به اندازه کافی جا نداره. حالا با استفاده از inserter این مشکل رو برطرف می‌کنیم:

vector<int> a1{1, 2, 3};
vector<int> a2{4, 5, 6};
vector<int> result;
std::merge(a1.begin(), a1.end(), a2.begin(), a2.end(), back_inserter(result));

تابع back_inserter درواقع میاد و به ازای هر عنصری که میخواد به result اضافه بشه، تابع push_back مربوط به کانتینر result رو صدا می‌زنه. به همین راحتی (:

Function Object ها

همونطور که می‌دونیم، بسیاری از الگوریتم های موجود در کتابخونه استاندارد میتونن یک تابع رو به عنوان آرگومان آخرشون بگیرن. تا اینجا دیدیم که این تابع میتونه یک function pointer یا یک تابع لاندا (lambda function) باشه. کلاس هایی که میتونن توابع لاندا یا اشاره گر به توابع رو به عنوان ورودی بگیرن، میتونن یک نوع دیگه از تابع رو هم دریافت کنن که اسمش function object هست. function object درواقع یک شئ از کلاسی هست که اوپراتور پرانتزش overload شده. یعنی ما در member function های کلاس، یک تابع به اسم operator()‎ تعریف کردیم.

اشیاء ای که از این کلاس ما ساخته میشن میتونن بجای تابع لاندا یا اشارهگر به تابع استفاده بشن.(درواقع خود توابع لاندا توسط کامپایلر به یک اشاره گر به تابع یا function object تبدیل میشن تا بشه روشون بهینه سازی انجام داد).

در بیشتر جاها(و نه همه جا) میشه بجای function object از تابع لاندا یا اشاره گر به تابع استفاده کرد.

از طریق هدر <functional> میتونیم به function object های از پیش تعریف شدهٔ STL دسترسی داشته باشیم که خیلی هم کاربردی و خفنن. تابع less<T>‎ که توی مثال‌های بالا(بخش set و …) دیدیم جزئی از function object های موجود در STL عه.

مزایای function object ها

اولین تفاوتش با لاندا و امثالهم اینه که از اونجایی که عضوی از یک کلاسه، کامپایلر راحت تر میتونه بهینه سازی هایی مثل inline کردن رو انجام بده.

دومین تفاوت که یک نقطه قوت محسوب میشه، قابلیت استفاده از data member های کلاس هست.

پایان

این فصل هم تموم شد. مثل فصل های قبلی با تاخیر اما برخلاف فصل های قبلی، تاخیرش زیاد نبود! فصل بعدی توی مدیریت استثنا ها و خطا ها عمیق میشیم.