ایتریتور
در برنامه‌نویسی رایانه، ایتریتور (به انگلیسی: Iterator) یا پیمایشگر[نیازمند منبع] یک شیء است که به یک برنامه‌نویس امکان می‌دهد تا یک گردآورد – به ویژه فهرست‌ها – را پیمایش کند.[۱][۲][۳] معمولاً رابط برنامه‌نویسی یک گردآورد، امکان استفاده از انواع مختلفی از پیمایشگرها را می‌دهد. هر نوع خاص از پیمایشگر می‌تواند در انواع مختلف گردآورد، کاربرد و معنای یکسانی داشته باشد اما چگونگی پیاده‌سازی درونی آن برای هر گردآورد، وابستگی زیادی به ساختار درونی و چگونگی پیاده‌سازی گردآورد متناظرش دارد.
اگرچه که پیمایشگر (ایتریتور) عملیات پیمایش را انجام می‌دهد و همچنین دسترسی به عناصر دادهٔ موجود در یک گردآورد را ممکن می‌سازد، اما خود ایتریشن را انجام نمی‌دهد (البته اگر دایرهٔ معنایی ایتریشن را خیلی گسترده در نظر نگیریم).[نیازمند منبع] می‌توان پیمایشگر را مشابه مکان‌نما در پایگاه داده در نظر گرفت و هر دو بر مبنای الگوی تکرار طراحی شده‌اند. پیمایشگرها با زبان برنامه‌نویسی سی‌ال‌یو در سال ۱۹۷۴ مطرح شدند.
تعریف ویرایش
پیمایشگرهای درونی ویرایش
پیمایشگرهای درونی، توابع مرتبهٔ بالاتری مانند 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 در ویکی‌پدیای انگلیسی، ۳۰ ژوئن ۲۰۲۱
- ↑ Gatcomb, Joshua. "Understanding and Using Iterators". Perl.com. Archived from the original on 20 May 2021. Retrieved 2012-08-08.
A user-defined iterator usually takes the form of a code reference that, when executed, calculates the next item in a list and returns it. When the iterator reaches the end of the list, it returns an agreed-upon value.
{{cite web}}: نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link) - ↑ ۲٫۰ ۲٫۱ Watt, Stephen M. "A Technique for Generic Iteration and Its Optimization". The University of Western Ontario, Department of Computer Science. Archived from the original on 25 May 2021. Retrieved 2012-08-08.
Iterators were introduced as constructs to allow looping over abstract data structures without revealing their internal representation.
{{cite web}}: نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link) - ↑ Alex Allain. "STL Iterators". Cprogramming.com - Your resource for C and C++. Retrieved 2012-08-08.
You can think of an iterator as pointing to an item that is part of a larger container of items.
- ↑ ۴٫۰ ۴٫۱ "Difference between an external iterator and an internal iterator". CareerRide.COM. 2009-04-03. Archived from the original on 21 June 2021. Retrieved 2012-08-08.
An internal iterator is implemented by the member functions of the class which has the iteration logic. An external iterator is implemented by a separate class which can be attached to the object which has iteration logic. The advantage of external iterator is that, many iterators can be made active simultaneously on the existing or same object.
{{cite web}}: نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link) - ↑ Watt, Stephen M. "A Technique for Generic Iteration and Its Optimization". The University of Western Ontario, Department of Computer Science. Archived from the original on 25 May 2021. Retrieved 2012-08-08.
Some authors use the term iterator, and others the term generator. Some make subtle distinctions between the two.
{{cite web}}: نگهداری یادکرد:ربات:وضعیت نامعلوم پیوند اصلی (link) - ↑ Freeman, Eric; Freeman, Elisabeth; Kathy, Sierra; Bert, Bates (2004). Hendrickson, Mike; Loukides, Mike (eds.). "Head First Design Patterns" (paperback). 1. O'REILLY: 338. ISBN 978-0-596-00712-6. Retrieved 2012-08-09.
{{cite journal}}: Cite journal requires|journal=(help)
پیوند به بیرون ویرایش
- اینترفیس .NET
- مقاله "درک و استفاده از پیمایشگرها" نوشته جاشوا گتکامب
- مقاله "روشی برای ایتریشن عمومی و بهینه سازی آن " (۲۱۷ کیلوبایت) توسط استفان م. وات
- مستندات برخط گنو جی‌سی‌سی برای پیمایشگرها
- کتابخانه‌ی پیمایشگرهای Boost C++
- اینترفیس جاوا
- PHP: ایتریشن روی اشیاء
- مستندات کامل پیمایشگرهای کتابخانهٔ استاندارد سی++
- پیمایشگرهای STL
- پیمایشگرها چه هستند؟ - شرح مرجع