Infinity/-infinity 用于未知类型的跳过列表插入？

Question

我正在实施一个跳过列表，例如：

template<typename Key, typename Value> class SkipList {...}

我在网上看到的解释是，skip list的头部和尾部有infinity/negative个无限键，但是它们都是和数字键一起使用的。

我可以假设 < 和 == 运算符可用于键，所以我不必担心 string < string

但是，如何找到 smallest/largest 类型的值作为 head/tail 指针？是否有类似 INT_MAX 或 INT_MIN 但适用于任何类型的东西？

Answer 1

您可以使用两个属性 private SkipListItem<K, E> negInfinity; 和 private SkipListItem<K, E> posInfinity;，稍后将 SkipListItems 与它们进行比较。

我是这样处理的：

private SkipListItem<K, E> negInfinity;
private SkipListItem<K, E> posInfinity;

public SkipListDictionary(K[] keys, E[] elements) {

    this.randomGenerator = new Random();
    this.negInfinity = new SkipListItem<K, E>();
    this.posInfinity = new SkipListItem<K, E>();

    this.constructSkipList(keys, elements);
}

然后稍后...:[=18=]

private SkipListItem<K, E> searchKey(K key) {

    SkipListItem<K, E> currentElement = this.lastListStart;

    while(currentElement.lower != null) {

        currentElement = currentElement.lower;

        while(currentElement.next != null && currentElement.next.getItem() != posInfinity &&
                currentElement.next.getKey().compareTo(key) < 1) {

            currentElement = currentElement.next;
        }
    }

    return  currentElement;
}

P.S.: 我使用属性 referenceItem 作为上层列表来引用下层的 SkipListItem 以便于构建，这就是为什么有这个 getItem 其中 returns 个 SkipListItem。然而，我不认为这是解决问题的最佳方法，这正是我所追求的。

Infinity/-infinity 用于未知类型的跳过列表插入？

Infinity/-infinity for skip list insertion with unknown type?

default

insert

max

min

skip-lists