跳至主要內容

迭代器模式

约 590 字

迭代器模式

核心思想

迭代器模式提供了一种方法来顺序访问一个聚合对象中的各个元素,而不需要暴露其底层细节。

典型用例

遍历集合

当需要遍历不同类型的集合对象(如数组、列表、树结构、图)时,迭代器模式提供了一种统一的方法来访问它们的元素,无需了解集合的内部表示。

// npm run code src/code/design-pattern/iterator/ergodic-set.ts

export {};

// 定义迭代器接口,包含遍历集合所需的方法
interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(): MyIterator<T>;
}

// 具体的集合类
class ConcreteCollection<T> implements IterableCollection<T> {
    private items: T[] = [];

    constructor(items: T[]) {
        this.items = items;
    }

    createIterator(): MyIterator<T> {
        return new ConcreteIterator<T>(this);
    }

    get length(): number {
        return this.items.length;
    }

    get(index: number): T {
        return this.items[index];
    }
}

// 具体的迭代器类
class ConcreteIterator<T> implements MyIterator<T> {
    private collection: ConcreteCollection<T>;
    private position: number = 0;

    constructor(collection: ConcreteCollection<T>) {
        this.collection = collection;
    }

    next(): T {
        // 返回集合中的当前元素,并将位置移至下一个元素
        return this.collection.get(this.position++);
    }

    hasNext(): boolean {
        return this.position < this.collection.length;
    }
}

const collection = new ConcreteCollection<number>([1, 2, 3, 4, 5]);
const iterator = collection.createIterator();

while (iterator.hasNext()) {
    console.log(iterator.next());
}

支持多种遍历方式

迭代器模式允许定义一个迭代器接口和一个具体的迭代器类,用于遍历特定的数据结构。例如,对于一个树结构,我们可以实现两种迭代器:深度优先遍历和广度优先遍历。

// npm run code src/code/design-pattern/iterator/multiple-traversal-methods.ts

export {};

interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(type: 'depth-first' | 'breadth-first'): MyIterator<T>;
}

class TreeNode<T> {
    constructor(public value: T, public children: TreeNode<T>[] = []) {}
}

class DepthFirstIterator<T> implements MyIterator<T> {
    private stack: TreeNode<T>[];

    constructor(root: TreeNode<T>) {
        this.stack = [root];
    }

    next(): T {
        const node = this.stack.pop();
        if (node) {
            for (let i = node.children.length - 1; i >= 0; i--) {
                this.stack.push(node.children[i]);
            }
            return node.value;
        }
        throw new Error("No more elements");
    }

    hasNext(): boolean {
        return this.stack.length > 0;
    }
}

class BreadthFirstIterator<T> implements MyIterator<T> {
    private queue: TreeNode<T>[];

    constructor(root: TreeNode<T>) {
        this.queue = [root];
    }

    next(): T {
        const node = this.queue.shift();
        if (node) {
            this.queue.push(...node.children);
            return node.value;
        }
        throw new Error("No more elements");
    }

    hasNext(): boolean {
        return this.queue.length > 0;
    }
}

class Tree<T> implements IterableCollection<T> {
    constructor(public root: TreeNode<T>) {}

    createIterator(type: 'depth-first' | 'breadth-first'): MyIterator<T> {
        if (type === 'depth-first') {
            return new DepthFirstIterator<T>(this.root);
        } else {
            return new BreadthFirstIterator<T>(this.root);
        }
    }
}

// Example usage
const tree = new Tree(new TreeNode(1, [
    new TreeNode(2, [new TreeNode(4), new TreeNode(5)]),
    new TreeNode(3, [new TreeNode(6), new TreeNode(7)])
]));

const depthFirstIterator = tree.createIterator('depth-first');
while (depthFirstIterator.hasNext()) {
    console.log(depthFirstIterator.next());
}

const breadthFirstIterator = tree.createIterator('breadth-first');
while (breadthFirstIterator.hasNext()) {
    console.log(breadthFirstIterator.next());
}

隐藏复杂结构的遍历细节

迭代器模式可以用于隐藏复杂数据结构的遍历细节。可以创建一个复杂的数据结构(树或者图结构),并为其实现一个迭代器,这样客户端代码就可以通过迭代器接口简单地遍历这个结构,而不需要关心其内部复杂性。

// npm run code src/code/design-pattern/iterator/hide-traversal-details.ts

export {};

interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(): MyIterator<T>;
}

class GraphNode<T> {
    constructor(public value: T, public neighbors: GraphNode<T>[] = []) {}
}

class GraphIterator<T> implements MyIterator<T> {
    private visited = new Set<GraphNode<T>>();
    private stack: GraphNode<T>[];

    constructor(private root: GraphNode<T>) {
        this.stack = [root];
    }

    next(): T {
        while (this.stack.length > 0) {
            const node = this.stack.pop();
            if (node && !this.visited.has(node)) {
                this.visited.add(node);
                for (const neighbor of node.neighbors) {
                    this.stack.push(neighbor);
                }
                return node.value;
            }
        }
        throw new Error("No more elements");
    }

    hasNext(): boolean {
        return this.stack.length > 0;
    }
}

class Graph<T> implements IterableCollection<T> {
    constructor(private nodes: GraphNode<T>[]) {}

    createIterator(): MyIterator<T> {
        return new GraphIterator<T>(this.nodes[0]);
    }
}

// Example usage
const node1 = new GraphNode(1);
const node2 = new GraphNode(2);
const node3 = new GraphNode(3);
const node4 = new GraphNode(4);

node1.neighbors.push(node2, node3);
node2.neighbors.push(node4);
node3.neighbors.push(node4);

const graph = new Graph([node1, node2, node3, node4]);

const iterator = graph.createIterator();
while (iterator.hasNext()) {
    console.log(iterator.next());
}

同时多个遍历

迭代器模式可以同时进行多个遍历。在这个例子中,创建一个集合类,并为其实现迭代器,使得可以同时创建多个独立的迭代器,每个迭代器都维护自己的遍历状态,不会相互影响。

// npm run code src/code/design-pattern/iterator/multiple-traversals-meanwhile.ts

export {};

interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(): MyIterator<T>;
}

class ArrayIterator<T> implements MyIterator<T> {
    private currentIndex = 0;

    constructor(private collection: T[]) {}

    next(): T {
        if (!this.hasNext()) {
            throw new Error("No more elements");
        }
        return this.collection[this.currentIndex++];
    }

    hasNext(): boolean {
        return this.currentIndex < this.collection.length;
    }
}

class ArrayCollection<T> implements IterableCollection<T> {
    constructor(private items: T[]) {}

    createIterator(): MyIterator<T> {
        return new ArrayIterator<T>(this.items);
    }
}

// Example usage
const collection = new ArrayCollection([1, 2, 3, 4, 5]);

const iterator1 = collection.createIterator();
const iterator2 = collection.createIterator();

console.log("Iterator 1:", iterator1.next()); // Outputs 1
console.log("Iterator 2:", iterator2.next()); // Outputs 1

console.log("Iterator 1:", iterator1.next()); // Outputs 2
console.log("Iterator 1:", iterator1.next()); // Outputs 3

console.log("Iterator 2:", iterator2.next()); // Outputs 2

分离集合对象的业务逻辑

迭代器模式可以将业务逻辑从集合对象分离出来。在这个例子中,首先创建了一个集合类,然后为其实现一个迭代器。这样,集合类专注于元素的管理,而迭代器负责遍历逻辑,从而实现关注点的分离。

// npm run code src/code/design-pattern/iterator/separate-business-logic.ts

export {};

interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(): MyIterator<T>;
}

class Product {
    constructor(public name: string, public price: number) {}
}

class ProductIterator implements MyIterator<Product> {
    private currentIndex = 0;

    constructor(private collection: Product[]) {}

    next(): Product {
        if (!this.hasNext()) {
            throw new Error("No more elements");
        }
        return this.collection[this.currentIndex++];
    }

    hasNext(): boolean {
        return this.currentIndex < this.collection.length;
    }
}

class ProductCollection implements IterableCollection<Product> {
    private products: Product[] = [];

    createIterator(): MyIterator<Product> {
        return new ProductIterator(this.products);
    }

    addProduct(product: Product): void {
        this.products.push(product);
    }

    removeProduct(product: Product): void {
        this.products = this.products.filter(p => p !== product);
    }
}

// Example usage
const collection = new ProductCollection();
collection.addProduct(new Product("Apple", 1.2));
collection.addProduct(new Product("Banana", 0.8));

const iterator = collection.createIterator();
while (iterator.hasNext()) {
    const product = iterator.next();
    console.log(`Product: ${product.name}, Price: ${product.price}`);
}

间接访问集合元素

迭代器模式允许客户端通过迭代器接口遍历集合,而不是直接操作集合内部数据结构。

// npm run code src/code/design-pattern/iterator/indirect-access-set.ts

export {};

interface MyIterator<T> {
    next(): T;
    hasNext(): boolean;
}

interface IterableCollection<T> {
    createIterator(): MyIterator<T>;
}

class Book {
    constructor(public title: string, public author: string) {}
}

class BookIterator implements MyIterator<Book> {
    private currentIndex = 0;

    constructor(private collection: Book[]) {}

    next(): Book {
        if (!this.hasNext()) {
            throw new Error("No more elements");
        }
        return this.collection[this.currentIndex++];
    }

    hasNext(): boolean {
        return this.currentIndex < this.collection.length;
    }
}

class BookCollection implements IterableCollection<Book> {
    private books: Book[] = [];

    createIterator(): MyIterator<Book> {
        return new BookIterator(this.books);
    }

    addBook(book: Book): void {
        this.books.push(book);
    }
}

// Example usage
const bookCollection = new BookCollection();
bookCollection.addBook(new Book("The Great Gatsby", "F. Scott Fitzgerald"));
bookCollection.addBook(new Book("1984", "George Orwell"));

const iterator = bookCollection.createIterator();
while (iterator.hasNext()) {
    const book = iterator.next();
    console.log(`Book: ${book.title}, Author: ${book.author}`);
}

上次编辑于: