参见英文答案 >
Does java has multiset data structure like the one in c++ STL?6个
我想要一个包含无序,可重复项目的集合.
在Java中,Set是不可重复的,List是有序的,这不是我想要的.
我想要一个包含无序,可重复项目的集合.
在Java中,Set是不可重复的,List是有序的,这不是我想要的.
似乎Pool是一个合适的集合,但它在Java中不存在.
界面应如下：
public interface Pool<T> {
void set(T item);
T get();
}
它存在于某个地方吗？
补充：
我意识到我错误地表达了自己的想法.事实上,我希望有这样的界面：
public interface Pool<T> {
void put(T item);
T randomremove();
}
也就是说,我希望每次都能得到一个项目.我怎样才能实现它？
解决方法
您可以实施您的Pool< T>包装List< T>的功能.
public class ListPool<T> implements Pool<T> {
private List<T> list = ArrayList<>();
public void put(T t) {
list.append(t);
}
public T randomremove() {
return list.remove(rand.nextInt(list.size()));
}
}
这不会特别有效,因为删除是标准List实现上的O(N).但是,有一个使用ArrayList的替代实现有点复杂,但提供了一个为O(1)的randomremove.我们的想法是将列表视为动态数组并自行管理“大小”.
像这样的东西：
public class FasterPool<T> implements Pool<T> {
private List<T> list = new ArrayList<>();
private int size = 0;
Random rand = new Random();
public void put(T t) {
if (size == list.size()) {
list.append(t);
} else {
list.set(size,t);
size++;
}
public T randomremove() {
int pos = rand.nextInt(size);
T result = list.get(pos);
if (pos < size - 1) {
list.set(pos,list.get(size - 1));
}
list.set(size - 1,null); // avoid memory leak ...
size--;
return result;
}
}
注意：当您尝试删除元素时,两个版本都不会处理池为空的情况.都没有编译或测试过.请相应地处理代码.
最后,如果您尝试使用未排序的集合类型来实现,那么您不太可能有效地删除随机元素.提示：删除集合的迭代器返回的第一个对于任何实际的集合数据结构都不是真正随机的.这也适用于(假设的)Bag实施.