1

我正在开发自己的跳过列表模板类。以下是它的规格：Iterator类保存单个跳过列表的副本。Head 和 Tail 迭代器始终为空，tail 迭代器的 tail 值设置为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));
4

1 回答 1

2

您的迭代器实现违反了规则三。如果您创建或分配迭代器的副本，您将获得 2 个fwdNodes指向相同内存位置的迭代器。一旦其中一个被删除，另一个最终将fwdNodes指向已经释放的内存。

于 2013-04-17T14:27:23.937 回答