איטרטור

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

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

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

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

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

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

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

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