איטרטור

איטרטור הוא אובייקט במדעי המחשב המאפשר מעבר על איברי קבוצה נתונה. המעבר מתבצע באמצעות ממשק שאינו תלוי במימוש הפרטני של מבנה הנתונים המממש את הקבוצה.

רקע

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

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

בהכללה, נניח שקיימים $m$ מבני נתונים שונים, ו- $n$ אלגוריתמים. שימוש באיטרטורים מאפשר כתיבת $m+n$ קטעי קוד, במקום $m\times n$ קטעי קוד (אחד לכל שילוב אפשרי של אלגוריתם ומבנה נתונים). זהו הבסיס לרבות מספריות מבני הנתונים והאלגוריתמים העדכניות (למשל בשפת התכנות ++C).

דוגמה לשימוש באיטרטורים

נקח כדוגמה אלגוריתם פשוט: חיפוש ליניארי. באלגוריתם זה יש לעבור איבר איבר על איברי קבוצה נתונה, עד שמוצאים איבר המתאים לקריטריון כלשהו. השאלה היא מהי המשמעות של "לעבור איבר איבר":

1. במערך יש לקדם מצביע כך שיצביע לאיבר הבא במערך.
2. ברשימה מקושרת יש לעקוב אחרי המצביע לחוליה הבאה בחוליה הנוכחית.
3. בעץ חיפוש בינארי ישנה חוקיות מסובכת יותר (המתחילה בכלל: אם לצומת יש בן ימני, יש לעבור אליו, ולהמשיך לרדת שמאלה ככל האפשר).

השימוש באיטרטורים מאפשר להגדיר אלגוריתם יחידי לחיפוש ליניארי, המתאים לכל אחת מאפשרויות אלו:

1. בקש ממבנה הנתונים איטרטור לאיבר הראשון; קבע את האיטרטור הנוכחי כאיטרטור עליו מצביעים כרגע.
2. בקש ממבנה הנתונים איטרטור לאיבר האחרון.
3. כל עוד האיבר המוצבע על ידי האיטרטור הנוכחי אינו ממלא את הקריטריון, בדוק האם הוא שקול לאיטרטור האחרון. אם כן, האיבר המבוקש אינו נמצא במבנה שלנו. אם לא, קדם את האיטרטור לאיבר הבא.

שימו לב כי מדובר באלגוריתם כללי שאינו תלוי במבנה הנתונים.

ראו גם

• איטרציה

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

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

24489103איטרטור