איטרטור

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

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

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

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

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

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

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

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

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

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

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