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

Question

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

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

在我在网上看到的解释中，跳过列表的头部和尾部有无穷大/负无穷大键，但它们都与数字键一起使用。

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

但是，如何找到最小/最大类型的值作为头/尾指针？是否有类似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);
}

然后稍后...：

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;
}

PS：我使用referenceItem上列表的属性来引用下列表以便SkipListItem于构造，这就是为什么 thisgetItem返回一个SkipListItem. 但是，我不认为这是解决它的最佳方法，这正是我所追求的。