c++如何实现跳表（skiplist）

二分查找底层依赖的是数组随机访问的特性，所以只能用数组来实现。如果数据存储在链表中，就真的没法用二分查找算法了吗？实际上，只需要对链表稍加改造，就可以支持类似“二分”的查找算法。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O，优于普通队列的O。性能上和红黑树，AVL树不相上下，但跳表的原理非常简单，目前Redis和LevelDB中都有用到。下面实现过程主要是简单实现跳表的过程，不是多线程安全的，LevelDB实现的跳表支持多线程安全，用了std::atomic原子操作，本文主要是为了理解跳表的原理，所以采用最简单的实现。