ایتریتور

بندانگشتی|محمد پیروندی
در برنامه‌نویسی رایانه، **ایتریتور**  یا **پیمایشگر** یک شیء است که به یک برنامه‌نویس امکان می‌دهد تا یک گردآورد – به ویژه فهرست‌ها – را پیمایش کند. معمولاً رابط برنامه‌نویسی یک گردآورد، امکان استفاده از انواع مختلفی از پیمایشگرها را می‌دهد. هر نوع خاص از پیمایشگر می‌تواند در انواع مختلف گردآورد،  کاربرد و معنای یکسانی داشته باشد اما چگونگی پیاده‌سازی درونی آن برای هر گردآورد، وابستگی زیادی به ساختار درونی و چگونگی پیاده‌سازی گردآورد متناظرش دارد.

اگرچه که پیمایشگر (ایتریتور) عملیات پیمایش را انجام می‌دهد و همچنین دسترسی به عناصر دادهٔ موجود در یک گردآورد را ممکن می‌سازد، اما خود ایتریشن را انجام نمی‌دهد (البته اگر دایرهٔ معنایی ایتریشن را خیلی گسترده در نظر نگیریم). می‌توان پیمایشگر را مشابه مکان‌نما در پایگاه داده در نظر گرفت و هر دو بر مبنای الگوی تکرار طراحی شده‌اند. پیمایشگرها با زبان برنامه‌نویسی سی‌ال‌یو در سال ۱۹۷۴ مطرح شدند.

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

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

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

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

#### مولدها
یکی از راه‌های پیاده‌سازی پیمایشگرها استفاده از شکلی محدود از هَم‌رَویه است که با نام مولد شناخته می‌شود. برخلاف یک رویه، یک هم‌رویهٔ مولد می‌تواند به جای این که فقط یک بار مقادیر خروجی را برای فراخوانندهٔ خود برگرداند، آنها را چندین بار به فراخواننده خود *واگذار* ** کند. بیشتر پیمایشگرها به‌طور طبیعی به عنوان مولد قابل بیان هستند، اما از آنجا که مولدها حالت محلی خود (یعنی مقدار متغیرهای تابع و …) را در بین فراخوانی‌ها حفظ می‌کنند، آنها به‌طور ویژه برای پیمایشگرهای پیچیده و حالتمند  مانند پیمایشگرهای درخت مناسب هستند. در معنای اصطلاحات «مولد» و «ایتریتور (پیمایشگر)» که بین نویسندگان و زبان‌ها متفاوت است، تفاوت‌ها و تمایزهای ظریفی وجود دارد. در پایتون، یک مولد، سازنده‌ی پیمایشگر است یا به عبارت دیگر، تابعی است که یک پیمایشگر برمی‌گرداند. در زیر، مثالی از مولد پایتون آمده که با استفاده از دستور `yield` در پایتون، پیمایشگری را برای اعداد فیبوناچی برگردانده است:
```python
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 باشد. به این گونه که از `*` و `<span lang="fa" dir="ltr">-></span>` برای ارجاع به عنصری که پیمایشگر به آن اشاره می‌کند استفاده می‌شود و از عملگرهای ریاضی روی اشاره‌گر مانند `++` برای تغییر دادن در پیمایشگر در هنگام پیمایش یک گردآورد استفاده می‌شود.

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

برای پیمایش کامل یک گردآورد، متد `<span lang="fa" dir="ltr">begin()</span>` حد پایین و متد `<span lang="fa" dir="ltr">end()</span>` حد بالای پیمایش را مشخص می‌کند. توجه شود که `<span lang="fa" dir="ltr">end()</span>` به هیچ عنصری از گردآورد ارجاع نمی‌دهد اما یک پیمایشگر معتبر است و می‌توان سایر پیمایشگرها را با آن مقایسه کرد.

مثال زیر استفادهٔ معمول از یک پیمایشگر را نشان می‌دهد.
```cpp
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".
```
نوع پیمایشگر از نوع گردآورد مورد پیمایش، مستقل است، گرچه این دو اغلب همراه یکدیگر استفاده می‌شوند. دستهٔ پیمایشگر (و در نتیجه عملیات تعریف شده برای آن) معمولاً به نوع گردآورد بستگی دارد، به عنوان مثال آرایه‌ها یا وکتورها پیمایشگر دسترسی تصادفی را ارائه می‌دهند، اما مجموع‌ه‌ها (که با یک ساختار پیوندی پیاده‌سازی شده‌اند) فقط پیمایشگرهای دوطرفه را ارائه می‌دهند. یک نوع گردآورد مشابه می‌تواند بیش از یک نوع پیمایشگر مرتبط داشته باشد. به عنوان مثال نوع `<span lang="fa" dir="ltr">std::vector&#x3C;T&#x3E;</span>` امکان پیمایش یا استفاده از اشاره‌گرهای (خام) عناصر آن (با نوع `<span lang="fa" dir="ltr">*&#x3C;T&#x3E;</span>`) یا مقادیر با نوع خاص `std::vector&#x3C;T&#x3E;::iterator` و نوع دیگری برای "پیمایشگرهای معکوس" ارائه شده‌است، که عملیات آنها به گونه‌ای تعریف می‌شود که الگوریتمی که یک پیمایش معمول (رو به جلو) را انجام می‌دهد، در صورت فراخوانی با پیمایشگرهای معکوس، پیمایش را به ترتیب معکوس انجام می‌دهد. اکثر گردآوردها همچنین یک `const_iterator` جداگانه ارائه می‌دهند، برای این کار عملیاتی که اجازه تغییر مقادیر اشاره شده را می‌دهند عمداً تعریف نشده‌اند.

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

تکرار ضمنی همچنین با استفاده از الگوهای عملکرد استاندارد، مانند `<span lang="fa" dir="ltr">[https://en.cppreference.com/w/cpp/algorithm/for_each std::for_each()]</span>`، `<span lang="fa" dir="ltr">[https://en.cppreference.com/w/cpp/algorithm/copy std::copy()]</span>` و `<span lang="fa" dir="ltr">[https://en.cppreference.com/w/cpp/algorithm/accumulate std::accumulate()]</span>` تا حدودی توسط C++ پشتیبانی می‌شود.

هنگام استفاده، آنها باید با پیمایشگرهای موجود مقداردهی شوند، معمولاً `begin` و `end` که محدوده تکرار را تعریف می‌کند. اما هیچ شی پیمایشگر صریحی متعاقباً با ادامه تکرار در معرض دید قرار نمی‌گیرد. این مثال استفاده از `for_each` نشان می‌دهد.
```cpp
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` و پاس دادن مقدار `[https://en.cppreference.com/w/cpp/iterator/ostream_iterator std::ostream_iterator]` به عنوان پیمایشگر سوم، می‌توان به همان نتیجه رسید:
```c++
std::copy(c.begin(), c.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));
```
از زمان C++11، به منظور بی‌نیازی از تعریف یک تابع با نام مشخص، می‌توان از ساختار تابع lambda برای تعیین عملکرد مورد نظر استفاده کرد. در اینجا مثالی از پیمایش با `for_each` با استفاده از یک تابع lambda آورده شده‌است:
```cpp
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` و …).
```rust
for n in 0..42 {
    println!("{}", n);
}
```
در زیر تابع `<span lang="fa" dir="ltr">fibonacci()</span>` یک پیمایشگر دلخواه خاص را برمی‌گرداند
```rust
for i in fibonacci().skip(4).take(4) {
    println!("{}", i);
}
```


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

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

## پیوند به بیرون
* اینترفیس <span lang="fa" dir="ltr">.NET</span>
* مقاله "درک و استفاده از پیمایشگرها" نوشته جاشوا گتکامب
* مقاله "روشی برای ایتریشن عمومی و بهینه سازی آن " (۲۱۷ کیلوبایت) توسط استفان م. وات
* مستندات برخط گنو جی‌سی‌سی برای پیمایشگرها
* کتابخانه‌ی پیمایشگرهای <span lang="fa" dir="ltr">Boost C++</span>
* اینترفیس جاوا
* PHP: ایتریشن روی اشیاء
*مستندات کامل پیمایشگرهای کتابخانه‌ٔ استاندارد سی++
* پیمایشگرهای STL
* پیمایشگرها چه هستند؟ - شرح مرجع
رده:تکرار در برنامه‌نویسی
رده:شیء (علوم رایانه)
رده:مقاله‌های با مثال کد سی شارپ
رده:مقاله‌های دارای کد نمونه به زبان پایتون
رده:مقاله‌های دارای کد نمونه جاوا
رده:نوع داده انتزاعی
رده:مقاله‌های دارای کد نمونه به زبان سی‌پلاس‌پلاس