java - 如何防止迭代器列表的突变?
问题描述
我想避免tests
其他人对迭代器输入列表的突变。我只希望其他人在tests
.
这如何在 Java 中实现?
这是一个显示突变对tests
. 这两部分都对输入进行排序。但是第二部分没有什么要排序的,因为第一部分的突变将迭代器迭代到最后。
您可以在此处在线运行以下示例: https ://onlinegdb.com/NC4WzLzmt
import java.util.*;
public class ImmutableExample {
public static void main(String[] args) {
System.out.println("sort on demand");
List<Iterator<Integer>> mutableTests = Arrays.asList(
Arrays.asList(1, 2).iterator(),
Arrays.asList(0).iterator(),
Collections.emptyIterator()
);
List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests);
MergingIterator mergingIterator = new MergingIterator(tests);
while (mergingIterator.hasNext()) {
System.out.println(mergingIterator.next());
}
System.out.println("sort all at once");
/* uncomment the following will see the same result:*/
// tests = Arrays.asList(
// Arrays.asList(1, 2).iterator(),
// Arrays.asList(0).iterator(),
// Collections.emptyIterator()
// );
MergeKSortedIterators sol = new MergeKSortedIterators();
Iterable<Integer> result = sol.mergeKSortedIterators(tests);
for (Integer num : result) {
System.out.println(num);
}
}
}
class PeekingIterator implements Iterator<Integer>, Comparable<PeekingIterator> {
Iterator<Integer> iterator;
Integer peekedElement;
boolean hasPeeked;
public PeekingIterator(Iterator<Integer> iterator) {
this.iterator = iterator;
}
public boolean hasNext() {
return hasPeeked || iterator.hasNext();
}
public Integer next() {
int nextElem = hasPeeked ? peekedElement : iterator.next();
hasPeeked = false;
return nextElem;
}
public Integer peek() {
peekedElement = hasPeeked ? peekedElement : iterator.next();
hasPeeked = true;
return peekedElement;
}
@Override
public int compareTo(PeekingIterator that) {
return this.peek() - that.peek();
}
}
class MergingIterator implements Iterator<Integer> {
Queue<PeekingIterator> minHeap;
public MergingIterator(List<Iterator<Integer>> iterators) {
// minHeap = new PriorityQueue<>((x, y) -> x.peek().compareTo(y.peek()));
minHeap = new PriorityQueue<>();
for (Iterator<Integer> iterator : iterators) {
if (iterator.hasNext()) {
minHeap.offer(new PeekingIterator(iterator));
}
}
}
public boolean hasNext() {
return !minHeap.isEmpty();
}
public Integer next() {
PeekingIterator nextIter = minHeap.poll();
Integer next = nextIter.next();
if (nextIter.hasNext()) {
minHeap.offer(nextIter);
}
return next;
}
}
class MergeKSortedIterators {
public Iterable<Integer> mergeKSortedIterators(List<Iterator<Integer>> iteratorList) {
List<Integer> result = new ArrayList<>();
if (iteratorList.isEmpty()) {
return result;
}
PriorityQueue<PeekingIterator> pq = new PriorityQueue<>();
for (Iterator<Integer> iterator : iteratorList) {
if (iterator.hasNext()) {
pq.add(new PeekingIterator(iterator));
}
}
while (!pq.isEmpty()) {
PeekingIterator curr = pq.poll();
// result.add(curr.peek());
// cannot use this one as hasNext() checks on `hasPeeked`
result.add(curr.next());
if (curr.hasNext()) {
pq.add(curr);
}
}
return result;
}
}
解决方案
这个问题似乎是基于一个误解......或两个。
如何防止迭代器列表的突变?
您需要区分列表的可变性和列表中项目的可变性。我想你实际上是在问后者。(因此,该列表与问题并不真正相关。正如我们将看到的。)
我想避免其他人对迭代器测试的输入列表进行突变。
同样,您似乎在询问列表,但我认为您实际上是在询问迭代器。
我只希望其他人在测试的深层副本上运行。
这意味着您希望迭代器是不可变的。
这是问题所在:
An
Iterator
是一个固有的有状态/可变对象。next()
实际上,如果不改变迭代器对象,就无法实现。Iterator
对象通常不可深度复制。它们通常不支持clone()
或公共构造函数,并且它们通常不实现Serializable
. (事实上,如果它们是可序列化的,那么序列化/反序列化的语义就会有问题。)
因此,基本上,您对不可变迭代器列表或(以某种方式)产生迭代器深层副本的列表的想法是不切实际的。
你评论说:
所以
List<Iterator<Integer>> tests = Collections.unmodifiableList(mutableTests);
不能产生一个不可修改的列表List<Iterator<Integer>>
?
嗯,是的,它可以。但这并不能解决问题。您需要一个不可修改的迭代器列表,而不是一个不可修改的迭代器列表。
可能的解决方案:
您可以为每次测试运行从其基本集合中重新创建迭代器列表。
使用
Iterable
而不是Iterator
. 您使用的集合类型都是 implementIterable
,第三个迭代器可以从一个空列表中创建。List<Iterable<Integer>> tests = Arrays.asList( Arrays.asList(1, 2), Arrays.asList(0), Collections.emptyList() ); // to use them ... for (Iterable<Integer> iterable : tests) { Iterator<Integer> iterator = iterable.iterator(); // etc ... }
如果您的迭代器无法重新创建(例如,如果您正在迭代一个无法创建或“重绕”的源),您可以想象实现一个缓存迭代器包装器,该包装器可以记住迭代序列中的所有元素,并且可以重置到序列的开头,或者生成一个新的迭代器来重放序列。(但这在这里有点矫枉过正。)
推荐阅读
- html - 我怎样才能使这个导航栏更薄并且背景颜色透明
- validation - 如何使用 ValidatedNec 累积错误?
- python - 如何在不复制的情况下在多个进程中使用大型数据集?
- design-patterns - DAO 方法应该接收数据对象作为参数还是仅接收其内容?
- java - 使用 JAXB 对对象中的 xml 属性进行分组
- amazon-web-services - 如何为每个 Amazon EC2 实例创建自定义报告
- vue.js - 重构 if 语句。哪个更好,哪些应该改变?
- sql - Teradata/Sql_server 查询以合并特定条件的连续行
- node.js - mssql 函数不会在节点中停止
- regex - 如何分离macid和时间戳wlan地址uisng python