一般来说,没有好的方法可以强制队列中的对象占用连续的内存块。然而,对于特定情况,有一些技巧是适用的。
在高层次上,这些技术涉及使用字节数组,并将数据“序列化”到数组中和从数组中读取数据。如果您要存储非常简单的对象,这实际上非常有效。例如,如果您要存储一堆2D点+权重,则可以简单地编写权重、x坐标、y坐标的字节等效值。
当然,在此时分配实例时出现了问题。您可以通过使用回调来避免这种情况。
请注意,即使在存储的对象本身很复杂的情况下,使用类似于此的技术,其中您保留一个用于权重的数组和一个用于实际对象的引用的单独数组,也可以避免直到绝对必要时才跟随对象引用。
回到存储简单不可变值类型的方法,这里是一个不完整的草图,显示您可以做什么:
abstract class LowLevelPQ<T> {
interface DataHandler<R, T> {
R handle(byte[] source, int startLoc);
}
LowLevelPQ(int entryByteSize) { ... }
abstract encode(T element, byte[] target, int startLoc);
abstract T decode(byte[] source, int startLoc);
abstract int compare(byte[] data, int startLoc1, int startLoc2);
abstract <R> R peek(DataHandler<R, T> handler) { ... }
abstract <R> R pop(DataHandler<R, T> handler) { ... }
}
class WeightedPoint {
WeightedPoint(int weight, double x, double y) { ... }
double weight() { ... }
double x() { ... }
...
}
class WeightedPointPQ extends LowLevelPQ<WeightedPoint> {
WeightedPointPQ() {
super(4 + 8 + 8);
}
int compare(byte[] data, int startLoc1, int startLoc2) {
for (int i = 0; i < 4; ++i) {
int v1 = 0xFF & (int) data[startLoc1];
int v2 = 0xFF & (int) data[startLoc2];
if (v1 < v2) { return -1; }
if (v1 > v2) { return 1; }
}
return 0;
}
...
}