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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

היסטוריה[עריכת קוד מקור | עריכה]

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

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

שירותי הספרייה[עריכת קוד מקור | עריכה]

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

מבני נתונים[עריכת קוד מקור | עריכה]

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

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

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

כמו כן, חלק ממבני הנתונים מבוססים על מבני נתונים בסיסיים אחרים. מבני נתונים אלה נקראים אדפטורים (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 מגדירה אלגוריתמים נפוצים לשימוש המתכנת. על אף שרובם פשוטים, הם מאפשרים להימנע מכתיבת לולאות רבות.

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]