插入跳过列表

Question

我正在开发自己的跳过列表模板类。以下是它的规格：Iterator类包含单个跳过列表的副本。头部和尾部迭代器总是空的，尾部迭代器的尾部值设置为TRUE。

class RandomHeight 
{ 
    public: 
    RandomHeight(int maxLvl, float prob); 
    ~RandomHeight() {} 
    int newLevel(void); 

    private: 
    int maxLevel; 
    float probability; 
}; 

RandomHeight::RandomHeight 
    (int maxLvl, float prob) 
{ 
    srand (time(NULL)); 
    maxLevel = maxLvl; 
    probability = prob; 
} 

int RandomHeight::newLevel(void) 
{ 
int tmpLvl = 1; 
    // Develop a random number between 1 and 
    // maxLvl (node height). 
    while ((((rand()%1000000)*1.0/1000000) < probability) && 
     (tmpLvl < maxLevel)) 
    tmpLvl++; 

    return tmpLvl; 
} 

template <typename Key_T, typename Mapped_T, size_t MaxLevel> class SkipList; 
template <typename Key, typename Obj> 
class Iterator 
{ 
    typedef std::pair<Key, Obj> ValueType; 
    template <typename Key1, typename Obj1, size_t MaxLevel1> friend class SkipList; 
    public: 
     // Iterator(const Iterator &); 
     //virtual Iterator& operator=(const Iterator &); 
     Iterator &operator++(); 
     Iterator operator++(int); 
     //virtual ValueType &operator*() const; 
     //virtual ValueType *operator->() const; 

     Iterator(Key, Obj, int,bool); 
     Iterator(int,bool); 
     ~Iterator(); 

     Key getKey(void) {return key;}; 
     Obj getObj(void) {return obj;}; 
     int getHgt(void) {return nodeHeight;}; 
    bool isTail(void) {return tail;}; 

    private: 
     int nodeHeight; 
     Key key; 
     Obj obj; 
    bool tail; // holds non null value 
    Iterator<Key,Obj>** fwdNodes; 
}; 


template <typename Key, typename Obj> 
Iterator<Key,Obj>::~Iterator() 
{ 
    delete [] fwdNodes; 
} 

template <typename Key, typename Obj> 
Iterator<Key,Obj>::Iterator(Key k,Obj o, int h,bool t = false) : nodeHeight (h) , key (k) , obj (o) , tail(t) 
{ 
    fwdNodes = new Iterator<Key,Obj>* [h+1]; 
    for (int x = 1; x <= nodeHeight; x++) 
     fwdNodes[x] = (Iterator<Key,Obj>*) NULL; 
} 

template <typename Key, typename Obj> 
Iterator<Key,Obj>::Iterator(int h,bool t = false) : nodeHeight (h) , key ((Key) NULL) , obj ((Obj) NULL) , tail(t) 
{ 
    fwdNodes = new Iterator<Key,Obj>* [h+1]; 
    for (int x = 1; x <= nodeHeight; x++) 
     fwdNodes[x] = (Iterator<Key,Obj>*) NULL; 
} 
template <typename Key_T, typename Mapped_T, size_t MaxLevel = 5> 
class SkipList 
{ 
    typedef std::pair<Key_T, Mapped_T> ValueType; 
public: 

    SkipList(); 
    ~SkipList(); 
    SkipList(const SkipList &); 
    SkipList &operator=(const SkipList &); 

    size_t size() const; 
    Iterator<Key_T,Mapped_T> begin(); 
    Iterator<Key_T,Mapped_T> end(); 
    //ConstIterator begin() const; 
    //ConstIterator end() const; 
    //virtual void clear(); 


    std::pair<Iterator<Key_T,Mapped_T>, bool> insert(const ValueType &); 
    template <typename IT_T> 
    void insert(IT_T range_beg, IT_T range_end); 

    void erase(Iterator<Key_T,Mapped_T> pos); 
    //virtual void erase(Iterator<Key_T,Mapped_T> range_beg, Iterator<Key_T,Mapped_T> range_end); 

private: 
    Iterator<Key_T,Mapped_T>* head; 
    Iterator<Key_T,Mapped_T>* tail; 
    float probability; 
    size_t maxHeight; 
    size_t curHeight; 
    RandomHeight* randGen; 
}; 
template <typename Key_T, typename Mapped_T, size_t MaxLevel> 
SkipList<Key_T,Mapped_T,MaxLevel>::SkipList() : curHeight (1), maxHeight(MaxLevel) , probability (1.0/MaxLevel) 
{ 
    randGen = new RandomHeight(MaxLevel,probability); 

    // Create head and tail and attach them 
    head = new Iterator<Key_T,Mapped_T> (maxHeight); 
    tail = new Iterator<Key_T,Mapped_T> (maxHeight,true); 
    for (int x = 1; x <= maxHeight; x++) 
     head->fwdNodes[x] = tail; 
} 

template <typename Key_T, typename Mapped_T, size_t MaxLevel> 
SkipList<Key_T,Mapped_T,MaxLevel>::~SkipList() 
{ 
// Walk 0 level nodes and delete all 
    Iterator<Key_T,Mapped_T>* tmp; 
    Iterator<Key_T,Mapped_T>* nxt; 
    tmp = head; 
    while (tmp) 
    { 
    nxt = tmp->fwdNodes[1]; 
    delete tmp; 
    tmp = nxt; 
    } 
    delete randGen; 
} 

我的问题是在下面的插入功能：

template <typename Key_T, typename Mapped_T, size_t MaxLevel> 
std::pair<Iterator<Key_T,Mapped_T>, bool> SkipList<Key_T,Mapped_T,MaxLevel>::insert(const ValueType &input) 
{ 
    Key_T k = input.first; 
    Mapped_T o = input.second; 
    int lvl = 0, h = 0; 
    Iterator<Key_T,Mapped_T>** updateVec = new Iterator<Key_T,Mapped_T>* [maxHeight+1]; 
    Iterator<Key_T,Mapped_T>* tmp = head; 
    Key_T cmpKey; 

    // Figure out where new node goes 
    for (h = curHeight; h >= 1; h--) 
    { 
    cmpKey = tmp->fwdNodes[h]->getKey(); 
    while (!tmp->fwdNodes[h]->isTail() && cmpKey < k) 
    { 
     tmp = tmp->fwdNodes[h]; 
     cmpKey = tmp->fwdNodes[h]->getKey(); 
    } 
    updateVec[h] = tmp; 
    } 

    tmp = tmp->fwdNodes[1]; 
    cmpKey = tmp->getKey(); 

    // If dup, return false 
    if (!tmp->isTail() && cmpKey == k) 
    { 
    delete updateVec; 
    return std::pair<Iterator<Key_T,Mapped_T>, bool> (NULL,false); 
    } 
    else 
    { 
    // Perform an insert 
    lvl = randGen->newLevel(); 
    if (lvl > curHeight) 
    { 
     for (int i = curHeight + 1; i <= lvl; i++) 
     updateVec[i] = head; 
     curHeight = lvl; 
    } 
    // Insert new element 
    tmp = new Iterator<Key_T,Mapped_T>(k, o, lvl); 
    for (int i = 1; i <= lvl; i++) 
    { 
     tmp->fwdNodes[i] = updateVec[i]->fwdNodes[i]; 
     updateVec[i]->fwdNodes[i] = tmp; 
    } 

    delete updateVec; 
    return std::pair<Iterator<Key_T,Mapped_T>, bool> (*tmp , true); 
    } 
    delete updateVec; 
    return std::pair<Iterator<Key_T,Mapped_T>, bool> (NULL,false); 
} 

有什么不对呢？经过很长时间的调试，我无法弄清楚。以下代码给出了内存转储错误！

std::pair < Iterator<int,float>,bool> a = s.insert(std::pair<int,int>(1,1)); 
    s.insert(std::pair<int,int>(2,1)); 
    s.insert(std::pair<int,int>(3,2)); 

Answer 1

您的迭代器实现违反Rule of three。如果您创建副本或分配迭代器，您将得到2个迭代器，其中fwdNodes指向相同的内存位置。一旦删除其中一个，另一个将以fwdNodes指向已释放的内存。