ایتریتور

پیمایشگرهای درونی

پیمایشگرهای درونی، توابع مرتبهٔ بالاتری مانند Map و Reduce هستند که پیمایش کل گردآورد همراه با اعمال به‌نوبتِ تابع ورودی روی هر عنصر را پیاده‌سازی می‌کنند.

پیمایشگرهای بیرونی و الگوی پیمایشگر

یک پیمایشگر بیرونی را می‌توان مانند یک اشاره‌گر در نظر گرفت که قادر به انجام دادن دو عملیات مهم است: ارجاع دادن به یک عنصر خاص درون گردآورد مورد استفاده (که به آن دسترسی به عنصر (به انگلیسی: element access) می‌گوییم) و ایجاد در تغییر در خودش به گونه‌ای که به عنصر بعدیِ گردآورد اشاره کند (که به آن پیمایش عنصر (به انگلیسی: element traversal) می‌گوییم). همچنین باید راهی برای ایجاد یک پیمایشگر وجود داشته باشد که در ابتدا به یکی از عناصر اشاره کند. افزون بر این، باید تدبیری برای تشخیص این که همهٔ عناصر موجود در گردآورد پیمایش شده‌اند یا خیر، وجود داشته باشد. البته پیمایشگرها ممکن است که توانایی انجام عملیات‌های بیشتری داشته باشند یا رفتارهای متفاوتی از خود نشان دهند اما این موضوع به زبان برنامه‌نویسی و کاربرد مورد نظر بستگی دارد.

هدف اصلی پیمایشگر این است که به کاربر این امکان را دهد که بدون توجه به ساختار درونی یک گردآورد، هر عنصر از گردآورد را پردازش کند. بدین ترتیب، گردآورد نیز این امکان را دارد که عناصر را به هر طریقی که بخواهد ذخیره کند در حالی که کاربر قادر است با آن صرفاً مانند یک دنباله یا فهرست ساده رفتار کند. معمولاً تلاش می‌شود که یک کلاس پیمایشگر شدیداً متناسب با کلاس گردآورد مربوطه طراحی شود. معمولاً خود گردآورد متدهای ساخت پیمایشگر را فراهم می‌کند.

از شمارندهٔ حلقه نیز گاهی اوقات به عنوان پیمایشگر حلقه یاد می‌شود. اما باید توجه کرد که شمارندهٔ حلقه فقط قابلیت پیمایش عناصر را دارد و امکان دسترسی به عنصر را ندارد.

مولدها

یکی از راه‌های پیاده‌سازی پیمایشگرها استفاده از شکلی محدود از هَم‌رَویه است که با نام مولد شناخته می‌شود. برخلاف یک رویه، یک هم‌رویهٔ مولد می‌تواند به جای این که فقط یک بار مقادیر خروجی را برای فراخوانندهٔ خود برگرداند، آنها را چندین بار به فراخواننده خود واگذار (به انگلیسی: yield) کند. بیشتر پیمایشگرها به‌طور طبیعی به عنوان مولد قابل بیان هستند، اما از آنجا که مولدها حالت محلی خود (یعنی مقدار متغیرهای تابع و …) را در بین فراخوانی‌ها حفظ می‌کنند، آنها به‌طور ویژه برای پیمایشگرهای پیچیده و حالتمند (به انگلیسی: stateful) مانند پیمایشگرهای درخت مناسب هستند. در معنای اصطلاحات «مولد» و «ایتریتور (پیمایشگر)» که بین نویسندگان و زبان‌ها متفاوت است، تفاوت‌ها و تمایزهای ظریفی وجود دارد. در پایتون، یک مولد، سازنده‌ی پیمایشگر است یا به عبارت دیگر، تابعی است که یک پیمایشگر برمی‌گرداند. در زیر، مثالی از مولد پایتون آمده که با استفاده از دستور yield در پایتون، پیمایشگری را برای اعداد فیبوناچی برگردانده است:

def fibonacci(limit):
    a, b = 0, 1
    for _ in range(limit):
        yield a
        a, b = b, a + b

for number in fibonacci(100): # The generator constructs an iterator
    print(number)

ایتریتورهای ضمنی

برخی از زبان‌های شی‌گرا مانند سی‌شارپ، سی‌پلاس‌پلاس (نسخه‌های جدیدتر)، دلفی (نسخه‌های جدیدتر)، گو، جاوا (نسخه‌های جدیدتر)، لوآ، پرل، پایتون، روبی برای پیمایش عناصر موجود در یک شیء گردآورد، بدون معرفی یک شیء پیمایشگر صریح، یک تابع ذاتی فراهم می‌کنند. ممکن است که در حقیقت، یک شیء پیمایشگر وجود داشته باشد، اما اگر هم چنین باشد، در کد منبع زبان قرار نمی‌گیرد.

++C

زبان ++C در کتابخانهٔ استاندارد خود از پیمایشگرها استفاده گسترده‌ای می‌کند و چندین دسته از پیمایشگرها را در رپرتوار عملیاتی که مجاز هستند متفاوت توصیف می‌کند. به منظور افزایش قابلیت‌ها، این دسته‌ها شامل پیمایشگرهای جلورونده، پیمایشگرهای دوطرفه و پیمایشگرهای با دسترسی تصادفی می‌شوند. همه انواع قالب استاندارد ظرف تکرارکننده یکی از این دسته‌ها را ارائه می‌دهند. پیمایشگرها، تعمیمی بر اشاره‌گرهای به عناصر یک آرایه هستند (در واقع خود این اشاره‌گرها می‌توانند به عنوان یک پیمایشگر استفاده شوند)، و نحوهٔ استفاده از آنها به گونه‌ای طراحی شده‌است که مانند محاسبات اشاره‌گر در زبان C باشد. به این گونه که از * و -> برای ارجاع به عنصری که پیمایشگر به آن اشاره می‌کند استفاده می‌شود و از عملگرهای ریاضی روی اشاره‌گر مانند ++ برای تغییر دادن در پیمایشگر در هنگام پیمایش یک گردآورد استفاده می‌شود.

معمولاً برای پیمایش با استفاده از پیمایشگرها، نیاز به یک پیمایشگر متحرک و دو پیمایشگر ثابت است که این دو، نقش محدودکنندهٔ بازهٔ پیمایش مورد نظر را دارند. فاصلهٔ بین پیمایشگرهای محدودکننده، از نظر تعداد دفعاتی که لازم است عملگر ++ روی حد پایین عمل کند تا آن را حد بالا برساند، برابر است با تعداد عناصری که در بازهٔ مورد نظر قرار دارند؛ بنابراین تعداد پیمایشگرهای متمایز دقیقاً یکی از تعداد عناصر موجود در بازهٔ مورد پیمایش بیشتر است. این‌طور قرارداد شده‌است که پیمایشگر مربوط به حد پایین به اولین عنصر موجود در بازهٔ پیمایش اشاره می‌کند اما پیمایشگر مربوط به حد بالا به هیچ عنصری درون بازهٔ پیمایش اشاره نمی‌کند، بلکه دقیقاً یک واحد فراتر از انتهای بازه است.

برای پیمایش کامل یک گردآورد، متد begin() حد پایین و متد end() حد بالای پیمایش را مشخص می‌کند. توجه شود که end() به هیچ عنصری از گردآورد ارجاع نمی‌دهد اما یک پیمایشگر معتبر است و می‌توان سایر پیمایشگرها را با آن مقایسه کرد.

مثال زیر استفادهٔ معمول از یک پیمایشگر را نشان می‌دهد.

std::vector<int> items;
items.push_back(5); // Append integer value '5' to vector 'items'.
items.push_back(2); // Append integer value '2' to vector 'items'.
items.push_back(9); // Append integer value '9' to vector 'items'.

for (auto it = items.begin(); it != items.end(); ++it) { // Iterate through 'items'.
  std::cout << *it; // And print value of 'items' for current index.
}
// In C++11, the same can be done without using any iterators:
for (auto x : items) {
  std::cout << x; // Print value of each element 'x' of 'items'.
}

// Each loops print "529".

نوع پیمایشگر از نوع گردآورد مورد پیمایش، مستقل است، گرچه این دو اغلب همراه یکدیگر استفاده می‌شوند. دستهٔ پیمایشگر (و در نتیجه عملیات تعریف شده برای آن) معمولاً به نوع گردآورد بستگی دارد، به عنوان مثال آرایه‌ها یا وکتورها پیمایشگر دسترسی تصادفی را ارائه می‌دهند، اما مجموع‌ه‌ها (که با یک ساختار پیوندی پیاده‌سازی شده‌اند) فقط پیمایشگرهای دوطرفه را ارائه می‌دهند. یک نوع گردآورد مشابه می‌تواند بیش از یک نوع پیمایشگر مرتبط داشته باشد. به عنوان مثال نوع std::vector<T> امکان پیمایش یا استفاده از اشاره‌گرهای (خام) عناصر آن (با نوع *<T>) یا مقادیر با نوع خاص std::vector<T>::iterator و نوع دیگری برای "پیمایشگرهای معکوس" ارائه شده‌است، که عملیات آنها به گونه‌ای تعریف می‌شود که الگوریتمی که یک پیمایش معمول (رو به جلو) را انجام می‌دهد، در صورت فراخوانی با پیمایشگرهای معکوس، پیمایش را به ترتیب معکوس انجام می‌دهد. اکثر گردآوردها همچنین یک const_iterator جداگانه ارائه می‌دهند، برای این کار عملیاتی که اجازه تغییر مقادیر اشاره شده را می‌دهند عمداً تعریف نشده‌اند.

پیمایش ساده یک شی گردآورد یا بازه‌ای از عناصر آن (همراه با ویرایش آن عناصر مگر اینکه از یک const_iterator استفاده شده باشد) را می‌توان فقط با پیمایشگر انجام داد. اما انواع گردآوردها ممکن است متدهایی مانند insert یا erase نیز فراهم کنند که ساختار خود گردآورد را ویرایش می‌کند. اینها متدهای کلاس گردآورد هستند، اما علاوه بر این برای تعیین عملکرد مورد نظر به یک یا چند مقدار پیمایشگر نیاز دارند. در حالی که امکان دارد چندین پیمایشگر به‌طور همزمان به یک ظرف اشاره داشته باشند، عملیات اصلاح ساختار ممکن است برخی از مقادیر پیمایشگرها را فاقد اعتبار کند (استاندارد برای هر مورد مشخص می‌کند که آیا این ممکن است). استفاده از پیمایشگرِ نامعتبر خطایی است که منجر به رفتار نامشخص می‌شود، و سامانه در زمان اجرا برای چنین خطاهایی لزوماً سیگنال نمی‌دهد.

تکرار ضمنی همچنین با استفاده از الگوهای عملکرد استاندارد، مانند std::for_each()، std::copy() و std::accumulate() تا حدودی توسط C++ پشتیبانی می‌شود.

هنگام استفاده، آنها باید با پیمایشگرهای موجود مقداردهی شوند، معمولاً begin و end که محدوده تکرار را تعریف می‌کند. اما هیچ شی پیمایشگر صریحی متعاقباً با ادامه تکرار در معرض دید قرار نمی‌گیرد. این مثال استفاده از for_each نشان می‌دهد.

ContainerType<ItemType> c; // Any standard container type of ItemType elements.

void ProcessItem(const ItemType& i) { // Function that will process each item of the collection.
  std::cout << i << std::endl;
}

std::for_each(c.begin(), c.end(), ProcessItem); // A for-each iteration loop.

با استفاده از std::copy و پاس دادن مقدار std::ostream_iterator به عنوان پیمایشگر سوم، می‌توان به همان نتیجه رسید:

std::copy(c.begin(), c.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));

از زمان C++11، به منظور بی‌نیازی از تعریف یک تابع با نام مشخص، می‌توان از ساختار تابع lambda برای تعیین عملکرد مورد نظر استفاده کرد. در اینجا مثالی از پیمایش با for_each با استفاده از یک تابع lambda آورده شده‌است:

ContainerType<ItemType> c; // Any standard container type of ItemType elements.

// A for-each iteration loop with a lambda function.
std::for_each(c.begin(), c.end(), [](const ItemType& i) { std::cout << i << std::endl; });

راست

در زبان راست می‌توان عناصر وکتور (vec) را پیمایش کرد یا پیمایشگر خود را ایجاد کرد. هر پیمایشگر آداپتورهایی دارد (از جمله map، filter، skip، take و …).

for n in 0..42 {
    println!("{}", n);
}

در زیر تابع fibonacci() یک پیمایشگر دلخواه خاص را برمی‌گرداند

for i in fibonacci().skip(4).take(4) {
    println!("{}", i);
}

• الگوی طراحی نرم‌افزار
• ایتریشن یا تکرار
• الگوی تکرار
• الگوی بازدیدگر
• اشاره‌گر (برنامه‌نویسی رایانه)

مشارکت‌کنندگان در مقالهٔ Iterator در ویکی‌پدیای انگلیسی، ۳۰ ژوئن ۲۰۲۱

• اینترفیس .NET
• مقاله "درک و استفاده از پیمایشگرها" نوشته جاشوا گتکامب
• مقاله "روشی برای ایتریشن عمومی و بهینه سازی آن " (۲۱۷ کیلوبایت) توسط استفان م. وات
• مستندات برخط گنو جی‌سی‌سی برای پیمایشگرها
• کتابخانه‌ی پیمایشگرهای Boost C++
• اینترفیس جاوا
• PHP: ایتریشن روی اشیاء
• مستندات کامل پیمایشگرهای کتابخانه‌ٔ استاندارد سی++
• پیمایشگرهای STL
• پیمایشگرها چه هستند؟ - شرح مرجع