Java:为什么迭代器不可复制

发布于 2024-09-25 13:30:39 字数 735 浏览 7 评论 0原文

我认为 Iterator.copy() 将是一个非常方便的函数。您可以以更好的方式实现迭代器过滤器。

例如,Google 的 Java Collection 中 filter(和类似)函数使用 UnmodifyingIterator(它只是一个没有 IteratorIterator)的唯一原因code>remove) 是因为您无法实现这样的过滤器 Iterator,否则无法在某个时刻复制它。 (实际上,这在当前接口中是不可能的;请您自己尝试一下。)

另一个优点是您可以在 for-each-循环中使用迭代器:因为可复制迭代器也将自动成为可迭代器。另请参阅问题。目前,不允许这样做的主要设计原因是因为实现了 IterableIteratorIterator 。迭代器(){返回这个; } 将使迭代器无效。通过使用 copy 函数,它就像 Iterator一样简单。迭代器() { 返回复制(); } 并且它不会使原始迭代器无效。因此,没有理由不再允许这样做。

有什么理由吗?只是为了让实施变得更简单吗?

I would think that Iterator.copy() would be quite a handy function. You could implement iterator filters in a much better way.

For example, the only reason in Googles Java Collection for the filter (and similar) functions to use UnmodifiableIterator (which is just an Iterator without remove) is because you cannot implement such a filter Iterator otherwise without being able to copy it at some point. (Really, that is not possible with the current interface; try yourself.)

Another advantage would be that you could use an iterator in a for-each-loop: Because a copy-able iterator would automatically also be iterable. See also this question. Right now, the main design reason to not allow this is because an Iterator which implements Iterable and Iterator<T> iterator() { return this; } would invalidate the iterator. By having a copy function, it is as simple as Iterator<T> iterator() { return copy(); } and it would not invalidate the original iterator. Thus there is no reason anymore to not allow this.

Is there any reason? Just to make it less complicated to implement it?

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(11

一世旳自豪 2024-10-02 13:30:39

尽管通常是这样,但迭代器理论上不必链接到集合。例如,输入流上的复制方法很难实现,并且很容易导致模糊的内存问题。

Although they usually are, Iterators do not theoretically have to be linked to a collection. The copy method over an input stream, for instance, would be difficult to implement, and would very easily cause obscure memory problems.

老街孤人 2024-10-02 13:30:39

Iterator 表示来自源的中的位置(Java 中的 Iterable),并且不保证可以复制甚至访问流的源。

例如,当字节从网络服务器流式传输时,您可能会迭代它们,在这种情况下,不可能告诉网络服务器中流“从这个位置开始,我希望您向我发送相同的字节两次,但是按照我的要求异步进行。”

流只有一个,无法复制。

您通常看到的大多数 Iterator 都位于 Collection 上,这一事实是偶然的。

An Iterator represents a position in a stream from a source (Iterable in java speak), and there is no guarantee that it is possible to copy or even access the source of the stream.

For example, you could be iterating over bytes as they are streamed from a webserver, in which case it would be impossible to tell the webserver mid-stream to "From this position on, i want you to send me the same bytes twice, but asynchronously as i request them."

There is only the one stream, and it can't be copied.

The fact that most of the Iterators you usually see are over a Collection, is incidental.

陈年往事 2024-10-02 13:30:39

Google 拥有 UnmodifyingIterator 的唯一原因是基本上保证其集合的不变性。他们确保您无法更改集合的内部状态。

不要忘记迭代器的最初想法是它是遍历过程中指向当前元素的指针,并且它管理到下一个/上一个遍历(对于双向链接迭代器来说是反向的)到它的下一个/上一个元素。

迭代器不可克隆并没有实际原因,很简单,克隆迭代器仍然意味着让迭代器指向相同的集合元素(除了它现在位于两个不同的地址空间中)。除非您希望克隆的迭代器指向另一个集合,否则没有意义。

The only reason why Google have UnmodifiableIterator is to basically guarantee immutability in their collections. They're making sure that there's no way that you can change the internal state of a collection.

Don't forget that the original idea for an iterator is that it's a pointer to the current element during transveral, and it manages to next/previous transversal (for reverse for doubly-linked iterators) to the element next/previous to it.

There is no actual reason why iterators aren't Cloneable, quite simply, cloning an iterator will still mean having an iterator pointing to the same collection elements (except it now lives in 2 different address space). Unless you want the cloned iterator to point to another collections, there is no point.

孤独难免 2024-10-02 13:30:39

我想要这样的东西,这就是我所做的(基于 Lambdaj 上完成的一些工作)。
主要缺陷是这个迭代器基本上会用迭代器的所有假定内容填充一个列表,这可能会占用大量内存。

为什么我使用 List,因为有时 Iterator 会按特定顺序进行迭代,因此“子Iterators”必须执行相同的操作(并且 ListIterator< /code> 在这里确实对我有帮助)。

public class IterableIterator<T> implements Iterable<T>, Iterator<T> {
    //The content of the given iterator. Will be filled by its iterators.
    private final List<T> iteratorContent = new ArrayList<T>();
    private final Iterator<T> originalIterator;
    private final Iterator<T> innerIterator;

    public IterableIterator(Iterator<T> originalIterator) {
        this(originalIterator, false);
    }

    public IterableIterator(Iterator<T> originalIterator, boolean cache) {
        if (originalIterator == null) {
            throw new IllegalArgumentException("Parameter can't be null");
        }

        this.originalIterator = originalIterator;
        if (cache) {
            while (originalIterator.hasNext()) {
                iteratorContent.add(originalIterator.next());
            }
        }

        innerIterator = iterator();
    }

    @Override
    public Iterator<T> iterator() {
        return new IteratorIterator();
    }

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

    @Override
    public T next() {
        return innerIterator.next();
    }

    @Override
    public void remove() {
        innerIterator.remove();
    }

    private class IteratorIterator implements Iterator<T> {
        private ListIterator<T> innerIterator = iteratorContent.listIterator();

        @Override
        public boolean hasNext() {
            return innerIterator.hasNext() || originalIterator.hasNext();
        }

        @Override
        public T next() {
            if (!innerIterator.hasNext() && originalIterator.hasNext()) {
                T item;
                synchronized (originalIterator) {
                    item = originalIterator.next();
                    iteratorContent.add(item);
                }
                innerIterator = iteratorContent.listIterator(innerIterator.nextIndex());
            }
            if (innerIterator.hasNext()) {
                try {
                    return innerIterator.next();
                } catch (ConcurrentModificationException e) {
                    //Quick and dirty solution if you have a concurrent modification.
                    //It can't happen from the outside, so you can easily suppose that another originalIterator
                    //from this class has been called and had added elements to the list.
                    //Best thing to do, reset the originalIterator to the current position.
                    innerIterator = iteratorContent.listIterator(innerIterator.nextIndex());
                    return innerIterator.next();
                }
            }

            throw new NoSuchElementException();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

I wanted something like this, here is what I've done (based on some work done on Lambdaj).
The main flaw is that this Iterator will basically fill a List with all the supposed content of the Iterator which could be really heavy in memory.

Why did I used a List, because sometimes an Iterator iterates in a specific order, so the "sub-Iterators" must do the same (and the ListIterator really helps me here).

public class IterableIterator<T> implements Iterable<T>, Iterator<T> {
    //The content of the given iterator. Will be filled by its iterators.
    private final List<T> iteratorContent = new ArrayList<T>();
    private final Iterator<T> originalIterator;
    private final Iterator<T> innerIterator;

    public IterableIterator(Iterator<T> originalIterator) {
        this(originalIterator, false);
    }

    public IterableIterator(Iterator<T> originalIterator, boolean cache) {
        if (originalIterator == null) {
            throw new IllegalArgumentException("Parameter can't be null");
        }

        this.originalIterator = originalIterator;
        if (cache) {
            while (originalIterator.hasNext()) {
                iteratorContent.add(originalIterator.next());
            }
        }

        innerIterator = iterator();
    }

    @Override
    public Iterator<T> iterator() {
        return new IteratorIterator();
    }

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

    @Override
    public T next() {
        return innerIterator.next();
    }

    @Override
    public void remove() {
        innerIterator.remove();
    }

    private class IteratorIterator implements Iterator<T> {
        private ListIterator<T> innerIterator = iteratorContent.listIterator();

        @Override
        public boolean hasNext() {
            return innerIterator.hasNext() || originalIterator.hasNext();
        }

        @Override
        public T next() {
            if (!innerIterator.hasNext() && originalIterator.hasNext()) {
                T item;
                synchronized (originalIterator) {
                    item = originalIterator.next();
                    iteratorContent.add(item);
                }
                innerIterator = iteratorContent.listIterator(innerIterator.nextIndex());
            }
            if (innerIterator.hasNext()) {
                try {
                    return innerIterator.next();
                } catch (ConcurrentModificationException e) {
                    //Quick and dirty solution if you have a concurrent modification.
                    //It can't happen from the outside, so you can easily suppose that another originalIterator
                    //from this class has been called and had added elements to the list.
                    //Best thing to do, reset the originalIterator to the current position.
                    innerIterator = iteratorContent.listIterator(innerIterator.nextIndex());
                    return innerIterator.next();
                }
            }

            throw new NoSuchElementException();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}
独木成林 2024-10-02 13:30:39

作为为什么要复制迭代器的简单示例,请考虑以下代码,该代码在单个数组中查找第一对匹配值。

for(int i=0;i<size;i++)
{
  x = array[i];

  for(int j=i+1;j<size;j++)
  {
    y = array[j];
    if(x == y)
    {
      doSomething();
      break;
    }
}

注意“j=i+1”。这就是迭代器遇到问题的地方。哦,好吧,解决方法在 Java 中似乎相当常见......

As a simplistic example of why you would want to copy an iterator, consider the following code which finds the first pair of matching values in a single array.

for(int i=0;i<size;i++)
{
  x = array[i];

  for(int j=i+1;j<size;j++)
  {
    y = array[j];
    if(x == y)
    {
      doSomething();
      break;
    }
}

Note the "j=i+1". That's where you run into problems with an iterator. Oh well, workarounds are fairly common in Java it seems...

一紙繁鸢 2024-10-02 13:30:39

您始终可以实现自己的实现 IteratorCopyableIterator。然后你可以做

new CopyableItereator(collection);

类将像这样

class CopyableIterator implements Iterator{
Iterator iterator;
Collection collection;
int index=0;

public CopyableIterator(Collection collection){
super();
this.collection = collection;
this.iterator = collection.iterator();
}

public CopyableIterator(Collection collection, int index){
super();
this.collection =collection;
this.iterator = collection.iterator();
this.advanceToIndex(iterator,index); //This function just moves the iterator till the index.
this.index=index;
}

//Override the functions of Iterator here returning iterator.function()

@Override
public Object next(){
index++;
return this.iterator.next();
}

public CopyableIterator copy(){
return new CopyableIterator(this.collection,this.index)

}

}

免责声明:这大致是类。它还没有经过测试。

You can always implement your own CopyableIterator that implements Iterator. And then you can do

new CopyableItereator(collection);

The class would be like this

class CopyableIterator implements Iterator{
Iterator iterator;
Collection collection;
int index=0;

public CopyableIterator(Collection collection){
super();
this.collection = collection;
this.iterator = collection.iterator();
}

public CopyableIterator(Collection collection, int index){
super();
this.collection =collection;
this.iterator = collection.iterator();
this.advanceToIndex(iterator,index); //This function just moves the iterator till the index.
this.index=index;
}

//Override the functions of Iterator here returning iterator.function()

@Override
public Object next(){
index++;
return this.iterator.next();
}

public CopyableIterator copy(){
return new CopyableIterator(this.collection,this.index)

}

}

Disclaimer: This is roughly the class. It has not been tested.

赠我空喜 2024-10-02 13:30:39

复制 Iterator 到底意味着什么?您的意思是它应该能够像它自己一样创建一个新的迭代器,除了从头开始?这是 Iterable 的职责...重复该功能是没有意义的,特别是考虑到迭代器的有状态性质...它只会让事情变得混乱。

您会期望发生什么

Iterator<Foo> iter = someIterable.iterator();
iter.next();
iter.next();
for (Foo foo : iter) {
  ...
}

如果您写道:您希望 for 循环迭代迭代器将返回的每个项目,还是除了前两个之外的每个项目, ?您是否希望 for 循环完成后迭代器为空?

What exactly would it mean to copy an Iterator? Do you mean than it should be able to create a new Iterator just like itself except starting at the beginning? That's the responsibility of an Iterable... it doesn't make sense to duplicate that functionality, especially given the stateful nature of iterators... it would just confuse things.

What would you expect to happen if you wrote:

Iterator<Foo> iter = someIterable.iterator();
iter.next();
iter.next();
for (Foo foo : iter) {
  ...
}

Would you expect the for loop to iterate over every item the iterator would return, or every one except the first two? Would you expect the iterator to be empty after the for loop completes?

半暖夏伤 2024-10-02 13:30:39

有什么理由吗?只是为了让实现变得更简单?

设计和实现支持复制操作的迭代器包装类会很简单。但我不确定它是否普遍有用,尤其是因为在一般情况下这将是一项昂贵的操作。仅此一点就足以让 Java 设计者不想将 copy() 添加到 Iterator 接口中。

FOLLOWUP

这就是我正在考虑的事情:

public class CopyableIterator<T> implements Iterator<T> {
    private Iterator<T> it;
    private List<T> copy = new ArrayList<T>();
    private int pos;
    public CopyableIterator(Iterator<T> it) {
        while (it.hasNext()) {
            copy.append(it.next());
        }
        this.it = copy.iterator();
    }
    public T next() {
        T res = next();
        pos++;
        return res;
    }
    public boolean hasNext() {
        return it.hasNext();
    }
    public Iterator<T> copy() {
        return copy.sublist(pos, copy.size()).iterator();
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

推理是这样的:

  • 如果我包装一个不透明的 Iterator,那么 我复制它的方法是使用 next()hasNext() 读取它,并从中构造副本 Iterator

  • 但我必须在开始使用原始迭代器之前执行此操作。

  • 执行此操作的简单方法是在开始使用迭代器之前制作迭代器内容的副本。 (这可以通过惰性增量复制来完成,但实现可能会变得非常复杂......尤其是当您考虑复制复制的迭代器时。)

另一个答案中提出的方法仅限于普通集合迭代器。如果您有一个包装的迭代器,或者来自其他源的迭代器(例如)没有实现Iterable,那么您就完蛋了。

即使有这个前提条件,上面的方法也不会返回迭代器的真实副本。相反,它为底层集合返回一个新的迭代器。这是一个重要的区别。除非您实际复制迭代的元素引用,否则不能保证迭代器将返回相同的序列。查看 Concurrent... 集合类型的迭代器的记录行为。

Is there any reason? Just to make it less complicated to implement it?

It would be simple to design and implement an Iterator wrapper class that supported a copy operation. I'm not sure it would be generally useful though, not least because in the general case it would be an expensive operation. This alone would be sufficient reason for the Java designers to not want to add copy() to the Iterator interface.

FOLLOWUP

This is the kind of thing I'm thinking of:

public class CopyableIterator<T> implements Iterator<T> {
    private Iterator<T> it;
    private List<T> copy = new ArrayList<T>();
    private int pos;
    public CopyableIterator(Iterator<T> it) {
        while (it.hasNext()) {
            copy.append(it.next());
        }
        this.it = copy.iterator();
    }
    public T next() {
        T res = next();
        pos++;
        return res;
    }
    public boolean hasNext() {
        return it.hasNext();
    }
    public Iterator<T> copy() {
        return copy.sublist(pos, copy.size()).iterator();
    }
    public void remove() {
        throw new UnsupportedOperationException();
    }
}

The reasoning is this:

  • If I'm wrapping an opaque Iterator, then the only way I can copy it is by reading it using next() and hasNext() and constructing the copy Iterator from that.

  • But I have to do that before I start using the original iterator.

  • The simple way to do that is to make that copy of the iterator's content before I start using it. (It could possibly be done with a lazy incremental copying, but the implementation could get very complicated ... especially when you consider copying copied iterators.)

The method proposed in the other answer is limited to plain collection iterators. If you have a wrapped iterator, or an iterator from some other source that (for instance) doesn't implement Iterable, then you are toasted.

And even with that precondition, the method above doesn't return a true copy of the iterator. Rather, it returns a new iterator for the underlying collection. That is an important distinction. Unless you actually copy the iterated element references, there's no guarantee that the iterators will return the same sequence. Look at the documented behaviour of the iterators for the Concurrent... collection types.

葮薆情 2024-10-02 13:30:39

ILMTitan 和 Christoffer Hammarström 暗示但没有具体说明复制流可能是不可能的,因为它要求流元素具有复制函数的实现,以便保存可复制迭代器所需的状态。意识到元素可能是可变的(或引用动态值),并且它们可能引用需要自定义复制功能的其他结构和语义。

因此,可复制迭代器与可复制流元素不正交,因此这就是可复制迭代器通常不可能的原因。

另一个更模糊的原因是复制行为对内存分配和释放有副作用。即使流元素的复制函数也可能有其他副作用。

另一个原因是编译为汇编语言时可能无法进行某些低级优化。

ILMTitan's and Christoffer Hammarström's imply but don't state concretely that copying the stream may not be possible because it requires that the stream elements have an implementation of a copy function, in order to save the state that a copyable iterator would require. Realize that elements could be mutable (or reference dynamic values) and they may reference other structures and semantics which require a customized copy function.

Thus copyable iterators is not orthogonal to copyable stream elements, so this is why copyable iterators are not possible in general.

Another more obscure reason is that the act of copying has side-effects on memory allocation and deallocation. Even the stream elements' copy function(s) might have other side effects.

Another reason is that some low-level optimizations might not be possible when compiling to assembly language.

皓月长歌 2024-10-02 13:30:39

创建迭代器是为了使用该集合支持的数据一次遍历集合中的所有对象。

Iterator 几乎总是使用私有内部类来实现,该内部类可能使用属于外部类一部分的状态。因此,如果不编写自己的 Collection (或其他内容),您就无法真正修改 Iterator 的行为。

复制迭代器可能会导致许多新问题,例如与后备集合不同步。

Iterators were created to step through all the objects in a collection one at a time, using data backed by said collection.

Iterator<T> is almost always implemented using a private inner class that may use state that is part of the outer class. Thus, you can't really modify an Iterator's behavior without writing your own Collection (or whatever) as well.

Copying the Iterator could cause a host of new problems, such as falling out of sync with the backing collection.

一身仙ぐ女味 2024-10-02 13:30:39

可能无法复制迭代器 - 它基本上没有意义。对于某些人来说,这从 Iterator 接口中显而易见,但让我们用一个具体的示例来演示它。事实上,让我们用一个关于具体的例子来演示。

bar withpieces ofcrete

这是混凝土棒上的混凝土迭代器的图片。在我们的例子中,迭代意味着使用撬棍将其从撬棍上折断。现在,请注意:

  • 该栏不是片段的集合(尽管其中一些有缺陷):我们在迭代时创建片段。
  • 通过迭代器(next())进行迭代的结果永远不可能是条形图另一次迭代的结果。结果已从中删除。
  • 迭代可能会产生不同的片段,具体取决于天气、施加的力的大小,或者可能是某种热噪声(想想:随机性)。
  • 通过迭代器(next())进行迭代的结果永远不可能是条形图另一次迭代的结果 - 因为精确迭代结果的概率空间是连续的,并且没有特定的结果片段具有连续性。非零概率测度。

上述任何一个都应该说服你不要尝试“复制迭代器”,那是愚蠢的......

You can't possibly copy an iterator - it's basically meaningless. For some, this is obvious from the Iterator interface, but let's demonstrate it with a concrete example. In fact, let's demonstrate with an example about concrete.

bar with pieces of concrete

This is a picture of a concrete iterator over a bar of concrete. Iteration in our case means applying the crow bar to break a piece off of the bar. Now, note that:

  • The bar is not a collection of pieces (though some of it has faults): We're creating pieces as we iterate.
  • The result of an iteration via the iterator (of next()) can never be the result of another iteration of the bar. The result has been removed from it.
  • The iteration may produce a different piece depending on the weather, on the amount of force you apply, or maybe on some kind of thermal noise (think: randomness).
  • The result of an iteration via the iterator (of next()) can never be the result of another iteration of the bar - as the probability space of exact iteration result is continuous, and no specific resulting piece has a non-zero probability measure.

Any of the above should convince you not to try to "copy the iterator", that's silly...

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文