/ OOD

[365 วันแห่งโปรแกรม #day62] Iterator pattern

วันที่หกสิบสองของ ‪#‎365วันแห่งโปรแกรม เรื่องแพทเทิร์นสำหรับท่องไปในข้อมูล (Iterator pattern ><)


Iterator pattern

พูดถึง Iterator ทีไรผมก็คิดถึงสมัยเรียนโปรแกรมมิ่งในมหาวิทยาลัย ที่เพื่อนๆ ท่องกันเป็นนกแก้วนกขุนทองว่า "Iterator ท่องไปในข้อมูล" คิดแล้วก็ยังขำไม่หาย ไม่รู้ทำไมผมถึงอธิบายไว้แบบนั้น แต่ก็นึกคำอื่นที่ง่ายๆ ไม่ออกจริงๆ นั่นแหละ

Iterator คิอ object ที่ช่วยให้เราสามารถิอ่านข้อมูลจาก container (collection) ขึ้นมาทีละตัวๆ ได้ โดยไม่ต้องสนใจว่า container นั้นมีโครงสร้างอย่างไร

จากนิยามนี้พบว่าประโยค "Iterator ท่องไปในข้อมูล" นั้นก็เหมาะสมดีแล้ว 5555+

Iterator เกิดขึ้นเพื่อช่วยให้เราสามารถเข้าถึงข้อมูลภายในโครงสร้างข้อมูลแบบต่างๆ ได้โดยใช้ interface แบบเดียวกัน แทนที่จะไปใช้โค้ดแบบ container-specific อีกทั้งยังเป็นการลดการ couple ระหว่างตัว container กับ algorithm อีกด้วย

สรุป Iterator pattern ก็คือการแยกส่วน algorithm ในการเข้าถึงข้อมูลบน container ออกมาเป็น Iterator

Implementation ของ Iterator ในภาษาโปรแกรมต่างๆ

ในแต่ละภาษาโปรแกรมก็มีการ implement iterator ไว้แตกต่างกัน

C++

C++ มีการ implement iterator เอาไว้โดยใช้ pointer เป็นหลัก มีการใช้ Generic ในการกำหนด type ของข้อมูลใน container แล้วใช้วิธี overload operator เพื่อเลื่อน pointer ไปที่ตำแหน่งต่างๆ ของสายข้อมูล

class MyIterator : public std::iterator<std::input_iterator_tag, int>
{
    int* p;
public:
    MyIterator(int* x) :p(x) {}
    MyIterator(const MyIterator& mit) : p(mit.p) {}
    MyIterator& operator++() {++p;return *this;}
    MyIterator operator++(int) {MyIterator tmp(*this); operator++(); return tmp;}
    bool operator==(const MyIterator& rhs) {return p==rhs.p;}
    bool operator!=(const MyIterator& rhs) {return p!=rhs.p;}
    int& operator*() {return *p;}
};

จากโค้ดจะเห็นว่า MyIterator มี constructor ที่รับ address ของ container (ของ int) ที่จะ iterate เข้าไปและมีการ overload เครื่องหมาย ++ ไว้เพื่อเลื่อน pointer (ทีละ 4 byte) ไปยังตัวเลขตำแหน่งถัดไป และเราสามารถดึงค่าที่ตำแหน่งปัจจุบันโดยใช้เครื่องหมาย *

การนำไปใช้ก็เริ่มจากการสร้าง Iterator ขึ้นมาโดยใส่พารามิเตอร์เป็น container ของ int แล้วก็ใช้ for loop ปกติในการวนดูสมาชิกไปเรื่อยๆ

int main () {
    int numbers[]={10,20,30,40,50};
    MyIterator from(numbers);
    MyIterator until(numbers+5);
    for (MyIterator it=from; it!=until; it++)
        std::cout << *it << ' ';
    std::cout << '\n';

    return 0;
}

จากตัวอย่างจะเห็นว่ามีการกำหนด iterator อีกตัวชื่อ until เพื่อเอาไว้กำหนดของเขตสูงสุดที่จะท่องไป (ใส่เป็นเงื่อนไขใน for loop)

Java

ใน Java มีการจัดเตรียม interface Iterator เอาไว้ให้ใช้สำหรับท่องดู object ใน container

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove();
}

จากโค้ดของ interface Iterator พบว่าใช้ Generic ในการระบุ type ของข้อมูลใน container เช่นกัน มีการเตรียม method สำหรับตรวจดูว่ามี element เหลืออีกไหม method สำหรับเลื่อน pointer ไปตัวถัดไป และ method สำหรับลบ element ปัจจุบัน

ตัวอย่างของการใช้งาน Iterator ใน Java

Set<Integer> set = new HashSet<Integer>();
// add some Integer to set
Iterator iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

จะเห็นว่าเราต้องขอ object ของ Iterator จาก Set มาก่อน แล้วถึงจะวนเอาขอดู element ต่างๆ ได้

ใน Java 5 นั้นมีการกำหนดว่า object ที่ implement interface Iterable ไว้ (มี method สำหรับขอ Iterator) สามารถใช้ enhanced for loop ในการวนขอ element แทนที่จะเรียก iterator ตรงๆ แบบเดิม

Set<Integer> set = new HashSet<Integer>();
// add some Integer to set
for(Integer i : set ) {
    System.out.println(i);
}

คราวนี้ไม่ค้องขอ Iterator เองแล้ว ตัว for loop จะเป็นคนจัดการให้หมดเลย

ภาษาอื่นๆ

ในภาษาโปรแกรมอื่นๆ นอกจากที่ยกตัวอย่างมา ก็มีการ implement Iterator ไว้คล้ายๆ กัน คือมี pointer สำหรับชี้ element ตัวปัจจุบัน และมี method สำหรับเลื่อน pointer

References

Iterator pattern - Wikipedia

std::iterator - cplusplus

Iterator interface - grepcode

#‎day62 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...