ספריית התבניות התקנית

ספריית התבניות התקנית (באנגלית: Standard Template Library או בקיצור: STL) היא חלק מהספרייה התקנית של C++‎. ספרייה זו אינה חלק מובנה בשפה, והיא מכילה כלי עזר שניתן לכתוב בשפת C++‎ עצמה; הספרייה חוסכת מהמתכנת את הטרחה שבכתיבתם. כל שירותי STL הם תבניות שתואמות את עקרונות התכנות הגנרי, ומכאן שם הספרייה.

היסטוריה

את יצירת ה-STL אפשר לזקוף בעיקר לאלכסנדר סטפנוב שב-1979 החל לעבוד על הרעיון של אלגוריתמים גנריים. ב-1987 כתבו סטפנוב ושותפו דוד מוסר קודים גנריים לשפת עדה. הם שמו לב שעדה יוצאת לאט לאט מהשוק והחליטו לכתוב ספריות גנריות עבור ++C.

סטפנוב החל לעבוד במעבדות AT&T ולאחר מכן במעבדות HP על אלגוריתמים גנריים ל-++C. לאחר זמן מה הציג סטפנוב את מחקרו בפני איגוד התקינה של שפת ++C. האיגוד התלהב מהמחקר וביקש מסטפנוב שימשיך לעבוד ויראה להם את התקדמותו. לאחר עבודה רבה על הקוד הם הציגו גרסה סופית שאושרה ביולי 1994. עוד החלטה שתרמה להתפשטות של ה-STL היא ההחלטה של HP לא לקחת תמלוגים על הקוד ולהפיץ אותו בחינם.

שירותי הספרייה

כל שירותי STL מובאים בצורת תבניות של מחלקות או פונקציות הנמצאות תחת מרחב שם של הספרייה התקנית: std. הספרייה מגדירה מחלקות עבור מבני נתונים נפוצים (כגון ווקטור, עץ חיפוש בינארי, רשימה מקושרת, תור, מחסנית), טיפוסי איטרטורים עבור מחלקות אלה (מצביעים מופשטים) ואלגוריתמים נפוצים (אלגוריתמי חיפוש, מיון, פעולות על קבוצות וכדומה).

מבני נתונים

STL מכילה תבניות של מחלקות שמממשות מבני נתונים נפוצים. טיפוס הנתונים שיכיל כל מבנה נתונים מוגדר בפרמטר הראשון של התבנית (או השני עבור מחלקות map), משמע הדבר שלא ניתן לערבב אובייקטים מטיפוסים שונים בתוך מבנה נתונים אחד. על מנת ליצור מבנה נתונים הטרוגני יש לשמור מצביעים למחלקת אם משותפת.

מבני הנתונים המובאים ב-STL מתחלקים לשני סוגים:

רצפים – במבני נתונים אלה האובייקטים מסודרים לפי סדר שיש לו משמעות.
אוספים אסוציאטיביים – במבני נתונים אלה האובייקטים מסודרים בתוך עץ חיפוש מאוזן או בתוך טבלת גיבוב ועל כן אין משמעות לסדרם.

כמו כן, חלק ממבני הנתונים מבוססים על מבני נתונים בסיסיים אחרים. מבני נתונים אלה נקראים אדפטורים (adaptors). למשל תור חד-כיווני הוא גרסה מוגבלת של תור דו-כיווני.

כל מבני הנתונים הבסיסיים המוגדרים ב-STL מגדירים ממשק דומה. דבר זה מאפשר לכתוב אלגוריתמים גנריים שיעבדו עם כל מבני הנתונים התומכים בפעולות אלה או אחרות. כמו כן הממשק הדומה מאפשר למתכנת לכתוב מחלקות עבור מבני נתונים משלו שישתלבו יחד עם כל שאר כלי הספרייה. דבר זה הופך את STL לספרייה הניתנת להרחבה, לדוגמה ספריית boost היא הרחבה ל-STL.

להלן טבלה המסכמת את מבני הנתונים הקיימים:

שם המחלקה	הסבר
רצפים (סדרות)
vector	מערך בטוח חד-ממדי. לעומת המערך המובנה שבשפה הוא שומר את גודלו ואחראי על הקצאת הזיכרון ופינויו. מחלקה זו מכילה שיטות לשינוי גודל המערך, כמו כן היא עשויה לפעולות מחסנית (הוספה ומחיקה מהסוף). מחלקה זו מאפשרת להקצות יותר מקום עבור השימוש העתידי על מנת לחסוך העתקות.
list	רשימה מקושרת דו-כיוונית. פעולות ההוספה והמחיקה מכל קצה של הרשימה או נקודה המוצבעת על ידי איטרטור תתבצענה תוך זמן קבוע. אין אפשרות פנייה לפי אינדקס. מציאת איבר לפי אינדקס באמצעות ספרייה יתבצע תוך זמן ${\mathcal {O}}\left(n\right)$ .
deque	דו-תור. ניתן להכניס לתור ולהוציא ממנו משני הקצוות תוך זמן קבוע. פעולות עם אמצע התור (הוצאה והכנסה למרכז) תתבצענה תוך ${\mathcal {O}}\left(n\right)$ . מאפשרת מיעון תוך זמן קבוע.
אדפטורים (adaptors)
queue	תור חד-כיווני. מבוסס כברירת מחדל על deque. ממשקו מאפשר אך ורק עבודה עם קצוות.
priority_queue	תור עדיפויות. ממומש על ידי ערימה (heap) שנשמרת בתוך vector, כברירת מחדל. הממשק זהה לזה של queue מלבד שתבנית מחלקה זו כוללת פרמטר נוסף, והוא פונקציית ההשוואה בין הערכים שתגדיר את העדיפויות.
stack	מחסנית. מבוססת על deque כברירת מחדל. פעולות הממשק כוללות אך ורק את ממשק המחסנית.
אוספים אסוציאטיביים
map	מילון הממומש על ידי עץ-חיפוש מאוזן שכל צומת בו שומר מפתח וערך.
set	מימוש של קבוצה כעץ חיפוש בינארי מאוזן ששומר רק את המפתחות.
multimap multiset	רב-קבוצה - זהה ל-map ול-set בהתאמה מלבד שיכולים להיות מספר הופעות של מפתחות שקולים.
unordered_map unordered_set unordered_multimap unordered_multiset	זהים בתפקידם ל-map, set, multimap ו-multiset בהתאמה. מחלקות אלה משתמשות בטבלת גיבוב ולכן זמן חיפוש, הוספה ומחיקה הוא בקירוב קבוע. כאשר טבלת הגיבוב מתמלאת, מחלקות אלה מגדילים אותה אוטומטית.
אחרים
bitset	דומה למערך של ערכים בינאריים, אך יעיל יותר לצורך זה.
valarray	דומה למערך של ערכים מספריים, אך יעיל יותר לצורך זה.
string	דומה למערך של תווים, ובעל פעולות מיוחדות למחרוזות.

איטרטורים

איטרטור (iterator) הוא מצביע מופשט. בניגוד למצביע רגיל שהוא טיפוס מובנה אשר מכיל כתובת בזיכרון, מימושו של איטרטור לא מוגדר. האיטרטורים עשויים לעבודה עם רצפים של אובייקטים הנמצאים בתוך מבני נתונים שפורטו למעלה או שהוגדרו על ידי המתכנת.

STL מגדירה חמש מחלקות בסיס עבור חמישה סוגי איטרטורים:

איטרטור קלט (input iterator) – איטרטור זה מאפשר רק קריאת האיבר עליו הוא מצביע וקידום לאיבר הבא ברצף.
איטרטור פלט (output iterator) – איטרטור זה מאפשר רק כתיבה (השמה) לתוך האיבר אליו הוא מצביע וקידום לאיבר הבא ברצף.
איטרטור חד-כיווני (forward iterator) – איטרטור זה מאפשר קריאה וכתיבה לאיבר שאליו הוא מצביע וקידום לאיבר הבא ברצף. לדוגמה: רשימה מקושרת חד-כיוונית מאפשרת אך ורק פעולות אלה. מחלקה זו נגזרת ממחלקת איטרטור הקלט ואיטרטור הפלט.
איטרטור דו-כיווני (bidirectional iterator) – נגזר מאיטרטור חד-כיווני. מאפשר גם מעבר לאיבר הקודם ולא רק לאיבר העוקב. לדוגמה: רשימה מקושרת דו-כיוונית מאפשרת אך ורק פעולות אלה.
איטרטור גישה אקראית (random access iterator) – נגזר מאיטרטור דו-כיווני. מאפשר גישה אקראית לאיברים שברצף, כלומר ניתן לגשת באמצעות אינדקס לכל אחד מהאיברים הבאים או הקודמים תוך זמן קבוע.

ניתן לקבל את האיטרטור למבנה נתונים מסוים באמצעות קריאה לפונקציית begin()‎ או end()‎. האיטרטורים, וחלוקתם לסוגים אלה, מאפשרים להגדיר אלגוריתמים גנריים. למשל מיון מהיר הממומש ב-STL יכול לקבל אך ורק איטרטור גישה אקראית ואילו אלגוריתם הסיכום יכול לקבל כל איטרטור קלט שהוא (והנגזרים ממנו).

אלגוריתמים

STL מגדירה אלגוריתמים נפוצים לשימוש המתכנת. על אף שרובם פשוטים, הם מאפשרים להימנע מכתיבת לולאות רבות.

האלגוריתמים שעובדים עם רצפים מקבלים איטרטורים לתחילת הרצף ולסוף הרצף. בין האלגוריתמים האלה קיימים אלגוריתמים:

שלא משנים את הרצף – בודקים שני רצפים לשוויון, מחפשים איבר בתוך הרצף (חיפוש בינארי וחיפוש ליניארי), סופרים את הופעת האובייקט בתוך הרצף, מחפשים תת-רצף בתוך הרצף הנתון.
משנים את הרצפים – מעתיקים רצף, מאתחלים רצף, מוחקים מהרצף את הופעות האובייקט, מערבבים את האיברים.
ממיינים את הרצף – במיון מהיר, מיון השומר על הסדר של איברים שווים, מיון חלקי.
עובדים עם רצפים ממויינים – מיזוג רצפים, פעולות על קבוצות.
מממשים ערימה – הוספה, מיון ומחיקה מערימה.

ראו גם

קישורים חיצוניים

אתר באנגלית המכיל את פירוט מבני הנתונים, והאלגוריתמים.
הרצאה על הספרייה הסטנדרטית במסגרת קורס באוניברסיטה העברית

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31713111ספריית התבניות התקנית