فصل ۲۲ دایتل: نکات اضافه

توی این فصل درمورد struct ها، bit field ها، اوپراتور های بیتی (bitwise) و توابع مربوط به دستکاری رشته های در سی صحبت شده.

البته دو مورد آخر رو من بلد بودم بنابراین توی این پست دربارشون چیزی نمی‌نویسم. راستی، این آخرین فصل کتاب فیزیکیه 🙂

structure ها

نکته جالب اینکه struct ها تقریبا همون کلاس ها هستند و تنها تفاوت‌شون اینه که اعضای یک struct بر خلاف کلاس، به صورت پیش‌فرض public هست و همچنین نوع ارث بری به صورت پیش‌فرض public هست(که در کلاس ها private هست).

typedef و using

همونطور که از قبل می‌دونستیم، از typedef برای تعریف کردن alias برای انواع داده هامون استفاده می‌کردیم. مثلا:

typdef char* string;

توی سی++ ۱۱ قابلیتی اضافه شده که میشه اینکار رو با استفاده از using انجام داد و عبارت پایین برابر با همون typedef عمل می‌کنه:

using string = char*;

Binary Literals ها

در سی++‌۱۴ میتونیم از Binary Literal ها استفاده بکنیم.

برای اینکار کافیه که پشت عبارتمون، کاراکتر 0b یا 0B رو قرار بدیم:

const unsigned binary{0b1000000'00000000'00000000'00000000};

Bit Field ها

‌سی++‌ این امکان رو به ما میده که تعیین کنیم یک عضو خاص(از نوع int یا enum) یک کلاس یا یک struct چقدر از حافظه رو اشغال بکنه(تعداد بیت ها). به عضوی که این قابلیت براش استفاده شده باشه میگن Bit Field.

struct BitCard {
unsigned face : 4;
unsigned suit : 2;
unsigned color : 1;
};

با توجه به مثال بالا، اندازهٔ حافظه ای(تعداد بیت ها) که میخوایم عضو ما داشته باشه رو با یک «:» جدا می‌کنیم.

اصطلاحا به اندازه ای که تعیین می‌کنیم میگن width of the bit field.

unnamed bit field

سی++ این امکان رو به ما میده که عضوی تعریف بکنیم که به عنوان padding استفاده بشه. این عضو هیچ اسمی نداره و صرفا به تعداد بیت ای که مشخص می‌کنیم، حافظه رو رزرو می‌کنه و اون بخش از حافظه قابل استفاده نیست.

struct Example {
unsigned a : 13;
unsigned : 3; // align to next storage-unit boundary
unsigned b : 4;
};

توی مثال بالا تعیین کردیم که ۳ بیت از حافظه رزرو بشه.

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

در این حالت خود کامپایلر میاد و هرچقدر که فضا در اون واحد حافظه باقی مونده رو رزرو می‌کنه. عضو بعدی ای که تعریف می‌کنیم در یک واحد دیگه قرار می‌گیره.

struct Example {
unsigned a : 13;
unsigned : 0; // align to next storage-unit boundary
unsigned b : 4;
};

نکات بیت فیلد ها

  • نباید با استفاده از اوپراتور & سعی کنیم که آدرس یک بیت فیلد رو بگیریم.
  • استفاده از بیت فیلد ها باعث میشه که کامپایلر کد کندتری رو تولید بکنه. بخاطر اینکه محاسبه های بیشتری برای پیدا کردن آدرس های حافظه باید انجام بده.

پایان

خب این فصل هم به پایان رسید و رسما فصل های موجود در کتاب pdf «آموزش برنامه نویسی سی++ دایتل» تموم شد. از این به بعد نکات اضافی ای که از منابع دیگه یاد میگیرم رو در پست های جدا می‌نویسم. کتاب جالبی بود 🙂

فصل ۲۱ دایتل: رشته ها

توی این فصل در مبحث رشته ها در سی++ بیشتر عمیق میشیم. درواقع کلاس string از STL رو بررسی می‌کنیم.

پست کوتاهیه چون بیشتر چیزها رو بلد بودم 🙂

تابع compare

این تابع جالبیه که باهاش میتونیم بخش خاصی از یک رشته رو با بخش خاصی از یک رشته دیگه مقایسه کنیم.

اینطوری:

string str1{"This is string"};
string str2{"oh This string"};
if (str1.compare(0, 3, str2, 3, 5)) {
// do something
}

تابع replace و نکته‌ش

تابع replace میاد و از مکانی که براش مشخص می‌کنیم میگرده و مقدار مشخص شده رو پیدا می‌کنه و رشتهٔ جایگزین رو بجاش می‌ذاره.

نکته‌ش اینه که اگر مثلا شما دنبال یک رشته بگردید که ۲ کاراکتر داره و بخواین این زیر رشته رو با یک رشته که ۴ کاراکتر داره جایگزین کنید، ۲ کاراکتر بعد از رشته مورد جستجوی ما از بین میره.

الآن حوصله نوشتن مثال ندارم. امیدوارم گنگ نگفته باشم 🙂

برای اینکه به این مشکل برنخوریم بهتره که اول موقعیت رخداد رشته مورد جستجو رو با استفاده از تابع find پیدا بکنیم و بعد با استفاده از تابع insert رشته مورد نظرمون رو بذاریم بجاش.

تبدیل رشته به عدد

توابعی که برای اینکار وجود دارن اینا هستن:

توابع مربوط به تبدیل رشته به عدد

تابع هایی که می‌بینیم درواقع ۳ تا ورودی دارن(به جز تابع های مربوط به اعداد اعشاری که ورودی سوم رو ندارن) که دوتای آخرشون default دارن.

  • ورودی اول: رشته ای که میخوایم به عدد تبدیل بشه
  • یک اشاره گر به size_t برای ذخیره کردن اولین اندیسی که این تابع قادر به تبدیلش نبوده
  • یک عدد صحیح بین ۲ تا ۳۶ که مبنای عدد رو مشخص می‌کنه.

به عنوان مثال فرض کنیم str یک رشته است که مقدار “123” در اون ذخیره شده. اینطور میشه به int تبدیلش کرد:

int convertedInt = stoi(str, nullptr, 10);

دوتا آرگومان آخر دلخواه هستند و میشه اونهارو ننوشت.

پایان

خیلی خوبه که بیشتر نکات این چندفصل آخر رو بلد بودم و دارم سریع پیش میرم 🙂 باعث میشه اعتماد به نفس بهتری داشته باشم.

فصل ۱۹ دایتل: نکاتی درباره پیاده سازی ساختمان داده ها

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

کلاس Self-Referential

کلاس های خود ارجاعی به کلاسی گفته میشه که یک data member داشته باشه که به یک شئ از جنس خود کلاس اشاره میکنه.

نام های وابسته و غیر وابسته (dependent names vs non-dependent)

به کد زیر توجه کنید:

توابعی که توی این کد استفاده شده در کلاس List تعریف شدن.

همونطور که می‌بینید، کلاس Stack از کلاس List که یک class template هست ارث بری کرده و همونطور که می‌دونیم، تمپلیت ها درواقع همون function overloading هستند که وقتی type رو براشون مشخص می‌کنیم، کامپایلر با اون type مشخص شده کد رو تولید می‌کنه.

خط ۱۳ و خط ۱۸ نمونهٔ اسم های وابسته هستن.

یعنی چی؟ یعنی اینکه تا وقتی نوع STACKTYPE مشخص نشده باشه، کد کلاس List تولید نشده و در نتیجه توابع ذکر شده هم تولید نشدن و کامپایلر این رو می‌فهمه(چون می‌بینه در ورودی‌شون یه STACKTYPE دارن).

خط ۲۳ و ۲۸ نمونه اسم های غیر وابسته یا non-dependent هستن.

این تابع ها(مثل isEmpty و print) چون هیچ ورودی ای ندارن، پس وابسته به type نیستند و کامپایلر وقتی به خطی می‌رسه که داره تابع print رو صدا می‌زنه،‌ گمون می‌کنه که این یک تابع معمولیه و کدش موجوده(درحالی که این تابع جزئی از کلاس List هست و تا مشخص شدن STACKTYPE کدی براش تولید نمیشه).

این مسئله باعث میشه ارور بوجود بیاد.

برای اینکه به کامپایلر بفهمونیم این توابع نباید در زمان دیده شدن resolve بشن و resolve شدن‌شون رو باید به بعد از تولید کد template موکول کرد، از کلمه this استفاده می‌کنیم.

پایان

فصل بعدی درباره الگوریتم های مرتب سازی (sort) و جستجو (search) هست.

فصل ۱۷ دایتل: نگاهی عمیق تر به Exception Handling

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

یادآوری

نکته اول اینکه همیشه باید سعی کنیم توی بلوک catch، تایپ مربوط به exception رو به صورت رفرنس بگیریم چراکه اولا از کپی شدن آبجکت اکسپشن جلوگیری میکنه و دوم اینکه باعث میشه اگر اکسپشن ما از stdexcept ارث بری شده، بتونه به درستی اجرا بشه.

یه بلاک try میتونه چندین بلاک catch رو بعد از خودش داشته باشه که هرکدوم یک استثنا خاصی رو هندل میکنن.

دو نوع مدل برای هندل کردن استثنا داریم:

termination model of exception handling

توی این مدل(که زبان سی++ از این مدل استفاده می‌کنه) وقتی داخل try یک اکسپشن پرت میشه(throw)، در همون نقطه از بلاک try بیرون میاد(اصطلاحا بهش میگن throw point) و بعد از پیدا کردن بلاک catch مورد نظرش میره و خطی که بعد از catch هست رو اجرا میکنه. نه خطی که بعد از throw point هست.

resumption model of exception handling

این مدل برعکس مدل بالاست و وقتی کار بلوک catch تموم میشه، برمیگرده و از ادامهٔ throw point یا همون نقطه پرتاب کد هارو اجرا می‌کنه.

با اینکه کلمهٔ throw میتونه هر چیزی رو پرت بکنه(مثل return) اما بهتره که فقط exception object رو پرت کنیم.

پرت کردن دوباره یک استثنا یا rethrowing exception

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

برای اینکه اینکار انجام بشه کافیه در بلوک catch ای که داریم یکبار دیگه throw کنیم تا به تابع صدا زننده بره. کد زیر کاملا شفافه و با خوندنش میتونیم بفهمیم دقیقا منظور از rethrowing exception چیه.

مثال برای پرت کردن دوبارهٔ یک استثنا

Stack unwinding

وقتی یک استثنا پرتاب میشه، برنامه به دنبال یک بلوک catch می‌گرده که متناسب با استثنا پرتاب شده باشه. اگر در جایی(تابعی) که قرار داره نتونه یک catch رو پیدا بکنه، اون تابع رو terminate می‌کنه و میره به جایی که تابع ما داخلش صدا زده شده. اگر اونجا هم بلوک catch ای وجود نداشت که متناسب با استثنا پرت شده بود، باز هم تابع رو terminate میکنه و میره به تابع صدا زننده‌ش و این کار تا موقعی که بتونه یک catch رو پیدا کنه ادامه داره.

اگر هیچ catch متناسبی پیدا نشه در نهایت برنامه بسته میشه.

به این فرآیند میگن stack unwinding چراکه function stack رو پیمایش می‌کنه و دونه دونه به سمت تابع بیرونی حرکت می‌کنه.

مثال زیر به روشن شدن ماجرا کمک می‌کنه:

کلمه noexcept

اگر تابعی داشته باشیم که به هیچ عنوان استثنا ای رو پرت نمی‌کنه یا توابعی رو صدا میزنه که اونها هم استثنا ای رو پرت نمی‌کنن، میتونیم صراحتا به عنوان تابعی که استثنا نداره تعریفش کنیم:

int functionWithoutException() noexcept;

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

نکته: اگر تابع ما const هست،‌ حتما کلمهٔ noexcept رو باید بعد از const بذاریم. نمیدونم چرا.

استثنا در Constructor و Destructor

یه سری نکات وجود داره که بهش می‌پردازیم:

  • از اشیاء ای که به صورت گلوبال تعریف شدن و اشیاء ای که به صورت static تعریف شدن نباید استثنا ای پرت بشه چرا که این اشیاء قبل از main ساخته میشن و نمیشه catch کردشون.
  • اگر یک شئ رو با استفاده از new ساخته باشیم و در کانستراکتورش یک استثنا رخ بده، اون حافظه ای که گرفته شده خود به خود آزاد میشه.
  • اگر کانستراکتور حافظه ای رو تخصیص داده، قبل از اینکه استثنا ای رو پرت بکنه باید حتما حافظه ای که گرفته رو پاک کنه!

استثنا ها در new

یکی از ویژگی های جالب سی++ که نظرمو جلب کرد، تابع set_new_handler (از هدر <new>)بود. این تابع یک تابع(بدون ورودی و خروجی void) رو به عنوان ورودی خودش میگیره و هر زمان و هرجای برنامه که موقع new کردن یک حافظه، مشکلی ایجاد بشه، اون تابع رو فراخوانی می‌کنه.

اگر تابع handler رجیستر نشده باشه،‌ در حالت پیشفرض new میاد و استثنا bad_alloc رو پرتاب می‌کنه.

کلاس unique_ptr

توضیحاتش زیاده ولی اگر مختصر بخوام بگم، یکی از اشاره گر های هوشمند سی++ هست که این نیاز رو که مجبوریم هر حافظه ای که گرفتیم رو به صورت دستی delete کنیم از بین می‌بره. خودش به صورت خودکار وقتی که out of scope بشه، حافظه رو برمیگردونه به سیستم.

یه مثال ازش میزنم: (کلاس Integer کار خاصی نمی‌کنه. فقط موقع نابود شدن یه متن چاپ میکنه و یه setter و getter داره)

تابع make_unique درواقع کار همون new رو انجام می‌ده و خط ۱۴ رو میشه به این شکل هم نوشت:

unique_ptr<Integer> ptrToInteger {new Integer(7)}

مالکیت در unique_ptr

هر اشاره گری فقط میتونه توسط یک شئ unique_ptr مدیریت بشه و این امکان که یک اشاره گر توسط چند شئ مدیریت بشن وجود نداره. درواقع وقتی یک شئ از این کلاس به یک شئ دیگه نسبت داده میشه(assign)، مالکیت اشاره گر از شئ سمت راست به شئ سمت چپ منتقل میشه.

این موضوع باعث میشه که بتونیم از unique_ptr برای پاس دادن آرگومان ها به تابع و یا برگردوندن اشاره گر از یک تابع استفاده بکنیم.

سلسله مراتب Exception های استاندارد

سلسله مراتب استثناهای استاندارد

با catch کردن کلاس والد، همه استثنا هایی که فرزند اون کلاس هستند هم catch می‌شن.

اگر می‌خوایم همهٔ انواع استثنا هارو catch بکنیم، میتونیم اینطوری بنویسیم:

catch (...) { // code here }

یکی از بدیای این روش اینه که دیگه نمی‌تونیم به جزئیات ارور دسترسی داشته باشیم. البته، اگر در سطوح پایین تر(توابعی که تابع موجود رو صدا زدند) catch ای وجود داشته باشه، میتونیم با rethrow کردن استثنا به جزئیات هم دسترسی داشته باشیم.

پایان

در فصل بعد درباره Template ها صحبت می‌کنیم. فصل باحالیه.

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

در این فصل قراره که یاد بگیریم چطور با استفاده از 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 و تابع لاندا. دیگه خود کد رو ننوشتم چون عکسش قشنگ تر درمیومد

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

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

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

[introducer](input arguments) {function  body}

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

توابع لاندا میتونن به متغییر های محلی(local) جایی که دارن داخلش تعریف میشن دسترسی داشته باشن. مثلا توی مثال بالا تابع های لاندای ما میتونن به متغییر هایی که داخل main تعریف شده دسترسی داشته باشن. اینجاست که lambda introducer به کار میاد. درواقع 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 های کلاس هست.

پایان

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

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

توی این فصل سه بخش از کتابخانه استاندارد سی++ که بهش 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 اون حافظه رو برای وکتور بگیریم تا از تخصیص و حذف پی در پی حافظه جلوگیری کنیم. C++11: shrink_to_fit

اینکه چطور یک وکتور اقدام به افزایش حافظه میکنه بستگی به پیاده سازی داره و ممکنه توی کامپایلر های مختلف، نتیجهٔ متفاوتی داشته باشه. در حالت کلی این یک 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 که قابلیت پیمایش برعکس روی یک آرایه رو میدن(از سی++ ۱۴ به بعد).

الگوریتم ها

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

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

نکات جدیدی که از فصل ۱۴ دایتل یادگرفتم – فایل ها

این فصل دربارهٔ پردازش فایل ها یا همون File Processing بود. بیشتر نکاتش رو از قبل می‌دونستم و صرفا برام مرور بود.

کلاس های مورد استفاده‌مون

برای انجام پردازش فایلی باید هدر های iostream و fstream رو اینکلود کنیم. توی fstream این سه تا typedef وجود داره:

  • typedef basic_ifstream<char> ifstream
  • typedef basic_ofstream<char> ofstream
  • typedef basic_fstream<char> fstream

همونطور که می‌بینید این سه تا typdef برای نوع دادهٔ char ویژه سازی شده(specialized).

توی این کلاس ها اپراتور bool هم overload شده. به این معنی که میتونیم معتبر(valid) بودن یک شئ رو به این شکل بررسی کنیم:

fstream myFile("something.txt", ios::out);
if (myFile) {
// do somthing
}

باز کردن فایل ها

برای باز کردن فایل ها چند حالت(mode) وجود داره که هرکدوم دارای ویژگی های خاصی هستن. نحوه‌ی نوشتنش و اینکه هرکدومشون چه کاری انجام می‌دن پایین تر نوشته شده:

ofstream handler("filename", ios::out)

حالت های مختلف موجود برای باز کردن فایل

نکتهٔ دیگه اینکه میتونیم این حالت هارو به صورت همزمان باهم دیگه استفاده بکنیم. چطوری؟ هرکدومشون رو با علامت «|» (bitwise or) از هم جدا می‌کنیم:

ofstream handler("filename", ios::in | ios::out | ios::binary)

پیمایش در فایل

میتونیم به سی++ بگیم که از کجای فایل میخوایم شروع کنیم به نوشتن/خوندن. وقتی یک فایل رو(هم برای خواندن و هم نوشتن) باز می‌کنیم، دو اشاره گر ایجاد میشه که به ابتدای فایل(بایت شماره صفر) اشاره می‌کنن. یکی از این اشاره گر ها برای خوندن از فایل و دیگری برای نوشتن در فایل هست. برای تغییر مکان اشاره گرِ خوندن، از تابع seekg و برای تغییر مکان اشاگر نوشتن از تابع seekp استفاده می‌کنیم.

// position to the nth byte of fileObject (assumes ios::beg)
fileObject.seekg(n);
// position n bytes in fileObject
fileObject.seekg(n, ios::cur);
// position n bytes back from end of fileObject
fileObject.seekg(n, ios::end);
// position at end of fileObject
fileObject.seekg(0, ios::end);

خوندن و نوشتن در فایل

من خوندن و نوشتن رو از قبل بلد بودم پس اینجا فقط چیز هایی رو می‌نویسم که به نظرم جالب تر بودن،‌ ممکنه یادم برن یا برام جدید بودن.

فرض کنیم یه فایلی داریم که متن های داخلش به این فرمت هستند:

100 "some text" 200

همونطور که میدونیم، input stream ها اسپیس رو به عنوان کلمه‌ی کلیدی برای جدا کردن آرگومان ها در نظر میگیرن. بنابراین اگر به شکل معمول زیر اقدام به خواندن خط بالا بکنیم، به مشکل برخواهیم خورد.

InputStream >> number1 >> text >> number2;

یکی از راه های موجود برای حل این مشکل، استفاده از یک stream manipulator به اسم quoted هست که در هدر <iomanip> قرار داره. حالا کدی که نوشتیم رو تغییر میدیم تا به درستی ورودی هارو از هم تشخیص بده.

نکته: این ابزار مختص رشته هایی هست که داخل دو double quotation قرار داره.

InputStream >> number1 >> quoted(text) >> number2;

خوندن و نوشتن به صورت Random-Access

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

در این روش که فایل رو در حالت باینری باز می‌کنیم، باید داده هامون رو به char * تبدیل کنیم.

اگر فرض بگیریم که int number{10};، برای نوشتن در فایل:

outFile.write(reinterpret_cast<const char*>(&number), sizeof(number));

و برای خوندن از فایل:

outFile.read(reinterpret_cast<char*>(&number), sizeof(number));

پارامتر اول تابع های read و write، داده ای هستن که میخوایم بنویسیم یا بخونیم و باید به صورت بایت به بایت خونده بشن. که برای اینکار، از char*استفاده می‌کنیم. پارامتر دوم همونطور که احتمالا فهمیدید، سایز داده ای هست که میخوایم بخونیم یا بنویسیم.

درباره انواع cast ها در سی++ احتمالا یه پست جدا می‌نویسم!

در آخر

برای صدمین بار رها کردن مطالعه، باز اومدم. اینبار هم مثل ۹۹ بار قبلی میگم که عزم بیشتری دارم 🙂

این فصل خیلی چیز جدیدی برام نداشت. فصل بعدی دربارهٔ کتابخانه استاندارد سی++‌ و container هاست.

چطور این ۲ هفته رو گذروندم

هوف! بالاخره پنل ادمین وبلاگمو باز کردم. بعد از آخرین پستم که تقریبا ۱۷ روز پیش بود حالا دوباره اومدم که فرآیند یادگیری‌ و مطالعه‌م رو شروع کنم. توی این تقریبا ۲ هفته کار زیادی نکردم. اولین برنامه‌ی اندرویدم رو نوشتم، چندتا فیلم دیدم و GTA V رو نصب کردم.

۵ تومن

داستان این برنامه برمیگرده به اونجا که شروع کردم در مقابل هرنوع کمکی که به دوستام میکردم، بهشون بگم ۵ تومن شد :))))

این داستان انقدر پیش رفت که تبدیل به تیکه کلام شد، یه سری واقعا این ۵ تومن هارو پرداخت کردن و دست آخر دیدم حسابشون داره از دستم در میره. خب چه چیزی بهتر از کامپیوتر برای نگهداری حسابا؟ ۵ تومن پول رایج مملکت مشوق من شد تا اولین برنامه‌ی خودم با کیوت بنویسم. و هیجان انگیز تر از اون؟ یه برنامه‌ی اندروید هم براش نوشتم! کیوت خیلی جالبه اما اگر تسلط کافی به خودِ سی++ و api های اندروید(یا هر بستر دیگه ای. مثلا iOS) ندارید و نقشه‌تون ایجاد یه برنامه‌ی مالتی پلتفرم نیست، بهتره که از زبان های native اون پلتفرم استفاده کنید.

این پروژه‌ی تمرینی چیز های جالب زیادی بهم یاد داد. مثلا اینکه ما داریم تو ایران زندگی می‌کنیم و واقعا بدبختیم. که ۲۵ دلار پول برای developer شدن توی گوگل پلی به پول ما خدا تومن میشه. که حتی همون خدا تومن رو هم نمیشه مثل آدم پرداخت کرد. بگذریم…

Cinema Paradiso

عجیبه که این فیلم رو انقدر دیر دیدم. درواقع پیش خودم فکر میکنم که چندتا فیلم/کتاب/موسیقی به این شکل زیبا توی جهان هست که من ازشون بی خبرم؟ و حتی تا آخر عمرم هم ازشون بهره ای نمیبرم. انگار واکنش من به لذت ها اینه. نوعی ناخوشی گُنگ حتی در خوشی هام هست.

GTA V

بازی GTA V توسط اپیک گیمز رایگان شد! البته، قبل از هرچیز باید بگم که لانچر اپیک گیمز یه آشغال به تمام معناست! نمیتونی دانلود/نصب برنامه رو متوقف کنی و بعدا ادامه بدی، انقدر تحریما رو سخت گرفته که حتما برای دانلودش هم باید فیلتر شکنت روشن باشه. د آخه مومن، پاچه خواری تا کجا؟ مگه فقط تو توی آمریکایی؟ میمیری مثل بقیه کمپانیا محدود کنی؟ بهرحال، لانچرش واقعا آشغاله.

و اما خود بازی. همون موقعی که تازه GTA V اومد همیشه دوست داشتم که روی سیستم خودم بازی کنمش. سیستم من ضعیف بود و هیچوقت نشد. کرک هاش درست کار نمیکردن و مشکلات دیگه. حتی روی پلتفرم های دیگه مثل کنسول هم شاید کلا ۲ بار بازی کردم.

اما بالاخره گرفتمش. و عجب بازی ایه! آهنگای خودم رو به بازی اضافه کردم و درحالی که داریوش داره میخونه مردم رو زیر میکنم.

در پایان

کلا اینکه این هفته هم مثل اکثر هفته های دیگه‌ی زندگیم آنچنان مفید نبود. اما حداقل لذت بخش بود. مفید نبود اما وقت تلف کردن هم نبود، چون وقتی که لذت بردی یعنی وقتت تلف نشده.

نکات جدیدی که از فصل ۱۲ سی++ دایتل یاد گرفتم – چندریختی

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

چند ریختی به ما اجازه میده که برنامه های گسترده ای بنویسیم و درواقع بتونیم برنامه نویسی general داشته باشیم بجای اینکه مجبور بشیم به صورت خاص برنامه بنویسیم(الآن براش مثالی توی ذهنم ندارم که کوتاه باشه).

کلمه‌ی virtual

معمولا وقتی از طریق یه پوینتر توابع رو فراخوانی می‌کنیم، توابع مربوط به [جنس اون] پوینتر صدا زده میشن نه توابع مربوط به کلاسی که بهش اشاره میشه. یعنی اگه تابعی با دو نسخه(یکی توی کلاس والد و یکی توی کلاس فرزند) وجود داشته باشه، اون نسخه ای صدا زده میشه که مربوط به type پوینتره. virtual به وجود اومده تا راه حلی برای این مشکل باشه، برای اینکه موقع صدا زدن یه تابع از طریق پوینتر/رفرنس، برنامه چک میکنه که اگر کلاس فرزند نسخه‌ی خودش از اون تابع رو داره، همون رو صدا بزنه در غیر این صورت نسخه‌ی مربوط به کلاس والد رو صدا می‌زنه.

درواقع توابع ویرچوال ابن امکان رو فراهم میکنن که بجای فراخوانی تابع مربوط به هندل، تابع مربوط به کلاس اشاره شده فراخوانی بشه.

بهتره که برای خوانایی بهتر توی هر سطح که توابع virtual والد رو بازنویسی می‌کنیم، قید کنیم که این یه تابع virtual عه.

Dynamic Binding

همونطور که بالاتر گفتیم اگر یکی از توابع به شکل virtual تعریف شده باشه، و این تابع از طریق یه پوینتر/رفرنس فراخوانی بشه، برنامه خودش تابع مناسب رو بر اساس جنسِ شئ ای که داره بهش اشاره میشه انتخاب میکنه. به این فرآیند میگن dynamic binding.

کلمه‌ی override

وقتی یه تابعی از کلاس والد رو توی کلاس فرزند بازنویسی می‌کنیم، بهتره که از کلمه‌ی override براش استفاده بکنیم، با استفاده کردن این کلمه، کامپایلر چک میکنه که آیا تابعی با امضا(signature) مشابه توی کلاس(های) والد وجود داره که بخواد بازنویسی بشه یا نه.

ضرورت virtual کردن destructor

مهمه که اگر میخوایم به صورت چند ریختی از کدمون استفاده بکنیم، حتما destructor رو به صورت virtual تعریف کنیم.

دلیلش اینه که اگر یک اشاره گر از نوع کلاس والد که داره به یک شئ از کلاس فرزند اشاره میکنه توسط کلمه‌ی delete پاک بشه، تابع نابودکننده مربوط به خودش صدا زده بشه و نه تابع نابودکننده والد.

کلمه‌ی default

چیز جدیدی که به سی++ ۱۱ اضافه شده کلمه‌ی default هست. وقتی میخوایم یه کانستراکتور و یا دیستراکتور پیش فرض داشته باشیم دیگه نیاز نیست که یه تابع با بدنه‌ی خالی بنویسیم. فقط کافیه توی اعلان، اون تابع رو default کنیم.

کلمه‌ی final

وقتی از کلمه‌ی final برای یه تابع استفاده میشه، دیگه کامپایلر اجازه نمیده که اون تابع توی کلاس های فرزند بازنویسی و override بشه.

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

کلاس Abstract

تا اینجا ما میتونستیم از کلاس هامون اشیاء ای رو بسازیم. اما یه سری کلاس های دیگه هم وجود دارن که نمیشه ازشون هیچ شئ ای ساخت که به این کلاس ها میگن Abstract. به کلاس های معمولی میگن concrete.

کلاسی رو میشه ابسترکت نامید که حداقل یکی از توابع virtual اش به صورت pure باشه.

برای اینکه یک تابع رو pure کنیم، باید اعلان تابع رو برابر 0 قرار بدیم که اون 0 نشان pure specifier هست. با pure اعلام کردن یک تابع دیگه نباید براش پیاده سازی ای نوشت بنابراین همه‌ی کلاس های فرزند باید توابع pure رو پیاده سازی کنن وگرنه خودشونم ابسترکت میشن.

چندریختی به صورت عمیق تر!

یه رفتار پلی مورفیک از سه سطح از پوینتر ها تشکیل شده.

مرحله اول، vtable

وقتی کاپایلر کلاسی رو که دارای توابع virtual عه رو کامپایل میکنه، برای اون کلاس یدونه Virtual function Table (vtable) میسازه. کار این جدول چیه؟ آدرس توابع virtual شده‌ی اون کلاس رو داخل خودش ذخیره می‌کنه. وقتی در زمان اجرا میخوایم با استفاده از dynamic binding یه تابع virtual رو فراخوانی کنیم، برنامه توی vtable کلاس مربوطه میگرده تا تابع درست رو پیدا و اجرا بکنه.

مرحله دوم

وقتی یه آبجکت از یک کلاس دارای توابع ویرچوال ساخته میشه، کامپایلر به اون آبجکت یه پوینتر اختصاص میده(این پوینتر رو معمولا در اول آبجکت میذاره) که اون پوینتر به vtable مربوط به اون کلاس اشاره می‌کنه.

مرحله سوم

پوینتریه که به خودِ شئ اشاره می‌کنه. به عنوان مثال ما یک وکتور از همه اشیاء از کلاس های مشتق شده از کلاس A داریم. پوینتر هایی که توی این وکتور هستند(که به اشیاء اشاره می‌کنن) به عنوان سطح سوم پوینتر ها محسوب میشن.

بنابراین برای اجرای یه تابع ویرچوال که به صورت dynamic binding میخواد صدا زده بشه، حداقل ۳ بار pointer dereferencing اتفاق میوفته که این موجب افزایش زمان اجرایی میشه. همچنین ذخیره کردن پوینتر مرحله ۲ و خودِ vtable هم باعث استفاده بیشتر از مموری میشه. اگر پرفورمنس و سرعت توی برنامه ای که داریم می‌نویسیم یک اصل بسیار مهم و سفت و سخته،‌ بهتره که از پلی مورفیسم استفاده نکنیم.

RunTime Type Information

تا اینجا وقتی به صورت پلی‌مورفیسم کار می‌کردیم، نیاز نبود بدونیم هر آبجکت دقیقا از چه نوعیه. اما ممکنه گاهی این نیاز رو پیدا بکنیم. با استفاده از قابلیت RTTI یا همون RunTime Type Information و قابلیت dynamic cast میتونیم در زمان اجرا بفهمیم که شئ ما از چه نوعیه و رفتار متناسب با خودش رو باهاش انجام بدیم. با استفاده از dymanic_cast میتونیم یه اشاره گر از جنس کلاس والد رو که داره به یکی از کلاس های فرزند اشاره می‌کنه به یک اشاره گر از نوع خودِ کلاس فرزند تغییر بدیم. فرقش با static_cast اینه که تایپ چک انجام میده و اگر کلاسی که داره بهش اشاره میشه از نوع کلاسی نباشه که میخواد بهش cast بشه، تبدیل انجام نمیشه.

همچنین با استفاده از typeid میتونیم در زمان اجرا بفهمیم که یه شئ از چه نوعیه. با استفاده از متود name اش میتونیم اسم جنسِ یه شئ رو به صورت یه رشته بگیریم.

در پایان

فصل بعدی توی I/O بیشتر عمیق میشیم.

یادگیری امروزم از معماری کامپیوتر(۴)

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

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

پًست امروز درباره‌ی Pipeline Processing عه و احتمالا پست بعدی هم درباره همین مورد باشه.

پردازش خط لوله‌ای(pipeline processing) یه تکنیکه که طی اون زیرعمل ها(sub operation) و یا بخش های مختلف از یک سیکل دستور، با همدیگه همپوشانی(overlap) پیدا میکنن.

این روش برای انجام کارها با تکرار زیاد بسیار مناسبه و نیازمند این هست که CPU چند فانکشنال یونیت مجزا داشته باشه که به صورت موازی کار انجام بدن.

دو بحش هست که پایپلاین داخلشون استفاده میشه یکیش arithmetic pipeline (عملیات های مختلف ریاضی رو به سگمنت های جدا تبدیل میکنه) و اون یکی هم instruction pipeline (بخش های مختلف مثل fetch و decode و execution رو به سگمنت های مختلف تبدیل میکنه)

معمولا بعد از هر سگمنت یک pipeline register وجود داره که نتیجه‌ی حاصل شده از کار سگمنت قبل از خودش ذخیره می‌کنه و در اختیار سگمنت بعدی میذاره.(درواقع بین دو سگمنت A و B یک رجیستر وجود داره که به عنوان خروجی A و ورودی B میتونه محسوب بشه)

Arithmetic Pipeline

معمولا این پایپلاین برای انجام عملیات ها روی اعداد اعشاری و ضرب برای اعداد غیر اعشاری انجام میشه. توضیحاتش به نظرم بدیهی اومد بنابراین نمی‌نویسمش.

Instruction Pipeline

همون طور که عمل پایپلاینینگ میتونه روی data stream ها انجام بشه، میتونه روی instruction stream هم انجام بشه. همونطور که میدونیم اجرای یه دستور از چند بخش تشکیل شده:

  • fetch
  • decode
  • محاسبه effective address
  • دریافت operand ها(fetch operand)
  • اجرا(execute)
  • write back

ما برای بررسی راحت تر چندتا از این بخش هارو باهم یکی می‌کنیم و فرض می‌کنیم مراحل اجرای یک دستور صرفا شامل مراحل زیر هست:

  • fetch (FI)
  • decode (DA)
  • fetch operand (FO)
  • execute (EX)

مثال ما ۴ استیج(سگمنت) هست اما توی کامپیوتر های دیگه تعداد استیج ها متفاوته(مثلا توی پنتیوم ۴ اینتل حدود ۳۰ تا استیج داریم).

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

جدول زمانی یک instruction pipeline

مشکلات instruction pipeline

  • resource conflict ها
  • Data dependency ها
  • Branch difficulty ها

Resource Conflict

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

Data Dependency

مشکل data dependency و address dependency که باعث کاهش پرفورمنس هم میشن، وقتی به وجود میان که یک سگمنت به یک داده و یا آدرسی نیاز داشته باشه که هنوز در دسترسش نیست. مثال: مثلا دستور A یک داده ای رو به عنوان خروجی تولید میکنه که این داده قراره به عنوان operand توی دستور B استفاده بشه. این دوتا دستور متوالی هستند، حالا قسمت Fetch operand(که میخواد اوپرند های دستور B رو لود کنه) تا زمانی که بخش Execute (که داره دستور A رو اجرا می‌کنه) تموم نشه نمیتونه داده های مورد نیاز خودش رو بدست بیاره. پس باید صبر کنه تا اجرای دستور قبلی به اتمام برسه تا کارش رو انجام بده. همین اتفاق برای آدرس ها هم میوفته. یعنی یک سگمنت به آدرسی نیاز داره که هنوز دستور قبلی تولیدش نکرده.

برای حل این مشکل معمولا سه تا راه وجود داره:

Hardware interlock

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

Operand forwarding

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

Delayed load

توی این روش، حل این مشکل رو به عهده‌ی کامپایلری میذاریم که داره زبان سطح بالا رو به زبان سطح پایین تبدیل میکنه. درواقع کامپایلر وقتی data conflict رو میبینه، سعی میکنه با تغییر دادن ترتیب دستور ها(مثلا با اضافه کردن nop) به قدر کافی برای اجرا شدن دستور قبلی زمان ایجاد بکنه.

Branch difficulty

این مشکل درواقع یک چالش برای مدیریت کردن branch های رخ داده توی برنامه‌ست. همونطور که میدونیم branch ها جریان عادی دستورات برنامه رو میشکنن. چالش اینه که چطور conditional branch و unconditional branch رو مدیریت کنیم که کمترین ضرر رو به پرفورمنس بزنیم.

Prefetch target instruction

این یکی از راه حل های موجود برای مدیریت کردن conditional branch هاست. نحوه‌ی کارش اینطوریه که هردوحالت (اجرا شدن branch و اجرا نشدنش) رو درنظر میگیره. یعنی چی؟ یعنی شروع میکنه دستوراتی که در صورت وقوع branch قراره اجرا بشن و به صورت همزمان دستوراتی که در صورت انجام نشدن branch قراره اجرا بشن رو fetch می‌کنه. اگر شرط مربوط به branch درست بود، میره و دستورات branch رو(که قبلا fetch کرده) اجرا میکنه. در غیر این صورت دستورات مربوط به جریان عادی برنامه رو اجرا می‌کنه.

Branch Target Buffer(BTB)

BTB یه حافظه کوچیکه که توی استیج fetch قرار می‌گیره.کارش اینه که آدرس چند branch اجرا شده‌ی اخیر + آدرس target اونها + چندتا از instruction های بعد از target رو داخل خودش ذخیره میکنه. وقتی دستور توی پایپلاین رمزگشایی دیکد میشه، توی BTB میگرده که آیا آدرس این دستور(که یه branch هست) توی BTB وجود داره یا نه. اگه وجود داشته باشه، اون دستور و متعلقاتش(مثل آدرس تارگت و چندتا دستور اولِ اون branch) مستقیما در دسترس هستند و دستورات از مسیر جدید به سرعت fetch میشن. اگه آدرس جستجو شده توی BTB وجود نداشته باشه، این دستور به علاوه‌ی متعلقاتش توی BTB ذخیره میشن و پایپلاین خالی میشه تا مسیر جدید دستور ها توی پایپلاین قرار بگیره.

Loop buffer

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

دستورات داخل حلقه تا پایان اجرای حلقه داخل این بافر میمونن.

Branch Prediction

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

branch prediction درواقع فرآیندیه که طی اون پایپلاین سعی میکنه قبل از اجرا شدن یه conditional branch حدس بزنه که آیا شرط (condition) صدق خواهد کرد یا نه. در صورتی که پیشبینی کنه این شرط درست خواهد شد، شروع میکنه دستوراتِ داخل branch رو fetch میکنه. اگر پیشبینی درست باشه،‌ دیگه وقفه ای در کار پایپلاین رخ نمی‌ده.

در آخر

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