کتابخانه استاندارد قالب (به انگلیسی: Standard Template Library) (مخفف: STL) یک کتابخانه نرمافزاری برای زبان برنامهنویسی ++C است که بسیاری از قسمتهای کتابخانه استاندارد ++C را تحت تأثیر قرار داده است.
زبان انگلیسی
زبان کوردی سورانی
زبان ترکی استانبول
کتابخانه استاندارد چهار جزء دارد:
STL مجموعه ای از کلاسهای متداول را برای ++C مانند کانتینرها و آرایههای انجمنی ارائه میدهد که میتواند با هر نوع داخلی و با هر نوع تعریف شده توسط کاربر که از برخی عملیاتهای ابتدایی پشتیبانی میکند (مانند کپی و انتساب) استفاده شود. الگوریتمهای STL مستقل از کانتینرها نیستند، که بهطور قابل توجهی از پیچیدگی کتابخانه میکاهد.
STL با استفاده از الگوها به نتایج خود میرسد. این رویکرد چندشکلی compile-time را ارائه میدهد که اغلب کارآمدتر از چند شکلی سنتی run-time است. کامپایلرهای مدرن ++C تنظیم شدهاند تا خطاها را با استفاده از STL را به حداقل برسانند.
STL به عنوان اولین کتابخانه الگوریتمهای عمومی و ساختارهای داده برای ++C با چهار ایده در ذهن ایجاد شده است: برنامهنویسی همگانی ، انتزاع بدون از دست دادن کارایی، معماری فون نویمان و Value semantics.
تاریخچه
تاریخچه کامل: History of the Standard Template Library
در نوامبر ۱۹۹۳ الکساندر استپانوف کتابخانه ای را براساس برنامهنویسی همگانی به کمیته ANSI / ISO برای استانداردسازی ++C ارائه داد. و با پاسخ مثبت کمیته رو به رو شد و منجر به درخواست آندرو کونیگ برای پیشنهاد رسمی در جلسه مارس ۱۹۹۴ شد. کمیته چندین درخواست تغییر و الحاق داشت و اعضای کمیته با استپانوف و منگ لی ملاقات کردند تا به جزئیات کمک کنند. الزامات مهمترین الحاقات (کانتینرهای انجمنی) باید با اجرای کامل آنها سازگار باشد، وظیفه ای که استپانوف به دیوید موسر محول کرد. پیشنهادی در جلسه کمیته ANSI / ISO در ژوئیه ۱۹۹۴ تصویب نهایی شد. متعاقباً، سند ۱۷ استپانوف و لی در پیش نویس استاندارد ANSI / ISO C ++ گنجانیده شد (۱، بخشهایی از بندهای ۱۷ تا ۲۷).
چشمانداز انتشار گسترده STL با تصمیم Hewlett-Packard برای در دسترس قرار دادن اجرای آن در اینترنت در ماه اوت ۱۹۹۴ بهطور قابل توجهی بهبود یافت.
اجزاء
کانتینرها
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
|
این نوع کانتینر یک کانتینر وابسته ساده است که از ۲ عنصر داده یا اشیا، تشکیل شده است و در مرتبسازی به ترتیب "اول" و "دوم" نامیده میشود.
|
متوالی (آرایه ها/لیستهای پیوندی)
|
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 را میتوان روی کانتینرها استفاده کرد.
تعداد زیادی الگوریتم برای انجام فعالیتهایی از قبیل جستجو و مرتبسازی در STL ارائه شده است که هرکدام برای نیاز به سطح مشخصی از تکرار کننده پیادهسازی شدهاند (و بنابراین بر روی هر کانتینر که از طریق تکرار کنندهها رابطی را فراهم میکند کار خواهند کرد).
Functions
شمول شدن کتابخانه الگوریتم توابعی را به همراه دارد که در ترتیب دهی و جستجو در آرایهها بسیار مفید است.[۱]الگوریتمها در ظروف نقش بسیار مفیدی دارند.[۳]
منابع