کتابخانه استاندارد قالب

کتابخانه استاندارد قالب (به انگلیسی: Standard Template Library) (مخفف: STL) یک کتابخانه نرم افزاری برای زبان برنامه نویسی ++C است که بسیاری از قسمت های کتابخانه استاندارد ++C را تحت تأثیر قرار داده است.

کتابخانه استاندارد چهار جزء دارد:

algorithms
containers
functions
iterators

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

STL با استفاده از الگوها به نتایج خود می رسد. این رویکرد چندشکلی compile-time را ارائه می دهد که اغلب کارآمدتر از چند شکلی سنتی run-time است. کامپایلرهای مدرن ++C تنظیم شده اند تا خطا ها را با استفاده از STL را به حداقل برسانند.

STL به عنوان اولین کتابخانه الگوریتمهای عمومی و ساختارهای داده برای ++C با چهار ایده در ذهن ایجاد شده است: برنامه‌نویسی همگانی ، انتزاع بدون از دست دادن کارایی ، معماری فون نویمان و Value semantics.

تاریخچه

تاریخچه کامل : History of the Standard Template Library

در نوامبر 1993 الكساندر استپانوف كتابخانه ای را براساس برنامه نویسی همگانی به كمیته ANSI / ISO برای استانداردسازی ++C ارائه داد. و با پاسخ مثبت کمیته رو به رو شد و منجر به درخواست آندرو کونیگ برای پیشنهاد رسمی در جلسه مارس 1994 شد.کمیته چندین درخواست تغییر و الحاق داشت و اعضای کمیته با استپانوف و منگ لی ملاقات کردند تا به جزئیات کمک کنند.الزامات مهمترین الحاقات (کانتینرهای انجمنی) باید با اجرای کامل آنها سازگار باشد ، وظیفه ای که استپانوف به دیوید موسر محول کرد.پیشنهادی در جلسه کمیته ANSI / ISO در ژوئیه 1994 تصویب نهایی شد.متعاقباً ، سند 17 استپانوف و لی در پیش نویس استاندارد ANSI / ISO C ++ گنجانیده شد (1 ، بخشهایی از بندهای 17 تا 27).

چشم انداز انتشار گسترده STL با تصمیم Hewlett-Packard برای در دسترس قرار دادن اجرای آن در اینترنت در ماه آگوست 1994 به طور قابل توجهی بهبود یافت.

اجزاء

Containers

STL شامل کانتینر های ترتیبی (sequence containers) و وابسته (associative containers) می شود. کانتینرها اشیایی هستند که داده ها را ذخیره می کنند.

کانتینر های ترتیبی (sequence containers) شامل موارد زیر می شوند :

vector
deque
list

و کانتینر های وابسته (associative containers) شامل موارد زیر می شوند :

set
multiset
map
multimap
hash_set
hash_map
hash_multiset
hash_multimap

همچنین کانتینر های ، prior_queue و stack وجود دارند که کانتینرهایی با interface های خاص هستند و از کانتینر های دیگر به عنوان پیاده سازی استفاده می کنند.

کانتینر ها	توضیحات
کانتینر های ساده
pair	این نوع کانتینر یک کانتینر وابسته ساده است که از 2 عنصر داده یا اشیا، تشکیل شده است و در مرتب سازی به ترتیب "اول" و "دوم" نامیده می شود.
متوالی (آرایه ها/لیست های پیوندی)
vector	یک آرایه پویا ، مانند آرایه C (یعنی امکان دسترسی تصادفی) با قابلیت تغییر اندازه خودکار هنگام قرار دادن یا پاک کردن یک شی. قرار دادن یک عنصر در انتهای vector انتها زمان ثابتی را در بر می گیرد. حذف آخرین عنصر فقط به زمان ثابت نیاز دارد ، زیرا تغییر سایز اتفاق نمی افتد. قرار دادن و پاک کردن در ابتدا یا وسط به صورت خطی است. یک نوع ویژه برای نوع bool وجود دارد که با ذخیره مقادیر آن به صورت بیت ، فضای را بهینه می کند.
list	یک لیست پیوندی دوگانه که عناصر را در به صورت پشت سرهم ذخیره نمی کند. که آن را با vector ها متمایز می کند.در list ها جستجوی و دسترسی به صورت آهسته (زمان خطی) خواهد بود ، اما هنگامی که موقعیتی پیدا شد ، درج و حذف سریع (زمان ثابت) است.
slist	یک لیست پیوندی که عناصر را در به صورت پشت سرهم ذخیره نمی کند. که آن را با vector ها متمایز می کند.در list ها جستجوی و دسترسی به صورت آهسته (زمان خطی) خواهد بود ، اما هنگامی که موقعیتی پیدا شد ، درج و حذف سریع (زمان ثابت) است. کمی درج و حذف کارآمدتر است و از حافظه کمتری نسبت به لیست پیوندی دوگانه استفاده می کند ، اما فقط می تواند به سمت جلو حرکت کندو در کتابخانه استاندارد ++C به عنوان forward_list اجرا می شود.
deque *( صف دو طرف بسته)*	یک آرایه پویا (vector) با قابلیت اضافه/حذف کردن از ابتدا و یا انتها در زمان Constant Amortized ( میانگین همه عملیات ها زمان ثابتی می گیره و زمان اجرا ربطی به سایز ورودی نداره.) وجود دارد، هرچند که پس از تغییر تضمین هایی در مورد اعتبار تکرار کننده ها ندارد.
Container adaptors
queue	صف با استفاده از روش FIFO عملیات های `push`/`pop`/`front`/`back`را فراهم می کند. از هر کانیتنیر های ترتیبی که `()front() ,back() ,push_back(), pop_front` می توان به عنوان صف درنظر گرفت.(همانند : list و deque)
priority queue	این نوغ صفی اولویت دار نسبت به `push`/`pop`/`top` را فراهم می کند. (عنصری که بالاترین اولویت را دارد در بالا است) از هر کانتینر های ترتیبی با دسترسی تصادفی که از عملیات های `()front() ,push_back() pop_fron` پشتیبانی می کند ، می تواند نمونه ای از صف های اولویت دار (به عنوان مثال vector و deque) استفاده شود. با استفاده از پشته اجرا می شود.
stack	پشته با استفاده از روش LIFO عملیات های `push / pop / top` فراهم می کند (آخرین عنصر وارد شده در بالا است). از هر کانتینر های ترتیبی که از عملیات های `()back() ,push_back() pop_back` پشتیبانی می کند ، می تواند نمونه ای از پشته (به عنوان مثال list , vector و deque) استفاده شود.
کانتینرهای وابسته: مجموعه های غیر مرتب
set	یک مجموعه ریاضی که درج / پاک کردن عناصر در یک مجموعه تکرارهای اشاره شده در مجموعه را باطل نمی کند. ایجاد یک مجموعه ی عملیاتی متحد
multiset	همانند یک مجموعه (set) ، اما اجازه عناصر تکراری (چند مجموعه ریاضی) را نیز می دهد.
map	یک آرایه وابسته که اجازه می دهد تا از یک مورد داده (یک کلید) به دیگری (یک مقدار) نقشه برداری شود. نوع کلید باید عملگر مقایسه را اجرا کند <یا عملکرد مقایسه کننده سفارشی باید مشخص شود. چنین عملکرد اپراتور مقایسه یا مقایسه کننده باید نظم ضعیف را تضمین کند ، در غیر این صورت رفتار تعریف نشده است. به طور معمول با استفاده از یک درخت جستجوی دودویی متعادل کننده اجرا می شود.
multimap	همانند map ، اما اجازه چند کلید را نیز دارد.
hash_set hash_multiset hash_map hash_multimap	به ترتیب مشابه یک multimap , map، multiset ،set اما با استفاده از جدول هش پیاده سازی شده است. کلیدها ترتیب نمی شوند ، اما یک تابع هش باید برای نوع کلید وجود داشته باشد. این نوع از استاندارد C ++ خارج شدند. کانتیر مشابه در C ++ 11 استاندارد شدند ، اما با نام های مختلف (unordered_set و unordered_map).
نوع های دیگر کانتینر ها
bitset	مجموعه ای از بیت ها را مشابه بردارهای bool با اندازه ثابت ذخیره می کند. عملیات بیتی را اجرا می کند و فاقد تکرار کننده است. دنباله ای نیست. دسترسی تصادفی را فراهم می کند.
valarray	نوع داده دیگری از آرایه ، که برای استفاده عددی (به ویژه برای نشان دادن بردارها و ماتریس ها) در نظر گرفته شده است. استاندارد C ++ بهینه سازی های خاصی را برای این منظور در نظر گرفته است. طبق گفته Josuttis ، والارای توسط افرادی "كه مدتها قبل از اتمام استاندارد از كمیته [C ++ standard] خارج شدند" بد طراحی شده است ، و كتابخانه های قالب بیان ترجیح داده می شوند. بازنویسی پیشنهادی بخش vlarray از استاندارد در این رد رد شد ، در عوض به مجوزی برای پیاده سازی آن با استفاده از الگوی بیان تبدیل شد.

Iterators

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

input iterators (که فقط برای خواندن مقادیر به صورت ترتیبی قابل استفاده هستند)،

output iterators (که فقط برای نوشتن مقادیر به صورت ترتیبی قابل استفاده هستند)،

forward iterators (که قابل خواندن ، نوشتن و حرکت به جلو است)،

bidirectional iterators (مانند forward iterators هستند ، اما همچنین می توانند به عقب حرکت کنند) و

random access iterators (که می توانند با تعداد آزادانه هر مرحله را در یک عملیات حرکت دهند)

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

bidirectional iterators ممکن است مانند random access iterators عمل کنند ، بنابراین حرکت به جلو در ده مرحله می تواند با حرکت به جلو در یک مرحله و در کل ده بار انجام شود. با این وجود ، random access iterators مجزا مزایای کارایی را به همراه دارد. به عنوان مثال ، یک بردار یک random access iterators دارد ، اما یک لیست فقط یک bidirectional iterators دارد.

تکرار کننده ها ویژگی اصلی هستند که به کلیات STL اجازه می دهند. به عنوان مثال ، یک الگوریتم برای معکوس سازی یک توالی می تواند با استفاده از bidirectional iterators پیاده سازی شود ، و سپس همان پیاده سازی را می توان در لیست ها ، vectors و deques استفاده کرد. کانتینرهای ایجاد شده توسط کاربر فقط باید یک تکرار کننده ارائه دهند که یکی از پنج رابط استاندارد تکرار کننده را پیاده سازی کند و تمام الگوریتم های ارائه شده در STL را می توان روی کانتینر ها استفاده کرد.

Algorithms

تعداد زیادی الگوریتم برای انجام فعالیتهایی از قبیل جستجو و مرتب سازی در STL ارائه شده است که هرکدام برای نیاز به سطح مشخصی از تکرار کننده پیاده سازی شده اند (و بنابراین بر روی هر کانتینر که از طریق تکرار کننده ها رابطی را فراهم می کند کار خواهند کرد).

Functions

شمول شدن کتابخانه الگوریتم توابعی را به همراه دارد که در ترتیب دهی و جستجو در آرایه‌ها بسیار مفید است.الگوریتم‌ها در ظروف نقش بسیار مفیدی دارند.

منابع

↑ «The C++ Standard Template Library (STL)». GeeksforGeeks (به انگلیسی). ۲۰۱۵-۱۲-۰۷. دریافت‌شده در ۲۰۲۰-۰۸-۰۳.
↑ Ryu, Gukbeen; Kim, Gyu-Tae; Song, Kwang Yong; Bae Lee, Sang; Lee, Kwanil (2018-07). "Long Range One-End Accessible BOCDA Adopting Time Domain Data Processing". 2018 23rd Opto-Electronics and Communications Conference (OECC). IEEE. doi:10.1109/oecc.2018.8729903. ISBN 978-1-5386-9145-8.
↑ «Containers - C++ Reference». www.cplusplus.com. دریافت‌شده در ۲۰۲۰-۰۸-۰۳.

[:0-1] «The C++ Standard Template Library (STL)». GeeksforGeeks (به انگلیسی). ۲۰۱۵-۱۲-۰۷. دریافت‌شده در ۲۰۲۰-۰۸-۰۳.

[2] Ryu, Gukbeen; Kim, Gyu-Tae; Song, Kwang Yong; Bae Lee, Sang; Lee, Kwanil (2018-07). "Long Range One-End Accessible BOCDA Adopting Time Domain Data Processing". 2018 23rd Opto-Electronics and Communications Conference (OECC). IEEE. doi:10.1109/oecc.2018.8729903. ISBN 978-1-5386-9145-8.

[:1-3] «Containers - C++ Reference». www.cplusplus.com. دریافت‌شده در ۲۰۲۰-۰۸-۰۳.