java 访谈：为集合集合设计迭代器

Interview: Design an iterator for a collection of collections

提问by

Design an iterator for a collection of collections in java. The iterator should hide the nesting, allowing you to iterate all of the elements belonging to all of the collections as if you were working with a single collection

在 java 中为集合的集合设计一个迭代器。迭代器应该隐藏嵌套，允许您迭代属于所有集合的所有元素，就像您在处理单个集合一样

采纳答案by Eyal Schneider

Here is a possible implementation. Note that I left remove() unimplemented:

这是一个可能的实现。请注意，我未实现 remove() ：

public class MultiIterator <T> implements Iterator<T>{

    private Iterator<? extends Collection<T>> it;
    private Iterator<T> innerIt;
    private T next;
    private boolean hasNext = true;

    public MultiIterator(Collection<? extends Collection<T>> collections) {
        it = collections.iterator();    
        prepareNext();
    }

    private void prepareNext() {
        do {
            if (innerIt == null || !innerIt.hasNext()) {
                if (!it.hasNext()) {
                    hasNext = false;
                    return;
                } else
                    innerIt = it.next().iterator();
            }
        } while (!innerIt.hasNext());

        next = innerIt.next();
    }

    @Override
    public boolean hasNext() {
        return hasNext;
    }

    @Override
    public T next() {
        if (!hasNext)
            throw new NoSuchElementException();
        T res = next;
        prepareNext();
        return res;
    }

    @Override
    public void remove() {
        //TODO
    }

}

回答by Federico Peralta Schaffner

This is an old question, but nowadays (2019) we have JDK8+ goodies. In particular, we have streams, which make this task straightforward:

这是一个老问题，但现在（2019 年）我们有 JDK8+ 好东西。特别是，我们有流，它使这个任务变得简单：

public static <T> Iterator<T> flatIterator(Collection<Collection<T>> collections) {

    return collections.stream()
            .filter(Objects::nonNull)
            .flatMap(Collection::stream)
            .iterator();
}

I'm filtering nullinner collections out, just in case...

我正在过滤null内部集合，以防万一......

---

---

EDIT:If you also want to filter nullelements out of the inner collections, just add an extra non-null filter aflter flatMap:

编辑：如果您还想null从内部集合中过滤元素，只需添加一个额外的非空过滤器 aflter flatMap：

return collections.stream()
        .filter(Objects::nonNull)
        .flatMap(Collection::stream)
        .filter(Objects::nonNull)
        .iterator();

回答by alfasin

In this postyou can see two implementations, the only (minor) difference is that it takes an iterator of iterators instead of a collection of collections.

在这篇文章中，您可以看到两个实现，唯一的（次要）区别是它采用迭代器的迭代器而不是集合的集合。

This difference combined with the requirement to iterate the elements in a round-robin fashion (a requirement that wasn't requested by the OP in thisquestion) adds the overhead of copying the iterators into a list.

这种差异与以循环方式迭代元素的要求（OP 在这个问题中没有要求的要求）相结合，增加了将迭代器复制到列表中的开销。

The first approach is lazy: it will iterate an element only when this element is requested, the 'price' we have to pay is that the code is more complex because it needs to handle more edge-cases:

第一种方法是惰性的：它只会在请求元素时迭代该元素，我们必须付出的“代价”是代码更复杂，因为它需要处理更多的边缘情况：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;    

public class MultiIterator<E> implements Iterator {

    List<Iterator<E>> iterators = new LinkedList<>();
    Iterator<E> current = null;

    public MultiIterator(Iterator<Iterator<E>> iterator) {
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
    }

    @Override
    public boolean hasNext() {
        boolean result = false;
        if (iterators.isEmpty() && (current == null || !current.hasNext())) {
            return false;
        }

        if (current == null) {
            current = iterators.remove(0);
        }

        while (!current.hasNext() && !iterators.isEmpty()) {
            current = iterators.remove(0);
        }

        if (current.hasNext()) {
            result = true;
        }
        return result;
    }

    @Override
    public E next() {
        if (current == null) {
            try {
                current = iterators.remove(0);
            } catch (IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }
        E result = current.next(); // if this method was called without checking 'hasNext' this line might raise NoSuchElementException which is fine
        iterators.add(current);
        current = iterators.remove(0);
        return result;
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        MultiIterator<Integer> it = new MultiIterator<>(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

and the second ('greedy' copying of all the elements from all the iterators in the requested order into a list and returning an iterator to that list ):

和第二个（“贪婪”将所有元素从请求的顺序中的所有迭代器复制到一个列表中，并将迭代器返回到该列表）：

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class MultiIterator<E> {

    Iterator<Iterator<E>> iterator = null;
    List<E> elements = new LinkedList<>();

    private MultiIterator(Iterator<Iterator<E>> iterator) {
        this.iterator = iterator;
    }

    private void copyElementsInOrder() {
        List<Iterator<E>> iterators = new LinkedList<>();
        // copy the iterators into a list
        while (iterator.hasNext()) {
            iterators.add(iterator.next());
        }
        // go over the list, round-robin, and grab one
        // element from each sub-iterator and add it to *elements*
        // empty sub-iterators will get dropped off the list
        while (!iterators.isEmpty()) {
            Iterator<E> subIterator = iterators.remove(0);
            if (subIterator.hasNext()) {
                elements.add(subIterator.next());
                iterators.add(subIterator);
            }
        }
    }

    public static <E> Iterator<E> iterator(Iterator<Iterator<E>> iterator) {
        MultiIterator<E> instance = new MultiIterator<>(iterator);
        instance.copyElementsInOrder();
        return instance.elements.iterator();
    }

    // test
    public static void main(String[] args) {
        List<Integer> a = new LinkedList<>();
        a.add(1);
        a.add(7);
        a.add(13);
        a.add(17);
        List<Integer> b = new LinkedList<>();
        b.add(2);
        b.add(8);
        b.add(14);
        b.add(18);
        List<Integer> c = new LinkedList<>();
        c.add(3);
        c.add(9);
        List<Integer> d = new LinkedList<>();
        d.add(4);
        d.add(10);
        d.add(15);
        List<Integer> e = new LinkedList<>();
        e.add(5);
        e.add(11);
        List<Integer> f = new LinkedList<>();
        f.add(6);
        f.add(12);
        f.add(16);
        f.add(19);
        List<Iterator<Integer>> iterators = new LinkedList<>();
        iterators.add(a.iterator());
        iterators.add(b.iterator());
        iterators.add(c.iterator());
        iterators.add(d.iterator());
        iterators.add(e.iterator());
        iterators.add(f.iterator());
        Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());
        while (it.hasNext()) {
            System.out.print(it.next() + ","); // prints: 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,
        }
    }
}

I included a simple 'test' code in order to show the way to use the MultiIterator, this is not always trivial (because of the use of Generics) as you can see on the line:

我包含了一个简单的“测试”代码，以展示使用 MultiIterator 的方式，这并不总是微不足道的（因为使用了泛型），正如您在行中看到的：

Iterator<Integer> it = MultiIterator.<Integer>iterator(iterators.iterator());

回答by Geoffroy Warin

Here is another implementation:

这是另一个实现：

import java.util.Iterator;
import java.util.NoSuchElementException;

import static java.util.Collections.emptyIterator;

public class Multiterator<E> implements Iterator<E> {
    private Iterator<Iterator<E>> root;
    private Iterator<E> current;

    public Multiterator(Iterator<Iterator<E>> root) {
        this.root = root;
        current = null;
    }

    @Override
    public boolean hasNext() {
        if (current == null || !current.hasNext()) {
            current = getNextNonNullOrEmpty(root);
        }
        return current.hasNext();
    }

    private Iterator<E> getNextNonNullOrEmpty(Iterator<Iterator<E>> root) {
        while (root.hasNext()) {
            Iterator<E> next = root.next();
            if (next != null && next.hasNext()) {
                return next;
            }
        }
        return emptyIterator();
    }

    @Override
    public E next() {
        if (current == null) {
            throw new NoSuchElementException();
        }
        return current.next();
    }
}

回答by Uche Dim

if all you have to work with is the java Iterator: which just have hasNext(), next() and remove(), i figured you have to go around it.

如果您只需要使用 java Iterator：它只有 hasNext()、next() 和 remove()，我想您必须绕过它。

Process it as you will process a 2D array, that is, with an outer and inner loop, because they have same "arrangement" but different datatype. As you process, you transfer them to a new collection.

像处理二维数组一样处理它，即使用外部和内部循环，因为它们具有相同的“排列”但不同的数据类型。在处理过程中，您将它们转移到一个新的集合中。

so maybe a private method:

所以也许是一个私有方法：

    private void convertToSingleCollection()
    {


         while("column")
         {
            //convert the "column" to an arra


           for( "Row")
           {
            //add to newCollection here
           }

          //remove the processed column from CollectionOFcollection
         } 
    }
    //call the above method in your constructor


    public iterator<T> Iterator()
    {
       newCollection.iterator();
    }

    public boolean hasNext()
    {
       return Iterator().hasNext()
    }

    public T next()
    {
       if(!hasNext())
       {
        //exception message or message
       }
       else
           //return "next"
    }

end

结尾

I hope this helps. There should be other ways to solve it i guess.

我希望这有帮助。我想应该有其他方法来解决它。

回答by Jose Diaz

First, take a look at the implementation of the iterator in java.util.LinkedList

首先看一下java.util.LinkedList中迭代器的实现

http://www.docjar.com/html/api/java/util/LinkedList.java.html

http://www.docjar.com/html/api/java/util/LinkedList.java.html

From there your task is easy just implement a single iterator that takes into account the fact that it is iterating over collections.

从那里您的任务很容易，只需实现一个迭代器，该迭代器考虑到它正在迭代集合的事实。

Regards.

问候。