C++ SkipList简单实现

SkipList.h：

#pragma once #include  
     struct SkipListNode { 
    SkipListNode(int data, int level); int m_data; std::vector<SkipListNode*> m_forward; }; class SkipList { 
    public: SkipList(); ~SkipList(); public: bool Find(int data); bool Insert(int data); bool Remove(int data); public: void Print(); private: void FirstInsert(int data); bool IsEmpty(); private: SkipListNode* m_pHead; int m_count; int m_level; }; 

SkipList.cpp

#include "SkipList.h" #include  
     #include  
     int GetRandLevel() { 
    int destLevel = 1; while (1 == rand() % 2) ++destLevel; return destLevel; } SkipListNode::SkipListNode(int data, int level) : m_data(data) , m_forward(level) { 
    } SkipList::SkipList() : m_pHead(nullptr) , m_count(0) , m_level(1) { 
    auto pHead = new SkipListNode(INT_MIN, m_level); m_pHead = pHead; } SkipList::~SkipList() { 
    auto* pNode = m_pHead; while (pNode != nullptr) { 
    auto pNextNode = pNode->m_forward[0]; delete pNode; pNode = pNextNode; } } bool SkipList::Find(int data) { 
    if (IsEmpty()) return false; auto pCurNode = m_pHead; for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    // 判断是否已经走到该层最后一个元素 if (nullptr == pCurNode->m_forward[curLevel]) continue; while (pCurNode->m_forward[curLevel]->m_data < data) { 
    pCurNode = pCurNode->m_forward[curLevel]; // 判断是否已经走到该层最后一个元素 if (nullptr == pCurNode->m_forward[curLevel]) break; } } if (data == pCurNode->m_forward[0]->m_data) { 
    return true; } return false; } void SkipList::Print() { 
    auto* pCurNode = m_pHead; while (pCurNode != nullptr) { 
    std::cout << pCurNode->m_data << "(" << int(pCurNode->m_forward.size()) << ")" << " "; pCurNode = pCurNode->m_forward[0]; } std::cout << std::endl; } void SkipList::FirstInsert(int data) { 
    int destLevel = GetRandLevel(); if (destLevel > m_level) { 
    destLevel = ++m_level; // 更新最高层数, 只增加一层 m_pHead->m_forward.resize(m_level); } auto pNewNode = new SkipListNode(data, destLevel); for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    m_pHead->m_forward[curLevel] = pNewNode; pNewNode->m_forward[curLevel] = nullptr; } ++m_count; return; } bool SkipList::IsEmpty() { 
    return 0 == m_count; } bool SkipList::Insert(int data) { 
    if (0 == m_count) // 首次插入 { 
    FirstInsert(data); return true; } auto pNode = m_pHead; // 需要更新下一跳指针的节点 std::vector<SkipListNode*> updates(m_level); for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    if (nullptr == pNode->m_forward[curLevel]) { 
    updates[curLevel] = pNode; continue; } while (pNode->m_forward[curLevel]->m_data < data) { 
    pNode = pNode->m_forward[curLevel]; if (nullptr == pNode->m_forward[curLevel]) break; } updates[curLevel] = pNode; } if ((pNode->m_forward[0] != nullptr) && (data == pNode->m_forward[0]->m_data)) { 
    // 已有节点处理 return false; } int destLevel = GetRandLevel(); if (destLevel > m_level) { 
    destLevel = ++m_level; // 更新最高层数 updates.resize(m_level); updates[m_level - 1] = m_pHead; m_pHead->m_forward.resize(m_level); } // 待插入元素 auto* pNewNode = new SkipListNode(data, destLevel); // 从插入节点的最高层开始向下处理，对插入节点最高层之上的指针无影响 for (int curLevel = destLevel - 1; curLevel >= 0; --curLevel) { 
    pNewNode->m_forward[curLevel] = updates[curLevel]->m_forward[curLevel]; updates[curLevel]->m_forward[curLevel] = pNewNode; } // 增加元素个数 ++m_count; return true; } bool SkipList::Remove(int data) { 
    auto* pCurNode = m_pHead; if (IsEmpty()) return false; // 需要更新下一跳指针的节点 std::vector<SkipListNode*> updates(m_level); for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    if (nullptr == pCurNode->m_forward[curLevel]) { 
    updates[curLevel] = pCurNode; continue; } while (pCurNode->m_forward[curLevel]->m_data < data) { 
    pCurNode = pCurNode->m_forward[curLevel]; if (nullptr == pCurNode->m_forward[curLevel]) break; } updates[curLevel] = pCurNode; } if (data != pCurNode->m_forward[0]->m_data) { 
    // 没有该节点 return false; } // 待删除元素 auto* pRmoveNode = pCurNode->m_forward[0]; // 将原来指向待删除元素的指针指向待删除元素的下一个元素 for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    if (updates[curLevel]->m_forward[curLevel] == pRmoveNode) updates[curLevel]->m_forward[curLevel] = pRmoveNode->m_forward[curLevel]; } // 修改层高，将为空的层删除 for (int curLevel = m_level - 1; curLevel >= 0; --curLevel) { 
    if (nullptr == m_pHead->m_forward[curLevel]) --m_level; } m_pHead->m_forward.resize(m_level + 1); // 元素个数-1 --m_count; } 

main.cpp:

#include  
     #include  
     #include  
     int main() { 
    SkipList skipList; std::vector<int> datas; datas.reserve(100); for (int idx = 0; idx < 100; ++idx)datas.push_back(idx); std::random_shuffle(datas.begin(), datas.end()); for (auto& data : datas) skipList.Insert(data); skipList.Print(); std::cout << "--------------------------------" << std::endl; for (auto& data : datas) skipList.Remove(data); skipList.Print(); return 0; }